2020-04-14

进程管理[更新中...]

1. 进程的基本概念

1.1. 程序的顺序执行及其特征

1.1.1. 程序的顺序执行

仅当前一操作（程序段）执行完后，才能执行后继操作。例如，在进行计算时，必须先输入(Input)用户的程序和数据，然后进行计算(Calculate)，最后才能打印(Print)结果。

1
2
3

S1:a : = x+y;
S2:b : = a-5;
S3:c : = b+1;

程序独占处理机顺序执行时特征：

顺序性：程序各程序段严格按照规定的顺序执行
封闭性：程序运行时机内各资源只受该程序控制而改变，执行结果不受外界因素影响
可再现性：只要程序执行环境和初始条件相同，程序多次执行，可获得相同结果

1.2. 前趋图

前趋图(Precedence Graph)是一个有向无循环图，记为DAG(Directed Acyclic Graph)，用于描述进程之间执行的前后关系。图中的每个结点可用于描述一个程序段或进程，乃至一条语句；结点间的有向边则用于表示两个结点之间存在的偏序(Partial Order)或前趋关系(Precedence Relation)”$\rightarrow$”

$\rightarrow={(P_i,P_j)|P_i\ must\ complete\ before\ P_j\ may\ start}$，如果$(P_i,P_j)\in\rightarrow$，可写成$P_i\rightarrow P_j$，称$P_i$是$P_j$的直接前趋，而称$P_j$是$P_i$的直接后继。在前趋图中，把没有前趋的结点称为初始结点(Initial Node)，把没有后继的结点称为终止结点(Final Node)。

每个结点还具有一个重量(Weight)，用于表示该结点所含有的程序量或结点的执行时间。

$$I_i\rightarrow C_i \rightarrow P_i 和 S_1\rightarrow S_2 \rightarrow S_3$$

对于上图(a)所示的前趋图，存在下述前趋关系：

$P_1 \rightarrow P_2, P_1\rightarrow P_3, P_1 \rightarrow P_4, P_2 \rightarrow P_5, P_3 \rightarrow P_5, P_4 \rightarrow P_6, P_4 \rightarrow P_7, P_5 \rightarrow P_8, P_6 \rightarrow P_8, P_7 \rightarrow P_9, P_8 \rightarrow P_9$

或表示为：

$P={P_1,P_2,P_3,P_4,P_5,P_6,P_7,P_8,P_9}\rightarrow ={(P_1,P_2),(P_1,P_3),(P_1,P_4),(P_2,P_5),(P_3,P_5),(P_4,P_6),(P_4,P_7),(P_5,P_8),(P_6,P_8),(P_7,P_9),(P_8,P_9)}$

PS: 前趋图中必须不存在循环，但在图(b)中却有着下述的前趋关系：

$$S_2 \rightarrow S_3, S_3 \rightarrow S_2$$

1.3. 程序的并发执行及其特征

1.3.1. 程序的并发执行

在该例中存在下述前趋关系：

$I_i \rightarrow C_i, I_i \rightarrow I_{i+1}, C_i \rightarrow P_i, C_i \rightarrow C_{i+1}, P_i \rightarrow P_{i+1}$

而$I_{i+1}$和$C_i$及$P_{i-1}$是重迭的，亦即在$I_{i+1}$和$C_i$及$P_{i-1}$之间，可以并发执行。对于具有下述四条语句的程序段：

S1:a: = x+2
S2:b: = y+4
S3:c: = a+b
S4:d: = c+b

程序并发执行特征:

间断性：程序在并发执行时，由于它们共享资源或为完成同一项任务而相互合作，使在并发程序之间形成了相互制约的关系。相互制约将导致并发程序具有“执行-暂停-执行”这种间断性活动规律。
失去封闭性：程序在并发执行时，是多个程序共享系统中的各种资源，因而这些资源的状态将由多个程序来改变，致使程序的运行已失去了封闭性。
不可再现性：程序在并发执行时，由于失去了封闭性，也将导致失去结果的可再现性。即程序经过多次运行，虽然其各次的环境和初始条件相同，但得到的结果却各不相同。

进程的引入：

为了提高资源利用率，系统采用多道程序设计，程序执行环境有顺序执行变为并发执行。
由于程序在并发执行时，可能会造成执行结果的不可再现，所以用“程序”这个概念已无法描述程序的并发执行，所以必须引入新的概念–进程来描述程序的并发执行，并要对进程进行必要的管理，以保证进程在并发执行时结果可再现。

1.4. 进程的特征与状态

1.4.1. 进程的特征和定义

进程这一术语最早由麻省理工学院著名的操作系统MULTICS中提出

进程(Process)定义：“可并发执行的程序在一个数据集合上的运行过程”

进程的特征：

动态性：动态性是进程的最基本特征，它是程序执行过程，它是有一定的生命期。他由创建而产生、由调度而执行、因得不到资源而暂停，并由撤销而死亡。而程序是静态的，它是存放在介质上一组有序指令的集合，无运动的含义。
并发性：并发性是进程的重要特征，同时也是OS的重要特征。并发性是指多个进程实体同存于内存中，能在一段时间内同时运行。而程序是不能并发执行。
独立性：进程是一个能独立运行的基本单位，即是一个独立获得资源和独立调度的单位，而程序不作为独立单位参加运行。
异步性：进程按各自独立的不可预知的速度向前推进，即进程按异步方式进行，正是这一特征，将导致程序执行的不可再现性，因此OS必须采用某种措施来限制各进程推进序列以保证各程序间正常协调运行。
结构特征：从结构上，进程实体由程序段、数据段和进程控制块三部分组成，UNIX中称为“进程映象”。

较典型的进程定义由：

进程是程序的一次执行
进程是一个程序及其数据在处理机上顺序执行时所发生的活动
进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位

在引入了进程实体的概念后，我们可以把传统OS中的进程定义为：“进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位”。

1.4.2. 进程的三种基本状态

运行态/执行态(Running)：当一个进程在处理机上运行时，则称该进程处于运行状态
就绪态(Ready)：一个进程获得了除处理机外的一切所需资源，一旦得到处理机即可运行，则称此进程处于就绪状态
阻塞态(Blocked)：又称挂起状态、等待状态，一个进程正在等待某一事件发生（例如请求I/O而等待I/O完成等）而暂时停止运行，这时即使把处理机分配给进程也无法运行，故称该进程处于阻塞状态

进程状态的转换：
三个基本状态之间可能转换和转换原因如下：

就绪态$\rightarrow$运行态：当处理机空闲时，进程调度程序必将处理机分配给一个处于就绪态的进程，改进成便由就绪态转换为运行态
运行态$\rightarrow$阻塞态：处于运行态的进程在运行过程中需要等待某一事件发生后（例如因I/O请求等待I/O完成后），才能继续运行，则该进程放弃处理机，从运行态转换为阻塞态
阻塞态$\rightarrow$就绪态：处于阻塞态的进程, 若其等待的事件已经发生, 于是进程由阻塞态转换为就绪态
运行态$\rightarrow$就绪态: 处于运行状态的进程在其运行过程中,因分给它的处理机事件片已用完, 而不得不让出(被抢占)处理机,于是进程由运行态转换为就绪态
阻塞态$\rightarrow$运行态和就绪态$\rightarrow$阻塞态这两种状态转换不可能发生

系统中各进程状态管理:

处于运行态进程: 如系统有一个处理机, 则在任一时刻, 最多只有一个进程处于运行态
处于就绪态进程: 一般处于就绪态的进程按照一定的算法(如先来的进程排在前面, 或采用优先权高的进程排在前面)排成一个就绪队列$RL$
处于阻塞态进程: 处于阻塞态的进程排在阻塞队列中。由于等待事件原因不同，阻塞队列也按事件分成几个队列$WL_i$

就绪队列无优先级（例：FIFO）
当事件n发生，对应队列移进就绪队列

在一个多道程序设计的系统中，各进程状态转换会互相影响。例如系统中一个运行态的进程A发生I/O请求后要等待I/O完成，它的状态也由运行态转换为阻塞态，此时进程调度程序就会按照一定的算法，在就绪队列中选一个进程B，将处理机分给它，该B进程的状态也由就绪态转换为运行态。如一个进程C等待的事件完成，则它的状态由阻塞态转换为就绪态，它也从阻塞队列中抽出插入就绪队列中。如进程C从阻塞态转换为就绪态时，有一个进程D在CPU上运行。而系统采用抢占式调度算法，进程C的优先级又高于正在CPU上运行的进程D的优先级，则要发生抢占调度。即接下去的操作由进程调度程序将正在运行的进程D由运行态转换为就绪态，插入就绪队列。

系统中各进程状态的分布实例

例：一个只有一个处理机的系统中，OS的进程由运行、就绪、阻塞三个基本状态。假如某时刻该系统中有10个进程并发执行，再略去调度程序所占用时间情况下试问：
这时刻系统中处于运行态的进程数最多几个？最少几个？
这时刻系统中处于就绪态的进程数最多几个？最少几个？
这时刻系统中处于就绪态的进程数最多几个？最少几个？

解：因为系统中只有一个处理机，所以某时刻处于运行态的进程数最多有一个，最少可能为0，此时其他10个进程一定全部排在阻塞队列中，再就绪队列中没有进程。而某时刻处于就绪态的进程数最多只有9个，不可能出现10个情况，因为一旦CPU有空，调度程序马上调度，当然这是在略去调度程序调度事件时考虑，处于阻塞态的进程数最少有0个。

1.4.3. 挂起状态

“挂起”、“激活”操作的引入：

系统管理员有时需要暂停某个进程，以便排除系统故障或暂时减轻系统负荷，用户有时也希望暂停自己的进程以便检查自己作业的中间结果。这就希望系统提供“挂起”操作，暂停进程运行，同时也要提供“激活”的操作，恢复被挂起的进程。由于被挂起前进程的状态有三种，挂起后的进程就分为二种状态：静止就绪态和静止阻塞态（有的称挂起就绪态和挂起阻塞态）。挂起前的进程就绪态和阻塞态也成为活动就绪态和活动阻塞态。

当进程处于运行态和活动就绪态时，执行挂起操作，进程状态转换为静止就绪态。当进程处于活动阻塞态时，执行挂起操作，进程状态转换为静止阻塞态。对被挂起的进程施加“激活”操作，则处于静止就绪的进程转换为活动就绪态，处于静止阻塞态的进程转换为活动阻塞态。被挂起的处于静止阻塞态的进程当它等待的事件发生后，他就由静止阻塞态转换为静止就绪态。具有以上五个状态和新增“挂起”、“激活”两个操作的进程状态图见下图所示：

进程状态的转换：

活动就绪 $\rightarrow$ 静止就绪
活动阻塞 $\rightarrow$ 静止阻塞
静止就绪 $\rightarrow$ 活动就绪
静止阻塞 $\rightarrow$ 活动阻塞

1.5. 进程控制块

1.5.1. 进程控制块的作用

进程控制块的作用是使一个在多道程序环境下不能独立运行的程序（含数据），成为一个能独立运行的基本单位，一个能与其他进程并发执行的进程。或者说，OS是根据PCB来对并发执行的进程进行控制和管理的

1.5.2. 进程控制块中的信息

进程标识符：进程标识符用于唯一地表示一个进程。一个进程通常由两种标识符
- 内部标识符：在所有地操作系统中，都为每一个进程赋予一个唯一地数字标识符，它通常是一个进程地序号。设置内部标识符主要是为了方便系统使用
- 外部标识符：他由创建者提供，通常是由字母、数字组成，往往是由用户（进程）在访问该进程时使用。为了描述进程地家族关系，还应设置父进程标识及子进程标识。此外，还可以设置用户标识，以指示拥有该进程的用户
处理机状态：处理机状态信息主要是由处理机的各种寄存器中的内容组成
- 通用寄存器：又称为用户可视寄存器，它们是用户程序可以访问的，用于暂存信息，在大多数处理机中，由8~32个通用寄存器，在RISC结构的计算机中可超过100个
- 指令寄存器：其中存放了要访问的下一条指令的地址
- 程序状态字PSW：其中含有状态信息，如条件码、执行方式、中断屏蔽标志等；
- 用户栈指针：指每个用户进程都有一个或若干个与之相关的系统栈，用于存放过程和系统调用参数及调用地址。栈指针指向该栈的栈顶
进程调度信息：在PCB中还存放一些与进程调度和进程对换有关的信息，包括：
- 进程状态：指明进程的当前状态，作为进程调度和对换时的依据
- 进程优先级：用于描述进程使用处理机的优先级别的一个整数，优先级高的进程应优先获得处理机
- 进程调度所需的其他信息：它们与所采用的进程调度算法有关，比如，进程已等待CPU的时间总和、进程已执行的时间总和等
- 事件：是指进程由执行状态转变为阻塞状态所等待发生的事件，即阻塞原因
进程控制信息：进程控制信息包括：
- 程序和数据的地址：是指进程的程序和数据所在的内存或外存(首)地址，以便再调度到该进程执行时，能从PCB中找到其程序和数据
- 进程同步和通信机制：指实现进程同步和进程通信时必需的机制，如消息队列指针、信号量等，它们可能全部或部分地放在PCB中
- 资源清单：是一张列出了除CPU以外的、进程所需的全部资源及已经分配到该进程的资源的清单
- 链表指针：它给出了本进程(PCB)所在队列中的下一个进程的PCB的首地址

1.5.3. 进程控制块的组织方式

链接方式

索引方式

2. 进程控制

2.1. 进程的创建

2.1.1. 进程图(Process Graph)

2.1.2. 引起创建进程的事件

用户登录
作业调度
提供服务
应用请求

2.1.3. 进程的创建(Creation of Progress)

申请空白PCB
为新进程分配资源
初始化进程控制块
将新进程插入就绪队列，如果新进程就绪队列能够接纳新进程，便将新进程插入就绪队列

// 进程创建原语
Procedure create(pn,pri,res,fn,args);
Begin getfrepcb(i);
    if i=NIL then return(NIL);
    i.id:=pn;i.priority:=pri;
    i.resources:=res;
    memallocate(datasetsize, add);
    if add=NIL then
    begin pcbrelease(i);return(NIL);end;
    i.dataadd:=add;i.datasize:=datasize;
    datasetinit(i.dataadd,args);
    filestate(fn,add,size);
    if add=NIL then
    begin memallocate(size, add);
    ......
    read(fn,size,add);end;
    i.pc:=add;i.parent:=EXE;i.state:='ready';i.queue:=RQ;......
    insert(RQ,i)
    ......

2.2. 进程的中止

2.2.1. 引起进程终止(Termination of Process)的事件

正常结束
在任何计算机系统中，都应有一个用于表示进程已经运行完成的指示。例如，在批处理系统中，通常在程序的最后安排一条Halt指令或终止的系统调用。当程序运行到Halt指令时，将产生一个中断，去通知OS本进程已经完成。在分时系统中，用户可利用Logs off去表示进程运行完毕，此时同样可产生一个中断，去通知OS进程已运行完毕。

// 进程停止原语
procedure halt(i);
begin
    i.state:='stop';
    send(i.parent,'completed');
end;

异常结束

在进程运行期间，由于出现某些错误和故障而迫使进程终止。这类异常时间很多，常见的有：

越界错误：这是指程序所访问的存储区，已越出该进程的区域
保护错：进程试图去访问一个不允许访问的资源或文件，或者以不适当的方式进行访问，例如，进程试图去写一个只读文件；
非法指令：程序试图去执行一条不存在的指令。出现该错误的原因，可能是程序错误地转移到数据区，把数据当成了指令
特权指令错：用户进程试图去执行一条只允许OS执行的指令
运行超时：进程的执行时间超过了指定的最大值
等待超时：进程等待某事件的事件，超过了规定的最大值；
算术运算错：进程试图去执行一个被禁止的运算，例如，被0除
I/O故障：这是指在I/O过程中发生了错误等

外界干预

外界干预并非指在本进程运行中出现了异常事件，而是指进程应外界的请求而终止运行。这些干预有：

操作员或操作系统干预：由于某种原因，例如，发生了死锁，由操作员或操作系统终止该进程
父进程请求：由于父进程提出请求时，系统将终止该进程
父进程终止：当父进程终止时，OS也将他的所有子孙进程终止

2.2.2. 进程的终止过程

根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态
若被终止进程正处于执行状态，应立即种种该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度
若该进程还有子孙进程，还应将其所有子孙进程予以终止，以防它们成为不可控进程。
将被终止进程所拥有的全部资源，或者归还给其父进程，或者归还给系统
将被终止进程（它的PCB）从所在队列（或链表）中移除，等待其他程序来搜集信息

// 进程终止原语
Procedure destory(i);
Begin
    if i.state<>'stop' then
        halt(i);
    while i.children>0 do
    begin
        i.children:=i.children-1;
        findchild(I,child);
        destory(child);
    end
    // 归还系统资源
    remove(i,queue,i);
    pcbrelease(i);
End;

2.3. 进程的阻塞与唤醒

2.3.1. 引起进程阻塞和唤醒的事件

请求系统服务
启动某种操作
新数据尚未到达
无新工作可做

2.3.2. 进程阻塞过程

正在执行的进程，当发现上述某事件时，由于无法继续执行，于是进程便通过调用阻塞原语block把自己阻塞。可见，进程的阻塞是进程自身的一种主动行为。进入block过程后，由于此时刻进程还处于执行状态，所以应先立即停止执行，把进程控制块中的现行状态由“执行”改为阻塞，并将PCB插入阻塞队列。如果系统中设置了因不同时间而阻塞的多个阻塞队列，则应将本进程插入到具有相同事件的阻塞（等待）队列。最后，转调度程序进行重新调度，将处理机分配给另一就绪进程，并进行切换，亦即，保留被阻塞进程的处理机状态（在PCB中），再按新进程的PCB中的处理机状态设置CPU的环境

2.3.3. 进程唤醒过程

当被阻塞进程所期待的事件出现时，如I/O完成或其所期待的数据已经到达，则由有关进程（比如，用完并释放了该I/O设备的进程）调用唤醒原语wakeup()，将等待该事件的进程唤醒。唤醒原语执行的过程是：首先把被阻塞的进程从等待改时间的阻塞队列中移除，将其PCB中的现行状态由阻塞改为就绪，然后再将该PCB插入到就绪队列中。

2.4. 进程的挂起与激活

2.4.1. 进程的挂起

当出现了引起进程挂起的事件时，比如，用户进程请求将自己挂起，或父进程请求将自己的某个子进程挂起，系统将利用挂起原语suspend()将指定进程或处于阻塞状态的进程挂起。挂起原语的执行过程是：首先检查被挂起进程的状态，若处于活动就绪状态，便将其改为静止就绪；对于活动阻塞状态的进程，则将之改为静止阻塞。为了方便用户或父进程考察该进程的运行情况而把该进程的PCB复制到某指定的内存区域。最后，若被挂起的进程正在执行，则转向调度程序重新调度。

终端用户的请求：当终端用户在自己的程序运行期间发现有可疑问题时，希望暂停使自己的程序静止下来。亦即，使正在执行的进程暂停执行；若此时用户进程正处于就绪状态而未执行，则该进程暂不接受调度，以便用户研究其执行情况或对程序进行修改。我们把这种静止状态称为“挂起状态”。
父进程的请求：有时父进程希望挂起自己的某个子进程，以便考察和修改子进程，或者协调各子进程间的活动。
负荷调节的需要：当实时系统中的工作负荷较重，已经可能影响到对实时任务的控制时，可由系统把一些不重要的进程挂起，以保证系统能正常执行
操作系统的需要：操作系统有时希望挂起某些进程，以便检查运行中的资源使用情况或进行记账
对换的需要：为了缓和内存紧张的情况，将内存中处于阻塞状态的进程换至外存上

2.4.2. 进程的激活过程

当发生激活进程的事件时，例如，父进程或用户进程请求激活指定进程，若该进程驻留在外存而内存中已有足够空间时，则可将在外存上处于静止就绪状态的进程换入内存。这时，系统将利用激活原语active()将指定进程激活。激活原语先将进程从外存调入内存，检查该进程的现行状态，若是静止就绪，便将之改为活动就绪；若为静止阻塞便将之改为活动阻塞。加入采用的是抢占调度策略，则每当有新进程进入就绪队列时，应检查是否要进行重新调度，即由调度程序将被激活进程与当前进程进行优先级比较，如果被激活进程的优先级更低，就不必重新调度；否则，立即剥夺当前进程的运行，把处理机分配给刚被激活的进程。

3. 进程同步

3.1. 进程同步的概念

3.1.1 进程间制约关系

在多道程序环境下系统，系统中各进程以不可预测的速度向前推进，进程的异步性会造成结果的不可再现性，为防止这种现象，异步的进程间推进收到两种限制：

资源共享关系：多进程共享资源，例如各进程争用一台打印机，这时各进程使用这台打印机时有一定的限制。每次只允许一个进程使用一段时间打印机，等该进程使用完毕后再将打印机分配给其他进程。这种使用原则称为 互斥使用。
进程之间竞争资源面临三个控制问题：
- 互斥(mutual exclusion)指多个进程不能同时使用同一个资源
- 死锁(deadlock)指多个进程互不相让，都得不到足够的资源
- 饥饿(starvation)指一个进程一直得不到资源（其他进程可能轮流占用资源
相互合作关系：在某些进程之间还存在合作关系，例如一个程序的输入、计算、打印三个程序段作为三个进程并发执行，由于这三个进程间存在着相互合作的关系，即先输入再计算、最后再打印的关系，所以这三个进程在并发执行时推进序列受到限制，要保证其合作关系正确，进程间这种关系称为 同步关系。

3.1.2. 临界资源

像打印机这类资源一次只允许一个进程使用的资源称为临界资源。属于临界资源有硬件打印机、磁盘机等，软件在消息缓冲队列、变量、数组、缓冲区等。当然还有一类像磁盘等资源，它允许进程间共享，即可交替使用，所以他称为 共享资源，而临界资源又称 独享资源

生产者-消费者(producer-consumer)问题是一个著名的进程同步问题。它描述的是：有一群生产者进程在生产产品，并将这些产品提供给消费者进程去消费。为使生产者进程与消费者进程能并发执行，在两者之间设置了一个具有n个缓冲区的缓冲池，生产者进程将它所生产的产品放入一个缓冲区中；消费者进程可从一个缓冲区中取走产品并消费。尽管所有的生产者进程和消费者进程都是以异步方式运行的，但他们之间必须保持同步，即不允许消费者进程到一个空缓冲区去去产品；也不允许生产者进程向一个已装满产品且尚未被取走的缓冲区中投放产品。

3.1.3. 临界区(critical sections)

多个进程共享临界资源时必须互斥使用，例如在两个进程A和B他们的程序如下：

A: begin
        Input data 1 from I/O 1 ;
        Computer......;
        Print results 1 by printer ;    // A临界区
    end
B: begin
        Input data 1 from I/O 2 ;
        Computer......;
        Print results 2 by printer ;    // B临界区
    end

A和B两个进程都需要使用打印机，它们必须互斥使用。如果为了保证结果的正确性限制A、B二进程推进序列，规定进程A执行好再执行进程B，或进程B执行好再执行进程A，这样的限制就显得过死，因为它已不能保证进程A、B并发执行，所以必须把限制减少到最少，以尽可能支持并发执行。为此把各进程代码分解，把访问临界资源的那段代码（称为临界区）与其他段代码分割开来，只对各种进程进入自己的临界区加以限制，即各进程互斥地进入自己的临界区。在上述A、B两程序中我们分别把A和B的使用打印机的二段程序print result 1 by printer和print result 2 by printer 称为A和B进程使用打印机的临界区A和临界区B，进程A和B必须互斥地分别进入各自的临界区A和B。

临界资源：一次只允许一个进程使用的资源
临界区：一个程序片段的集合，这些程序片段分散在不同的进程中，对某个共享的数据结构进行操作。
互斥：不允许两个以上的共享某个资源的并发进程同时进入临界区

3.1.4. 进程同步机制

进程在并发执行时为了保证结果的可再现性，各进程执行序列必须加以限制以保证互斥地使用临界资源，相互合作完成任务。

多个相关进程在执行次序上的协调称为进程同步。用于保证多个进程在执行次序上的协调关系的相应机制称为 进程同步机制

所有的进程同步机制应遵循下述四条准则：

空闲让进：当无进程进入临界区时，相应的临界资源处于空闲状态，因而允许一个请求进入临界区的进程立即进入自己的临界区。
忙则等待：当已有进程进入自己的临界区时，即相应的临界资源正被访问，因而其他试图进入临界区的进程必须等待，以保证进程互斥地访问临界资源
有限等待：对要求访问临界资源的进程，应保证进程能在有限时间进入临界区，以免陷入“饥饿”状态
让权等待：当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入忙等

一个由临界区和剩余区1以及剩余区2程序段组成的进程采用进程同步机制后的描述如下：

begin remainder section 1 ;  // 剩余区1
    // 进入区
    critical section ;      // 临界区
    // 退出区
    remainder section 2 ;   // 剩余区2
end

进程同步机制在临界区前加上进入去，她负责对欲访问的临界资源状态进行检查，以决定是允许该进程进入临界区还是等待。同时在临界区后加上退出区，它负责释放临界资源以便其他等待该临界资源的进程使用

实现进程互斥和同步的信号量机制有软件方法、硬件指令方法、信号量机制和管程等

3.2. 信号量机制

3.2.1. 整型信号量

最初由Dijkstra把整型信号量定义为一个整型量，除初始化外，仅能通过两个标准的原子操作(Atomic Operation)wait(S)和Signal(S)来访问。这两个操作一直被分别称为P、V操作。wait和signal操作可描述为：

1
2
3

wait(S): while S <= 0 do no-op
            S: = S-1
signal(S):  S: = S+1

3.2.2. 记录型信号量

在整型信号量机制中的wait操作，只要是信号量S$\ge$0，就会不断地测试。因此，该机制并未遵循“让权等待”的准则，而是使进程处于“忙等”的状态。记录型信号量机制，则是一种不存在“忙等”现象的进程同步机制。但在采取了“让权等待”的策略后，又会出现多个进程等待访问同一临界资源的情况。为此，在信号量机制中，除了需要一个用于代表资源数目的整型变量value外，还应增加一个进程链表L，用于链接上述的所有等待进程。记录型信号量是由于它采用了记录型的数据结构而得名的。它所包含的上述两个数据项可描述为：

type semaphore = record
    value:integer;
    L:list of process;
    end

相应的，wait(S)和signal(S)操作可描述为：

procedure wait(S)
    var S:semaphore;
    begin
        S.value:= S.value-1
        if S.value<0 then block(S,L)
    end
procedure signal(S)
    var S:semaphore;
    begin
        S.value:= S.value+1
        if S.value<=0 then wakeup(S,L)
    end

信号量的类型

信号量按联系进程的关系分成两类：

公用信号量（互斥信号量）：它为一组需互斥共享临界资源的并发进程而设置，它代表永久性的共享的临界资源，每个进程均可对它施加P、V操作，即都可申请和释放该临界资源，其初始值置为1。
专用信号量（同步信号量）：它为一组需同步协作完成任务的并发进程而设置，它代表消耗性的专用资源，只有拥有该资源的进程才能对它施加P操作（即可申请资源），而由其合作进程对它施加V操作（即释放资源）。

信号量S取值意义

S.value > 0 ：表示可供使用资源数
= 0 : 表示是资源已被占用
< 0 (= -n) : 表示资源已被占用，还有n个进程因等待资源而阻塞

3.2.3. AND型信号量

在两个进程中都要包含两个对Dmutex和Emutex的操作，即

1
2
3

process A:              process B:
wait(Dmutex)            wait(Emutex)
wait(Emutex)            wait(Dmutex)

若进程A和B按下述次序交替执行wait操作：

process A: wait(Dmutex);    // 于是Dmutex = 0
process B: wait(Emutex);    // 于是Emutex = 0
process A: wait(Emutex);    // 于是Emutex = -1 A阻塞
process B: wait(Dmutex);    // 于是Dmutex = -1 B阻塞

AND同步机制的基本思想是：将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其他所有可能为之分配的资源，也不分配给他。亦即，对若干个临界资源的分配，采取原子操作方式：要么全部分配到进程，要么一个也不分配。由死锁理论可知，这样就可避免上述死锁情况的发生。为此，在wait操作中，增加了一个“AND”条件，故称为AND同步，或称为同时wait操作，即Swait（Simultaneous wait）定义如下：

Swait(S_1, S_2, ..., S_n)
    if S_i>=1 and ... and S_n>=1 then
        for i:=1 to n do
        S_i:=S_i-1;
        endfor
    else
    place the process in the waiting queue associated with the first S_i found with S_i<1, and set program count of this process to the beginning of Swait operation
    endif
Ssignal(S_1,S_2,...,S_n)
    for i:=1 to n do
    S_i=S_i+1;
    Remove all the process waiting in the queue associated with S_i into the ready queue.
    endfor;

3.2.4. 信号量集

Swait(S_1,t_1,d_1,...,S_n,t_n,d_n)
    if S_i>=t_i and ... and S_n>=t_n then
        for i:=1 to n do
            S_i:=S_i-d_i
        endfor
    else
    Place the executing process in the waiting queue of the first S_i with S_i<t_i and set its program counter to the beginning of the Swait Operation.
    endif

signal(S_1,d_1,...,S_n,d_n)
    for i:=1 to n do
        S_i:=S_i+d_i;
    Remove all the process waiting in the queue associated with S_i into the ready queue
    endfor;

一般“信号集”的几种特殊情况：
（1）Swait(S,d,d)：此时在信号量集中只有一个信号量S，但允许它每次申请d个资源，当现有资源数少于d时，不予分配
（2）Swait(S,1,1)：此时的信号量集已蜕化位一般的记录型信号量（S>1时）或互斥信号量（S=1时）
（3）Swait(S,1,0)：这是一个很特殊且很有用的信号量操作。当S$\ge$1时，允许多个进程进入某特定区；当S变为0后，将阻止任何进程进入特定区。换言之，它相当于一个可控开关。

3.3. 信号量的应用

3.3.1. 利用信号量实现进程互斥

利用信号量实现进程互斥的进程可描述如下：
① 成对出现 ② 同一进程

Var mutex:semaphore:=1      // 初始信号量
    begin
    parbegin
    process 1:begin
        repeat
        wait(mutex);        // 申请资源
        critical section    // 临界区
        signal(mutex);      // 释放资源
        remainder seetion
        until false;
        end
    process 2:begin
        repeat
        wait(mutex)
        critical section    // 临界区
        signal(mutex)
        remainder section
        until false;
        end
    parend

3.3.2. 利用信号量实现前趋关系

Var a,b,c,d,f,g:semaphore:=0,0,0,0,0,0,0;
    begin
        parbegin
        begin S_1;signal(a);signal(b);end;
        begin wait(a);S_2;signal(c);signal(d);end;
        begin wait(b);S_3;signal(e);end;
        begin wait(c);S_4;signal(f);end;
        begin wait(d);S_5;signal(g);end;
        begin wait(e);wait(f);S_6;end;
        parend
    end

3.3.3. 利用信号量实现进程同步

利用信号量能解决进程间的同步问题，这里以下图所示的计算进程C和打印进程P通过缓冲区Buffer传送数据的同步问题为例说明。

C和P两进程基本算法如下：

C:  begin
    repeat
    Compute next number;
    add to Buffer;
    until false
    end
P:  begin
    repeat
    remove from Buffer;
    print last number;
    until false
    end

C和P进程并发执行，必须在执行序列上遵循以下规则，才能避免错误。

只有当C进程把数据送入Buffer后，P进程才能从Buffer中取出数据来打印，否则P进程只能等待。
只有当P进程从Buffer中取走数据后，C进程才能将新计算的数据再存入Buffer，否则C进程也只能等待。

为了实现进程同步，需采用同步信号量。为了满足第一条同步规则：只有当C进程把数据送入Buffer后，P进程才能从Buffer中取出数据来打印。设置一个同步信号量full，它代表的消耗性专用资源是缓冲器装满数据，这个资源只是后面动作（Remove from buffer）的进程（P进程）所拥有，P进程在动作前可以申请该资源，对它施加P操作，如条件满足P进程可从Buffer中取数，它的初值为0。而前面动作的进程（P进程的合作进程C）在动作（Add to Buffer）完成后对full信号量施加V操作，即当C进程将数据存入Buffer后，即可释放该资源供P进程再使用。实现C和P两进程第一条同步规则的类PASCAL程序：

考虑第一个同步关系-C加入后P再取

var:full:semaphore:=0;
begin
    parbegin
    C:  begin
        repeat
            Computer next number;
            Add to buffer;
            V(fulll);
            until false
        end
    P:  begin
        repeat
            P(full);
            remove from Buffer;
            Print last number;
            until false
        end
    parend
end

为了满足第二条同步规则：只有当P进程从Buffer中取走数据后，C进程才能将新计算的数据再存入Buffer。设置另一个同步信号量empty，它代表的消耗性的专用资源是缓冲器为空，这个资源只是后面动作（Add to buffer）的进程（C进程）所拥有，C进程在动作前可以申请该资源，对它施加P操作，如条件满足进程C可以折你去哪个该资源，它的初值为1.而前面动作（Remove from buffer）的进程（C进程的合作进程P）在动作完成后对empty信号量施加V操作，即当P进程从Buffer中取走数据后，即可释放该资源供C进程再使用。

实现C和P进程第二条同步规则的类PASCAL程序：
考虑第二个同步关系——P取走后C再加入

var:full:semaphore:=0;
begin
    parbegin
    C:  begin
        repeat
            Computer next number;
            P(empty);
            Add to buffer;
            until false
        end
    P:  begin
        repeat
            remove from Buffer;
            V(empty);
            Print last number;
            until false
        end
    parend
en

当同时考虑两个同步关系时，类PASCAL程序：

var:full:semaphore:=0;
begin
    parbegin
    C:  begin
        repeat
            Computer next number;
            P(empty);
            Add to buffer;
            V(full);
            until false
        end
    P:  begin
        repeat
            P(full);
            remove from Buffer;
            V(empty);
            Print last number;
            until false
        end
    parend
en

同步物理意义：同步可以理解为，先做动作的进程C在动作完成后对同步信号量施加V操作，代表发送消息；后做动作的进程P在动作前对同步信号量施加P操作，代表测试消息是否到达。

例：有三个共行进程P、Q和R以及一对供存数据的缓冲BufI和BufO，P进程把数据输入BufI，R进程输出BufO中的数据。Q把BufI中的数据变换后送入BufO，在上述假定之下，使三个进程实现最大并行性。试在下述类PASCAL程序中虚线位置分别填上信号量、信号初值和P、V操作实现三个进程正确的并发执行

Program ito;
    var BufI,BufO:buffer;
    (信号量)_ _ _ _ _ _:SEMAPHORE:=(信号量初值)_ _ _ _ _ _;
    begin
    parbegin
    P:begin
        repeat
            input from IO;
            _ _ _ _ _ _
            Add to BufI;
            _ _ _ _ _ _
        until false
    end;
    Q:begin
        repeat
            _ _ _ _ _ _
            Remove from BufI;
            _ _ _ _ _ _
            transform;
            _ _ _ _ _ _
            Add to BufO;
            _ _ _ _ _ _
        until false
    end;
    R:begin
        repeat
            _ _ _ _ _ _
            Remove from BufO;
            _ _ _ _ _ _
            Output ...;
        until false
    end;
    parend
    end

答案:
emptyI,fullI,emptyO,fullO
1,0,1,0
wait(emptyI)
signal(fullI)
wait(fullI)
signal(emptyI)
wait(emptyO)
signal(fullO)
wait(fullO)
signal(emptyO)

本文标题:进程管理[更新中...]

文章作者:Oh_MyBug

发布时间:2020-04-14, 12:15:14

最后更新:2020-04-14, 12:15:14

原始链接:https://oh-mybug.github.io/2020/04/14/%E8%BF%9B%E7%A8%8B%E7%AE%A1%E7%90%86-%E6%9B%B4%E6%96%B0%E4%B8%AD/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。