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

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

2、、已運行時間和進程的狀態(tài)以及指針的信息。實現(xiàn)的過程即運用指針指向某一個進程，判斷當(dāng)前的進程是否是就緒狀態(tài)" r”，如果是，則為該進程分配一個時間片，同時， 已運行時間加一旦要求運行的時間減一， 如此循環(huán)執(zhí)行，當(dāng)某一個進程的所需要運行的時間減少至 0時，則將該進程的狀態(tài)設(shè)置為“ e”。然后，將指針指向下一個未運行完成的進程，重復(fù)判斷，直 至所有的進程都運行結(jié)束。2、概要設(shè)計：(1)所用數(shù)據(jù)結(jié)構(gòu)及符號說明typedef struct PCBchar name10; / struct PCB *next; int need_time; / int worked_time; / char c

3、ondition; / int flag;/PCB;PCB *front,*rear; / int N; /N為進程數(shù)(2)主程序的流程圖：進程名循環(huán)鏈指針要求運行時間已運行時間，初始為0進程狀態(tài)，只有“就緒”和“結(jié)束”兩種狀態(tài)進程結(jié)束標(biāo)志，用于輸出循環(huán)鏈隊列的頭指針和尾指針開始1輸入進程數(shù)N輸入各進程信息為每個進程創(chuàng)建PCB并初始化形成一個循環(huán)鏈隊列由于本實驗是模擬處理器調(diào)度的(3)程序說明：處理器調(diào)度總是由畚彰十東示的講程運行功能，所以，對被選中的進程并不實際的啟動運行，而是執(zhí)行：已運行時間+1來模擬進程的一次運行，表示進程已經(jīng)運行過一個單位的時間3、詳細設(shè)計(1)首先每一個進程用一個進程

4、控制塊 PC瞇代表。進程控制塊的格式為:其中，進程名一一作為進程的標(biāo)識，如 Q1、Q2等。指針一一進程按順序排成循環(huán)鏈隊列，用指針指出下一個進程的進程控制塊的首地址，最后一 個進程的指針指出第一個進程的進程控制塊首地址。指求運行時間一一假設(shè)進程需要運行的單位時間數(shù)。已運行時間一一假設(shè)進程已經(jīng)運行的單位時間數(shù)，初始值為“0”。狀態(tài)一一有兩種狀態(tài)，“就緒”和“結(jié)束”，初始狀態(tài)都為“就緒"，用"R'表示。當(dāng)一個進程運行結(jié)束后，它的狀態(tài)為“結(jié)束”，用“ E”表示。(2)每次運行所設(shè)計的處理器調(diào)度程序前，為每個進程任意確定它的“要求運行時間”把五個進程按順序排成循環(huán)鏈隊列，用

5、指針指出隊列連接情況。用指針表示輪到運行的進程,如下圖描述所示:K2QK3QK4QK5K3K4K5431000RRRKiPCB1PCB2PCB3PCB4PCB5(3)程序詳細設(shè)計步驟：a.首先建立PCB的數(shù)據(jù)結(jié)構(gòu)，為了便于正確輸出，加上了進程結(jié)束標(biāo)志 flag 。輸入進程信息 (包括進程名和要求運行的時間)，并為每個進程創(chuàng)建一個PCW初始化形成一個循環(huán)鏈隊列，用 函數(shù)creatPCB()來實現(xiàn)。b.建立函數(shù)judge()用來判斷進程全部運行結(jié)束標(biāo)志，即當(dāng)所有進程的狀態(tài)變?yōu)閑'(即完成狀態(tài))后，循環(huán)結(jié)束，表示所有進程都已運行成功。c.建立時間片輪轉(zhuǎn)算法creatProcess ()對進程

6、進行輪轉(zhuǎn)運行，首先指針 s指向第一個進程 PCB即s=front ,判斷該進程的狀態(tài)是否為r'(就緒狀態(tài))，即if(s->condition = 'r'),若是則表示此進程尚 未執(zhí)行結(jié)束，則執(zhí)行s->worked_time+且s->need_time-, if(s->need_time=0),則表示此進程已運行結(jié)束，將其狀態(tài)置為結(jié)束，即 s->condition='e',并 根據(jù)狀態(tài)位輸出完成信息，且以后不會再運行此進程。將指針指向下個進程，s=s->next ,并判斷所有進程是否已全部運行結(jié)束，沒有則重復(fù)上面算法。當(dāng)

7、所有進程的狀態(tài)位都變成e'表示所有進程運行完成，則循環(huán)結(jié)束。d.建立主函數(shù)main(),輸入進程數(shù)N,調(diào)用初始化循環(huán)鏈隊列函數(shù) creatPCB()和時間片輪轉(zhuǎn)算 法creatProcess(N)，每次選中進程的進程名以及運行一次后進程隊列的變化， 實現(xiàn)處理器的調(diào)度。 4、調(diào)試分析：a.調(diào)試過程中遇到的問題及解決方案開始運行到Q5運行完成后顯示錯誤，如下圖所示：原因：經(jīng)檢查程序發(fā)現(xiàn)語句if(s->condition='e' )printf("進程s已經(jīng)運行完成！nn”,s->name); 有錯誤，因為當(dāng)某個進程運行完成后，其狀態(tài)標(biāo)志已修改為 e&#

8、39;,所以再次循 環(huán)運行未完成的進程時，當(dāng)運行到此句時仍會將前面已完成的進程重新輸出一遍完成信息，導(dǎo)致輸出錯誤。解決方案：為每個進程加上一個結(jié)束標(biāo)志flag ,并賦初值為0,當(dāng)進程運行完成后，將flag改為1,再將后面輸出改為if(s->condition='e'| s->flag=0 )printf("進程$已經(jīng)運行完成！ nn”,s->name);s->flag=0;,這樣在前面進程運行完成輸出后，后面再循環(huán)時就不會重新輸出一遍了。b.改進設(shè)想：本實驗較簡單，但還不夠完善，如未實現(xiàn)插入進程功能，即進程在運行過程中 可以插入其他的進程再運行

9、。還有未進行進程優(yōu)先級判別，本實驗?zāi)J進程的優(yōu)先級按輸入的先后 順序從大到小排列的，還有其他功能等，希望在以后的實驗中逐步完善。5、測試結(jié)果：a.首先輸出五個進程的初始狀態(tài)b.開始從進程Q1開始按時間片輪轉(zhuǎn)運行進程，Q4先運行完成c.接著Q1運行完成d.接著Q5運行完成e.再Q(mào)3運行完成f.最后Q2運行完成四、實驗總結(jié)因在早期的時間片輪轉(zhuǎn)法中，系統(tǒng)將所有的就緒進程按照先來先服務(wù)的原則排成一個隊列，每次調(diào)度是，把CPU配給隊首進程，并令其執(zhí)行一個時間片。當(dāng)執(zhí)行的時間片用完時，調(diào)度程序停 止該進程的執(zhí)行，并將它送往就緒隊列的末尾；然后，再把處理機分配給就緒隊列中新的隊首進程， 同時也讓它執(zhí)行一個時

10、間片。在時間片輪轉(zhuǎn)算法中，時間片的大小對系統(tǒng)性能有很大的影響。如果選擇很小的時間片將有利于短作業(yè)，因為它能較快地完成，但會頻繁的發(fā)生中斷、進程上下文的切 換，從而增加系統(tǒng)的開銷；反之，如果選擇太長時間片，使得每個進程都能在一個時間片內(nèi)完成， 所以，一般定為時間片略大于一次典型地交互所需要的時間。在完成時間片輪轉(zhuǎn)算法的實現(xiàn)過程中， 我們遇到了一些問題，比如怎樣運用循環(huán)隊列，如何設(shè) 計結(jié)構(gòu)體等等，也積極配合并思考進行解決。整體來說，我們的算法雖然實現(xiàn)了體現(xiàn)進程動態(tài)運行 變化的過程，但是相對而言比較簡單。 實驗中，我們小組不斷討論對算法進行優(yōu)化，使得運行結(jié)果 看起來更容易理解，也達到了處理機調(diào)度的功

11、能。做實驗讓我們對于時間片輪轉(zhuǎn)的思想理解的更加 透徹，鞏固了理論知識的學(xué)習(xí)。實驗心得體會：首先，我們認為這次課程設(shè)計是對學(xué)習(xí)操作系統(tǒng)的一次綜合考察，鍛煉我 們綜合分析問題、解決問題的能力。初次得到課程設(shè)計的題目時，為程序本身的簡單而竊喜過；實驗過程中也出現(xiàn)了一些難題需要 解決，為此去苦苦探索過。課程設(shè)計期間，幾乎有幾天我們完全投入進去了，就像是在做一個相當(dāng) 重要的項目一樣的感覺。曾經(jīng)跑過圖書館幾次，只是為了一種新的想法得到實現(xiàn)， 也曾多次登錄網(wǎng) 站瀏覽網(wǎng)頁，為了彌補一些知識上的批漏，為此曾灑下了真實的汗水。當(dāng)我們的想法得到實現(xiàn)，又學(xué)會了新的知識的時候，心中滿是欣喜，或許這是實踐出真知的真實驗證

12、， 有付出就有回報的真實 寫照吧。其次，我們感受了真誠的友誼。在實驗中，遇到的問題是多方面的，而且有那么一部分是以前 學(xué)過的C問題，但是已經(jīng)忘卻或是以前沒有真正的理解過。但是你會發(fā)現(xiàn)就在你的身邊，會有那 么一批人在背后熱心的幫助你，讓你身處困境卻感到無限希望。這好像是人生的一種歷程，風(fēng)風(fēng)雨 雨中我們一起走過，然后為了一些坑坑洼洼彼此真誠的幫助過和無私的付出過。團隊的協(xié)作和彼此心的交流讓我們彼此豐厚起來，這也是我們成長中必不可失的重要部分。最后，我認識到了自己的不足。平心而論，以前真的沒有認真的學(xué)習(xí)過，即使是在聽課，可是 后來卻沒有對學(xué)習(xí)中出現(xiàn)的問題而仔細分析過。得過且過，迷失了我前進的方向，而

13、現(xiàn)在卻又重新敞開了。不論是以后的學(xué)習(xí)還是工作，我想這都是很重要的，我們需要不斷進步的動力?？偟恼f來知識上的收獲很是重要，精神上的豐收也是更加可喜的，讓我知道了學(xué)無止境的道理。 我們每一個人永遠不能滿足于現(xiàn)有的成就，人生就像在爬山，一座山峰的后面還有更高的山峰在等著你。挫折是一份財富，經(jīng)歷是一份擁有。這次課程設(shè)計必將成為我人生旅途上一個非常美好的回 憶。五、附錄實驗源程序如下：#include"stdio.h"#include"conio.h"#include"malloc.h"#include"string.h"#

14、define NULL 0typedef struct PCBchar name10;/進程名struct PCB *next; /鏈指針歡迎共閱int need_time;/要求運行時間int worked_time; 已運行時間char condition; /進程狀態(tài)，只有 就緒”和 結(jié)束"兩種狀態(tài)int flag;/進程結(jié)束標(biāo)志PCB；PCB *front,*rear;int N; /N為進程數(shù)void creatPCB()/為每個進程創(chuàng)建一個PCB并初始化形成一個循環(huán)鏈隊列PCB *p,*l;l = (PCB *)malloc(sizeof(PCB);printf(&quo

15、t;Please enter process name and timen");scanf("%s%d",l->name,&l->need_time);l->condition = 'r' /進程初始狀態(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-&

16、gt;need_time);p->condition = 'r'p->worked_time = 0;p->flag=0;l->next = p;l=l->next;rear=l;rear->next=front;void output()/進程輸出函數(shù)printf("name runtime needtime staten");for(int j=1;j<=N;j+)printf(" %-4st%-4dt%-4dt%-cn”,front->name,front->worked_time,fro

17、nt->need_time,front->condition); front=front->next;printf("n");int judge(PCB *p) /判斷所有進程運行結(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) /時間片輪轉(zhuǎn)算法 PCB *s,*p;int i,j,flag1=0;s = (PCB *)mallo

18、c(sizeof(PCB);s=front;printf("nAn");output();printf("Press any key to continuenn");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 continuenn"); getch(