時(shí)間片輪轉(zhuǎn)算法

1、、實(shí)驗(yàn)?zāi)康?1)在單處理器情況下按時(shí)間片輪轉(zhuǎn)算法實(shí)現(xiàn)處理器調(diào)度，輸出運(yùn)行動(dòng)態(tài) 變化過程。(2)通過算法的實(shí)現(xiàn)加深了解處理器調(diào)度的工作。二、實(shí)驗(yàn)內(nèi)容輸入實(shí)現(xiàn)處理器調(diào)度的幾個(gè)進(jìn)程信息，任意確定一組“要求運(yùn)行時(shí)間”，啟動(dòng)所設(shè)計(jì)的處理器調(diào)度程序，顯示逐次被選中進(jìn)程的進(jìn)程名以及進(jìn)程控制塊的動(dòng) 態(tài)變化過程。三、實(shí)驗(yàn)步驟1、任務(wù)分析：時(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)算法的主要實(shí)現(xiàn)過程是首先為每一個(gè)進(jìn)程創(chuàng)建一個(gè)進(jìn)程控制 塊，定義數(shù)據(jù)結(jié)構(gòu)，說明進(jìn)程控制塊所包含的內(nèi)容，有進(jìn)程名、進(jìn)程所需運(yùn)行時(shí)

2、問、已運(yùn)行時(shí)間和進(jìn)程的狀態(tài)以及指針的信息。實(shí)現(xiàn)的過程即運(yùn)用指針指向某一 個(gè)進(jìn)程，判斷當(dāng)前的進(jìn)程是否是就緒狀態(tài)" r”，如果是，則為該進(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é)束。2、概要設(shè)計(jì)：typedef struct PCB char name10; / struct PCB *next; / int need_time; / int worked_time; / char condition;

3、 / int flag; / PCB;PCB *front,*rear; / int N; /N 為進(jìn)程數(shù) (2)主程序的流程圖:(1)所用數(shù)據(jù)結(jié)構(gòu)及符號(hào)說明進(jìn)程名循環(huán)鏈指針要求運(yùn)行時(shí)間已運(yùn)行時(shí)間，初始為0進(jìn)程狀態(tài)，只有“就緒”和“結(jié)束”兩種狀態(tài)進(jìn)程結(jié)束標(biāo)志，用于輸出循環(huán)鏈隊(duì)列的頭指針和尾指針開始3、詳細(xì)設(shè)計(jì)(1)首先每一個(gè)進(jìn)程用個(gè)進(jìn)程控制塊 PC瞇代表。進(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)

4、行時(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”表示。(2)每次運(yùn)行所設(shè)計(jì)的處理器調(diào)度程序前，為每個(gè)進(jìn)程任意確定它的“要 求運(yùn)行時(shí)間”。把五個(gè)進(jìn)程按順序排成循環(huán)鏈隊(duì)列，用指針指出隊(duì)列連接情況。用指針表示輪到運(yùn)行的進(jìn)程，如下圖描述所示：KQK2QK3QK4QK5QK2K3K4K5Ki2431200000RRRRR(3)PCB1PCB2程序詳細(xì)設(shè)計(jì)步驟：PCB3PCB4PCB5a.首先建立PC

5、B勺數(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()來實(shí)現(xiàn)。b.建立函數(shù)judge()用來判斷進(jìn)程全部運(yùn)行結(jié)束標(biāo)志，即當(dāng)所有進(jìn)程的狀態(tài) 變?yōu)閑'(即完成狀態(tài))后，循環(huán)結(jié)束，表示所有進(jìn)程都已運(yùn)行成功。c.建立時(shí)間片輪轉(zhuǎn)算法creatProcess ()對(duì)進(jìn)程進(jìn)行輪轉(zhuǎn)運(yùn)行，首先指針s 指向第一個(gè)進(jìn)程PCB即s=front ,判斷該進(jìn)程的狀態(tài)是否為r'(就緒狀態(tài))， 即if(s->condition = 'r'),若是則表

6、示此進(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é)束，沒有則重復(fù)上面算法。當(dāng)所有進(jìn)程的狀態(tài)位都變 成'e'表示所有進(jìn)程運(yùn)行完成，則循環(huán)結(jié)束。d.建立主函數(shù)main(),輸入進(jìn)程數(shù)N,調(diào)用初始化循環(huán)鏈隊(duì)列函數(shù)creatPCB() 和時(shí)間片輪轉(zhuǎn)算法

7、creatProcess(N),每次選中進(jìn)程的進(jìn)程名以及運(yùn)行一次后進(jìn) 程隊(duì)列的變化，實(shí)現(xiàn)處理器的調(diào)度。4、調(diào)試分析：a.調(diào)試過程中遇到的問題及解決方案開始運(yùn)行到Q5運(yùn)行完成后顯示錯(cuò)誤，如下圖所示：原因：經(jīng)檢查程序發(fā)現(xiàn)語句if(s->condition='e' )printf("進(jìn)程$已經(jīng)運(yùn)行完成！ nn”,s->name);有錯(cuò)誤，因?yàn)楫?dāng)某個(gè)進(jìn)程運(yùn)行完成后，其狀態(tài)標(biāo)志已修改為e',所以再次循環(huán)運(yùn)行未完成的進(jìn)程時(shí)，當(dāng)運(yùn)行到此句時(shí)仍會(huì)將前 面已完成的進(jìn)程重新輸出一遍完成信息，導(dǎo)致輸出錯(cuò)誤。解決方案：為每個(gè)進(jìn)程加上一個(gè)結(jié)束標(biāo)志flag ,并賦初值為0,當(dāng)

8、進(jìn)程運(yùn)行 完成后，將flag 改為1,再將后面輸出改為if(s->condition='e' | s->flag=0 )printf("進(jìn)程s已經(jīng)運(yùn)行完成！ nn",s->name);s->flag=0;,這樣在前面進(jìn)程運(yùn)行完成輸出后，后面再循環(huán)時(shí)就不會(huì)重新輸出一遍了。b.改進(jìn)設(shè)想：本實(shí)驗(yàn)較簡(jiǎn)單，但還不夠完善，如未實(shí)現(xiàn)插入進(jìn)程功能，即進(jìn)程在運(yùn)行過程中可以插入其他的進(jìn)程再運(yùn)行。還有未進(jìn)行進(jìn)程優(yōu)先級(jí)判別，本實(shí)驗(yàn)?zāi)J(rèn)進(jìn)程的優(yōu)先級(jí)按輸入的先后順序從大到小排列的，還有其他功能等，希望在以后的實(shí)驗(yàn)中逐步完善。5、測(cè)試結(jié)果：a.首先輸出五個(gè)進(jìn)程的初

9、始狀態(tài)b.開始從進(jìn)程Q1開始按時(shí)間片輪轉(zhuǎn)運(yùn)行進(jìn)程，Q4先運(yùn)行完成c. 接著Q1 運(yùn)行完成d.接著Q5運(yùn)行完成e.再Q(mào)3運(yùn)行完成f.最后Q2運(yùn)行完成四、 實(shí)驗(yàn)總結(jié)因在早期的時(shí)間片輪轉(zhuǎn)法中，系統(tǒng)將所有的就緒進(jìn)程按照先來先服務(wù)的原則排成一個(gè)隊(duì)列，每次調(diào)度是，把 CPU配給隊(duì)首進(jìn)程，并令其執(zhí)行一個(gè)時(shí)間片。當(dāng)執(zhí)行的時(shí)間片用完時(shí)，調(diào)度程序停止該進(jìn)程的執(zhí)行，并將它送往就緒隊(duì)列的末尾； 然后， 再把處理機(jī)分配給就緒隊(duì)列中新的隊(duì)首進(jìn)程，同時(shí)也讓它執(zhí)行一個(gè)時(shí)間片。 在時(shí)間片輪轉(zhuǎn)算法中，時(shí)間片的大小對(duì)系統(tǒng)性能有很大的影響。如果選擇很小的時(shí)間片將有利于短作業(yè)，因?yàn)樗茌^快地完成，但會(huì)頻繁的發(fā)生中斷、進(jìn)程上下文的切換，

10、從而增加系統(tǒng)的開銷；反之，如果選擇太長時(shí)間片，使得每個(gè)進(jìn)程都能在一個(gè)時(shí)間片內(nèi)完成，所以， 一般定為時(shí)間片略大于一次典型地交互所需要的時(shí)間。在完成時(shí)間片輪轉(zhuǎn)算法的實(shí)現(xiàn)過程中，我們遇到了一些問題，比如怎樣運(yùn)用循環(huán)隊(duì)列，如何設(shè)計(jì)結(jié)構(gòu)體等等，也積極配合并思考進(jìn)行解決。整體來說，我們的算法雖然實(shí)現(xiàn)了體現(xiàn)進(jìn)程動(dòng)態(tài)運(yùn)行變化的過程，但是相對(duì)而言比較簡(jiǎn)單。實(shí)驗(yàn)中， 我們小組不斷討論對(duì)算法進(jìn)行優(yōu)化，使得運(yùn)行結(jié)果看起來更容易理解，也達(dá)到了處理機(jī)調(diào)度的功能。做實(shí)驗(yàn)讓我們對(duì)于時(shí)間片輪轉(zhuǎn)的思想理解的更加透徹，鞏固了理論知識(shí)的學(xué)習(xí)。實(shí)驗(yàn)心得體會(huì)：首先，我們認(rèn)為這次課程設(shè)計(jì)是對(duì)學(xué)習(xí)操作系統(tǒng)的一次綜合考察，鍛煉我們綜合分析問題

11、、解決問題的能力。初次得到課程設(shè)計(jì)的題目時(shí)，為程序本身的簡(jiǎn)單而竊喜過；實(shí)驗(yàn)過程中也出現(xiàn)了一些難題需要解決，為此去苦苦探索過。課程設(shè)計(jì)期間，幾乎有幾天我們完全投入進(jìn)去了，就像是在做一個(gè)相當(dāng)重要的項(xiàng)目一樣的感覺。曾經(jīng)跑過圖書館幾次， 只是為了一種新的想法得到實(shí)現(xiàn)，也曾多次登錄網(wǎng)站瀏覽網(wǎng)頁，為了彌補(bǔ)一些知識(shí)上的紕漏，為此曾灑下了真實(shí)的汗水。當(dāng)我們的想法得到實(shí)現(xiàn)，又學(xué)會(huì)了新的知識(shí)的時(shí)候，心中滿是欣喜，或許這是實(shí)踐出真知的真實(shí)驗(yàn)證，有付出就有回報(bào)的真實(shí)寫照吧。其次，我們感受了真誠的友誼。在實(shí)驗(yàn)中，遇到的問題是多方面的，而且有那么一部分是以前學(xué)過的C 問題，但是已經(jīng)忘卻或是以前沒有真正的理解過。但是你會(huì)發(fā)

12、現(xiàn)就在你的身邊，會(huì)有那么一批人在背后熱心的幫助你，讓你身處困境卻感到無限希望。這好像是人生的一種歷程，風(fēng)風(fēng)雨雨中我們一起走過，然后為了一些坑坑洼洼彼此真誠的幫助過和無私的付出過。團(tuán)隊(duì)的協(xié)作和彼此心的交流讓我們彼此豐厚起來，這也是我們成長中必不可失的重要部分。最后，我認(rèn)識(shí)到了自己的不足。平心而論，以前真的沒有認(rèn)真的學(xué)習(xí)過，即使是在聽課，可是后來卻沒有對(duì)學(xué)習(xí)中出現(xiàn)的問題而仔細(xì)分析過。得過且過，迷失了我前進(jìn)的方向，而現(xiàn)在卻又重新敞開了。不論是以后的學(xué)習(xí)還是工作，我想這都是很重要的，我們需要不斷進(jìn)步的動(dòng)力?？偟恼f來知識(shí)上的收獲很是重要，精神上的豐收也是更加可喜的，讓我知道了學(xué)無止境的道理。我們每一個(gè)人

13、永遠(yuǎn)不能滿足于現(xiàn)有的成就，人生就像在爬山，一座山峰的后面還有更高的山峰在等著你。挫折是一份財(cái)富，經(jīng)歷是一份擁有。這次課程設(shè)計(jì)必將成為我人生旅途上一個(gè)非常美好的回憶。五、附錄實(shí)驗(yàn)源程序如下：#include"stdio.h"#include"conio.h"#include"malloc.h"#include"string.h"#define NULL 0typedef struct PCBchar name10;/進(jìn)程名struct PCB *next; /鏈指針int need_time; /要求運(yùn)行時(shí)間int

14、worked_time; /已運(yùn)行時(shí)間char condition;/進(jìn)程狀態(tài)，只有“就緒 ”和 “結(jié)束 ”兩種狀態(tài)int flag;/進(jìn)程結(jié)束標(biāo)志PCB;PCB *front,*rear;int N; /N 為進(jìn)程數(shù)void creatPCB()/為每個(gè)進(jìn)程創(chuàng)建一個(gè)PCB 并初始化形成一個(gè)循環(huán)鏈 隊(duì)列PCB *p,*l;l = (PCB *)malloc(sizeof(PCB);printf("Please enter process name and timen");scanf("%s%d",l->name,&l->need_ti

15、me);l->condition = 'r' /進(jìn)程初始狀態(tài)為就緒l->worked_time = 0;l->next=NULL;l->flag=0;front=l;for(int i = 1;i < N ;i +)p = (PCB *)malloc(sizeof(PCB);scanf("%s%d",p->name,&p->need_time);p->condition = 'r'p->worked_time = 0;p->flag=0;l->next = p;l=l-

16、>next;rear=l;rear->next=front;void output() /進(jìn)程輸出函數(shù)printf("name runtime needtime staten");for(int j=1;j<=N;j+)printf(" %-4st%-4dt%-4dt%-cn",front->name,front->worked_time,front->need_tim e,front->condition);front=front->next;printf("n");int judge

17、(PCB *p) /判斷所有進(jìn)程運(yùn)行結(jié)束int flag = 1;for(int i=0;i<N;i+)if(p->condition != 'e')flag = 0;break;p=p->next;return flag;void creatProcess(int n) /時(shí)間片輪轉(zhuǎn)算法PCB *s,*p;int i,j,flag1=0;s = (PCB *)malloc(sizeof(PCB);s=front;printf("nn");output();printf("Press any key to continue.nn");getch();/按任意鍵繼續(xù)s=front;while(flag1 != 1)if(s->condition = 'r') s->worked_time+; s->need_time-;if(s->need_time=0) s->condition='e'output();printf("Press any key to continue.nn"); getch();if