孙钟秀操作系统第三章同步、通信与死锁1.ppt

《孙钟秀操作系统第三章同步、通信与死锁1.ppt》由会员分享，可在线阅读，更多相关《孙钟秀操作系统第三章同步、通信与死锁1.ppt（67页珍藏版）》请在三一文库上搜索。

1、1,第三章 同步、通信与死锁,2,3.1 进程的同步与互斥 在多道程序的环境中，系统中的多个进程可以并发执行，同时它们又要共享系统中的资源，由此诸进程间会产生错综复杂的相互制约的关系。 一、进程间制约关系 1.竞争关系 源于资源共享，多个不存在逻辑关系的进程因共享资源而产生制约关系。 若一个进程要求使用某一资源，而该资源正被另一个进程使用，并且这一资源不允许两个进程同时访问，那么该进程只有等待，只有这一资源释放后才能使用。 2.协作关系 源于进程间的协作。 一组进程为完成共同任务分工协作，各进程都独立以不可预知速度推进，在执行的先后次序就有约束，在一些关键点上协调工作。若一个进程运行到某关键点

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

3、R2=count; R1=R1+1; R2=R2+1; count=R1; count=R2; . . 两进程并发执行，可能的执行顺序为： 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在校门口，不见不散。当一个同学先来到校门口，要等另一个同学，到齐后一起去玩。,互斥的概念来自于诸进程对临界资源的竞争，同步来源于多个进程的协作。在人类社会中竞争与协作是永恒的。 进程同步：几个进程相互协作，一个进程到达某点后，若另一进程尚未完成某些操作，就必须

5、停下来等待，只有等另一进程的这些操作完成了才能继续执行。协作进程间需要在某些关键点上排定执行先后次序而等待、传递信号或消息所产生的协作关系称为进程同步。,7,例：计算fun1(X)*fun2(y) 两进程合作完成任务 进程1：计算fun1(X)。 进程2：计算fun2(X)；与进程1结果相乘。 进程1和进程2并发执行。,8,3.2 进程互斥的实现,一、实现进程互斥的软件算法 现在很少用软件方法解决互斥，但通过学习软件解法能使读者了解到，在早期进程互斥问题的解决并不是一件很简单的事。,9,尝试 (1),bool inside1=false; /P1不在其临界区内 bool inside2=fal

6、se; /P2不在其临界区内 cobegin process P1( ) process P2( ) while(inside2); while(inside1); inside1=true; inside2=true; 临界区; 临界区; inside1=false; inside2=false; coend P1和P2可能同时进入临界区,10,尝试 (2),bool inside1=false; /P1不在其临界区内 bool inside2=false; /P2不在其临界区内 cobegin process P1( ) process P2( ) inside1=true; inside

7、2=true; while(inside2); while(inside1); 临界区; 临界区; inside1=false; inside2=false; coend P1和P2可能永远等待。,11,process P0( ) inside0=true; turn=1; while(inside1 ,process P1( ) inside1=true; turn=0; while(inside0 ,cobegin,coend,bool inside2; inside0=false; inside1=false; enum 0,1 turn;,Peterson算法,12,为每一进程设标志位

8、insidei，当insidei=true时，表示进程pi要求进入，或正在临界区中执行。此外再设一个变量turn，用于指示允许进入的进程编号。 进程0为了进入先置inside0=true，并置turn为1，表示应轮到p1进入。接着再判断inside1&turn=1的条件是否满足,若不满足则可进入。或者说当inside 1 =false或者turn=0时，进程可以进入。前者表示p1未要求进入，后者表示仅允许p0进入.,13,软件解法的缺点,1. 忙等待 2. 实现过于复杂，需要较高的编程技巧,14,二、实现进程互斥的硬件设施,用软件解决很难，现代计算机大多提供一些硬件指令。 利用关中断实现进程互

9、斥 利用Test-and-Set指令实现互斥 利用swap指令实现进程互斥,15,1.利用关中断实现进程互斥,进程进入临界区时关中断，在进程退出临界区时开中断。 关中断方法简单有效 关中断方法的缺点,16,2.Test-and-Set（TS）指令实现互斥,TS指令 bool TS(bool ,17,TS指令实现进程互斥 bool s=true; cobegin process Pi( ) /i=1,2,.,n while(!TS(s); /上锁 临界区; s=true; /开锁 coend,变量s代表了临界资源的状态，可把它看成一把锁。S初值设为true，表示没有进程在临界区，资源可用。进入临

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

11、(keyi,lock); while(keyi); /上锁 临界区; SWAP(keyi,lock); /开锁 coend,20,实现进程互斥的软件算法太过复杂，效率低下； 实现进程互斥的硬件方法虽简单有效，但采用忙式等待，白白浪费cpu时间；将测试能否进入临界区的责任推卸给各进程，会削弱系统的可靠性，加重用户的编程负担；且这些方案只能解决进程互斥问题，却不能解决进程同步问题。,21,3.3 信号量与PV操作,一、信号量的概念 信号量的概念是由荷兰科学家Dijkstra于1965年提出的。,管理和控制铁路和公路交通的重要工具是信号灯，利用信号灯的颜色控制各种车辆的正常通行。在操作系统中引入了信

12、号灯（信号量）的概念，让多个进程通过信号量展开交互。,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操作是一个原子操作。 在实际系统中，一般情况下是由机器硬件提供P、V操作的指令，当然是原子操作，

13、若机器不提供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操作相当于释放资源。,25,二、用信号量实现进程互斥,1. 两个进程间的互斥 s

14、emaphore 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，2，3，） P(S)； 进入购

15、票厅； 购票； 离开购票厅； 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,三、用信号量

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

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

18、出程序描述,35,36,例：试用信号量实现这三个进程的同步。 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,要保证打

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

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

21、程同步问题。 在操作系统中，生产者进程可以是计算进程、发送进程；而消费者进程可以是打印进程、接收进程等等。 解决好生产者-消费者问题就解决好了一类并发进程的同步问题。,43,问题分析,对于生产者进程：生产一个产品，当要送入缓冲区时，要检查是否有空缓冲区，若有，则可将产品送入缓冲区，并通知消费者进程；否则，等待； 对于消费者进程：当它去取产品时，要看缓冲区中是否有产品可取，若有则取走一个产品，并通知生产者进程，否则，等待。 这种相互等待，并互通信息就是典型的进程同步。 因此应该设两个同步信号量： empty：表示可用的空缓冲区的数目，初值为k full：表示可以使用产品的数目，初值为。 缓冲区是

22、一个临界资源，必须互斥使用，所以另外还需要设置一个互斥信号量mutex，其初值为。,44,问题的解,item Bk; semaphore empty; empty=k; /可以使用的空缓冲区数 semaphore full; full=0; /缓冲区内可以使用的产品数 semaphore mutex; mutex=1; /互斥信号量 int in=0; /放入缓冲区指针 int out=0; /取出缓冲区指针,cobegin process producer_i ( ) process consumer_j ( ) while(true) while(true) produce( ); P(f

23、ull); P(empty); P(mutex); P(mutex); take( ) from Bout; append to Bin; out=(out+1)%k; in=(in+1)%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)上等待。这就导致两进程都处于无休止的等待状态，造成了死锁。 若将

24、消费者进程中两P操作交换次序，则当缓冲区为空时，也会出项上述类似问题。,46,总结： P.V操作必须成对出现，有一个P操作就一定有一个V操作。 当为互斥操作时，它们同处于同一进程。 当为同步操作时，则不在同一进程中出现。 如果两个P操作在一起，那么P操作的顺序至关重要。 一个同步P操作与一个互斥P操作在一起时，同步P操作在互斥P操作前。 而两个V操作在一起时顺序无关紧要。,47,2. 读者/写者问题,问题描述 有两组并发进程: 读者和写者,共享一个文件F 要求： 允许多个读者同时执行读操作 只允许一个写者执行写操作 任一写者在完成写操作之前不允许其它读者或写者工作 写者执行写操作前，应让已有的

25、写者和读者全部退出,48,问题分析,读者和写者互斥，写者和写者互斥访问文件 设信号量writeblock，用于实现读写互斥、写写互斥地访问文件。 另设一个全局变量readcount，记录正在读的读者数目。 设置信号量mutex，用于使读者互斥地访问共享变量readcount 。,49,int readcount=0; /读进程计数 semaphore writeblock,mutex; writeblock=1; mutex=1; cobegin process reader_i( ) process writer_j( ) P(mutex); P(writeblock); readcount

26、+; 写文件; if(readcount=1) V(writeblock); P(writeblock); V(mutex); 读文件; P(mutex); readcount-; if(readcount=0) V(writeblock); V(mutex); Coend,50,3.哲学家就餐问题,问题描述,有五个哲学家围坐在一圆桌旁，桌中央有一盘通心面，每人面前有一只空盘于，每两人之间放一把叉子。每个哲学家思考、饥饿、然后吃通心面。为了吃面，每个哲学家必须获得两把叉子，且每人只能直接从自己左边或右边去取叉子。,51,问题分析,每把叉子都必须互斥使用，因此为每把叉子设置互斥信号量forki(

27、i=0,1,2,3,4),初值均为1； 当哲学家吃面前必须执行两个P操作，获得自己左边和右边的两把叉子；吃完后必须执行两次V操作，放下两把叉子。,52,semaphore fork5; for (int i=0;i5;i+) forki=1; cobegin process philosopher_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）至多允许四个哲学家同时

28、吃； （2）奇数号先取左手边的叉子，偶数号先 取右手边的叉子； （3）每个哲学家取到手边的两把叉子才吃，否则一把叉子也不取。,54,3.4 进程通信,进程通信(Interprocess Communication,IPC)是指进程之间的信息交换。 信号量及P.V操作实现的是进程之间的低级通讯，所以P.V为低级通讯原语。它只能传递简单的信号，不能传递交换大量信息。 本节介绍高级进程通信，是指进程间高效的传送大量数据的通信方式。,55,进程间通信的方式,信号(signal)通信机制 管道(pipeline)通信机制 消息传递(message passing)通信机制 信号量(semaphore)通

29、信机制 共享主存(shared memory)通信机制 前两种是UNIX最早的版本就提供的进程通信机制。信号通信机制只能发送单个信号而不能传递数据；管道通信虽能传送数据，却只能在进程家族内使用，应用范围有限。,56,进程通信方式发展,UNIX发展历史中，AT&T的Bell与加大伯克利的BSD是两大主力。 Bell致力于改进传统的进程IPC，形成了SYSTEM IPC机制（上述后三种通信机制）。 BSD在改进IPC的同时，把网络通信规程(TCP/IP)实现到UNIX内核中，考虑把同一计算机上的进程通信纳入更广的网络范围的进程间通信，这种努力结果出现了socket网络通信机制。,57,一、管道通信

30、机制,管道通信是UNIX的传统进程通信方式，也是UNIX发展最有意义的贡献之一。 所谓管道，是指用于连接一个读进程和一个写进程的特殊文件，称pipe文件。 发送进程以字符流形式把大量数据送入管道，接收进程从管道中接收数据，所以叫管道通信。,58,管道的实质是一个共享文件，基本上可借助于文件系统的机制实现，包括（管道）文件的创建、打开、关闭和读写。 但写进程和读进程间的相互协调单靠文件系统机制解决不了，读写进程相互同步，必须做到以下几点： （1）互斥，即一个进程正在使用某个管道写入或读出数据时，另一个进程就必须等待； （2）发送者和接收者双方必须能够知道对方是否存在，如果对方已经不存在，就没有必

31、要再发送信息。 （3）同步，指当写进程把一定量的数据发送后，便睡眠等待，直到读进程把管道中数据取走后，在把它唤醒。反之当读进程读空管道时，也被阻塞，直到写进程将数据写入管道后，才将它唤醒。,59,二、共享主存通信机制,在主存中开辟一个公用存储区，要通信的进程把自己的虚地址空间映射到共享主存区。发送进程将信息写入共享主存区的某个位置上，接收进程可从此位置读取信息。,60,三、消息传递通信机制,进程间的数据交换以消息为单位，程序员利用系统的通信原语实现通信。操作系统隐藏了通信的实现细节，简化了通信程序编制的复杂性。因而得到广泛应用。,61,消息传递通信机制可分为： 直接通信：发送进程直接把消息发送

32、给接收者，并将它挂在接收进程的消息缓冲队列上。接收进程从消息缓冲队列中取得消息。 间接通信：发送进程将消息发送到某种中间实体中（信箱），接收进程从中取得消息。也称信箱通信，在网络中称为电子邮件系统。,62,思考,两种方式的主要区别？ 前者需要两进程都存在，后者不需要。,63,1.直接通信的实现,发送或接收消息的进程必须指出消息发给谁或从谁那里接收消息。至少需要提供两条原语： 原语send（P，消息）：把一个消息发送给进程P 原语receive（Q，消息）：从进程Q接收一个消息 直接通信的实现在操作系统空间设置一组缓冲区。 当发送进程需要发送消息时，执行send系统调用，产生访管中断，进入操作系

33、统。 操作系统为发送进程分配一个空缓冲区，并将所发送的消息从发送进程copy到缓冲区中，然后将该载有消息的缓冲区连接到接收进程的消息链链尾，如此就完成了发送过程。 发送进程返回到用户态继续执行。,64,在以后某个时刻，当接收进程执行到receive接收原语时，也产生访管中断进入操作系统。 由操作系统将载有消息的缓冲区从消息链中取出，并把消息内容copy到接收进程空间，之后收回缓冲区，如此就完成了消息的接收。 接收进程返回到用户态继续进行。,65,2.间接通信的实现,Send实现 send（MailBox，M）：把信件M送到指定的信箱MailBox中 步骤： 查找指定信箱MailBox ； 若信箱未满，则把信件M送入信箱且唤醒“等信件”者； 若信箱已满置发送信件进程为“等信箱”状态；,66,Receive实现,receive（ MailBox ，X）：从指定信箱MailBox中取出一封信，存放到指定的地址X中 步骤： 查找指定信箱MailBox ； 若信箱有信，则取出一封信存于X中且唤醒“等信箱”者； 若信箱无信件则置接收信件进程“等信件”状态；,67,信箱的设置,私有信箱 设置在用户空间 设置在系统空间 公用信箱,