操作系統(tǒng) 第2章

1、 進(jìn)程管理進(jìn)程管理 I1C1P1I2C2P2 進(jìn)程管理進(jìn)程管理 P1 P2 P3 P4 進(jìn)程管理進(jìn)程管理 I1I2I3I4 C1C2C3C4 P1P2P3P4 t 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 就緒就緒 阻塞阻塞執(zhí)行執(zhí)行 時(shí)間片完時(shí)間片完 進(jìn)程調(diào)度進(jìn)程調(diào)度 I/O請(qǐng)求請(qǐng)求 I/O完成完成 圖圖25 進(jìn)程的三種基本狀態(tài)及其轉(zhuǎn)換進(jìn)程的三種基本狀態(tài)及其轉(zhuǎn)換 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 執(zhí)行執(zhí)行 活動(dòng)活動(dòng) 就緒就緒 靜止靜止 就緒就緒 活動(dòng)活動(dòng) 阻塞阻塞 靜止靜止 阻塞阻塞 激活激活 掛起掛起 激活激活 掛起掛起 釋放釋放 釋放釋放

2、掛起掛起 請(qǐng)求請(qǐng)求I/O 進(jìn)程管理進(jìn)程管理 v寫(xiě)一個(gè)程序描述進(jìn)程狀態(tài)遷移過(guò)程。寫(xiě)一個(gè)程序描述進(jìn)程狀態(tài)遷移過(guò)程。 v要求：要求： 提供導(dǎo)致進(jìn)程狀態(tài)變化的調(diào)用接口，包括創(chuàng)建、提供導(dǎo)致進(jìn)程狀態(tài)變化的調(diào)用接口，包括創(chuàng)建、 刪除、調(diào)度、阻塞、時(shí)間到、掛起、激活等。刪除、調(diào)度、阻塞、時(shí)間到、掛起、激活等。 實(shí)現(xiàn)進(jìn)程列表顯示的接口。實(shí)現(xiàn)進(jìn)程列表顯示的接口。 注：這里設(shè)計(jì)的進(jìn)程是一個(gè)假設(shè)的對(duì)象實(shí)體，是注：這里設(shè)計(jì)的進(jìn)程是一個(gè)假設(shè)的對(duì)象實(shí)體，是 由程序自己創(chuàng)建和刪除，不是系統(tǒng)維護(hù)的進(jìn)程。由程序自己創(chuàng)建和刪除，不是系統(tǒng)維護(hù)的進(jìn)程。 進(jìn)程管理進(jìn)程管理 pid 現(xiàn)場(chǎng)現(xiàn)場(chǎng) 進(jìn)程狀態(tài)進(jìn)程狀態(tài) 優(yōu)先級(jí)優(yōu)先級(jí) 阻塞原因阻塞原

3、因 程序地址程序地址 同步機(jī)制同步機(jī)制 資源清單資源清單 鏈接指針鏈接指針 進(jìn)程管理進(jìn)程管理 執(zhí)行指針執(zhí)行指針 就緒隊(duì)列指針就緒隊(duì)列指針 阻塞隊(duì)列指針阻塞隊(duì)列指針 空閑隊(duì)列指針空閑隊(duì)列指針 PCB14 PCB23 PCB30 PCB48 PCB5 PCB67 PCB79 PCB80 PCB91 進(jìn)程管理進(jìn)程管理 structstruct wait_queuewait_queue structstruct task_structtask_struct * * task; task; structstruct wait_queuewait_queue * * next; next; ; PCBPC

4、B PCB 進(jìn)程管理進(jìn)程管理 PCB1 PCB2 PCB3 PCB4 PCB5 PCB6 PCB7 執(zhí)行指針執(zhí)行指針 就緒表指針就緒表指針 阻塞表指針阻塞表指針 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 producer: repeat produce an item in nextp; while counter=n do no-op; bufferin:=nextp; in:=(in+1)mod n; counter:

5、=counter+1; until false; consumer: repeat while counter=0 do no-op; nextc:=bufferout; out:=(out+1) mod n; counter:=counter-1; consumer the item in nextc; until false; 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 Swait(s1,s2,sn) if s11 and and sn 1 then for i:=1 to

6、 n do si:=si-1; endfor else place the process in the waiting queue with the first si found with si1, and set the program count of this process to the beginning of swait operation end if 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 t

7、he ready queue endfor 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 S1 S2 S3 S4 S5 S6 a b c d e g f 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 練習(xí)：已知一個(gè)求知公式 （A2+3B）/（B+5A），若A， B已賦值，試畫(huà)出求值過(guò)程的前趨圖，并用信號(hào)量描述前 驅(qū)關(guān)系。 進(jìn)程管理進(jìn)程管理 v練習(xí)：兩位同學(xué)約好練習(xí)：兩位同學(xué)約好 星期天去東湖，早上星期天去東湖，早上 8:00在校門(mén)口，不見(jiàn)在校門(mén)口，不見(jiàn) 不散。不散。當(dāng)一個(gè)同學(xué)先當(dāng)一個(gè)同學(xué)先 來(lái)到校門(mén)口，要等另一來(lái)到校門(mén)口，要等另一 個(gè)同學(xué)，到齊后一道打個(gè)同學(xué)，到齊后一道打 的去

8、東湖。請(qǐng)用用信號(hào)的去東湖。請(qǐng)用用信號(hào) 量知識(shí)實(shí)現(xiàn)同步。量知識(shí)實(shí)現(xiàn)同步。 南昌 航空 大學(xué) 進(jìn)程管理進(jìn)程管理 va,ba,b 兩點(diǎn)間是一段東西向的單行車(chē)道，現(xiàn)要設(shè)計(jì)一兩點(diǎn)間是一段東西向的單行車(chē)道，現(xiàn)要設(shè)計(jì)一 個(gè)自動(dòng)管理系統(tǒng)，管理規(guī)則如下：當(dāng)個(gè)自動(dòng)管理系統(tǒng)，管理規(guī)則如下：當(dāng)abab間有車(chē)輛在間有車(chē)輛在 行駛時(shí)同方向的車(chē)可以同時(shí)駛?cè)胄旭倳r(shí)同方向的車(chē)可以同時(shí)駛?cè)隺bab段，但另一方向段，但另一方向 的車(chē)必須在的車(chē)必須在abab段外等待；當(dāng)段外等待；當(dāng)abab之間無(wú)車(chē)時(shí)，到達(dá)之間無(wú)車(chē)時(shí)，到達(dá)a a （或（或b b）的車(chē)輛可以進(jìn)入）的車(chē)輛可以進(jìn)入abab段，但不能從段，但不能從a a，b b點(diǎn)同點(diǎn)同 時(shí)駛

9、入；當(dāng)某方向在時(shí)駛?cè)?；?dāng)某方向在abab段行駛的車(chē)輛使出了段行駛的車(chē)輛使出了abab段且段且 無(wú)車(chē)輛進(jìn)入無(wú)車(chē)輛進(jìn)入abab段時(shí)，應(yīng)讓另一方向等待的車(chē)輛進(jìn)入段時(shí)，應(yīng)讓另一方向等待的車(chē)輛進(jìn)入 abab段行駛。請(qǐng)用段行駛。請(qǐng)用wait,signalwait,signal工具對(duì)工具對(duì)abab段實(shí)現(xiàn)正確段實(shí)現(xiàn)正確 管理。管理。 進(jìn)程管理進(jìn)程管理 Semaphore s, mutexab,mutexba Pab： Wait(mutexab) Countab+ If countab=1 then wait(s); Signal(mutexab) . wait(mutexab) countab- -; if

10、countab=0 then signal(s) signal(mutexab); 進(jìn)程管理進(jìn)程管理 Pba: wait(mutexba) countba=countba+1; If countba=1 then wait(s) signal(mutexba) enter; wait(mutexba) countba-; if countba=0 then signal(s) signal(mutexba); 進(jìn)程管理進(jìn)程管理 v蘋(píng)果桔子問(wèn)題：桌上有一只盤(pán)子，最 多可以容納兩個(gè)水果，每次只能放入/ 取出一只水果；爸爸專(zhuān)向盤(pán)子中放蘋(píng) 果(apple)，媽媽專(zhuān)向盤(pán)子中放桔子 (orange)，兩個(gè)

11、兒子專(zhuān)等吃盤(pán)子中的桔 子，兩個(gè)女兒專(zhuān)等吃盤(pán)子里的蘋(píng)果。 請(qǐng)用P，V操作來(lái)實(shí)現(xiàn)爸爸、媽媽兒子 、女兒之間的同步和互斥。（南京大 學(xué)2000年） 進(jìn)程管理進(jìn)程管理 main()main() tpyedeftpyedef intint semaphore; ; semaphore emptyempty； / /* * 盤(pán)子里可以放幾個(gè)水果盤(pán)子里可以放幾個(gè)水果 * */ / semaphore orange; /orange; /* * 盤(pán)子里有桔子盤(pán)子里有桔子 * */ / semaphore apple; /apple; /* * 盤(pán)子里有蘋(píng)果盤(pán)子里有蘋(píng)果 * */ / semaphore mut

12、ex; / /* *不能同時(shí)對(duì)盤(pán)子操作的互不能同時(shí)對(duì)盤(pán)子操作的互 斥量斥量 empty = 2; /= 2; /* * 盤(pán)子里允許放一個(gè)水果盤(pán)子里允許放一個(gè)水果* */ / orange =0; /=0; /* * 盤(pán)子里沒(méi)有桔子盤(pán)子里沒(méi)有桔子 * */ / apple = 0; /= 0; /* * 盤(pán)子里沒(méi)有蘋(píng)果盤(pán)子里沒(méi)有蘋(píng)果* */ / mutexmutex=1=1 cobegin/*可并發(fā)的進(jìn)程可并發(fā)的進(jìn)程*/ father(); mother(); son(); daugher(); coend 進(jìn)程管理進(jìn)程管理 father()father() while( while(手中還有蘋(píng)

13、果手中還有蘋(píng)果) ) P(empty); P(mutex)； 向盤(pán)中放蘋(píng)果向盤(pán)中放蘋(píng)果； V(mutex)； V(apple); mother()mother() while( while(手中手中還有桔子還有桔子) ) P(empty); P(mutex)； 向盤(pán)中放桔子向盤(pán)中放桔子； V(mutex)； V(orange); 進(jìn)程管理進(jìn)程管理 soni()/isoni()/i=1=1，2 2 while(while(盤(pán)中還有蘋(píng)果盤(pán)中還有蘋(píng)果) ) P(apple); P(mutex)； 從盤(pán)中拿蘋(píng)果從盤(pán)中拿蘋(píng)果； V(mutex)； V(empty); daugheridaugheri()

14、 () /i=1，2 while( while(盤(pán)中還有桔子盤(pán)中還有桔子) ) P(orange); P(mutex)； 從盤(pán)中拿桔子從盤(pán)中拿桔子； V(mutex)； V(empty); 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 producer: begin repeat Produce an item in nextp; 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 練習(xí)練習(xí) v 有4個(gè)進(jìn)程共享同一程序段，且每次最多允許3個(gè)

15、進(jìn)程進(jìn)入該程序段，則信號(hào)量的變化范圍是（ ）。 A3，2，1，0B3，2，1，0，-1 C4，3，2，1，0 D2，1，0，-1，-2 進(jìn)程管理進(jìn)程管理 v理發(fā)店里有一位理發(fā)師、一把理發(fā)椅子和五把供等 候理發(fā)的顧客坐的椅子。如果沒(méi)有顧客，理發(fā)師便 在理發(fā)椅上睡覺(jué)。當(dāng)一個(gè)顧客到來(lái)時(shí)，他必須先叫 醒理發(fā)師，如果理發(fā)師正在理發(fā)時(shí)又有顧客來(lái)到， 而如果有空椅子可坐，他們就坐下來(lái)等，如果沒(méi)有 空椅子，他就離開(kāi)。請(qǐng)為理發(fā)師和顧客各編寫(xiě)一段 程序來(lái)描述他們行為，并用wait和signal原語(yǔ)或p、v 操作實(shí)現(xiàn)其同步。 進(jìn)程管理進(jìn)程管理 #define CHAIRS 5 /*為等候的顧客準(zhǔn)備椅子數(shù)為等候的顧客

16、準(zhǔn)備椅子數(shù)*/ typedef int semaphore; /* 信號(hào)量類(lèi)型信號(hào)量類(lèi)型*/ semphore customers=0; /*等候服務(wù)的顧客數(shù)等候服務(wù)的顧客數(shù)*/ semaphore barbers=1 /*等候服務(wù)的理發(fā)師數(shù)等候服務(wù)的理發(fā)師數(shù)*/ semaphore mutex=1; /*用于互斥用于互斥*/ int waiting=0; /*還沒(méi)理發(fā)的等候顧客還沒(méi)理發(fā)的等候顧客*/ void barber (void) while(TRUE) wait(customers); /*如果顧客數(shù)是如果顧客數(shù)是0，則睡覺(jué)，則睡覺(jué)*/ wait(mutex); /*要求進(jìn)程等候要求

17、進(jìn)程等候*/ waiting=waiting-1; /*等候顧客數(shù)減等候顧客數(shù)減1*/ signal(mutex); /*釋放等候釋放等候*/ cut_hair(); /*理發(fā)（非臨界區(qū)操作）理發(fā)（非臨界區(qū)操作）*/ signal(barbers); /*一個(gè)理發(fā)師現(xiàn)在開(kāi)始理發(fā)一個(gè)理發(fā)師現(xiàn)在開(kāi)始理發(fā)*/ 進(jìn)程管理進(jìn)程管理 void customers (void) wait(mutex); if (waitingCHAIRS) waiting=waiting+1; signal(customers); signal(mutex); wait(barbers); else signal(mutex); 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 進(jìn)程管理進(jìn)程管理 mq mutex sm sender:A size:5 text:Hello send(B,a) sender :A size :5 text:hello next:0 發(fā)送區(qū)發(fā)送區(qū)Asender:A size:5 text:Hello receive(b) 接收區(qū)接收區(qū)B a b 進(jìn)程進(jìn)程A PCB(B