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

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

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

3、創(chuàng)造出可重用的代碼；利用虛擬性可以在必要時(shí)更好的控制窗口的活動(dòng)。而且C+缽身所具備的超越C語言的特性都可以使開發(fā)者編寫出更易用，更靈活的代碼。3 .功能描述時(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í)間、已運(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í)間

4、加一旦要求運(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é)束。4 .方案論證4.1 概要設(shè)計(jì)4.1.1 各模塊功能1)intInitQueue(LinkQueue&Q):輸入進(jìn)程時(shí)，初始化輸入的鏈表。2)intDestroyQueue(LinkQueue&Q):運(yùn)行完后，銷毀鏈表。3)intEnQueue(LinkQueue&Q,QElemTypee):將進(jìn)程插入循環(huán)隊(duì)列中。4)intDeQueue(LinkQueue&Q,QElemTy

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

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

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

8、總體設(shè)計(jì)輸出運(yùn)行結(jié)果4.1.5程序說明處理器調(diào)度總是選擇指針指示的進(jìn)程運(yùn)行。由于本實(shí)驗(yàn)是模擬處理器調(diào)度的功能，所以，對(duì)被選中的進(jìn)程并不實(shí)際的啟動(dòng)運(yùn)行，而是執(zhí)行：已運(yùn)行時(shí)間+1來模擬進(jìn)程的一次運(yùn)行，表示進(jìn)程已經(jīng)運(yùn)行過一個(gè)單位的時(shí)間。4.2詳細(xì)設(shè)計(jì)首先每一個(gè)進(jìn)程用一個(gè)進(jìn)程控制塊PCB來代表。進(jìn)程控制塊的格式如表3所示。表3PCB控制塊要求運(yùn)行時(shí)間已運(yùn)行時(shí)間其中，進(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)程已經(jīng)運(yùn)行的單位時(shí)間數(shù)，初始值為“0”。狀態(tài)一一有

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

10、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)行成功。建立時(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'),若是則表示此進(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='

11、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é)束。建立主函數(shù)main(),輸入進(jìn)程數(shù)N,調(diào)用初始化循環(huán)鏈隊(duì)列函數(shù)creatPCB()和時(shí)間片輪轉(zhuǎn)算法creatProcess(N),每次選中進(jìn)程的進(jìn)程名以及運(yùn)行一次后進(jìn)程隊(duì)列的變化，實(shí)現(xiàn)處理器的調(diào)度5.程序的運(yùn)行及結(jié)果1)主菜單：輸入選項(xiàng)1:進(jìn)程創(chuàng)建及結(jié)果2:結(jié)束，如圖5所示圖5主菜單2）運(yùn)行過程：選才?1,創(chuàng)建進(jìn)程。輸入進(jìn)程總數(shù)，進(jìn)程的名稱a、b,各進(jìn)程到達(dá)的時(shí)間

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

13、合考察，鍛煉我綜合分析問題、解決問題的能力。初次找到課程設(shè)計(jì)的題目時(shí)，為程序本身的簡單而竊喜過；實(shí)驗(yàn)過程中也出現(xiàn)了一些難題需要解決，為此去苦苦探索過。課程設(shè)計(jì)期間，曾多次登錄網(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é)過的問題，但是已經(jīng)忘卻或是以前沒有真正的理解過。但是你會(huì)發(fā)現(xiàn)就在你的身邊，會(huì)有那么一批人在背后熱心的幫助你，這好像是人生的一種歷程，團(tuán)隊(duì)的協(xié)作和彼此心的交流讓我們彼此豐厚起來

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

15、的認(rèn)識(shí)J.改革與開放,2011,04:140.5湯小丹.計(jì)算機(jī)操作系統(tǒng)（第4版）M.西安：電子科技大學(xué)出版社.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<<"請(qǐng)選擇(1-2):"<<endl;cin>>n;if(n<

18、1|n>2)cout<<"輸入有誤，請(qǐng)重新輸入"<<endl;switch(n)case1:create();break;case2:return;/RR算法的具體實(shí)現(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<<"時(shí)亥

20、U"<<setw(2)<<time<<":進(jìn)程"<<e<<"正在運(yùn)行"<<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)/判斷進(jìn)程e是否已執(zhí)行完EnQueue(Q,e);for(i=0;i<n;i+)/求周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間WholeTimei=FinishedTimei-mi.ArrivalTime;WeightWholeTimei=(double)(WholeTimei*1.000000/mi.ServiceTime);Average_WT+=WholeTimei;Average_WWT+=WeightWholeTimei;)Average_WT/=n;/求平均周轉(zhuǎn)時(shí)間Average_WWT/=n;/求平均帶權(quán)周轉(zhuǎn)時(shí)間/輸出cout«""«endl;c

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

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

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

25、間為："<<Average_WWT«endl;DestroyQueue(Q);/初始化鏈隊(duì)列QintlnitQueue(LinkQueue&Q)(Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);Q.front->next=NULL;return1;)/銷毀鏈隊(duì)列QintDestroyQueue(LinkQueue&Q)(while(Q.front)(Q.rear=Q.front->next;free(Q.front);Q.front=Q.rear;)return1;)/入隊(duì)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;)/出隊(duì)，并用e返回出隊(duì)節(jié)點(diǎn)的元素值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;)/判斷鏈隊(duì)列Q是否為空intQueueEmpty(LinkQueue&Q)(if(Q.front=Q.rear)returntrue;elsereturnfalse;)/選擇排序，對(duì)結(jié)構(gòu)體中的關(guān)鍵字到達(dá)時(shí)間，按從小到大的順序排列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;進(jìn)程創(chuàng)建及結(jié)果*"<<endl;結(jié)束*"<<endl;cout<<"*cout<<''*1.cout<<''*2.voidcreate()cout<<"請(qǐng)輸入進(jìn)程總數(shù)n的值(0<n<=100):"<<endl;cin>>n;while(n<0|n&g