0x00 进程的基本概念

在多道程序环境下，允许多个程序并发执行，此时他们将失去封闭性，并具有间断性和不可再现的特性，为此引入进程的概念。同时为了使并发的程序和数据能独立地运行，必需为其单独配置一个进程控制块（PCB），系统利用进程控制块来描述进程的基本情况和运行状态，进而控制和管理进程。相应地，由程序段、相关数据段和PCB三部分构成了进程映像（进程实体）。创建进程即为创建进程映像中的PCB，撤销进程实质上也是撤销的进程的PCB。由此也说明了PCB是进程存在的唯一标识。进程映像是静态的，进程则是动态的。

进程的基本特征：

动态性：即为进程有着创建、活动、暂停、终止等过程，具有一定的生命周期。
并发性：指的是多个进程实体同存在于内存中，内在一段时间内同时运行。
独立性：指进程实体是一个能独立运行、独立获得资源和独立接受调度的基本单位。凡未建立PCB的程序都不能作为一个独立的单位参与运行。
异步性：进程具有执行的间断性，即进程按各自独立的、不可预知的速度向前推进。异步性会导致执行结果的不可再现性，为此操作系统必须配置相应的进程同步机制。
结构性：每个进程都有一个PCB对其进行描述，从结构上看，进程实体是由程序段、数据段和进程控制段三部分组成。

其中，动态性是进程最基本的特征。

进程的状态与转换：

运行状态
就绪状态：进程得到了除处理机以外的一切所需资源已处于准备运行的状态。一旦得到处理机就可以运行。处于运行状态的进程时间片用完之后不得不让出处理机，此时进程就由运行状态转化为就绪状态。
阻塞状态：又称等待状态，进程正在等待某一时间而暂停，例如等待用户输入
创建状态：进程正在被创建，尚未转到就绪状态，进程的创建往往具有多个步骤：首先申请一个空白的PCB，并向PCB中填写一些控制和管理进程的信息，然后系统为该进程分配所需的资源，最后把该进程切换到就绪状态。
结束状态：当进程需要结束运行时，系统首先将其置为结束状态，然后进一步处理资源释放和回收工作。

进程的状态的常见应用：

用户态：Trap指令（从内核态到用户态的入口）
内核态：设置定时器的初值（时钟管理），内存单元复位，中断机制的实现

0x01 进程控制

0x00 进程创建

操作系统允许一个进程创建另一个进程，而且允许子进程继承父进程所拥有的资源，当子进程被撤销时，其在父进程处继承的资源应当还给父进程。同时，撤销父进程时同时也会撤销其所有的子进程。创建进程的过程如下（创建原语）：

为新进程分配一个唯一的进程标识号，并申请一个空白的PCB，PCB是有限的，若申请失败则创建失败
为进程分配资源，此处如果资源不足，进程就会进入等待状态，以等待资源
初始化PCB
如果进程的调度队列能够接纳新进程，那就将进程插入到就绪队列，等待被调度运行

0x01 进程终止

进程可以有3种终止方式：正常结束、异常结束以及外界干预（任务管理器）。

操作系统终止进程的过程如下（撤消原语）：

根据被终止进程的标识符，检索PCB，从中读出该进程的状态
若处于执行状态，则立即终止该进程的执行，然后将处理机资源分配给其他进程
若其还有子进程，则应将其所有子进程终止
将该进程所拥有的全部资源都归还给父进程或操作系统
将其从PCB所在队列中删除

0x02 进程的阻塞和唤醒

阻塞原语：

找到将要被阻塞进程标识号对应的PCB
若其为运行状态，则保护其现场，将其状态转为阻塞状态，停止运行
将该PCB插入到相应时间的等待队列中去

唤醒原语：

在该事件的等待队列中找到相应进程的PCB
将其从等待队列中移出，并置其状态为就绪状态
把该PCB插入到就绪队列中，等待调度程序调度

注意阻塞原语是由被阻塞进程自我调用实现的，而唤醒原语是一个由与被唤醒进程相合作或被其他相关进程调用实现的。

0x03 进程切换

进程切换过程如下：

保存处理机上下文，包括程序计数器和其他存储器
更新PCB信息
把进程的PCB移入响应的队列
选择另一个进程执行并更新其PCB
更新内存管理的数据结构
恢复处理机上下文

进程切换与处理机的模式切换要注意区分哦。进程切换时是进程变了，处理机模式切换后可能还处在同一进程中。

0x02 进程的组成部分

0x00 进程控制块PCB

进程创建后操作系统就会创建一个新的进程控制块，此后就常驻内存。在任一时刻可以存取，进程结束时删除。PCB是进程实体的一部分是进程存在的唯一标识。下面说一下PCB的主要组成部分：

进程描述信息
- 进程标识符：标识各个进程，每个进程都有一个并且唯一的标识符
- 用户标识符：进程归属的用户，用户标识符主要为共享和保护服务
进程控制和管理信息
- 进程当前状态
- 进程优先级：进程抢占处理机时的优先级
资源分配清单：说明有关内存地址空间或虚拟地址空间的状况，所打开文件的列表和所使用的I/O设备信息
处理机相关信息：处理机中各个寄存器的值，当进程被切换时，处理机的状态信息都会被保存在响应的PCB中，以便进程重新执行时，能从断点处继续执行

目前操作系统中有2种方式来组织各个进程的PCB，即为链接方式和索引方式：

链接方式：将处于同一状态的PCB链接成一个队列，不同的状态对应不同的队列
索引方式：将同一状态的进程组织在一个索引表中，索引表项指向相应的PCB，不同状态对应不同的索引表

0x01 其他

程序段：就是能被进程调度程序调度到CPU执行的程序代码段

数据段：进程对应程序加工处理的原始数据或者执行时产生的中间数据或者结果。

0x03 进程的通信

在这只写高级通信方法：

共享存储：两个互相通信的进程之间存在一块可直接访问的共享空间以实现信息的交换。在对共享空间进行读写操作时，需要使用同步互斥工具对读写进行控制。共享存储又分为两种方式：基于数据结构共享的低级方式以及基于存储区共享的高级方式。
消息传递：进程通过系统提供的发送消息和接受消息两个原语进行数据交换：
- 直接通信方式：发送进程把消息直接发送给接受进程，并将其挂在接受进程消息缓冲队列上
- 间接通信方式：发送进程消息把消息发送到某个中间实体，然后接收方再从中间实体出取得
管道通信：管道是指用于连接一个读进程和一个写进程以实现其互相同通信的一个共享文件，从管道中读数据是一次性的操作，数据一旦被读取即会从管道中删除。由此，管道通信是半双工通信。

0x04 处理机调度

处理机调度是多道程序操作系统的基础。

0x00 三层调度

一个作业从提交到完成，往往需要经过如下的三层调度：

作业调度：又称高级调度，从外存中挑选一个或多个作处于后备状态的作业，给他们分配内存、I/O设备及必要的资源，并建立相关进程以使他们获得竞争处理机的权利，对于每个作业只调入一次，调出一次。
中级调度：又称内存调度，引入中级调度是为了提高内存利用率和系统吞吐量，为此应使那些暂时不能运行的进程调至外存等待，把此时的进程称之为挂起状态，当他们具备运行条件且内存稍有空闲时，由中级调度来决定把外存上那些已具备运行条件的就绪进程再重新调入内存，并修改其状态为就绪状态。
进程调度：又称为低级调度，主要任务是按照一定的方法和策略从就绪队列中选取一个进程，将处理机分配给它，进程调度是操作系统最基本的调度，而且执行的频率很高。

作业调度首先从外存的后备队列中选择一批作业进入内存，为它们建立进程，然后将其送入就绪队列，进程调度再从就绪队列中选择一个进程，将其状态改为运行状态并为其分配处理机，中级队列为了提高系统中的内存使用率，将那些暂时不能运行的进程置于挂起状态，当内存空间宽松时，通过中级调度选择具备运行条件的进程，将其唤醒。

其中，作业调度次数少，中级调度次数略多，进程调度频率最高。

0x01 调度的时机

一般情况下，当请求调度的事件发生之后，才可能会运行进程调度程序，当调度了新的就绪进程之后，才会去进行进程间的切换，理论上这三件事情应该是顺序执行的，但是在实际的设计中，当发生如下情况时，不能进行进程的调度与切换：

在处理中断的过程中：中断处理是系统工作的一部分，逻辑上不属于某一进程，不应该剥夺处理机资源
进程在操作系统内核程序临界区：进入临界区后，需要以独占的方式访问共享数据，理论上需要加锁，防止其他程序并行进入，在解锁前不应切换到其他程序运行，以加快该共享数据的释放
其他需要完全屏蔽中断的原子操作：例如加锁解锁、中断现场保护，在原子过程中，连中断都要屏蔽，更不能进行进程的调度和切换。

发生进程调度和切换的场景有：

当前进程无法继续进行，可以马上进行调度和切换，如果操作系统仅在这种情况下进行调度，那就是非剥夺调度。
当中断处理结束或自陷处理结束，返回被中断进程的用户态程序执行现场前，若置请求调度标识，即可马上进行进程调度和切换，这就实现了剥夺方式的调度。

0x02 调度方式

进程调度指的是当某一个进程在处理机上运行时，此时又有一个优先级更高的进程进入了就绪队列，处理机的调度方法，一般由如下两种：

非剥夺调度，又称非抢占式调度，更高优先级的进程进入就绪队列后，也啥也不管，仍然让当先处理机运行的进程执行，直到其完成或者进入阻塞状态，才会把处理机再分配给优先级更高的进程
剥夺调度，又称抢占式调度，更高优先级的进程进入就绪队列后，马上暂停正在执行的进程，把处理机分配给这个更重要的进程，采用剥夺调度方式对提高系统吞吐率和响应效率都有明显的好处

0x03 调度基本原则和衡量参数（评价标准）

CPU利用率：应当尽可能使CPU保持忙的状态，使这一资源利用率最高
系统吞吐量：表示单位时间内CPU完成作业的数量，长作业需要消耗较长的处理机时间，因此会降低系统的吞吐量，相反，短作业会提升系统吞吐量
周转时间：表示从作业提交到完成所经历的时间，可有如下几种：

$周转时间=作业完成时间-作业提交时间\\ 平均周转时间=\frac{\sum_{i=1}^n{作业i的周转时间}}{n}\\ 带权周转时间=\frac{作业周转时间}{作业实际运行时间}\\ 平均带权周转时间=\frac{\sum_{i=1}^n{作业i的带权周转时间}}{n}\\$
等待时间：进程等待处理机状态时间的总和，等待时间越长，用户就越不满意，处理机的调度算法其实并不影响作业的执行以及I/O操作所需的时间，而只影响其在就绪队列中等待所花费的时间，所以，考查一个调度算法的优劣，只需简单地考查进程的等待时间即可。
响应时间：用户提交请求到系统第一次产生响应所花费的时间，在交互式系统中，响应时间是衡量调度算法好坏的主要标准。

0x04 调度算法

总结练习题：进程调度算法习题

0x00 先来先服务（FCFS）

顾名思义啊，就是讲究先来后到，每次从就绪队列中选择最先进入该队列的进程然后运行，这是一种不可剥夺算法，其对所有的作业都是公平的，但是如果一个长作业先到达系统，就会使后面很多短作业等待很长的时间，因此其不能作为分时系统和实时系统的主要调度策略。

FCFS算法简单，但效率低，对长作业有利，适用于CPU繁忙型作业，而不适用于I/O繁忙型作业

0x01 短进程（作业）优先（SJF）

顾名思义，不断地从就绪队列中选择一个运行时间最短的作业，然后调入内存运行，使之立即执行。

SJF算法对长作业不利，导致长作业的周转时间会增加，如果有一长作业进入后备队列，其可能会被不断地调度到以后执行，导致长作业长期不被调度。此外，此算法未考虑作业的优先级，不能保证优先级高的会被及时处理。作业执行时间往往由用户所提供的估计时间而定，而用户可能会有意无意地缩短其所估计的时间，导致此算法不能真正地做到短进程优先调度。

SJF算法的平均等待时间、平均周转时间最少。

0x02 优先级调度算法

此算法既可以用于作业调度也可以用于进程调度，顾名思义，此算法从队列中选择一个优先级最高的算法调入内存运行，往往又有如下两种：

非剥夺式：当有优先级更高的进程进入就绪队列时，先将手头上的这个进程处理完，然后再将处理机分配给优先级更高的那个进程
剥夺式：某个优先级更高的进程进来之后，马上暂停手头上的这个进程，然后为优先级更高的那个分配处理机

进程的优先级又可以分为如下两种：

静态优先级：优先级在进程创建时确定，然后在其整个运行时间都保持不变。
动态优先级：依据进程的动态变化动态调整优先级，动态调整的策略一般有CPU占用时间长度以及就绪进程等待CPU的时间长短

优先级的选择：

I/O作业的优先级高于计算型作业的优先级：因为I/O设备没办法长时间保存输入输出信息
系统进程优先级高于用户进程
在动态优先级中，进程执行时间增加，优先级降低，作业等待时间增加，优先级升高
资源要求低的进程的优先级高于资源要求高的进程的优先级：避免死锁，因为多个资源要求高的进程同时工作容易导致死锁

优先级跟作业的长度没有任何关系

0x03 高响应比优先调度算法（HRRN）

该算法为对FCFS算法和SJF算法的一个均衡，同时等待每个作业的等待时间和估计的运行时间，每次进行作业调度时，先计算响应比，然后将响应比最高的作业投入运行，响应比计算公式为：

$R_P=\frac{等待时间+要求服务时间}{要求服务时间}$

两个作业等待时间相同时，要求服务时间越短，其响应比就越高，有利于短作业。

两个作业要求的服务时间相同时，等待时间越长，响应比就越高，此时就类似于先来先服务了。

对于长作业，作业的响应比可以随时间等待的增加而提高，当其等待时间足够长时，其响应比便可以升到很高，从而获得处理机。此时兼顾了长作业。

0x04 时间片轮转调度算法

此算法主要适用于分时系统，其设定一个时间片，然后将所有的进程按先来后到的顺序放入一个队列，从队列中选择一个程序执行，每次只执行一个时间片的时间，如果一个时间片用完了，进程还没有运行完成的话，它也必需释放处理机给下一个进程运行，而被剥夺的这个进程就会返回到就绪队列的末尾，继续排队，重新等待执行。

此算法中，时间片的大小对系统性能影响较大，如果选择地很大，以至于每个进程都可以在1个时间片内完成，那么其就相当于一个FCFS算法，如果选择地很小，大部分的时间都会被浪费在进程间的频繁切换上，使处理机的开销增大。

0x05 多级反馈队列调度算法

通过动态调整进程优先级和时间片大小，多级反馈队列可以见多多方面的系统目标，例如为提高系统吞吐量和平均周转时间而照顾短进程，为获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程，同时也不用事先预估进程的执行时间。其基本思想为：

有多个就绪队列，并为所有的就绪队列赋予不同的优先级，第1级优先级最高，然后依次往下次之，
赋予不同优先级的队列的时间片也不一样，优先级越高的，时间片越小
当一个进程进入内存后，首先将其放入第1级队列的末尾，按FCFS原则排队等待执行，在1个时间片内尚未完成，则将其转入第2级队列的末尾，以此类推
仅当第一级队列为空时，调度程序才调度第二级队列中的进程运行

其有如下优点：

对于终端型作业用户：短作业有限

对于短批处理作业用户：周转时间较短

对于长批处理作业用户：经过前几轮的部分执行，不会长期得不到处理

0x05 进程同步

0x00 基本概念

临界资源：一次仅允许一个进程使用的资源。

临界区：对于临界资源的访问必需互斥地进行，对于访问临界资源的那段代码称之为临界区。

同步：即为直接制约关系，两个或多个进程有的时候需要协调工作次序而等待。

互斥，间接制约关系，当一进程进入临界区使用临界资源时，其余进程必需等待。

为禁止两个进程同时进入临界区，同步机制应遵循如下4个原则：

空闲让进：临界区空闲，允许一个请求进入的进程进入
忙则等待：临界区已有进程使用时，其他试图进入的进程必需等待
有限等待：对于请求进入的进程应保证在有限时间内进入
让权等待：当进程进入临界区时，应当释放处理机，防止进程忙等待

0x01 信号量

PV操作是一种低级进程通信原语（不是系统调用）：

P操作（wait）：检查信号量S的值，忙等待直到其大于0，然后为信号量S-1
1
2
3
4
void wait(int S) {
S = S - 1;
while (S <= 0);
}
V操作（signal）：为信号量+1
1
2
3
void signal(int S) {
S = S + 1;
}

我们可以通过信号量来实现：

进程的同步，若期望的消息尚未产生则初值为0，否则应设置一个非0正整数
进程的互斥，初值为可用的资源数，一般为1

实例不在此一一列举。

对于互斥信号量S而言，初值为N，则当 $S \leqslant 0$ 时，有N个进程在访问资源，有 $|S|$ 个进程在等待资源。

除上述的整型信号量之外，还有一种记录型信号量：

struct Semaphore
{
    int value;
    Process *list;
};

记录型信号量是不存在忙等现象的进程同步机制，value代表资源数目，list为一个链表记录了所有等待该资源的进程。其基本PV操作如下：

void P(semaphore s)
{
    // 申请资源，边界是value已经为0了，那么现在变-1，表示有一个进程在等待
    s.value--; 
    if(s.value < 0)
    {
        // 将此进程加入就绪队列，等待
        addToList(s.L);
        block(s.L);
    }
}

void V(semaphore s)
{
    s.value++;
    if(s.value <= 0)
    {
        // 将进程P从就绪队列中移出
        removeFromList();
        wakeup(P); // 唤醒一个阻塞队列进程
    }
}

当S.value > 0时，表示某类可用资源的数量，每次P操作，意味着请求分配一个单位的资源
当S.value <= 0时，表示该资源以及没有了，其绝对值为正在等待资源的进程的数目

0x02 管程

管程是由一组数据及定义在这组数据之上的对这组数据的操作组成的软件模块，这些操作可以实现初始化并改变管程中的数据、进程间的互斥及同步，是由编程语言来支持的。其具有如下几个基本特性：

局部于管程的数据只能被局部与管程的过程访问
一个进程只有通过调用管程内的过程才能进入管程访问的共享数据
每次只允许一个进程在管程内执行某个内部过程

其基本的特征就像是对临界资源定义的一个类一样。

0x06 死锁

死锁是指多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都无法向前推进。

系统不会发生死锁的最少资源数S为：

$S=M\times(N-1)+1$

其中：

有M个进程，每个进程平均需要N台机器，S为系统不会发生死锁的最小资源数

上述公式延伸：

当有M个进程，每个进程分别需要 $N_1, N_2, ..., N_M$ 个某种资源时，如果发生死锁，所有的这M个进程都至少少一个资源，所以这M个进程至多持有 $\sum_{i=1}^{m}N_i-1$ 个资源，此时发生死锁系统无法进行下去，大家都在干等着再来一个资源，如果此时再多出1个资源，就可以打破这个僵局，让所有的进程都可以依次完成，所以系统不会发生死锁的最少资源数S为：

$S=\sum_{i=1}^{m}{(N_i-1)}+1$

当把N记作 $N_1, N_2, ..., N_M$ 的平均值时，就有了最上面的那个公式。

0x00 产生的原因

系统资源的竞争：只有对不可剥夺资源的竞争才会产生死锁，对可剥夺资源的竞争不会产生死锁。例如磁带机和打印机
进程间推进顺序非法：请求和释放资源的顺序不当继而产生死锁
信号量使用不当：例如进程1在等待进程2发来消息，进程2也在等待进程1发来消息，也会使得两个进程无法向前推进从而产生死锁

死锁产生的必要条件，产生死锁必需同时满足如下4个条件，任一条件不成立死锁都不会发生：

互斥条件
不剥夺条件：进程所获得的资源在未使用完毕的情况下不能被其他进程强行夺走，只能由获得资源的进程自行释放
请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已经被其他进程占有，此时请求被阻塞，但对已获得的资源不加以释放。
循环等待条件：存在一种进程资源的循环等待链

0x01 死锁的预防

破坏互斥条件：如果允许系统中所有的资源都能共享使用，则系统不会发生死锁，但是这种方法不太可能实现。
破坏不剥夺条件：当进程请求新的资源得不到满足的时候，其必须释放现在已有的资源，需要的时候再重新申请。这种策略实现起来较为复杂，释放已获得的资源可能造成前一段的工作失效，反复释放和请求资源又会增加处理器的开销，降低系统吞吐量。
破坏请求和保持条件：系统在运行前一次性申请完所有它所需要的资源，在资源未满足前不投入运行，一旦投入运行，这些资源就一直归他所有。这种方式会导致系统资源的严重浪费。
破坏循环等待条件：采用顺序资源分配法，每个进程必需按编号递增的允许请求资源。

0x02 死锁避免

要注意，此处的避免和上述的预防是不一样的！预防是事先采取某种措施以破坏死锁发生的4个必要条件，而避免是在资源的分配过程中，防止系统进入不安全的状态，以避免发生死锁，避免的限制条件较弱，但是可以取得较好的系统性能。

0x00 系统安全状态

避免死锁的方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程，否则，让进程等待。

当然并非所有的不安全状态都是死锁状态，但当系统进入不安全状态之后，便可能进入死锁状态，反之只要系统处于安全状态，便可以避免进入死锁状态。

0x01 银行家算法

假设资源P1申请资源，银行家算法先试探性地分配给它（当然先要看看当前资源池中的资源数量够不够），若申请的资源数量小于等于Available，然后接着判断分配给P1后剩余的资源，能不能使进程队列的某个进程执行完毕，若没有进程可执行完毕，则系统处于不安全状态（即此时没有一个进程能够完成并释放资源，随时间推移，系统终将处于死锁状态）。

若有进程可执行完毕，则假设回收已分配给它的资源（剩余资源数量增加），把这个进程标记为可完成，并继续判断队列中的其它进程，若所有进程都可执行完毕，则系统处于安全状态，并根据可完成进程的分配顺序生成安全序列（如{P0，P3，P2，P1}表示将申请后的剩余资源Work先分配给P0–>回收（Work+已分配给P0的A0=Work）–>分配给P3–>回收（Work+A3=Work）–>分配给P2–>······满足所有进程）。

如此就可避免系统存在潜在死锁的风险。注意：银行家算法所找到的安全序列不是唯一的。

0x03 死锁检测与解除

0x00 死锁的检测

系统死锁可以用资源分配（有向）图来描述，如下图：

用一个圆圈代表一个进程，用框代表一类资源，框中的一个点代表一类资源中的一个资源，从进程到资源的有向边叫请求边，表示该进程申请一个单位的资源（想要），从资源到进程的边叫做分配边（已经得到）。

上图是一个带有死锁的资源分配图，因为P2想要R2，R2又给了P3，P3又想要R3，可是2个R3在P1和P2手里。

死锁的检测就是检查的资源分配图，在资源分配图中，把分配的资源与进程连好，再看进程请求边。按照分配边分配好以后，剩余的资源就是空闲资源。此时再来分析进程Pi的请求边，如果空闲资源都能满足Pi的请求，也就意味着Pi可以从这个纠缠的图中得到解脱。删除Pi的所有相关的资源，已分配的+请求的。再递归处理剩下的资源分配图，如果资源分配图是可完全简化的，那就没有死锁，否则就满足死锁产生的条件了，这就是死锁定理。

0x01 死锁的解除

有2种办法：

剥夺资源：挂起某些死锁的进程，并抢占它的资源，然后将这些资源分配给其他死锁的进程
撤销进程：强制撤销部分乃至全部死锁进程
进程回退：让一个或多个进程回退到足以回避死锁的地步