第2章進(jìn)程的描述與控制(part5)

1、第二章 進(jìn) 程 管 理 Heb Nomal University Department of Computer Science1第二章第二章 進(jìn)程的描述與控制進(jìn)程的描述與控制 2.1 2.1 前驅(qū)圖和程序執(zhí)行前驅(qū)圖和程序執(zhí)行 2.2 2.2 進(jìn)程進(jìn)程 的描述的描述2.3 2.3 進(jìn)程控制進(jìn)程控制 2.4 2.4 進(jìn)程同步進(jìn)程同步 2.5 2.5 經(jīng)典進(jìn)程的同步問(wèn)題經(jīng)典進(jìn)程的同步問(wèn)題 2.6 2.6 進(jìn)程通信進(jìn)程通信 2.7 2.7 線程的基本概念線程的基本概念 2.8 2.8 線程的實(shí)現(xiàn)線程的實(shí)現(xiàn) 第二章 進(jìn) 程 管 理 Heb Nomal University Department of C

2、omputer Science2 關(guān) 于 進(jìn)程同步 P.V操作必須成對(duì)出現(xiàn) 當(dāng)為互斥互斥操作時(shí)，它們同處于同一進(jìn)程 當(dāng)為同步同步操作時(shí)，則不在同一進(jìn)程中出現(xiàn) 如果P(S1)和P(S2)兩個(gè)操作在一起，那么P操作的順序至關(guān)重要。第二章 進(jìn) 程 管 理 Heb Nomal University Department of Computer Science3掌握信號(hào)量的物理意義掌握信號(hào)量的物理意義（1 1）一般考查對(duì)記錄型信號(hào)量的理解。）一般考查對(duì)記錄型信號(hào)量的理解。 信號(hào)量的物理含義：信號(hào)量的物理含義：S-value0S-value0表示有表示有S-valueS-value個(gè)資源可用；個(gè)資源可用；

3、S-value=0S-value=0表示無(wú)資源可用；表示無(wú)資源可用；S-valuevaluevalue|S-value|表示等待隊(duì)列中的進(jìn)程個(gè)數(shù)。表示等待隊(duì)列中的進(jìn)程個(gè)數(shù)。說(shuō)明：根據(jù)以上信號(hào)量的物理意義，可以計(jì)算信號(hào)量的變說(shuō)明：根據(jù)以上信號(hào)量的物理意義，可以計(jì)算信號(hào)量的變化范圍?；秶?。（2 2）S-valueS-value的初值的初值 表示系統(tǒng)中某類資源的數(shù)目，稱為資源信號(hào)量。表示系統(tǒng)中某類資源的數(shù)目，稱為資源信號(hào)量。若若S-valueS-value的初值為的初值為1 1，表示只允許一個(gè)進(jìn)程訪問(wèn)，此時(shí)信，表示只允許一個(gè)進(jìn)程訪問(wèn)，此時(shí)信號(hào)量轉(zhuǎn)化為互斥信號(hào)量。號(hào)量轉(zhuǎn)化為互斥信號(hào)量。（3 3）對(duì)信

4、號(hào)量只能執(zhí)行）對(duì)信號(hào)量只能執(zhí)行waitwait、signalsignal操作操作wait(S)wait(S)表示申請(qǐng)一個(gè)資源表示申請(qǐng)一個(gè)資源 ；signal(S)signal(S)表示釋放一個(gè)資源。表示釋放一個(gè)資源。注意：整型信號(hào)量不會(huì)取負(fù)值，可由此判斷題目中的信號(hào)注意：整型信號(hào)量不會(huì)取負(fù)值，可由此判斷題目中的信號(hào)量是整型信號(hào)量還是記錄型信號(hào)量。量是整型信號(hào)量還是記錄型信號(hào)量。第二章 進(jìn) 程 管 理 Heb Nomal University Department of Computer Science4semaphore empty=1, full=0;item buffer;void pro

5、ducer() do wait(empty); putdata; signal(full); while(1); void consumer() do wait(full); getdata; signal(empty); while(1); void main()cobegin producer();consumer();coend說(shuō)明：對(duì)資源信號(hào)量說(shuō)明：對(duì)資源信號(hào)量emptyempty和和fullfull的的waitwait和和signalsignal操作，操作，同樣需要成對(duì)地出現(xiàn)，但處于不同的程序中。同樣需要成對(duì)地出現(xiàn)，但處于不同的程序中。1. 利用記錄型信號(hào)量解決生產(chǎn)者利用記錄型信號(hào)量

6、解決生產(chǎn)者消費(fèi)者問(wèn)題消費(fèi)者問(wèn)題 設(shè)置設(shè)置2個(gè)信號(hào)量個(gè)信號(hào)量full和和empty。 Full:表示表示buffer中有數(shù)據(jù)的緩沖區(qū)個(gè)數(shù)，初值為中有數(shù)據(jù)的緩沖區(qū)個(gè)數(shù)，初值為0； Empty:表示表示buffer中空緩沖區(qū)的個(gè)數(shù)，初值為中空緩沖區(qū)的個(gè)數(shù)，初值為1; 取值范圍都是取值范圍都是-1，1。 buffer生產(chǎn)者消費(fèi)者第二章 進(jìn) 程 管 理 Heb Nomal University Department of Computer Science5l復(fù)雜情況（既有同步，又有互斥）：復(fù)雜情況（既有同步，又有互斥）：一個(gè)一個(gè)buffer，n個(gè)生產(chǎn)者，個(gè)生產(chǎn)者，m個(gè)消費(fèi)者個(gè)消費(fèi)者，生產(chǎn)者不斷地生產(chǎn)，消

7、費(fèi)者不生產(chǎn)者不斷地生產(chǎn)，消費(fèi)者不斷地消費(fèi)。只有斷地消費(fèi)。只有buffer為空時(shí)生產(chǎn)者才能進(jìn)行為空時(shí)生產(chǎn)者才能進(jìn)行putdata操作，只有操作，只有buffer有數(shù)據(jù)有數(shù)據(jù)時(shí)消費(fèi)者才能進(jìn)行時(shí)消費(fèi)者才能進(jìn)行g(shù)etdata操作。操作。buffer變成了臨界資源，不允許多個(gè)進(jìn)程同時(shí)操作buffer。即不允許多個(gè)生產(chǎn)者同時(shí)進(jìn)行putdata操作，也不允許多個(gè)消費(fèi)者同時(shí)進(jìn)行g(shù)etdata操作。與簡(jiǎn)單情況相比，需要增加一個(gè)信號(hào)量mutex來(lái)實(shí)現(xiàn)對(duì)buffer的互斥訪問(wèn)，其初始值為1。 信號(hào)量full和empty的變化范圍與簡(jiǎn)單情況有所不同。full初值仍然為0，變化范圍：-m-m，11，n是消費(fèi)者進(jìn)程總數(shù)量

8、；empty初值仍然為1，變化范圍：1-n1-n，11，m是生產(chǎn)者進(jìn)程總數(shù)量。 buffer生產(chǎn)者消費(fèi)者第二章 進(jìn) 程 管 理 Heb Nomal University Department of Computer Science6semaphore empty=1, full=0,mutex=1;item buffer;void producer() do wait(empty); putdata; signal(full); while(1); void consumer() do wait(full); getdata; signal(empty); while(1); void mai

9、n()cobegin producer();consumer();coendwait(mutex);signal(mutex);wait(mutex);signal(mutex);說(shuō)明：說(shuō)明：（1）在生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程中，）在生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程中，V操作的次序無(wú)關(guān)緊要，但操作的次序無(wú)關(guān)緊要，但兩個(gè)兩個(gè)P操作操作的次序卻不能顛倒，否則可能導(dǎo)致死鎖，的次序卻不能顛倒，否則可能導(dǎo)致死鎖，即，應(yīng)即，應(yīng)先執(zhí)行對(duì)資源信號(hào)量的先執(zhí)行對(duì)資源信號(hào)量的wait操操作，再執(zhí)行對(duì)互斥信號(hào)量的作，再執(zhí)行對(duì)互斥信號(hào)量的wait操作操作。（2）由于）由于buffer只有一個(gè)，只有一個(gè)，full和和empty就可以保

10、證對(duì)就可以保證對(duì)buffer的互斥操作，故的互斥操作，故mutex也可以省略，但如果也可以省略，但如果buffer有多個(gè)，則有多個(gè)，則mutex不能省略。不能省略。第二章 進(jìn) 程 管 理 Heb Nomal University Department of Computer Science7l一般意義的一般意義的“生產(chǎn)者生產(chǎn)者消費(fèi)者消費(fèi)者”問(wèn)題：?jiǎn)栴}：N個(gè)個(gè)buffer，多個(gè)生產(chǎn)者，多個(gè)消費(fèi)者多個(gè)生產(chǎn)者，多個(gè)消費(fèi)者，循環(huán)存取，循環(huán)存取buffer。 l(教材上的教材上的)buffer生產(chǎn)者消費(fèi)者bufferbufferbufferbuffer第二章 進(jìn) 程 管 理 Heb Nomal Univ

11、ersity Department of Computer Science81. 利用記錄型信號(hào)量解決生產(chǎn)者消費(fèi)者問(wèn)題 假定：在P-C之間的公用緩沖池中，具有n個(gè)緩沖區(qū)；利用互斥信號(hào)量mutex實(shí)現(xiàn)各進(jìn)程對(duì)緩沖池的互斥使用；利用信號(hào)量empty和full分別表示緩沖池中空緩沖區(qū)和滿緩沖區(qū)的數(shù)量。這些生產(chǎn)者和消費(fèi)者相互等效，只要緩沖池未滿，生產(chǎn)者便可將消息送入緩沖池；只要緩沖池未空，消費(fèi)者便可從緩沖池中取走一個(gè)消息。full是“滿”緩沖區(qū)數(shù)目，初值為0，empty是“空”緩沖區(qū)數(shù)目，初值為N。實(shí)際上，full和empty是同一個(gè)含義：full + empty = N初值為1第二章 進(jìn) 程 管 理

12、 Heb Nomal University Department of Computer Science9P(full);P(mutex); one unit buffer;V(mutex);V(full);Producer每個(gè)進(jìn)程中各個(gè)每個(gè)進(jìn)程中各個(gè)P操作的次序很重要：操作的次序很重要： 先檢查資源數(shù)目，再檢查是否互斥先檢查資源數(shù)目，再檢查是否互斥否則可能否則可能死鎖死鎖第二章 進(jìn) 程 管 理 Heb Nomal University Department of Computer Science10semaphore mutex=1, empty=n, full=0; /互斥信號(hào)量初值為1；

13、/資源信號(hào)量empty表示空緩沖區(qū)個(gè)數(shù)，初值為n/full表示滿緩沖區(qū)個(gè)數(shù)，初值為0 item buffern; int in=0, out=0; void proceducer( ) do producer an item nextp; wait(empty); wait(mutex); bufferin = nextp; in = (in+1) % n; signal(mutex); signal(full); while(True); void consumer( ) do wait(full); wait(mutex); nextc = bufferout; out = (out+1)

14、 % n; signal(mutex); signal(empty); consumer the item in nextc; while(true);void main( ) cobegin proceducer(); consumer( ); coend第二章 進(jìn) 程 管 理 Heb Nomal University Department of Computer Science11l在 每 個(gè) 程 序 中 用 于在 每 個(gè) 程 序 中 用 于 實(shí) 現(xiàn) 互 斥 的實(shí) 現(xiàn) 互 斥 的 w a i t ( m u t e x ) 和和signal(mutex)必須成對(duì)必須成對(duì)地出現(xiàn)；地出現(xiàn)； l

15、對(duì)對(duì)資源信號(hào)量資源信號(hào)量empty和和full的的wait和和signal操作，同樣需操作，同樣需要成對(duì)地出現(xiàn)要成對(duì)地出現(xiàn)，但它們分別處于不同的程序中。但它們分別處于不同的程序中。 例如，例如，wait(empty)在計(jì)算進(jìn)程中，而在計(jì)算進(jìn)程中，而signal(empty)則在打印進(jìn)程中，則在打印進(jìn)程中，計(jì)算進(jìn)程若因執(zhí)行計(jì)算進(jìn)程若因執(zhí)行wait(empty)而阻塞，而阻塞， 則以后將由打印進(jìn)程將它喚醒；則以后將由打印進(jìn)程將它喚醒；l在每個(gè)程序中的在每個(gè)程序中的多個(gè)多個(gè)wait操作順序不能顛倒。應(yīng)先執(zhí)行操作順序不能顛倒。應(yīng)先執(zhí)行對(duì)資源信號(hào)量的對(duì)資源信號(hào)量的wait操作，然后再執(zhí)行對(duì)互斥信號(hào)量的操

16、作，然后再執(zhí)行對(duì)互斥信號(hào)量的wait操作，操作，否則可能引起進(jìn)程死鎖否則可能引起進(jìn)程死鎖。 在生產(chǎn)者消費(fèi)者問(wèn)題中應(yīng)注意：Why?第二章 進(jìn) 程 管 理 Heb Nomal University Department of Computer Science12 生產(chǎn)者消費(fèi)者問(wèn)題生產(chǎn)者消費(fèi)者問(wèn)題 哲學(xué)家就餐問(wèn)題 讀者寫者問(wèn)題 理發(fā)師問(wèn)題第二章 進(jìn) 程 管 理 Heb Nomal University Department of Computer Science132.5.2 哲學(xué)家進(jìn)餐問(wèn)題哲學(xué)家進(jìn)餐問(wèn)題 哲學(xué)家就餐問(wèn)題 有五個(gè)哲學(xué)家圍坐在一圓桌旁，桌中央有一盤通心粉，每人面前有一只空盤子，每?jī)扇酥?/p>

17、間放一只筷子。 每個(gè)哲學(xué)家的行為是思考，感到饑餓，然后吃通心粉。 為了吃通心粉，每個(gè)哲學(xué)家必須拿到兩只筷子，并且每個(gè)人只能直接從自己的左邊或右邊去取筷子 1. 利用記錄型信號(hào)量解決哲學(xué)家進(jìn)餐問(wèn)題利用記錄型信號(hào)量解決哲學(xué)家進(jìn)餐問(wèn)題 經(jīng)分析可知，放在桌子上的經(jīng)分析可知，放在桌子上的筷子是臨界資源筷子是臨界資源，在一段，在一段時(shí)間內(nèi)只允許一位哲學(xué)家使用。為了實(shí)現(xiàn)對(duì)筷子的互斥使時(shí)間內(nèi)只允許一位哲學(xué)家使用。為了實(shí)現(xiàn)對(duì)筷子的互斥使用，可以用，可以為每一只筷子設(shè)置一個(gè)信號(hào)量（取筷子執(zhí)行為每一只筷子設(shè)置一個(gè)信號(hào)量（取筷子執(zhí)行P操作，操作，放下筷子執(zhí)行放下筷子執(zhí)行V操作），由這五個(gè)信號(hào)量構(gòu)成信號(hào)量數(shù)組。操作），

18、由這五個(gè)信號(hào)量構(gòu)成信號(hào)量數(shù)組。其描述如下：其描述如下： semaphore chopstick5= 1,1,1,1,1; 所有信號(hào)量均被初始化為所有信號(hào)量均被初始化為1 第二章 進(jìn) 程 管 理 Heb Nomal University Department of Computer Science14第第i位哲學(xué)家的活動(dòng)可描述為：位哲學(xué)家的活動(dòng)可描述為： do wait(chopsticki); /取左邊筷子取左邊筷子 wait(chopstick(i+1) % 5); /取右邊筷子取右邊筷子 eat; signal(chopsticki); /放下左邊筷子放下左邊筷子 signal(chops

19、tick(i+1) % 5); /放下右邊筷子放下右邊筷子 think; while(True); 可能出現(xiàn)死鎖可能出現(xiàn)死鎖第二章 進(jìn) 程 管 理 Heb Nomal University Department of Computer Science15 可采取以下幾種解決方法：可采取以下幾種解決方法： (1) 至多只允許有四位至多只允許有四位哲學(xué)家同時(shí)去拿左邊的筷子，哲學(xué)家同時(shí)去拿左邊的筷子，最最終能保證至少有一位哲學(xué)家能夠進(jìn)餐，并在用畢時(shí)能釋放出他用過(guò)的終能保證至少有一位哲學(xué)家能夠進(jìn)餐，并在用畢時(shí)能釋放出他用過(guò)的兩只筷子，從而使更多的哲學(xué)家能夠進(jìn)餐。兩只筷子，從而使更多的哲學(xué)家能夠進(jìn)餐。

20、(2) 僅當(dāng)哲學(xué)家的左、右兩只筷子均可用時(shí)，才允許僅當(dāng)哲學(xué)家的左、右兩只筷子均可用時(shí)，才允許他拿起筷子進(jìn)餐。他拿起筷子進(jìn)餐。 (3) 規(guī)定規(guī)定奇數(shù)號(hào)哲學(xué)家先拿他左邊的筷子，然后再去奇數(shù)號(hào)哲學(xué)家先拿他左邊的筷子，然后再去拿右邊的筷子；而偶數(shù)號(hào)哲學(xué)家則相反拿右邊的筷子；而偶數(shù)號(hào)哲學(xué)家則相反。按此規(guī)定，將是按此規(guī)定，將是1、 2號(hào)哲學(xué)家競(jìng)爭(zhēng)號(hào)哲學(xué)家競(jìng)爭(zhēng)1號(hào)筷子；號(hào)筷子；3、4號(hào)哲學(xué)家競(jìng)爭(zhēng)號(hào)哲學(xué)家競(jìng)爭(zhēng)3號(hào)筷子。即五位哲學(xué)家號(hào)筷子。即五位哲學(xué)家都先競(jìng)爭(zhēng)奇數(shù)號(hào)筷子，獲得后，再去競(jìng)爭(zhēng)偶數(shù)號(hào)筷子，最后總會(huì)有一都先競(jìng)爭(zhēng)奇數(shù)號(hào)筷子，獲得后，再去競(jìng)爭(zhēng)偶數(shù)號(hào)筷子，最后總會(huì)有一位哲學(xué)家能獲得兩只筷子而進(jìn)餐。位哲學(xué)家能獲

21、得兩只筷子而進(jìn)餐。 第二章 進(jìn) 程 管 理 Heb Nomal University Department of Computer Science16semaphore chopstick5=1，1，1，1，1;semaphore count=4;void philosopher_i( )while(true)think();wait(count); /請(qǐng)求進(jìn)入房間進(jìn)餐請(qǐng)求進(jìn)入房間進(jìn)餐wait(chopsticki); /請(qǐng)求左手邊的筷子請(qǐng)求左手邊的筷子wait(chopstick(i+1)%5); /請(qǐng)求右手邊的筷子請(qǐng)求右手邊的筷子eat();signal(chopstick(i+1)%5)

22、; /釋放右手邊的筷子釋放右手邊的筷子signal(chopsticki); /釋放左手邊的筷子釋放左手邊的筷子signal(count); /退出房間釋放信號(hào)量退出房間釋放信號(hào)量room 解法一：解法一：第二章 進(jìn) 程 管 理 Heb Nomal University Department of Computer Science17解法二：解法二：semaphore chopstick5=1，1，1，1，1;integer i=0,1,4;void philosopher_i( ) while(true) if(i%2=0)then P(chopsticki); P(chopstick(i+

23、1)%5);eating; V(chopsticki); V(chopstick(i+1)%5);else P(chopstick(i+1)%5); P(chopsticki);eating; V(chopstick(i+1)%5); V(chopsticki);第二章 進(jìn) 程 管 理 Heb Nomal University Department of Computer Science18AND型信號(hào)量 在兩個(gè)進(jìn)程中都要包含兩個(gè)對(duì)在兩個(gè)進(jìn)程中都要包含兩個(gè)對(duì)Dmutex和和Emutex的操作，的操作， 即即process A: process B:wait(Dmutex); wait(Emut

24、ex);wait(Emutex); wait(Dmutex);若進(jìn)程若進(jìn)程A和和B按下述次序交替執(zhí)行按下述次序交替執(zhí)行wait操作：操作：process A: wait(Dmutex); 于是于是Dmutex=0process B: wait(Emutex); 于是于是Emutex=0process A: wait(Emutex); 于是于是Emutex=-1 A阻塞阻塞process B: wait(Dmutex); 于是于是Dmutex=-1 B阻塞阻塞 2. 利用利用AND信號(hào)量機(jī)制解決哲學(xué)家進(jìn)餐問(wèn)題信號(hào)量機(jī)制解決哲學(xué)家進(jìn)餐問(wèn)題(回到回到2.4.3) 第二章 進(jìn) 程 管 理 Heb No

25、mal University Department of Computer Science19 AND同步機(jī)制的基本思想是：同步機(jī)制的基本思想是：將進(jìn)程在整個(gè)運(yùn)行過(guò)程將進(jìn)程在整個(gè)運(yùn)行過(guò)程中需要的所有資源，一次性全部地分配給進(jìn)程，待進(jìn)程使中需要的所有資源，一次性全部地分配給進(jìn)程，待進(jìn)程使用完后再一起釋放。用完后再一起釋放。只要尚有一個(gè)資源未能分配給進(jìn)程，只要尚有一個(gè)資源未能分配給進(jìn)程，其它所有可能為之分配的資源，也不分配給他。亦即，對(duì)其它所有可能為之分配的資源，也不分配給他。亦即，對(duì)若干個(gè)臨界資源的分配，采取若干個(gè)臨界資源的分配，采取原子操作方式：要么全部分原子操作方式：要么全部分配到進(jìn)程，要么

26、一個(gè)也不分配配到進(jìn)程，要么一個(gè)也不分配。 由死鎖理論可知，這樣就可避免上述死鎖情況的發(fā)生。由死鎖理論可知，這樣就可避免上述死鎖情況的發(fā)生。為此，在為此，在wait操作中，增加了一個(gè)操作中，增加了一個(gè)“AND”條件，故稱為條件，故稱為AND同步，或稱為同時(shí)同步，或稱為同時(shí)wait操作，操作， 即即Swait(Simultaneous wait)定義如下：定義如下： 第二章 進(jìn) 程 管 理 Heb Nomal University Department of Computer Science20Swait(S1, S2, , Sn) while(1) if( S1 =1 & & S

27、n =1) for(i=1;i=n ; i+) Si -; break; 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 Ssignal(S1, S2, , Sn) for(i=1;i=n;i+) Si +; Remove all the process waiting in the queue associat

28、ed with Si into the ready queue. 第二章 進(jìn) 程 管 理 Heb Nomal University Department of Computer Science21利用AND信號(hào)量機(jī)制解決哲學(xué)家進(jìn)餐問(wèn)題 在哲學(xué)家進(jìn)餐問(wèn)題中，在哲學(xué)家進(jìn)餐問(wèn)題中，要求每個(gè)哲學(xué)家先獲得兩個(gè)臨界要求每個(gè)哲學(xué)家先獲得兩個(gè)臨界資源資源(筷子筷子)后方能進(jìn)餐，這在本質(zhì)上就是前面所介紹的后方能進(jìn)餐，這在本質(zhì)上就是前面所介紹的AND同步問(wèn)題，故用同步問(wèn)題，故用AND信號(hào)量機(jī)制可獲得最簡(jiǎn)潔的解法。信號(hào)量機(jī)制可獲得最簡(jiǎn)潔的解法。Semaphore chopsiick 5 =1,1,1,1,1; do

29、 think; Swait(chopstick(i+1) % 5, chopsticki); eat; Ssignal(chopstick (i+1) % 5, chopsticki); while(True); 第二章 進(jìn) 程 管 理 Heb Nomal University Department of Computer Science22Semaphore mutex=1, empty=n, full=0; item buffer n ; int in=0, out= 0; void producer( ) do produce an item in nextp; Swait(empty,

30、 mutex); buffer(in) =nextp; in =(in+1) % n; Ssignal(mutex, full); while(True); void consumer( ) do Swait(full, mutex); nextc =buffer(out); out =(out+1) % n; Ssignal(mutex, empty); consumer the item in nextc; while(True); 利用AND信號(hào)量解決生產(chǎn)者消費(fèi)者問(wèn)題 第二章 進(jìn) 程 管 理 Heb Nomal University Department of Computer Science23在一輛公共汽車上，司機(jī)和售