進(jìn)程管理實(shí)驗(yàn)

1、進(jìn)程管理實(shí)驗(yàn) 本系統(tǒng)的同步機(jī)構(gòu)采用信號(hào)量上的本系統(tǒng)的同步機(jī)構(gòu)采用信號(hào)量上的P、V操作的機(jī)制；控制機(jī)操作的機(jī)制；控制機(jī)構(gòu)包括：構(gòu)包括： （1)阻塞和喚醒操作；阻塞和喚醒操作； （2)時(shí)間片中斷處理程序模擬時(shí)間片中斷；時(shí)間片中斷處理程序模擬時(shí)間片中斷； （3)進(jìn)程調(diào)度程序負(fù)責(zé)為各進(jìn)程分配處理機(jī)。進(jìn)程調(diào)度程序負(fù)責(zé)為各進(jìn)程分配處理機(jī)。 系統(tǒng)中涉及了系統(tǒng)中涉及了3個(gè)并發(fā)進(jìn)程。它們之間的關(guān)系是：個(gè)并發(fā)進(jìn)程。它們之間的關(guān)系是： （1) 3個(gè)進(jìn)程需要互斥使用臨界資源個(gè)進(jìn)程需要互斥使用臨界資源S2。 （2)進(jìn)程進(jìn)程12又需互斥使用臨界資源又需互斥使用臨界資源S1 本系統(tǒng)在運(yùn)行過程中隨機(jī)打印出各進(jìn)程的狀態(tài)變換過程

2、，系統(tǒng)本系統(tǒng)在運(yùn)行過程中隨機(jī)打印出各進(jìn)程的狀態(tài)變換過程，系統(tǒng)的調(diào)度過程及公共變量的變化情況。的調(diào)度過程及公共變量的變化情況。題目題目系統(tǒng)為進(jìn)程設(shè)置了系統(tǒng)為進(jìn)程設(shè)置了5種運(yùn)行狀態(tài)：種運(yùn)行狀態(tài)： e執(zhí)行態(tài)；執(zhí)行態(tài)；r高就緒態(tài)；高就緒態(tài)；t低就緒態(tài)（執(zhí)行進(jìn)程因時(shí)間低就緒態(tài)（執(zhí)行進(jìn)程因時(shí)間片到限而轉(zhuǎn)入）；片到限而轉(zhuǎn)入）；w等待態(tài)；等待態(tài)；c完成態(tài)。各進(jìn)程的初始完成態(tài)。各進(jìn)程的初始狀態(tài)均設(shè)置為狀態(tài)均設(shè)置為r. 系統(tǒng)分時(shí)執(zhí)行各進(jìn)程，并規(guī)定系統(tǒng)分時(shí)執(zhí)行各進(jìn)程，并規(guī)定3個(gè)進(jìn)程的執(zhí)行概率均為個(gè)進(jìn)程的執(zhí)行概率均為33。通過產(chǎn)生隨機(jī)數(shù)。通過產(chǎn)生隨機(jī)數(shù)x來模擬時(shí)間片。當(dāng)進(jìn)程來模擬時(shí)間片。當(dāng)進(jìn)程process1訪問隨訪

3、問隨機(jī)數(shù)機(jī)數(shù)x時(shí)，若時(shí)，若x=0.33；當(dāng)進(jìn)程；當(dāng)進(jìn)程process2訪問訪問x時(shí)，若時(shí)，若x=0.66;當(dāng)進(jìn)程當(dāng)進(jìn)程process3訪問訪問x時(shí)，若時(shí)，若x0.66，則分別認(rèn)為，則分別認(rèn)為各進(jìn)程的執(zhí)行時(shí)間片到限，產(chǎn)生各進(jìn)程的執(zhí)行時(shí)間片到限，產(chǎn)生“時(shí)間片中斷時(shí)間片中斷”而轉(zhuǎn)入低就而轉(zhuǎn)入低就緒態(tài)緒態(tài)t?；舅悸坊舅悸?進(jìn)程調(diào)度算法采用剝奪式最高優(yōu)先數(shù)法。各進(jìn)程的優(yōu)先數(shù)通過進(jìn)程調(diào)度算法采用剝奪式最高優(yōu)先數(shù)法。各進(jìn)程的優(yōu)先數(shù)通過鍵盤輸入予以靜態(tài)設(shè)置。調(diào)度程序每次總是選擇優(yōu)先數(shù)最?。▋?yōu)鍵盤輸入予以靜態(tài)設(shè)置。調(diào)度程序每次總是選擇優(yōu)先數(shù)最小（優(yōu)先權(quán)最高）的就緒進(jìn)程投入執(zhí)行。先從先權(quán)最高）的就緒進(jìn)程投入執(zhí)

4、行。先從r狀態(tài)進(jìn)程中選擇，再從狀態(tài)進(jìn)程中選擇，再從t狀態(tài)進(jìn)程中選擇。當(dāng)現(xiàn)行進(jìn)程喚醒某個(gè)等待進(jìn)程，且被喚醒進(jìn)程狀態(tài)進(jìn)程中選擇。當(dāng)現(xiàn)行進(jìn)程喚醒某個(gè)等待進(jìn)程，且被喚醒進(jìn)程的優(yōu)先數(shù)小于現(xiàn)行進(jìn)程時(shí)，則剝奪現(xiàn)行進(jìn)程的執(zhí)行權(quán)。的優(yōu)先數(shù)小于現(xiàn)行進(jìn)程時(shí)，則剝奪現(xiàn)行進(jìn)程的執(zhí)行權(quán)。 各進(jìn)程在使用臨界資源各進(jìn)程在使用臨界資源S1和和S2時(shí)，通過調(diào)用信號(hào)量時(shí)，通過調(diào)用信號(hào)量sem1和和sem2上的上的P、V操作來實(shí)現(xiàn)同步。阻塞和喚醒操作負(fù)責(zé)完成操作來實(shí)現(xiàn)同步。阻塞和喚醒操作負(fù)責(zé)完成從進(jìn)程的執(zhí)行態(tài)到等待態(tài)以及從等待態(tài)到就緒態(tài)的轉(zhuǎn)換。從進(jìn)程的執(zhí)行態(tài)到等待態(tài)以及從等待態(tài)到就緒態(tài)的轉(zhuǎn)換。 系統(tǒng)啟動(dòng)后，在完成必要的系統(tǒng)初始化后便

5、執(zhí)行進(jìn)程調(diào)度程系統(tǒng)啟動(dòng)后，在完成必要的系統(tǒng)初始化后便執(zhí)行進(jìn)程調(diào)度程序。當(dāng)執(zhí)行進(jìn)程因序。當(dāng)執(zhí)行進(jìn)程因“時(shí)間片中斷時(shí)間片中斷”，或被排斥使用臨界資源，或，或被排斥使用臨界資源，或喚醒某個(gè)進(jìn)程時(shí)，立即進(jìn)行進(jìn)程調(diào)度。當(dāng)喚醒某個(gè)進(jìn)程時(shí)，立即進(jìn)行進(jìn)程調(diào)度。當(dāng)3個(gè)進(jìn)程都處于完成狀個(gè)進(jìn)程都處于完成狀態(tài)后，系統(tǒng)退出運(yùn)行。態(tài)后，系統(tǒng)退出運(yùn)行。 基本思路基本思路 （1）每個(gè)進(jìn)程有一個(gè)進(jìn)程控制塊）每個(gè)進(jìn)程有一個(gè)進(jìn)程控制塊PCB，內(nèi)容包括：，內(nèi)容包括：id進(jìn)程標(biāo)識(shí)號(hào)，進(jìn)程標(biāo)識(shí)號(hào)，id0，1，2；status進(jìn)程狀態(tài)，可為進(jìn)程狀態(tài)，可為e，r，t，w，c；priority 進(jìn)程優(yōu)先數(shù)；進(jìn)程優(yōu)先數(shù)；nextwr 等待鏈指針

6、，指示在同一信號(hào)量上等待的下一等待鏈指針，指示在同一信號(hào)量上等待的下一個(gè)進(jìn)程的標(biāo)識(shí)號(hào)。個(gè)進(jìn)程的標(biāo)識(shí)號(hào)。 （2）信號(hào)量）信號(hào)量semaphore，對(duì)應(yīng)于臨界資源，對(duì)應(yīng)于臨界資源S1和和S2分別有分別有sem1和和sem2，均為互斥信號(hào)量，內(nèi)容包括：，均為互斥信號(hào)量，內(nèi)容包括： value 信號(hào)量，初值為信號(hào)量，初值為1； firstwr 等待鏈?zhǔn)字羔?，指示在同一信?hào)量上等待的下一個(gè)等待鏈?zhǔn)字羔?，指示在同一信?hào)量上等待的下一個(gè)進(jìn)程的標(biāo)識(shí)數(shù)。進(jìn)程的標(biāo)識(shí)數(shù)。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) （3）現(xiàn)場(chǎng)保留區(qū)，用數(shù)組）現(xiàn)場(chǎng)保留區(qū)，用數(shù)組savearea34表示。即每個(gè)進(jìn)程表示。即每個(gè)進(jìn)程都有一個(gè)大小為都有一個(gè)大小為4個(gè)

7、單元的保留區(qū)，用來保存被個(gè)單元的保留區(qū)，用來保存被“中斷中斷”時(shí)時(shí)的現(xiàn)場(chǎng)信息，如通用寄存器的內(nèi)容和斷點(diǎn)地址等。的現(xiàn)場(chǎng)信息，如通用寄存器的內(nèi)容和斷點(diǎn)地址等。 此外，系統(tǒng)中還用到下列主要全程變量：此外，系統(tǒng)中還用到下列主要全程變量： exe執(zhí)行進(jìn)程指針，其值為進(jìn)程標(biāo)識(shí)號(hào)；執(zhí)行進(jìn)程指針，其值為進(jìn)程標(biāo)識(shí)號(hào)； i用來模擬一個(gè)通用寄存器；用來模擬一個(gè)通用寄存器； addr用來模擬程序計(jì)數(shù)器；用來模擬程序計(jì)數(shù)器； s1,s2兩個(gè)公共變量，用作共享臨界資源兩個(gè)公共變量，用作共享臨界資源 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)const MAXPRI=100; NIL=-1;TYPE procp=record PCB類型類型 id:

8、integer; status:char; 進(jìn)程號(hào)進(jìn)程號(hào),進(jìn)程狀態(tài)進(jìn)程狀態(tài) nextwr:integer; mess:message; 等待號(hào)等待號(hào),消息隊(duì)指針消息隊(duì)指針 inum:integer; addr:char; 運(yùn)行次數(shù)運(yùn)行次數(shù),返回地址返回地址 priority:integer; end; 優(yōu)先數(shù)優(yōu)先數(shù) message=messagetp; 指向消息塊指針類型指向消息塊指針類型 messagetp=record 消息塊類型消息塊類型(信息信息,指針指針,發(fā)送者號(hào)發(fā)送者號(hào)) num:integer; next:message; pro:integer; end; semaphorel

9、=record 信號(hào)量類型信號(hào)量類型(信號(hào)量信號(hào)量,等待隊(duì)頭號(hào)等待隊(duì)頭號(hào)) value:integer; firstwr:integer; end;VAR pcb:array1.3 of procb; PCB表表 sem:array1.2 of semaphorel; 信號(hào)量表信號(hào)量表 addr:char; i,seed,exe:integer; 當(dāng)前進(jìn)程地址當(dāng)前進(jìn)程地址,運(yùn)行次數(shù)運(yùn)行次數(shù),隨機(jī)變量隨機(jī)變量,當(dāng)前運(yùn)行進(jìn)程號(hào)當(dāng)前運(yùn)行進(jìn)程號(hào)program processc(input,output);var q,p:message; 工作指針工作指針 begin new(p); p.num:=sn

10、um; 申請(qǐng)消息塊申請(qǐng)消息塊,寫入緩沖寫入緩沖 p.next:=NIL; :=sender; 下一指針置空下一指針置空,置發(fā)送者置發(fā)送者 writeln(send message to process ,receiver); writeln(process ,sender,already run ,snum, times); q:=pcbreceiver.mess; q指向接收者消息等待隊(duì)列首指向接收者消息等待隊(duì)列首 if(q=NIL) then pcbreceiver.mess:=p q空則空則p插入隊(duì)首插入隊(duì)首 else begin while(q.nextNIL) do q:=

11、q.next; q移到隊(duì)尾移到隊(duì)尾 q.next:=p; 將將p鏈接到隊(duì)尾鏈接到隊(duì)尾 end; end;proc send(sender, receiver, snum:integer); 發(fā)送發(fā)送var p,q:message; 工作指針工作指針begin p:=pcbreceiver.mess; p指向接收者消息等待隊(duì)列首指向接收者消息等待隊(duì)列首 while(pNIL) do begin 顯示發(fā)送者和接收者信息顯示發(fā)送者和接收者信息 writeln(receive message from process ,); writeln(process ,,is already

12、 run, p.num,times); q=p; 陸續(xù)將接收過的的消息塊刪除并釋放陸續(xù)將接收過的的消息塊刪除并釋放 p:=p.next; dispose(q) end; pcbreceiver.mess:=NIL; 接收完后消息等待隊(duì)列置空接收完后消息等待隊(duì)列置空end; proce receive(receiver:integer); 接收接收var j:integer;begin for j:=1 to 3 do 初始化各進(jìn)程控制塊初始化各進(jìn)程控制塊 begin pcbj.id:=j; pcbj.status:=r; 進(jìn)程號(hào)進(jìn)程號(hào),進(jìn)程狀態(tài)進(jìn)程狀態(tài) pcbj.nextwr:=NIL; pc

13、bj.mess:=NIL; 等待等待,消息指針消息指針 write(process, j,priority?); readln(pcbj.priority); 讀入優(yōu)先數(shù)讀入優(yōu)先數(shù) pcbj.inum:=0; pcbj.addr:=0; 運(yùn)行次數(shù)運(yùn)行次數(shù), 地址地址 end; sem1.value:=1; sem1.firstwr:=NIL; 對(duì)信號(hào)量初始化對(duì)信號(hào)量初始化 sem2.value:=1; sem2.firstwr:=NIL; exe:=NIL; 當(dāng)前執(zhí)行進(jìn)程號(hào)置為空當(dāng)前執(zhí)行進(jìn)程號(hào)置為空end;proce init; 初始化初始化func random:real; proc eex

14、it(n:integer);func random:real; 產(chǎn)生產(chǎn)生01之間的隨機(jī)數(shù)之間的隨機(jī)數(shù)var m:integer; begin seed為為integer 型型,實(shí)際值在實(shí)際值在-32768到到32767之間之間 if seed0 then m:=-seed else m:=-seed; seed:=(25171*seed+13841) mod 65536; random:=m/32767.0 end;proce eexit(n:integer); 退出退出 begin pcbn.status:=c; 本進(jìn)程置為完成態(tài)本進(jìn)程置為完成態(tài) writeln(process,n,is c

15、ompleted !); exe:=NIL; 當(dāng)前執(zhí)行進(jìn)程號(hào)置空當(dāng)前執(zhí)行進(jìn)程號(hào)置空 end;func find:integer; 選進(jìn)程選進(jìn)程 var j, pd, w: integer;begin pd:=NIL; W:=MAXPRI; for j:=1 to 3 do 先在高就緒態(tài)中找優(yōu)先數(shù)最小的進(jìn)程先在高就緒態(tài)中找優(yōu)先數(shù)最小的進(jìn)程 if pcbj.status=r then if pcbj.priorityw then begin w:=pcbj.priority; pd:=j end; if pd=NIL then for j:=1 to 3 do 再在低就緒態(tài)中找優(yōu)先數(shù)最小的進(jìn)程再在

16、低就緒態(tài)中找優(yōu)先數(shù)最小的進(jìn)程 if pcbj.status=t then if pcbj.priorityw then begin w:=pcbj.priority; pd:=j end; find:=pd 返回進(jìn)程號(hào)返回進(jìn)程號(hào)end;func scheduler:integer; 調(diào)度調(diào)度 var pd:integer;begin pd:=find; 找優(yōu)先進(jìn)程找優(yōu)先進(jìn)程 if (pdNIL) or (exeNIL) then begin if pdNIL then 若有就緒進(jìn)程則若有就緒進(jìn)程則 if exe=NIL then 若無當(dāng)前執(zhí)行進(jìn)程則若無當(dāng)前執(zhí)行進(jìn)程則 begin pcbpd.s

17、tatus:=e; exe:=pd; 新進(jìn)程置執(zhí)行態(tài)新進(jìn)程置執(zhí)行態(tài) writeln(process,exe,is executing); end else if pcbpd.prioritypcbexe.priority then 切切換換 begin pcbexe.status:=r; 原執(zhí)行進(jìn)程置高就緒態(tài)原執(zhí)行進(jìn)程置高就緒態(tài) writeln(process,exe,enter into ready); pcbpd.status:=e; exe:=pd; 新進(jìn)程置執(zhí)行態(tài)新進(jìn)程置執(zhí)行態(tài) writeln(process,exe,is executing); end; i:=pcbexe.inum

18、; addr:=pcbexe.addr; 恢復(fù)現(xiàn)場(chǎng)恢復(fù)現(xiàn)場(chǎng) end scheduler:=exe; 返回當(dāng)前執(zhí)行進(jìn)程號(hào)返回當(dāng)前執(zhí)行進(jìn)程號(hào)end; proce block三三; 阻塞阻塞 proce wakeup三三; 喚醒喚醒proce block(se:integer); var w:integer; 工作指針工作指針begin writeln(process,exe,is block); pcbexe.status:=w; pcbexe.nextwr=NIL; 置阻塞態(tài)置阻塞態(tài) w:=semse.firstwr; 信號(hào)量等待隊(duì)列頭指針賦給信號(hào)量等待隊(duì)列頭指針賦給w if w=NIL the

19、n semse.firstwr:=exe 空則當(dāng)前進(jìn)程作隊(duì)頭空則當(dāng)前進(jìn)程作隊(duì)頭 else begin while(pcbw.nextwrNIL) do w:=pcbw.nextwr; 指針后推到隊(duì)尾指針后推到隊(duì)尾 pcbw.nextwr:=exe 當(dāng)前進(jìn)程鏈接到隊(duì)尾當(dāng)前進(jìn)程鏈接到隊(duì)尾 end;end;proce wakeup(se:integer); var w:integer; begin w:=semse.firstwr; 隊(duì)列頭指針賦給隊(duì)列頭指針賦給w if wNIL then begin 非空則摘下首塊非空則摘下首塊 semse.firstwr:=pcbw.nextwr; 重鏈接重鏈接

20、 pcbw.status:=r; 置為高就緒態(tài)置為高就緒態(tài) writeln(process,exe,is wakeup); end; end;func p( ); func v( ); funct p(se:integer;ad:char):boolean; wait操作操作 begin semse.value:=semse.value-1; 信號(hào)量減信號(hào)量減1 if semse.value=0 then p:=false 有資源不等有資源不等待待 else begin block(se); 阻塞到阻塞到 se 等待隊(duì)列等待隊(duì)列 pcbexe.inum:=i; pcbexe.addr:=ad;

21、 保護(hù)現(xiàn)場(chǎng)保護(hù)現(xiàn)場(chǎng) exe:=NIL; p:=true 執(zhí)行進(jìn)程置空?qǐng)?zhí)行進(jìn)程置空,等待標(biāo)志置真等待標(biāo)志置真 end; end;function v(se:integer;ad:char):boolean; signal操作操作 begin semse.value:=semse.value+1; 信號(hào)量加信號(hào)量加1 if semse.value0 then v:=false 無等待不重新調(diào)無等待不重新調(diào)度度 else begin wakeup(se); 有等待喚醒有等待喚醒 se 等待隊(duì)列的進(jìn)程等待隊(duì)列的進(jìn)程 pcbexe.inum:=i; pcbexe.addr:=ad; 保護(hù)現(xiàn)場(chǎng)保護(hù)現(xiàn)場(chǎng) v

22、:=true 要重新調(diào)度要重新調(diào)度 end;end;function timeint(ad:char):boolean; 模擬時(shí)間片中斷模擬時(shí)間片中斷var x:real;begin x:=rendom; x為為01之間的隨機(jī)數(shù)之間的隨機(jī)數(shù) if (x=0.67)and(exe=3) or (x0.33)and(x0.67)and(exe=2) then timeint:=false 若在各自的時(shí)間片不產(chǎn)生中斷若在各自的時(shí)間片不產(chǎn)生中斷 else begin 否則產(chǎn)生時(shí)間片中斷否則產(chǎn)生時(shí)間片中斷 pcbexe.inum:=i; pcbexe.addr:=ad; 保護(hù)現(xiàn)場(chǎng)保護(hù)現(xiàn)場(chǎng) pcbexe.

23、status:=t; 置為低就緒態(tài)置為低就緒態(tài) writeln(Times silce interrupt.); writeln(process,exe,enter into ready); exe:=NIL; 執(zhí)行進(jìn)程置空?qǐng)?zhí)行進(jìn)程置空 timeint:=true 中斷標(biāo)志置真中斷標(biāo)志置真 end; end; procedure process1(var s1,s2:integer); 模擬并發(fā)進(jìn)程模擬并發(fā)進(jìn)程1label a1,b1,c1,d1,e1,f1,stop1;begin if addr=a then goto a1; if addr=b then goto b1; if addr=

24、c then goto c1; if addr=d then goto d1; if addr=e then goto e1; if addr=f then goto f1; while(i=5) then eexit(1); 5次循環(huán)后本進(jìn)程結(jié)束次循環(huán)后本進(jìn)程結(jié)束end; writeln(process1 calls p on sem1); if p(1,a) then goto stop1; 對(duì)信號(hào)量對(duì)信號(hào)量1進(jìn)行進(jìn)行P操作返回操作返回a地址地址a1: writeln(process1 is execution on its cretical section 1.);入臨界區(qū)入臨界區(qū) if

25、 timeint(b) then goto stop1; 若時(shí)間片到則重新調(diào)度若時(shí)間片到則重新調(diào)度b1: s1:=s1+1; writeln(s1=,s1); s1是臨界資源不是信號(hào)量是臨界資源不是信號(hào)量 writeln(process1 calls v on sem1 and quit cretical section 1); if v(1,c) then goto stop1; 對(duì)信號(hào)量對(duì)信號(hào)量1進(jìn)行進(jìn)行V操作操作,出臨界區(qū)出臨界區(qū)c1: writeln(process1 calls p on sem2); if p(2,d) then goto stop1; 對(duì)信號(hào)量對(duì)信號(hào)量2進(jìn)行進(jìn)行P

26、操作返回操作返回d地址地址d1: writeln(process1 is execution on its cretical section 2.); if timeint(e) then goto stop1;e1: s2:=s2+1; writeln(s2=,s2); s2是臨界資源不是信號(hào)量是臨界資源不是信號(hào)量 writeln(process1 calls v on sem1 and quit cretical section 2.); if v(2,f) then goto stop1; 對(duì)信號(hào)量對(duì)信號(hào)量2進(jìn)行進(jìn)行V操作操作,出臨界區(qū)出臨界區(qū)f1: writeln(process1 cyclen count=, i+1); i:=i+1; send(1,2,i); send(1,3,i); readln; 循環(huán)次數(shù)加循環(huán)次數(shù)加1,發(fā)消息發(fā)消息procedure process2(var s