優(yōu)先調(diào)度時(shí)間片輪轉(zhuǎn)剖析

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

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

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

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

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

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

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

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

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

10、0; intprio; intcputime; intneedtime; charstate; structnode*next; intround; intcount;時(shí)間片輪轉(zhuǎn)調(diào)度算法: /*進(jìn)程標(biāo)識(shí)符*/ /*進(jìn)程優(yōu)先數(shù)*/ /*進(jìn)程占用CPU時(shí)間*/ /*進(jìn)程到完成還要的時(shí)間*/ /*進(jìn)程的狀態(tài)*/ /*鏈指針*/ 分配cpu的時(shí)間片*/ /*執(zhí)行次數(shù)*/ PCB; PCB*finish,*ready,*run;/*隊(duì)列指針*/ intN;/*選擇數(shù)*/ /*將就緒隊(duì)列中的第一個(gè)進(jìn)程投入運(yùn)行*/ 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();/*輸出標(biāo)題*/ if(run!=NULL)/*如果運(yùn)行指針不空*/ prt2(run);/*輸出當(dāng)前正在運(yùn)行的PCB*/ run=ready; /*就緒隊(duì)列頭指針賦值給運(yùn)行頭指針*/ ru

12、n-state=R; /*進(jìn)程狀態(tài)變?yōu)檫\(yùn)行態(tài)*/ ready=ready-next; /*就緒對(duì)列頭指針后移到下一進(jìn)程*/ voidprt1()/*標(biāo)題輸出函數(shù) */ printf( name cputimeneedtimeprioritystaten); printf( name cputimeneedtimestatecountn); voidprt2(PCB*q) /*進(jìn)程 PCB輸出*/ printf( p=ready;/*輸出就緒隊(duì)列PCB*/ while(p!=NULL)( prt2(p); p=p-next; p=finish;/*輸出完成隊(duì)列的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;/*就緒隊(duì)列頭指針*/ 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;/*否則插入在就緒隊(duì)列的頭*/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;/*進(jìn)程的優(yōu)先數(shù)以 else insert(p); elsep-prio=50; /*進(jìn)程的優(yōu)先數(shù)都為50*/ if(ready!=NULL) /*就緒隊(duì)列不空調(diào)用插入函數(shù)插入*/ ready=NULL; /*就緒隊(duì)列頭指針*/ finish=NULL; /*完成隊(duì)列

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

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

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

18、”); scanf(%d,&N); create(); priority(); 五、程序運(yùn)行結(jié)果及分析 優(yōu)先數(shù)調(diào)度算法:輸入5個(gè)進(jìn)程的名稱和時(shí)間finish=run; run-state=F; /*置狀態(tài)為完成態(tài)*/ run=NULL; /*運(yùn)行隊(duì)列頭指針為空*/ if(ready!=NULL) /*如就緒隊(duì)列不空*/ firstin(); /*將就緒對(duì)列的第一個(gè)進(jìn)程投入運(yùn)行*/ */ 方作業(yè)。讀驗(yàn)Debug第T向片輪轉(zhuǎn)實(shí)驗(yà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.時(shí)間片輪轉(zhuǎn)算法：1 1 請(qǐng)選擇算法:1:1.優(yōu)先數(shù)調(diào)度算法; 08610861 1812218122 和名名名名名滬一 nt1234512345 1jlir吊Hg-F五FmF 入人入人入入 產(chǎn)- 時(shí)間片輪轉(zhuǎn)算法: E:fplkQSDebugDeb