《操作系统原理》第三章进程间的并发控制和死锁.ppt

第三章进程之间的并发控制和死锁,进程通信,进程的状态是基于一定的原因和条件而变化的，而这些原因和条件又常常是由于进程之间的相互制约关系引起的。系统中诸进程之所以有这种关系，是由两方面原因引起的：1）各并发进程对资源的共享2）系统中存在若干协作进程,1、各并发进程对资源的共享 互斥关系：通过共享资源而使进程之间产生的关系叫间接制约关系，又叫互斥关系。可用“进程资源进程”来描述。例：进程P1和P2在运行中都要使用打印机，为了使各进程输出的完整性，打印机的使用必须独占。一旦系统将打印机分配给进程P1，那么进程P2必须等待，等待P1使用完打印机并释放后，才能使用。,2、系统中存在若干协作进程 同步关系：通常，一个用户作业涉及一组并发进程（输入、计算和输出进程），这些进程须相互协作完成这项任务。在运行过程中，这些进程可能要在某些同步点上等待协作者发来信息后才能继续运行。进程之间的这种制约关系叫直接制约关系。又叫同步关系。可用“进程进程”来描述,进程通信：是指进程的上述相互依赖关系。进程之间的这种相互依赖又相互制约、相互合作又相互竞争的关系，也即进程的同步与互斥关系。互斥是同步的一个特例。进程之间的这种关系就叫进程的低级通信。,一、进程之间的互斥,（进程的互斥是由于共享资源而引起的）共享资源：慢速的硬件设备，如打印机、磁带机等资源软件资源，如共享变量、共享文件等临界资源（critical resource）：就是一次仅允许一个进程使用的资源。如：打印机临界区（critical section）：就是并发执行的进程访问临界资源的那个必须互斥执行的程序段,程序1Y=Y+1output,程序2Y=Y+2output,内存共享区Y,pcb1,pcb2,临界资源和临界区,为了正确而有效地使用临界资源，系统中的并发进程需要遵循如下四个准则：空闲让进无进程在临界区就允许进入忙则等待有进程在临界区，则等待有限等待多进程要求进入临界区是，应该让某一个进入，而不能无限等待都不让进让权等待等待的进程必须释放CPU,四个准则,1、关中断,二、解决进程之间互斥的方法,进程AClose_INT;Critical_region();Open_INT;,进程BClose_INT;Critical_region();Open_INT;,解决思想在临界区中防止发生进程调度保证临界区操作的完整性方法分析用户控制系统中断是非常危险的本方法对多个CPU系统将失去作用,2、lock,unlock在原语里设置一个公共变量代表临界资源的状态。x=使用临界资源必须做如下三步：1、检查锁的设置2、进入临界区，访问临界区3、释放临界资源，开锁,二、解决进程之间互斥的方法,锁机制框图,测试x=0?,Lockx,x=1,进入临界区,退出临界区Unlockx,x=0,返回继续测试,x=1,x=0,返回,显然，采用加锁机制，由于进程循环测试，白白浪费了CPU的时间，降低了系统的速度,三、进程之间的同步,同步原因：一组进程要合作完成一项任务。例：两个用户进程通过共享缓冲区完成其计算和打印任务。计算进程负责将计算结果送入共享缓冲区，打印进程从缓冲区取数据打印。当缓冲区空时，不允许取数据，满时不允许送数据。否则，将出现错误。计算进程与打印进程这种制约关系，不是由于两个进程同时访问共享缓冲区，而是由于它们访问缓冲区时的速度不匹配造成的。为了使进程同步，需要引入信号量机制。,四、信号量,1965年，荷兰学者Dijkstra提出的。基本原理：两个或多个进程可以通过简单的信号进行合作，一个进程可以被迫在某一位置停止，直到它接收到一个特定的信号。任何复杂的合作需求通过适当的信号结构得到满足。为此，需要使用一个称作为信号量的特殊变量，以便通过信号量传送信号。信号量是一个数据结构定义如下：struct semaphore int value;Pointer_PCB queue;,整型变量，其值大小表示该资源的可用数量,是等待使用该资源的进程排成队列的队列头指针,对信号量S的操作只允许执行P、V操作。其中P/V操作由原语组成，执行过程中不可分割。,P操作原语P(S)1）S:=S 1/请求一个资源2）If S=0,go on;if S0,blocked/申请不成功（资源用完），调用阻塞原语“让权等待”,V操作原语V(S)1）S:=S+1/释放一个资源2）If S0,go on;if Sready,go on/表示在信号链表，仍有等待该资源的进程，调用唤醒原语。,显然，P、V操作的引入，克服了加锁操作的忙等待现象，有效提高了系统的效率操作系统正是利用信号量的状态对进程和资源进行管理和控制的。从物理意义上理解，P操作相当于申请资源；V操作相当于释放资源。,1、利用信号量实现进程之间的互斥,引入一个互斥信号量，用mutex表示。对于互斥使用的资源，其信号量的初值为1欲进入临界区执行的进程须先对互斥信号量mutex执行P操作若已有进程占有临界资源，进程必须等待，直到临界资源空闲为止；若无进程占用，可使用它进程完成临界区操作（即临界资源使用完）后，通过执行V操作释放临界资源，供其它进程使用,P/V操作实现进程间互斥,输入进程AP(s)读消息到缓冲区V(s),输出进程BP(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;void Pc()/*计算进程*/while(TRUE)computer next number p(s1);add the number to buffer v(s2);,void Pp()/*打印进程*/while(TRUE)p(s2);take next number from buffer v(s1);print the number void main()parbegin(Pc,Pp);,两个经典的同步/互斥问题-生产者和消费者问题,假定有一组生产者和一组消费者进程，通过一个有界缓冲区发生联系。正常情况下，生产者将生产的产品放入缓冲区，消费者从缓冲区取用产品。当缓冲区满时，生产者要等消费者取走产品后才能向缓冲区放下一个产品；当缓冲区空时，消费者要等生产者放一个产品入缓冲区后才能从缓冲区取下一个产品。,in,out,0,1,n-1,同步问题：生产者进程不能往“满”的缓冲区中放置产品 消费者进程不能从“空”的缓冲区中取产品,设有界缓冲区的容量为n。为了正确地存取缓冲区，要求各生产者与消费者进程互斥地使用缓冲区。为此，要设两个同步信号量分别标识生产者进程和消费者进程能否正确前进的标志。用empty表示空缓冲个数，初值为n；用full表示装满产品的缓冲个数，初值为0。再设置一个互斥使用临界区的信号量mutex，初值为1。两者的同步算法如下：,生产者消费者算法-1,var mutex,empty,full:semaphore;mutex:=1;实现互斥访问的互斥信号量empty:=n;full:=0;空缓冲区和装满产品的缓冲区的个数buffer:array0.n-1 of product;环形队列缓冲区in,out,goods:integer in:=0;out:=0;指向空缓冲区和装满产品的缓冲区begin cobegin 并发进程 producer和consumer producer;consumer;coend end,生产者消费者算法-2,procedure producer;生产者 begin while true do beginproduce next product;生产一个产品productP(empty);请求将产品存入空的缓冲区P(mutex);请求独占使用缓冲区资源buffer(in):=product;产品送入空缓冲区in:=(in+1)mod n;in指针移动到下一个空缓冲区V(mutex);释放使用缓冲区资源V(full);有产品的缓冲区增加一个 endend;,生产者消费者算法-3,procedure consumer;消费者进程 begin while true do beginP(full);请求消费缓冲区中的资源P(mutex);请求独占使用缓冲区资源goods:=buffer(out);将out所指向的缓冲区产品送goodsout:=(out+1)mod n;out移动到下一个装满产品的缓冲区V(mutex);释放使用缓冲区资源V(empty);空缓冲区增加一个consume product;endend;,P、V操作的次序问题,无论是生产者还是消费者，P操作的顺序是重要的。应该将互斥使用的信号量的P操作放在紧挨临界区的位置，如果把生产者进程中的两个P操作交换次序，当缓冲区满时，生产者欲向缓冲区放产品时，将在P(empty)上等待，但它已得到了使用缓冲区的权力。若此后，消费者欲取产品时，由于申请使用缓冲区不成功，它将在P(mutex)上等待。从而导致生产者等待消费者取走产品，而消费者却在等待生产者释放缓冲区，这种相互等待是无休止的，从而造成系统死锁。,一般来说，V原语是释放资源的，所以可以任意次序出现，但P原语则不然，如果次序混乱，将会造成进程之间的死锁。,两个经典的同步/互斥问题,读者与写者问题 有一个许多进程共享的数据区，对共享资源的读写操作，任一时刻“写者”最多只允许一个，而“读者”则允许多个：“读-写”互斥：若一个写进程正在写，禁止任何进程读。“写-写”互斥：一次只有一个写进程可以往数据区中写；“读-读”允许：任意多的读进程可以同时读这个数据区；,解决读者/写者问题，需设置两个信号量：（1）读互斥信号量rmutex,用于使读者互斥地访问共享变量count,这里count是记录有多少读者正在读;（2）写互斥信号量wmutex,用于实现读写互斥和写写互斥地访问共享文件。,读者、写者问题算法1,var rmutex,wmutex:semaphore;rmutex:=1;wmutex:=1count:integercount:=0begin cobegin 并发进程 reader和writer reader;writer;coend end,读者、写者问题算法2,procedure reader;begin P(rmutex);count:=count+1;if count=1 then P(wmutex);第一个读者开始访问就禁止写者访问 V(rmutex);读文件；P(rmutex);count:=count-1;if count=0 then V(wmutex);没有读者访问就允许写者访问 V(rmutex)end,读者、写者问题算法3,procedure writer;begin P(wmutex);写文件；V(wmutex);end,五、管程(monitor),用信号量可实现进程间的同步，但由于信号量的控制分布在整个程序中，其正确性分析很困难。管程是管理进程间同步的机制，它保证进程互斥地访问共享变量，并方便地阻塞和唤醒进程。管程可用函数库的形式实现。相比之下，管程比信号量好控制。,信号量同步的缺点,同步操作分散：信号量机制中，同步操作分散在各个进程中，使用不当就可能导致各进程死锁（如P、V操作的次序错误、重复或遗漏）易读性差：要了解对于一组共享变量及信号量的操作是否正确，必须检查整个系统或者并发程序；不便于维护和修改：各模块的独立性差，任一组变量或一段代码的修改都可能影响全局；正确性难易保证：操作系统或并发程序通常很大，很难保证这样的一个复杂的系统没有逻辑错误；,管程的引入,1973年，Hoare和hanson提出基本思想：是把信号量及其操作原语封装在一个对象内部。即：将共享变量以及对共享变量能够进行的所有操作集中在一个模块中。管程的定义：管程是关于共享资源的数据结构及一组针对该资源的操作过程所构成的软件模块。,管程的主要特征,模块化：一个管程是一个基本程序单位，可以单独编译。增加了模块的相对独立性；抽象数据类型：系统按资源管理的观点分解成若干模块，用数据表示抽象的系统资源，按共享资源和专用资源不同的管理方式定义模块的类型和结构，使同步操作相对集中。模块之间关系清晰。信息封装：管程是半透明的，管程中的外部过程（函数）实现了某种功能，且这些功能的实现，在其外部则是不可见的。,管程的实现要素,管程中的共享变量在管程外部是不可见的，外部只能通过调用管程中所说明的外部过程（函数）来间接访问管程中的共享变量；为了保证管程共享变量的数据完整性，规定管程必须互斥进入；管程通常是用来管理资源的，因而在管程中设有进程等待队列以及相应的等待及唤醒操作。,管程中的多个进程进入,当一个进入管程的进程执行等待操作时，它应当释放管程的互斥权；当一个进入管程的进程执行唤醒操作时（如P唤醒Q），管程，管程中便存在两个同时处于活动状态的进程。管程中的唤醒切换方法：P等待Q继续，直到Q等待或退出；Q等待P继续，直到P等待或退出；规定唤醒为管程中最后一个可执行的操作；,管程的操作,当进程执行管程中的过程时被堵塞，应该退出管程，否则就阻碍其他进程的进入引入条件变量和wait(x),signal(x)操作预防死锁。条件变量：在管程内部通常使用一种特殊类型的变量-条件变量，每个变量标识一种等待原因，对应一个队列。并不取具体数值。管程需要进行初始化,monitor ringbuffer;var rbuffer:array0.n-1 of item;环形缓冲区goods,k,nextempty,nextfull:integer;k是缓冲区中的元素个数empty,full:condition;条件变量procedure entry put(var product:item);向缓冲区送元素的过程 beginif k=n then wait(empty);产品已经满，等待空闲缓冲区，阻塞rubffernextempty:=product;k:=k+1;产品增加nextempty:=(nextempty+1)mod n;改变指针signal(full);唤醒因为等待产品而阻塞的进程end;,管程实例：生产者/消费者-1,procedure entry get(var goods:item);从缓冲区取元素的过程beginif k=0 then wait(full);等待有可消费的产品，阻塞 goods:=rbuffernextfull;k:=k-1;产品减少nextfull:=(nextfull+1)mod n;改变指针signal(empty);唤醒等待送产品的生产者end;begin 初始化变量k:=0;产品的数量nextempty:=0;nextfull:=0;end;,管程实例：生产者/消费者-2,producer:beginrepeatproduce an item:ringbuffer.put(item);until false;endconsumer:beginrepeatringbuffer.get(item);consume the item;until falseend,管程实例：生产者/消费者-3,消息缓冲-高级通信原语,高级通信：是指用户可直接利用操作系统的一组通信命令，高效地传递大量数据的一种通信方式高效通信机制一般有：管道通信系统、消息传递系统等消息传递系统：进程间的数据交换以消息（message）为单位，直接利用系统提供的一组通信命令（原语）实现通信,消息：是进程之间以不连续的成组方式发送的信息。消息缓冲区：系统设置一个大的缓冲区，作为消息缓冲池，它又分成若干消息缓冲区，每个放一个消息,当进程需要发送消息时，就申请消息缓冲区。消息缓冲区是进程通信的基本单位。,消息缓冲区的类型,struct message_buffer xx sender；发送进程标识符 xx size；消息长度 xx text；消息正文 struct message_buffer*next；指向下一个 消息缓冲区的指针,PCB中有关消息通信的数据项,struct PCB.mq;接受消息队列队首指针sm;接受消息队列资源信号量mutex;接受消息队列互斥信号量.,消息缓冲通信的过程,发送原语.接受原语.,申请消息缓冲区消息进入消息缓冲区消息缓冲区挂入接受队列接收进程摘下消息缓冲区，读入归还系统消息缓冲区,消息缓冲原语-send(B,a)发送消息原语,先在自己的内存空间，设置一发送区a，把待发送的消息正文、发送进程标识符、消息长度等信息填入其中，然后调用发送原语。如下一页的消息缓冲通信图所示。,消息缓冲原语-send(B,a)发送消息原语,Procedure send(receiver,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)接受消息原语,Procedure receive(b)BeginP(j.sm);P(j.mutext);remove(j.mq,i);从自己的消息缓冲队列mq中摘下第一个消息缓冲区iV(j.mutext);b.sender:=i.sender;b.size:=i.size;b.text:=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。若ij，允许A请求B占有的资源i，但绝不允许B请求A占有的资源j，故进程资源图绝不会形成环路。但找到能满足所有进程要求的资源编号不可能。,发现死锁,允许死锁发生，一旦发现，则用最小的代价恢复系统正常资源分配表S进程等待表W未阻塞进程表L,选择L中：未阻塞进程,选择S中：未阻塞进程释放资源,修改W,解除死锁,死锁状态的恢复，常采用如下两种方法：1、资源剥夺法 可以从一些进程那里强行剥夺足够数量的资源分配给死锁进程，以解除死锁状态。剥夺的顺序可以是以花费最小资源数为依据。并且需要在每次剥夺后重新调用检测算法。一个资源被剥夺的进程必须退回到前面获得这个资源的地方。还原算法：恢复计算状态建立检查点：恢复到局部检查点,解除死锁（2）,2、撤消进程法 按照某种顺序逐渐地撤销已死锁的进程，直到获得为解除死锁所需要的足够可用的资源为止。使全部死锁进程都夭折掉按照某种顺序逐个地撤销进程，直至有足够的资源可用，使死锁状态消除为止。,