第二章 进程管理 2.1 进程的基本概念 2.2 进程控制 2.3 进程同步

上节回顾 进程的终止 进程的阻塞和唤醒 进程的挂起与激活 进程的同步：两种制约关系 生产者--消费者问题：临界资源 临界区 同步机制的规则：P41

3. 临界区(critical section) 可把一个访问临界资源的循环进程描述如下： repeat ——进入区，检查 critical section; ——临界区，访问资源  ——退出区，恢复 remainder section; until false; entry section exit section

4. 同步机制应遵循的规则 空闲让进。 (2) 忙则等待。 (3) 有限等待。 (4) 让权等待。

2.3.2 信号量机制 1. 整型信号量 最初由Dijkstra把整型信号量定义为一个整型量，除初始化外，仅能通过两个标准的原子操作(Atomic Operation) wait(S)和signal(S)来访问。这两个操作一直被分别称为P、V操作。 wait和signal操作可描述为： wait(S): while S≤0 do no-op S∶=S-1; signal(S): S ∶=S+1; While循环不能释放处理机，“忙等”，未遵循“让权等待”规则。

2. 记录型信号量 记录型信号量机制，是一种不存在“忙等”现象的进程同步机制。但在采取了“让权等待”的策略后，又会出现多个进程等待访问同一临界资源的情况。为此，在信号量机制中，除了需要一个用于代表资源数目的整型变量value外，还应增加一个进程链表L，用于链接上述的所有等待进程。记录型信号量是由于它采用了记录型的数据结构而得名的。它所包含的上述两个数据项可描述为：

在记录型信号量机制中，S.value的初值表示系统中某类资源的数目， 因而又称为资源信号量，对它的每次wait操作，意味着进程请求一个单位的该类资源，因此描述为S.value∶ =S.value-1； 当S.value＜0时，表示该类资源已分配完毕，因此进程应调用block原语，进行自我阻塞，放弃处理机，并插入到信号量链表S.L中。

该机制遵循了“让权等待”准则。 此时S.value的绝对值表示在该信号量链表中已阻塞进程的数目。 对信号量的每次signal操作，表示执行进程释放一个单位资源，故S.value∶ =S.value+1操作表示资源数目加1。 若加1后仍是S.value≤0，则表示在该信号量链表中，仍有等待该资源的进程被阻塞，故还应调用wakeup原语，将S.L链表中的第一个等待进程唤醒。如果S.value的初值为1，表示只允许一个进程访问临界资源，此时的信号量转化为互斥信号量。 S.value意义的变化: >0， 可用资源数量 <=0，阻塞进程个数

3. AND型信号量 在两个进程中都要包含两个对Dmutex和Emutex的操作， 即 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(S1, S2, …, Sn) if Si≥1 and … and Sn≥1 then for i∶ =1 to n do Si∶=Si-1; endfor else place the process in the waiting queue associated with the first Si found with Si＜1, and set the program count of this process to the beginning of Swait operation endif （将进程插入首个令它阻塞的资源阻塞队列，并将程序计数器设置在Swait操作的开始位置）

Ssignal(S1, S2, …, Sn) for i∶ =1 to n do Si=Si+1; remove all the process waiting in the queue associated with Si into the ready queue. endfor; （将Si对应阻塞队列中的所有进程移入就绪队列，重新调度）

4. 信号量集

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

2.3.3 信号量的应用 1. 利用信号量实现进程互斥 利用信号量实现进程互斥的进程可描述如下： Var mutex : semaphore∶ =1; begin parbegin process 1: begin repeat wait(mutex); critical section signal(mutex); remainder section until false; end

process 2: begin repeat wait(mutex); critical section signal(mutex); remainder section until false; end parend

2. 利用信号量实现前趋关系 图 2-10 前趋图举例

Var a,b,c,d,e,f,g; semaphore∶=0,0,0,0,0,0,0; begin parbegin begin S1; signal(a); signal(b); end; begin wait(a); S2; signal(c); signal(d); end; begin wait(b); S3; signal(e); end; begin wait(c); S4; signal(f); end; begin wait(d); S5; signal(g); end; begin wait(e); wait(f); wait(g); S6; end; parend end