进程

在计算机的系统管理器中，可以看到当前计算机中的进程信息

进程与线程

进程的概念

目前，程序大多都是并行执行的，那么每个程序自身的代码信息和变量信息（状态信息）如何保存下来？操作系统又如何对每个代码信息和变量信息进行管理？
为了解决这个问题，引入了进程的概念
进程实体可以分成三部分，分别是：程序段、数据段和进程控制块（PCB）

• 程序段：用来保存程序的代码信息
• 数据段：保存程序的状态信息（比如变量的值、寄存器信息）
• PCB：描述进程的基本情况和运行状态，是进程存在的唯一标识

进程和进程实体

进程强调的是一种运行时的概念（状态），是系统进行资源分配和调度的一个独立单位。一般来说，我们认为进程实体就是实体。

在严格意义下，进程实体和进程并不相同。进程实体是静态的，而进程是动态的。因此，也可以说：进程是由程序段、数据段和PCB三部分组成的。

进程的组织方式

进程的组织方式可以按照结构的不同，分为链接方式和索引方式：

1. 链接方式：按照不同进程的状态将PCB划分为多个队列，并且操作系统持有不同状态队列的指针，比如就绪队列的指针等，通过这些指针可以获取到每个进程的PCB
2. 索引方式：根据不同进程的状态建立几张索引表，操作系统持有指向各个索引表的指针。

进程的特征

1. 动态性
2. 并发性
3. 独立性
4. 异步性

进程的状态和转换

通常进程有如下5种状态，前3种是进程的基本状态

1. 运行态：进程正在处理机上运行。在单处理机中，每个时刻只能有一个进程处于运行态。
2. 就绪态：进程获得了除处理机以外的所有资源，只要获得了处理机，就可以立即运行。
3. 阻塞态：进程正在等待某一事件而暂停运行，比如等待某个资源可用，或等待输入/输出的完成。
4. 创建态：进程正在被创建，创建PCB的过程。
5. 结束态：进程正在被撤销，撤销PCB的过程。

• 运行态到阻塞态是进程自身做出的主动行为。
• 阻塞态到就绪态对进程来说是被动的行为。
• 不能直接由阻塞态直接转换为运行态，也不能由就绪态直接转换为阻塞态。
• 当资源分配到位，或者等待的事件完成之后，处于阻塞态的进程就会自动进入就绪态，等待处理机的处理。

进程调度算法

等待时间：开始时间-提交时间 周转时间：完成时间-提交时间 带权周转时间：周转时间/运行时间

FCFS策略

FCFS：First Comming First Service

既可以用于作业调度，也可以用于进程调度。

• 在作业调度中，每次都从后备作业队列中选择最先进入该队列的一个或者几个作业，将他们调入内存，分配必要的资源，创建进程并放入就绪队列中。
• 在进程调度中，每次从就绪队列中选择最先进入该队列的进程，将处理机分配给它，使之可以投入运行。

直接按照到达的先后顺序进行调度

SJF策略

如果题目没有明确指出，那么默认的SJF策略指的是非抢占性的

非抢占式

用于进程调度的应该称为：短进程优先调度算法（SPF）

短进程优先调度算法是非抢占式的，每次调度的时候都选择当前已到达并且运行时间最短的作业/进程 如果两个进程的运行时间相同，那么就优先运行到达时间较早的进程

如上图所示，按照短进程优先调度算法的要求，调度顺序依次是：P1->P3->P2->P4

抢占式

抢占式，顾名思义就是进程之间会存在争抢CPU处理机的情况 最短剩余时间优先算法：每当有进程加入，导致就绪队列发生改变时就需要进行调度。

• 如果新到达的进程所需运行时间比当前运行的进程剩余时间更短，那么就由新进程抢占处理机，当前运行进程重新回到就绪队列。
• 如果新到达的进程所需运行时间比当前运行的进程剩余时间要长，那么原进程依旧持有处理机，而新到达的进程进入就绪队列。

文字不太好理解，具体过程可以参考上图示例：

抢占式的调度大概率会导致进程中间间断执行。虽然进程是间断执行了，但是计算时间的时候还是按照公式中的定义来计算。比如上图中的P1进程，周转时间还是结束时间16-到达时间0=16

HRRN策略

HRRN：Highest Response Ratio Next高响应比优先算法

非抢占式的算法，因此只有当前运行的作业/进程主动放弃处理机的时候，才需要进行调度并计算响应比。
在每次调度的时候先计算各个作业/进程的响应比，选择当前响应比最高的作业/进程，调用处理机为其服务。

当两个进程的运行时间相同的时候，一定会优先调用到达时间早的进程 当两个进程的等待时间相同的时候，需要服务时间短的进程优先

前三种小结

RR时间片轮转调度策略

时间片轮转调度：时间片即为CPU调度的最短时间。某个进程在使用完一个时间片之后，即使进程并没有执行完成，它也必须要释放（被剥夺）处理机的使用权，给下一个就绪线程，被剥夺的未完成进程将会返回到就绪队列的队尾重新排位，等候再次运行。

一些规定：

• 如果在某个时间节点，某个进程的时间片结束，同时有一个新的进程进入，那么视为新的进程先进入队列，而后刚刚结束的进程再重新排入队列尾部
• 如果就绪队列为空，那么就让上一个执行线程再执行一个时间片

时间片轮转调度算法主要用于分时系统，并且时间片的选择并不是随意设定的，如下所示：

假设现在各个进程的到达时间和运行时间如下图所示：

当我们将时间片分别设置为：2和5的时候，调度情况如下所示：

时间片大小为2

时间片大小为5

结论：时间片的大小需要根据实际情况而具体分析，太大或太小都会导致进程的执行（调度）效率降低。

优先级调度策略

优先级调度策略：为每一个进程都分配一个优先级，调度机会优先调用优先级最高的作业或者线程。如果两个进程的优先级相同，那么就会优先调用到达时间早的进程。 优先级调度分为抢占式和非抢占式：

1. 非抢占式：只有当进程主动放弃处理机的时候才会进行重新调度。
2. 抢占式：除了进程主动放弃处理机以外，当就绪队列发生变化的时候也会重新进行调度。

下面就非抢占式和抢占式两种，举例进行说明：
各个进程的到达情况如下图所示：

非抢占式

抢占式

如何合理的设置不同进程的优先级？

根据优先级是否可以动态的改变，可以将优先级分为：静态优先级和动态优先级

• 静态优先级：创建进程的时候就已经确定，并且后续不再改变
• 动态优先级：创建进程的时候会有一个初始值，之后在进程的调度过程中，会动态地调整进程的优先级。

动态优先级如何合理的变化？

• 如果某个进程长时间在就绪队列中等待，可以适当提升其优先级。
• 如果某个进程长时间抢占处理机，可以适当降低其优先级
• 如果某个进程长时间进行IO操作，可以适当提升优先级

多级反馈队列策略

• 多级反馈队列调度算法是集成了前面几种算法的优点于一身，缺点在于需要很 复杂的硬件设施来支持其工作。
• 此调度算法既有抢占式，也有非抢占式，但是一般我们默认为抢占式的算法。
• 多级反馈队列设置多个就绪队列，各个队列优先级从高到底，时间片长度从小到大。
• 新进程到达的时候先进入第1级队列，按照FCFS原则排队等待分配时间片。如果用完了时间片，进程还未结束，那么进程就进入下一级队列。如果此时已经处于最低级队列中，那么就重新放回最低级队列。
• 对于抢占式的多级反馈调度算法，如果某个进程在占用时间片运行的过程中，某个新的较高优先级的进程进入了就绪队列，那么就会抢占处理机。未处理完的进程重新进入其所在就绪队列，处理器分配给新进来的进程进行处理。

后三种总结

后三种调度算法更适用现代的交互式系统。

进程同步和互斥

概念

进程同步

计算机对进程进行调度的时候，因并发性带来了异步性。有的进程之间需要相互配合的完成工作（具有一定的先后顺序），各个进程的工作推进需要遵循一定的先后顺序。这就需要进程同步来解决这种异步问题。

使计算机中的异步进程按照某种期望的顺序执行

进程互斥

对临界资源的访问，需要互斥地进行。同一时间段内只允许一个进程访问某资源。
按照规则的不同，可以分为以下4个部分

• 进入区：主要执行上锁操作
• 临界区：对临界资源进行操作
• 退出区：主要执行解锁操作
• 剩余区：其他的代码部分

进程互斥需要遵循以下原则：

• 空闲让进
• 忙则等待
• 有限等待：避免饥饿现象
• 让权等待：进入不了临界区的进程，要及时释放处理机，避免忙等待（占用处理机，但是一直不执行任务）

  进程互斥的实现

  软件实现

  

  单标志法

  使用一个标志变量来标志当前允许哪个进程访问临界区资源，如果当前允许的进程号和本进程的进程号不匹配的话，那么就循环等待，不能访问临界区资源。

存在的问题：使用这种方法的话，所有进程就只能按照一种顺序执行（比如上面就只能P0-P1-P0-P1）。但是如果P0一直不访问临界区的话，虽然临界区是空闲的，但是其他线程（比如P1）仍然不可以访问。违背了“空闲让进”的原则

双标志先检查法

设置一个布尔数组flag[]，数组中各个元素用来标记各个进程想进入临界区的意愿。 每个进程在进入临界区之前都先要检查当前是否有其他的进程想要进入临界区，如果没有的话，将自身的意愿标记为true，然后再访问临界区。在访问完成之后，再将自身资源标记为false

和单标志法对比：由于使用的是两个变量来控制，因此不会违背“空闲让进”原则：比如可以出现P0-P1-P1-P1这样的调度顺序。
存在的问题：由于处理机调度的不确定性，导致进程执行的异步性，这种方法可能会导致两个进程同时访问临界区。（如上图所示，假设我们按照1、5、2、6的顺序执行，那么就会导致同时访问临界区）违背了“忙则等待”的原则

双标志后检查法

和双标志先检查法对比：在先检查法中，由于检查和上锁这两个步骤不是原子操作，可能存在异步执行的问题，从而导致两个进程可能同时进入临界区。而后检查法，是先上锁，然后再检查，从而来避免上述问题。
存在的问题：后检查法可能导致“饥饿”现象（比如上图如果执行顺序为：1、5、2、6），那么就会导致两个进程都进入循环等待的结果。

Peterson算法

除了使用bool数组来标志当前是哪一个进程想要访问临界区资源以外，还使用一个变量来表示当前偏向于让哪个进程去访问临界区资源。 当某个进程想要访问临界资源，或当前更偏向于让这个进程访问临界资源时（这往往是由另外一个进程所造成的），此才能访问临界区资源，否则循环等待。

硬件实现

基于硬件实现可以避免非原子性操作带来的异步执行问题

信号量

信号量机制也是功能很强的一种机制，可以用来解决互斥与同步问题，它只能被两个标准的原语Wait(S)和Signal(S)访问，也被记作是“P操作”和“V操作”。

原语是指完成某个任务且不被分割、中断的操作序列，通常可以使用硬件来实现。 在非原语化的操作中，对某个变量的操作过程可能会被打断，去运行另一个对同一变量的操作过程，从而出现临界段的问题。

整型信号量

用一个表示资源数目的整型量S来表示资源可用的数目，wait和signal操作可以描述为如下所示代码段

wait(S) {
    while(s <= 0);
    s = s - 1;
}
signal(S) {
    S = S + 1;
}

但是在wait操作中，如果S <= 0，那么就会一直在while中循环等待。因此，该机制并未遵循“让权等待”的准则。

记录型信号量

记录型信号量机制是一种不存在“忙等”的线程同步机制。除了需要一个用于代表资源数目的整型变量value以外，还需要维护一个等待进程链表L，用于链接所有等待该资源的进程。大概类型如下所示：

typedef struct {
    int value;
    struct process* L;
} semaphore;

两个原语：

block：进行自我阻塞，主动放弃处理机，并将进程插入到等待队列中 wakeup：将等待队列中的第一个进程进行唤醒

使用信号量实现同步

如果P2先执行到P(s)的时候，S为0，那么执行P操作会把进程P2阻塞，并放入阻塞队列； 当进程P1中的x执行完之后，执行V操作，从而可以将进行P2wakeup，继续执行后续操作

可以使用一段代码来模拟上述场景

如果不采取同步措施，那么执行结果为：0

如果采用了同步措施，那么结果为：60

使用信号量实现进程互斥

使用信号量实现前驱关系

将每一对前驱关系都看作是一个同步问题 在前操作之后对相应的同步变量执行V操作 在后操作之前对相应的同步变量执行P操作

生产者、消费者问题

唯一生产者和唯一消费者

描述：一组生产者进程和一组消费者进程共享一个初始为空、大小未n的缓冲区，并且需要遵循如下要求：

• 只有当缓冲区没有满的时候，生产者才能将消息放入缓冲区内，否则必须等待
• 只有当缓冲区不为空的时候，消费者才能从中取出消息，否则必须等待
• 临界区属于共享资源，因此同一时间内，只允许一个生产者放入消息，或一个消费者取出消息

  根据分析就可以知道这里一共存在3组PV操作 定义三个整型信号量：

  • semaphore mutex=1 临界区互斥信号量
  • semaphore empty=n 表示当前空缓冲区的个数，初始为n
  • semaphore full=0 表示当前非空缓冲区的个数，初始为0

  1. 生产者在生产消息前：要执行p(empty)和p(mutex)，然后执行生产部分的代码，执行完毕后，再执行v(mutex)和v(full)
  2. 消费者在消费消息前：要执行p(full)和p(mutex)，然后执行消费部分的代码，执行完毕后，再执行v(mutex)和v(empty)
  3. 不论是生产者还是消费者，在执行操作前，都需要申请获取临界区互斥信号量的权限。

能不能改变p(empty)和p(mutex)之间的顺序？

如果empty=0,full=n，那么当按照1、2、3、4的顺序执行时，执行到2的时候，producer会因为当前缓冲区中没有为空的块，所以会进行等待。而当consumer掌握处理机时，由于producer未对临界区信号量执行v操作，所以会停止在3号操作，从而两个进程陷入死锁。

多生产者和多消费者

同步操作：

• 爸爸放苹果的行为，肯定在女儿吃苹果之前（同步操作）
• 妈妈放橘子的行为，肯定在儿子吃橘子之前（同步操作）
• 只有当盘子为空的时候，父亲或者父亲才能够放入水果，可以由女儿或者儿子触发（同步操作）

互斥操作：

• 对缓冲区（盘子）的访问要互斥进行（爸爸和妈妈不能同时放水果）

因此需要设置四个整型信号量：

• Mutex：临界区的互斥信号量，初始为1
• Orange：橘子个数的信号量，初始为0
• Apple：苹果个数的信号量，初始为0
• Plate：表示盘子个数的信号量，初始为1

对各个信号量执行PV操作如下：

但是由于这里只有一个缓冲区（盘子），因此其实可以不需要mutex这个互斥信号量（三个p操作同一时刻最多只有一个能执行）。 但是如果有多个缓冲区，那么不仅需要使用mutex信号量来保持互斥性，并且对plate的p操作要在对mutex的p操作之前

哲学家问题

和前面的资源共享问题所不同的是，这个问题相当于两个进程之间一共有两个共享资源。

• 哲学家和左右邻居对其中间筷子的访问是互斥关系
• 造成资源共享会出现问题的原因
  • 筷子数目不够（很直接的原因）
  • 取筷子不是原子操作：本题中，取左右两个筷子并非是原子操作，如果能同时取两个筷子而不被打断，那么就可以避免饥饿或者死锁

因此，我们需要对科学家的操作进行限制，定义信号量数据chopstick[5]={1,1,1,1,1}，用于对5个筷子的互斥访问。哲学家按照顺序编号为：0~4，哲学家左边筷子的编号为：i，右边筷子编号为（i+1）%5

但是当五个哲学家同时想进餐的时候，每个人都先拿起自己左边的筷子，然后等待别人将右边的筷子进行归还，从而陷入死锁。

因此我们还需要对哲学家的动作进行限制：

1. 最多允许4名哲学家同时进餐
2. 当且仅当左右两边的筷子都可用的时候，才允许他拿起筷子
3. 对于编号为奇数的科学家，要求他先拿起左边的筷子，然后拿右边的筷子。编号为偶数的则刚好相反。

管程

死锁

死锁、饥饿和死循环

死锁的条件

预防死锁

产生死锁的必要条件：

• 互斥条件：对资源进行排他性使用，在一段时间内，某资源只能为一个进程所占有，此时如果有其他的进程请求该资源，那么请求进程就只能等待。
• 不剥夺条件：进程所获得的资源在未使用完之前，不能被其他的进程强行夺走，只能由获得该资源的进程主动释放。
• 请求并保持条件：进程本身已经保持了至少一个资源，但又提出了新的资源请求，而该资源已经被其他的进程所占有，此时请求进程被阻塞，但是对自身所获得的资源保持不放。
• 循环等待条件：存在一种进程资源的循环等待链，链中的每个资源都同时被链中的下一个进程所请求。

要预防死锁，其实就是对产生死锁的四个必要条件进行预防：

破坏互斥条件

顾名思义，就是让某些资源能够同时被共享使用。但是，有的资源很显然不能同时访问，比如打印机等临界资源只能够互斥使用。所以，破坏互斥条件来预防死锁的方法不太可行，在有的场景下我们甚至要保护这种互斥性。

破坏不剥夺条件

当某个进程已经获得了部分资源，而在请求新的资源但得不到满足的时候，它必须要释放已经保持的所有资源，待以后需要的时候再重新申请。

• 该策略实现起来比较复杂，释放已获得的资源可能造成已完成的工作失效
• 反复申请和释放系统资源会增加系统的开销
• 比较适合CPU的寄存器和内存资源，不太适合打印机之类的资源

破坏请求并保持条件

使用预先静态分配的方式，进程在运行前，一次性申请它需要的所有资源，在需要的资源未被满足前，不将它投入实际运行。一旦投入了运行，那么这个资源就一直归其所有。

这种方式实现简单，但缺点在于：

• 系统的资源容易被浪费：有些资源可能在运行初期或者运行快结束时才会被使用，全程控制这些资源，会导致利用率降低。
• 可能导致饥饿现象

破坏循环等待条件

小结

避免死锁（银行家算法）

安全序列

安全与否，其实是看当前所拥有的资源，在后续的分配中，会不会出现无法满足任何一个进程的最大需求的情况

之所以考虑最大需求，是因为我们要考虑的是最坏的情况

如果在后续的分配中，可能会出现无法满足任何一个进程的最大需求的情况，那么这就是一种不安全序列。如果能让每个进程都顺利完成，那么就是一种安全序列。

如上所示，假设现在共有三种资源，并且三种资源的剩余量分别为：(m,n,p)，进程P0的资源分配情况如下所示：

• 如果现有资源(m,n,p)可以满足进程P0最多还需要（7,4,3）的需求，那么由于进程使用完资源后会将占用的资源全部进行归还，因此可用资源就变成了(m,n+1,p)
• 如果不能满足，那么就说明当前系统资源不能分配给这个进程（一旦分配给这个进程，可能会导致其他进程需要的资源无法得到满足，从而出现死锁现象）

对每个进程，依次执行上述操作，从而看能否得到一串安全序列。

• 如果可以得到安全序列，那么就说明当前系统处于安全状态
• 如果不可以，那么就说明当前系统处于不安全状态，很有可能出现死锁

银行家算法

死锁检测和解除

死锁检测

• 使用某一种数据结构来保存资源请求和分配信息。
• 提供一种算法，利用上述保存的信息来检测系统是否已经进入死锁状态。

如何根据资源分配图来检测是否发生了死锁？

如果能将资源分配图中的所有边都进行消除，那么就说明没发生死锁。 反之，则很有可能是会发生死锁

比如上图中，由于R1资源已经全部分配出去了，因此此时P2再次申请R1资源是无法完成的，从而P2会阻塞。
而P1进程的资源已经全部申请到，因此可以正常进行，而当P1正常执行完毕之后，将资源归还给R1和R2，这时已经可以满足P2的执行条件，从而唤醒P2进程，最终P1和P2进程都执行完毕，图中所有边都可以消去。

死锁解除

小结

练习题

一、

1. 如果系统中没有运行进程，是否一定就没有就绪进程，为什么？

   是的，因为如果一旦有就绪进程，那么在很短的时间内就会有处理机来对其进行处理，从而变成运行进程。

2. 如果系统中既没有运行进程，也没有就绪进程，系统中是否就没有进程？为什么？

   不一定，有可能所有的进程都处于等待状态，比如出现死锁的情况。

3. 在采用优先级进程调度时，运行进程是否一定是系统中优先级最高的进程？

   不一定，如果优先级较高的进程由于某些原因，比如等待IO或其他资源而阻塞，那么处理机就会优先处理优先级较低的进程。

二、现代操作系统一般都提供多进程（或称多任务）运行环境，回答以下问题：

1. 为支持多进程的并发执行，系统必须建立哪些关于进程的数据结构？

   为支持多进程的并发执行，系统为每个进程都建立了一种数据结构：进程控制块（PCB）。

2. 为支持进程状态的变迁，系统至少应该提供哪些进程控制原语？

   每个进程都具有以下几种状态

   • 创建态
   • 就绪态
   • 运行态
   • 终止态
   • 阻塞态

   而对进程状态的切换，使用的是操作系统所提供的的原语，进行的原子化操作。按照功能的不同，可以将原语分为如下几种：

   • 创建原语
   • 唤醒原语
   • 阻塞原语
   • 终止原语

3. 执行每个进程控制原语时，进程状态发生什么变化？相应的数据结构发生什么变化？

   创建原语：申请一个空的PCB，并将进程携带的一些参数添加到该PCB中，并将新进程的状态设置为就绪态 终止原语：回收进程所使用的资源，消去进程的PCB信息 阻塞原语：将进程的状态从运行态变为阻塞态。进程被插入阻塞队列。 唤醒原语：将进程的状态从阻塞态变为就绪态。进程从阻塞队列中移出，插入就绪队列中，等待处理机的调度。