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

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

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

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

4、加一旦要求運行的時間減一，如此循環(huán)執(zhí)行，當(dāng)某一個進程的所需要運行的時間減少至0時，則將該進程的狀態(tài)設(shè)置為“e”。然后，將指針指向下一個未運行完成的進程，重復(fù)判斷，直至所有的進程都運行結(jié)束。4 .方案論證4.1 概要設(shè)計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):當(dāng)進程完成后，輸出鏈表中元素。5)intQueueEmpty(LinkQueue&Q):判斷鏈表是否為空。6)voidchioce(structPCBpcb口,intn):對于輸入鏈表中數(shù)的按關(guān)鍵字一到達(dá)時間用選擇法從小到大進行進行排序。7)voidcaidan():主菜單，包含：進程的創(chuàng)建和結(jié)果和結(jié)束。8)voidcreate():進程的創(chuàng)建。9)voidmain()：實現(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)體變量，存隊列的相關(guān)信息：QElemTypedata、structQNode*next。同時定義結(jié)構(gòu)體指針*QueuePtr,便于之后書寫開辟空問級表示。系統(tǒng)調(diào)用時，每次分配一個QNode®么大的空間進行存儲。3)typedefstructPCBcharname10;/進程名structPCB*next;/循環(huán)鏈指針intneed_time;/要求運行時間intworked_time;/已運行時間，初始為0charcondition;/進程狀態(tài)，只有“就緒”和“結(jié)束”兩種狀態(tài)intflag;/進程結(jié)束標(biāo)志，用于輸出PCB

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

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

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

10、judge()用來判斷進程全部運行結(jié)束標(biāo)志，即當(dāng)所有進程的狀態(tài)變?yōu)閑'(即完成狀態(tài))后，循環(huán)結(jié)束，表示所有進程都已運行成功。建立時間片輪轉(zhuǎn)算法creatProcess()對進程進行輪轉(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='

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

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

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

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

15、的認(rèn)識J.改革與開放,2011,04:140.5湯小丹.計算機操作系統(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<<"請選擇(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+)/求周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間WholeTimei=FinishedTimei-mi.ArrivalTime;WeightWholeTimei=(double)(WholeTimei*1.000000/mi.ServiceTime);Average_WT+=WholeTimei;Average_WWT+=WeightWholeTimei;)Average_WT/=n;/求平均周轉(zhuǎn)時間Average_WWT/=n;/求平均帶權(quán)周轉(zhuǎn)時間/輸出cout«""«endl;c

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

23、ndl;cout«"服務(wù)時間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«"周轉(zhuǎn)時間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)時間為："«Average_WT«endl;cout«"平均帶權(quán)周轉(zhuǎn)時

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;)/選擇排序，對結(jié)構(gòu)體中的關(guān)鍵字到達(dá)時間，按從小到大的順序排列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)建及結(jié)果*"<<endl;結(jié)束*"<<endl;cout<<"*cout<<''*1.cout<<''*2.voidcreate()cout<<"請輸入進程總數(shù)n的值(0<n<=100):"<<endl;cin>>n;while(n<0|n&g