计算机操作系统：协作进程同步

在OS中引入进程后，虽然提高了资源的利用率和系统的吞吐量，但由于其异步性，也会使系统造成混乱。例如，当多个进程去争用一台打印机时，有可能使多个进程的输出结果交织在一起，难以区分；而当多个进程去争用共享变量、表格、链表时，有可能致使数据处理出错。进程同步的主要任务是对多个相关进程在执行次序上进行协调，以使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。

3.4.1 进程同步的概念

在多道程序环境下，当程序并发执行时，由于资源共享和进程合作，使同处于一个系统中的诸进程之间可能存在以下两种形式的制约关系。

（1）竞争关系。系统中的多个进程之间彼此无关，它们并不知道其他进程的存在，也不受其他进程执行的影响。例如，批处理系统中建立的多个用户进程，分时系统中建立的多个终端进程。由于这些进程共用一套计算机系统资源，因而必然会出现多个进程竞争资源的问题。当多个进程竞争共享硬件设备、存储器、处理器和文件等资源时，操作系统必须协调好进程对资源的争用。

由于相互竞争资源的进程间并不交换信息，但是一个进程的执行可能影响同其竞争资源的其他进程，如果两个进程要访问同一资源，那么一个进程通过操作系统分配得到该资源，另一个将不得不等待。在极端的情况下，被阻塞进程永远得不到访问权，从而不能成功地终止。所以，资源竞争出现了两个控制问题：一个是死锁（deadlock）问题，一组进程如果都获得了部分资源，还想要得到其他进程所占有的资源，最终所有的进程将陷入死锁；另一个是饥饿（starvation）问题，即一个进程由于其他进程总是优先于它而被无限期拖延。由于操作系统负责资源分配，资源竞争的控制应由系统来解决，因而操作系统应该提供各种支持，例如，提供锁机制给并发进程在使用共享资源之前来表达互斥的要求。操作系统需要保证诸进程能互斥地访问临界资源，既要解决饥饿问题，又要解决死锁问题。

进程的互斥（mutual exclusion）是解决进程间竞争关系（间接制约关系）的手段，也称间接同步。进程互斥指若干个进程要使用同一共享资源时，任何时刻最多允许一个进程去使用，其他要使用该资源的进程必须等待，直到占有资源的进程释放该资源。临界区管理可以解决进程互斥问题。

（2）协作关系。某些进程为完成同一任务需要分工协作，由于合作的每一个进程都是独立地以不可预知的速度推进，这就需要相互协作的进程在某些协调点上协调各自的工作。当合作进程中的一个到达协调点后，在尚未得到其伙伴进程发来的消息或信号之前应阻塞自己，直到其他合作进程发来协调信号或消息后方被唤醒并继续执行。这种协作进程之间相互等待对方消息或信号的协调关系称为进程同步。例如有三个进程：input（读入数据）、process（对读入的数据进行处理）和output（将处理完的数据打印），这是一种典型的协作关系，各自都知道对方的存在。这时操作系统要确保诸进程在执行次序上协调一致，一块数据没有输入完之前不能加工处理，没有加工处理完之前不能打印输出等。进程间的协作可以是双方不知道对方名字的间接协作，例如，通过共享访问一个缓冲区进行松散式协作；也可以是双方知道对方名字，直接通过通信机制进行紧密协作。

进程的同步（synchronization）是解决进程间协作关系（直接制约关系）的手段，也称直接同步。进程同步指两个以上进程基于某个条件来协调它们的活动。一个进程的执行依赖于另一个协作进程的消息或信号，当一个进程没有得到来自另一个进程的消息或信号时则需等待，直到消息或信号到达才被唤醒。不难看出，进程互斥关系是一种特殊的进程同步关系，即逐次使用互斥共享资源，也是对进程使用资源次序上的一种协调。

3.4.2 临界区及其管理

1.临界资源和临界区

假设一个飞机订票系统有两个终端，分别运行进程T1和T2。该系统的公共数据区中的一些单元Aj（j＝1，2，…）分别存放某月某日某次航班的余票数，而x1和x2表示进程T1和T2执行时所用的工作单元。飞机票售票程序如下：

void Ti（int i） ／／i＝1或2

｛int Xi；

按旅客订票要求找到Aj

Xi＝Aj；

i f（Xi＞＝1）

｛Xi＝Xi－1；

Aj＝Xi；

输出一张票；

｝

else

｛输出信息“票已售完”｝；

｝

由于T1和T2是两个可同时执行的并发进程，它们在同一个计算机系统中运行，共享同一批票源数据，因此，可能出现如下所示的运行情况：

T1：X1：=Aj； X1=m（m＞0）

T2：X2：=Aj； X2=m

T2：X2：=X2-1；Aj：=X2；输出一张票；Aj=m-1

T1：X1：=X1-1；Aj：=X1；输出一张票；Aj=m-1

显然，此时出现了把同一张票卖给了两位旅客的情况，两位旅客可能各自都买到一张同天同次航班的机票，可是，Aj的值实际上只减去了1，造成余票数的不正确。特别地，当某次航班只有一张余票时，就可能把这一张票同时售给了两位旅客，之所以会产生错误，原因在于多个售票进程交叉访问了共享变量Aj。这里把并发进程中与共享变量有关的程序段称为临界区（critical section），共享变量代表的资源称为临界资源（critical resource）。在上例中，进程T1的临界区为

X1＝Aj；

i f（X1＞＝1）

｛X1＝X1－1；

Aj＝X1；｝

进程T2的临界区为：

X2＝Aj；

i f（X2＞＝1）

｛X2＝X2－1；

Aj＝X2；｝

与同一变量有关的临界区分散在各有关进程的程序段中，而各进程的执行速度不可预知。如果能保证一个进程在临界区执行时，不让另一个进程进入相关的临界区，即各进程对共享变量的访问是互斥的，那么就不会造成与时间有关的错误。

2.临界区管理

为实现进程间接同步，使进程互斥地进入自己的临界区，可用软件或硬件方法来协调各进程间的运行。其互斥机制（间接同步机制）都应遵循下述四条准则：

（1）空闲让进。当无进程处于临界区时，表明临界资源处于空闲状态，应允许一个请求进入临界区的进程立即进入自己的临界区，以有效地利用临界资源。

（2）忙则等待。当已有进程进入临界区时，表明临界资源正在被访问，因而其他试图进入临界区的进程必须等待，以保证对临界资源的互斥访问。

（3）有限等待。对要求访问临界资源的进程，应保证在有限时间内能进入自己的临界区，以免陷入“死等”状态。

（4）让权等待。当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”状态。

3.实现临界区管理的方法

要达到上述四条准则，实现临界区管理可以通过软件和硬件两种方法。

1）软件方法

（1）Dekker算法。荷兰数学家T.Dekker提出的Dekker算法能保证进程互斥地进入临界区，这是最早提出的一个软件互斥方法，此方法用一个指示器turn来指示哪一个进程应该进入临界区。若turn＝1，则进程P1可以进入临界区；若turn＝2，则进程P2可以进入临界区。Dekker算法如下：

bool inside［2］；

int turn；

turn＝1 or 2；

inside［1］＝false；

inside［2］＝false；

parbegin

Void P1（）

｛inside［1］＝t rue；

while（inside［2］）

｛if（turn＝＝2）

｛inside［1］＝false；

whi le（turn＝＝2）

｛

｝

inside［1］＝t rue；

｝

｝

临界区；

turn＝2；

inside［1］＝false；

｝

Void P2（）

｛inside［2］＝true；

while（inside［1］）

｛i f（turn＝＝1）

｛inside［2］＝false；

while（turn＝＝1）

｛

｝

inside［2］＝t rue；

｝

｝

临界区；

turn＝1；

inside［2］＝false；

｝

parend.

Dekker算法的执行过程描述如下：当进程P1（或P2）想进入自己的临界区时，它把自己的标志位inside1（或inside2）置为true，然后继续执行并检查对方的标志位。如果为false，表明对方不在也不想进入临界区，进程P1（或P2）可以立即进入自己的临界区；否则，咨询指示器turn，若turn为1（或为2），那么P1（或P2）知道应该自己进入，反复地去测试P2（或P1）的标志值inside2（或inside1）；进程P2（或P1）注意到应该礼让对方，故把其自己的标志位置为false，允许进程P1（或P2）进入临界区；在进程P1（或P2）结束其临界区工作后，把自己的标志置为false，且把turn置为2（或1），从而把进入临界区的权力交给进程P2（或P1）。

这种方法显然能保证互斥进入临界区的要求，这是因为仅当turn＝i（i＝1，2）时进程Pi（i＝1，2）才有权力进入其临界区。因此，一次只有一个进程能进入临界区，且在一个进程退出临界区之前，turn的值是不会改变的，保证不会有另一个进程进入相关临界区。同时，turn的值不是1就是2，故不可能同时出现两个进程均在while语句中等待而进不了临界区。Dekker算法虽能解决互斥问题，但算法复杂难于理解，Peterson算法则较为简单。

（2）Peterson算法。在1981年，G.L.Perterson提出了一个简单得多的软件互斥算法来解决互斥进入临界区的问题。此方法为每个进程设置一个标志，当标志为false时表示该进程要求进入临界区。另外再设置一个指示器turn以指示可以由哪个进程进入临界区，当turn＝i时则可由进程Pi进入临界区。Perterson算法的程序如下：

bool inside［2］；

int turn；

turn＝1 or 2；

inside［1］＝false； ／*P1不在其临界区内*／

inside［2］＝false； ／*P2不在其临界区内*／

parbegin

void P1（）

｛

inside［1］＝t rue；

turn＝2；

whi le（inside［2］&turn＝2）

｛｝

临界区；

inside［1］＝false；

｝

void P2（）

｛

inside［2］＝true；

turn＝1；

while（inside［1］&turn＝＝1）

｛｝

临界区；

inside［2］＝false；

｝

parend.

在上面的程序中，用对turn的置值和while语句来限制每次最多只有一个进程可以进入临界区，当有进程在临界区执行时不会有另一个进程闯入临界区；进程执行完临界区程序后，修改inside［i］的状态而使等待进入临界区的进程可在有限的时间内进入临界区。所以，Peterson算法满足了对临界区管理的三个条件。由于在while语句中的判别条件是“inside［i］和turn＝1（或2）”，因此，任意一个进程进入临界区的条件是对方不在临界区或对方不请求进入临界区。于是，任何一个进程均可以多次进入临界区。本算法也很容易推广到n个进程的情况。

2）硬件方法

在单处理器计算机中，并发进程不会同时只会交替执行，为了保证互斥，仅需要保证一个进程不被中断即可。分析临界区管理尝试中的两种算法，问题出在管理临界区的标志时要用到两条指令，而这两条指令在执行过程中有可能被中断，从而导致执行的不正确。能否把标志看作一个锁，开始时锁是打开的，在一个进程进入临界区时便把锁锁上以封锁其他进程进入临界区，直至它离开其临界区，再把锁打开以允许其他进程进入临界区。如果希望进入其临界区的一个进程发现锁未开，它将等待，直到锁被打开。可见，要进入临界区的每个进程必须首先测试锁是否打开，如果是打开的，则应立即把它锁上，以排斥其他进程进入临界区。显然，测试和上锁这两个动作不能分开，以防两个或多个进程同时测试到允许进入临界区的状态。下面是一些硬件设施，可用来实现对临界区的管理。

（1）关中断。实现互斥的最简单方法之一是关中断。当进入锁测试之前关闭中断，直到完成锁测试并上锁之后再开中断。进程在临界区执行期间，计算机系统不响应中断，因此不会转向调度，也就不会引起进程或线程切换，保证了锁测试和上锁操作的连续性和完整性，也就保证了互斥，有效地实现了临界区管理。关中断方法有许多缺点：滥用关中断权力可能导致严重后果；关中断时间过长会影响系统效率，限制了处理器交叉执行程序的能力；关中断方法也不适用于多CPU系统，因为在一个处理器上关中断，并不能防止进程在其他处理器上执行相同临界段代码。

（2）测试并建立指令。实现这种管理的另一种办法是使用硬件提供的“测试并建立”指令TS（test and set）。可把这条指令看作函数过程，它有一个布尔参数x和一个返回条件码，当TS（x）测到x为true时则置x为false，且根据测试到的x值形成条件码。下面给出了TS指令的处理过程。TS（x）：若x＝true，则x：＝false；return true；否则return false；用TS指令管理临界区时，可把一个临界区与一个布尔变量s相连，由于变量s代表了临界资源的状态，可把它看成一把锁。s初值置为true，表示进程在临界区内使用资源。系统可以提供在锁上的利用TS指令实现临界区的上锁和开锁原语操作。在进入临界区之前，首先用TS指令测试s，如果没有进程在临界区内，则可以进入，否则必须循环测试直到TS（s）为true，此时s的值一定为false；当进程退出临界区时把s置为true。由于TS指令是一个不可分指令，在测试和形成条件码之间不可能有另一进程去测试x值，从而保证了临界区管理的正确性。

bool s；

s＝t rue；

void Pi（） ／*i＝1，2，…，n*／

｛bool pi；

do

pi＝TS（s）；

whi le（pi）；／*上锁*／

临界区；

s＝t rue； ／*开锁*／

｝

3.4.3 信号量及PV操作

1965年，荷兰学者Dijkstra提出的信号量（semaphores）机制是一种卓有成效的进程同步工具。在之后的应用中，信号量机制又得到了很大的发展，它从整型信号量、记录型信号量，进而发展为“信号量集”机制。

1.整型信号量

最初由Dijkstra把整型信号量定义为一个用于表示资源数目的整型量S，它与一般整型量不同，除初始化外，仅能通过两个标准的原子操作P（S）和V（S）来访问。很长时间以来，这两个操作一直被分别称为P，V操作。这两个操作可描述为

P（S）：whi le（S＜＝0）

｛；｝

S＝S－1；

V（S）：S＝S＋1；

P（S）和V（S）是两个原子操作，因此它们在执行时是不可中断的。亦即当一个进程在修改某信号量时，没有其他进程可同时对该信号量进行修改。此外，在P操作中，对S值的测试和做S：＝S－1操作时都不可中断。

2.记录型信号量

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

＃def ine A 1000

type st ruct｛

int value；

PCBL［A］；

｝semaphore；

相应地，P（S）和V（S）操作可描述为

void P（semaphore S）

｛S.value＝S.value－1；

i f（S.value＜0） block（S.L）；

｝

void V（semaphore S）

｛S.value＝S.value＋1；

if（S.value＜＝0） wakeup（S.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，表示只允许一个进程访问临界资源，此时的信号量转化为互斥信号量，用于进程互斥。

3.AND型信号量

上述的进程互斥问题，是针对各进程之间只共享一个临界资源而言的。在有些应用场合，一个进程需要先获得两个或更多的共享资源后方能执行其任务。假定现有两个进程A和B，它们都要求访问共享数据D和E。当然，共享数据都应作为临界资源。为此，可为这两个数据分别设置用于互斥的信号量Dmutex和Emutex，并令它们的初值都是1。相应地，在两个进程中都要包含两个对Dmutex和Emutex的操作，即

process A（） process B（）：

｛ ｛

P（Dmutex）； P（Emutex）；

P（Emutex）； P（Dmutex）；

｝ ｝

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

process A：P（Dmutex）；于是Dmutex＝0

process B：P（Emutex）；于是Emutex＝0

process A：P（Emutex）；于是Emutex＝－1 A阻塞

process B：P（Dmutex）；于是Dmutex＝－1 B阻塞

最后，进程A和B处于僵持状态。在无外力作用下，两者都将无法从僵持状态中解脱出来，称此时的进程A和B已进入死锁状态。显然，当进程同时要求的共享资源越多时，发生进程死锁的可能性也就越大。

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

void Swait（S1，S2，…，Sn）

｛

i f（Si＞＝1 and… and Sn＞＝1）

｛for（int i＝1；i＜＝n；i＋＋）

Si：＝Si－1；

｝

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

｝

void Ssignal（S1，S2，…，Sn）

｛for（int i＝1；i＜＝n；i＋＋）

｛

Si：＝Si＋1；

Remove al l the process waiting in the queue associated with Si into the

ready queue.

｝

｝

4.信号量集

在记录型信号量机制中，P（S）或V（S）操作仅能对信号量施以加1或减1操作，意味着每次只能获得或释放一个单位的临界资源。而当一次需要N个某类临界资源时，便要进行N次P（S）操作，显然这是低效的。此外，在有些情况下，当资源数量低于某一下限值时，便不予以分配。因而，在每次分配之前，都必须测试该资源的数量，查看其是否大于其下限值。基于上述两点，可以对AND信号量机制加以扩充，形成一般化的“信号量集”机制。Swait操作可描述如下（其中S为信号量，d为需求值，而t为下限值）：

void Swait（S1，t1，d1，…，Sn，tn，dn）

｛i f（Si＞＝t1 and…and Sn＞＝tn）

｛for（int i＝1；i＜＝n；i＋＋）

Si：＝Si－di；

｝

else

Place the executing process in the waiting queue of the first Si with Si＜ti and set its program counter to the beginning of the Swait Operation.

｝

void Ssignal（S1，d1，…，Sn，dn）

｛for（int i＝1；i＜＝n；i＋＋）

｛Si：＝Si＋di；

Remove al l the process waiting in the queue associated with Si into the ready queue(www.xing528.com)

｝

｝

信号量集的几种特殊情况如下：

（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后，将阻止任何进程进入特定区。换言之，它相当于一个可控开关。

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

利用信号量可以方便地实现进程互斥，与TS指令相比较，P，V操作也是用测试信号量的办法来决定是否能进入临界区，但不同的是P，V操作只对信号量测试一次，而用TS指令则必须反复测试。用信号量和P，V操作管理几个进程互斥只需为该资源设置一互斥信号量mutex，并设其初始值为1，然后将各进程访问该资源的临界区CS置于P（mutex）和V（mutex）操作之间即可。这样，每个欲访问该临界资源的进程在进入临界区之前，都要先对mutex执行P操作，若该资源此刻未被访问，本次P操作必然成功，进程便可进入自己的临界区，这时若再有其他进程也欲进入自己的临界区，由于对mutex执行P操作定会失败，因而该进程阻塞，从而保证了该临界资源能被互斥地访问。当访问临界资源的进程退出临界区后，又应对mutex执行signal操作，以便释放该临界资源。利用信号量实现进程互斥的进程可描述如下：

semaphore：mutex＝1；

parbegin

process 1：｛do

｛P（mutex）；

critical section

V（mutex）；

remainder section

｝while（false）；

｝

process 2：｛do

｛P（mutex）；

critical section

V（mutex）；

remainder section

｝whi le（false）；

｝

在利用信号量机制实现进程互斥时应注意，P（mutex）和V（mutex）必须成对地出现。缺少P（mutex）将会导致系统混乱，不能保证对临界资源的互斥访问；而缺少V（mutex）将会使临界资源永远不被释放，从而使因等待该资源而阻塞的进程不能被唤醒。

3.4.4 几个经典的进程同步问题

1.生产者-消费者问题

1）利用记录型信号量

假定在生产者和消费者之间的公用缓冲池中，具有n个缓冲区，这时可利用互斥信号量mutex实现诸进程对缓冲池的互斥使用。利用信号量empty和full分别表示缓冲池中空缓冲区和满缓冲区的数量。又假定这些生产者和消费者相互等效，只要缓冲池未满，生产者便可将消息送入缓冲池；只要缓冲池未空，消费者便可从缓冲池中取走一个消息。对生产者-消费者问题可描述如下：

semaphore：mutex＝1，empty＝n，ful l＝0；

item：buf fer：［n］；

int in＝0，out＝0；

parbegin

void producer_i（）

｛L1：produce an item in nextp；

P（empty）；

P（mutex）；

Buf fer［in）＝nextp；

in＝（in＋1）mod n；

V（mutex）；

V（ful l）；

goto L1；

｝

void consumer_j（）

｛L2：P（ful l）；

P（mutex）；

Nextc＝buf fer（out）；

Out＝（out＋1）mod n；

V（mutex）；

V（empty）；

consumer the item in nextc；

goto L2；

｝

parend

在这个问题中，P操作的次序是很重要的，如果把生产者进程中的两个P操作交换次序，那么当缓冲器中存满了k件产品（此时，empty＝0，mutex＝l，full＝k）时，生产者又生产了一件产品，它欲向缓冲器存放时将在P（empty）上等待（注意，现在empty＝0），但它已经占有了使用缓冲器的权力。这时消费者欲取产品时将停留在P（mutex）上得不到使用缓冲器的权力。导致生产者等待消费者取走产品，而消费者却在等待生产者释放使用缓冲器的权力，这种相互等待永远结束不了。所以，在使用信号量和P，V操作实现进程同步时，特别要当心P操作的次序，而V操作的次序倒是无关紧要的。一般而言，用于互斥的信号量上的P操作，总是在后面执行。

2）利用AND型信号量

Semaphore：mutex＝1，empty＝n，ful l＝0；

i tem：buf fer：［n］；

2.读者-写者问题

一个数据文件或记录，可被多个进程共享，把只要求读该文件的进程称为“Reader进程”，其他进程则称为“Writer进程”。允许多个进程同时读一个共享对象，因为读操作不会使数据文件混乱。但不允许一个Writer进程和其他Reader进程或Writer进程同时访问共享对象，因为这种访问将会引起混乱。所谓“读者-写者问题”，是指保证一个Writer进程必须与其他进程互斥地访问共享对象的同步问题。读者-写者问题常被用来测试新同步原语。

1）利用记录型信号量

单纯使用信号量不能解决读者-写者问题，必须引入计数器rc对读进程计数，mutex是用于对计数器rc操作的互斥信号量，W表示是否允许写的信号量，于是管理该文件的程序可设计如下：

int in＝0，out＝0；

parbegin

void producer（）

｛do｛

produce an item in nextp；

Swait（empty，mutex）；

Buf fer［in］＝nextp；

in＝（in＋1）mod n；

Ssignal（mutex，ful l）；

whi le（false）；

｝

void consumer（）

｛do ｛

Swait（ful l，mutex）；

Nextc＝buf fer［out］；

Out＝（out＋1）mod n；

Ssignal（mutex，empty）；

consumer the item in nextc；

while（false）；

｝

parend

int rc；

semaphore：W，mutex；

rc＝0； ／*读进程计数*／

W＝1；

mutex＝1；

void read（）

｛

P（mutex）；

rc＝rc＋1；

i f（rc＝1）

P（W）；

V（mutex）；

读文件；

P（mutex）；

rc＝rc－1；

i f（rc＝0）

V（W）；

V（mutex）；

｝

void write（）

｛

P（W）；

写文件；

V（W）；

｝

parbegin

process readeri；

process wr iter j；

parend.

process readeri；

｛

read（）；

｝

process writer j

｛

Wr ite（）；

｝

在上面的解法中，读者是优先的，当存在读者时，写操作将被延迟，并且只要有一个读者活跃，随后而来的读者都将允许访问文件，从而导致了写进程长时间等待，并有可能出现写进程被“饿死”。增加信号量并修改上述程序可以得到写进程具有优先权的解决方案，能保证当一个写进程声明想写时，不允许新的读进程再访问共享文件。

2）利用信号量集

这里的读者-写者问题与前面的略有不同，它增加了一个限制，即最多只允许RN个读者同时读。为此，又引入了一个信号量L，并赋予其初值为RN，通过执行Swait（L，1，1）操作来控制读者的数目。每当有一个读者进入时，就要先执行Swait（L，1，1）操作，使L的值减1。当有RN个读者进入读后，L便减为0，第RN＋1个读者要进入读时，必然会因Swait（L，1，1）操作失败而阻塞。对利用信号量集来解决读者-写者问题的描述如下：

int RN；

semaphore：L＝RN，mx＝1；

parbegin

process reader

｛do｛ Swait（L，1，1）；

Swait（mx，1，0）；

per form read operation；

Ssignal（L，1）；

while（false）；

｝

process writer

｛do ｛

Swait（mx，1，1；L，RN，0）；

per formwrite operation；

Ssignal（mx，1）；

｝whi le（false）；

｝

parend

end

其中，Swait（mx，1，0）语句起着开关的作用。只要无writer进程进入写，mx＝1，reader进程就都可以进入读。但一旦有writer进程进入写时，其mx＝0，则任何reader进程都无法进入读。Swait（mx，1，1；L，RN，0）语句表示仅当既无writer进程在写（mx＝1），又无reader进程在读（L＝RN）时，writer进程才能进入临界区写。

3.哲学家进餐问题

由Dijkstra提出并解决的哲学家进餐问题是典型的同步问题。该问题是描述有五位哲学家共用一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五个碗和五支筷子，他们的生活方式是交替地进行思考和进餐。平时，一位哲学家进行思考，饥饿时便试图取用其左右最靠近他的筷子，只有在他拿到两支筷子时才能进餐。进餐完毕，放下筷子继续思考。

利用记录型信号量解决时，在一段时间内只允许一位哲学家使用。为了实现对筷子的互斥使用，可以用一个信号量表示一支筷子，由这五个信号量构成信号量数组。其描述如下：

semaphore chopstick［5］；

所有信号量均被初始化为1，第i位哲学家的活动可描述为

do

｛P（chopstick［i］）；

P（chopstick［（i＋1）mod 5］）；

eat；

V（chopstick［i］）；

V（chopstick［（i＋1）mod 5］）；

think；

｝while（false）；

在以上描述中，当哲学家饥饿时，总是先去拿他左边的筷子，即执行P（chopstick［i］）；成功后，再去拿他右边的筷子，即执行P（chopstick［（i＋1）mod 5］）；又成功后便可进餐。进餐完毕，又先放下他左边的筷子，然后再放右边的筷子。虽然，上述解法可保证不会有两个相邻的哲学家同时进餐，但有可能引起死锁。假如五位哲学家同时饥饿而各自拿起左边的筷子时，就会使五个信号量chopstick均为0；当他们再试图去拿右边的筷子时，都将因无筷子可拿而无限期地等待。对于这样的死锁问题，可采取以下几种解决方法：

（1）至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕时能释放出他用过的两支筷子，从而使更多的哲学家能够进餐。

（2）仅当哲学家的左、右两支筷子均可用时，才允许他拿起筷子进餐。

（3）规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子，而偶数号哲学家则相反。按此规定，将是1、2号哲学家竞争1号筷子；3、4号哲学家竞争3号筷子。即五位哲学家都先竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一位哲学家能获得两支筷子而进餐。

3.4.5 管程机制

虽然信号量机制是一种既方便又有效的进程同步机制，但每个要访问临界资源的进程都必须自备同步操作P（S）和V（S）。这就使大量的同步操作分散在各个进程中。这不仅给系统的管理带来麻烦，而且会因同步操作的使用不当而导致系统死锁。这样，在解决上述问题的过程中，便产生了一种新的进程同步工具——管程（monitors）。

1.管程的定义

系统中的各种硬件资源和软件资源，均可用数据结构抽象地描述其资源特性，即用少量信息和对该资源所执行的操作来表征该资源，而忽略了它们的内部结构和实现细节。例如，对一台电传机，可用与分配该资源有关的状态信息（busy或free）和对它执行请求与释放的操作，以及等待该资源的进程队列来描述。又如，一个FIFO队列，可用其队长、队首和队尾以及在该队列上执行的一组操作来描述。利用共享数据结构抽象地表示系统中的共享资源，而把对该共享数据结构实施的操作定义为一组过程，如资源的请求（request）和释放（release）过程。进程对共享资源的申请、释放和其他操作，都是通过这组过程对共享数据结构的操作来实现的，这组过程还可以根据资源的情况，或接受或阻塞进程的访问，确保每次仅有一个进程使用共享资源，这样就可以统一管理对共享资源的所有访问，实现进程互斥。

代表共享资源的数据结构，以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序，共同构成了一个操作系统的资源管理模块，称为管程。管程被请求和释放资源的进程所调用。Hansan为管程所下的定义是：“一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据。”由上述的定义可知，管程由四部分组成：①管程的名称；②局部于管程内部的共享数据结构说明；③对该数据结构进行操作的一组过程；④对局部于管程内部的共享数据设置初始值的语句。

管程的语法描述如下：

MONITOR monitor_name；

＜共享变量说明＞；

define＜（能被其他模块引用的）过程名列表＞；

use ＜（要调用的本模块外定义的）过程名列表＞；

void ＜过程名＞（＜形式参数表＞）；

｛

……

｝

……

｛

＜管程的局部数据初始化语句序列＞；

｝

需要指出的是，局部于管程内部的数据结构，仅能被局部于管程内部的过程所访问，任何管程外的过程都不能访问它；反之，局部于管程内部的过程也仅能访问管程内的数据结构。由此可见，管程相当于围墙，它把共享变量和对它进行操作的若干过程围了起来，所有进程要访问临界资源时，都必须经过管程（相当于通过围墙的门）才能进入，而管程每次只准许一个进程进入管程，从而实现了进程互斥。

管程是一种程序设计语言结构成分，它和信号量有同等的表达能力，从语言的角度看，管程主要有以下特性：

（1）模块化。管程是一个基本程序单位，可以单独编译。

（2）抽象数据类型。管程中不仅有数据，而且有对数据的操作。

（3）信息隐蔽。管程中的数据结构只能被管程中的过程访问，这些过程也是在管程内部定义的，供管程外的进程调用，而管程中的数据结构以及过程（函数）的具体实现外部不可见。

管程和进程不同，主要体现在以下几个方面：

（1）虽然两者都定义了数据结构，但进程定义的是私有数据结构PCB，管程定义的是公共数据结构，如消息队列等。

（2）两者都存在对各自数据结构上的操作，但进程是由顺序程序执行有关的操作，而管程主要是进行同步操作和初始化操作。

（3）设置进程的目的在于实现系统的并发性，而管程的设置则是解决共享资源的互斥使用问题。

（4）进程通过调用管程中的过程对共享数据结构实行操作，该过程就如通常的子程序一样被调用，因而管程为被动工作方式，进程则为主动工作方式。

（5）进程之间能并发执行，而管程则不能与其调用者并发。

（6）进程具有动态性，由“创建”而诞生，由“撤销”而消亡，而管程则是操作系统中的一个资源管理模块，供进程调用。

2.条件变量

在利用管程实现进程同步时，必须设置同步工具，如两个同步操作原语P和V。当某进程通过管程请求获得临界资源而未能满足时，管程便调用wait原语使该进程等待，并将其排在等待队列上。仅当另一进程访问完成并释放该资源之后，管程才又调用V原语，唤醒等待队列中的队首进程。

但是仅仅有上述的同步工具是不够的。考虑一种情况：当一个进程调用了管程，在管程中时被阻塞或挂起，直到阻塞或挂起的原因解除，而在此期间，如果该进程不释放管程，则其他进程无法进入管程，被迫长时间地等待。为了解决这个问题，引入了条件变量condition。通常，一个进程被阻塞或挂起的条件（原因）可有多个，因此在管程中设置了多个条件变量，对这些条件变量的访问，只能在管程中进行。

管程中对每个条件变量都须予以说明，其形式为：Var x，y：condition。对条件变量的操作仅仅是wait和signal，因此条件变量也是一种抽象数据类型，每个条件变量保存了一个链表，用于记录因该条件变量而阻塞的所有进程，同时提供的两个操作即可表示为x.wait和x.signal。

（1）x.wait。正在调用管程的进程因x条件需要被阻塞或挂起，则调用x.wait将自己插入x条件的等待队列上，并释放管程，直到x条件变化。此时其他进程可以使用该管程。

（2）x.signal。正在调用管程的进程发现x条件发生了变化，则调用x.signal，重新启动一个因x条件而阻塞或挂起的进程。如果存在多个这样的进程，则选择其中的一个；如果没有，则继续执行原进程，而不产生任何结果。这与信号量机制中的signal操作不同，因为后者总是要执行s：＝s＋1操作，因而总会改变信号量的状态。

如果有进程Q因x条件处于阻塞状态，当正在调用管程的进程P执行了x.signal操作后，进程Q被重新启动，此时两个进程P和Q，如何确定哪个执行，哪个等待，可采用下述两种方式进行处理：

（1）P等待，直至Q离开管程或等待另一条件。

（2）Q等待，直至P离开管程或等待另一条件。

采用哪种处理方式，当然是各执一词。Hoare采用了第一种处理方式，而Hansan选择了两者的折中，他规定管程中的过程所执行的signal操作是过程体的最后一个操作，于是进程P执行signal操作后立即退出管程，因而进程Q马上被恢复执行。