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

1、進(jìn)程管理進(jìn)程管理I1C1P1I2C2P2進(jìn)程管理進(jìn)程管理P1P2P3P4進(jìn)程管理進(jìn)程管理I1I2I3I4C1C2C3C4P1P2P3P4t進(jìn)程管理進(jìn)程管理進(jìn)程管理進(jìn)程管理進(jìn)程管理進(jìn)程管理進(jìn)程管理進(jìn)程管理進(jìn)程管理進(jìn)程管理就緒就緒阻塞阻塞執(zhí)行執(zhí)行時間片完時間片完進(jìn)程調(diào)度進(jìn)程調(diào)度I/O請求請求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í)行活動活動就緒就緒靜止靜止就緒就緒活動活動阻塞阻塞靜止靜止阻塞阻塞激活激活掛起掛起激活激活掛起掛起釋放釋放釋放釋放掛起掛起請求請求I/O進(jìn)程管理進(jìn)程管理v寫一個程序描述進(jìn)程狀態(tài)遷移過程。寫一個程序描

2、述進(jìn)程狀態(tài)遷移過程。v要求：要求： 提供導(dǎo)致進(jìn)程狀態(tài)變化的調(diào)用接口，包括創(chuàng)建、提供導(dǎo)致進(jìn)程狀態(tài)變化的調(diào)用接口，包括創(chuàng)建、刪除、調(diào)度、阻塞、時間到、掛起、激活等。刪除、調(diào)度、阻塞、時間到、掛起、激活等。 實現(xiàn)進(jìn)程列表顯示的接口。實現(xiàn)進(jìn)程列表顯示的接口。 注：這里設(shè)計的進(jìn)程是一個假設(shè)的對象實體，是注：這里設(shè)計的進(jìn)程是一個假設(shè)的對象實體，是由程序自己創(chuàng)建和刪除，不是系統(tǒng)維護(hù)的進(jìn)程。由程序自己創(chuàng)建和刪除，不是系統(tǒng)維護(hù)的進(jìn)程。進(jìn)程管理進(jìn)程管理pid現(xiàn)場現(xiàn)場進(jìn)程狀態(tài)進(jìn)程狀態(tài)優(yōu)先級優(yōu)先級阻塞原因阻塞原因程序地址程序地址同步機制同步機制資源清單資源清單鏈接指針鏈接指針進(jìn)程管理進(jìn)程管理執(zhí)行指針執(zhí)行指針就緒隊列指

3、針就緒隊列指針阻塞隊列指針阻塞隊列指針空閑隊列指針空閑隊列指針PCB14PCB23PCB30PCB48PCB5PCB67PCB79PCB80PCB91進(jìn)程管理進(jìn)程管理structstruct wait_queuewait_queue structstruct task_structtask_struct * * task; task;structstruct wait_queuewait_queue * * next; next;PCBPCBPCB進(jìn)程管理進(jìn)程管理PCB1PCB2PCB3PCB4PCB5PCB6PCB7執(zhí)行指針執(zhí)行指針就緒表指針就緒表指針阻塞表指針阻塞表指針進(jìn)程管理進(jìn)程管理進(jìn)程

4、管理進(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:=counter+1;until false;consumer: repeatwhile counter=0 do no-op;nextc:=bufferout;out:=(out+1) mod n;counte

5、r:=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 n do si:=si-1; endforelseplace the process in the waiting queue with the first si found with si1, and set the program count

6、of this process to the beginning of swait operationend 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 the ready queue endfor進(jìn)程管理進(jìn)程管理進(jìn)程管理進(jìn)程管理進(jìn)程管理進(jìn)程管理進(jìn)程管理進(jìn)程管理S1S2S3S4S5S6abcdegf進(jìn)程管理進(jìn)程管理進(jìn)程管理進(jìn)程管理練習(xí)：已知一個求知公式 （A2+3B）/（B+5A），若A，B已賦值，試畫出求值過

7、程的前趨圖，并用信號量描述前驅(qū)關(guān)系。進(jìn)程管理進(jìn)程管理v練習(xí)：兩位同學(xué)約好練習(xí)：兩位同學(xué)約好星期天去東湖，早上星期天去東湖，早上8:00在校門口，不見在校門口，不見不散。不散。當(dāng)一個同學(xué)先當(dāng)一個同學(xué)先來到校門口，要等另一來到校門口，要等另一個同學(xué)，到齊后一道打個同學(xué)，到齊后一道打的去東湖。請用用信號的去東湖。請用用信號量知識實現(xiàn)同步。量知識實現(xiàn)同步。南昌航空大學(xué)進(jìn)程管理進(jìn)程管理va,ba,b 兩點間是一段東西向的單行車道，現(xiàn)要設(shè)計一兩點間是一段東西向的單行車道，現(xiàn)要設(shè)計一個自動管理系統(tǒng)，管理規(guī)則如下：當(dāng)個自動管理系統(tǒng)，管理規(guī)則如下：當(dāng)abab間有車輛在間有車輛在行駛時同方向的車可以同時駛?cè)胄旭倳r

8、同方向的車可以同時駛?cè)隺bab段，但另一方向段，但另一方向的車必須在的車必須在abab段外等待；當(dāng)段外等待；當(dāng)abab之間無車時，到達(dá)之間無車時，到達(dá)a a（或（或b b）的車輛可以進(jìn)入）的車輛可以進(jìn)入abab段，但不能從段，但不能從a a，b b點同點同時駛?cè)?；?dāng)某方向在時駛?cè)耄划?dāng)某方向在abab段行駛的車輛使出了段行駛的車輛使出了abab段且段且無車輛進(jìn)入無車輛進(jìn)入abab段時，應(yīng)讓另一方向等待的車輛進(jìn)入段時，應(yīng)讓另一方向等待的車輛進(jìn)入abab段行駛。請用段行駛。請用wait,signalwait,signal工具對工具對abab段實現(xiàn)正確段實現(xiàn)正確管理。管理。進(jìn)程管理進(jìn)程管理Semaph

9、ore s, mutexab,mutexbaPab：Wait(mutexab)Countab+If countab=1 then wait(s);Signal(mutexab) .wait(mutexab)countab- -;if 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)sign

10、al(mutexba);進(jìn)程管理進(jìn)程管理v蘋果桔子問題：桌上有一只盤子，最多可以容納兩個水果，每次只能放入/取出一只水果；爸爸專向盤子中放蘋果(apple)，媽媽專向盤子中放桔子(orange)，兩個兒子專等吃盤子中的桔子，兩個女兒專等吃盤子里的蘋果。請用P，V操作來實現(xiàn)爸爸、媽媽兒子、女兒之間的同步和互斥。（南京大學(xué)2000年）進(jìn)程管理進(jìn)程管理main()main() tpyedeftpyedef intint semaphore; ; semaphore emptyempty； / /* * 盤子里可以放幾個水果盤子里可以放幾個水果 * */ / semaphore orange; /or

11、ange; /* * 盤子里有桔子盤子里有桔子 * */ / semaphore apple; /apple; /* * 盤子里有蘋果盤子里有蘋果 * */ / semaphore mutex; / /* *不能同時對盤子操作的互不能同時對盤子操作的互斥量斥量 empty = 2; /= 2; /* * 盤子里允許放一個水果盤子里允許放一個水果* */ / orange =0; /=0; /* * 盤子里沒有桔子盤子里沒有桔子 * */ / apple = 0; /= 0; /* * 盤子里沒有蘋果盤子里沒有蘋果* */ / mutexmutex=1=1 cobegin/*可并發(fā)的進(jìn)程可并發(fā)的

12、進(jìn)程*/ father(); mother(); son(); daugher(); coend進(jìn)程管理進(jìn)程管理father()father() while( while(手中還有蘋果手中還有蘋果) ) P(empty); P(mutex)； 向盤中放蘋果向盤中放蘋果； V(mutex)； V(apple); mother()mother() while( while(手中手中還有桔子還有桔子) ) P(empty); P(mutex)； 向盤中放桔子向盤中放桔子； V(mutex)； V(orange); 進(jìn)程管理進(jìn)程管理soni()/isoni()/i=1=1，2 2 while(whil

13、e(盤中還有蘋果盤中還有蘋果) ) P(apple); P(mutex)； 從盤中拿蘋果從盤中拿蘋果； V(mutex)； V(empty); daugheridaugheri() () /i=1，2 while( while(盤中還有桔子盤中還有桔子) ) P(orange); P(mutex)； 從盤中拿桔子從盤中拿桔子； 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)程

14、管理進(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個進(jìn)程共享同一程序段，且每次最多允許3個進(jìn)程進(jìn)入該程序段，則信號量的變化范圍是（ ）。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ā)的顧客坐的椅子。如果沒有顧客，理發(fā)師便在理發(fā)椅上睡覺。當(dāng)一個顧客到來時，他必須先叫醒理發(fā)師，如果理發(fā)師正在理發(fā)時又有顧客來到，而如果有空椅子可坐，他們就坐下來等，如果沒有空椅子，他就離開。請為理發(fā)師和顧客各編寫一段程序來描述他們行為，并用wait和si

15、gnal原語或p、v操作實現(xiàn)其同步。 進(jìn)程管理進(jìn)程管理#define CHAIRS 5 /*為等候的顧客準(zhǔn)備椅子數(shù)為等候的顧客準(zhǔn)備椅子數(shù)*/typedef int semaphore; /* 信號量類型信號量類型*/semphore customers=0; /*等候服務(wù)的顧客數(shù)等候服務(wù)的顧客數(shù)*/semaphore barbers=1 /*等候服務(wù)的理發(fā)師數(shù)等候服務(wù)的理發(fā)師數(shù)*/semaphore mutex=1; /*用于互斥用于互斥*/int waiting=0; /*還沒理發(fā)的等候顧客還沒理發(fā)的等候顧客*/void barber (void) while(TRUE) wait(cust

16、omers); /*如果顧客數(shù)是如果顧客數(shù)是0，則睡覺，則睡覺*/ wait(mutex); /*要求進(jìn)程等候要求進(jìn)程等候*/ waiting=waiting-1; /*等候顧客數(shù)減等候顧客數(shù)減1*/ signal(mutex); /*釋放等候釋放等候*/cut_hair(); /*理發(fā)（非臨界區(qū)操作）理發(fā)（非臨界區(qū)操作）*/signal(barbers); /*一個理發(fā)師現(xiàn)在開始理發(fā)一個理發(fā)師現(xiàn)在開始理發(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)程管理mqmutexsmsender:Asize:5text:Hellosend(B,a)sender :Asize :5text:hellonext:0發(fā)送區(qū)發(fā)送區(qū)Asender:Asize:5text:Helloreceive(b)接收區(qū)接收區(qū)B