进程管理_12-16.ppt

1、2020/7/29,第二章 进程管理,1,进程的同步与通信,1 进程互斥 2 信号量和、操作 3 进程同步 4 经典的进程同步问题 5 进程通信 要求：掌握进程同步与互斥，灵活运用信号量描述同步与互斥问题。,2020/7/29,第二章 进程管理,2,1.1互斥的基本概念,与时间有关的错误: 飞机订票系统中，两个终端，运行T1、T2进程 T1 : T2: . . Read(x); Read(x); if x=1 then if x=1 then x:=x-1; x:=x-1; write(x); write(x); . .,2020/7/29,第二章 进程管理,3,同步：对于进程操作的时间顺序所

2、加的某种限制，如操作应在之前执行。 互斥：同步的特例，多个操作决不能同时执行， 如：操作和操作不能在同时执行。,2020/7/29,第二章 进程管理,4,临界资源(critical resource)：一次仅允许一个进程访问的资源。 临界资源可能是硬件，也可能是软件：变量，数据，表格，队列等。 并发进程对临界资源的访问必须作某种限制，否则就可能出与时间有关的错误，如：联网售票。,2020/7/29,第二章 进程管理,5,临界区(critical section)：临界段，在每个程序中，访问临界资源的那段程序。 注意：临界区是对某一临界资源而言的，对于不同临界资源的临界区，它们之间不存在互斥。

3、如有程序段A、B是关于变量X的临界区，而C、D是关于变量Y的临界区，那么，A、B之间需要互斥执行，C、D之间也要互斥执行，而A与C、B与D之间不用互斥执行。,2020/7/29,第二章 进程管理,6,解决互斥的准则,1、空闲让进 2、忙则等待 3、有限等待 4、让权等待,2020/7/29,第二章 进程管理,7,1.2 软件方法解决进程互斥,假如有两个进程Pi和Pj，它们共享一个临界资源R。 如何用软件方法使进程Pi和Pj能互斥地访问R。 下面介绍四个算法。,2020/7/29,第二章 进程管理,8,算法1,设整型变量turn，用于指示被允许进入临界区的进程的编号。 若turn=0 表示进程P

4、i可进入。 若turn=1 表示进程Pj可进入。,2020/7/29,第二章 进程管理,9,进程Pi : Repeat While turni do no_op; Critical section turn:=j; Other code Until false;,该算法可确保每次只允许一个进程进入临界区。 但它强制两个进程轮流进入。 如当Pi退出时将turn置为j，以便Pj能进入，但Pj暂不需要进入，而这时Pi又需要进入时，它无法进入。 违反：空闲让进,2020/7/29,第二章 进程管理,10,算法2,设var flag:array0.1 of boolean，flagi=true，表示进程

5、Pi正在临界区内。flagi=false，表示进程Pi不在临界区内。flagj=true，表示进程Pj正在临界区内。flagj=false，表示进程Pj不在临界区内。,2020/7/29,第二章 进程管理,11,Pi进程： Repeat While flag j do no_op; flagi:=true; Critical section flagi:=false; Other code Until false;,该算法可确保空闲让进。 但当pi和pj都未进入时，它们各自的访问标志都为false。如果pi和pj几乎同时要求进入，它们都发现对方的标志为false，于是都进入了。 问题在于：当进

6、程Pi观察到进程Pj的标志为false后，便将自己的标志由false改为true，而正是在这两步之间，可能发生进程切换。当Pj运行时，它会观察到Pi的标志为false，从而可以将自己的标志设为true，并进入临界区。,2020/7/29,第二章 进程管理,12,算法3,设var Flag:array0.1 of boolean， 若flagi=true，表示进程Pi希望进入临界区内。 若flagj=true，表示进程Pj希望进入临界区。,2020/7/29,第二章 进程管理,13,Pi进程： Repeat flagi:=true;/希望进入 While (flagj) do no_op; Cr

7、itical section flagi:=false; Other code Until false;,该算法又出现新问题。它可能造成谁也不能进入。如，当pi和pj几乎同时都要进入，分别把自己的标志置为true，都立即检查对方的标志，发现对方为true. 最终谁也不能进入。,2020/7/29,第二章 进程管理,14,算法4（正确算法）,组合算法1、3 为每一进程设标志位flagi， 当flagi=true时，表示进程pi要求进入，或正在临界区中执行。 再设一个变量turn，用于指示允许进入的进程编号。,2020/7/29,第二章 进程管理,15,进程为了进入先置flagi=true，并置t

8、urn为j，表示应轮到pj进入。 接着再判断flagj and turn=j的条件是否满足。若不满足则可进入。或者说，当flagj=false或者turn=i时，进程可以进入。前者表示pj未要求进入，后者表示仅允许pi进入。,2020/7/29,第二章 进程管理,16,算法4（正确算法）,Repeat flagi:=true; turn:=j; While (flagj and turn=j) do no_op; Critical section flagi:=false; Other code Until false,2020/7/29,第二章 进程管理,17,软件解法的缺点,1.忙等待 2

9、.实现过于复杂，需要较高的编程技巧,2020/7/29,第二章 进程管理,18,3 用原语实现进程互斥,锁即操作系统中的一标志位，表示资源可用，表示资源已被占用。 用户程序不能对锁直接操作，必须通过操作系统提供的上锁和开锁原语来操作。 通常锁用w表示，上锁开锁原语分别用lock(w)、unlock(w)来表示。,2020/7/29,第二章 进程管理,19,上锁和开锁原语,上锁原语lock(w)可描述为： L：if(w=1) goto L else w=1； 上述上锁原语中存在忙等待。 开锁原语unlock(w)可描述为： w=0；,2020/7/29,第二章 进程管理,20,用原语实现进程互斥

10、,2020/7/29,第二章 进程管理,21,改进的上锁原语,2020/7/29,第二章 进程管理,22,改进的开锁原语,2020/7/29,第二章 进程管理,23,1965年，由荷兰学者Dijkstra提出 （P、V分别是荷兰语的test (proberen) 和increment (verhogen) ） 一种卓有成效的进程同步机制 最初提出的是二元信号量（互斥） 后来推广到一般信号量（多值）（同步） P、V操作是原语,2 信号量及P、V操作,2020/7/29,第二章 进程管理,24,信号量：semaphore,是一个数据结构，定义如下： struct semaphore int val

11、ue; pointer_PCB queue; 信号量说明： semaphore s;,2020/7/29,第二章 进程管理,25,P操作,P(s) s.value = s.value -1 ; if (s.value 0) 该进程状态置为等待状态 将该进程的PCB插入相应的等待队列末尾s.queue; ,2020/7/29,第二章 进程管理,26,V操作,V(s) s.value = s.value +1; if (s.value = 0) 唤醒相应等待队列s.queue中等待的一个进程 改变其状态为就绪态 并将其插入就绪队列 ,2020/7/29,第二章 进程管理,27,必须置一次且只能置一

12、次初值 初值不能为负数 只能执行P、V操作,信号量的使用,2020/7/29,第二章 进程管理,28,进程互斥,用信号量实现临界区互斥 设置一信号量，信号量初值唯一， 进入临界区以前对信号量执行P操作， 退出临界区后对信号量执行V操作.,2020/7/29,第二章 进程管理,29,用P、V操作解决进程间互斥问题,2020/7/29,第二章 进程管理,30,信号量及P、V操作讨论,对两个并发进程，互斥信号量MUTEX仅取1、0和1三个值 若MUTEX1表示没有进程进入临界区 若MUTEX0表示有一个进程进入临界区 若MUTEX1表示一个进程进入临界区，另一个进程等待进入。,2020/7/29,第

13、二章 进程管理,31,1) 信号量的物理含义： S0表示有S个资源可用 S=0表示无资源可用 S0则| S |表示S等待队列中的进程个数 P(S)：表示申请一个资源 V(S)：表示释放一个资源。 信号量的初值应该大于等于0,信号量及P、V操作讨论,2020/7/29,第二章 进程管理,32,2) P.V操作必须成对出现，有一个P操作就一定有一个V操作 当为互斥操作时，它们同处于同一进程 当为同步操作时，则不在同一进程中出现 如果P(S1)和P(S2)两个操作在一起，那么P操作的顺序至关重要。 一个同步P操作与一个互斥P操作在一起时同步P操作在互斥P操作前 而两个V操作无关紧要,信号量及P、V操

14、作讨论,2020/7/29,第二章 进程管理,33,3）P、V操作的优缺点 优点： 简单，而且表达能力强 （用P、V操作可解决 任何同步互斥问题） 缺点： 不够安全，P、V操作使用不当会出现死锁； 遇到复杂同步互斥问题时实现复杂。,信号量及P、V操作讨论,2020/7/29,第二章 进程管理,34,3 进程同步,同步问题可分为两类： 保证一组合作进程按确定的次序执行 保证共享缓冲区的合作进程的同步。,2020/7/29,第二章 进程管理,35,合作进程的执行次序,若干个进程为了完成一个共同任务而并发执行，有些进程之间有次序的要求，有些进程之间没有次序的要求 为了描述方便，可以用一个图来表示进程

15、集合的执行次序。,2020/7/29,第二章 进程管理,36,例,如图，试用信号量实现这三个进程的同步。 设有两个信号量SB、SC，初值均为 Pa： Pb： Pc： P(SB); P(SC) V(SB); V(SC);,2020/7/29,第二章 进程管理,37,【思考题1】,如图，试用信号量实现这三个进程的同步。,2020/7/29,第二章 进程管理,38,解,设有两个信号量S1、S2，初值均为 P1： P2： P3： P(S1) V(S1); V(S2); P(S2) ,2020/7/29,第二章 进程管理,39,【思考题2】,如图，试用信号量实现这6个进程的同步,2020/7/29,第二

16、章 进程管理,40,解,设有5个信号量S2、S3、S4、S5、S6，初值均为 P1： P2： P3： P(S2); P(S3) V(S2); V(S3)； V(S4); V(S6); V(S5),P4： P5： P6： P(S4); P(S5); P(S6); P(S5); P(S6); V(S5)； V(S6);,2020/7/29,第二章 进程管理,41,【思考题】,用P.V操作解决司机与售票员的问题,2020/7/29,第二章 进程管理,42,解,设有两个信号量S1，S2，初值均为0。,2020/7/29,第二章 进程管理,43,共享缓冲区的进程的同步,设某计算进程CP和打印进程IOP共

17、用一个单缓冲区，CP进程负责不断地计算数据并送入缓冲区T中，IOP进程负责不断地从缓冲区T中取出数据去打印。,2020/7/29,第二章 进程管理,44,分析,通过分析可知，CP、IOP必须遵守以下同步规则： 当CP进程把计算结果送入缓冲区时，IOP进程才 能从缓冲区中取出结果去打印; 当IOP进程把缓冲区中的数据取出打印后，CP进程才能把下一个计算结果送入缓冲区,2020/7/29,第二章 进程管理,45,解,为此设有两个信号量Sa=0，Sb=1，Sa表示缓冲区中有无数据，Sb表示缓冲区中有无空位置。 两个进程的同步可以描述如下：,2020/7/29,第二章 进程管理,46,【思考题】,1.

18、用P.V操作解决下图之同步问题 提示：分别考虑对缓冲区S和T的同步，再合并考虑,2020/7/29,第二章 进程管理,47,解,设置四个信号量Sin=1，Sout=0，Tin=1，Tout=0；,get： while（1） P(Sin）; 将数放入S; V(Sout); ,copy： while（1） P(Sout）; P(Tin）; 将数从S取出放入T; V(Tout); V(Sin); ,put： while（1） P(Tout）; 将数从T取走; V(Tin); ,2020/7/29,第二章 进程管理,48,【思考题】,桌上有一空盘，最多允许存放一只水果。爸爸可向盘中放一个苹果或放一个桔

19、子，儿子专等吃盘中的桔子，女儿专等吃苹果。 试用P、V操作实现爸爸、儿子、女儿三个并发进程的同步。 提示：设置一个信号量表示可否向盘中放水果，一个信号量表示可否取桔子，一个信号量表示可否取苹果。,2020/7/29,第二章 进程管理,49,解,设置三个信号量S,So,Sa ，初值分别为1，0，0。分别表示可否向盘中放水果，可否取桔子，可否取苹果。,2020/7/29,第二章 进程管理,50,2020/7/29,第二章 进程管理,51,2.4 经典的进程同步问题,4.1 生产者/消费者问题 4.2 读者/写者问题 4.3 哲学家进餐问题,2020/7/29,第二章 进程管理,52,2.4.1 生

20、产者/消费者问题,是一种同步问题的抽象描述。 计算机系统中的每个进程都可以消费（使用）或生产（释放）某类资源。这些资源可以是硬件资源，也可以是软件资源。 当某一进程使用某一资源时，可以看作是消费，称该进程为消费者。 而当某一进程释放某一资源时，它就相当于生产者。,2020/7/29,第二章 进程管理,53,问题描述,通过一个有界缓冲区把一群生产者P1,P2,Pm，和一群消费者Q1,Q2, Qn联系起来。 只要缓冲区未满，生产者就可以把产品送入缓冲区; 只要缓冲区未空，消费者就可以从缓冲区中取走物品。,2020/7/29,第二章 进程管理,54,图,2020/7/29,第二章 进程管理,55,问

21、题分析,用一个数组来表示具有n个(0，1，n-1)缓冲区的缓冲池 设两个同步信号量， 一个说明空缓冲区的数目，用S1表示，初值为有界缓冲区的大小N， 另一个说明已用缓冲区的数目，用S2表示，初值为。 M个生产者和N个消费者对有界缓冲区操作。 有界缓冲区是一个临界资源，必须互斥使用，设置一个互斥信号量mutex，初值为。,2020/7/29,第二章 进程管理,56,问题的基本解,Q： j = 0;输出指针 while (1) P(S2); P(mutex); 从Bufferj取产品; j = (j+1) % n; V(mutex); V(S1); 消费产品; ;,P：i = 0;输入指针whil

22、e (1) 生产产品; P(S1); P(mutex); 往Buffer i放产品; i = (i+1) % n; V(mutex); V(S2); ;,2020/7/29,第二章 进程管理,57,【思考题】,有一个仓库，可以存放A和B两种产品，但要求： （1） 每次只能存入一种产品（A或B） （2） NA产品数量B产品数量M。 其中，N和M是正整数。试用P、V操作描述产品A与B的入库过程。 提示：设两个信号量Sa、Sb Sa表示允许A产品比B产品多入库的数量 Sb表示允许B产品比A产品多入库的数量,2020/7/29,第二章 进程管理,58,解,设两个信号量Sa、Sb，初值分别为M-1，N-

23、1 Sa表示允许A产品比B产品多入库的数量 Sb表示允许B产品比A产品多入库的数量 设互斥信号量mutex，初值为1。,2020/7/29,第二章 进程管理,59,B产品入库进程： while (1) P(Sb); P(mutex); B产品入库 V(mutex); V(Sa); 消费产品; ;,A产品入库进程：while (1) 生产产品; P(Sa); P(mutex); A产品入库 V(mutex); V(Sb); ;,2020/7/29,第二章 进程管理,60,2.4.3 读者/写者问题,有两组并发进程: 读者和写者,共享一组数据区 要求： 允许多个读者同时执行读操作 不允许读者、写者

24、同时操作 不允许多个写者同时操作,2020/7/29,第二章 进程管理,61,第一类：读者优先,如果读者来： 1）无读者、写者，新读者可以读 2）有写者等，但有其它读者正在读，则新读者也可以读 3）有写者写，新读者等 如果写者来： 1）无读者，新写者可以写 2）有读者，新写者等待 3）有其它写者，新写者等待,2020/7/29,第二章 进程管理,62,第一类读者写者问题的解法,设两个信号量w=1，mutex=1 设一个全局变量readcount =0 w用于读者和写者、写者和写者之间的互斥 readcount表示正在读的读者数目 mutex用于对readcount 这个临界资源的互斥访问,20

25、20/7/29,第二章 进程管理,63,读者： while (1) P(mutex); readcount +; if (readcount=1) P (w); V(mutex); 读 P(mutex); readcount -; if (readcount=0) V(w); V(mutex); ;,写者： while (1) P(w); 写 V(w); ;,2020/7/29,第二章 进程管理,64,【思考题】写优先,修改以上读者写者问题的算法，使之对写者优先，即一旦有写者到达，后续的读者必须必须等待，无论是否有读者在读。 提示，增加一个信号量，用于在写者到达后封锁后续的读者,2020/7/

26、29,第二章 进程管理,65,解 增加一个信号量s，初值为1,读者： while (1) P(s); P(mutex); readcount +; if (readcount=1) P (w); V(mutex); V(s); 读 P(mutex); readcount - -; if (readcount=0) V(w); V(mutex); ;,写者： while (1) P(s); P(w); 写 V(w); V(s); ;,2020/7/29,第二章 进程管理,66,2.4.2 哲学家就餐问题,有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子

27、每个哲学家的行为是思考，感到饥饿，然后吃通心粉 为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子,2020/7/29,第二章 进程管理,67,设fork5为5 个信号量，初值为均1 Philosopheri： while (1) 思考； P(forki); P(fork(i+1) % 5)； 进食； V(forki); V(fork(i+1) % 5)； ,试解,2020/7/29,第二章 进程管理,68,以上解法会出现僵局 为防止死锁发生可采取的措施： 最多允许4个哲学家同时坐在桌子周围 仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子（） 给所有哲

28、学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之,分析,2020/7/29,第二章 进程管理,69,使用一个状态数组state来跟踪一个哲学家是在吃饭、思考还是正在试图拿筷子。 一个哲学家只有在两个邻居都不在进餐时才允许转移到进餐状态。 第i位哲学家的邻居由宏LEFT和RIGHT定义，换言之，若i为2，则LEFT为1，RIGHT为3。,2020/7/29,第二章 进程管理,70,信号量集AND型信号量集,AND型信号量集是指同时需要多种资源且每种占用一个时的信号量操作 AND型信号量集的基本思想：在一个原语中申请整段代码需要的多个临界资源，要么全部分配给它，要么一个都不分配

29、AND型信号量集P原语为Swait AND型信号量集V原语为Ssignal,2020/7/29,第二章 进程管理,71,Swait(S1, S2, , Sn)/P原语； while (TRUE) if (S1 =1 ,2020/7/29,第二章 进程管理,72,Ssignal(S1, S2, , Sn) for (i = 1; i = n; +i) +Si;/释放占用的资源； for (在Si.queue中等待的每一个进程P) /检查每种资源的等待队列的所有进程； 从等待队列Si.queue中取出进程P;,2020/7/29,第二章 进程管理,73,if (判断进程P是否通过Swait中的测试

30、) /注：与signal不同，这里要进行重新判断； /通过检查（资源够用）时的处理； 进程P进入就绪队列; else /未通过检查（资源不够用）时的处理； 进程P进入某等待队列； ,2020/7/29,第二章 进程管理,74,一般“信号量集”,一般信号量集是指同时需要多种资源、每种占用的数目不同、且可分配的资源还存在一个临界值时的信号量处理 一般信号量集的基本思路就是在AND型信号量集的基础上进行扩充，在一次原语操作中完成所有的资源申请。,2020/7/29,第二章 进程管理,75,进程对信号量Si的 测试值为ti（表示信号量的判断条件，要求当资源数量低于ti时，便不予分配） 占用值为di（表

31、示对资源i的申请量） 对应的P、V原语格式为： Swait(S1, t1, d1; .; Sn, tn, dn); Ssignal(S1, d1; .; Sn, dn); 思考: 用于解决哲学家问题,2020/7/29,第二章 进程管理,76,一般“信号量集”可以用于各种情况的资源分配和释放，几种特殊情况：,Swait(S, d, d)表示每次申请d个资源，当少于d个时，便不分配 Swait(S, 1, 1)表示互斥信号量 Swait(S, 1, 0)可作为一个可控开关（当S1时，允许多个进程进入临界区；当S=0时，禁止任何进程进入临界区）,2020/7/29,第二章 进程管理,77,2.5管

32、程机制,Hoare（1974）和Brinch Hansen（1975）提出了一种高级的同步原语，称为管程( monitor )。 一个管程是一个由过程、变量及数据结构等组成的一个集合，它们组成一个特殊的模块或软件包。 进程可在任何需要的时候调用管程中的过程，但它们不能在管程外的过程中直接访问管程内的数据结构。,2020/7/29,第二章 进程管理,78,在OS中引入管程的目的是为了更简便、更可靠地解决进程之间的同步、互斥问题。 在未引入管程之间，进程间的同步、互斥问题是由程序员处理的。例如，在临界区的前后插入P、V操作。 但是，由程序员处理同步、互斥问题有可能引入种种人为的错误。 管程主要是管理对共享数据的操作和使用，即把对共享数据互斥使用的控制这一任务从程序员身上，交由编译程序去处理，这样既方便了编程，又不会产生人为的同步、互斥上的错误。,2020/7/29,第二章 进程管理,79,管程机制,管程有一个很重要的特性，任一时刻管程中只能有一个活跃进程。 使管程能有效地完成互斥，只要把临界区代码放在管程中即可。 管程提供了一种实现互斥的简便途径，但这还不够，还需要一种办法以使得进程在无法继续运行时被阻塞。 例如，在生产者消费者问题中，很容易将针对缓冲区满和缓冲区空的测试放到管程的过程中，但是生产者在发现缓冲区满的时