同步通信与死锁.ppt

《同步通信与死锁.ppt》由会员分享，可在线阅读，更多相关《同步通信与死锁.ppt（67页珍藏版）》请在三一办公上搜索。

1、1,第三章 同步、通信与死锁,2,3.1 进程的同步与互斥在多道程序的环境中，系统中的多个进程可以并发执行，同时它们又要共享系统中的资源，由此诸进程间会产生错综复杂的相互制约的关系。一、进程的相互制约关系 1.间接相互制约关系 源于资源共享 若一个进程要求使用某一资源，而该资源正被另一个进程使用，并且这一资源不允许两个进程同时访问，那么该进程只有等待，只有这一资源释放后才能使用。2.直接相互制约关系 源于进程间的合作 一组进程分工协作，在执行的先后次序有约束，在一些关键点上协调工作。若一个进程运行到某点时，在尚未收到另一协作进程发来的信息前应阻塞自己，等协作进程发来消息后方可继续执行。,进程资

2、源进程,进程进程,3,进程间这种相互依赖又相互制约，相互合作又相互竞争的关系，主要表现在进程互斥和进程同步两方面二、进程互斥引例：宿舍电话的使用 打印机的使用1、临界资源 一次仅允许一个进程使用的资源称为临界资源。引例中的电话和打印机都属于临界资源。还有光盘刻录机、绘图仪、共享变量、共享的数据结构等等也是临界资源。2、临界区：每个进程中访问临界资源的那段程序段称为临界区。（临界段）,4,例：统计两个进程P1和P2对共享变量count的访问计数。P1：.P2:.R1=count;R2=count;R1=R1+1;R2=R2+1;count=R1;count=R2;.两进程并发执行，可能的执行顺序

3、为：P1:R1=count;R1=R1+1;P2:R2=count;R2=R2+1;count=R2;P1:count=R1;虽然两个进程各自都执行了对count加1的操作，但结果为何count只增加1？count是临界资源，P1、P2访问count的两个程序段就是临界区，两个进程必须互斥的进入临界区,否则就可能出与时间有关的错误.,5,、进程互斥当某一进程正在访问某临界区时，就不允许其它进程进入，否则就会发生无法估计的错误。进程之间的这种相互制约的关系称为进程互斥。,4、进入临界区的准则：每次至多有一个进程进入临界区内执行；若已有进程在临界区中，试图进入此临界区的其他进程应等待；进入临界区的

4、进程应在有限时间内退出，以便让等待队列中的一个进程进入。,6,三、进程同步,引例：两位同学约好星期天去玩，早上8:00在校门口，不见不散。当一个同学先来到校门口，要等另一个同学，到齐后一起去玩。,互斥的概念来自于诸进程对临界资源的竞争，同步来源于多个进程的合作。在人类社会中竞争与合作是永恒的。进程同步：几个进程相互合作，一个进程到达某点后，若另一进程尚未完成某些操作，就必须停下来等待，只有等另一进程的这些操作完成了才能继续执行。,7,例：计算fun1(X)*fun2(y)两进程合作完成任务进程1：计算fun1(X)。进程2：计算fun2(X)；与进程1结果相乘。进程1和进程2并发执行。,8,3

5、.2 进程互斥的实现,一、实现进程互斥的软件算法现在很少用软件方法解决互斥，但通过学习软件解法能使读者了解到，在早期进程互斥问题的解决并不是一件很简单的事。,9,尝试(1),bool inside1=false;/P1不在其临界区内bool inside2=false;/P2不在其临界区内cobegin process P1()process P2()while(inside2);while(inside1);inside1=true;inside2=true;临界区;临界区;inside1=false;inside2=false;coend P1和P2可能同时进入临界区,10,尝试(2),b

6、ool inside1=false;/P1不在其临界区内bool inside2=false;/P2不在其临界区内cobeginprocess P1()process P2()inside1=true;inside2=true;while(inside2);while(inside1);临界区;临界区;inside1=false;inside2=false;coendP1和P2可能永远等待。,11,process P0()inside0=true;turn=1;while(inside1,process P1()inside1=true;turn=0;while(inside0,cobegin

7、,coend,bool inside2;inside0=false;inside1=false;enum 0,1 turn;,Peterson算法,12,为每一进程设标志位insidei，当insidei=true时，表示进程pi要求进入，或正在临界区中执行。此外再设一个变量turn，用于指示允许进入的进程编号。进程0为了进入先置inside0=true，并置turn为1，表示应轮到p1进入。接着再判断inside1&turn=1的条件是否满足,若不满足则可进入。或者说当inside 1=false或者turn=0时，进程可以进入。前者表示p1未要求进入，后者表示仅允许p0进入.,13,软件解

8、法的缺点,1.忙等待2.实现过于复杂，需要较高的编程技巧,14,二、实现进程互斥的硬件设施,用软件解决很难，现代计算机大多提供一些硬件指令。利用关中断实现进程互斥 利用Test-and-Set指令实现互斥 利用swap指令实现进程互斥,15,1.利用关中断实现进程互斥,进程进入临界区时关中断，在进程退出临界区时开中断。关中断方法简单有效关中断方法的缺点,16,2.Test-and-Set（TS）指令实现互斥,TS指令bool TS(bool,17,TS指令实现进程互斥bool s=true;cobeginprocess Pi()/i=1,2,.,n while(!TS(s);/上锁 临界区;s

9、=true;/开锁coend,变量s代表了临界资源的状态，可把它看成一把锁。S初值设为true，表示没有进程在临界区，资源可用。进入临界区前，首先用TS指令测试s，若没有进程在临界区，则可进入，否则循环测试直至s的值为true；当进程退出临界区时，把s的值置为true。,18,3.swap指令实现进程互斥,swap指令又称交换指令，在Intel x86中称为XCHG。功能是交换两个字的内容。,void SWAP(bool,19,利用swap实现进程互斥为每一临界资源设置一个全局布尔变量lock，其初值为false，表示无进程在临界区内。在每个进程中有局部布尔变量keyi。,bool lock=

10、false;cobeginProcess Pi()/i=1,2,.,n bool keyi=true;do SWAP(keyi,lock);while(keyi);/上锁 临界区;SWAP(keyi,lock);/开锁coend,20,实现进程互斥的软件算法太过复杂，效率低下；实现进程互斥的硬件方法虽简单有效，但采用忙式等待，白白浪费cpu时间；将测试能否进入临界区的责任推卸给各进程，会削弱系统的可靠性，加重用户的编程负担；且这些方案只能解决进程互斥问题，却不能解决进程同步问题。,21,3.3 信号量与PV操作,一、信号量的概念 信号量的概念是由荷兰科学家Dijkstra于1965年提出的。,

11、管理和控制铁路和公路交通的重要工具是信号灯，利用信号灯的颜色控制各种车辆的正常通行。在操作系统中引入了信号灯（信号量）的概念，让多个进程通过信号量展开交互。,22,1.信号量的定义是一个结构型数据结构，定义如下：struct semaphore int value;/信号量的值 struct pcb*list;/信号量队列的头指针 信号量说明：semaphore s;信号量必须置一次且只能置一次初值，初值不能为负数。对信号量只能执行P、V操作,23,2.P、V操作对信号量仅能执行P、V操作。对信号量的P操作记为：P(S)，P操作是一个原子操作。对信号量的V操作记为：V(S),V操作是一个原子操

12、作。在实际系统中，一般情况下是由机器硬件提供P、V操作的指令，当然是原子操作，若机器不提供P、V操作的指令，则操作系统提供P、V操作原语。,24,P(s)：s.value-；若s.value0，则执行P(s)的进程继续执行；若s.value0，则执行P(s)的进程被阻塞，并把它插入到等待信号量s的阻塞队列中。,V(s)：s.value+；若s.value0，则执行V(s)的进程继续执行；若s.value0，则执行V(s)的进程从等待信号量s的阻塞队列中唤醒头一个进程，然后自己继续执行。,操作系统正是利用信号量的状态对进程和资源进行管理。从物理意义上理解，P操作相当于申请资源；V操作相当于释放资

13、源。,25,二、用信号量实现进程互斥,1.两个进程间的互斥 semaphore S；S=1；cobegin Process P1()Process P2()P（S）P（S）V（S）V（S）coend,临界区,临界区,26,对于两个并发进程，互斥信号量的值仅取1、0和-1三个值 若S1表示没有进程进入临界区若S0表示有一个进程进入临界区若S-1表示一个进程进入临界区，另一个进程等待进入。,27,例：有一个售票厅只能容纳300人，当少于300人时，可以进入购票；否则在外等待。若将每一个购票者看作一个进程，请用P、V操作编程实现。,semaphore S；S=300；Process Pi()（i=1

14、，2，3，）P(S)；进入购票厅；购票；离开购票厅；V(S)；,28,思考：对于n个并发进程，如何实现互斥；信号量的取值范围是什么，有什么含义。,设置互斥信号量 S=m（m为某种临界资源可用数量）cobegin process P1 process P2 process pn P（S）P（S）P（S）V（S）V（S）V（S）coend,临界区,临界区,临界区,互斥信号量联系一组并发进程，各进程对此信号量执行P、V操作，因此又称为公用信号量。,29,信号量取值范围：mm-n信号量的含义：S0表示有S个资源可用 S=0表示无资源可用 S0则|S|表示S等待队列中的进程个数,30,三、用信号量实现进

15、程的同步,1.进程同步模型 进程P1到达L1这一点时，若进程P2还未执行到L2点，进程P1就必须停下来等待，等到进程P2到达L2这一点时，P1才能继续运行。也就是进程P1在L1这一点要与进程P2同步。（P1等待P2）semaphore s；S=0Cobegin process P1（）process P2（）L1:P(s)L2:V(s)coend,总结：P1在L1点等待P2进程执行到L2点才能继续执行。设置信号量s=0P1进程L1点：P(S)P2进程L2点：V(S),31,在操作系统中，同步有各种各样，归纳起来有两类：保证一组合作进程按确定的次序执行保证共享缓冲区的合作进程的同步。,2.合作进

16、程的执行次序 若干个进程为了完成一个共同任务而并发执行，在这些进程中，有些进程之间有次序的要求，有些进程之间没有次序的要求。为了描述方便，可以用一个图来描述诸进程合作完成某一任务的次序。进程流图,32,33,进程流图是实际例子抽象出来的。例：(a+b)*(c+d)+c*f,34,例：试用信号量实现这三个并发进程按确定的次序执行。a、分析进程的同步关系 进程P1、P2可并发执行，P3的执行必须等待P1、P2都完成后才能开始执行。b、设置信号量，说明含义、初值。s13=0 表示进程P1尚未执行完成；s23=0 表示进程P2尚未执行完成；c、写出程序描述,35,36,例：试用信号量实现这三个进程的同

17、步。Semaphore SB，SC；SB=0；SC=0；cobegin Pa（）Pb（）Pc（）P(SB);P(SC)；V(SB);V(SC);coend,37,3.共享缓冲区的合作进程的同步 设有一个缓冲区buffer，大小为一个字节，某计算进程和打印进程共用，CP进程不断产生字符，送buffer，IOP进程从buffer中取出字符打印。如不加控制，会有多种打印结果，这取决于这两个进程运行的相对速度。在这众多的打印结果中，只有CP、IOP进程的运行刚好匹配的一种是对的，其它均为错误，并且不能重现。,38,要保证打印结果的正确，CP、IOP必须遵循以下同步规则：(1)当CP把结果送入buffe

18、r后，IOP才能从buffer中取，否则IOP必须等待；(2)当IOP从buffer中取走数据后，CP才能将新产生数据送buffer，否则也必须等待。,解决这个问题的步骤：(1)分析问题，弄清楚同步关系，如上分析；(2)设置信号量，说明含义、初值；(3)写出程序描述。,39,40,四、互斥和同步对信号量操作方法的差异,互斥和同步都是通过对信号量的P、V操作来实现的，但这两种控制机制对信号量的操作策略是不同的。互斥的实现：是不同进程对同一信号量进行P、V操作。进入临界区之前执行P操作，退出临界区后执行V操作。同步的实现：Pa进程要同步等待Pb需设置一信号量，Pa进程中实行P操作，Pb进程实行V操

19、作。若进程Pb也要同步等待Pa，则要设置另一个信号量。P.V操作必须成对出现，有一个P操作就一定有一个V操作 当为互斥操作时，它们同处于同一进程 当为同步操作时，则不在同一进程中出现,41,五、经典的进程同步、互斥问题,1.生产者消费者问题,问题描述：有m个生产者和n个消费者，它们共享可存放k件产品的缓冲区。只要缓冲区未满，生产者就可以把产品送入缓冲区;只要缓冲区未空，消费者就可以从缓冲区中取走物品。,42,著名的生产者-消费者问题是计算机操作系统中并发进程内在关系的一种抽象，是典型的进程同步问题。在操作系统中，生产者进程可以是计算进程、发送进程；而消费者进程可以是打印进程、接收进程等等。解决

20、好生产者-消费者问题就解决好了一类并发进程的同步问题。,43,问题分析,对于生产者进程：生产一个产品，当要送入缓冲区时，要检查是否有空缓冲区，若有，则可将产品送入缓冲区，并通知消费者进程；否则，等待；对于消费者进程：当它去取产品时，要看缓冲区中是否有产品可取，若有则取走一个产品，并通知生产者进程，否则，等待。这种相互等待，并互通信息就是典型的进程同步。因此应该设两个同步信号量：empty：表示可用的空缓冲区的数目，初值为k full：表示可以使用产品的数目，初值为。缓冲区是一个临界资源，必须互斥使用，所以另外还需要设置一个互斥信号量mutex，其初值为。,44,问题的解,item Bk;sem

21、aphore empty;empty=k;/可以使用的空缓冲区数semaphore full;full=0;/缓冲区内可以使用的产品数semaphore mutex;mutex=1;/互斥信号量int in=0;/放入缓冲区指针int out=0;/取出缓冲区指针,cobeginprocess producer_i()process consumer_j()while(true)while(true)produce();P(full);P(empty);P(mutex);P(mutex);take()from Bout;append to Bin;out=(out+1)%k;in=(in+1)

22、%k;V(mutex);V(mutex);V(empty);V(full);consume();coend,45,讨论：若将生产者进程中两个P操作交换次序，那么当缓冲区存满k件产品（empty=0，mutex=1，full=k）时，生产者又生产一件产品，将在P(empty)上等待，此时mutex=0。消费者进程将在P(mutex)上等待。这就导致两进程都处于无休止的等待状态，造成了死锁。若将消费者进程中两P操作交换次序，则当缓冲区为空时，也会出项上述类似问题。,46,总结：P.V操作必须成对出现，有一个P操作就一定有一个V操作。当为互斥操作时，它们同处于同一进程。当为同步操作时，则不在同一进程

23、中出现。如果两个P操作在一起，那么P操作的顺序至关重要。一个同步P操作与一个互斥P操作在一起时，同步P操作在互斥P操作前。而两个V操作在一起时顺序无关紧要。,47,2.读者/写者问题,问题描述有两组并发进程:读者和写者,共享一个文件F要求：允许多个读者同时执行读操作只允许一个写者执行写操作任一写者在完成写操作之前不允许其它读者或写者工作写者执行写操作前，应让已有的写者和读者全部退出,48,问题分析,读者和写者互斥，写者和写者互斥访问文件设信号量writeblock，用于实现读写互斥、写写互斥地访问文件。另设一个全局变量readcount，记录正在读的读者数目。设置信号量mutex，用于使读者互

24、斥地访问共享变量readcount。,49,int readcount=0;/读进程计数semaphore writeblock,mutex;writeblock=1;mutex=1;cobeginprocess reader_i()process writer_j()P(mutex);P(writeblock);readcount+;写文件;if(readcount=1)V(writeblock);P(writeblock);V(mutex);读文件;P(mutex);readcount-;if(readcount=0)V(writeblock);V(mutex);Coend,50,3.哲学

25、家就餐问题,问题描述,有五个哲学家围坐在一圆桌旁，桌中央有一盘通心面，每人面前有一只空盘于，每两人之间放一把叉子。每个哲学家思考、饥饿、然后吃通心面。为了吃面，每个哲学家必须获得两把叉子，且每人只能直接从自己左边或右边去取叉子。,51,问题分析,每把叉子都必须互斥使用，因此为每把叉子设置互斥信号量forki(i=0,1,2,3,4),初值均为1；当哲学家吃面前必须执行两个P操作，获得自己左边和右边的两把叉子；吃完后必须执行两次V操作，放下两把叉子。,52,semaphore fork5;for(int i=0;i5;i+)forki=1;cobegin process philosopher_

26、i()/i=0,1,2,3,4 while(true)think();P(forki);P(fork(i+1)%5);eat();V(forki);V(fork(i+1)%5);coend,53,上述解法可能出现永远等待，有若干种办法可避免死锁：（1）至多允许四个哲学家同时吃；（2）奇数号先取左手边的叉子，偶数号先 取右手边的叉子；（3）每个哲学家取到手边的两把叉子才吃，否则一把叉子也不取。,54,3.4 进程通信,进程通信(Interprocess Communication,IPC)是指进程之间的信息交换。信号量及P.V操作实现的是进程之间的低级通讯，所以P.V为低级通讯原语。它只能传递简

27、单的信号，不能传递交换大量信息。本节介绍高级进程通信，是指进程间高效的传送大量数据的通信方式。,55,进程间通信的方式,信号(signal)通信机制管道(pipeline)通信机制 消息传递(message passing)通信机制 信号量(semaphore)通信机制共享主存(shared memory)通信机制前两种是UNIX最早的版本就提供的进程通信机制。信号通信机制只能发送单个信号而不能传递数据；管道通信虽能传送数据，却只能在进程家族内使用，应用范围有限。,56,进程通信方式发展,UNIX发展历史中，AT&T的Bell与加大伯克利的BSD是两大主力。Bell致力于改进传统的进程IPC，

28、形成了SYSTEM IPC机制（上述后三种通信机制）。BSD在改进IPC的同时，把网络通信规程(TCP/IP)实现到UNIX内核中，考虑把同一计算机上的进程通信纳入更广的网络范围的进程间通信，这种努力结果出现了socket网络通信机制。,57,一、管道通信机制,管道通信是UNIX的传统进程通信方式，也是UNIX发展最有意义的贡献之一。所谓管道，是指用于连接一个读进程和一个写进程的特殊文件，称pipe文件。发送进程以字符流形式把大量数据送入管道，接收进程从管道中接收数据，所以叫管道通信。,58,管道的实质是一个共享文件，基本上可借助于文件系统的机制实现，包括（管道）文件的创建、打开、关闭和读写。

29、但写进程和读进程间的相互协调单靠文件系统机制解决不了，读写进程相互同步，必须做到以下几点：（1）互斥，即一个进程正在使用某个管道写入或读出数据时，另一个进程就必须等待；（2）发送者和接收者双方必须能够知道对方是否存在，如果对方已经不存在，就没有必要再发送信息。（3）同步，指当写进程把一定量的数据发送后，便睡眠等待，直到读进程把管道中数据取走后，在把它唤醒。反之当读进程读空管道时，也被阻塞，直到写进程将数据写入管道后，才将它唤醒。,59,二、共享主存通信机制,在主存中开辟一个公用存储区，要通信的进程把自己的虚地址空间映射到共享主存区。发送进程将信息写入共享主存区的某个位置上，接收进程可从此位置读

30、取信息。,60,三、消息传递通信机制,进程间的数据交换以消息为单位，程序员利用系统的通信原语实现通信。操作系统隐藏了通信的实现细节，简化了通信程序编制的复杂性。因而得到广泛应用。,61,消息传递通信机制可分为：直接通信：发送进程直接把消息发送给接收者，并将它挂在接收进程的消息缓冲队列上。接收进程从消息缓冲队列中取得消息。间接通信：发送进程将消息发送到某种中间实体中（信箱），接收进程从中取得消息。也称信箱通信，在网络中称为电子邮件系统。,62,思考,两种方式的主要区别？前者需要两进程都存在，后者不需要。,63,1.直接通信的实现,发送或接收消息的进程必须指出消息发给谁或从谁那里接收消息。至少需要

31、提供两条原语：原语send（P，消息）：把一个消息发送给进程P原语receive（Q，消息）：从进程Q接收一个消息直接通信的实现在操作系统空间设置一组缓冲区。当发送进程需要发送消息时，执行send系统调用，产生访管中断，进入操作系统。操作系统为发送进程分配一个空缓冲区，并将所发送的消息从发送进程copy到缓冲区中，然后将该载有消息的缓冲区连接到接收进程的消息链链尾，如此就完成了发送过程。发送进程返回到用户态继续执行。,64,在以后某个时刻，当接收进程执行到receive接收原语时，也产生访管中断进入操作系统。由操作系统将载有消息的缓冲区从消息链中取出，并把消息内容copy到接收进程空间，之后收

32、回缓冲区，如此就完成了消息的接收。接收进程返回到用户态继续进行。,65,2.间接通信的实现,Send实现send（MailBox，M）：把信件M送到指定的信箱MailBox中步骤：查找指定信箱MailBox；若信箱未满，则把信件M送入信箱且唤醒“等信件”者；若信箱已满置发送信件进程为“等信箱”状态；,66,Receive实现,receive（MailBox，X）：从指定信箱MailBox中取出一封信，存放到指定的地址X中步骤：查找指定信箱MailBox；若信箱有信，则取出一封信存于X中且唤醒“等信箱”者；若信箱无信件则置接收信件进程“等信件”状态；,67,信箱的设置,私有信箱 设置在用户空间 设置在系统空间公用信箱,