chp02-进程同步章进程的描述与控制

1、第2章 进程的描述与控制主讲教师：高俊涛 目录前趋图和程序执行进程的描述进程控制进程通信进程同步经典进程的同步问题线程的基本概念线程的实现进程同步： 指对多个相关进程在执行次序上的协调。这些进程相互合作，在一些关键点上可能需要互相等待或互通消息。进程同步的主要任务： 使并发执行的诸进程间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。进程同步的基本概念 进程同步的基本概念 1、两种形式的制约关系（并发进程间的关系） * 资源共享关系 * 相互合作关系（间接相互制约）（直接相互制约） 进程间彼此无关，进程同步要确保诸进程互斥的访问临界资源。 进程间存在先后次序关系，进程同步要确保诸进程

2、在执行次序上的协调，时间上无差错。2、临界资源 一段时间内只允许一个进程访问的资源；临界资源要求互斥的被访问。实例 ：生产者消费者问题进程同步的基本概念 实例 ：生产者消费者问题同步规则 ： 不允许消费者进程到一个空缓冲区去取消息； 也不允许生产者进程向一个已装有消息且尚未取走消息的缓冲池投放消息。producerconsumer进程同步的基本概念 实例 ：生产者消费者问题解决方案 ： 1）数组buffer，表示具有n个缓冲区的缓冲池； 输入指针in，指示下一个可投放消息的缓冲区； 输出指针out，指示下一个可获取消息的缓冲区。2）采用循环缓冲方式： 投放消息时：in=(in+1) mod n

3、 获取消息时：out=(out+1) mod n 缓冲池空： in = out 缓冲池满： (in +1) mod n = out3）引入整形变量counter,表示当前缓冲中的消息数： 投放消息时： counter = counter + 1 获取消息时： counter = counter - 1进程同步的基本概念 生产者/消费者问题的有界循环缓冲进程同步的基本概念 producer: repeat produce an item in nextp; while counter=n do no-op; buffer in: = nextp; in: = in+1 mod n; counte

4、r: = counter+1; until false;consumer: repeat while counter=0 do no-op; nextc: = buffer out; out: = (out+1) mod n; counter: = counter-1; consumer the item in nextc; until false; Var n, integer;type item=;var buffer: array0, 1, , n-1 of item;in, out: 0, 1, , n-1;counter: 0, 1, , n;进程同步的基本概念 生产者程序和消费者程

5、序都是正确的，而且顺序执行时其结果也是正确的。 但在并发执行时，就会出现差错，问题就在于这两个进程共享变量counter。程序执行时，可简化描述如下：register1:=counter; register2:=counter; register1:=register1+1; register2:=register2-1; counter: =register1; counter:=register2; 进程同步的基本概念 假设：counter的当前值是5，如采用顺序执行方式，则最后共享变量counter的值仍为5；如采用并发执行方式，则可能出现下列执行顺序和结果：counter值是4 reg

6、ister 1 =counter; (register 1=5) register 1 =register 1+1; (register 1=6) register 2 =counter; (register 2=5) register 2 =register 2-1; (register 2=4) counter =register 1; (counter=6) counter =register 2; (counter=4) 进程同步的基本概念 实例 ：生产者消费者问题存在问题 ： 相同次数的输入/输出操作中，由于程序段执行的次序不同，所得到counter的值不同，偏离正确值，出错。可得结

7、论 ： 变量counter应作为临界资源，应互斥的访问。进程同步的基本概念 3、临界区* 临界区的定义 各进程中访问临界资源的程序代码称为临界区。Repeat entry section（进入区） critical section（临界区） exit section（退出区） remainder section（剩余区）until false进程同步的基本概念 4、同步机制应遵循的准则空闲让进：忙则等待：有限等待：让权等待：“死等”“忙等”进程同步的基本概念 Critical-Section Problem两进程解法两个进程标为P0和P1，为了方便，当使用Pi时，用Pj来表示另一个进程；即j

8、= 1 i算法1进程共享一普通整数变量turn，其初值为0（或1）如果turn = i, Pi允许在其临界区内执行。Shared variables: int turn; / initially turn = 0turn = i; / Pi can enter its critical sectionProcess Pido while (turn != i) ;critical sectionturn = j;reminder section while (1);满足互斥，但不满足空闲让进。算法2布尔标志flag用来表示线程它准备进入其临界区Shared variablesboolean f

9、lag2; / initially flag0 = flag1 = false.flag i = true; / Intention: Pi ready to enter its critical sectionProcess Pido flagi = true;while (flagj) ;critical sectionflag i = false;remainder section while (1);满足互斥，但不满足空闲让进。算法21. do 2. flagi = true;3. while (flagj) ; /进入区4. 临界区5. flagi = false; /退出区6. 剩

10、余区7. while (1);将语句2与语句3的位置互换，又将如何？不满足互斥和忙则等待。算法3结合算法1与算法2的思想是否满足临界区的要求？do flagi = true;turn = j;while (flagj & turn = j) ; /进入区临界区flagi = false; /退出区剩余区 while (1);多进程解法面包店算法的思想：该算法的基本思想源于顾客在面包店中购买面包时的排队原理. 顾客在进入面包店前, 首先抓一个号, 然后按照号码由小到大的次序依次进入面包店购买面包. 这里, 面包店发放的号码是由小到大的, 但是两个或两个以上的顾客却有可能得到相同的号码(使所抓号码

11、不同需要互斥), 如果多个顾客抓到相同的号码, 则规定按照顾客名字的字典次序进行排序, 这里假定顾客是没有重名的. 在计算机系统中, 顾客就相当于进程, 每个进程有一个唯一的标识, 我们用P的下面加一个下标来表示. 例如: 对于 Pi和Pj, 如果有ij, 则先为Pi服务, 即Pi先进入临界区。多进程解法实现boolean choosingn;int numbern; 前者表示进程是否正在抓号，正在抓号的进程choosingi为true，否则为false, 其初值均为false. 后者用来记录各个进程所抓到的号码, 如numberi为0, 则进程Pi没有抓号, 如numberi不为0, 则其正

12、整数值为进程Pi所抓到的号码, 其初值均为0.定义：(a,b)(c,d) 如果 ac or (a=c and bd). max(a0,an-1) 其值为一正整数k, 对于所有i, 0in-1, kai 算法见下页 do choosingi = true;numberi = max(number0, number1, , numbern-1) + 1;choosingi = false;for (j = 0; j n; j +) while (choosingj) ;while (numberj != 0) & (numberj, j) =0，则进程继续运行； 若S 0，则进程继续运行； 若S=

13、0，则从该信号量的等待队列中移出一个进程，使其变为就绪态，然后，再返回原进程继续执行；Signal：（S）操作信号量机制P、V操作的定义例：网络访问人数计数程序。 S=1定义信号量，初值为1P（S）Wait（S）Application(“Counter”)= Application(“Counter”)+1V（S）Signal（S）信号量机制P、V操作的定义 为使多个进程能互斥地访问某临界资源，只需为该资源设置一互斥信号量mutex，并设其初始值为； 然后将各进程的临界区（）置于wait(mutex)和signal(mutex)操作之间。 但，在利用信号量机制实现进程互斥时，wait和sign

14、al必须成对地出现。信号量机制整型信号量例：var mutex:semaphore:=1beginrepeatwait(mutex)；critical section；signal(mutex) ；remainder section ；until false ；end临界区，访问临界资源定义信号量信号量机制整型信号量整型信号量机制： 未遵循“让权等待”的准则； 进程可能处于“忙等”的状态。记录型信号量机制： 整型变量value：代表资源数目； 进程链表指针L：链接等待该资源的进程。信号量机制记录型信号量procedure wait(S) var S: semaphore; begin S.va

15、lue:=S.value-1; if S.value0 then block(S,L) endprocedure signal(S) var S: semaphore; begin S.value: =S.value+1; if S.value0 then wakeup(S,L); end type semaphore=record value:integer; L:list of process; end信号量机制记录型信号量 （1）S.value的初值表示系统中某类资源的数目， 因而又称为资源信号量，每次wait操作意味着进程请求一个单位的该类资源，S.value:=S.value-1 。

16、 （2）当S.value0时，进程自阻塞，S.value的绝对值表示在该信号量链表中已阻塞进程的数目。 （3）该机制遵循了“让权等待”准则。 （4）如果S.value的初值为1，表示只允许一个进程访问临界资源，此时的信号量转化为互斥信号量。 信号量机制记录型信号量process A: process B:Wait (Dmutex); wait (Emutex);Wait (Emutex); wait (Dmutex); 假设：进程A、B均需要共享数据D、E，则两个进程中资源申请程序段如下：A、B执行操作可能为：process A: wait(Dmutex); 于是Dmutex=0process

17、 B: wait(Emutex); 于是Emutex=0process A: wait(Emutex); 于是Emutex=-1 A阻塞process B: wait(Dmutex); 于是Dmutex=-1 B阻塞 信号量机制AND型信号量AND同步机制的基本思想是: （1）将进程所有资源，一次性地全部分配给进程或者回收。 （2）采取原子操作方式：要么全部分配到进程，要么一个也不分配。 （3）在wait操作中，增加了一个“AND”条件，故称为AND同步，或称为同时wait操作。信号量机制AND型信号量避免请求保持条件，防止系统的不安全性。Wait(S1,S2,Sn )if S11 and S

18、n1 thenfor i:=1 to n doSi:=Si-1;endforelse(block ) endifSignal(S1,S2,Sn )for i:=1 to n doSi:=Si+1;(wakeup)endfor信号量机制AND型信号量Ssignal(S1, S2, , Sn) for i:=1 to n do Si=Si+1; Remove all the process waiting in the queue associated with Si into the ready queue. endfor; Swait(S1, S2, , Sn) if Si1 and and

19、Sn1 then for i: =1 to n do Si:=Si-1; endfor else Place the process in the waiting queue associated with the first Si found with Si1, and set the program count of this process to the beginning of Swait operation endif信号量机制AND型信号量 （1）在记录型信号量机制中，每次只能获得或释放一个单位的临界资源。因此，当一次需个某类临界资源时，便需要次wait操作，显然这是低效的。 （2

20、）在有些情况下，当资源数量低于某一下限值时，便不予以分配。因此，在每次分配之前，都必须测试该资源的数量是否大于测试值。 （3）基于上述两点，可以对AND信号量机制进行扩充，形成一般化的“信号量集”机制。信号量机制信号量集Swait(S1, t1, d1, , Sn, tn, dn) if Sit1 and and Sntn then for i=1 to n do Si=Si-di; endfor else Place the executing process in the waiting queue of the first Si with Siti and set its program

21、 counter to the beginning of the Swait Operation. (block ) endifsignal(S1, d1, , Sn, dn) for i：=1 to n do Si ：=Si+di;Remove all the process waiting in the queue associated with Si into the ready queue。 (wakeup) endfor; S为信号量, t为下限值, d为需求量信号量机制信号量集一般“信号量集”的几种特殊情况： (1) Swait(S, d, d)。 此时在信号量集中只有一个信号量S

22、， 但允许它每次申请d个资源，当现有资源数少于d时，不予分配。 (2) Swait(S, 1, 1)。 此时的信号量集已蜕化为一般的记录型信号量(S1时)或互斥信号量(S=1时)。 (3) Swait(S, 1, 0)。这是一种很特殊且很有用的信号量操作。当S1时，允许多个进程进入某特定区；当S变为0后，将阻止任何进程进入特定区。换言之，它相当于一个可控开关。 信号量机制信号量集1、利用信号量实现进程互斥 Var mutex:semaphore: =1;begin parbegin process 1: begin repeat wait(mutex); critical section si

23、gnal(mutex); remainder section until false;end process 2: begin repeat wait(mutex); critical section signal(mutex); remainder section until false; endparend end信号量机制信号量的应用 Var a,b,c,d,e,f,g; semaphore：=0,0,0,0,0,0,0; begin parbegin begin S1; signal(a); signal(b); end; begin wait(a); S2; signal(c); s

24、ignal(d); end; begin wait(b); S3; signal(e); end; begin wait(c); S4; signal(f); end; begin wait(d); S5; signal(g); end; begin wait(e); wait(f); wait(g); S6; end; parend end 2、利用信号量实现前趋关系 图 2-12 前趋图举例 S4S5S3S1S6S2信号量机制信号量的应用1）信号量可能存在的问题 * 临界区的执行分散在各进程中，不便于系统对控制和管理。 * 很难发现和纠正分散在用户程序中的对同步原语的错误使用。2）解决问题

25、的可能措施 * 把分散的各同类临界资源集中起来，统一管理。 * 为每个共享资源设立一个专门程序，来统一管理各进程对资源的访问。3）达到的可能结果 * 既便于系统管理共享资源，又能保证互斥访问。管程机制1、管程的基本思想 * 系统中各种硬件资源和软件资源，均采用数据结构加以抽象的描述，即用少量信息和对该资源所执行的操作来表征资源，而忽略它们的内部结构和实现细节。 * 资源管理程序可用对该数据结构进行操作的一组过程表示，并实现对资源的管理。2、管程的定义 * 把表征某种资源的一个数据结构和实现资源管理的相关过程一并称为管程。管程机制2、管程的定义 * 把表征某种资源的一个数据结构和实现资源管理的相

26、关过程一并称为管程。 * 即：一个管程定义了一个数据结构和能为并发进程所执行的一组操作，这组操作能同步进程和改变管程中的数据。 在该数据结构上使进程同步互斥共享资源资源状态分配参数使用状况管程机制图 2-13 管程的示意图 3、管程的组成 type monitor-name=monitor variable declarations procedure entry P1(); begin end; procedure entry P2(); begin end; procedure entry Pn(); begin end; begin initialization code; end 管程

27、的语法如下：共享数据一组操作过程初始化代码进入队列条件(不忙)队列管程机制4、条件变量 引入： 区分不同原因造成的等待； 形式： var x,y:condition ； 引用： x.wait x.signal； 注意： x.signal操作的作用是重新启动一个被阻塞的进程。假如没有阻塞进程，则不起作用。 x.signal与信号量机制中的signal操作不同。 管程机制目录前趋图和程序执行进程的描述进程控制进程通信进程同步经典进程的同步问题线程的基本概念线程的实现 未考虑进程的互斥与同步问题，因而造成了数据Counter的不确定性。 生产者消费者问题是相互合作的进程关系的一种抽象，有很大的代表性

28、及实用价值。 生产者消费者问题 1、利用记录型信号量解决生产者消费者问题 （1）设公用缓冲池，具有n个缓冲区； （2）利用互斥信号量mutex实现对缓冲池的互斥使用； （3）资源信号量empty和full分别表示空缓冲区和满缓冲区的数量。 （4）只要缓冲池未满，生产者便可将消息送入缓冲池； （5）只要缓冲池未空，消费者便可从池中取走一个消息。同步规则 ：（4）（5）生产者消费者问题 begin parbegin proceducer:begin repeat producer an item nextp; wait(empty); wait(mutex); buffer(in):=nextp;

29、 in:= (in+1) mod n; signal(mutex); signal(full); until false; endconsumer:begin repeat wait(full); wait(mutex); nextc:=buffer(out); out:= (out+1) mod n; signal(mutex); signal(empty); consumer the item in nextc; until false; end parend end Var mutex, empty, full:semaphore: = 1,n,0; buffer:array0, , n

30、-1 of item; in, out: integer: = 0, 0;生产者消费者问题在生产者消费者问题中应特别注意： （1）实现互斥的wait(mutex)和signal(mutex)必须成对地出现； （2）对资源信号量empty和full的wait和signal操作，同样需要成对地出现，但它们分别处于不同的程序中。 （3）多个wait操作顺序不能颠倒。应先执行对资源信号量的wait操作，然后再执行对互斥信号量的wait操作，否则可能引起进程死锁。生产者消费者问题 begin parbegin producer:begin repeat produce an item in nextp;

31、 Swait(empty, mutex); buffer(in)： = nextp; in：= (in+1)mod n; Ssignal(mutex, full); until false; end2、利用AND信号量解决生产者消费者问题 Var mutex, empty, full:semaphore: = 1, n, 0; buffer:array0, , n-1 of item; in out:integer: = 0, 0;consumer:begin repeat Swait(full, mutex); nextc： = buffer(out); out： = (out+1) mod

32、 n; Ssignal(mutex, empty); consumer the item in nextc; until false; end parend end 生产者消费者问题3、利用管程解决生产者-消费者问题 建立管程Proclucer-Consumer, 简称为PC，包括两个过程： (1) put(item)过程：生产者利用该过程将自己生产的产品投放到缓冲池中， 并用整型变量count来表示在缓冲池中已有的产品数目，当countn时，表示缓冲池已满，生产者须等待。 (2) get(item)过程：消费者利用该过程从缓冲池中取出一个产品，当count0时，表示缓冲池中已无可取用的产品，

33、 消费者应等待。 生产者消费者问题procedure entry put(item) begin if countn then notfull.wait; buffer(in): = nextp; in: = (in+1) mod n; count: = count+1; if notempty.queue then notempty.signal; endtype producer-consumer=monitor Var in,out,count:integer; buffer:array0,n-1 of item; notfull, notempty:condition;procedur

34、e entry get(item) begin if count0 then notempty.wait; nextc:=buffer(out); out:= (out+1) mod n; count:=count-1; if notfull.quene then notfull.signal; end begin in:=out:=0; count=0 end 生产者消费者问题 producer: begin repeat produce an item in nextp; PC.put(item); until false; end consumer: begin repeat PC.ge

35、t(item); consume the item in nextc; until false; end 生产者消费者问题 * 五个哲学家生活方式交替的进行思考和进餐；相邻两个哲学家只能有一个哲学家用餐。 * 共用一张园桌，分别座在五把椅子上；圆桌上有五个碗和五支筷子（临界资源）。 * 平时一个哲学家进行思考，饥饿时取左右两个筷子进餐。哲学家进餐问题1、利用记录型信号量解决哲学家进餐问题 （1）筷子是临界资源； （2）用一个信号量表示一只筷子；五个信号量构成信号量数组： Var chopstick: array0, , 4 of semaphore; 所有信号量均被初始化为1，表示只有1只筷子

36、，同时起到互斥信号量和资源信号量作用。哲学家进餐问题第i位哲学家的活动可描述为: repeat wait(chopsticki); wait(chopstick(i+1) mod 5); eat; signal(chopsticki); signal(chopstick(i+1) mod 5); think; until false; 可能导致死锁哲学家进餐问题解决可能发生死锁的方法： (1) 至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐。 (2) 仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐。 (3) 规定奇数号哲学家先拿他左边的筷子，然后再去拿右

37、边的筷子；而偶数号哲学家则相反。 哲学家进餐问题2、利用AND信号量机制解决哲学家进餐问题Var chopsiick array 0, , 4 of semaphore: = (1,1,1,1,1); processi repeat think; Sswait(chopstick(i+1) mod 5, chopstick i); eat; Ssignat(chopstick (i+1) mod 5, chopstick i); until false; 哲学家进餐问题Shared data semaphore chopstick5 = 1, 1, 1, 1, 1;/ One chopstic

38、k can only be picked up / by one philosophersemaphore coord = 4;/ Only four philosophers can try to eat/ simultaneously 哲学家进餐问题Philosopher i:do wait(coord);wait(chopsticki)wait(chopstick(i+1) % 5) eat signal(chopsticki);signal(chopstick(i+1) % 5);signal(coord); think while (1);哲学家进餐问题monitor dp enum

39、 thinking, hungry, eating state5;condition self5;void pickup(int i) / following slidesvoid putdown(int i) / following slidesvoid test(int i) / following slidesvoid init() for (int i = 0; i 5; i+)statei = thinking;哲学家进餐问题管程void test(int i) if ( (state(i + 4) % 5 != eating) & (statei = hungry) & (stat

40、e(i + 1) % 5 != eating) statei = eating;selfi.signal();哲学家进餐问题管程void pickup(int i) statei = hungry;testi;if (statei != eating)selfi.wait();void putdown(int i) statei = thinking;/ test left and right neighborstest(i+4) % 5);test(i+1) % 5);哲学家进餐问题管程Philosopher(i)dp.pickup(i);eat, eat, eatdp.putdown(i)

41、哲学家进餐问题管程1）同步规则： * 保证一个write进程必须与其它进程互斥地访问共享对象的同步问题。 * 允许多个进程同时读一个共享对象； * 但，绝不允许一个write进程和其它读进程或写进程同时访问共享文件。 1、利用记录型信号量解决读者-写者问题读者写者问题2）解决方案： * 为实现reader进程和write进程读或写时的互斥，设置互斥信号量wmutex； * 因为readcount可能被多个readcount进程访问，设置互斥信号量rmutex ； * 整型信号量readcount表示正在读的进程数目； * 仅当redacount=0时才可以写。 1、利用记录型信号量解决读者-写

42、者问题读者写者问题 begin parbegin Reader:begin repeat wait(rmutex); if readcount=0 then wait(wmutex); Readcount: = Readcount+1; signal(rmutex); perform read operation; wait(rmutex); readcount: = readcount-1; if readcount=0 then signal(wmutex); signal(rmutex); until false; end读者优先：Var rmutex, wmutex:semaphore

43、:=1,1; Readcount:integer: =0; writer:begin repeat wait(wmutex); perform write operation; signal(wmutex); until false; end parend end 读者写者问题Reader:begin Wait(Mut1); Signal(Mut1); Wait(Mut2); Rcount:=Rcount+1; IfRcount=1thenWait(Fmutex); Signal(Mut2); 读操作； Wait(Mut2); Rcount:=Rcount-1; IfRcount=0thenSignal(Fmutex); Singal(Mut2); end写者优先：Writer:begin Wait(Mut1);Wcount:=Wcount+1；IfWcount=1then Wait(Fmutex);Signal(Mut1);Wait(WMutex); 写操作；Signal(Wmutex);Wait(Mut1);Wcount:=Wcount-1;IfWcount=0then Signal(Fmutex);Signal(Mut1); end 读者写者问题Var Mut