操作系统设计原理 课件第3章 互斥与同步

2025/11/61第3章互斥与同步第3章互斥与同步本章目标：掌握进程同步与互斥的基本原理及处理机制能够识别同步与互斥功能实现的关键环节和影响因素能够认识到同步与互斥功能实现有多种方案，能够通过文献研究，在多种方案中，寻求一种更合适的解决方案能够遵循系统化的基本要求，确定解决同步与互斥问题的设计目标和技术方案能够运用所学知识解决同步与互斥进程设计与实现问题，能在设计实现中体现创新意识能够对实验结果进行进行输入条件关联分析和解释，并能综合应用场景和技术需求，得出结论的有效性3.1进程互斥

并发进程之间的关系间接的相互制约关系─资源共享（竞争资源）直接的相互制约关系─公共变量（进程协作）3.1.1并发原理例1：生产者和消费者问题(Producer&Consumer)

生产者进程:{

while(count==BUFFER_SIZE);count++;buffer[in]=item;in=(in+1)%BUFFER_SIZE;}消费者进程：{while(count==0);count--;item=buffer[out];out=(out+1)%BUFFER_SIZE;}

生产者进程:数据→缓冲区(buffer)消费者进程:缓冲区(buffer)→数据BUFFER_SIZE=K，count：buffer中数据个数，是共享变量inout结果不唯一Producer进程：

count++Consumer进程：

count--T0:register1=count;T1:register1=register1+1;T4(5):count=register1;T2:register2=count;T3:register2=register2-1;T5(4):count=register2;(count=5(7))例2假设有两个并发进程borrow和return分别负责申请与归还主存资源，程序片段如下。

X：现有的空闲主存量；B：申请或归还的主存量。processborrow(…,B,…)intB;{if(B>X){等待主存资源；}X=X-B;

修改主存分配表；

}processreturn(…,B,…)intB;{X=X+B;

释放等待主存资源者；修改主存分配表；

}永远等待processborrow(…,B,…)intB;{if(B>X)

调度returnprocessreturn(…,B,…)intB;{X=X+B;

释放等待主存资源者；修改主存分配表；

}

{等待主存资源；}X=X-B;

修改主存分配表；

}

临界区

错误原因：两个进程交叉访问共享变量count或X并发进程中与共享变量有关的程序段称为“临界区”（Criticalsection)

一次只允许一个进程使用的资源称临界资源临界资源的访问过程：进入区临界区退出区剩余区进程中访问临界资源的那段代码称临界区

3.1.2临界资源与临界区“生产者和消费者”问题

生产者进程的临界区:count++;buffer[in]=item;in=(in+1)%BUFFER_SIZE;消费者进程的临界区:count--;item=buffer[out];out=(out+1)%BUFFER_SIZE;一个进程在临界区中执行时，不让另一个进程进入相关的临界区执行，就不会造成与时间有关的错误。

不允许两个以上共享共有资源或变量的进程同时进入临界区执行的性质称为互斥(mutualexclusion)。即临界区的执行必须具有排它性。互斥(MutualExclusion)临界区的管理应有三个要求：(1)互斥性：如果一个进程在它临界区中执行，其它任何进程均不能进入相关的临界区执行；(2)进展性：如果一个进程不在它临界区中执行，不应阻止其它任何进程进入相关的临界区执行；(3)有限等待性：某个进程从申请进入临界区时开始，应在有限的时间内得以进入临界区执行。3.1.3互斥的软、硬件实现方法1.标志法 如P1和P2两个进程，它们的程序代码均包含有相关的临界区。我们对P1和P2分别用两个变量inside1和inside2来标志它们是否在临界区中，当进程在它的临界区内时其值为1，不在临界区时其值为0。intinside1,inside2;/*两并发进程共享变量*/

inside1=0;/*表示P1不在临界区内*/

inside2=0;/*表示P2不在临界区内*/

processP1

{……

while(inside2);/*等待inside2变成0*/

inside1=1;

临界区;

inside1=0;

……

}

processP2

{……

while(inside1);/*等待inside1变成0*/

inside2=1;

临界区;

inside2=0;

……}

可能出现两个并发进程同时进入了各自的临界区的情况2.严格轮换法用一个指针turn来指示应该由哪个进程进入临界区。若turn=0则表示P0可进入临界区；若turn=1则表示P1可进入临界区。intturn;

turn=0;

processP0

{……

while(turn==1);/*等待turn变成0*/

临界区;

turn=1;

……

}

processP1

{……

while(turn==0);/*等待turn变成1*/

临界区;

turn=0;

……

}问题：

1）严格强制了两个进程轮换地进入临界区

2）违反要求（2）3）忙等待3.Peterson算法为每一个进程设置一个标志flag，当标志为1时表示该进程请求进入临界区。设置一个指针turn以指示可以由哪个进程进入临界区，当turn等于i时则可由进程Pi进入临界区。提供两个函数来管理临界区，分别为enter_region,leave_region。intturn;

intflag[2]={0，0};

voidenter_region(intprocess)

{

intother;

other=1-process;

flag[process]=1;

turn=other;

while(turn==other&&flag[other]==1);

}

voidleave_region(intprocess)

{

flag[process]=0;

}

Peterson算法好处：能正确解决互斥问题.缺点：进程会出现“忙等待”.6．2．2．2互斥的硬件实现方法1.中断屏蔽方法……

屏蔽中断(disableinterrupts)；临界区；开中断(enableinterrupts)；……2.硬件指令方法……while(TS(&lock));临界区代码；lock=0;……

用Swap指令来管理临界区时，则进程程序结构为：……key=1;doSwap(&lock,&key)while(key);临界区代码；lock=0;……测试并设置指令：对一个字进行检测和修正交换指令：实现两个字的内容交换intTS(int*flag){intold_flag;old_flag=*flag;*flag=1;return(old_flag);}voidSwap(int*x,int*y){inttemp;temp=*x;*x=*y;*y=temp;}缺点：忙等待3.1.4信号量和P、V操作思想：在多个相互合作的进程之间使用简单的信号来协调控制。一个进程检测到某个信号后，就被强迫停止在一个特定的地方，直到它收到一个专门的信号为止才能继续执行。这个信号就称为“信号量”，类似于十字路口的交通控制信号灯。

信号量定义:含有整型数据项的结构变量，其整型值大于等于零代表可供并发进程使用的资源实体数，小于零时则表示正在等待使用临界区的进程数。typedefstruct{intvalue;PCB*pointer;}semaphore;

P操作P(s)：将信号量s的整型值减去1，若结果大于等于0，则调用进程继续运行；若结果小于0，则将调用P(s)的进程置成等待信号量s的状态，直到其他进程在s上执行V操作将其释放为止。V操作V(s)：将信号量s的整型值加上1，若结果大于0，则调用进程继续运行；若结果不大于0，则释放一个等待信号量s的进程，然后调用进程继续运行。ProcedureP(vars:semaphore) begin s.value:=s.value-1; ifs.value<0thenW(s); end;ProcedureV(vars:semaphore) begin s.value:=s.value+1; ifs.value<=0thenR(s); end;P操作V操作s=s-1s<0Y调用进程被阻塞继续Ns=s+1s<=0Y唤醒一个阻塞进程继续N信号量S的物理含义信号量S>0时，表示某类公用资源的可用数;S<=0时，表示已经没有此类资源可供分配了，S的整型值的绝对值等于在该信号量上等待的进程数。P(S)请求分配一个单位的资源给调用P操作的进程信号量S的值应减去1当S的值小于等于0时，表示已经没有此类资源可供分配了，因此，请求资源的进程将被阻塞在S上。V(S)释放出一个单位的该类可用资源信号量S的值应增加1若S的值还小于等于0，表示S的阻塞队列中还有被阻塞的进程，因此，就唤醒一个阻塞进程，将其转移到就绪队列中去。P、V操作的物理含义

例：有两个并发进程insert_item和delet_item分别负责对一个队列进行插入数据项和删除数据项的操作，插入数据项和删除数据项均需要对队列中的指针进行修改。因此，它们对队列中指针的操作是一种互斥关系。

semaphoremutex;

mutex.value=1;

Processdelet_item{……P(&mutex);

从数据队列中摘除数据项data；

V(&mutex);

释放数据项data的缓冲区；

……}processinsert_item{……

向系统申请一个缓冲区；将数据data送入该缓冲区中；

P(&mutex);

把该缓冲区挂入数据队列中；

V(&mutex);……}N个进程实现互斥的一般形式

semaphoremutex;mutex.value=1;……processPi{……P(mutex);

进程Pi的临界区代码；

V(mutex);……}2025/11/6273.2进程同步

3.2.1进程同步概念进程同步的引入“生产者-消费者”问题中有两种情况会导致不正确的结果：消费者从一个空的缓冲区buffer中取数据。就意味着重复取已经取走的数据或取缓冲区中并不是生产者放入的数据。生产者把数据存入已满的缓冲区，这就意味着将覆盖尚未消费（取走）的数据。出现的两种不正确的结果是因为它们访问缓冲区的速率不匹配。正确地控制生产者和消费者的执行，必须使它们在执行速率上做到相匹配，即在执行中它们是应相互制约的。2.进程同步定义异步环境下的一组并发进程，因直接制约互相发送消息而进行相互协作、相互等待，使得各进程按一定的速度执行的过程称为进程间的同步。实现进程同步的机制称同步机制。3.2.2用P、V操作实现进程间的同步例1生产者每次生产一件物品（数据）存入缓冲区，消费者每次从缓冲区取一件物品消费。假定缓冲区只能存放一件物品。生产者进程和消费者进程的程序描述如下：

semaphores1,s2;intB;s1.value=1;s2.value=0;

processproducer{intdata;

生产一件物品并暂存在data中；

P(s1);B=data;V(s2);}processconsumer{intdata;P(s2);data=B;V(s1);

消费data；

}例2用P，V操作实现：semaphoresa,sb,sc,sd,se;sa.value=sb.value=sc.value=sd.value=se.value=0;cobegin Pa(); Pb(); …… Pf();coend;

A

BCD

EFProcessPa{……V(sa);V(sa);V(sa);}ProcessPb{P(sa);……V(sb);}ProcessPc{P(sa);……V(sc);}ProcessPd{P(sa);……V(sd);}ProcessPe{P(sb);P(sc); ……V(se);}ProcessPf{ P(se); P(sd); ……}intbuffer[k];semaphores1,s2,s;intin,out;s.value=1;s1.value=k;s2.value=0;in=0;out=0;Cobeginrepeatproduceri;repeatconsumerj;Coend;

例3现有m个生产者和n个消费者，它们共享可存放k件物品的缓冲区。必须使用公用信号量s，以限制它们对缓冲区的互斥存取，另用两个私有信号量s1和s2，以控制生产者不往满的缓冲区中存物品，消费者不从空的缓冲区中取物品。各进程的程序描述如下：

processproduceri{intitem;P(s1);P(s);buffer[in]=item;in=(in+1)%k;V(s2);V(s);}processconsumerj{intitem;P(s2);P(s);item=buff[out];out=(out+1)%k;V(s1);V(s);

消费item；

}P(s);P(s1);?在用P、V操作实现同步与互斥共存的问题时，一般来说，私有信号量的P操作应在前执行，而用于互斥的公用信号量P操作应在后执行。而V操作的次序无关紧要。例4有三个并发进程,R负责从输入设备读入信息并传送给M,M将信息加工（空格转为分号）并传送给P,P把加工后的信息打印输出。现有一个缓冲区，容量为K。

用PV操作写出这三个进程正确工作的程序。semaphoresr,sm,sp;intlr,lm,lp;DatatypeB[K];lr=lm=lp=0;sr.value=K;sm.value=0;sp.value=0;cobegin repeatR;repeatM; repeatP;coendProcessR{readdata;P(sr);B[lr]=data;lr=(lr+1)%K;V(sm);}ProcessM{P(sm);if(B[lm]==‘’)B[lm]=‘;’；

lm=(lm+1)%K;V(sp);}ProcessP{P(sp);data=B[lp];lp=(lp+1)%K;V(sr);printdata;}例5若零件A的最大库容量为m,零件B的最大库容量为n,当A和B的产量差超过k时，暂停对数量大的零件的生产而补充生产数量少的零件。用p,v操作实现。SemaphoreemptyA,emptyB,fullA,fullB,Sa,Sb;emptyA.value=m;emptyB.value=n;fullA.value=0;fullB.value=0;Sa.value=k;Sb.value=k;cobeginrepeatPA;repeatPB;repeatCA;repeatCB;coendProcessPA{P(&emptyA);

生产一件A入库；

V(&fullA);

}ProcessPB{P(&emptyB);

生产一件B入库;V(&fullB);}ProcessCA{P(&fullA);

取A消费；

V(&emptyA);}ProcessCB{P(&fullB);

取B消费；

V(&emptyB);}V(&Sb);

P(&Sa);

V(&Sa);

P(&Sb);例6读者与写者问题。一个数据集为多个并发进程所共享，其中一些进程只要求读该数据集的内容，这些进程称为“读者”，而另一些进程则要求修改该数据集的内容，这些进程称为“写者”。

具体要求是：允许多个读者同时读该数据集的内容，若有一个写者在写，则其他读者不能读，若一个写者在写或有其他读者在读，则其他写者均被拒绝。

intreadcount;semaphoreR,W;readcount=0;R.value=1;W.value=1;cobegin repeatreader; repeatwriter;coend;ProcessreaderbeginP(&R);readcount++;if(readcount==0)P(&W);V(&R);

读数据集；

P(&R);readcount--;if(readcount==0)V(&W);V(&R);end;Procedurewriterbegin------P(&W);

写数据集；

V(&W);------end例7读者与写者问题。具体要求是：允许多个读者同时读该数据集的内容；若有一个写者在写，则其他读者不能读；若一个写者在写或有其他读者在读，则其他写者均被拒绝；当一个写者正在写，而有多个读者与写者在等待时，写者应优先唤醒。

intreadcount,readapp,writecount;semaphoremutex,sw,sr;readcount=0;writecount=0;readapp=0;mutex.value=1;sr.value=0;sw.value=0;cobegin repeatreaderi; repeatwriterj;coend;processreaderi

{P(&mutex);if(writecount>0){readapp++;V(&mutex);P(&sr);P(&mutex);readapp--;readcount++;if(readapp>0)V(&sr);V(&mutex);}else{readcount++;V(&mutex);}

读数据集；

P(&mutex);readcount--;if(readcount==0&&writecount>0)V(&sw);V(&mutex);}processwriterj{P(&mutex);writecount++;if(readcount>0||writecount>1){V(&mutex);P(&sw);}elseV(&mutex);

写数据集；

P(&mutex);writecount--;if(writecount>0)V(&sw);elseif(readapp>0)V(&sr);V(&mutex);}例8桌上有一只盘子，每次只能放入一只水果。爸爸专放苹果，妈妈专放橘子，一个儿子专等吃盘子中的橘子，一个女儿专等吃盘子中的苹果。分别用P，V操作和管程实现。(1)用p,v操作实现：(Pascal形式表示）empty,full1,full2:semaphore;empty:=1;full1:=0;full2;=0;Cobeginrepeatfarther;repeatmother;repeatson;repeatdaughter;Coend;Procedurefather;begin P(empty); 放苹果入盘； V(full1);end;proceduremother;begin P(empty); 放橘子入盘； V(full2);end;Procedureson;begin P(full2); 从盘中取橘子； V(empty);

吃橘子；

end;proceduredaughterbegin P(full1); 从盘中取苹果； V(empty);

吃苹果；

end;3.2.3经典问题哲学家进餐问题打瞌睡的理发师3.3进程通信3.3.1进程通信的类型进程通信：一个进程将一批信息发送给另一进程的过程。即进程间用信件来交换信息。一个正在执行的进程可以在任何时刻向另一个正在执行的进程发送一封信件；一个正在执行的进程也可以在任何时刻向另一个正在执行的进程请求一封信件。如果一个进程在某一时刻的执行依赖于另一进程的信件或接收进程对信件的回答，那么通信机制将与进程的阻塞和释放相联系。这样的进程间的通信就进一步扩充了并发进程间对数据的共享。进程通信分类共享存储器系统相互通信的进程共享某些数据结构或存储区域，进程之间通过共享的存储区域进行通信。通信过程：先向系统申请共享存储区域，并指定该共享区域的名称，若系统已分配该共享区域，则将该共享区域的句柄返回给申请者。申请进程把获得的共享区域连接在本进程上，便可以像读写普通区域一样对该共享存储区域进行读写操作，可达到传递大量信息的目的。

消息传递系统进程间的数据交换以消息为单位。用户通过使用操作系统提供的一组消息通信原语来实现信息的传递。消息传递系统是一种高级通信方式，按实现方式不同可以分为直接通信方式和间接通信方式。管道通信管道：是指用于连接一个读进程和一个写进程，以实现进程之间通信的一种共享文件，又称为Pipe文件。发送进程（写进程）向管道输入数据，接收进程（读进程）从管道接收数据，形成通信。管道机制必须协调：1）互斥：读、写互斥；2）同步：管道满是写进程等待，管道无数据读进程等待；3）确认对方存，才能通信。消息传递所谓直接通信是指发送进程把信件直接发送给接收进程。在这种通信方式下，发送进程必须指出信件发给哪个进程，接收进程也指出从哪个进程接收信件。为指名对称通信方式。使用两个不可分操作send原语和receive原语实现。原语：send(P，信件)：表示把一封信件发送给进程P；receive(Q，信件)：表示从进程Q处接收一封信件。1、直接通信非对称指名通信方式：

数据结构信件：包括信息：接收进程Id，发送进程Id，信件长度和正文。信件缓冲区：包括：发送进程Id，信件长度，正文和形成信件缓冲队列的链指针的数据项。信件缓冲队列：为信件缓冲区的链表结构，其头指针保存在接收进程的进程控制块PCB中。队列可按先进先出或优先级的原则来组织。信号量sm：为信件缓冲队列的信号量，初值为0。信号量mutex：为信件缓冲队列操作互斥信号量，初值为1。

通信原语算法：send(接收进程Id，信件){向系统申请一个信件缓冲区；将信件存入该信件缓冲区；据接收进程Id找到其PCB；

P(&mutex);

把信件缓冲区链接到接收进程PCB的信件缓冲队列的尾部；

V(&mutex)；

V(&sm);}receive(信件){P(&sm);P(&mutex);从信件缓冲队列中摘取第一个缓冲区；V(&mutex)；将该缓冲区中的信息考到信件的存储区域中；释放该缓冲区；}间接通信间接通信是指发送信件进程把信件发送到一个共享的数据结构—信箱(mailbox)中，接收进程也到信箱去取信件。即进程间发送或接收信件均通过信箱来进行。信箱：存放多封信件的存储区域，有信箱特征和信箱体两部分。

1）信箱特征描述信箱容量、指针和信件格式等；信箱体是存放信件的区域；

2）信箱体分成若干个区，每个区存放一封信。发送和接收原语：send(B，信件)：把一封信件传送到信箱B中。receive(B，信件)：从信箱B中接收一封信件。多个进程发信和收信操作，类似于生产者与消费者问题，也必须考虑同步与互斥问题。对send和receive原语的设计可采用P、V操作或管程的方法。

直接通信与间接通信的区别：

1）进程间的密切关系不同：直接通信常用于进程间关系比较密切的情形，而间接通信则用于联系不十分紧密的进程之间通信。

2）间接通信具有较大的灵活性：发送进程和接收进程之间的关系可以有一对一、一对多、多对一和多对多的多种关系；进程与信箱的关系可以是静态的，也可以是动态的(提供connect，disconnect原语)。3.3.2进程通信的有关问题缓冲问题1）缓冲区容量为0：发送者必须等待接收者2）缓冲区容量有界：有时需等待3）缓冲区容量无界：无法真正实现并行性问题1）双向通信：发信后等待回答消息，接收者等收到信后再回信。2）发信后立即往下执行，直到需要回答消息时，才等待回答消息。并行性高，但需要增加两条原语：

answer(P,result)：向进程P发送回答消息result。

Wait(Q,result)：等待接收进程Q的回答消息result。

3.4死锁交通阻塞的原因：所有车辆竞争使用资源（道路）。类似的，一个多道程序系统中，可能存在多个并发进程或线程，它们共享该计算机系统的所有资源。因为资源（CPU、内存、磁盘、数据、表格、信号量等）竞争而造成系统无法继续推进就不可避免。死锁资源3.4.1死锁的概念死锁是指一组并发进程彼此相互等待对方所占有的资源，而且这些进程在得到对方的资源之前不会释放自己所占有的资源，从而造成这组进程都不能继续向前推进的状况。关键：申请新资源；不释放原有资源。进程使用资源的一般步骤：请求资源使用资源释放资源

-----未批准，进程阻塞等待。等待时原有的资源并不释放例如，有n个进程，P1,P2,……Pnn个资源R1,R2,……RnR1P1R2RnP2Pn……资源已经被进程获得进程在等待该资源P1,P2,……Pn处于死锁状态死锁例子：例1：3.2.1节例2中的生产者与消费者问题。如果我们把互斥信号量(s)的P(&s)操作放在同步信号量(s1)的P(&s1)操作前面，就出现死锁。processproduceri{intitem;

生产一件物品并暂存在item中；

P(&s1);P(&s);buffer[in]=item;in=(in+1)%k;V(&s2);V(&s);}processconsumerj{intitem;P(&s2);P(&s);item=buff[out];out=(out+1)%k;V(&s1);V(&s);

消费item；

}P(&s);P(&s1);?例2：对临时性资源（如信件）的使用不加限制也会出现死锁现象。综上所述，死锁是由于资源的使用不加合理的控制而引起的。因此，必须从资源的性质、资源分配的方法来考虑解决死锁问题。3.4.2死锁的必要条件(1)互斥条件(mutualexclusion)：一个资源一次只能由一个进程使用，如果有其它进程申请使用该资源，申请进程必须等待直到所申请的资源被释放。(2)部分分配条件(holdandwait)：一个进程已占有一定资源后，执行期间又再申请其它资源。(3)不可抢占条件(nopreemption)：一个资源仅由一个占有它的进程来释放，不能被其它进程抢占使用。(4)循环等待条件(circularwait)：在系统中存在一个由若干进程申请使用资源而形成的循环等待链，其中每一个进程占有若干资源，同时又在等待下一个进程所占有的资源。要防止死锁就要破坏其中之一的必要条件。可能性：1。破坏条件（1），即破坏互斥条件，允许多个进程同时访问资源。由于资源本身的使用性质的限制，不可行。2。破坏条件（3），即破坏不可抢占条件。只能适用于CPU和主存这类资源的管理。3。破坏条件（2），即破坏部分分配条件，一次性为进程分配所有应使用的资源。可行。4。破坏条件（4），即破坏循环等待条件，使运行期间不存在进程循环等待现象。可行。解决死锁的办法：（1）死锁的预防，消除可能产生死锁的原因。（2）死锁的避免。（3）死锁的检测和修复。3.4.3死锁的防止主要方法有：资源静态分配法和资源的层次分配法。1.资源静态分配法破坏部分分配条件。一个进程必须在执行前就申请它所需的全部资源，并且直到它所需的资源得到满足后才能开始执行。这种策略实现简单，但资源利用率低。2.资源的层次分配法

思想：1）把资源分成多个层次；2）一个进程得到某一层的一个资源后，它只能再申请较高一层的资源；3）当一个进程要释放某层的一个资源时，必须先释放所占有的较高层的资源；4）当一个进程获得了某一层的一个资源后，它想再申请该层中的另一个资源，则必须先释放该层中的已占有的资源。简化：资源的按序分配法优点：资源的利用率有较大的提高缺点：要特别小心地安排资源所处的层次。（1）各类设备的资源层次一经排定，不可经常随意改动。若系统要添加一些新设备，就必须重新改写已经存在的程序和系统。（2）资源层次的安排要大体反映大多数进程使用资源的顺序。对资源使用与此层次相匹配的进程，资源能得到有效的利用，否则，资源的浪费现象将仍然存在。

3.4.4死锁的避免死锁避免方法的基本思想：在为申请者分配资源前先测试系统的资源状况，若把资源分配给申请者会产生死锁的话，则拒绝分配，否则接受申请并为它分配资源。著名的避免死锁的方法是银行家算法。银行家算法的基本思想：检查申请者对各类资源的最大需求量，如果系统现存的各类资源可以满足它的最大需求量时，就满足当前的申请。换句话说，仅仅在申请者获得资源最终能运行完毕，无条件地归还它所申请的全部资源时，才分配资源给它。例1，假设系统现有三个进程P,Q,R，系统只有一类资源共10个，每个进程使用该资源的总数都小于10，目前分配情况如下表所示：

进程已占有资源还需申请数P44Q22R27例2.某系统有R1,R2,R3共3种资源在T0时刻P1,P2,P3和P4这4个进程对资源的占用和需求如下，系统的可用资源向量为（2，1，2）问：（1）将系统中各种资源的总和和此刻各进程对资源的需求数目用向量或矩阵表示出来。（2）如果此时P1和P2均发出资源请求向量（1，0，1），为了保持系统安全性，应如何分配资源给这两个进程。3.4.5死锁检测与恢复基本思想： 对资源的分配不加限制，但系统必须定时或不定时地运行一个“死锁检测”程序，判断系统内是否出现死锁，若检测到死锁则采取相应的办法解除死锁，并以尽可能小的代价恢复相应的进程运行。资源分配图和相应的等待图

死锁检测算法可基于等待图来检测:只要检测出等待图中存在一个环时，就意味着检测到了一个进程循环等待链，因此检测到系统中存在死锁。

例：资源分配表为：资源号占用资源的进程号１１２３３２４２５１进程等待表为：进程号所等待的资源号１３２２３５请画出等待图判断有无环路，是否会产生死锁。R3R1R4R5R2P1P3P2P1P2P3资源分配图进程等待图故有环路。产生死锁。解：解除死锁的方法有两种：（1）撤消进程法；

（2）剥夺资源法。(1)撤消进程法：可有两种形式：1）撤消所有卷入死锁的进程。2）一次撤消一个进程直到死锁消失。通常应基于成本来选择撤消进程，选择的原则是：（1）选择使用处理器时间最少的进程；（2）选择输出工作量最少的进程；（3）选择具有最多剩余时间的进程；（4）选择分得资源最少的进程；（5）选择具有最小优先级的进程。(2)剥夺资源法：思想：是从一个或多个卷入死锁的进程中强占资源，再把这些资源分配给卷入死锁的其它进程，以解除死锁。恢复进程执行1）资源被剥夺的进程为了再次得到该资源，必须重新提出资源申请，返回到分配资源前的某一点处重新执行。2）设立检查点(checkpoint)是一种恢复进程重新运行的有效方法。可在资源申请处设检查点，恢复时从最近的检查点处执行。3.5多核环境下的进程同步硬件原子操作加载存入指令测试与设置指令总线锁交换指令3.5多核环境下的进程同步多核环境下的软件同步原语1.Linux内核提供的原子操作包括如下几种：

·

总线锁：置换，比较与置换，原子递增操作。

·

原子算术操作：原子读、设置、加、减、递增、递减、递减与测试。

·

原子位操作：位设置、位清除、位测试与设置、位测试与清除、位测试与改变。2.Windows内核提供的原子操作包括如下几种：

·

互锁操作(InterlockedOperation)；

·

执行体互锁操作(ExecutiveInterlockedOperation)。3.5多核环境下的进程同步旋锁旋锁(spinlock)是几乎所有多核操作系统均会提供的一种CPU互斥机制，旋锁通常用于保护某个全局的数据结构。这里的互斥指的是多个处理器或执行核之间的互斥，即两个处理器或核不能(物理上)同时访问同一个数据结构；而不是多线程之间的互斥。3.5多核环境下的进程同步使用旋锁的过程如下：

1)等待旋锁变为闲置

2)获得旋锁

3)访问寄存器和全局数据结构

4)释放旋锁3.5多核环境下的进程同步旋锁的实现：使用测试与设置原子操作如果一个处理器要使用旋锁，就必须检查旋锁的特定内存单元的值。如果为0，则将其设置为1，可获得该旋锁。如果为1，则表示该旋锁被其他处理器所占有，则在该旋锁上进行繁忙等待，即不停地循环。3.5多核环境下的进程同步队列旋锁基本思想：需要旋锁的CPU不要到全局内存去SPIN，而是到自己的局部内存去SPIN。这样就可以排除对总线的竞争。实现：在旋锁上设置一个队列，表示哪些CPU要使用这个旋锁，旋锁释放时就检查这个队列，交给队列里的第一个CPU。

3.6进程同步与通信实例UNIXSystemV中的进程通信分为三个部分：低级通信、管道通信和进程间通信IPC(InterProcessCommunication)低级通信：主要用来传递进程间的控制信号主要系统调用和实用程序：1）sleep(),wait():使当前进程以指定的优先数在指定的队列上睡眠；wait()用于父子进程间的同步。

wakeup():唤醒在指定队列上睡眠的所有进程。2）传递和接收软中断信号的系统调用

-kill(pig,sig):向标识为pid的进程发软中断信号sig-signal(sig,func)捕捉到sig信号后，执行动作func3）用于互斥的实用程序lockf(fd,function,size)3.6进程同步与通信实例实现方法：1）利用睡眠原语sleep和唤醒原语wakeup实现进程间的同步与互斥。－sleep:使当前进程以指定的优先数在指定的队列上睡眠－wakeup:唤醒在指定队列上睡眠的所有进程3.6进程同步与通信实例2)利用软中断信号实现同一用户的诸进程之间的通信某进程向接收进程的proc结构中的相应项发送一个信号接收进程收到软中断信号后，执行软中断信号处理程序。

注意：软中断处理程序不像硬中断处理程序那样，收到中断信号后立即被启动，它必须等到接收进程执行时才能生效。

3.6进程同步与通信实例管道通信：最早的进程间通信机制之一特点：（1）管道是半双工的，数据只能向一个方向流动；（2）单独构成一种独立的文件系统；（3）数据的读出和写入由管道的两端进行，一个进程向管道的一端写入的内容被管道另一端的进程读出。3.6进程同步与通信实例进程间通信IPC：完成进程之间的大信息量的数据传输工作它由三部分构成：（1）消息(message)：用于进程之间分类的格式化数据；（2）共享存储区(sharedmemory)：可使得不同进程通过共享彼此的虚拟空间对共享区操作和传输数据；（3）信号量(semaphore)机制：用于进程之间的同步控制。信号量总是和共享存储区方式一起使用。3.6进程同步与通信实例（1）消息机制（类似与间接通信）提供msgget,msgctl,msgsnd,msgrev等四个系统调用，在使用各种通信机制的系统调用之前，必须include三个头文件(<sys/types.h>,<sys.ipc.h>和<sys/msg.h>)。系统调用msgget(key,msgflg)返回一个消息描述字msgqid，msgqid指定一个消息队列以便其它三个系统调用使用。系统调用msgctl(msgqid,cmd,buf)用来设置和返回与msgqid相关联的参数选择项，以及用来删除消息描述字的选择项。3.6进程同步与通信实例系统调用msgsnd(msgqid,msgp,msgsz,msgflg)用于发送一消息。系统调用msgrev(msgqid,msgp,msgsz,msgtyp,msgflg)用于接收一消息。

Example:Server,clientsendandreceivemessages#include<sys/types.h>#include<sys/ipc.h>#include<sys/msg.h>#defineMSGKEY75structmsgform{longmtype;charmtext[256];};main()/*client*/{structmsgformmsg;intmsgqid,pid,*pint;msgqid=msgget(MSGKEY,0777);pid=getpid();pint=(int*)msg.mtext;*pint=pid;msg.mtype=1;msgsnd(msgqid,&msg,sizeof(int),0);msgrcv(msgqid,&msg,256,pid,0);printf(“client:receivefrompid%d\n”,*pint);}#include<sys/types.h>#include<sys/ipc.h>#include<sys/msg.h>#defineMSGKEY75structmsgform{longmtype;charmtext[256];}msg;intmsgqid;main()/*server*/{inti,pid,*pint;externcleanup();for(i=0;i<20;i++)signal(i,cleanup);msgqid=msgget(MSGKEY,0777|IPC_CREAT);for(;;