時間片輪轉算法

1、時間片輪轉算法1 .課程設計的目的通過操作系統(tǒng)課程設計，通過對作業(yè)調度算法的設計，深入理解作業(yè)調度的原理，從原理分析、物理設計，到功能分析和應用程序的最終實現(xiàn)，讓我親自動手參與一個操作系統(tǒng)的模擬設計，真正理解和掌握操作系統(tǒng)的有關內容，加深對操作系統(tǒng)，軟件工程，程序設計語言的理論知識的理解和應用水平；在理論和實驗教學基礎上進一步鞏固已學基本理論及應用知識并加以綜合提高；學會將知識應用于實際的方法，提高分析和解決問題的能力，增強對手能力；并更好的理解和消化課本所學的知識，為畢業(yè)設計和以后工作打下必要基礎。2 .課程設計的開發(fā)語言在本次課程設計中，我們選擇了C+轉言作為我們所使用的開發(fā)語言，開發(fā)工具

2、則選用了MicrosoftVisualC+6.0。MFC昔助C+勺優(yōu)勢為Windows開發(fā)開辟了一片新天地，同時也借助ApplicationWizzard使開發(fā)者擺脫離了那些每次都必寫基本代碼，借助ClassWizard和消息映射使開發(fā)者擺脫了定義消息處理時那種混亂和冗長的代碼段。更重要的是利用C+勺封裝功能使開發(fā)者擺脫Windows中各種句柄的困擾，只需要面對C+”的對象，這樣一來使開發(fā)更接近開發(fā)語言而遠離系統(tǒng)。正因為MFO建立在C+勺基礎上，所以我強調C/C+鈉言基礎對開發(fā)的重要性。利用C+勺封裝性開發(fā)者可以更容易理解和操作各種窗口對象；利用C+勺派生性開發(fā)者可以減少開發(fā)自定義窗口的時間和

3、創(chuàng)造出可重用的代碼；利用虛擬性可以在必要時更好的控制窗口的活動。而且C+缽身所具備的超越C語言的特性都可以使開發(fā)者編寫出更易用，更靈活的代碼。3 .功能描述時間片輪轉的主要思想就是按順序為每一個進程一次只分配一個時間片的時間。算法要完成的功能就是將各個進程按照時間片輪轉運行的動態(tài)過程顯示出來。時間片輪轉算法的主要實現(xiàn)過程是首先為每一個進程創(chuàng)建一個進程控制塊，定義數(shù)據(jù)結構，說明進程控制塊所包含的內容，有進程名、進程所需運行時間、已運行時間和進程的狀態(tài)以及指針的信息。實現(xiàn)的過程即運用指針指向某一個進程，判斷當前的進程是否是就緒狀態(tài)"r”，如果是，則為該進程分配一個時間片，同時，已運行時間

4、加一旦要求運行的時間減一，如此循環(huán)執(zhí)行，當某一個進程的所需要運行的時間減少至0時，則將該進程的狀態(tài)設置為“e”。然后，將指針指向下一個未運行完成的進程，重復判斷，直至所有的進程都運行結束。4 .方案論證4.1 概要設計4.1.1 各模塊功能1)intInitQueue(LinkQueue&Q):輸入進程時，初始化輸入的鏈表。2)intDestroyQueue(LinkQueue&Q):運行完后，銷毀鏈表。3)intEnQueue(LinkQueue&Q,QElemTypee):將進程插入循環(huán)隊列中。4)intDeQueue(LinkQueue&Q,QElemTy

5、pee):當進程完成后，輸出鏈表中元素。5)intQueueEmpty(LinkQueue&Q):判斷鏈表是否為空。6)voidchioce(structPCBpcb口,intn):對于輸入鏈表中數(shù)的按關鍵字一到達時間用選擇法從小到大進行進行排序。7)voidcaidan():主菜單，包含：進程的創(chuàng)建和結果和結束。8)voidcreate():進程的創(chuàng)建。9)voidmain()：實現(xiàn)函數(shù)調用的總控制。4.1.2 相關數(shù)據(jù)類型1)typedefintQElemType自定義類型，定義QElemTy向int型。2)typedefstructQNodeQElemTypedata;struc

6、tQNode*next;QNode,*QueuePtr;采用結構體變量，存隊列的相關信息：QElemTypedata、structQNode*next。同時定義結構體指針*QueuePtr,便于之后書寫開辟空問級表示。系統(tǒng)調用時，每次分配一個QNode®么大的空間進行存儲。3)typedefstructPCBcharname10;/進程名structPCB*next;/循環(huán)鏈指針intneed_time;/要求運行時間intworked_time;/已運行時間，初始為0charcondition;/進程狀態(tài)，只有“就緒”和“結束”兩種狀態(tài)intflag;/進程結束標志，用于輸出PCB

7、;PCB*front,*rear;/循環(huán)鏈隊列的頭指針和尾指針intN;/N為進程數(shù)定義循環(huán)鏈表的頭指針和尾指針。QueuePtrfront,QueuePtrrear。4)structPCBintArrivalTime;intServiceTime;harnumber;mMaxNum;采用結構體數(shù)組，創(chuàng)建一個進程，包含進程相關信息：進程名稱、進程到達時間、進程服務時間。4.2.3總體設計程序總體設計：首先選擇1創(chuàng)建進程，輸入進程總數(shù)，進程的名稱，各進程到達的時間，各進程服務的時間，以及時間片q的值，運行出結果。選擇2將結束運行，如圖1所示。箔束L進程的創(chuàng)建及結果時間片卷專篁法輸入迸程數(shù)圖1系統(tǒng)

8、總體設計輸出運行結果4.1.5程序說明處理器調度總是選擇指針指示的進程運行。由于本實驗是模擬處理器調度的功能，所以，對被選中的進程并不實際的啟動運行，而是執(zhí)行：已運行時間+1來模擬進程的一次運行，表示進程已經(jīng)運行過一個單位的時間。4.2詳細設計首先每一個進程用一個進程控制塊PCB來代表。進程控制塊的格式如表3所示。表3PCB控制塊要求運行時間已運行時間其中，進程名一一作為進程的標識，如Q1、Q2等。指針一一進程按順序排成循環(huán)鏈隊列，用指針指出下一個進程的進程控制塊的首地址，最后一個進程的指針指出第一個進程的進程控制塊首地址。已運行時間一一假設進程已經(jīng)運行的單位時間數(shù)，初始值為“0”。狀態(tài)一一有

9、兩種狀態(tài)，“就緒”和“結束”，初始狀態(tài)都為“就緒"，用"R'表示。當一個進程運行結束后，它的狀態(tài)為“結束”，用“E”表示。每次運行所設計的處理器調度程序前，為每個進程任意確定它的“要求運行時間”。把五個進程按順序排成循環(huán)鏈隊列，用指針指出隊列連接情況。用指針表示輪到運行的進程，如表4描述述所示。表4進程隊列4K3QK430RPCB3PCB24.3程序詳細設計步驟首先建立PCB的數(shù)據(jù)結構，為了便于正確輸出，加上了進程結束標志flagPC輸入進程信息(包括進程名和要求運行的時間)，并為每個進程創(chuàng)建一個并初始化形成一個循環(huán)鏈隊列，用函數(shù)creatPCB()來實現(xiàn)。建立函數(shù)

10、judge()用來判斷進程全部運行結束標志，即當所有進程的狀態(tài)變?yōu)閑'(即完成狀態(tài))后，循環(huán)結束，表示所有進程都已運行成功。建立時間片輪轉算法creatProcess()對進程進行輪轉運行，首先指針s指向第一個進程PCB即s=front,判斷該進程的狀態(tài)是否為r'(就緒狀態(tài))，即if(s->condition='r'),若是則表示此進程尚未執(zhí)行結束，則執(zhí)行s->worked_time+且s->need_time-,if(s->need_time=0),貝表示止匕進程已運行結束，將其狀態(tài)置為結束，即s->condition='

11、e',并根據(jù)狀態(tài)位輸出完成信息，且以后不會再運行此進程。將指針指向下個進程，s=s->next,并判斷所有進程是否已全部運行結束，沒有則重復上面算法。當所有進程的狀態(tài)位都變成e'表示所有進程運行完成，則循環(huán)結束。建立主函數(shù)main(),輸入進程數(shù)N,調用初始化循環(huán)鏈隊列函數(shù)creatPCB()和時間片輪轉算法creatProcess(N),每次選中進程的進程名以及運行一次后進程隊列的變化，實現(xiàn)處理器的調度5.程序的運行及結果1)主菜單：輸入選項1:進程創(chuàng)建及結果2:結束，如圖5所示圖5主菜單2）運行過程：選才?1,創(chuàng)建進程。輸入進程總數(shù)，進程的名稱a、b,各進程到達的時間

12、，各進程服務的時間，以及時間片q的值。當輸入進程為2時，各進程到達時間為3,2,各進程服務時間為2,3,以及時間片q=2時的情況，輸入情況如圖6所示。圖6創(chuàng)建進程3）輸入成功后，按回車鍵，進程在程序中的具體實現(xiàn)情況即：時間輪轉情況。進程在調度算法中，計算出的具體的完成時間，周轉時間，帶權時間，平均周轉時間，平均帶權周轉時間，如圖7所示。行尊正仃運i適伍在在在在在正正J正正0011M-港井_升1ftV_A¥n.-aBK2345b噢離刻刻刻.errkk、程運行的結果是:圖7進程運行結果3）選擇2:退出界面，如圖8。圖8退出界面6 .心得體會首先，我認為這次課程設計是對學習操作系統(tǒng)的一次綜

13、合考察，鍛煉我綜合分析問題、解決問題的能力。初次找到課程設計的題目時，為程序本身的簡單而竊喜過；實驗過程中也出現(xiàn)了一些難題需要解決，為此去苦苦探索過。課程設計期間，曾多次登錄網(wǎng)站瀏覽網(wǎng)頁，為了彌補一些知識上的批漏，一次次實踐。當我的想法得到實現(xiàn)，又學會了新的知識的時候，心中滿是欣喜，或許這是實踐出真知的真實驗證，有付出就有回報的真實寫照吧。其次，我們感受了真誠的友誼。在實驗中，遇到的問題是多方面的，而且有那么一部分是以前學過的問題，但是已經(jīng)忘卻或是以前沒有真正的理解過。但是你會發(fā)現(xiàn)就在你的身邊，會有那么一批人在背后熱心的幫助你，這好像是人生的一種歷程，團隊的協(xié)作和彼此心的交流讓我們彼此豐厚起來

14、，這也是我們成長中必不可失的重要部分。最后，我認識到了自己的不足。平心而論，以前真的沒有認真的學習過，即使是在聽課，可是后來卻沒有對學習中出現(xiàn)的問題而仔細分析過。得過且過，迷失了我前進的方向，而現(xiàn)在卻又重新敞開了。不論是以后的學習還是工作，我想這都是很重要的，我需要不斷進步的動力。7 .參考文獻1陳莉君等.Linux操作系統(tǒng)原理與應用M.北京:清華大學出版社.2012.12李龍來，吳杰，呂智慧，楊明.基于Wet®務的分布式文件系統(tǒng)管理與優(yōu)化方案J.計算機工程與設計,2012.3龐麗萍，陽富民.計算機操作系統(tǒng)（第2版）M.北京：人民郵電出版社.2014.14孫洪慶.淺談對計算機操作系統(tǒng)

15、的認識J.改革與開放,2011,04:140.5湯小丹.計算機操作系統(tǒng)（第4版）M.西安：電子科技大學出版社.2014.5附錄：#include<iostream.h>#include<iomanip.h>#include<malloc.h>typedefintQElemType;staticconstintMaxNum=100;typedefstructQNodeQElemTypedata;structQNode*next;QNode,*QueuePtr;typedefstructQueuePtrfront;QueuePtrrear;LinkQueue;s

16、tructPCBintArrivalTime;intServiceTime;charnumber;mMaxNum;intInitQueue(LinkQueue&Q);intDestroyQueue(LinkQueue&Q);intEnQueue(LinkQueue&Q,QElemTypee);intDeQueue(LinkQueue&Q,QElemTypee);intQueueEmpty(LinkQueue&Q);voidchioce(structPCBpcb,intn);voidcaidan();voidcreate();intn,q,Finished

17、TimeMaxNum,WholeTimeMaxNum;doubleWeightWholeTimeMaxNum,Average_WT=0,Average_WWT=0;LinkQueueQ;voidRR(int*ArrivalTime,int*ServiceTime,intn,intq,LinkQueue&Q);voidmain()while(1)/system("cls");cout<<endl;caidan();intn;cout<<"請選擇(1-2):"<<endl;cin>>n;if(n<

18、1|n>2)cout<<"輸入有誤，請重新輸入"<<endl;switch(n)case1:create();break;case2:return;/RR算法的具體實現(xiàn)voidRR(int*ArrivalTime,int*ServiceTime,intn,intq,LinkQueue&Q)intcountTime=0,e;chioce(m,n);if(ArrivalTime0=0)countTime=0;elsecountTime=m0.ArrivalTime;intSTimeMaxNum,pushedMaxNum;for(inti=0

19、;i<n;i+)STimei=mi.ServiceTime;pushedi=0;InitQueue(Q);EnQueue(Q,0);pushed0=1;inttime=m0.ArrivalTime;while(QueueEmpty(Q)=false)e=DeQueue(Q,e);if(STimee>q)STimee=STimee-q;countTime+=q;elsecountTime+=STimee;STimee=0;FinishedTimee=countTime;while(time<countTime)if(STime>0)cout<<"時亥

20、U"<<setw(2)<<time<<":進程"<<e<<"正在運行"<<endl;time+;for(i=1;i<n;i+)if(STime!=0&&i!=e&&mi.ArrivalTime<countTime&&pushedi=0|STime!=0&&i!=e&&mi.ArrivalTime=countTime)EnQueue(Q,i);pushedi=1;if(STimee&g

21、t;0)/判斷進程e是否已執(zhí)行完EnQueue(Q,e);for(i=0;i<n;i+)/求周轉時間和帶權周轉時間WholeTimei=FinishedTimei-mi.ArrivalTime;WeightWholeTimei=(double)(WholeTimei*1.000000/mi.ServiceTime);Average_WT+=WholeTimei;Average_WWT+=WeightWholeTimei;)Average_WT/=n;/求平均周轉時間Average_WWT/=n;/求平均帶權周轉時間/輸出cout«""«endl;c

22、out«endl;cout«endl;cout«"進程運行的結果是："«endl;cout«"-"«endl;cout«"進程名稱for(i=0;i<n;i+)cout«setw(8)«mi.number«"cout«endl;cout«"到達時間for(i=0;i<n;i+)cout«setw(8)«mi.ArrivalTime«"cout«e

23、ndl;cout«"服務時間for(i=0;i<n;i+)cout«setw(8)«mi.ServiceTime<<"cout«endl;cout«"完成時間for(i=0;i<n;i+)cout«setw(8)«FinishedTimei<<"cout«endl;cout«"周轉時間for(i=0;i<n;i+)cout«setw(8)«WholeTimei<<"cout

24、«endl;cout«"帶權周轉："«"for(i=0;i<n;i+)cout«setw(8)«setiosflags(ios:fixed)«setprecision(2)«WeightWholeTimei«"H.5cout«endl;cout«"-"«endl;cout«"平均周轉時間為："«Average_WT«endl;cout«"平均帶權周轉時

25、間為："<<Average_WWT«endl;DestroyQueue(Q);/初始化鏈隊列QintlnitQueue(LinkQueue&Q)(Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);Q.front->next=NULL;return1;)/銷毀鏈隊列QintDestroyQueue(LinkQueue&Q)(while(Q.front)(Q.rear=Q.front->next;free(Q.front);Q.front=Q.rear;)return1;)/入隊intEnQueu

26、e(LinkQueue&Q,QElemTypee)(QueuePtrp=(QueuePtr)malloc(sizeof(QNode);p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;return1;)/出隊，并用e返回出隊節(jié)點的元素值intDeQueue(LinkQueue&Q,QElemTypee)(QueuePtrp;if(Q.front=Q.rear)return0;p=Q.front->next;e=p->data;Q.front->next=p->next;if(Q.rear=p)

27、(Q.rear=Q.front;)free(p);returne;)/判斷鏈隊列Q是否為空intQueueEmpty(LinkQueue&Q)(if(Q.front=Q.rear)returntrue;elsereturnfalse;)/選擇排序，對結構體中的關鍵字到達時間，按從小到大的順序排列voidchioce(structPCBpcb口,intn)(inti,j;structPCBt;for(j=0;j<n-1;j+)for(i=0;i<n-1-j;i+)if(pcbi.ArrivalTime>pcbi+1.ArrivalTime)t=pcbi;pcbi=pcbi+1;pcbi+1=t;voidcaidan()主頁*"<<endl;進程創(chuàng)建及結果*"<<endl;結束*"<<endl;cout<<"*cout<<''*1.cout<<''*2.voidcreate()cout<<"請輸入進程總數(shù)n的值(0<n<=100):"<<endl;cin>>n;while(n<0|n&g