操作系统第3章2-进程的同步与互斥课件

两种制约关系直接相互制约关系（同步）

间接相互制约关系（互斥）产生的原因进程合作资源共享

7/26/20231进程的同步（1）直接相互制约关系（同步）指系统中一些进程需要相互合作，共同完成一项任务,这种协作进程之间相互等待对方消息或信号的协调关系称为进程同步.具体说，并发进程在一些关键点上可能需要互相等待与互通消息，进程间的相互联系是有意识的安排的。产生的原因进程合作7/26/20232进程的同步（2）一般同步问题有两类保证一组合作进程按逻辑需要的执行次序执行

【例】司机P1

售票员P2

REPEATREPEAT

启动关门

正常运行售票

到站停开门

UNTILFALSEUNTILFALSE保证共享缓冲区（共享数据）的合作进程的同步

【例】输入进程PI缓冲区缓冲区计算进程PC打印进程PP7/26/20233进程的互斥是解决进程间竞争关系(间接制约关系)的手段。间接相互制约关系（互斥）

是指若干个进程同时竞争一个需要互斥使用的资源时，任何时刻最多允许一个进程去使用，其他要使用该资源的进程必须等待，直到该资源被释放。进程间要通过某种中介发生联系，是无意识安排的。产生的原因资源共享互斥是一种特殊的同步逐次使用互斥资源，也是对进程使用资源次序上的一种协调。7/26/20234临界资源临界资源

系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量。硬件临界资源：打印机、磁带机软件临界资源：只能排它使用的变量、表格、队列7/26/20235临界资源实例二人合作存款

count=100;PAS1:N=count;S2:N=N+100;S3:count=N;PBS4:M=count;S5:M=M+200;S6:count=M;执行情况：（1）PA—>PB,PB—>PAcount=400√

（2）S1—>PB—>S2—>S3

count=200×（3）S4—>PA—>S5—>S6

count=300×因count是一个互斥性使用的变量，是一个临界资源7/26/20236临界区临界区（临界段）

在进程中访问临界资源的那段代码区。例子7/26/20237具有临界资源的进程结构

……/*进入区*/criticalsection;/*临界区*//*退出区*/remaindersection;/*剩余区*/

……entrysectionexitsection7/26/20238访问临界区应遵循的原则空闲让进当无进程在临界区时，任何有权使用临界区的进程可进入。忙则等待不允许两个以上的进程同时进入临界区。有限等待任何进入临界区的要求应在有限的时间内得到满足。让权等待不能进入临界区的进程应放弃占用CPU。7/26/20239临界区互斥解决方法硬件缺点：成本高软件用编程解决缺点：

(1)忙等待

(2)实现过于复杂，需要高的编程技巧信号量机制7/26/202310信号量机制一类资源抽象成S（信号量）信号量只能由P、V操作对其进行操作的变量。信号量的使用应注意必须置一次且只能置一次初值。初值只能为非负整数，实现互斥时初值为1。只能执行P、V操作。7/26/202311P、V操作

P(S)：表示申请一个资源。

V(S)：表示释放一个资源。

P、V操作必须成对出现，有一个P操作就一定有一个V操作。7/26/202312整型信号量整型信号量信号量S：整型量，除初始化外仅能通过P、V操作访问P和V操作原语定义：

varS:integer;S=1;

P(S)：whileS≤0dono-opS=S-1；

V(S)：S=S+1；一类资源抽象成S（信号量）整型量7/26/202313利用整型信号量实现进程互斥P(S)V(S)P1P2互斥区P(S)V(S)7/26/202314记录型信号量记录型信号量信号量S：记录型数据结构,一个分量为整型量value,另一个分量为信号量队列L；信号量的物理含义当S.value>0：表示可用资源个数当S.value＝0：表示可用资源正好用完当S.value<0：表示等待该类资源的进程数一类资源抽象成S（信号量）value0L=nil信号量的值(-2)信号量队列指针7/26/202315structsemaphore{

intvalue;

int*L;}voidP(structsemaphoreS);{S.value=S.value–1;/*把信号量减去1*/

ifS.value<0thenblock(S.L);/*若信号量小于0，则调用P(S)的进程被置成等待信号量S的状态*/}物理意义：申请一个资源，如果申请成功，则返回；如果申请不成功，则挂在该资源的等待队列上。voidV(structsemaphoreS);{S.value=S.value+1; /*把信号量加1*/ifS.value<=0thenwakeup(S.L);/*若信号量小于等于0，则释放一个等待信号量s的进程*/}物理意义：归还一个资源，如果没有进程等待该资源，则返回；如果有进程在等待，把等待的进程从L上移到就绪队列。记录型信号量描述7/26/202316利用记录型信号量实现进程互斥P(mutex)V(mutex)P1P2互斥区P(mutex)V(mutex)7/26/202317信号量及P、V操作讨论(1)

信号量的物理含义：

S.value>0:表示有S.value个资源可用

S.value=0:表示无资源可用

S.value<0:则|S.value|表示等待队列中的进程个数

信号量的初值应该大于等于07/26/202318P、V操作讨论(2)

P(S)：表示申请一个资源

V(S)：表示释放一个资源。

P、V操作必须成对出现，有一个P操作就一定有一个V操作P、V操作的优点

简单，而且表达能力强，可解决任何互斥问题P、V操作的缺点不够安全，P、V操作使用不当会出现死锁，遇到复杂互斥问题时，实现复杂。7/26/202319用P、V操作实现互斥信号量初值为1对于两个并发进程，互斥信号量的值仅取1、0和-1三个值：若mutex.value＝1表示没有进程进入临界区若mutex.value＝0表示有一个进程进入临界区若mutex.value

＝-1表示一个进程进入临界区，另一个进程等待进入。7/26/202320利用P、V操作实现两个进程互斥的模板如下：

structsemaphoremutex;

mutex.value=1;mutex.L=nil;{

cobegin

ProcessP1:BeginM

P(mutex);

临界区1

V(mutex);MEnd

ProcessP2:BeginM

P(mutex);

临界区2

V(mutex);MEnd

coend}

7/26/202321使用PV操作实现互斥应注意识别临界资源是否被共享;是否有排它性使用要求。临界区代码应尽量短小，不能有死循环。P和V原语应分别紧靠临界区的头尾。P、V操作在同一进程中必须成对出现。7/26/202322思考题

用记录型信号量解决二人存款问题，用类C语言编写进程互斥算法。7/26/202323用P、V操作实现进程的同步只要信号量初值是一个大于等于0的整数就能达到同步的目的，就可以直接使用P、V操作实现同步互斥是一种特殊的同步P、V操作既可以实现互斥，也可以实现同步7/26/202324利用信号量实现进程同步的实例设有三个并发执行的进程P1、P2、P3，其前趋图如下，试用信号量实现这三个进程同步。设两个同步信号量S1、S2分别表示进程P2、P3能否开始执行structsemaphoreS1,S2=0,0;/*初值均为0*/{

cobeginP1:{V(S1);V(S2);}P2:{P(S1);;}P3:{P(S2);;}

coend}

P1P3P27/26/202325使用PV操作实现同步应注意信号量的设置信号量的初值

PV操作要成对出现，并在不同的进程中7/26/202326信号量及P、V操作讨论(3)(1)P、V操作必须成对出现，有一个P操作就一定有一

个V操作(2)当为互斥操作时，它们同处于同一进程当为同步操作时，则不在同一进程中出现(3)如果P(S1)和P(S2)两个操作在一起，那么P操作的顺序至关重要。一个同步P操作与一个互斥P操作在一起时，同步

P操作在互斥P操作前，而两个V操作无关紧要。7/26/202327PV操作实现互斥与同步的模板进程互斥

S初值为1

P1

P2

P(S)P(S)

临界区1临界区2V(S)V(S)在P1与P2中设置相同的P、V操作进程同步

S1初值为n，S2初值为0

P1

P2

P(S1)

P(S2)

段1段2

V(S2)

V(S1)7/26/202328经典的进程同步问题生产者/消费者问题读者/写者问题哲学家进餐问题7/26/202329生产者/消费者问题生产者消费者问题是一种同步问题的抽象描述。计算机系统中的每个进程都可以消费（使用）或生产（释放）某类资源。这些资源可以是硬件资源，也可以是软件资源。当某一进程使用某一资源时，可以看作是消费，称该进程为消费者。而当某一进程释放某一资源时，它就相当于生产者。7/26/202330生产者/消费者问题(描述)

通过一个公用缓冲池可以把一群生产者p1,p2…,pm，和一群消费者Q1,Q2,…,Qn联系起来。如图:只要缓冲区未满，生产者就可以把产品送入缓冲区;只要缓冲区未空，消费者就可以从缓冲区中取走物品。7/26/202331生产者/消费者问题(图示)7/26/202332生产者/消费者问题(分析)为解决生产者消费者问题，应该设两个同步信号量，一个说明空缓冲区的数目，用empty表示，初值为缓冲池的大小N，另一个说明已用缓冲区的数目，用full表示，初值为０。由于在此问题中有i个生产者和j个消费者，它们在执行生产活动和消费活动中要对缓冲池进行操作。由于缓冲池是一个临界资源，必须互斥使用，所以，另外还需要设置一个互斥信号量mutex，其初值为１。struct

semaphoneempty=n,full=0,mutex=1;voidbuffer[n-1];

intin=,out=0;7/26/202333生产者/消费者问题(解决)Consumerj:while(1){

P(full);

P(mutex);

从Buffer[out]取产品;out=(out+1)modn;

V(mutex);

V(empty);

消费产品;}coend;cobegin

procedurei:while(1){

生产产品;

P(empty);

P(mutex);

往Buffer[in]放产品;in=(in+1)modn;

V(mutex);

V(full);

}7/26/202334生产者/消费者问题(思考)在生产者进程和消费者进程中，两个P操作的执行顺序是否能交换？两个V操作的执行顺序是否能交换？7/26/202335思考题

两个进程合作完成数据计算和打印工作，计算进程未计算完就不可打印，反之也然，双方共用一个缓冲区，写出此算法。7/26/202336读者/写者问题

有两组并发进程:读者和写者,共享一个数据文件

要求：允许多个读者同时执行读操作不允许读者、写者同时操作不允许多个写者同时操作7/26/202337读者/写者问题如果读者来：1）无读者、写者，新读者可以读2）有写者等，但有其它读者正在读，则新读者也可以读3）有写者写，新读者等如果写者来：1）无读者、写者，新写者可以写2）有读者，新写者等待3）有其它写者，新写者等待7/26/202338读者写者问题的解法为实现读者和写者、写者和写者之间的互斥，设置一个互斥信号量Wmutex=1由于“读—读”允许，再设置一个整型变量Readcount表示正在读的进程数，初值Readcount=0由于Readcount是一个可被多个读者进程访问的临界资源，所以要为它设置一个互斥信号量Rmutex=1读者—写者算法如下：读者：{

P(Rmutex);ifreadcount=0thenP(Wmutex);

Readcount=Readcount+1;

V(Rmutex);

读

P(Rmutex);

Readcount=Readcount-1;ifReadcount=0thenV(Wmutex);

V(Rmutex);}写者：

{

P(Wmutex);

写

V(Wmutex);}7/26/202339哲学家就餐问题有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子。每个哲学家的行为是思考，感到饥饿，取筷子，然后吃通心粉，放筷子，思考。为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子。筷子是临界资源，要用5个互斥信号量来表示这5只筷子。7/26/202340哲学家就餐问题解设fork[5]为5个信号量，初值均为1struct

semaphore

fork[4];fork[i]:=1;Philosopheri：While(1){

思考；

P(fork[i]);P(fork[(i+1)mod5])；

进食；

V(fork[