時(shí)間片輪轉(zhuǎn)調(diào)度算法設(shè)計(jì)與實(shí)現(xiàn)

1、鄭州輕工業(yè)學(xué)院實(shí)驗(yàn)報(bào)告課程名稱：操作系統(tǒng)姓 名：學(xué) 號(hào)：專業(yè)班級(jí)：任課教師：黃偉2016 年 11 月 2 日實(shí)驗(yàn)報(bào)告成績(jī)?cè)u(píng)定表評(píng)定項(xiàng)目?jī)?nèi)容滿分評(píng)分總分實(shí)驗(yàn)態(tài)度態(tài)度端正、遵守紀(jì)律、出勤情況20實(shí)驗(yàn)過(guò)程按要求完成算法設(shè)計(jì)、代碼書寫、注釋清晰、運(yùn)行結(jié)果正確40報(bào)告撰寫報(bào)告書寫規(guī)范、內(nèi)容條理清楚、表 達(dá)準(zhǔn)確規(guī)范、上交及時(shí)。40評(píng)語(yǔ)：指導(dǎo)老師簽字：年 月曰實(shí)驗(yàn)報(bào)告正文實(shí)驗(yàn)二時(shí)間片輪轉(zhuǎn)調(diào)度算法設(shè)計(jì)與實(shí)現(xiàn)一、實(shí)驗(yàn)?zāi)康哪康模毫私獠⒄莆諘r(shí)間片輪轉(zhuǎn)調(diào)度算法的理論，熟悉并掌握時(shí)間片設(shè)置的大小對(duì)系統(tǒng)的影響。任務(wù)：模擬實(shí)現(xiàn)時(shí)間片輪轉(zhuǎn)調(diào)度算法。二、實(shí)驗(yàn)內(nèi)容任務(wù)描述1）時(shí)間片輪轉(zhuǎn)調(diào)度算法問(wèn)題簡(jiǎn)介時(shí)間片輪轉(zhuǎn)的主要思想就是按

2、順序?yàn)槊恳粋€(gè)進(jìn)程一次只分配一個(gè)時(shí)間片的時(shí)間。算法 要完成的功能就是將各個(gè)進(jìn)程按照時(shí)間片輪轉(zhuǎn)運(yùn)行的動(dòng)態(tài)過(guò)程顯示出來(lái)。時(shí)間片輪轉(zhuǎn)算法的 主要實(shí)現(xiàn)過(guò)程是首先為每一個(gè)進(jìn)程創(chuàng)建一個(gè)進(jìn)程控制塊，定義數(shù)據(jù)結(jié)構(gòu)，說(shuō)明進(jìn)程控制塊所 包含的內(nèi)容，有進(jìn)程名、進(jìn)程所需運(yùn)行時(shí)間、已運(yùn)行時(shí)間和進(jìn)程的狀態(tài)以及指針的信息。實(shí) 現(xiàn)的過(guò)程即運(yùn)用指針指向某一個(gè)進(jìn)程，判斷當(dāng)前的進(jìn)程是否是就緒狀態(tài)”，如果是，則為 該進(jìn)程分配一個(gè)時(shí)間片，同時(shí)，已運(yùn)行時(shí)間加一且要求運(yùn)行的時(shí)間減一，如此循環(huán)執(zhí)行，當(dāng) 某一個(gè)進(jìn)程的所需要運(yùn)行的時(shí)間減少至0時(shí)，則將該進(jìn)程的狀態(tài)設(shè)置為e”。然后，將指針 指向下一個(gè)未運(yùn)行完成的進(jìn)程，重復(fù)判斷，直至所有的進(jìn)程都運(yùn)行結(jié)

3、束。2）設(shè)計(jì)任務(wù)簡(jiǎn)介模擬實(shí)現(xiàn)時(shí)間片輪轉(zhuǎn)調(diào)度算法，具體如下：設(shè)置進(jìn)程體：進(jìn)程名，進(jìn)程的到達(dá)時(shí)間，服務(wù)時(shí)間，進(jìn)程狀態(tài)（W等待,R 運(yùn)行,F完成），進(jìn)程間的鏈接指針進(jìn)程初始化：由用戶輸入進(jìn)程名、服務(wù)時(shí)間進(jìn)行初始化，同時(shí)，初始化進(jìn)程的狀態(tài) 為W。顯示函數(shù)：在進(jìn)程調(diào)度前、調(diào)度中和調(diào)度后進(jìn)行顯示。排序函數(shù)：對(duì)就緒狀態(tài)的進(jìn)程按照進(jìn)入就緒隊(duì)列的時(shí)間排序，新到達(dá)的進(jìn)行應(yīng)優(yōu)先 于剛剛執(zhí)行過(guò)的進(jìn)程進(jìn)入就緒隊(duì)列的隊(duì)尾。注意考慮到達(dá)時(shí)間調(diào)度函數(shù)：每次從就緒隊(duì)列隊(duì)首調(diào)度優(yōu)一個(gè)進(jìn)程執(zhí)行，狀態(tài)變化。并在執(zhí)行一個(gè)時(shí) 間片后化，服務(wù)時(shí)間變化，狀態(tài)變化。當(dāng)服務(wù)時(shí)間為0時(shí)，狀態(tài)變?yōu)镕。刪除函數(shù)：撤銷狀態(tài)為F的進(jìn)行。調(diào)度問(wèn)題的表示方案

4、首先每一個(gè)進(jìn)程用一個(gè)進(jìn)程控制塊PCB來(lái)代表。進(jìn)程控制塊的格式為:進(jìn)程名指針要求運(yùn)行時(shí)間已運(yùn)行時(shí)間 一狀態(tài)其中，進(jìn)程名一一作為進(jìn)程的標(biāo)識(shí)，如Q1、Q2等。指針一一進(jìn)程按順序排成循環(huán)鏈隊(duì)列，用指針指出下一個(gè)進(jìn)程的進(jìn)程控制塊的首地址， 最后一個(gè)進(jìn)程的指針指出第一個(gè)進(jìn)程的進(jìn)程控制塊首地址。要求運(yùn)行時(shí)間一一假設(shè)進(jìn)程需要運(yùn)行的單位時(shí)間數(shù)。已運(yùn)行時(shí)間一一假設(shè)進(jìn)程已經(jīng)運(yùn)行的單位時(shí)間數(shù)，初始值為“0”。狀態(tài)一一有兩種狀態(tài)，“就緒”和“結(jié)束”，初始狀態(tài)都為“就緒”，用“R”表示。 當(dāng)一個(gè)進(jìn)程運(yùn)行結(jié)束后，它的狀態(tài)為“結(jié)束”，用“E”表示。抽象描述這里采用流程圖來(lái)詳細(xì)描述時(shí)間片輪轉(zhuǎn)調(diào)度算法三、測(cè)試1. 方案每次運(yùn)行所

5、設(shè)計(jì)的處理器調(diào)度程序前，為每個(gè)進(jìn)程任意確定它的“要求運(yùn)行時(shí)間”。把 五個(gè)進(jìn)程按順序排成循環(huán)鏈隊(duì)列，用指針指出隊(duì)列連接情況。用指針表示輪到運(yùn)行的進(jìn)程，如下圖描述所示:PCB25PCB5首先建立PCB的數(shù)據(jù)結(jié)構(gòu)，為了便于正確輸出，加上了進(jìn)程結(jié)束標(biāo)志flag。輸入進(jìn) 程信息(包括進(jìn)程名和要求運(yùn)行的時(shí)間)，并為每個(gè)進(jìn)程創(chuàng)建一個(gè)PCB并初始化形成一個(gè)循 環(huán)鏈隊(duì)列，用函數(shù)creatPCB()來(lái)實(shí)現(xiàn)。建立函數(shù)judge()用來(lái)判斷進(jìn)程全部運(yùn)行結(jié)束標(biāo)志，即當(dāng)所有進(jìn)程的狀態(tài)變?yōu)?e (即完成狀態(tài))后，循環(huán)結(jié)束，表示所有進(jìn)程都已運(yùn)行成功。建立時(shí)間片輪轉(zhuǎn)算法creatProcess()對(duì)進(jìn)程進(jìn)行輪轉(zhuǎn)運(yùn)行，首先指針s

6、指向第一 個(gè)進(jìn)程PCB，即s=front，判斷該進(jìn)程的狀態(tài)是否為 r(就緒狀態(tài))，即if(s-condition =r)，若是則表示此進(jìn)程尚未執(zhí)行結(jié)束，則執(zhí)行s-worked_time+且 s-need_time， if(s-need_time=0)，則表示此進(jìn)程已運(yùn)行結(jié)束，將其狀態(tài)置為結(jié)束，即s-condition=e， 并根據(jù)狀態(tài)位輸出完成信息，且以后不會(huì)再運(yùn)行此進(jìn)程。將指針指向下個(gè)進(jìn)程，s=s-next， 并判斷所有進(jìn)程是否已全部運(yùn)行結(jié)束，沒(méi)有則重復(fù)上面算法。當(dāng)所有進(jìn)程的狀態(tài)位都變成 e表示所有進(jìn)程運(yùn)行完成，則循環(huán)結(jié)束。建立主函數(shù)main()，輸入進(jìn)程數(shù)N，調(diào)用初始化循環(huán)鏈隊(duì)列函數(shù)cre

7、atPCB()和時(shí)間片 輪轉(zhuǎn)算法creatProcess(N)，每次選中進(jìn)程的進(jìn)程名以及運(yùn)行一次后進(jìn)程隊(duì)列的變化，實(shí)現(xiàn) 處理器的調(diào)度。2. 結(jié)果實(shí)例進(jìn)程名ABCDE平均到達(dá)時(shí)間01234服務(wù)時(shí)間62598RRQ=2完成時(shí)間164153029周轉(zhuǎn)時(shí)間16319272518帶權(quán)周轉(zhuǎn) 時(shí)間2.671.53.833.132.82RRQ=4完成時(shí)間206213029周轉(zhuǎn)時(shí)間20519272519.2帶權(quán)周轉(zhuǎn) 時(shí)間3.332.53.833.133.15Q=2Q=4忌暗入曲過(guò)間什粕轉(zhuǎn)進(jìn)程隊(duì)列為:Nan* Ml hUneBHune-CriajFie9E*rrivttirw-0Artivfit irw 旦1 a

8、rr ivet ine -2 ftrriu*ctiic-3runtime =6 runt infr-2 runt int-5funtstateR stalw-R stateR SttC-R stateR請(qǐng)置入時(shí)間片輪轉(zhuǎn)調(diào)度的時(shí)間片為:4 時(shí)刻進(jìn)程運(yùn)行后的敏態(tài)4 A R R C寸刻&進(jìn)畋行始原進(jìn)程職轉(zhuǎn)時(shí)間 5皿常t陰轉(zhuǎn)時(shí)間16141S時(shí)刻，成運(yùn)行結(jié)柬髓程建琵1禮弟皿.帝任胃轉(zhuǎn)時(shí)由二 TOC o 1-5 h z 21CC時(shí)刻21進(jìn)華運(yùn)作結(jié)束總程硒轉(zhuǎn)時(shí)間W槌叭帶枚.周轉(zhuǎn)時(shí)斗25IRG 0C2.13時(shí)刻及進(jìn)理演行拮束,進(jìn)程瞭轉(zhuǎn)時(shí)間翡5投罔轉(zhuǎn)時(shí)間G請(qǐng)稿入時(shí)間片輪轉(zhuǎn)調(diào)度的可間片為I時(shí)割 進(jìn)程 運(yùn)行后的狀態(tài)

9、 TOC o 1-5 h z 4AR&口c時(shí)刻6進(jìn)程B運(yùn)行結(jié)來(lái).進(jìn)程R周轉(zhuǎn)時(shí)間M 5.0帶權(quán)冏轉(zhuǎn)時(shí)間 2.5010CR14DRIBER2BAC時(shí)刻德進(jìn)笛運(yùn)行拮束，進(jìn)程周轉(zhuǎn)時(shí)間跪血,帶校周轉(zhuǎn)時(shí)間 3-33g jGg時(shí)剽就捱程C運(yùn)行結(jié)基迸程瑚轉(zhuǎn)時(shí)間 .卵滯極周轉(zhuǎn)時(shí)間 3.802&bR29*EC時(shí)刻網(wǎng)進(jìn)程E運(yùn)行始來(lái)湖程E周轉(zhuǎn)時(shí)間志一皿帶視周轉(zhuǎn)時(shí)間-3.1JJBbC與刻捆進(jìn)程。運(yùn)行堵束展程。周轉(zhuǎn)時(shí)問(wèn)營(yíng).昵帶機(jī)周轉(zhuǎn)時(shí)（Bl- 3.M 華期周待時(shí)間F.曲.翔蚩權(quán)內(nèi)林時(shí)即1.1SPress ad9 *4iy to cant inu*四、總結(jié)與討論通過(guò)本次實(shí)驗(yàn)了解到算法很重要，又更加明白算法本身可以節(jié)約時(shí)間，

10、而且不同 的函數(shù)之間在調(diào)用的時(shí)候要注意很多的問(wèn)題。意識(shí)到自己的不足，代碼在運(yùn)行過(guò)程中， 無(wú)法運(yùn)行，錯(cuò)誤很多，。通過(guò)本次實(shí)驗(yàn)，我更加了解了時(shí)間片輪轉(zhuǎn)調(diào)度算法，通過(guò)翻看 課本，對(duì)其的理解更加的深刻了，在以后的學(xué)習(xí)中，我會(huì)更加努力的學(xué)習(xí)操作系統(tǒng)的 相關(guān)課程。當(dāng)然，實(shí)驗(yàn)中也遇到了問(wèn)題，但都不是理論上的問(wèn)題，而是編程的問(wèn)題，根 本原因還是編程基礎(chǔ)不牢。以后會(huì)在編程方面努力。五、附：程序模塊的源代碼RR.h#include#include#include#include#include#define MaxNum 100typedef struct pcbchar NameMaxNum;int arriv

11、etime;int runtime;int wholetime;int FinishTime;double WeightTime;double WeightWholeTime;char state;struct pcb *next;PCB;int N;double SumWT;double SumWWT;double AverageWT;double AverageWWT;typedef struct PCB *front,*rear;queue;queue *init()queue *head;head=(queue*)malloc(sizeof(queue);head-front=NULL

12、;head-rear=NULL;return head;int empty(queue *head)return (head-front?0:1);queue *append(queue *head,char cMaxNum,int a,int r,char s) PCB *p;p=(PCB *)malloc(sizeof(PCB);strcpy(p-Name,c);p-arrivetime=a;p-runtime=r;p-wholetime=r;p-state=s;/p-FinishTime=0;/p-WeightTime=0;/p-WeightWholeTime=0;p-next=NULL

13、;if(empty(head)head-front=head-rear=p;elsehead-rear-next=p;head-rear=p;return head;queue *creat(queue *head)char cMaxNum;char s=R;int a,r,i;printf(請(qǐng)輸入共有幾個(gè)進(jìn)程：n);scanf(%d”,&N);for(i=1;ifront;if(!p)printf(時(shí)間片輪轉(zhuǎn)調(diào)度隊(duì)列為空!n”);while(p)printf(Name=%s arrivetime=%d runtime=%d state=%c”,p-Name,p-arrivetime,p-ru

14、ntime,p-state);printf(n);p=p-next;void RR(queue *head,int q)int t=head-front-arrivetime, lt=head-rear-arrivetime;if(head-front-runtimefront-runtime;elset=t+q;while(!empty(head)PCB *p1,*p2;printf (-n時(shí)刻 進(jìn)程運(yùn)行后的狀態(tài)n);while(tfront;printf(%2d %s”,t,p1-Name);p1-runtime=p1-runtime-q;if(p1-runtimestate=C;prin

15、tf( %cn”,p1-state);p1-FinishTime=t;p1-WeightTime=p1-FinishTime-p1-arrivetime;p1-WeightWholeTime=p1-WeightTime/p1-wholetime;SumWT+=p1-WeightTime;SumWWT+=p1-WeightWholeTime;printf(時(shí)刻%2d進(jìn)程%s運(yùn)行結(jié)束，進(jìn)程%s周轉(zhuǎn)時(shí)間=%5.2f,帶權(quán)周轉(zhuǎn)時(shí)間=%5.2fn”,t,p1-Name,p1-Name,p1-WeightTime,p1-WeightWholeTime);head-front=p1-next;free(p1

16、);elseprintf( %cn”,p1-state);p2=p1-next;while(p2-next & p2-arrivetime != t)p2=p2-next;/2.找位置往后插入if(p2-arrivetime != t)PCB *p3=p1,*p4; while(p3-next & p3-arrivetimenext;if(p3-arrivetimet)if(p4!=p1)/p1 插在 p4 后，頭為 p1-nexthead-front=p1-next;p1-next=p4-next;p4-next=p1;else 不做操作p4=p3=p2=NULL;elsep4=p3=p2=

17、NULL;elsehead-front=p1-next;p1-next=p2-next;p2-next=p1;if(head-front-runtimefront-runtime;elset=t+q;while(t=lt)p1=head-front;printf(%2d %s”,t,p1-Name);p1-runtime=p1-runtime-q;if(p1-runtimestate=C;printf( %cn”,p1-state);p1-FinishTime=t;p1-WeightTime=p1-FinishTime-p1-arrivetime;p1-WeightWholeTime=p1-W

18、eightTime/p1-wholetime;SumWT+=p1-WeightTime;SumWWT+=p1-WeightWholeTime;printf(時(shí)刻%2d進(jìn)程%s運(yùn)行結(jié)束，進(jìn)程%s周轉(zhuǎn)時(shí)間=%5.2f,帶權(quán)周轉(zhuǎn)時(shí)間 =%5.2fn”,t,p1-Name,p1-Name,p1-WeightTime,p1-WeightWholeTime);/printf(時(shí)刻2d 進(jìn)程s 運(yùn)行結(jié)束，t,p1-pname);head-front=p1-next;free(p1);elseprintf( %cn”,p1-state);if(!p1-next)head-front=p1;/若原隊(duì)列有多個(gè)進(jìn)程 elsehead-front=p1-next;head-rear-next=p1;head-rear=p1;p1-next=NULL;if(empty(head)return;elseif(head-front-runtimefront-runtime;elset=t+q;Main.cp