1、計算機操作系統(tǒng)課程實驗報告 姓名: 學號: 班級: 完成日期: 實驗題目 進程調(diào)度模擬程序 實驗形式 小組合作獨立完成 設計目的 1 .加深對進程、進程控制塊及進程隊列等概念的理解。 2 .了解優(yōu)先數(shù)調(diào)度算法、時間片輪轉(zhuǎn)算法、先來先服務調(diào)度算法、短作業(yè)優(yōu)先調(diào)度算法的具體實施辦法，加深對進程管理各部分內(nèi)容的理解。 設計預備知識 1 .進程管理。 2 .優(yōu)先數(shù)調(diào)度算法、時間片輪轉(zhuǎn)算法、先來先服務調(diào)度算法、短作業(yè)優(yōu)先調(diào)度算法。 設計內(nèi)容 設一個至少包含兩種調(diào)度算法的模擬進程調(diào)度程序(已給出優(yōu) 先數(shù)算法模擬進程調(diào)度程序， 要求再加進至少一種調(diào)度算法， 模擬程序的設計可以在給出的優(yōu)先數(shù)算法的基礎上添加，

2、也可以自行設計，開發(fā)語后可自選)。 設計的模擬程序要求如下： (1) 設計適合所選算法的進程控制塊PCB表結(jié)構(gòu)。 (2) 對/、同的算法建立進程就緒隊列。 (3) 設計的程序中能顯示或打印進程控制塊的動態(tài)變化過程。 一、設計理論描述 a)a)優(yōu)先數(shù)調(diào)度算法 為了照顧緊迫型作業(yè)，使之在進入系統(tǒng)后便獲取優(yōu)先處理，引入了最高優(yōu)先權(quán)優(yōu)先調(diào)度算法，此算法常被用于批處理系統(tǒng)中，作為作業(yè)調(diào)度算法木，也作為多鐘操作系統(tǒng)中的進程調(diào)度算法，還可以用于實時操作系統(tǒng)中。當把該算法用于作業(yè)調(diào)度時，系統(tǒng)將從后備隊列中選擇若干優(yōu)先權(quán)最高的作業(yè)裝入內(nèi)存。 b)b)時間片輪轉(zhuǎn)調(diào)度算法 在早期的時間片輪轉(zhuǎn)法中，系統(tǒng)將所有的就緒進

3、程按照先來先服務的原則排成一個隊列，每次調(diào)度時，把 CPUCPU 分配桂隊首進程，并執(zhí)行一個時間片。當執(zhí)行時間片用完時，由一個計時器發(fā)出時鐘中斷請求，調(diào)度程序便據(jù)此信號停止該進程的執(zhí)行，并將它送往就緒隊列的隊尾。 二、設計思想、設計分析及數(shù)據(jù)結(jié)構(gòu)模型 1 1、優(yōu)先數(shù)調(diào)度算法 (1)(1)設計思想 按某種原則對就緒隊列中的每個進程賦予一個優(yōu)先級，進程調(diào)度時則根據(jù)進程的優(yōu)先級確定選擇順序，即把處理機分配給就緒隊列中優(yōu)先級高的進程。由于進程的優(yōu)先級別通常用數(shù)字表示，所以又稱為進程的優(yōu)先數(shù)。有些操作系統(tǒng)中規(guī)定優(yōu)先數(shù)愈小，其優(yōu)先級愈高，本設計研究的是優(yōu)先數(shù)愈高，優(yōu)先級愈高的情況。 優(yōu)先數(shù)調(diào)度算法一般可以

4、采用搶占式優(yōu)先調(diào)度算法或非搶占優(yōu)先調(diào)度算法。 在采用搶占式優(yōu)先調(diào)度算法時，系統(tǒng)同樣是把處理機分配給優(yōu)先數(shù)最高的進程，使之執(zhí)行。但在其執(zhí)行期間，只要又出現(xiàn)了另一個具優(yōu)先數(shù)更高的進程，進程調(diào)度程序就立即停止當前進程(原優(yōu)先數(shù)最高的進程)的執(zhí)行，重新將處理機分配給新到的優(yōu)先數(shù)最高的進程。 在采用非搶占式優(yōu)先調(diào)度算法時，系統(tǒng)一旦把處理機分配給就緒隊列中優(yōu)先數(shù)最高的進程后，該進程便一直執(zhí)行下去，直至結(jié)束；或因發(fā)生某事件使該進程放棄處理機時，系統(tǒng)方可再將處理機重新分配給另一優(yōu)先數(shù)最高的進程。這種調(diào) 度算法主要用于批處理系統(tǒng)中；也可用于某些對實時性要求不嚴的實時系統(tǒng)中。 (2)(2)設計分析 進程調(diào)度所依賴

5、的數(shù)據(jù)結(jié)構(gòu)通常是調(diào)度隊列，由于調(diào)度的原因不同，在單處 理器系統(tǒng)中設置了多種等待隊列；只有就緒隊列中的進程能夠獲得處理器而最終運行，其他隊列中的進程從隊列中調(diào)度出來后，必須進入就緒隊列才能分配處理 (3)(3)數(shù)據(jù)結(jié)構(gòu)模型 用結(jié)構(gòu)體變量定義進程控制塊的優(yōu)先級，進程需要占用 CPUCPU 的時間 (cputime),(cputime),運行后還需要 CPUCPU 的時間，進程的狀態(tài)，及指向 pcbpcb 結(jié)構(gòu)體變量的指針。具體代碼如下： typedefstructnode ( charname10;/*進程標識符*/ intprio;/*進程優(yōu)先數(shù)*/ intcputime;/*進程占用CPU時間

6、*/ intneedtime;/*進程到完成還要的時間*/ charstate;/*進程的狀態(tài)*/ structnode*next;/*鏈指針*/ PCB; 進程名 next 優(yōu)先數(shù) 占用CPU時間 到完成還要的時間 狀態(tài) 2 2、時間片輪轉(zhuǎn)調(diào)度算法 (1)(1)設計思想 時間片輪轉(zhuǎn)的主要思想就是按順序為每一個進程一次只分配一個時間片的時間。算法要完成的功能就是將各個進程按照時間片輪轉(zhuǎn)運行的動態(tài)過程顯示出來。 時間片輪轉(zhuǎn)算法中，系統(tǒng)將所有的就緒進程按先來先服務的原則排成一個隊列，每次調(diào)度時，把 CPUCPU 分配給隊首進程，并令其執(zhí)行一個時間片。時間片的大小從幾 msms 到幾百 msms。當

7、執(zhí)行的時間片用完時，由一個計時器發(fā)出時鐘中斷請求，調(diào)度程序便據(jù)此信號來停止該進程的執(zhí)行，并將其送往就緒隊列的末尾；然 后，再把處理機分配給就緒隊列中新的隊首進程，同時也讓它執(zhí)行一個時間片。這樣就可以保證就緒隊列中的所有進程在一定給定的時間內(nèi)均能獲得一時間片的處理機執(zhí)行時間。換言之，系統(tǒng)能在給定時間內(nèi)響應所有用戶的請求。 (2)(2)設計分析 每個進程用一個 PCBPCB 表示。PCBPCB 包括進程名，到達時間，運行時間，剩余時間，進程狀態(tài)，鏈接指針。其中，進程名，到達時間和運行時間由用戶輸入，剩余時間的初值等于運行時間。 為簡單起見， 進程狀態(tài)設為三種： 就緒， 運行和完成。 鏈接指針指向下

8、一個進程的 PCB;PCB;按照進程到達的先后順序排成一個隊 列。設置一個隊頭指針指向隊列中第一個進程，并設置一個隊尾指針指向隊列中 的最后一個進程；執(zhí)行調(diào)度時，先選擇隊首的第一個進程運行。另外設置一個指向當前運行進程的指針。 (3)(3)數(shù)據(jù)結(jié)構(gòu)模型 用結(jié)構(gòu)體變量定義進程控制塊的優(yōu)先級，進程需要占用 CPUCPU 的時間 (cputime),(cputime),運行后還需要 CPUCPU 的時間，進程的狀態(tài)，分配 cpucpu 時間，執(zhí)行次數(shù)及指向 pcbpcb 結(jié)構(gòu)體變量的指針。具體代碼如下： typedefstructnode charname10; /*進程標識符*/ PCB; 進程名

9、 優(yōu)先數(shù) 占用CPU時間 到完成還要的時間 next 狀態(tài) 分配CPU的時間片 執(zhí)行次數(shù) 三、變量說明及程序流程圖 intcputime; /*進程占用CPU時間*/ intneedtime; /*進程到完成還要的時間 charstate; /*進程的狀態(tài)*/ intround; /*分配cpu的時間片*/ intcount; /*執(zhí)行次數(shù)*/ structnode*next; /*鏈指針*/ intprio; /*進程優(yōu)先數(shù)*/ */ 優(yōu)先數(shù)調(diào)度算法: 四、源代碼 #include #include #include #include typedefstructnode( charname1

10、0; intprio; intcputime; intneedtime; charstate; structnode*next; intround; intcount;時間片輪轉(zhuǎn)調(diào)度算法: /*進程標識符*/ /*進程優(yōu)先數(shù)*/ /*進程占用CPU時間*/ /*進程到完成還要的時間*/ /*進程的狀態(tài)*/ /*鏈指針*/ 分配cpu的時間片*/ /*執(zhí)行次數(shù)*/ PCB; PCB*finish,*ready,*run;/*隊列指針*/ intN;/*選擇數(shù)*/ /*將就緒隊列中的第一個進程投入運行*/ voidfirstin() if(N=1) else if(N=1) %-10s%-10d%

11、-10d%-10d%cn”,q-name, q-cputime,q-needtime,q-prio,q-state); else q-count=q-cputime/q-round; printf(%-10s%-10d%-10d%ct%-10dn,q-name, q-cputime,q-needtime,q-state,q-count); voidprt()/*輸出函數(shù)*/ ( PCB*p; prt1();/*輸出標題*/ if(run!=NULL)/*如果運行指針不空*/ prt2(run);/*輸出當前正在運行的PCB*/ run=ready; /*就緒隊列頭指針賦值給運行頭指針*/ ru

12、n-state=R; /*進程狀態(tài)變?yōu)檫\行態(tài)*/ ready=ready-next; /*就緒對列頭指針后移到下一進程*/ voidprt1()/*標題輸出函數(shù) */ printf( name cputimeneedtimeprioritystaten); printf( name cputimeneedtimestatecountn); voidprt2(PCB*q) /*進程 PCB輸出*/ printf( p=ready;/*輸出就緒隊列PCB*/ while(p!=NULL)( prt2(p); p=p-next; p=finish;/*輸出完成隊列的PCB*/ while(p!=NU

13、LL)( prt2(p); p=p-next; getch();/*按任意鍵繼續(xù)*/ voidinsert(PCB*q)/*優(yōu)先數(shù)的插入算法*/ ( PCB*p1,*s,*r; intb; s=q;/*待插入的PCB指針*/ p1=ready;/*就緒隊列頭指針*/ r=p1;/*r做p1的前驅(qū)指針*/ b=1; while(p1!=NULL)&b)/*根據(jù)優(yōu)先數(shù)確定插入位置*/ if(p1-prio=s-prio)( r=p1; p1=p1-next; else b=0; if(r!=p1)/*如果條件成立說明插入在r與p1之間*/ ( r-next=s; s-next=p1; el

14、se s-next=p1;/*否則插入在就緒隊列的頭*/ready=s; voidcreate()/*優(yōu)先數(shù)創(chuàng)建初始PCB信息*/ PCB*p; charna10; for(i=1;iname,na); p-cputime=0; p-needtime=time; p-state=w; if(N=1) p-prio=35-time;/*進程的優(yōu)先數(shù)以 else insert(p); elsep-prio=50; /*進程的優(yōu)先數(shù)都為50*/ if(ready!=NULL) /*就緒隊列不空調(diào)用插入函數(shù)插入*/ ready=NULL; /*就緒隊列頭指針*/ finish=NULL; /*完成隊列

15、頭指針*/ run=NULL; /*運行隊列指針*/ printf(nn輸入5個進程標識和所需時間 n);/*輸入進程標識和所需時間創(chuàng)建 PCB*/ printf(輸入第%d個進程的名字和時間 :,i); 35-time構(gòu)成*/ p-next=ready;/*創(chuàng)建就緒隊列的第一個PCB*/ ready=p; ) ) system(cls); printf(outputofprocess:n); printf(*n); prt();/*輸出進程PCB信息*/ run=ready;/*將就緒隊列的第一個進程投入運行*/ ready=ready-next; run-state=R; ) voidpr

16、iority()/*優(yōu)先數(shù)調(diào)度算法*/ ( while(run!=NULL)/*當運行隊列不空時，有進程正在運行*/ (run-round=1;/*時間片*/run-cputime=run-cputime+1;/*CPU時間片數(shù)加1*/if(N=1)(run-needtime=run-needtime-1;/*進程還需要的日間片數(shù)減1*/ run-prio=run-prio-2;/*每運行一次優(yōu)先數(shù)降低2個單位*/ )else(run-needtime=run-needtime-run-round;/*進程還需要的時間片數(shù)減時間片*/run-prio=run-prio-5;/*每運行一次優(yōu)先數(shù)

17、降低5個單位，即該進程到隊列最 后*/ )if(run-needtime=0)/*如所需時間為0將其插入完成隊列*/( run-next=finish; /*沒有運行完同時優(yōu)先數(shù)不是最大，則將其變?yōu)榫途w態(tài)插入到就緒隊列elseif(ready!=NULL)&(run-prioprio) run-state=W; insert(run); firstin();/*將就緒隊列的第一個進程投入運行*/ prt();/*輸出進程PCB信息*/ /*主函數(shù)*/voidmain() system(cls); printf(*n); printf(請選擇算法：1.優(yōu)先數(shù)調(diào)度算法；2.時間片輪轉(zhuǎn)算法：

18、”); scanf(%d,&N); create(); priority(); 五、程序運行結(jié)果及分析 優(yōu)先數(shù)調(diào)度算法:輸入5個進程的名稱和時間finish=run; run-state=F; /*置狀態(tài)為完成態(tài)*/ run=NULL; /*運行隊列頭指針為空*/ if(ready!=NULL) /*如就緒隊列不空*/ firstin(); /*將就緒對列的第一個進程投入運行*/ */ 方作業(yè)。讀驗Debug第T向片輪轉(zhuǎn)實驗-礪 輸出結(jié)果: 廣 “E:fPlkCl婚口后勺啊間片輪轉(zhuǎn)犍-Bt.exe D 回 loutputofprocessloutputofprocessi i中HHMM

19、W=W*MMW IIII nanenanecputcputimeneedtimeneedtIneIneprioritystateprioritystate p2p208082727w w plW1025wplW1025w p301817up301817u pS0pS02121HuHu p40p40269269u u nnecputimcnedtimeprioritystatennecputimcnedtimeprioritystate p2p21 1725725R R pl010pl0102S2Sw w p3p3廿1817w1817w p502114up502114u p40p40269269

20、u u nanenanecputcputimeneedtimeneedtininppioritj/stateppioritj/state plplH H1025R1025R p22623p22623U U p3p30 018171817w w p5M2114wp5M2114w p40269up40269u namecputimenamecputimeneeneedtdtin)ppriain)ppriaritritJJstatestate plpl1 1923923H H p2p22 22323U U p3p30 0IB17IB17u u pSpS0 021142114w w p40269wp40269w namecputin)eneedtimeppioyitystatenamecputin)eneedtimeppioyitystate |p22623R|p22623R plpl2 2821821U U p3p30 0IBIB17w17w * *0 0212114w14w p40p40269269u u 半: 1 b1 J 2.2.時間片輪轉(zhuǎn)算法：1 1 請選擇算法:1:1.優(yōu)先數(shù)調(diào)度算法; 08610861 1812218122 和名名名名名滬一 nt1234512345 1jlir吊Hg-F五FmF 入人入人入入 產(chǎn)- 時間片輪轉(zhuǎn)算法: E:fplkQSDebugDeb