安徽大學(xué)操作系統(tǒng)進(jìn)程管理.ppt

《安徽大學(xué)操作系統(tǒng)進(jìn)程管理.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《安徽大學(xué)操作系統(tǒng)進(jìn)程管理.ppt（64頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

計(jì)算機(jī)操作系統(tǒng),楊為民m0304abc@,湯子瀛哲鳳屏湯小丹編著,2,2.3.2信號(hào)量機(jī)制,1.整型信號(hào)量最初由Dijkstra把整型信號(hào)量定義為一個(gè)整型量，除初始化外，僅能通過兩個(gè)標(biāo)準(zhǔn)的原子操作(AtomicOperation)wait(S)和signal(S)來訪問。這兩個(gè)操作一直被分別稱為P、V操作。wait和signal操作可描述為：wait(S):whileS≤0dono-opS∶=S-1;signal(S):S∶=S+1;,3,2.3.2信號(hào)量機(jī)制,2.記錄型信號(hào)量在整型信號(hào)量機(jī)制中的wait操作，只要是信號(hào)量S≤0，就會(huì)不斷地測(cè)試。因此，該機(jī)制并未遵循“讓權(quán)等待”的準(zhǔn)則，而是使進(jìn)程處于“忙等”的狀態(tài)。記錄型信號(hào)量機(jī)制，則是一種不存在“忙等”現(xiàn)象的進(jìn)程同步機(jī)制。但在采取了“讓權(quán)等待”的策略后，又會(huì)出現(xiàn)多個(gè)進(jìn)程等待訪問同一臨界資源的情況。為此，在信號(hào)量機(jī)制中，除了需要一個(gè)用于代表資源數(shù)目的整型變量value外，還應(yīng)增加一個(gè)進(jìn)程鏈表L，用于鏈接上述的所有等待進(jìn)程。記錄型信號(hào)量是由于它采用了記錄型的數(shù)據(jù)結(jié)構(gòu)而得名的。它所包含的上述兩個(gè)數(shù)據(jù)項(xiàng)可描述為：,4,2.3.2信號(hào)量機(jī)制,typesemaphore=recordvalue:integer;L:listofprocess;end相應(yīng)地，wait(S)和signal(S)操作可描述為：procedurewait(S)varS:semaphore;beginS.value∶=S.value-1;ifS.value＜0thenblock(S,L)endproceduresignal(S)varS:semaphore;beginS.value∶=S.value+1;ifS.value≤0thenwakeup(S,L);end,5,2.3.2信號(hào)量機(jī)制,在記錄型信號(hào)量機(jī)制中，S.value的初值表示系統(tǒng)中某類資源的數(shù)目，因而又稱為資源信號(hào)量，對(duì)它的每次wait操作，意味著進(jìn)程請(qǐng)求一個(gè)單位的該類資源，因此描述為S.value∶=S.value-1；當(dāng)S.value＜0時(shí)，表示該類資源已分配完畢，因此進(jìn)程應(yīng)調(diào)用block原語(yǔ)，進(jìn)行自我阻塞，放棄處理機(jī)，并插入到信號(hào)量鏈表S.L中。可見，該機(jī)制遵循了“讓權(quán)等待”準(zhǔn)則。此時(shí)S.value的絕對(duì)值表示在該信號(hào)量鏈表中已阻塞進(jìn)程的數(shù)目。對(duì)信號(hào)量的每次signal操作，表示執(zhí)行進(jìn)程釋放一個(gè)單位資源，故S.value∶=S.value+1操作表示資源數(shù)目加1。若加1后仍是S.value≤0，則表示在該信號(hào)量鏈表中，仍有等待該資源的進(jìn)程被阻塞，故還應(yīng)調(diào)用wakeup原語(yǔ)，將S.L鏈表中的第一個(gè)等待進(jìn)程喚醒。如果S.value的初值為1，表示只允許一個(gè)進(jìn)程訪問臨界資源，此時(shí)的信號(hào)量轉(zhuǎn)化為互斥信號(hào)量。信號(hào)量S是一個(gè)整數(shù)，S大于等于零時(shí)代表可供并發(fā)進(jìn)程使用的資源實(shí)體數(shù)，但S小于零時(shí)則表示正在等待使用臨界區(qū)的進(jìn)程數(shù)。,6,2.3.2信號(hào)量機(jī)制,3.AND型信號(hào)量在兩個(gè)進(jìn)程中都要包含兩個(gè)對(duì)Dmutex和Emutex的操作，即processA:processB:wait(Dmutex);wait(Emutex);wait(Emutex);wait(Dmutex);若進(jìn)程A和B按下述次序交替執(zhí)行wait操作：processA:wait(Dmutex);于是Dmutex=0processB:wait(Emutex);于是Emutex=0processA:wait(Emutex);于是Emutex=-1A阻塞processB:wait(Dmutex);于是Dmutex=-1B阻塞,7,2.3.2信號(hào)量機(jī)制,AND同步機(jī)制的基本思想是：將進(jìn)程在整個(gè)運(yùn)行過程中需要的所有資源，一次性全部地分配給進(jìn)程，待進(jìn)程使用完后再一起釋放。只要尚有一個(gè)資源未能分配給進(jìn)程，其它所有可能為之分配的資源，也不分配給他。亦即，對(duì)若干個(gè)臨界資源的分配，采取原子操作方式：要么全部分配到進(jìn)程，要么一個(gè)也不分配。由死鎖理論可知，這樣就可避免上述死鎖情況的發(fā)生。為此，在wait操作中，增加了一個(gè)“AND”條件，故稱為AND同步，或稱為同時(shí)wait操作，即Swait(Simultaneouswait)定義如下：,8,2.3.2信號(hào)量機(jī)制,Swait(S1,S2,…,Sn)ifSi≥1and…andSn≥1thenfori∶=1tondoSi∶=Si-1;endforelseplacetheprocessinthewaitingqueueassociatedwiththefirstSifoundwithSi＜1,andsettheprogramcountofthisprocesstothebeginningofSwaitoperationendifSsignal(S1,S2,…,Sn)fori∶=1tondoSi=Si+1;RemovealltheprocesswaitinginthequeueassociatedwithSiintothereadyqueue.endfor;,9,2.3.2信號(hào)量機(jī)制,4.信號(hào)量集Swait(S1,t1,d1,…,Sn,tn,dn)ifSi≥t1and…andSn≥tnthenfori∶=1tondoSi∶=Si-di;endforelsePlacetheexecutingprocessinthewaitingqueueofthefirstSiwithSi＜tiandsetitsprogramcountertothebeginningoftheSwaitOperation.endifSsignal(S1,d1,…,Sn,dn)fori∶=1tondoSi∶=Si+di;RemovealltheprocesswaitinginthequeueassociatedwithSiintothereadyqueueendfor;,10,2.4經(jīng)典進(jìn)程的同步問題,2.4.1生產(chǎn)者—消費(fèi)者問題2.4.2哲學(xué)家進(jìn)餐問題2.4.3讀者-寫者問題,11,2.4.1生產(chǎn)者—消費(fèi)者問題,前面我們已經(jīng)對(duì)生產(chǎn)者—消費(fèi)者問題(Theproceducer-consumerproblem)做了一些描述，但未考慮進(jìn)程的互斥與同步問題，因而造成了數(shù)據(jù)Counter的不定性。生產(chǎn)者—消費(fèi)者問題是相互合作的進(jìn)程關(guān)系的一種抽象。在輸入時(shí)，輸入進(jìn)程是生產(chǎn)者，計(jì)算進(jìn)程是消費(fèi)者；而在輸出時(shí)，則計(jì)算進(jìn)程是生產(chǎn)者，而打印進(jìn)程是消費(fèi)者，因此，該問題有很大的代表性及實(shí)用價(jià)值。,12,2.4.1生產(chǎn)者—消費(fèi)者問題,1.利用記錄型信號(hào)量解決生產(chǎn)者—消費(fèi)者問題假定在生產(chǎn)者和消費(fèi)者之間的公用緩沖池中，具有n個(gè)緩沖區(qū)，這時(shí)可利用互斥信號(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è)消息。對(duì)生產(chǎn)者—消費(fèi)者問題可描述如下：,13,2.4.1生產(chǎn)者—消費(fèi)者問題,Varmutex,empty,full:semaphore∶=1,n,0;buffer:array［0,…,n-1］ofitem;in,out:integer∶=0,0;beginparbeginproceducer:beginrepeat…produceranitemnextp;…wait(empty);wait(mutex);buffer(in)∶=nextp;in∶=(in+1)modn;signal(mutex);signal(full);untilfalse;end,14,2.4.1生產(chǎn)者—消費(fèi)者問題,consumer:beginrepeatwait(full);wait(mutex);nextc∶=buffer(out);out∶=(out+1)modn;signal(mutex);signal(empty);consumertheiteminnextc;untilfalse;endparendend,15,2.4.1生產(chǎn)者—消費(fèi)者問題,在生產(chǎn)者—消費(fèi)者問題中應(yīng)注意：首先，在每個(gè)程序中用于實(shí)現(xiàn)互斥的wait(mutex)和signal(mutex)必須成對(duì)地出現(xiàn)；其次，對(duì)資源信號(hào)量empty和full的wait和signal操作，同樣需要成對(duì)地出現(xiàn)，但它們分別處于不同的程序中。例如，wait(empty)在計(jì)算進(jìn)程中，而signal(empty)則在打印進(jìn)程中，計(jì)算進(jìn)程若因執(zhí)行wait(empty)而阻塞，則以后將由打印進(jìn)程將它喚醒；最后，在每個(gè)程序中的多個(gè)wait操作順序不能顛倒。應(yīng)先執(zhí)行對(duì)資源信號(hào)量的wait操作，然后再執(zhí)行對(duì)互斥信號(hào)量的wait操作，否則可能引起進(jìn)程死鎖。,16,2.4.1生產(chǎn)者—消費(fèi)者問題,2.利用AND信號(hào)量解決生產(chǎn)者—消費(fèi)者問題Varmutex,empty,full:semaphore∶=1,n,0;buffer:array［0,…,n-1］ofitem;inout:integer∶=0,0;beginparbeginproducer:beginrepeat…produceaniteminnextp;…Swait(empty,mutex);buffer(in)∶=nextp;in∶=(in+1)modn;Ssignal(mutex,full);untilfalse;end,17,2.4.1生產(chǎn)者—消費(fèi)者問題,consumer:beginrepeatSwait(full,mutex);nextc∶=buffer(out);out∶=(out+1)modn;Ssignal(mutex,empty);consumertheiteminnextc;untilfalse;endparendend,18,2.4.2哲學(xué)家進(jìn)餐問題,1.利用記錄型信號(hào)量解決哲學(xué)家進(jìn)餐問題經(jīng)分析可知，放在桌子上的筷子是臨界資源，在一段時(shí)間內(nèi)只允許一位哲學(xué)家使用。為了實(shí)現(xiàn)對(duì)筷子的互斥使用，可以用一個(gè)信號(hào)量表示一只筷子，由這五個(gè)信號(hào)量構(gòu)成信號(hào)量數(shù)組。其描述如下：Varchopstick:array［0,…,4］ofsemaphore;,19,2.4.2哲學(xué)家進(jìn)餐問題,所有信號(hào)量均被初始化為1，第i位哲學(xué)家的活動(dòng)可描述為：repeatwait(chopstick［i］);wait(chopstick［(i+1)mod5］);…eat;…signal(chopstick［i］);signal(chopstick［(i+1)mod5］);…think;untilfalse;,20,2.4.2哲學(xué)家進(jìn)餐問題,可采取以下幾種解決方法：(1)至多只允許有四位哲學(xué)家同時(shí)去拿左邊的筷子，最終能保證至少有一位哲學(xué)家能夠進(jìn)餐，并在用畢時(shí)能釋放出他用過的兩只筷子，從而使更多的哲學(xué)家能夠進(jìn)餐。(2)僅當(dāng)哲學(xué)家的左、右兩只筷子均可用時(shí)，才允許他拿起筷子進(jìn)餐。(3)規(guī)定奇數(shù)號(hào)哲學(xué)家先拿他左邊的筷子，然后再去拿右邊的筷子；而偶數(shù)號(hào)哲學(xué)家則相反。按此規(guī)定，將是1、2號(hào)哲學(xué)家競(jìng)爭(zhēng)1號(hào)筷子；3、4號(hào)哲學(xué)家競(jìng)爭(zhēng)3號(hào)筷子。即五位哲學(xué)家都先競(jìng)爭(zhēng)奇數(shù)號(hào)筷子，獲得后，再去競(jìng)爭(zhēng)偶數(shù)號(hào)筷子，最后總會(huì)有一位哲學(xué)家能獲得兩只筷子而進(jìn)餐。,21,2.4.2哲學(xué)家進(jìn)餐問題,2.利用AND信號(hào)量機(jī)制解決哲學(xué)家進(jìn)餐問題在哲學(xué)家進(jìn)餐問題中，要求每個(gè)哲學(xué)家先獲得兩個(gè)臨界資源(筷子)后方能進(jìn)餐，這在本質(zhì)上就是前面所介紹的AND同步問題，故用AND信號(hào)量機(jī)制可獲得最簡(jiǎn)潔的解法。Varchopsiickarray［0,…,4］ofsemaphore∶=(1,1,1,1,1);processirepeatthink;Sswait(chopstick［(i+1)mod5］,chopstick［i］);eat;Ssignat(chopstick［(i+1)mod5］,chopstick［i］);untilfalse;,22,2.4.3讀者-寫者問題,1.利用記錄型信號(hào)量解決讀者-寫者問題為實(shí)現(xiàn)Reader與Writer進(jìn)程間在讀或?qū)憰r(shí)的互斥而設(shè)置了一個(gè)互斥信號(hào)量Wmutex。另外，再設(shè)置一個(gè)整型變量Readcount表示正在讀的進(jìn)程數(shù)目。由于只要有一個(gè)Reader進(jìn)程在讀，便不允許Writer進(jìn)程去寫。因此，僅當(dāng)Readcount=0,表示尚無Reader進(jìn)程在讀時(shí)，Reader進(jìn)程才需要執(zhí)行Wait(Wmutex)操作。若wait(Wmutex)操作成功，Reader進(jìn)程便可去讀，相應(yīng)地，做Readcount+1操作。同理，僅當(dāng)Reader進(jìn)程在執(zhí)行了Readcount減1操作后其值為0時(shí)，才須執(zhí)行signal(Wmutex)操作，以便讓W(xué)riter進(jìn)程寫。又因?yàn)镽eadcount是一個(gè)可被多個(gè)Reader進(jìn)程訪問的臨界資源，因此，應(yīng)該為它設(shè)置一個(gè)互斥信號(hào)量rmutex。,23,2.4.3讀者-寫者問題,讀者-寫者問題可描述如下：Varrmutex,wmutex:semaphore∶=1,1;Readcount:integer∶=0;beginparbeginReader:beginrepeatwait(rmutex);ifreadcount=0thenwait(wmutex);Readcount∶=Readcount+1;signal(rmutex);…performreadoperation;…,24,wait(rmutex);readcount∶=readcount-1;ifreadcount=0thensignal(wmutex);signal(rmutex);untilfalse;endwriter:beginrepeatwait(wmutex);performwriteoperation;signal(wmutex);untilfalse;endparendend,2.4.3讀者-寫者問題,25,2.4.3讀者-寫者問題,2.利用信號(hào)量集機(jī)制解決讀者-寫者問題VarRNinteger;L,mx:semaphore∶=RN,1;beginparbeginreader:beginrepeatSwait(L,1,1);Swait(mx,1,0);…performreadoperation;…,26,2.4.3讀者-寫者問題,Ssignal(L,1);untilfalse;endwriter:beginrepeatSwait(mx,1,1;L,RN,0);performwriteoperation;Ssignal(mx,1);untilfalse;endparendend,27,1．對(duì)于生產(chǎn)者一消費(fèi)者問題，假設(shè)緩沖區(qū)是無界的，試用信號(hào)燈與PV操作給出解法。答：由于是無界緩沖區(qū)，所以生產(chǎn)者不會(huì)因?yàn)榈貌坏骄彌_區(qū)而被阻塞，不需要對(duì)空緩沖區(qū)進(jìn)行管理，可以舍去在有界緩沖區(qū)中用來管理空緩沖區(qū)的信號(hào)量及其PV操作。semaphoremutex_in=1；semaphoremutex_out=1；semaphreproduct=0；intin=0，out=0；生產(chǎn)者活動(dòng)：消費(fèi)者活動(dòng)：{while（1）{while（1）producenextpreduct；P（product）P（mutex_in）；P（mutex_out）；addtheproducttobuffer［in］；taketheproductfrombuffer[out]；in++；out++；V（mutex_in）；V（mutex_out）；V（product）；}},28,14．設(shè)有一個(gè)可以裝A、B兩種物品的倉(cāng)庫(kù)，其容量無限大，但要求倉(cāng)庫(kù)中A、B兩種物品的數(shù)量滿足下述不等式：-M＜=A物品數(shù)量-B物品數(shù)量＜=N其中，M和N為正整數(shù)。試用信號(hào)燈和PV操作描述A、B兩種物品的入庫(kù)過程。答：已知條件-M＜=A物品數(shù)量-B物品數(shù)量＜=N可以拆分成兩個(gè)不等式，即A物品數(shù)量-B物品數(shù)量＜=NB物品數(shù)量-A物品數(shù)量＜=M這兩個(gè)不等式的含義是：倉(cāng)庫(kù)中A物品可以比B物品多，但不能超過N個(gè)；B物品可以比A物品多，但不能超過M個(gè)。semaphorea=n；semaphoreb=m；voidmain（）{createprocess（A，…）；createprocess（B，…）；}A物品入庫(kù)：B物品入庫(kù)：void（A）void（B）；{while（1）{while（1）{P（a）；{P（b）；A物品入庫(kù)；B物品入庫(kù)；V（b）；V（a）；}}}},29,18、一座小橋（最多只能承重兩個(gè)人）橫跨南北兩岸，任意時(shí)刻同一方向只允許一人過橋，南側(cè)橋段和北側(cè)橋段較窄只能通過一人，橋中央一處寬敞，允許兩個(gè)人通過或歇息。試用信號(hào)燈和PV操作寫出南、北兩岸過橋的同步算法。解：需要三個(gè)信號(hào)量。load用來控制橋上人數(shù)，初值為2，表示橋上最多有2個(gè)人；north用來控制北段橋的互斥使用，初值為1；south用來控制南段橋的互斥使用，初值為1。semaphoreload＝2；semaphorenorth＝1；semaphresouth＝l；tosouth（）tonorth（）{P（load）；{P（load）；P（north）；P（south）；過北段橋；過南段橋；到橋中間；到橋中間；V（north）；V（south）；P（south）；P（north）；過南段橋；過北段橋；到達(dá)南岸；到達(dá)北岸；V（south）；V（north）；V（load）；V（load）；}},30,31,,32,,,33,,,34,,,35,11．何謂并行？何謂并發(fā)？在單處理機(jī)系統(tǒng)中下述并行和并發(fā)現(xiàn)象哪些可能發(fā)生？哪些不會(huì)發(fā)生？（1）進(jìn)程與進(jìn)程之間的并行；（2）進(jìn)程與進(jìn)程之間的并發(fā)；（3）處理機(jī)與設(shè)備之間的并行；（4）處理機(jī)與通道之間的并行；（5）通道與通道之間的并行；（6）設(shè)備與設(shè)備之間的并行。,36,,答：所謂并行是指同一時(shí)刻同時(shí)進(jìn)行，進(jìn)程并行需要多處理器的支持；所謂并發(fā)，是指在一段時(shí)間內(nèi)，多個(gè)進(jìn)程都在向前推進(jìn)，而在同一時(shí)刻，可能只有一個(gè)進(jìn)程在執(zhí)行，多個(gè)過程輪流使用處理器。在單處理機(jī)系統(tǒng)中，可能發(fā)生的并行和并發(fā)現(xiàn)象如下：（1）進(jìn)程與進(jìn)程之間的并發(fā)。例如，在Windows操作系統(tǒng)中，MP3播放進(jìn)程和Word字處理進(jìn)程可以并發(fā)執(zhí)行，這樣用戶就可以邊聽音樂邊寫文章了。（2）處理機(jī)與設(shè)備之間的并行。例如，當(dāng)處理機(jī)進(jìn)行科學(xué)運(yùn)算時(shí)，打印機(jī)可以打印文檔。（3）處理機(jī)與通道之間的并行，通道程序的執(zhí)行可與處理機(jī)的操作并行。（4）通道與通道之間的并行。通常一個(gè)系統(tǒng)中有多個(gè)通道，這些通道可以并行地執(zhí)行相應(yīng)的通道程序。（5）設(shè)備與設(shè)備之間的并行。例如，打印機(jī)打印文檔時(shí)，磁帶機(jī)在輸入數(shù)據(jù)。,37,2．什么是進(jìn)程？進(jìn)程具有哪些主要特性？比較進(jìn)程與程序之間的相同點(diǎn)與不同點(diǎn)。答：進(jìn)程是具有一定獨(dú)立功能的程序關(guān)于一個(gè)數(shù)據(jù)集合的一次運(yùn)行活動(dòng)。進(jìn)程具有以下主要特性：（1）并發(fā)性：可以與其他進(jìn)程一起在宏觀上同時(shí)向前推進(jìn)。（2）動(dòng)態(tài)性：進(jìn)程是執(zhí)行中的程序。此外，進(jìn)程的動(dòng)態(tài)性還體現(xiàn)在如下兩個(gè)方面。首先，進(jìn)程是動(dòng)態(tài)產(chǎn)生、動(dòng)態(tài)消亡的；其次，在進(jìn)程的生存期內(nèi)，其狀態(tài)處于經(jīng)常性的動(dòng)態(tài)變化之中。（3）獨(dú)立性：進(jìn)程是調(diào)度的基本單位，它可以獲得處理機(jī)并參與并發(fā)執(zhí)行。（4）交往性：進(jìn)程在運(yùn)行過程中可能會(huì)與其他進(jìn)程發(fā)生直接或間接的相互作用。（5）異步性：每個(gè)進(jìn)程都以其相對(duì)獨(dú)立、不可預(yù)知的速度向前推進(jìn)。（6）結(jié)構(gòu)性：每個(gè)進(jìn)程有一個(gè)控制塊PCB。,38,,進(jìn)程和程序的相同點(diǎn)：程序是構(gòu)成進(jìn)程的組成部分之一，一個(gè)進(jìn)程存在的目的就是執(zhí)行其所對(duì)應(yīng)的程序，如果沒有程序，進(jìn)程就失去了其存在的意義。進(jìn)程與程序的不同點(diǎn)：（1）程序是靜態(tài)的，而進(jìn)程是動(dòng)態(tài)的。（2）程序可以寫在紙上或在某一存儲(chǔ)介質(zhì)上長(zhǎng)期保存，而進(jìn)程具有生存期，創(chuàng)建后存在，撤銷后消亡。（3）一個(gè)程序可以對(duì)應(yīng)多個(gè)進(jìn)程，但一個(gè)進(jìn)程只能對(duì)應(yīng)一個(gè)程序。例如，一組學(xué)生在一個(gè)分時(shí)系統(tǒng)中做C語(yǔ)言實(shí)習(xí)，他們都需要使用C語(yǔ)言的編譯程序?qū)ζ湓闯绦蜻M(jìn)行編譯，為此每個(gè)學(xué)生都需要有一個(gè)進(jìn)程，這些進(jìn)程都運(yùn)行C語(yǔ)言的編譯程序。另外，一個(gè)程序的多次執(zhí)行也分別對(duì)應(yīng)不同的進(jìn)程。,39,,6．有幾種類型進(jìn)程隊(duì)列？每類各應(yīng)設(shè)置幾個(gè)隊(duì)列？答：通常，系統(tǒng)中的進(jìn)程隊(duì)列分為如下三類：（1）就緒隊(duì)列：整個(gè)系統(tǒng)一個(gè)。所有處于就緒狀態(tài)的進(jìn)程按照某種組織方式排在這一隊(duì)列中，進(jìn)程入隊(duì)列和出隊(duì)列的次序與處理機(jī)調(diào)度算法有關(guān)。在某些系統(tǒng)中，就緒隊(duì)列可能有多個(gè)，用以對(duì)就緒進(jìn)程分類，以方便某種調(diào)度策略的實(shí)施。（2）等待隊(duì)列：每個(gè)等待事件一個(gè)。當(dāng)進(jìn)程等待某一事件時(shí)，進(jìn)入與該事件相關(guān)的等待隊(duì)列中；當(dāng)某事件發(fā)生時(shí)，與該事件相關(guān)的一個(gè)或多個(gè)進(jìn)程離開相應(yīng)的等待隊(duì)列，進(jìn)入就結(jié)隊(duì)列。（3）運(yùn)行隊(duì)列：在單CPU系統(tǒng)中只有一個(gè)，在多CPU系統(tǒng)中每個(gè)CPU各有一個(gè)。每個(gè)隊(duì)列中只有一個(gè)進(jìn)程，指向運(yùn)行隊(duì)列頭部的指針被稱作運(yùn)行指示字。,40,,12．設(shè)S1和S2為兩個(gè)信號(hào)燈變量，下列八組P、V操作哪些可以同時(shí)進(jìn)行？哪些不能同時(shí)進(jìn)行？為什么？（1）P（S1），P（S2）；（2）P（S1），V（S2）；（3）V（S1），P（S2）；（4）V（S1），V（S2）；（5）P（S1），P（S1）；（6）P（S2），V（S2）；（7）V（S1），P（S1）；（8）V（S2），V（S2）。答：能同時(shí)進(jìn)行的包括：（1）、（2）、（3）、（4）。這些操作涉及不同的信號(hào)燈變量，屬于關(guān)于不同組共享變量的臨界區(qū)。不能同時(shí)進(jìn)行的包括：（5）、（6）、（7）、（8）。這些操作涉及相同的信號(hào)燈變量，屬于關(guān)于同一組共享變量的臨界區(qū)。,41,2.5進(jìn)程通信,2.6.1進(jìn)程通信的類型2.6.2消息傳遞通信的實(shí)現(xiàn)方法2.6.3消息傳遞系統(tǒng)實(shí)現(xiàn)中的若干問題2.6.4消息緩沖隊(duì)列通信機(jī)制,42,2.5進(jìn)程通信,通信（communication）意味著在進(jìn)程間傳送數(shù)據(jù)。操作系統(tǒng)可以被看作是各種進(jìn)程組成的。這些進(jìn)程都具有各自的獨(dú)立功能，且大多數(shù)被外部需要而啟動(dòng)執(zhí)行。一般來說，進(jìn)程間的通信根據(jù)通信內(nèi)容可以劃分為二種：控制信息的傳送與大批量數(shù)據(jù)傳送。有時(shí)，也把進(jìn)程間控制信息的交換稱為低級(jí)通信，低級(jí)通信一般只傳送一個(gè)或幾個(gè)字節(jié)的信息，以達(dá)到控制進(jìn)程執(zhí)行速度的作用。把進(jìn)程間大批量數(shù)據(jù)的交換稱為高級(jí)通信。高級(jí)通信要傳送大量數(shù)據(jù)。高級(jí)通信的目的不是為了控制進(jìn)程的執(zhí)行速度，而是為了交換信息。,43,2.5.1進(jìn)程通信的類型,共享存儲(chǔ)器系統(tǒng)(Shared-MemorySystem)消息傳遞系統(tǒng)(Messagepassingsystem)管道(Pipe)通信,44,2.5.1進(jìn)程通信的類型,1.共享存儲(chǔ)器系統(tǒng)(Shared-MemorySystem)(1)基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式：諸進(jìn)程公用數(shù)據(jù)結(jié)構(gòu)以實(shí)現(xiàn)進(jìn)程間的信息交換；(2)基于共享存儲(chǔ)區(qū)的通信方式：諸進(jìn)程通過對(duì)共享存儲(chǔ)區(qū)中數(shù)據(jù)的讀或?qū)憣?shí)現(xiàn)通信。,45,2.5.1進(jìn)程通信的類型,2.消息傳遞系統(tǒng)(Messagepassingsystem)不論是單機(jī)系統(tǒng)、多機(jī)系統(tǒng)，還是計(jì)算機(jī)網(wǎng)絡(luò)，消息傳遞機(jī)制都是用得最廣泛的一種進(jìn)程間通信的機(jī)制。在消息傳遞系統(tǒng)中，進(jìn)程間的數(shù)據(jù)交換，是以格式化的消息(message)為單位的；在計(jì)算機(jī)網(wǎng)絡(luò)中，又把message稱為報(bào)文。程序員直接利用系統(tǒng)提供的一組通信命令(原語(yǔ))進(jìn)行通信。操作系統(tǒng)隱藏了通信的實(shí)現(xiàn)細(xì)節(jié)，大大減化了通信程序編制的復(fù)雜性，而獲得廣泛的應(yīng)用。消息傳遞系統(tǒng)的通信方式屬于高級(jí)通信方式。又因其實(shí)現(xiàn)方式的不同而進(jìn)一步分成直接通信方式和間接通信方式兩種。,46,2.5.1進(jìn)程通信的類型,3.管道(Pipe)通信所謂“管道”，是指用于連接一個(gè)讀進(jìn)程和一個(gè)寫進(jìn)程以實(shí)現(xiàn)他們之間通信的一個(gè)共享文件，又名pipe文件。向管道(共享文件)提供輸入的發(fā)送進(jìn)程(即寫進(jìn)程)，以字符流形式將大量的數(shù)據(jù)送入管道；而接受管道輸出的接收進(jìn)程(即讀進(jìn)程)，則從管道中接收(讀)數(shù)據(jù)。由于發(fā)送進(jìn)程和接收進(jìn)程是利用管道進(jìn)行通信的，故又稱為管道通信。這種方式首創(chuàng)于UNIX系統(tǒng)，由于它能有效地傳送大量數(shù)據(jù)，因而又被引入到許多其它操作系統(tǒng)中。,47,2.5.1進(jìn)程通信的類型,為了協(xié)調(diào)雙方的通信，管道機(jī)制必須提供以下三方面的協(xié)調(diào)能力：①互斥，即當(dāng)一個(gè)進(jìn)程正在對(duì)pipe執(zhí)行讀/寫操作時(shí)，其它(另一)進(jìn)程必須等待。②同步，指當(dāng)寫(輸入)進(jìn)程把一定數(shù)量(如4KB)的數(shù)據(jù)寫入pipe，便去睡眠等待，直到讀(輸出)進(jìn)程取走數(shù)據(jù)后，再把他喚醒。當(dāng)讀進(jìn)程讀一空pipe時(shí)，也應(yīng)睡眠等待，直至寫進(jìn)程將數(shù)據(jù)寫入管道后，才將之喚醒。③確定對(duì)方是否存在，只有確定了對(duì)方已存在時(shí)，才能進(jìn)行通信。,48,2.5.2消息傳遞通信的實(shí)現(xiàn)方法,1.直接通信方式這是指發(fā)送進(jìn)程利用OS所提供的發(fā)送命令，直接把消息發(fā)送給目標(biāo)進(jìn)程。此時(shí)，要求發(fā)送進(jìn)程和接收進(jìn)程都以顯式方式提供對(duì)方的標(biāo)識(shí)符。通常，系統(tǒng)提供下述兩條通信命令(原語(yǔ))：Send(Receiver,message);發(fā)送一個(gè)消息給接收進(jìn)程；Receive(Sender,message);接收Sender發(fā)來的消息；例如，原語(yǔ)Send(P2,m1)表示將消息m1發(fā)送給接收進(jìn)程P2;而原語(yǔ)Receive(P1，m1)則表示接收由P1發(fā)來的消息m1。,49,2.5.2消息傳遞通信的實(shí)現(xiàn)方法,在某些情況下，接收進(jìn)程可與多個(gè)發(fā)送進(jìn)程通信，因此，它不可能事先指定發(fā)送進(jìn)程。例如，用于提供打印服務(wù)的進(jìn)程，它可以接收來自任何一個(gè)進(jìn)程的“打印請(qǐng)求”消息。對(duì)于這樣的應(yīng)用，在接收進(jìn)程接收消息的原語(yǔ)中的源進(jìn)程參數(shù)，是完成通信后的返回值，接收原語(yǔ)可表示為：Receive(id,message);,50,2.5.2消息傳遞通信的實(shí)現(xiàn)方法,我們還可以利用直接通信原語(yǔ)，來解決生產(chǎn)者-消費(fèi)者問題。當(dāng)生產(chǎn)者生產(chǎn)出一個(gè)產(chǎn)品(消息)后，便用Send原語(yǔ)將消息發(fā)送給消費(fèi)者進(jìn)程；而消費(fèi)者進(jìn)程則利用Receive原語(yǔ)來得到一個(gè)消息。如果消息尚未生產(chǎn)出來，消費(fèi)者必須等待，直至生產(chǎn)者進(jìn)程將消息發(fā)送過來。生產(chǎn)者-消費(fèi)者的通信過程可分別描述如下：repeat…produceaniteminnextp;…send(consumer,nextp);untilfalse;repeatreceive(producer,nextc);…consumetheiteminnextc;untilfalse;,51,2.5.2消息傳遞通信的實(shí)現(xiàn)方法,2.間接通信方式(1)信箱的創(chuàng)建和撤消。進(jìn)程可利用信箱創(chuàng)建原語(yǔ)來建立一個(gè)新信箱。創(chuàng)建者進(jìn)程應(yīng)給出信箱名字、信箱屬性(公用、私用或共享)；對(duì)于共享信箱，還應(yīng)給出共享者的名字。當(dāng)進(jìn)程不再需要讀信箱時(shí)，可用信箱撤消原語(yǔ)將之撤消。(2)消息的發(fā)送和接收。當(dāng)進(jìn)程之間要利用信箱進(jìn)行通信時(shí)，必須使用共享信箱，并利用系統(tǒng)提供的下述通信原語(yǔ)進(jìn)行通信。Send(mailbox,message);將一個(gè)消息發(fā)送到指定信箱Receive(mailbox,message);從指定信箱中接收一個(gè)消息,52,2.5.2消息傳遞通信的實(shí)現(xiàn)方法,信箱可由操作系統(tǒng)創(chuàng)建，也可由用戶進(jìn)程創(chuàng)建，創(chuàng)建者是信箱的擁有者。據(jù)此，可把信箱分為以下三類。1)私用信箱用戶進(jìn)程可為自己建立一個(gè)新信箱，并作為該進(jìn)程的一部分。信箱的擁有者有權(quán)從信箱中讀取消息，其他用戶則只能將自己構(gòu)成的消息發(fā)送到該信箱中。這種私用信箱可采用單向通信鏈路的信箱來實(shí)現(xiàn)。當(dāng)擁有該信箱的進(jìn)程結(jié)束時(shí)，信箱也隨之消失。,53,2.5.2消息傳遞通信的實(shí)現(xiàn)方法,2)公用信箱它由操作系統(tǒng)創(chuàng)建，并提供給系統(tǒng)中的所有核準(zhǔn)進(jìn)程使用。核準(zhǔn)進(jìn)程既可把消息發(fā)送到該信箱中，也可從信箱中讀取發(fā)送給自己的消息。顯然，公用信箱應(yīng)采用雙向通信鏈路的信箱來實(shí)現(xiàn)。通常，公用信箱在系統(tǒng)運(yùn)行期間始終存在。3)共享信箱它由某進(jìn)程創(chuàng)建，在創(chuàng)建時(shí)或創(chuàng)建后，指明它是可共享的，同時(shí)須指出共享進(jìn)程(用戶)的名字。信箱的擁有者和共享者，都有權(quán)從信箱中取走發(fā)送給自己的消息。,54,2.5.2消息傳遞通信的實(shí)現(xiàn)方法,在利用信箱通信時(shí)，在發(fā)送進(jìn)程和接收進(jìn)程之間，存在以下四種關(guān)系：(1)一對(duì)一關(guān)系。這時(shí)可為發(fā)送進(jìn)程和接收進(jìn)程建立一條兩者專用的通信鏈路，使兩者之間的交互不受其他進(jìn)程的干擾。(2)多對(duì)一關(guān)系。允許提供服務(wù)的進(jìn)程與多個(gè)用戶進(jìn)程之間進(jìn)行交互，也稱為客戶/服務(wù)器交互(client/serverinteraction)。(3)一對(duì)多關(guān)系。允許一個(gè)發(fā)送進(jìn)程與多個(gè)接收進(jìn)程進(jìn)行交互，使發(fā)送進(jìn)程可用廣播方式，向接收者(多個(gè))發(fā)送消息。(4)多對(duì)多關(guān)系。允許建立一個(gè)公用信箱，讓多個(gè)進(jìn)程都能向信箱中投遞消息；也可從信箱中取走屬于自己的消息。,55,2.5.3消息傳遞系統(tǒng)實(shí)現(xiàn)中的若干問題,1.通信鏈路(communicationlink)為使在發(fā)送進(jìn)程和接收進(jìn)程之間能進(jìn)行通信，必須在兩者之間建立一條通信鏈路。有兩種方式建立通信鏈路。由發(fā)送進(jìn)程在通信之前，用顯式的“建立連接”命令(原語(yǔ))請(qǐng)求系統(tǒng)為之建立一條通信鏈路；在鏈路使用完后，也用顯式方式拆除鏈路。這種方式主要用于計(jì)算機(jī)網(wǎng)絡(luò)中。發(fā)送進(jìn)程無須明確提出建立鏈路的請(qǐng)求，只須利用系統(tǒng)提供的發(fā)送命令(原語(yǔ))，系統(tǒng)會(huì)自動(dòng)地為之建立一條鏈路。這種方式主要用于單機(jī)系統(tǒng)中。,56,2.5.3消息傳遞系統(tǒng)實(shí)現(xiàn)中的若干問題,根據(jù)通信鏈路的連接方法，又可把通信鏈路分為兩類：①點(diǎn)—點(diǎn)連接通信鏈路，這時(shí)的一條鏈路只連接兩個(gè)結(jié)點(diǎn)(進(jìn)程)；②多點(diǎn)連接鏈路，指用一條鏈路連接多個(gè)(n＞2)結(jié)點(diǎn)(進(jìn)程)。而根據(jù)通信方式的不同，則又可把鏈路分成兩種：?jiǎn)蜗蛲ㄐ沛溌罚辉试S發(fā)送進(jìn)程向接收進(jìn)程發(fā)送消息；雙向鏈路，既允許由進(jìn)程A向進(jìn)程B發(fā)送消息，也允許進(jìn)程B同時(shí)向進(jìn)程A發(fā)送消息。,57,2.5.3消息傳遞系統(tǒng)實(shí)現(xiàn)中的若干問題,2.消息的格式在某些OS中，消息是采用比較短的定長(zhǎng)消息格式，這減少了對(duì)消息的處理和存儲(chǔ)開銷。這種方式可用于辦公自動(dòng)化系統(tǒng)中，為用戶提供快速的便箋式通信；但這對(duì)要發(fā)送較長(zhǎng)消息的用戶是不方便的。在有的OS中，采用另一種變長(zhǎng)的消息格式，即進(jìn)程所發(fā)送消息的長(zhǎng)度是可變的。系統(tǒng)在處理和存儲(chǔ)變長(zhǎng)消息時(shí)，須付出更多的開銷，但方便了用戶。這兩種消息格式各有其優(yōu)缺點(diǎn)，故在很多系統(tǒng)(包括計(jì)算機(jī)網(wǎng)絡(luò))中，是同時(shí)都用的。,58,2.5.3消息傳遞系統(tǒng)實(shí)現(xiàn)中的若干問題,3.進(jìn)程同步方式(1)發(fā)送進(jìn)程阻塞、接收進(jìn)程阻塞。(2)發(fā)送進(jìn)程不阻塞、接收進(jìn)程阻塞。(3)發(fā)送進(jìn)程和接收進(jìn)程均不阻塞。,59,2.5.4消息緩沖隊(duì)列通信機(jī)制,1.消息緩沖隊(duì)列通信機(jī)制中的數(shù)據(jù)結(jié)構(gòu)(1)消息緩沖區(qū)。在消息緩沖隊(duì)列通信方式中，主要利用的數(shù)據(jù)結(jié)構(gòu)是消息緩沖區(qū)。它可描述如下：typemessagebuffer=recordsender;發(fā)送者進(jìn)程標(biāo)識(shí)符size;消息長(zhǎng)度text;消息正文next;指向下一個(gè)消息緩沖區(qū)的指針end,60,2.5.4消息緩沖隊(duì)列通信機(jī)制,(2)PCB中有關(guān)通信的數(shù)據(jù)項(xiàng)。在利用消息緩沖隊(duì)列通信機(jī)制時(shí)，在設(shè)置消息緩沖隊(duì)列的同時(shí)，還應(yīng)增加用于對(duì)消息隊(duì)列進(jìn)行操作和實(shí)現(xiàn)同步的信號(hào)量，并將它們置入進(jìn)程的PCB中。在PCB中應(yīng)增加的數(shù)據(jù)項(xiàng)可描述如下：typeprocesscontrolblock=record…mq;消息隊(duì)列隊(duì)首指針mutex;消息隊(duì)列互斥信號(hào)量sm;消息隊(duì)列資源信號(hào)量…end,61,2.5.4消息緩沖隊(duì)列通信機(jī)制,2.發(fā)送原語(yǔ)發(fā)送進(jìn)程在利用發(fā)送原語(yǔ)發(fā)送消息之前，應(yīng)先在自己的內(nèi)存空間，設(shè)置一發(fā)送區(qū)a，把待發(fā)送的消息正文、發(fā)送進(jìn)程標(biāo)識(shí)符、消息長(zhǎng)度等信息填入其中，然后調(diào)用發(fā)送原語(yǔ)，把消息發(fā)送給目標(biāo)(接收)進(jìn)程。發(fā)送原語(yǔ)首先根據(jù)發(fā)送區(qū)a中所設(shè)置的消息長(zhǎng)度a.size來申請(qǐng)一緩沖區(qū)i，接著，把發(fā)送區(qū)a中的信息復(fù)制到緩沖區(qū)i中。為了能將i掛在接收進(jìn)程的消息隊(duì)列mq上，應(yīng)先獲得接收進(jìn)程的內(nèi)部標(biāo)識(shí)符j，然后將i掛在j.mq上。由于該隊(duì)列屬于臨界資源，故在執(zhí)行insert操作的前后，都要執(zhí)行wait和signal操作。,62,圖2-12消息緩沖通信,2.5.4消息緩沖隊(duì)列通信機(jī)制,63,proceduresend(receiver,a)begingetbuf(a.size,i);根據(jù)a.size申請(qǐng)緩沖區(qū)；i.sender∶=a.sender;將發(fā)送區(qū)a中的信息復(fù)制到消息緩沖區(qū)之中；i.size∶=a.size;i.text∶=a.text;i.next∶=0;getid(PCBset,receiver.j);獲得接收進(jìn)程內(nèi)部標(biāo)識(shí)符；wait(j.mutex);insert(j.mq,i);將消息緩沖區(qū)插入消息隊(duì)列；signal(j.mutex);signal(j.sm);end,2.5.4消息緩沖隊(duì)列通信機(jī)制,64,2.5.4消息緩沖隊(duì)列通信機(jī)制,3.接收原語(yǔ)接收原語(yǔ)描述如下：procedurereceive(b)beginj∶=internalname;j為接收進(jìn)程內(nèi)部的標(biāo)識(shí)符；wait(j.sm);wait(j.mutex);remove(j.mq,i);將消息隊(duì)列中第一個(gè)消息移出；signal(j.mutex);b.sender∶=i.sender;將消息緩沖區(qū)i中的信息復(fù)制到接收區(qū)b;b.size∶=i.size;b.text∶=i.text;end,