第五讲进程同步和通信（partII）

1、第五讲第五讲 进程同步和通信（进程同步和通信（part II）中国科学技术大学计算机系中国科学技术大学计算机系 陈香兰陈香兰2013Fall内容提要内容提要v进程同步问题的来由和进程同步的主要任务v临界资源和临界区v2任务的进程互斥问题的解决方案v信号量Semaphores v死锁和饿死现象v经典同步问题v管程v进程间通信内容提要内容提要v进程同步问题的来由和进程同步的主要任务v临界资源和临界区v2任务的进程互斥问题的解决方案v信号量信号量Semaphores v死锁和饿死现象v经典同步问题v管程v进程间通信信号量机制信号量机制 SemaphorevReading计算机操作系统，汤子瀛，3.2

2、节Operating System Concepts，7th edition，section6.5 P200信号量机制信号量机制v整型信号量v记录型信号量v信号量集整型信号量整型信号量v The real situation may be more complex v Semaphore S integer variablev Can only be accessed via two indivisible (atomic) operations: Proberen & Verhogen (Dutch)P(S): while S 0 do no-op;S-;V(S): S+;P：又称为

3、：又称为wait操作操作V：又称为：又称为signal操作操作Counting & binary semaphorev Counting semaphore (资源信号量） Used to control access to a given resource consisting of only a finite number 0,nv Binary semaphore (二进制信号量或互斥信号量，mutex) 0 or 1 Used to control access to the CSGenerally using counting semaphorev Shared semaph

4、ore semaphore resources; /* initially resources = n */v Pi:do P( resources );Critical section;V( resources );Remainder section; while(1);Generally using binary semaphorev Shared semaphore semaphore mutex; /* initially mutex = 1 */v Pi: /利用信号量实现互斥do P( mutex );Critical section;V( mutex );Remainder se

5、ction; while(1);v What is the different between these two?Another common examplev E.g.: Pi has code segment A Pj has code segment B A must be executed before B Solution Using semaphoresemaphore finish; / Initialize finish = 0PiPjAV(flag)P(flag)B利用信号量进行同步；利用信号量进行同步；可以描述前驱关系可以描述前驱关系同步举例（前驱举例）同步举例（前驱举例

6、）semaphore a,b,c,d,e,f,g = 0,0,0,0,0,0,0begin parbegin begin S1;signal(a);signal(b);end; begin wait(a);S2;signal(c);signal(d);end; begin wait(b);S3;signal(g);end; begin wait(c);S4;signal(e);end; begin wait(d);S5;signal(f);end; begin wait(e);wait(f);wait(g);S6;end; parendendS1S2S3S4S5S6abcdgef忙等问题忙等问

7、题v Busy-Waiting So far, all solutions have this common problem Entry section, always loop if l Wastes CPU cyclel Still in ready state and participate in scheduling These kind of semaphore is also called a spinlock Spinlock, is useful in some casesv Solution: Instead of busy-waiting (loop), it just b

8、locks itself, when must waitRecord semaphore记录型信号量记录型信号量v Define semaphore as a recordtypedef struct int value;struct process *L; /等待队列等待队列 semaphore;v Use two system call: blockl The state of the process is switched to the waiting state, and then the control CPU scheduler; wakeupl Changes the proce

9、ss from the waiting state to the ready state, and places it to ready queue汤子瀛，汤子瀛，2版版 & 汤小丹，汤小丹，3版版procedure wait(S)var S: semaphore;beginS.value:=S.value-1;if S.value0 then block(S.L);endprocedure signal(S)var S: semaphorebeginS.value:=S.value+1;if(S.value0) then wakeup(S.L);endv Type semaphore

10、record value: integer; L: List of process; end;分析分析S.value对于wait操作，v 开始时： 当value1时，说明有资源剩余；只需要减1 当value1时，说明没有资源剩余；减去1，并等待v 结束时： value 0，说明没有等待者 value0，说明有等待者，此时L上有等待进程；此时，此时，value的的绝对值表示等待进程的个数绝对值表示等待进程的个数对于signal操作，v 开始时，同wait结束时 value 0，说明没有等待者，不必唤醒，只需要加1 value0，说明有等待者；加1，并唤醒1个进程Operating system

11、concepts, 7thv P(S)S.value-;If (S.value0: number of remaining resourcesv S.value 0: number of waiting processesv V(S)S.value+;If (S.value0=0GOT!0L=NULL=00Failed!0=0L!=NULLImplementation of semaphorev 临界区问题: No two processes can execute P/V operation on the same semaphore at the same timev Two ways U

12、niprocessorl Disable interrupt during P/V Multiprocessorl Software solutionsl Hardware instructionsMisuse of semaphorev E.g.:Process P0, & P1Semaphore S & Q, both initially = 1;P0P1P(S)P(Q).V(S)V(Q)P(Q)P(S).V(Q)V(S)blockblockAND型信号量型信号量vAND型信号量的基本思路：将进程在整个运行过程中需要的所有资源，一次性全部的分配该进程，待进程使用完后再一起释

13、放。v即资源分配具有原子性，要么全分配；要么一个都不分配vSwait和Ssignal操作Swait(S1,S2,Sn)if(S11 and S21 and and Sn1 ) then for i:=1 to n do Si:=Si1; endforelse 将进程加入第一个条件不满足的Si的等待队列上，并且修改程序指针到Swait操作的开始部分endifSsignal(S1,S2,Sn) for i:=1 to n do Si:=Si1; 若Si有等待进程，则唤醒endfor信号量集信号量集v 目标：更一般化 例如，一次申请多个单位的资源；又如，当资源数低于某一下限值时，就不予分配Swait

14、(S1, t1, d1,S2, t2, d2,Sn,tn,dn)if(S1t1 and S2t2 and and Sn tn )then for i:=1 to n do Si:=Sidi; endforelse 将进程加入第一个条件不满足的Si的等待队列上，并且修改程序指针到Swait操作的开始部分endift: 需求值需求值d: 下限下限Ssignal(S1, d1,S2, d2,Sn,dn)for i:=1 to n do Si:=Sidi; 若Si有等待进程，则唤醒endforv信号量集的几种特殊情况：Swait(S,d,d)：多单位Swait(S,1,1)：一般记录型信号量Swait

15、(S,1,0)：s1时，允许多个进入临界区；s0后，阻止一切内容提要内容提要v进程同步问题的来由和进程同步的主要任务v临界资源和临界区v2任务的进程互斥问题的解决方案v信号量Semaphores v死锁和饿死现象死锁和饿死现象v经典同步问题v管程v进程间通信Deadlock & starvation 死锁和饿死现象死锁和饿死现象v Deadlock 死锁 Two or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processesv

16、Starvation 饿死 Indefinite blocking A process may never be removed from the semaphore queue in which it is blockedl If LIFO queue (stack mode)内容提要内容提要v进程同步问题的来由和进程同步的主要任务v临界资源和临界区v2任务的进程互斥问题的解决方案v信号量Semaphores v死锁和饿死现象v经典同步问题经典同步问题v管程v进程间通信Classical Problems of SynchronizationvBounded-Buffer Problem生产

17、者-消费者问题vReaders and Writers Problem读者与写者问题vDining-Philosophers Problem哲学家就餐问题Bounded-buffer problemv Producer-Consumer problem Producer process produces information, & that is consumed by a consumer process Use buffer to share information The access to buffer must be synchronizedv Bounded-buffer

18、 Fixed buffer size Both need to wait in some conditions buffer producer consumer 使用记录型信号量解决使用记录型信号量解决PC问题问题v Shared semaphore semaphore full, empty, mutex; Initially:lfull = 0; /* counting full items */lempty = N; /* counting empty items */lmutex = 1; /* binary semaphore, control access to CS */v Ot

19、her shared variable item bufBufSize; int in=0; int out = 0;P&CProducerConsumerdo /* * produce an item * in nextp */ P(empty); P(mutex); /* add nextp to buffer*/ bufin=nextp; in=(in+1) mod n; V(mutex); V(full);while(1);do P(full); P(mutex); /* remove a item to nextc*/ nextc=bufout; out=(out+1) mo

20、d n; V(mutex); V(empty); /* * consume the item * in nextc */while(1);Readers-Writers problem读者写者问题读者写者问题vA data object can be shared among several concurrent process/threads.Readers读者: those only want to read the data objectWriters写者: others want to update (r/w) the data objectv读者与写者之间的冲突R|RW/RW/WRe

21、aders-Writers problem (contd)v写者对共享数据具有独占性读者-写者问题的变形:vThe first R/W problemReader has the higher priorityWriter may starvevThe second R/W problemWriter has the higher priorityReader may starveR/W problem: a solutionv Shared variable int readcount = 0;v Shared semaphore semaphore Wmutex=1; semaphore

22、Rmutex = 1;v WriterdoP(Wmutex);/* perform write operation */V(Wmute);while(1);v ReaderdoP(Rmutex);if (readcount=0)P(Wmutex);readcount+;V(Rmutex);/* perform read operation */P(Rmutex);readcount-;if (readcount=0)V(Wmutex);V(Rmutex);while(1);利用信号量集解决读者利用信号量集解决读者-写者问题写者问题v 假定最多只允许RN个读者v 使用信号量L控制读者的数量var

23、 RN integer; L, mx:semaphore:=RN,1; reader: begin repeat Swait(L,1,1); Swait(mx,1,0); read Ssignal(L,1); until false; endwriter: beginrepeat Swait(mx,1,1; L,RN,0); write Ssignal(mx,1)endDining-Philosophers Problem哲学家就餐问题哲学家就餐问题v5 philosophersThinking or eatingOnly 5 chopstickslLeft & rightlOne a

24、t a timeAt most 2 philosophers can eat at a timevsemaphore chopstick5 =1,1,1,1,1; Dining-philosophers problem (cont.)v A possible solution Philosopher iv Possible deadlock When 5 philosophers each grabs the left chopstick, v Solutions: Philosophers =4 Only if both chopsticks are available, Odd, firs

25、t left then right; even, first right then leftdoP(chopsticki); / leftP(chopstick(i+1)%5; / right/* eating */V(chopsticki;V(chopstick(i+1)%5;/* thinking */while(1);利用利用AND信号量解决哲学家就餐问题信号量解决哲学家就餐问题var chopstick array of semaphore:=(1,1,1,1,1)process i repeat think; Swait(chopstick(i+1)mod5, chopsticki)

26、; eat; Ssignal(chopstick(i+1)mod5, chopsticki); until false;Timing errorsv Only happen when some particular execution sequences take placev For example: counter+; counter-;v Difficult to detectv Do not always occurMisuse of semaphore timing errorsv Semaphore is just a convenient and effective mechan

27、ism for process synchronization.If be used incorrect, timing errors will happen.v Example 1: The given solution to Dining-philosophers problem Only if 5 philosophers each grabs the left chopstick simultaneouslyv An honest programming error or an uncooperative programmer also results in timing errors

28、.For example:Example 2v Example 2.1:If the order of P/V is interchangedV(mutex);CS section;P(mutex);irreproducible, violating the mutual-exclusion requirementv Example 2.2:If replaces V(mutex) with P(mutex)P(mutex);CS section;P(mutex);always deadlockExample 2 (contd)vExample 2.3:If P or V or both be

29、 omittedP(mutex);CS section; / starving (deadlock)orCS section;V(mutex); / mutual exclusion is violated orCS section; / mutual exclusion is violated 内容提要内容提要v进程同步问题的来由和进程同步的主要任务v临界资源和临界区v2任务的进程互斥问题的解决方案v信号量Semaphores v死锁和饿死现象v经典同步问题v管程管程v进程间通信The solution: Monitor 管程管程v引入管程的原因：方便性管程将对共享资源（数据）的同步操作加以

30、封装vHansan关于管程的定义：一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据v高级语言结构：管程类型v管程的组成：管程的名称局部于管程内部的共享数据说明对该数据结构进行操作的一组过程对局部于管程内部的共享数据设置初始值的语句v type monitor-name = monitorvariable declarationsprocedure entry P1() begin end; procedure entry P2() begin end; procedure entry Pn() begin end;begin in

31、itilization code;endSynchronization of monitorv The monitor constructprohibits concurrent access to all procedures defined within the monitor.v Only one process may be active within the monitor at a time.v The synchronization is built into the monitor type, the programmer does not need to code it ex

32、plicitly.Condition Variables条件变量条件变量v To allow a process to wait within the monitor, a condition variable must be declared, as condition x, y;/分别表示不同的等待原因v 条件变量只能通过 wait 和 signal来操作x.waitv The process invoking this operation is blocked until another thread invokes x.signalx.signalv Resumes exactly o

33、ne thread. If no thread is blocked, then its no effect具有条件变量的管程具有条件变量的管程Something about signalv E.g.: P invokes x.signal, and Q is blocked on condition x. Which one will execute then? Make sure: only one process can be active!v Two possibilities: Signal-&-Wait Signal-&-continueMonitor for PC

34、 problemtype PCmonitorvar in,out,count: integer;buffer: array0,n-1 of item;notfull, notempty: condition;procedure entry put(item) begin if (countn) then notfull.wait; /满，则等待非满 bufferin := nextp; in := (in+1)mod n count:=count+1; if notempty.queue then notempty.signal; endprocedure entry get(item)beg

35、in if count0 then notempty.wait; /空，则等待非空 nextc:=bufferout; out:=(out+1)mod n; count:=count-1; if notfull.queue then notfull.signal;endbegin in:=out:=0; count:=0; endproducer begin repeat produce item PC.put(item) until false endconsumer: begin repeat PC.get(item); consume item until false end利用管程解决哲学家同步问题利用管程解决哲学家同步问题type DPmonitorvar state: array0,4 of (thinking, hungry, eating);var self: