【文档说明】《操作系统原理》第三章进程间的并发控制和死锁课件.ppt，共(73)页，418.559 KB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-54864.html

以下为本文档部分文字说明：

第三章进程之间的并发控制和死锁进程通信进程的状态是基于一定的原因和条件而变化的，而这些原因和条件又常常是由于进程之间的相互制约关系引起的。系统中诸进程之所以有这种关系，是由两方面原因引起的：1）各并发进程对资源的共享2）系统中存在若干协作进程

1、各并发进程对资源的共享互斥关系：通过共享资源而使进程之间产生的关系叫间接制约关系，又叫互斥关系。可用“进程—资源—进程”来描述。例：进程P1和P2在运行中都要使用打印机，为了使各进程输出的完整性，打印机的使用

必须独占。一旦系统将打印机分配给进程P1，那么进程P2必须等待，等待P1使用完打印机并释放后，才能使用。2、系统中存在若干协作进程同步关系：通常，一个用户作业涉及一组并发进程（输入、计算和输出进程），这些进程须相互协作完成这项任务。在运行过程中，这些进程可能

要在某些同步点上等待协作者发来信息后才能继续运行。进程之间的这种制约关系叫直接制约关系。又叫同步关系。可用“进程—进程”来描述进程通信：是指进程的上述相互依赖关系。进程之间的这种相互依赖又相互制约、

相互合作又相互竞争的关系，也即进程的同步与互斥关系。互斥是同步的一个特例。进程之间的这种关系就叫进程的低级通信。一、进程之间的互斥（进程的互斥是由于共享资源而引起的）共享资源：慢速的硬件设备，如打印机、磁带机等资源

软件资源，如共享变量、共享文件等临界资源（criticalresource）：就是一次仅允许一个进程使用的资源。如：打印机临界区（criticalsection）：就是并发执行的进程访问临界资源的那个必须互斥执行的程序段程序1Y=Y+1ou

tput程序2Y=Y+2output内存共享区Ypcb1pcb2临界资源和临界区为了正确而有效地使用临界资源，系统中的并发进程需要遵循如下四个准则：空闲让进－无进程在临界区就允许进入忙则等待－有进程在临界区，则等待有限等待－多进程要求进入临

界区是，应该让某一个进入，而不能无限等待都不让进让权等待－等待的进程必须释放CPU四个准则1、关中断二、解决进程之间互斥的方法进程AClose_INT;Critical_region();Open_INT;进程BClose_INT;Cr

itical_region();Open_INT;解决思想在临界区中防止发生进程调度保证临界区操作的完整性方法分析用户控制系统中断是非常危险的本方法对多个CPU系统将失去作用2、lock,unlock在原语里设置一个公共变量代表临界资源的状态。x=使用临界资源必须做如下三步：1、

检查锁的设置2、进入临界区，访问临界区3、释放临界资源，开锁资源可用资源正在使用011,0,1x关锁：资源可用继续测试资源正在使用二、解决进程之间互斥的方法锁机制框图测试x=0?Lock[x],x=1进入临界区退出临界区Unlo

ck[x],x=0返回继续测试x=1x=0返回显然，采用加锁机制，由于进程循环测试，白白浪费了CPU的时间，降低了系统的速度三、进程之间的同步同步原因：一组进程要合作完成一项任务。例：两个用户进程通过共享缓冲区完成其计算和打印任务

。计算进程负责将计算结果送入共享缓冲区，打印进程从缓冲区取数据打印。当缓冲区空时，不允许取数据，满时不允许送数据。否则，将出现错误。计算进程与打印进程这种制约关系，不是由于两个进程同时访问共享缓冲区，而是由于它们访问缓冲区时的速

度不匹配造成的。为了使进程同步，需要引入信号量机制。四、信号量1965年，荷兰学者Dijkstra提出的。基本原理：两个或多个进程可以通过简单的信号进行合作，一个进程可以被迫在某一位置停止，直到它接收到一个特定的信号。任何复杂的合作需求通过适当的信号结构得到满足。为此，需要使用

一个称作为信号量的特殊变量，以便通过信号量传送信号。信号量是一个数据结构定义如下：structsemaphore{intvalue;Pointer_PCBqueue;}整型变量，其值大小表示该资源的可

用数量是等待使用该资源的进程排成队列的队列头指针对信号量S的操作只允许执行P、V操作。其中P/V操作由原语组成，执行过程中不可分割。P操作原语P(S)1）S:=S–1//请求一个资源2）IfS>=0,goon;ifS<0,blocked//申请不成功

（资源用完），调用阻塞原语“让权等待”V操作原语V(S)1）S:=S+1//释放一个资源2）IfS>0,goon;ifS<=0,thefirstblockedprocessinwaitingqueueblocked->ready,goon//表示在信号链表，

仍有等待该资源的进程，调用唤醒原语。显然，P、V操作的引入，克服了加锁操作的忙等待现象，有效提高了系统的效率操作系统正是利用信号量的状态对进程和资源进行管理和控制的。从物理意义上理解，P操作相当于申请资源；V操作相当于释放资源。1、利用信号量实现进程之间的互斥引入一个互斥信号量，用m

utex表示。对于互斥使用的资源，其信号量的初值为1欲进入临界区执行的进程须先对互斥信号量mutex执行P操作若已有进程占有临界资源，进程必须等待，直到临界资源空闲为止；若无进程占用，可使用它进程完成临界区操作（即临界资源使用完）后，通过执行V操作释放临界资源，供其

它进程使用P/V操作实现进程间互斥输入进程A……P(s)读消息到缓冲区V(s)……输出进程B……P(s)从缓冲区取走消息V(s)……用信号量可以方便地解决n个进程互斥地使用临界区的问题。信号量的取值范围

是+1~（1-n)。信号量的值为负时，说明一个进程正在临界区执行，其它的正排在信号量等待队列中等待，等待的进程数等于信号量值的绝对值例：若P、V操作的信号量初值为1，当前值为-3，则表示3个等待进程。2、利用信号量实现

进程之间的同步进程同步：是指相互合作的一组共行进程，各自以独立的，不可预知的速度向前推进，在前进过程中彼此之间需要相互协调步伐，才能更好地完成统一项任务。这些进程互相合作，在一些关键点上可能需要互相等待或互通消息。为了解决进程的同步，同样也可以引入信号量

P/V操作实现进程间同步例：用信号量实现计算进程与打印进程之间的同步过程。假定计算进程和打印进程共同使用一个单缓冲。分析：当计算进程对数据的计算尚未完成时，计算的结果没有送入缓冲区，打印进程不能执行打印

操作。一旦计算机把计算结果送入缓冲区后，就应给打印进程发送一信号，打印进程收到该信号后，便可从缓冲区取出计算结果进行打印。在打印进程尚未把缓冲区的计算结果打印完之前，计算进程也不能把下一次的计算结果送入缓冲区。只有在打印进程打印完缓冲区中的内容，给计算进程发出一个信号后

，计算进程才能将下一次的计算结果送入缓冲区。因此，计算进程和打印进程也是同步的。为此，引入两个同步信号量s1和s2。S1：表示缓冲区是否空，s1的初值为1;S2：表示缓冲区中是否有可供打印的计算结果，其初始值为0。计算进程(Pc)和打印进程(Pp)之间的同步算法如下：int

s1,s2;s1=1;s2=0;voidPc(){/*计算进程*/while(TRUE){computernextnumberp(s1);addthenumbertobufferv(s2);…}}voidPp(){/*打印进程*/while(TRUE){p(s2);takenext

numberfrombufferv(s1);printthenumber…}}voidmain(){parbegin(Pc,Pp);}两个经典的同步/互斥问题--生产者和消费者问题假定有一组生产者和一组消费者进程，通过一个有界缓冲区发生联系。正常情况下，生产者将生产的产品放入缓冲区，消费者从缓冲

区取用产品。当缓冲区满时，生产者要等消费者取走产品后才能向缓冲区放下一个产品；当缓冲区空时，消费者要等生产者放一个产品入缓冲区后才能从缓冲区取下一个产品。inout01n-1同步问题：•生产者进程不能往“满”的缓冲区中放置产品•

消费者进程不能从“空”的缓冲区中取产品设有界缓冲区的容量为n。为了正确地存取缓冲区，要求各生产者与消费者进程互斥地使用缓冲区。为此，要设两个同步信号量分别标识生产者进程和消费者进程能否正确前进的标志。用empty表

示空缓冲个数，初值为n；用full表示装满产品的缓冲个数，初值为0。再设置一个互斥使用临界区的信号量mutex，初值为1。两者的同步算法如下：生产者－消费者算法-1varmutex,empty,full:semaphore;mutex:=1;实现互斥访问的互斥信号量e

mpty:=n;full:=0;空缓冲区和装满产品的缓冲区的个数buffer:array[0..n-1]ofproduct;环形队列缓冲区in,out,goods:integerin:=0;out:=0;指向空缓冲区和装满产品的缓冲区be

gincobegin并发进程producer和consumerproducer;consumer;coendend生产者－消费者算法-2procedureproducer;生产者beginwhiletruedobeginproducenextproduct;生产一个产品

productP(empty);请求将产品存入空的缓冲区P(mutex);请求独占使用缓冲区资源buffer(in):=product;产品送入空缓冲区in:=(in+1)modn;in指针移动到下一个空缓冲区V(mutex);释放使用缓冲区资源V(f

ull);有产品的缓冲区增加一个endend;生产者－消费者算法-3procedureconsumer;消费者进程beginwhiletruedobeginP(full);请求消费缓冲区中的资源P(mutex);请求独占使用缓冲区资源good

s:=buffer(out);将out所指向的缓冲区产品送goodsout:=(out+1)modn;out移动到下一个装满产品的缓冲区V(mutex);释放使用缓冲区资源V(empty);空缓冲区增加一个consumeprod

uct;endend;P、V操作的次序问题无论是生产者还是消费者，P操作的顺序是重要的。应该将互斥使用的信号量的P操作放在紧挨临界区的位置，如果把生产者进程中的两个P操作交换次序，当缓冲区满时，生产者欲向缓冲区放产品时，将在P(empty)上等待，但它已得到

了使用缓冲区的权力。若此后，消费者欲取产品时，由于申请使用缓冲区不成功，它将在P(mutex)上等待。从而导致生产者等待消费者取走产品，而消费者却在等待生产者释放缓冲区，这种相互等待是无休止的，从而造成系统死锁。一般来说，V原语是

释放资源的，所以可以任意次序出现，但P原语则不然，如果次序混乱，将会造成进程之间的死锁。两个经典的同步/互斥问题读者与写者问题有一个许多进程共享的数据区，对共享资源的读写操作，任一时刻“写者”最多只允许一个，而“读者”则允许多

个：“读--写”互斥：若一个写进程正在写，禁止任何进程读。“写--写”互斥：一次只有一个写进程可以往数据区中写；―读--读‖允许：任意多的读进程可以同时读这个数据区；解决读者/写者问题，需设置两个信号量：（1）读互斥信号量rmutex,用于使读

者互斥地访问共享变量count,这里count是记录有多少读者正在读;（2）写互斥信号量wmutex,用于实现读写互斥和写写互斥地访问共享文件。读者、写者问题算法－1varrmutex,wmutex:semaphore;rmutex:=1;wmutex:=1count:integercoun

t:=0begincobegin并发进程reader和writerreader;writer;coendend读者、写者问题算法－2procedurereader;beginP(rmutex);count:=count+1;ifcount=1thenP(wmutex);第一个读者开始访问就禁止写

者访问V(rmutex);读文件；P(rmutex);count:=count-1;ifcount=0thenV(wmutex);没有读者访问就允许写者访问V(rmutex)end读者、写者问题算法－3procedurewriter;beginP(wmutex);

写文件；V(wmutex);end五、管程(monitor)用信号量可实现进程间的同步，但由于信号量的控制分布在整个程序中，其正确性分析很困难。管程是管理进程间同步的机制，它保证进程互斥地访问共享变量，并方便地阻塞和唤醒进程。管程可用函数库的形式实现。相

比之下，管程比信号量好控制。信号量同步的缺点同步操作分散：信号量机制中，同步操作分散在各个进程中，使用不当就可能导致各进程死锁（如P、V操作的次序错误、重复或遗漏）易读性差：要了解对于一组共享变量及信号量的操作

是否正确，必须检查整个系统或者并发程序；不便于维护和修改：各模块的独立性差，任一组变量或一段代码的修改都可能影响全局；正确性难易保证：操作系统或并发程序通常很大，很难保证这样的一个复杂的系统没有逻辑错误；管

程的引入1973年，Hoare和hanson提出基本思想：是把信号量及其操作原语封装在一个对象内部。即：将共享变量以及对共享变量能够进行的所有操作集中在一个模块中。管程的定义：管程是关于共享资源的数据结构及

一组针对该资源的操作过程所构成的软件模块。管程的主要特征模块化：一个管程是一个基本程序单位，可以单独编译。增加了模块的相对独立性；抽象数据类型：系统按资源管理的观点分解成若干模块，用数据表示抽象的系统资源，按共享资源和专用资源不同

的管理方式定义模块的类型和结构，使同步操作相对集中。模块之间关系清晰。信息封装：管程是半透明的，管程中的外部过程（函数）实现了某种功能，且这些功能的实现，在其外部则是不可见的。管程的实现要素管程中的

共享变量在管程外部是不可见的，外部只能通过调用管程中所说明的外部过程（函数）来间接访问管程中的共享变量；为了保证管程共享变量的数据完整性，规定管程必须互斥进入；管程通常是用来管理资源的，因而在管程中设有进程等待队列以及相应的等待及唤醒操作。管程中的多个进程进入当一个进入管程的进程执行等

待操作时，它应当释放管程的互斥权；当一个进入管程的进程执行唤醒操作时（如P唤醒Q），管程，管程中便存在两个同时处于活动状态的进程。管程中的唤醒切换方法：P等待Q继续，直到Q等待或退出；Q等待P继续，直到P等待或退出；规定唤醒为管程中最后一个可执行的操作；管程的操作当进程执行

管程中的过程时被堵塞，应该退出管程，否则就阻碍其他进程的进入引入条件变量和wait(x),signal(x)操作预防死锁。条件变量：在管程内部通常使用一种特殊类型的变量----条件变量，每个变量标识一种等待原因，对应一个队列。并不取具体数值。管程需

要进行初始化monitorringbuffer;varrbuffer:array[0..n-1]ofitem;环形缓冲区goods,k,nextempty,nextfull:integer;k是缓冲区中的元素个数empty,full:condition;条件变量procedureent

ryput(varproduct:item);向缓冲区送元素的过程beginifk=nthenwait(empty);产品已经满，等待空闲缓冲区，阻塞rubffer[nextempty]:=product;k:=k+1;产品增加nextempty:=(nextempty+1)modn;改变指针

signal(full);唤醒因为等待产品而阻塞的进程end;管程实例：生产者/消费者-1procedureentryget(vargoods:item);从缓冲区取元素的过程beginifk=0thenwait(

full);等待有可消费的产品，阻塞goods:=rbuffer[nextfull];k:=k-1;产品减少nextfull:=(nextfull+1)modn;改变指针signal(empty);唤醒等待送

产品的生产者end;begin初始化变量k:=0;产品的数量nextempty:=0;nextfull:=0;end;管程实例：生产者/消费者-2producer:beginrepeatproduceanitem:ringbuffer.put(item);untilfalse;en

dconsumer:beginrepeatringbuffer.get(item);consumetheitem;untilfalseend管程实例：生产者/消费者-3消息缓冲-高级通信原语高级通信：是指用户可直接利用操作系统的一组通信命令，高效地传递大量数据的一种通信方式高效通信机制一般有：管

道通信系统、消息传递系统等消息传递系统：进程间的数据交换以消息（message）为单位，直接利用系统提供的一组通信命令（原语）实现通信消息：是进程之间以不连续的成组方式发送的信息。消息缓冲区：系统设置一个大的缓冲区，作为消息缓冲池，它又

分成若干消息缓冲区，每个放一个消息当进程需要发送消息时，就申请消息缓冲区。消息缓冲区是进程通信的基本单位。消息缓冲区的类型structmessage_buffer{xxsender；发送进程标识符xxsize；消

息长度xxtext；消息正文structmessage_buffer*next；指向下一个消息缓冲区的指针}PCB中有关消息通信的数据项structPCB{......mq;接受消息队列队首指针sm;接受消息队列资源信号量mutex;接受消

息队列互斥信号量......}消息缓冲通信的过程发送原语........接受原语........1.申请消息缓冲区2.消息进入消息缓冲区3.消息缓冲区挂入接受队列4.接收进程摘下消息缓冲区，读入5.归还系统消息缓

冲区消息缓冲原语-send(B,a)发送消息原语先在自己的内存空间，设置一发送区a，把待发送的消息正文、发送进程标识符、消息长度等信息填入其中，然后调用发送原语。如下一页的消息缓冲通信图所示。消息缓冲原语-send(B,a)发送消息原语Proceduresend(re

ceiver,a)Begingetbuf(a,size,i);根据a区消息长度来申请一缓冲区ii.sender:=a.sender;i.size:=a.size;i.text:=a.text;i.next:=0getid(PCB,receiver,j);获得接收进

程的内部标识符jP(j.mutext);申请资源Insert(j.mq,I);将i挂在接收进程j的消息队列mq上（属于临界资源）V(j.mutext);释放资源V(j.sm);消息队列同步信号量smEnd消息缓冲原语-receive(b)接受消息原语

Procedurereceive(b)BeginP(j.sm);P(j.mutext);remove(j.mq,i);从自己的消息缓冲队列mq中摘下第一个消息缓冲区iV(j.mutext);b.sender:=i.sender;b.size:=i.size;b.te

xt:=i.text;putbuf(i);End死锁死锁在多道程序系统中，并发进程改善了系统资源利用率和提高系统的吞吐量，但可能死锁。例：一个计算机系统，它有4台磁带机和2个并发执行的进程。某一时刻，每一进程都已占有2台磁带机，还要再请求一台磁带机才

能完成它们的任务。这时，由于系统再无空闲的磁带机，两个进程就处于永远的等待状态，我们就说系统产生了死锁。资源特性硬件资源：如打印机、磁带机、主存等。软件资源：如共享变量、数据库中的加锁记录。可抢占资源

：是这样一类资源，当资源从占用进程剥夺走时，对进程不产生什么破坏性的影响。如主存、CPU。不可抢占资源：一旦分配，不能强收回，只能由其自动释放。如打印机、磁带机。通常情况下，死锁涉及的是不可抢占资源。一个进程必须按下述三个顺序事件使用资源。（1）请求资源：若请求不能立即满足，则申请者等待。

（2）使用资源：获得资源后，可使用它。（3）释放资源：使用完毕，将资源归还系统。死锁的定义死锁：是指多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都将永远不能向前推进。死锁产生原因竞争资源。系统提供的

资源不能满足每个进程的需要多道程序运行时，进程推进顺序不合法。进程在运行过程中，请求和释放资源的顺序不当，也同样会导致产生进程死锁。死锁产生的必要条件1）互斥条件。指进程对所分配到的资源进行排它性使用。每

个资源是不可共享的，它或者已经分配给一个进程，或者空闲。2）不剥夺条件。资源已获得，未用完不被剥夺，用完时自己释放。3）请求和保持条件。进程已保持了至少一个资源，但又请求新资源，无时，阻塞等待，但又对已

经分配给它的资源保持不放。4）环路等待条件。存在一个进程循环链，链中有二个或多个进程，每一个进程正在等待链中的下一个成员保持的资源。解决死锁的方法用有向图研究解决死锁的方法。图中圆圈代表进程，方块代表资源。资源已经分配给进程用从资源(方块)到进程(圆圈)的有向弧表示

；进程请求该资源用从进程到资源的有向弧表示。P105死锁例子死锁的预防不太可能避免死锁，因为有些进程无法事先提供最大资源需求量。因产生死锁须四个必要条件。若能破坏其中的一个或几个条件，则死锁不发生。(1)破坏互斥条件资源的互斥使用条件是由资源

本身的性质决定的，因此不能破坏。但如果采用spooling技术，就可以将一台独享设备改造成多台设备，满足多个进程的需求，可预防死锁。实际中，不是所有设备都能采用spooling技术的。即使采用spooling技术，由于多个进程竞争磁盘

空间，磁盘空间的不足，仍可能导致死锁。死锁的预防(2)(2)破坏请求和保持条件（资源独占）让进程在开始运行前，必须获得其所需的全部资源。若系统不能满足，则该进程等待。然而，许多进程在开始运行之前，不能精确提出所用资源数量。如果它能提出，那么就可以采用银行家算法避免死锁了。死锁的预防

(3)(3)破坏非剥夺条件当一个进程已占有某些资源，又申请新的资源而不能立即得到满足时，则在进入阻塞状态前强行使其释放已经占有的资源。以后运行时，再重新申请。这个办法显然也不行，因为保护进程放弃资源时的现场以及之后的恢复现场，系统要付出很高的代价。死锁的预防(4

)(4)破坏循环等待条件(资源顺序分配)将系统全部资源按类进行全局编号排序。进程对资源的请求必须按照资源的序号（递增或递减顺序）申请，这样，在资源分配图中就不会出现环路，使进程一直运行，而不出现死锁。(即有序资源分配法)有序资源分配法：即将系统中的所有资源都

按类型赋予一个编号，如打印机为1，磁带机为2，等等。并且要求每一个进程均严格地按照编号递增的次序请求资源。也就是说，只要进程提出请求资源Ri，则在以后的请求中，只能请求排在Ri后面的那些资源，不能再要求编号低于Ri的那些资源。对资源请求作了这样的限制后，系统中就不会再出现几个进程对资源的请求

成为环路的情况。存在的问题：各种资源编号后不宜修改，从而限制了新设备的增加。例：系统拥有资源为：输入机=1，打印机=2，绘图机=3，磁带机=4，光盘=5。系统有两个进程A和B。所有进程对资源的请求必须严格按序号递增顺序进行。如果A请求到资源j，B请求到资源i。若i>j，允

许A请求B占有的资源i，但绝不允许B请求A占有的资源j，故进程资源图绝不会形成环路。但找到能满足所有进程要求的资源编号不可能。发现死锁允许死锁发生，一旦发现，则用最小的代价恢复系统正常资源分配表S进程等待表W未阻塞进程表L选择L中：未阻塞进程选择S中：未

阻塞进程释放资源修改WOKLL表，所有进程进入表，死锁状态有进程不能进入解除死锁死锁状态的恢复，常采用如下两种方法：1、资源剥夺法可以从一些进程那里强行剥夺足够数量的资源分配给死锁进程，以解除死锁状态。剥夺的顺序可以是以花费最小资源数为依据。并且需

要在每次剥夺后重新调用检测算法。一个资源被剥夺的进程必须退回到前面获得这个资源的地方。还原算法：恢复计算状态建立检查点：恢复到局部检查点解除死锁（2）2、撤消进程法按照某种顺序逐渐地撤销已死锁的进程，直到获得为解除死锁所需要的足够可用的资源为止。使全部死锁进程都夭折掉按照某种顺序逐个地

撤销进程，直至有足够的资源可用，使死锁状态消除为止。