第4章进程的同步和死锁§4.1进程的同步和互斥4.1.1进程的同步1.进程同步举例例.公共汽车中的司机和售票员。§
4.1进程的同步和互斥2.进程同步的概念进程的同步是指系统中多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成一
项任务。具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状态，获得消息后被唤醒进入就绪
态。通常，把共同完成一个任务的若干进程称为合作进程。合作进程在并发执行时必须同步推进才能得到正确的执行结果。§4.1进程的
同步和互斥4.1.2进程互斥1.进程互斥举例假定系统中只有一台打印机，进程p1，p2都需要使用打印机，如果让它们同时使用，
则两个进程的输出交织在一起，打印出的结果无法使用。为了解决这一问题，进程使用之前先要提出申请，一旦系统将打印机分配给它，就一直由
它独占使用，其它申请使用打印机的进程则必须等待。进程p1和p2在逻辑上完全独立，毫无关系，只是由于竞争同一个物理资源而相互制约。
这种进程之间的间接制约关系不具有时间次序的特征，谁先向系统提出申请，谁就先执行。这种对共享资源的排他性的使用关系就是进程的互斥关系
。§4.1进程的同步和互斥2.临界资源在计算机的资源中，有些资源，如上面提到的打印机资源，一次能被一个进程使用，这类
资源称为临界资源（CriticalResource）。临界资源可能是硬件，也可能是软件：变量，数据，表格，队列等。它们虽然可以
被若干个进程所共享，但一次能为一个进程所利用。为了保证共享临界资源的各个进程能正确运行，当临界资源由一个进程占用后，其它进程如果
要使用它，必须等待占用进程使用完毕并把它释放后，才能由另一个进程使用。多个进程在共享临界资源时的这种制约关系称为进程的互斥。§
4.1进程的同步和互斥3.临界区的概念一个程序片段的集合，这些程序片段分散在不同的进程中，对某个共享的数据结构（共享资源）
进行操作。在进程中涉及到临界资源的程序段叫临界区或临界段。对临界区操作的诸进程必须互斥地进入临界区。§4.1进程的同步和
互斥临界区是对某一临界资源而言的，对于不同临界资源的临界区，它们之间不相交，所以不必互斥地执行，而相对于同一临界资源的若干个临界
区，则必须互斥的进入，即对临界资源的操作必须互斥地执行。例如有程序段A、B是关于变量X的临界区，而C、D是关于变量Y的临界区，那
么，A、B之间需要互斥执行，C、D之间也要互斥执行，而A与C、B与D之间不用互斥执行。§4.1进程的同步和互斥临界区进入
准则：空闲让进。当无进程处于临界区时，表明临界资源处于空闲状态，应允许一个请求进入临界区的进程立即进入自己的临界区。忙则等待
。当已有进程进入临界区时，表明临界资源正在被访问，因而其他试图进入临界区的进程必须等待。有限等待。对任何要求访问临界资源的进程，
应保证在有限的时间内能进入自己的临界区，以免陷入“死等”状态。让权等待。当进程不能进入自己的临界区，应立即放弃占用CPU，以使其
他进程有机会得到CPU的使用权，以免陷入“忙等”。§4.1进程的同步和互斥4.进程同步和互斥的区别互斥的各个进程在各自
单独执行时都可以得到正确的运行结果，但是当它们在临界区内交叉执行时就可能出现问题。而同步的各个进程，如果各自单独执行将不会完
成作业的特定任务，只要当它们互相配合、共同协调推进时才能得到正确的运行结果。互斥的进程只要求它们不能同时进入临界区，而至于哪个进
程先进入则不会产生运行的错误。但同步的进程的协调关系是建立在它们之间执行时序的基础上，所以，各个进程必须按照严格的先后次序执行。
一般情况下，互斥的进程并不知道对方的存在，而同步的进程不仅知道其它进程的存在，还要通过与其它进程的通信来达到相互的协调。§4.1
进程的同步和互斥4.1.3信号量机制信号量（Semaphore）机制是荷兰学者E.W.Dijkstra在1965年提出的
一种解决进程同步、互斥问题的更通用工具，并在THE操作系统中得到实现。信号量S是个整数变量，除了初始化外，它只能通过两个标准的
原子操作wait和signal来访问。这两个操作原来被称为P(用于wait，表测试)和V(用于signal，表增加)操作。§4
.1进程的同步和互斥wait的经典定义可用伪代码表示为：wait(s){while(s<=0)；
//no.ops--..;}signal的经典定义可用伪代码表示为：signal(s){s
++；}§4.1进程的同步和互斥1.信号量的使用可使用信号量来解决n个进程的临界区问题。这n个进程共享一个信号量mu
tex,并初始化为1。每个进程Pi的组织结构如下：§4.1进程的同步和互斥也可以使用信号量来解决各种同步问题。例如，考虑
两个正在执行的并发进程：p1有语句s1，而p2有语句s2。假设要求只有在s1执行完之后才执行s2，可以很容易地实现这一要求：让p1
和p2共享一个共同信号量synch，且初始化为0。在进程p1中插入语句：s1;
signal(synch);在进程p2中插入语句：
wait(synch);s2;§4.1进程的同步和互斥2.信号量的实现上面定义的
信号量虽然能够用来解决进程的同步和互斥问题，但存在一个明显的缺陷，即该机制没有遵循“让权等待”的原则，而是使进程处于“忙等”状态。
为了克服这个缺点，可定义一个结构体信号量：typedefstruct{intvalue;
structprocessL;//进程链表}semaphore;§4.1进程的同步
和互斥信号量操作wait现在可按如下来定义：voidwait(semaphoreS){S.value-
-;if(S.value<0){addthisprocesstoS.L;
block();}}信号量操作signal现在可按如下来定义：voidsignal(
semaphoreS){S.value++;if(S.value<=0){
removeaprocessPfromS.L;wakeup(P)
;}}§4.1进程的同步和互斥信号量的说明：在信号量的实现中，S.value的初值表示系统某类资源
的数目，因而又称为资源信号量，对它的每次wait操作，意味着进程请求一个单位的该类资源。当S.value<0时，表示该类资源已分
配完毕，因而进程调用block原语，进行自我阻塞，放弃处理机，并插入到信号量链表S.L中。此时，S.value的绝对值表示在该信号
量链表中已阻塞进程的个数、亦即恰好等于对信号量S实施wait操作而被封锁起来并进入信号量S队列的进程数。对信号量的每次signa
l操作，表示执行进程释放一个单位资源。§4.1进程的同步和互斥3.AND型信号量(1)问题的引入
假定有两个进程A和B，它们都要求访问共享数据D和E。当然，共享数据都应作为临界资源。为此，可为这两个数据分别设置用于互斥的信号量D
mutex和Emutex，并令它们的初值都是1。相应地，在两个进程中都要包含两个对Dmutex和Emutex的操作，即p
rocessA:processB:wait(Dmutex);
wait(Emutex);wait(Emutex);
wait(Dmutex);若进程A和B按下述次序交替执行wait操作：process
A:wait(Dmutex);于是Dmutex=0processB:wait(Emutex);于是Emutex
=0processA:wait(Emutex);于是Emutex=-1,A阻塞processB:w
ait(Dmutex);于是Dmutex=-1,B阻塞§4.1进程的同步和互斥(2)AND型信号量的基本思想上述例子出现
死锁的原因主要在于进程运行时需要多个资源，在为每个进程分配所需的全部资源时，不能保证原子操作，从而导致进程之间相互等待对方释放所占
资源的死锁状态。为了解决进程同时需要多种资源且每种资源要占用一段时间的问题，人们提出了AND型信号量同步机制。AND型信号量
的基本思想：将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程
，其他所有可能为之分配的资源，也不分配给它。亦即，对若干个临界资源的分配，采取了原子操作方式：要么全部分配给进程，要么一个也不分配
。§4.1进程的同步和互斥AND型信号量wait原语为Swait,其定义如下：Swait(S1,S
2,…,Sn) {if(S1>=1&&S2>=1&&…&&Sn>=1){ //满足资源要求时
的处理；for(i=1;i<=n;++i).–-Si;}else{ //某些资源不够时的处理
；调用进程进入第一个小于1信号量的等待队列Sj.queue;阻塞调用进程;}}§4.1
进程的同步和互斥AND型信号量集signal原语为Ssignal,其定义如下：Ssignal(S1,S2,…,Sn)
{for(i=1;i<=n;++i){++Si; //释放占用的资源；for(在Si
.queue中等待的每一个进程P){从等待队列Si.queue中取出进程P;if(判断进程P是否通过
Swait中的测试)//重新判断{进程P进入就绪队列;break；}
else进程P进入某等待队列；}}}§4.1进程的同步和互斥引入AND信号量后，上面的例子就可以简单改写
为：processA:processB:Swait(Dmu
tex,Emutex);Swait(Emutex,Dmetux);………
………Ssignal(Dmutex,Emutex);
Ssignal(Emutex,Dmutex);这样也就不会出现死锁问题。§4.1进程的同步和互斥4.
信号量的应用利用信号量可以很好的解决进程之间的同步问题。一般同步问题可分为两类：一类是保证一组合作进程按
逻辑需要所确定的次序执行；另一类是保证共享缓冲区（或共享数据）的合作进程的同步。（1）合作进程的执行次序若干个进程为了完成一个
共同任务而并发执行，然而，这些并发进程之间根据逻辑上的需要，有的操作可以没有时间上的先后次序，即不论谁先做，最后的计算结果都是正确
的。但有的操作有一定的先后次序，也就是说它们必须遵循一定的同步规则，只有这样，并发执行的最后结果才是正确的。§4.1进程
的同步和互斥为了描述方便，可以用一个图来表示进程集合的执行次序。图的连接描述了进程开始和结束的次序约束。此图称为进程流图。如果用
s表示系统中某一任务启动，f表示完成，则可以下列的进程流图来表示这一组合作进程执行的先后顺序。§4.1进程的同步和互斥例题
：假设某个程序段包含如下语句：inta,b,c,d,e,f;intt1,t2,t3,t4,t5
;t1=a+b;t2=c+d;t3=e/f;t4=t1t2;
t5=t4-t3;§4.1进程的同步和互斥例题4-1：进程pa,pb,pc为一组合作进程，其进程流图如右图所
示，使用信号量机制来实现这三个进程的同步。§4.1进程的同步和互斥§4.1进程的同步和互斥（2）共享缓冲区
的进程的同步例题4-2：设某计算进程cp和打印进程iop共用一个单缓冲区（如右图所示）。其中，cp进程负责不断地计算数据并
送入缓冲区buffer中，iop进程负责不断地从缓冲区buffer中取出数据去打印。§4.1进程的同步和互斥§4.2
经典同步问题4.2.1生产者—消费者问题1.问题描述生产者——消费者问题可描述如下：有n个生产者和m个消费者，连接
在一个有N个单位缓冲区的有界缓冲上。其中，pi和cj都是并发进程，只要缓冲区未满，生产者pi生产的产品就可投入缓冲区；只要缓冲区不
空，消费者进程cj就可从缓冲区取走并消耗产品。如右图所示。§4.2经典同步问题2.问题分析为了使这两类进程协调工作，防
止盲目生产和消费，它们应满足如下的同步条件：任何时刻所有生产者存放产品的数目不能超过缓冲区的总容量（N）;所有消费者取出的产品
总量不能超过所有生产者当前生产的产品总量。设置三个信号量：full：表示放有产品的缓冲区数，其初值为0。empty：表示
可供使用的缓冲区数，其初值为N。mutex：互斥信号量，初值为1，表示各进程互斥进入临界区，保证任何时候只有一个进程使用缓冲区。
voidproducer()voidconsumer()
{{
do{do{……
wait(full);produ
ceaproduct;wait(mutex); ……
……wait(empty);
removeanitemfrombuffer;wait(mutex);
……; ……
signal(mutex);addnextptobuffer;
signal(empty); ……
……signal(mutex);cons
umetheiteminnextc;signal(full);
……}while（1）；}while(1);
}}§4.2
经典同步问题4.2.2读者—写者问题1.问题描述：有两组并发进程：读者和写者，共享一个文件F，要求：允许多个读者同时执行
读操作任一写者在完成写操作之前不允许其它读者或写者工作写者执行写操作前，应让已有的写者和读者全部退出2.问题分析：通过
分析，我们可以发现读者和写者、写者和写者之间必须保持互斥，为此应设置一个信号量（wmutex）用于读者和写者以及写者和写者之间的
互斥。另外，为了说明多个读者可以同时读，可以设置一个读者计数器（readcount）。它是一个整型变量，初值为0。§4.2
经典同步问题读者Readers:while(TR
UE){wait(rmutex);
readcount=read
count+1;if(readcount==1)
wait(wmutex);
signal(rmutex);执行读操
作wait(rmutex);readcount=readcount-1;
if(readcount==0)singal(wmutex);si
ngal(rmutex);使用读取的数据}§4.2经典同步问题4.2.3哲学家进餐问题
1.问题描述：假设有五个哲学家，他们花费一生的时光思考和吃饭。这些哲学家公用一个圆桌，每个哲学家都有一把椅子。在桌中央有一碗
米饭。每个哲学家面前有一只空盘于，每两人之间放一根筷子（如右图）。当一个哲学家思考时，他与其他同事不交互，时而，哲学家会感到饥饿，
并试图拿起与他最近的两支筷子（他与邻近左、右两人之间的筷子）。一个哲学家一次只能拿起一支筷子。显然，他不能从其他哲学家手里拿走筷子
。当一个饥饿的哲学家同时有两支筷子时，他就能不用释放他的筷子而自己吃了。当吃完后，他会放下两支筷子，并再次开始思考。§4.2
经典同步问题设fork[5]为5个信号量，初值均为1voidphilosopher(inti){while(1
){思考；wait(fork[i]);wait(fork[(i+1)%5])；
进食；signal(fork[i]);signal(fork[(i+1)%5])；}}§4.2
经典同步问题分析:以上解法会出现死锁。为防止死锁发生可采取的措施：最多允许4个哲学家同时坐在桌子周围仅当一个哲学家左右两边
的筷子都可用时，才允许他拿筷子（?）给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之为了避免死锁，把
哲学家分为三种状态，思考，饥饿，进食，并且一次拿到两只筷子，否则不拿。§4.2经典同步问题采用AND信号量集解决哲学家就餐
问题设fork[5]为5个信号量，初值为均1Philosopher（i）while(1){思考；
Swait(fork[i],fork[(i+1)%5])；进食；Ssignal(fork[i],
fork[(i+1)%5])；}§4.2经典同步问题4.2.4理发师问题1.问题描述：理发店有一位理发
师、一把理发椅和n把供等候理发的顾客坐的椅子。如果没有顾客，理发师便在理发椅上睡觉。一个顾客到来时，他必须叫醒理发师。如果理发师正
在理发时又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则就离开这个理发店。§4.2经典同步问题2.问题分析
为了解决这个问题，可以定义三个信号量customer、barbers和mutex以及一个计数变量waiting。信号量cus
tomer用来记录等待理发的顾客数（不包括正在理发的顾客），其初值化为0。信号量barbers用来记录正在等候顾客的理发师数，其
初值为0或1。信号量mutex用于对变量waiting的互斥操作。计数变量waiting记录正在等候理发的顾客数，初值为0
。它实际上是信号量customer的一份拷贝，之所以使用变量waiting主要是因为无法读取信号量的当前值。§4.2经典同
步问题3.具体解法如下：§4.2经典同步问题§4.3管程4.3.1管程的概念1.问题的提出采用信号
量同步机制来编写并发程序，对于共享变量及信号量变量的操作将被分散于各个进程中，具有以下缺点：易读性差，因为要了解对于一组共享变量
及信号量的操作是否正确，则必须通读整个系统或者并发程序。不利于修改和维护，因为程序的局部性很差，所以任一组变量或一段代码的修改都
可能影响全局。正确性难以保证，因为操作系统或并发程序通常很大，要保证这样一个复杂的系统没有逻辑错误是很难的。§4.3管程
2.管程的概念一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据。
管程由三部分组成：（1）局部于管程的若干公共变量说明；（2）对该数据结构进行操作的一组过程；（3）对局部于管程的数据设置初
值的语句。此外，还必须给管程赋予一个名字。§4.3管程管程具有以下三个特性：管程内部的局部数据变量只能被管程内定义的过程
所访问，不能被管程外面声明的过程直接访问。进程要想进入管程，必须调用管程内的某个过程。一次只能有一个进程在管程内执行，而其余调
用该管程的进程都被挂起，等待该管程成为可用的。即管程能有效地实现互斥。§4.3管程4.3.2条件变量管程构造确保一次只
能有一个进程在管程内活动，提供了一种实现互斥的简便途径，但这还不够，还需要一种办法使得进程在无法继续运行时被阻塞。例如，当一个进程
进入管程后等待某个条件未满足时，这个进程必须挂起，释放管程，以便其他进程能够进入。以后，当所需的条件满足了，且该管程处于可用的情况
下，就要恢复该进程的执行，且让它在先前的挂起点重新进入该管程。解决这个问题的方法是引入条件变量（conditionvariab
les）。条件变量是当调用管程过程的进程无法运行时，用于阻塞进程的一种信号量，它包含在管程内，且只能在管程内对它进行访问。对条件变
量仅有的操作是wait和signal。当一个管程过程发现无法继续时，它在某些条件变量condition上执行wait，这个动作引起
调用进程阻塞，并将另一个先前被挡在管程之外的进程调入管程。§4.3管程另一个进程可以通过对其伙伴在等待的同一个条件变量co
ndition上执行同步原语signal操作来唤醒等待进程。使用signal释放等待进程时，可能出现两个进程同时停留在管程内。解
决方法：执行signal的进程等待，直到被释放进程退出管程或等待另一个条件被释放进程等待，直到执行signal的进程退出管程或
等待另一个条件§4.3管程4.3.3利用管程解决生产者—消费者问题在利用管程方法来解决生产
者—消费者问题时，首先要为它们建立一个管程，并命名为Procedure_Consumer,其中包括两个过程：（1）pu
t(item)过程。生产者利用该过程将自己生产的产品放入缓冲池，并用整型变量count来表示在缓冲池中已有的产品数目，当count
≥n时，表示缓冲池已满，生产者必须等待。（2）get(item）过程。消费者利用该过程从缓冲池中取走一个产品，当coun
t≤0时，表示缓冲池中已无可取走的产品，消费者应等待。§4.3管程monitorProcedure_Consumer
{intin,out,count;itembuffer[n];//空缓冲区数目condi
tionnotfull,notempty;//条件变量voidput
(item){if（count≥n）notfull.wait;buffer[in]=item;
in=(in+1)%n;count=count+1;if（notempty.queque）
notempty.signal;}§4.3管程voidproceducer(){
repeatproduceaniteminnextp;Procedure_Consumer
.put(nextp);untilfalse;}voidconsumer{rep
eatProcedure_Consumer.get(nextc);consumetheitem
innextc;untilfalse;}§4.4进程同步实例研究4.4.1WindowsSer
ver2003中的进程同步互斥对象(Mutex)就是互斥信号量，在一个时刻只能被一个线程使用。它的相关API包括：Create
Mutex、OpenMutex和ReleaseMutex。CreateMutex创建互斥对象，返回对象句柄；OpenMutex
打开并返回一个已存在的互斥对象句柄，用于后续访问；ReleaseMutex释放对互斥对象的占用，使之成为可用。信号量对象（Sem
aphore）就是资源信号量，初始值的取值范围在0到指定最大值之间，用于限制并发访问的线程数。它的相关API包括：CreateSe
maphore、OpenSemaphore和ReleaseSemaphore。CreateSemaphore创建一个信号量对象，
在输入参数中指定初值和最大值，返回对象句柄。OpenSemaphore打开并返回一个已存在的信号量对象句柄，用于后续访问。Rel
easeSemaphore释放对信号量对象的占用，使之成为可用。§4.4进程同步实例研究事件对象（Event）相当于“
触发器”，用于通知一个或多个线程某事件的出现。它的相关API包括：CreateEvent、OpenEvent、SetEvent、R
esetEvent和PulseEvent。CreateEvent创建一个事件对象，返回对象句柄。OpenEvent打开并返回一
个已存在的事件对象句柄，用于后续访问。SetEvent和PulseEvent设置指定事件对象为可用状态。ResetEvent设置指
定事件对象为不可用状态。对于这三种同步对象，WindowsServer2003系统提供两个统一的等待操作WaitForSin
gleObjec和WaitForMultipleObjects。WaitForSingleObjec可在指定的时间内等待指定对象为
可用状态；WaitForMultipleObjects可在指定的时间内等待多个对象为可用状态。§4.4进程同步实例研究4
.4.2Linux中的进程同步Linux提供了提供了两类进程同步原语。一是内核同步原语，也就是通常的计数信号量
。它既可以用于单处理机系统也可用于多处理机系统。另一类原语是二进制信号量，称为自旋锁（spinlock）。信号量是一种睡眠锁，
它可以允许任意数量的锁持有者。信号量同时允许的持有者的数量可以在声明信号量时指定。信号量的两个原子操作p（wait）和v(sign
al)操作在Linux系统分别称为down()和up()操作。down()操作通过对信号量计数减1来请求获得一个信号量。如果结果
是0或大于0，获得信号量锁，任务就可以进入临界区。如果结果是负数，任务会被放入等待队列，处理器执行其他任务。相反，当临界区中的操作
完成后，up()操作用来释放信号量，如果在该信号量上的等待队列不为空，那么处于队列中等待的任务在被唤醒的同时获得信号量。§4.4
进程同步实例研究自旋锁是Linux内核中最常见的锁。自旋锁最多只能被一个进程持有。如果一个进程试图去获得一个被其他进程持有的
自旋锁，那么该进程就会一直进行“忙等待——旋转——等待锁重新可用”。要是锁没有被争用，请求锁的进程便能立即得到它，继续执行。在任意
时间，自旋锁都可以防止多于一个的进程同时进入临界区。一个被争用的自旋锁使得请求它的进程在等待锁重新可用时自旋（特别浪费处理机时间）
，所以自旋锁不应该被长时间持有。自旋锁的基本使用形式如下：spinlock_t_mr_lock=SPIN_LOCK_UNLOCK
ED;spin_lock(&mr_lock);/临界区/spin_unlock(&mr_lock);§4.5
进程通信并发进程之间的交互必须满足两个基本要求：同步和通信。进程竞争资源时要实施互斥，互斥是一种特殊的同步，实质上需要解决好
进程同步问题。进程同步是一种进程通信，通过修改信号量，进程之间可建立起联系，相互协调运行和协同工作。进程协同工作时，需要互相交
换信息，有些情况下进程间交换的少量信息，有些情况下进程间交换大批数据。进程之间互相交换信息的工作称为进程通信IPC（InterP
rocessCommunication）。§4.5进程通信4.5.1进程通信的方式1.信号通信机制在计算机软件中
提到的信号不是一个抽象的概念，而是非常具体的一组事件。核心用整数来标识这些事件。每个进程在执行时，都要通过信号机制来检查是否有信号
到达。若有信号到达，表示某进程已发生了某种异常事件，便立即中断正在执行的进程，转向由该信号（某整数）所指示的处理程序，去完成对所发
生的事件（事先约定）的处理。处理完毕，再返回此前的断点处继续执行。可见，信号机制是对硬件中断的一种模拟，因此又称软中断。信号机制
是一种简单的异步通信机制，当某个事件发生时，核心或发送进程发送给进程的信号实际上就是事先定义好的代表该事件的一个整数，所以说，信号
是一个很短的信息。信号不但能从内核发给一个进程，也能由一个进程发给另一个进程。§4.5进程通信2.管道通信机制管道(
pipeline)是连接一个读进程和一个写进程以实现它们之间通信的一个特殊共享文件，又称为pipe文件。它允许进程按先进先出方式传
送数据,也能使进程同步执行操作。向管道提供数据输入的发送进程（即写进程），以字符流形式把大量数据送入管道，而接收管道输出
的接收进程（即读进程），则从管道中接收（读取）数据。§4.5进程通信管道的实质是一个共享文件，基本上可借助于文件系统的机
制实现，包括（管道）文件的创建、打开、关闭和读写。读写进程相互协调，必须做到：进程对通信机构的使用应该互斥，一个进程正在使用某
个管道写入或读出数据时，另一个进程就必须等待。发送者和接收者双方必须能够知道对方是否存在，如果对方已经不存在，就没有必要再发送信
息。§4.5进程通信3.共享内存通信机制为了在进程间传送大量数据，在存储器中划出一块共享存储区，诸进程可通过对共享存储区
中的数据地读或写来实现通信。进程在通信前，先向系统申请获得共享存储区中的一个分区，并指定该分区的关键字，若系统已经给其它进程分配
了这样的分区，则将该分区的描述符返回给申请者。接着，申请者把获得的共享存储分区连接到本进程上，此后，便可象读、写普通存储器一样地读
、写该公用存储区。实现共享存储区通信的关键在于进程自己要负责共享存储区的同步和互斥问题。§4.5进程通信4.消息传递系
统在消息传递系统中，进程间的数据交换是以格式化的消息(message)为单位的，程序员直接利用系统提供的一组通信命令（原语）进
行通信。操作系统隐藏了通信的实现细节，简化了通信程序编制的复杂性。消息通信机制有以下两种实现方式：（1）直接通信方式。发送进程
直接把消息发送给接收者，并将它挂在接收进程的消息缓冲队列上。接收进程从消息缓冲队列中取得消息，这种通信方式也称为消息缓冲通信。（
2）间接通信。发送进程将消息发送到某种中间实体中（信箱），接收进程从中取得消息。这种通信方式也称信箱通信。在网络中称为电子邮件系统
。§4.5进程通信4.5.2基于消息的通信1.直接通信发送或接收消息的进程必须指出信件发给谁或从谁那里接收
消息原语send（P，消息）：把一个消息发送给进程P原语receive（Q，消息）：从进程Q接收一个消息2.间接通信
进程间发送或接收消息通过信箱进行，消息可被理解成信件?原语send（A，信件）：把一封信件（消息）传送到信箱A?原语rece
ive（A，信件）：从信箱A接收一封信件（消息）§4.5进程通信4.5.3消息缓冲队列通信1.消息缓冲队列通信机制
在操作系统空间设置一组缓冲区。当发送进程需要发送消息时，执行send系统调用，产生访管中断，进入操作系统。操作系统为发送进程分
配一个空缓冲区，并将所发送的消息从发送进程copy到缓冲区中，然后将该载有消息的缓冲区连接到接收进程的消息链链尾，如此就完成了发送
过程。§4.5进程通信发送进程返回到用户态继续执行。在以后某个时刻，当接收进程执行到receive接收原语时，也产生访管
中断进入操作系统。由操作系统将载有消息的缓冲区从消息链中取出，并把消息内容copy到接收进程空间，之后收回缓冲区，如此就完成了消
息的接收，接收进程返回到用户态继续进行。§4.5进程通信为了实现消息缓冲队列通信，需要设置相关的数据结构，其中主要利用的数
据结构是消息缓冲区。它可描述如下：typemessageBuffer=recordsend
er;//发送消息的进程名或标识符size;//发送的消息长度
text;//发送的消息正文next;//指向下一个消息缓冲区的指针
end除此之外，在设置消息缓冲区队列的同时，还应增加用于对消息队列进行操作和实现同步的信号量，并将它们置入进程的PCB
中。在进程的PCB中涉及通信的数据结构有：?????mptr：消息队列队首指针????mutex：消息队列互斥信号量,初值
为1?????sm：表示接收进程消息队列上消息的个数，初值为0，是控制收发进程同步的信号量§4.5进程通信§4.5进
程通信2.发送原语send（R,M）begin在OS中分配M.size大小的缓冲区t;将
M中的内容复制到t;得到进程R的PCB的指针q；wait(q.mutex); 将t挂到队列q.mq队尾；si
gnal(q.mutex);signal（q.sm);end§4.5进程通信3.接收原语Receive(N）
begin得到本进程PCB的指针q；wait(q.sm);wait(q.mute
x);从q.mq队首取下一个缓冲区t；siganl(q.mutex);将t的内容复制到N，并释放ten
d§4.5进程通信4.5.4客户/服务器系统通信1.套接字（socket）套接字（socket）可定义为通信的
端点。一对通过网络通信的进程需要使用一对套接字，即每个进程各一个。套接字由IP地址和端口号连接组成。通常，套接字采用客户机/服务
器结构。服务器通过监听指定端口来等待进来的客户机的请求。一旦收到请求，服务器就接受来自客户机套接字的连接，从而完成通信连接。服务
器实现的特定服务（如telnet、ftp和http）是通过监听熟知端口（telnet服务器监听端口23，ftp服务器监听端口21，
Web或http服务器监听端口80）进行的。所有低于1024的端口都认为是众所周知的，可用它们来实现标准服务。§4.5进程通
信§4.5进程通信§4.6死锁4.6.1死锁的概念设系统有一台打印机和一台扫描仪，进程P1、P2并发执行，
在某时刻T，进程P1和P2分别占用了打印机和扫描仪。在时刻T1（T1>T），P1又要申请扫描仪，但由于扫描仪被P2占用，P1只有等
待。在时刻T2（T2>T），P2又申请打印机，但由于打印机被P1占用，P2只有等待。如此两进程均不能执行完成。称这种现象为死锁。具
体过程可描述如下：时刻进程p1进程p2
request(打印机)；request(扫描仪)；Tholding
打印机；holding扫描仪；T1request(扫描仪)；
…T2…request(打印机)；§4.6
死锁操作系统中的死锁指：如果在一个进程集合中的每个进程都在等待只能由该集合中的其他一个进程才能引发的事件，则称一组进程或系统
此时发生了死锁。例如，n个进程P1、P2，…，Pn，Pi因为申请不到资源Rj而处于等待状态，而Rj又被Pi+1占有，Pn欲申请的
资源被P1占有，此时这n个进程的等待状态永远不能结束，则说这n个进程处于死锁状态。§4.6死锁4.6.2死锁产生的原因
和必要条件1.死锁产生的原因:死锁产生的原因可归结为如下两点：（1）资源有限。当系统中多个进程共享资源，如打印机、公用队列
等，其数目不足以满足诸进程的需要，会引起进程对资源的竞争而产生死锁。（2）并发进程间的推进顺序不当。进程在运行过程中，请求和释放
资源的顺序不当，也会导致产生进程死锁。§4.6死锁§4.6死锁2.死锁产生的必要条件:互斥条件：涉及的资源
是非共享的。不剥夺条件：不能强行剥夺进程拥有的资源。部分分配条件：进程在等待一新资源时继续占有已分配的资源。环路条件：存在一
种进程的循环链，链中的每一个进程已获得的资源同时被链中的下一个进程所请求。§4.6死锁4.6.3死锁的描述——资源分
配图系统资源分配图是一个有向图，该图有一个节点的集合V和一个边的集合E组成。节点集合V分成两种类型的节点P={p1,p2,
…,pn}，它由系统中所有活动进程组成；R={r1,r2,…,rm}，它由系统中全部资源类型组成。从进程pi到资源类型
rj的有向边记为pi→rj，它表示进程pi申请了资源类型rj的一个实例，并正在等待资源。从资源类型rj到进程pi的有向边记为rj
→pi，它表示资源类型的一个实例rj已经分配给进程pi。有向边pi→rj称为申请边，而有向边rj→pi称为分配边。§4.6
死锁在资源分配图中，通常用圆圈表示每个进程，用方框表示每种资源类型。由于同一资源类型可能有多个实例，所以在矩形中用圆点数表示
实例数。注意申请边只指向表示资源的矩形，而分配边必须指向矩形内的某个圆点。§4.6死锁根据资源分配图的定义，可以证明：如果
资源分配图中没有环，系统就没有死锁。如果图中有环，那么就可能存在死锁。如果每类资源的实体都只有一个，那么图中出现环路就说明死锁了
。在这种情况下，资源分配图中存在环路是死锁存在的充分必要条件；如果每类资源的实体不止一个，那么资源分配图中出现环路并不表明一定出现
死锁，在这种情况下，资源分配图中存在环路是死锁存在的必要条件，但不是充分条件。§4.6死锁§4.6死锁4.6.4处
理死锁的方法从原理上来说，有三种方式可处理死锁问题：利用某些协议预防或避免死锁，保证系统不会进入死锁状态。允许系统进入死锁状
态，然后设法发现并克服它。完全忽略这个问题，好像系统中从来也不会出现死锁。这种方法为大多数操作系统，如UNIX系统所使用。§4
.7死锁的预防和避免4.7.1死锁的预防死锁的产生需要一定的条件，因此，只要采取一定的措施来确
保死锁产生的必要条件中的一个或多个不成立，就可能预防死锁。（1）破坏互斥条件：（2）部分分配（占
有并等待）条件：静态资源分配（3）不剥夺条件：抢占资源（4）环路条件：资源编号，按序号递增的方式申请
§4.7死锁的预防和避免4.7.2死锁的避免死锁避免定义：在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行
动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配安全状态：如果系统能按某种顺序（如P
4，P1，…,Pn,称为安全序列）为每个进程分配其所需的资源，直至所有进程都能运行完成，称系统处于安全状态。若不存在这样一个安全
序列称系统处于不安全状态。§4.7死锁的预防和避免安全状态举例：有三个进程p1,p2,p3，有12台磁带机。P1共要
求10台，P2共要求4台，P3共要求9台。在T0时刻，p1,p2,p3分别获得5、2、2台，尚有3台空闲。经分析，
在T0时刻，系统是安全的。因为存在一个安全序列p2、p1、p3§4.7死锁的预防和避免银行家算法的原理银行家算法的实质就
是:要设法保证系统动态分配资源后不进入不安全状态，以避免可能产生的死锁。即每当进程提出资源请求且系统的资源能够满足该请求时，系统将
判断如果满足此次资源请求，系统状态是否安全。如果判断结果为安全，则给该进程分配资源，否则不分配资源，申请资源的进程将阻塞，直到其他
进程释放出足够资源为止。银行家算法的执行有个前提条件，即要求进程必须预先提出自己的最大资源请求数量，这一数量不可能超过系统资源的
总量，系统资源的总量是一定的。§4.7死锁的预防和避免银行家算法的数据结构◆可用资源向量Available：长度为m的
向量表示系统中各类资源的当前可用实例数。如果Available[j]=k，表示系统中现有Rj类资源k个。◆最大需求矩阵Max：
n×m矩阵定义每个进程对各类资源的最大需求量。如果Max[i,j]=k，那么进程Pi最多可申请k个资源类型Rj的实例。◆已分配
资源矩阵Allocation：n×m矩阵定义了每个进程现在所分配的各种资源类型的实例数。如果Allocation[i,j]=k，
表示进程Pi当前分到k个Rj类资源。◆需求矩阵Need：n×m矩阵表示每个进程还需要的各类资源的数目。如果Need[i,j
]=k，表示进程Pi尚需k个Rj类资源才能完成其任务。很显然，Need[i,j]=Max[i,j]-Allocation[i
,j]，因而，这些数据结构的大小和值会随着时间而改变。§4.7死锁的预防和避免安全检查算法①令Work和Finish分
别表示长度为m和n的向量。按如下方式进行初始化：Work=Available，Finish[i]=false，i=1,2,…,
n。②搜寻满足下列条件的i值：Finish[i]==false，且Need[i]≤Work。如果没有这样的
i存在，则转向步骤④。③修改数据值：Work=Work+Allocation[i]（Pi释放所占的全部资源
）Finish[i]=true并返回步骤②。④若Finish[i]==true对所有i都成立，则系统处于
安全状态；否则，系统处于不安全状态。§4.7死锁的预防和避免资源请求算法设Request[i]表示进程Pi的
申请向量。Request[i,j]=k，表示进程Pi需要申请k个Rj类资源。当进程Pi申请资源时，就执行下列动作：①若Req
uest[i]＞Need[i]，产生出错条件，因为进程Pi对资源的请求量已超过其说明的最大数量。否则，转到步骤②。②如果Re
quest[i]＞Available，则进程Pi必须等待，这是因为系统现在没有可用的资源。否则，转到步骤③。③假设系统可以给进
程Pi分配所请求的资源，则应对有关数据结构进行修改：Available=Available–Reques
t[i];Allocation[i]=Allocation[i]+Request[i];
Need[i]=Need[i]–Request[i];④系统执行安全性算法，查看此时系统状态是否安全。如果是安全的，
就实际分配资源，满足进程Pi的此次申请；否则，若新状态是不安全的，则Pi等待，对所申请资源暂不予分配，并且把资源分配状态恢复成③
之前的情况。§4.7死锁的预防和避免例题：设系统有五个进程和三类资源，每类资源分别有10、5、7。在T0时刻资源分配情况如
图§4.7死锁的预防和避免T0时刻可以找到一个安全序列{p1,p3,p4,p2,p0}.系统是安全的。§4
.7死锁的预防和避免P1发出请求Request(1,0,2)，执行银行家算法§4.7死锁的预防和避免可以找到一个安全
序列{p1,p3,p4,p0,p2}.系统是安全的，可以将P1的请求分配给它。§4.7死锁的预防和避免P4发出请求Req
uest(3,3,0),执行银行家算法Available=（2，3，0）不能通过算法第2步（Request[i]≤Av
ailable），所以P4等待。P0请求资源Request（0，2，0），执行银行家算法：§4.8死锁的检测和解除
解决死锁问题的一条途径是死锁检测和解除，这种方法对资源的分配不加任何限制，也不采取死锁避免措施，但系统定时地运行一个“死锁
检测”程序，判断系统内是否已出现死锁，如果检测到系统已发生了死锁，再采取措施解除它。§4.8死锁的检测和解除4.8.1
死锁的检测资源分配图可以形象直观地描述出进程的死锁状态，因此，可以利用资源分配图化简的方法来检测系统处于某一时刻的状态
是否是死锁状态。资源分配图的化简方法如下：（1）在资源分配图中，找出一个既不阻塞又非独立的进程结点Pi.在顺利的情况下，Pi可获
得所需资源而继续运行，直至运行完毕，再释放其所占用的全部资源，这相当于消去Pi所有的请求边和分配边，使其成为孤立结点。（2）再把
相应的资源分配给一个等待该资源的进程，即将某进程的申请边变为分配边。（3）在进行了一系列的简化后，若能消去图中所有的边，使所有进
程结点都成为孤立结点，则称该图是可完全简化的；若不能通过任何过程使该图完全简化，则称该图是不可完全简化的。§4.8死锁的检测
和解除§4.8死锁的检测和解除4.8.2死锁的解除通过抢占资源实现恢复和通过杀掉进程解除死锁。1．通过
抢占资源实现恢复即临时性地把资源从当前占有它的进程那里拿过来，分给另外某些进程，直至死锁环路被打破。2．通过杀掉进程实现
恢复终止所有的死锁进程。一次终止一个进程，直至消除死锁环路。重点概念和内容提示进程同步和互斥的概念、临界资源和临界区临
界区使用原则信号量的定义及物理含义利用信号量解决进程同步和互斥问题死锁的概念、产生的原因和必要条件解决死锁问题的方法：死锁
的预防、避免及死锁的检测和解除对于较复杂的资源分配图，可能有多个既未阻塞，又非孤立的进程结点，有关文献已经证明，所有的简化顺序，
都将得到相同的不可化简图。同样可以证明：S状态为死锁状态的充分条件是当且仅当S状态的资源分配图是不可完全简化的。该充分条件被称为死
锁定理。接收进程名:Q信件长:5c正文:ABCDESend(发送区首址)发送区消息队列首指针mut
exsm发送进程名:P信件长:5正文:ABCDE后继信件缓冲指针0进程Q的PCB发送进程名:P信件长
:5正文:ABCDEreceive(接收区首址)接收区进程P进程Q2.远程过程调用远程过程调用（Remo
teProcedureCall,RPC）是远程服务的一种常见形式。RPC是网络连接系统之间采用的抽象过程调用机制。远程过程调
用的思想很简单：允许程序调用另外机器上过程。当机器A的一个客户进程（或者线程）调用机器B上的一个过程时，A上的调用进程挂起，被调用
过程在B上开始执行。调用者以参数形式把信息传送给被调用者，被调用者把过程执行结果回送给调用者。对程序员来说，完全看不到消息传送或者
I/O。RPC象一个常规过程，需要进行同步。调用者发出命令后就一直等待着，直到它得到结果。RPC把在网络环境下过程调用所产生的各
种复杂情况都隐藏起来。在其内部，RPC的超时重传软件收集参数值，构成消息，且把这个消息发往远程服务器。服务器接受请求后，打开参数调
用过程，并将回答返给客户。（1）集合P、R和E：P={P1,P2,P3}R={r1,r2,r3,r4}E={p1→r1
,p2→r3,r1→p2,r2→p2,r2→p1,r3→p3}（2）资源实例资源类型r1有1个实例，资源类
型r2有2个实例，资源类型r3有1个实例，资源类型r4有3个实例有死锁的资源分配图p1→r1→p2→r3→p3→r2→p1
p2→r3→p3→r2→p2有环路但无死锁的资源分配图p1→r1→p3→r2→p1729p3224p
235510p1可用还需已分配最大需求进程写者Writers：while(TRUE){
wait(wmutex);执行写操作singal(wmutex);}
这个算法隐含读者的优先级高于写者。#defineCHAIR5
/为顾客准备的椅子数/intwaiting=0;/等候理发的顾客数/
semaphorecustomers=0;semaphorebarbers=0;semaphoremut
ex=1;voidbarber(){while(TRUE);/理完一人,还有顾客吗?/{
wait(cutomers);/若无顾客,理发师睡眠/wait(mutex);
/进程互斥/waiting=waiting-1;//等候顾客数少一个cut_ha
ir();//理发师为一个顾客理发signal(mutex);/开放临界区
/signal(barbers);//理发师为顾客理完发}]voidcustomer()
{wait(mutex);/进程互斥/if(waiting<
CHAIRS){/看看有没有空椅子/waiting=waiting+1;/
等候顾客数加1/signal(customers);/必要的话唤醒理发师/
signal(mutex);/开放临界区/wait(barbers);
/无理发师,顾客坐着养神/get-haircut();/一个顾客坐下等理发/}elsesignal(mutex);/人满了,走吧!/}管程的基本形式TYPE<管程名>=MONITOR<管程变量说明>;define<（能被其他模块引用的）过程名列表>;use<（要引用的模块外定义的）过程名列表>；procedure<过程名>(<形式参数表>);begin<过程体>；end;……procedure<过程名>(<形式参数表>);begin<过程体>；end;begin<管程的局部数据初始化语句>；end;局部数据过程1过程k出口初始化代码入口管程等待调用的进程队列…voidget(item){if（count≤0）notempty.wait;item=buffer[out];out=(out+1)%n;count=count-1;if（notfull.queue）notfull.signal;}in=out=0;count=0;}写进程共享文件读进程司机P1售票员P2while(true)while(true){{启动车辆；关门；正常运行；售票；到站停车；开门；}}wait(mutex）临界区（CS)signal(mutex)t2=c+dSFt1=a+bt3=e/ft4=t1×t2t5=t4-t3分析：从图可以看出，进程pb、pc只有在进程pa执行完成以后才能执行，进程pb、pc可以并发执行。为确保这三个进程的执行顺序，设两个同步信号量SB、SC分别表示进程pb和pc能否开始执行，其初值均为０。voidpa(){……signal(SB);signal(SC);}main(){semaphoreSB=SC=0;cobeginpa();pb();pc();coend;}voidpb(){wait(SB);……}voidpc(){wait(SC);……}cpiop缓冲区buffer分析：cp、iop必须遵守以下同步规则：（1）当cp进程把计算结果送入缓冲区buffer时，iop进程才能从缓冲区buffer中取出结果去打印。（2）当iop进程把缓冲区buffer中的数据取出打印后，cp进程才能把下一个计算结果送入缓冲区buffer中。voidcp(){while(计算未完成){得到一个计算结果；wait(Sb);将计算结果送缓冲区buffer中；signal(Sa);}}main(){semaphoreSa=0;semaphoreSb=1;cobegincp();iop();coend;}voidiop(){while(打印工作未完成){wait(Sa);从缓冲区buffer中取出信息；signal(Sb);打印输出结果；}} |
|
