【正文】 計(jì)算機(jī)操作系統(tǒng)實(shí)驗(yàn)指導(dǎo)書(shū) 1 實(shí)驗(yàn)一 進(jìn)程管理 一、目的 本課題實(shí)驗(yàn)的目的是，加深對(duì)進(jìn)程概念及進(jìn)程管理各個(gè)部分內(nèi)容的理解；熟悉進(jìn)程管理中主要數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)及進(jìn)程調(diào)度算法，進(jìn)程控制機(jī)構(gòu)，同步機(jī)構(gòu)，通信機(jī)構(gòu)的實(shí)施。 二、 題目 進(jìn)程管理 三、要求及提示 要求設(shè)置 PCB，進(jìn)程控制原語(yǔ)，進(jìn)程調(diào)度算法，能描述進(jìn)程調(diào)度中不同進(jìn)程狀態(tài)之間的轉(zhuǎn)換，設(shè)計(jì)一個(gè)允許 n個(gè)進(jìn)程并發(fā)運(yùn)行的進(jìn)程管理模擬系統(tǒng)。該系統(tǒng)包括有簡(jiǎn)單的進(jìn)程控制，同步及通信機(jī)構(gòu)，其進(jìn)程調(diào)度算法可任意選擇。每個(gè)進(jìn)程用一個(gè) PCB表示，其內(nèi)容可根據(jù)具體情況設(shè)置。各進(jìn)程之間應(yīng)有一定的同步關(guān)系。系 統(tǒng)在運(yùn)行過(guò)程中能顯示或打印各進(jìn)程的狀態(tài)及有關(guān)參數(shù)的變化情況，以便觀察諸進(jìn)程的運(yùn)行過(guò)程及系統(tǒng)的管理過(guò)程。 編程實(shí)現(xiàn)。 工具： C語(yǔ)言或其它高級(jí)語(yǔ)言 實(shí)驗(yàn)時(shí)間： 3學(xué)時(shí) 四、實(shí)驗(yàn)報(bào)告 寫出進(jìn)程管理的思想。 畫出算法流程圖和設(shè)置的數(shù)據(jù)結(jié)構(gòu)。 寫出調(diào)試程序出現(xiàn)的問(wèn)題及解決的方法。 打印實(shí)驗(yàn)報(bào)告及程序清單。 報(bào)告給出測(cè)試的結(jié)果。 五、范例 支持多個(gè)進(jìn)程并發(fā)運(yùn)行的簡(jiǎn)單進(jìn)程管理模擬系統(tǒng)。 問(wèn)題描述 本系統(tǒng)的同步機(jī)構(gòu)采用的是信號(hào)量上的 P， V操作的機(jī)制；控制機(jī)構(gòu)包括阻塞和喚醒操作；時(shí)間 片中斷處理程序處理模擬的時(shí)間片中斷；進(jìn)程調(diào)度程序負(fù)責(zé)為各進(jìn)程分配處理機(jī)。系統(tǒng)中設(shè)計(jì)了 3個(gè)并發(fā)進(jìn)程。它們之間有如下同步關(guān)系： 3 個(gè)進(jìn)程需要互斥使用臨界資源 s2，進(jìn)程 1 和進(jìn)程 2 又需互斥使用臨界資源 s1。本系統(tǒng)在運(yùn)行過(guò)程中隨機(jī)打印出各進(jìn)程的狀態(tài)變換過(guò)程，系統(tǒng)的調(diào)度過(guò)程及公共變量的變化情況。 算法 系統(tǒng)為進(jìn)程設(shè)置了 5 種運(yùn)行狀態(tài)： e－執(zhí)行態(tài)； r－高就緒態(tài)； t－低就緒態(tài)（執(zhí)行進(jìn)程因時(shí)間片到限而轉(zhuǎn)入）； w－等待態(tài)； c－完成態(tài)。各進(jìn)程的初始狀態(tài)均設(shè)置為 r。系統(tǒng)分時(shí)執(zhí)行各進(jìn)程，并規(guī)定 3 個(gè)進(jìn)程的執(zhí)行概率均為 33%。通 過(guò)產(chǎn)生隨機(jī)數(shù) x來(lái)模擬時(shí)計(jì)算機(jī)操作系統(tǒng)實(shí)驗(yàn)指導(dǎo)書(shū) 2 間片。當(dāng)進(jìn)程 process1 訪問(wèn)隨機(jī)數(shù) x 時(shí)，若 x ≥ ；當(dāng)進(jìn)程 process2 訪問(wèn) x 時(shí)，若x 或 x≥ ；當(dāng)進(jìn)程 process3 訪問(wèn) x時(shí)，若 x，分別認(rèn)為各進(jìn)程的執(zhí)行時(shí)間片到限，產(chǎn)生“時(shí)間片中斷”而轉(zhuǎn)入低就緒態(tài) t。 進(jìn)程調(diào)度算法采用剝奪式最高優(yōu)先數(shù)法。各進(jìn)程的優(yōu)先數(shù)通過(guò)鍵盤輸入予以靜態(tài)設(shè)置。調(diào)度程序每次總是選擇優(yōu)先數(shù)最?。▋?yōu)先權(quán)最高）的就緒進(jìn)程投入執(zhí)行。先從 r 狀態(tài)進(jìn)程中選擇，在從 t 狀態(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)。 各進(jìn)程在使用臨界資源 s1 和 s2 時(shí)，通過(guò)調(diào)用信號(hào)量 sem1 和 sem2 上的 P,V操作來(lái)實(shí)現(xiàn)同步，阻塞和喚醒操作負(fù)責(zé)完成從進(jìn)程的執(zhí)行態(tài)到等待態(tài)到就緒態(tài)的轉(zhuǎn)換。 系統(tǒng)啟動(dòng)后，在完成必要的系統(tǒng)初始化后便執(zhí)行進(jìn)程調(diào)度程序。但執(zhí)行進(jìn)程因“時(shí)間片中斷”，或被排斥使用臨界資源，或喚醒某個(gè)等待資源時(shí)，立即進(jìn)行進(jìn)程調(diào)度。當(dāng)3 個(gè)進(jìn)程都處于完成狀態(tài)后，系統(tǒng)退出運(yùn)行。 圖 1 和圖 2 分別示出了系統(tǒng)主控程序和進(jìn)程調(diào)度程序的大致流程。 N Y 圖 1 進(jìn) 程管理主控程序 初始化 處處石化初始化 有進(jìn)程管理 （ exe≠ NIL） 進(jìn)程 1 進(jìn)程 2 進(jìn)程 3 main scheduler END 計(jì)算機(jī)操作系統(tǒng)實(shí)驗(yàn)指導(dǎo)書(shū) 3 3 、數(shù)據(jù)結(jié)構(gòu) （ 1）每個(gè)進(jìn)程有一個(gè)進(jìn)程控制塊 PCB，內(nèi)容包括： id 進(jìn)程控制數(shù)， id=0,1,2。 圖 2 進(jìn)程調(diào)度程序 status 進(jìn)程狀態(tài)，可為 e,r,t,w,c。 priorty 進(jìn)程優(yōu)先數(shù)； Y N N Y Y N N Y Y N Y 有 r 態(tài)就 緒進(jìn)程？ 有 t 態(tài)就 緒進(jìn)程？ 選取優(yōu)先數(shù)最小 pd 有無(wú)執(zhí)行者 （ exe≠ NIL） ? pd 優(yōu)先數(shù) exe 優(yōu)先數(shù)？ 置 exe 進(jìn) 程狀態(tài)為“ r” 置 pd 進(jìn)程狀態(tài)為“ e” 恢復(fù)進(jìn)程 pd 的現(xiàn)場(chǎng) 有無(wú)執(zhí)行 進(jìn) 程？ exe← pd return(NIL) 恢復(fù)現(xiàn)行進(jìn)行現(xiàn)場(chǎng) scheduler 計(jì)算機(jī)操作系統(tǒng)實(shí)驗(yàn)指導(dǎo)書(shū) 4 nexrtwr 等待鏈指針，只是在同一信號(hào)量上等待的下一個(gè)進(jìn)程的標(biāo)時(shí)數(shù)。 （ 2）信號(hào)量 semaphore，對(duì)于臨界資源 s1 和 s2分別有 sem1 和 sem2 均為互斥信號(hào)量。內(nèi)容包括： value 信號(hào)量值，初值為 1； firstwr 等待鏈?zhǔn)字羔?，指示該信?hào)量上等待的下一個(gè)進(jìn)程標(biāo)識(shí)數(shù)。 （ 3）現(xiàn)場(chǎng)保留區(qū)，用數(shù)組 savearea[3][4]表示，即每一個(gè)進(jìn)程都有一個(gè)大小為 4 個(gè)單元的保留區(qū)，用來(lái)保存被“中斷”時(shí)的現(xiàn)場(chǎng)信息，如通用寄存器的內(nèi)容和斷點(diǎn)地址等。此外，系統(tǒng)中還用到下列主要全程變量： exe 執(zhí)行進(jìn)程指針，其值為進(jìn)程標(biāo)識(shí)數(shù)； i 用來(lái)模擬一個(gè)通用寄存器； addr 用來(lái)模擬程序計(jì)數(shù)器； s1， s2 兩個(gè)公用變量，與來(lái)共享臨界資源。 程序清單 include define TRUE 1 define FALSE 0 define MAXPRI 100 define NIL1 struct{ int id。 char status。 int nextwr。 int priority。 }pcb[3]。 struct{ int value。 int firstwr。 }sem[2]。 char savearea[3][4],addr。 int i,s1,s2,seed,exe=NIL。 init() /*initialization*/ { int j。 計(jì)算機(jī)操作系統(tǒng)實(shí)驗(yàn)指導(dǎo)書(shū) 5 for (j=0。j3。j++) { pcb[j].id=j。 pcb[j].status=39。r39。 pcb[j].nextwr=NIL。 printf(\n process%d priority?,j+1)。 scanf(%d,amp。i)。 pcb[j].priority=i。 } sem[0].value=1。sem[0].firstwr=NIL。 sem[1].value=1。sem[1].firstwr=NIL。 for(i=1。i3。i++) for(j=0。j4。j++) savearea[i][j]=39。039。 } float random() {int m。 if (seed0)m=seed。 else m=seed。 seed=(25173*seed+13849)%65536。 return(m/)。 } timeint(ad) /*time slice interrupt */ char ad。 { float x。 x=random()。 if((x)amp。amp。(exe==0))return(FALSE)。 if((x)amp。amp。(exe==1))return(FALSE)。 if((x)amp。amp。(exe==2))return(FALSE)。 savearea[exe][0]=i。 savearea[exe][1]=ad。 pcb[exe].status=39。t39。 printf(Time silce interrupt39。\nprocess%d enter inro ready.\n,exe+1)。 exe=NIL。 return(TRUE)。 } scheduler() {int pd。 計(jì)算機(jī)操作系統(tǒng)實(shí)驗(yàn)指導(dǎo)書(shū) 6 if((pd=find())==NILamp。amp。exe==NIL) return(NIL)。 /*quit system*/ if(pd!=NIL){ if(exe==NIL){ pcb[pd].status=39。e39。 exe=pd。 printf(process%d is executing.\n,exe+1)。 } else if(pcb[pd].prioritypcb[exe].priority) { pcb[exe].status=39。r39。 printf(process%d enter into ready\n,exe+1)。 pcb[pd].status=39。e39。 exe=pd。 printf(process%d is executing\n,exe+1)。 } } i=savearea[exe][0]。 addr=savearea[exe][1]。 return(exe)。 } find() { int j,pd=NIL,w=MAXPRI。 for (j=0。j3。j++) if(pcb[j].status==39。r39。) if (pcb[j].priorityw){ w=pcb[j].priority。pd=j。 } if (pd==NIL) for (j=0。j3。j++) if(pcb[j].status==39。t39。) if(pcb[j].priorityw){ w=pcb[j].priority。pd=j。 } return (pd)。 } p(se,ad) int se。 char ad。 計(jì)算機(jī)操作系統(tǒng)實(shí)驗(yàn)指導(dǎo)書(shū) 7 { if(sem[se].value=0) return(FALSE)。 block(se)。 savearea[exe][0]=i。 savearea[exe][1]=ad。 exe=NIL。 return(TRUE)。 } block(se) int se。 { int w。 printf(process%d is blocked\n,exe+1)。 pcb[exe].status=39。w39。 pcb[exe].nextwr=NIL。 if((w=sem[se].firstwr)==NIL) sem[se].firstwr=exe。 else{ wh