第五講進(jìn)程同步和通信（partII）

1、第五講第五講 進(jìn)程同步和通信（進(jìn)程同步和通信（part II）中國(guó)科學(xué)技術(shù)大學(xué)計(jì)算機(jī)系中國(guó)科學(xué)技術(shù)大學(xué)計(jì)算機(jī)系 陳香蘭陳香蘭2013Fall內(nèi)容提要內(nèi)容提要v進(jìn)程同步問題的來由和進(jìn)程同步的主要任務(wù)v臨界資源和臨界區(qū)v2任務(wù)的進(jìn)程互斥問題的解決方案v信號(hào)量Semaphores v死鎖和餓死現(xiàn)象v經(jīng)典同步問題v管程v進(jìn)程間通信內(nèi)容提要內(nèi)容提要v進(jìn)程同步問題的來由和進(jìn)程同步的主要任務(wù)v臨界資源和臨界區(qū)v2任務(wù)的進(jìn)程互斥問題的解決方案v信號(hào)量信號(hào)量Semaphores v死鎖和餓死現(xiàn)象v經(jīng)典同步問題v管程v進(jìn)程間通信信號(hào)量機(jī)制信號(hào)量機(jī)制 SemaphorevReading計(jì)算機(jī)操作系統(tǒng)，湯子瀛，3.2

2、節(jié)Operating System Concepts，7th edition，section6.5 P200信號(hào)量機(jī)制信號(hào)量機(jī)制v整型信號(hào)量v記錄型信號(hào)量v信號(hào)量集整型信號(hào)量整型信號(hào)量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 (資源信號(hào)量） Used to control access to a given resource consisting of only a finite number 0,nv Binary semaphore (二進(jìn)制信號(hào)量或互斥信號(hào)量，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: /利用信號(hào)量實(shí)現(xiàn)互斥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利用信號(hào)量進(jìn)行同步；利用信號(hào)量進(jìn)行同步；可以描述前驅(qū)關(guān)系可以描述前驅(qū)關(guān)系同步舉例（前驅(qū)舉例）同步舉例（前驅(qū)舉例

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記錄型信號(hào)量記錄型信號(hào)量v Define semaphore as a recordtypedef struct int value;struct process *L; /等待隊(duì)列等待隊(duì)列 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對(duì)于wait操作，v 開始時(shí)： 當(dāng)value1時(shí)，說明有資源剩余；只需要減1 當(dāng)value1時(shí)，說明沒有資源剩余；減去1，并等待v 結(jié)束時(shí)： value 0，說明沒有等待者 value0，說明有等待者，此時(shí)L上有等待進(jìn)程；此時(shí)，此時(shí)，value的的絕對(duì)值表示等待進(jìn)程的個(gè)數(shù)絕對(duì)值表示等待進(jìn)程的個(gè)數(shù)對(duì)于signal操作，v 開始時(shí)，同wait結(jié)束時(shí) value 0，說明沒有等待者，不必喚醒，只需要加1 value0，說明有等待者；加1，并喚醒1個(gè)進(jìn)程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 臨界區(qū)問題: 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型信號(hào)量型信號(hào)量vAND型信號(hào)量的基本思路：將進(jìn)程在整個(gè)運(yùn)行過程中需要的所有資源，一次性全部的分配該進(jìn)程，待進(jìn)程使用完后再一起釋

13、放。v即資源分配具有原子性，要么全分配；要么一個(gè)都不分配vSwait和Ssignal操作Swait(S1,S2,Sn)if(S11 and S21 and and Sn1 ) then for i:=1 to n do Si:=Si1; endforelse 將進(jìn)程加入第一個(gè)條件不滿足的Si的等待隊(duì)列上，并且修改程序指針到Swait操作的開始部分endifSsignal(S1,S2,Sn) for i:=1 to n do Si:=Si1; 若Si有等待進(jìn)程，則喚醒endfor信號(hào)量集信號(hào)量集v 目標(biāo)：更一般化 例如，一次申請(qǐng)多個(gè)單位的資源；又如，當(dāng)資源數(shù)低于某一下限值時(shí)，就不予分配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 將進(jìn)程加入第一個(gè)條件不滿足的Si的等待隊(duì)列上，并且修改程序指針到Swait操作的開始部分endift: 需求值需求值d: 下限下限Ssignal(S1, d1,S2, d2,Sn,dn)for i:=1 to n do Si:=Sidi; 若Si有等待進(jìn)程，則喚醒endforv信號(hào)量集的幾種特殊情況：Swait(S,d,d)：多單位Swait(S,1,1)：一般記錄型信號(hào)量Swait

15、(S,1,0)：s1時(shí)，允許多個(gè)進(jìn)入臨界區(qū)；s0后，阻止一切內(nèi)容提要內(nèi)容提要v進(jìn)程同步問題的來由和進(jìn)程同步的主要任務(wù)v臨界資源和臨界區(qū)v2任務(wù)的進(jìn)程互斥問題的解決方案v信號(hào)量Semaphores v死鎖和餓死現(xiàn)象死鎖和餓死現(xiàn)象v經(jīng)典同步問題v管程v進(jìn)程間通信Deadlock & starvation 死鎖和餓死現(xiàn)象死鎖和餓死現(xiàn)象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)內(nèi)容提要內(nèi)容提要v進(jìn)程同步問題的來由和進(jìn)程同步的主要任務(wù)v臨界資源和臨界區(qū)v2任務(wù)的進(jìn)程互斥問題的解決方案v信號(hào)量Semaphores v死鎖和餓死現(xiàn)象v經(jīng)典同步問題經(jīng)典同步問題v管程v進(jìn)程間通信Classical Problems of SynchronizationvBounded-Buffer Problem生產(chǎn)

17、者-消費(fèi)者問題vReaders and Writers Problem讀者與寫者問題vDining-Philosophers Problem哲學(xué)家就餐問題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 使用記錄型信號(hào)量解決使用記錄型信號(hào)量解決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寫者對(duì)共享數(shù)據(jù)具有獨(dú)占性讀者-寫者問題的變形: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);利用信號(hào)量集解決讀者利用信號(hào)量集解決讀者-寫者問題寫者問題v 假定最多只允許RN個(gè)讀者v 使用信號(hào)量L控制讀者的數(shù)量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哲學(xué)家就餐問題哲學(xué)家就餐問題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信號(hào)量解決哲學(xué)家就餐問題信號(hào)量解決哲學(xué)家就餐問題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 內(nèi)容提要內(nèi)容提要v進(jìn)程同步問題的來由和進(jìn)程同步的主要任務(wù)v臨界資源和臨界區(qū)v2任務(wù)的進(jìn)程互斥問題的解決方案v信號(hào)量Semaphores v死鎖和餓死現(xiàn)象v經(jīng)典同步問題v管程管程v進(jìn)程間通信The solution: Monitor 管程管程v引入管程的原因：方便性管程將對(duì)共享資源（數(shù)據(jù)）的同步操作加以

30、封裝vHansan關(guān)于管程的定義：一個(gè)管程定義了一個(gè)數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進(jìn)程所執(zhí)行（在該數(shù)據(jù)結(jié)構(gòu)上）的一組操作，這組操作能同步進(jìn)程和改變管程中的數(shù)據(jù)v高級(jí)語言結(jié)構(gòu)：管程類型v管程的組成：管程的名稱局部于管程內(nèi)部的共享數(shù)據(jù)說明對(duì)該數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的一組過程對(duì)局部于管程內(nèi)部的共享數(shù)據(jù)設(shè)置初始值的語句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利用管程解決哲學(xué)家同步問題利用管程解決哲學(xué)家同步問題type DPmonitorvar state: array0,4 of (thinking, hungry, eating);var self: