多級反饋隊列調(diào)度算法的實現(xiàn)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上學(xué)生實習(xí)報告課程名稱_ 數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)處理應(yīng)用訓(xùn)練 題目名稱 多級反饋隊列調(diào)度算法的實現(xiàn) 學(xué)生學(xué)院 計算機(jī)與計算科學(xué) 專業(yè)班級 學(xué) 號 學(xué)生姓名 指導(dǎo)教師 2012 年 2 月 16 日多級反饋隊列調(diào)度算法的實現(xiàn)【摘要】 多級反饋隊列調(diào)度算法是操作系統(tǒng)中CPU處理機(jī)調(diào)度算法之一，該算法既能使高優(yōu)先級的進(jìn)程（任務(wù)）得到響應(yīng)又能使短進(jìn)程（任務(wù)）迅速完成。UNIX操作系統(tǒng)便采取這種算法，而本次試驗就是試用C語言模擬某多級反饋隊列調(diào)度算法。本次試驗中前三級就緒隊列采用時間片輪轉(zhuǎn)法，時間片大小分別為2、4和8，最后一級就緒隊列采用FIFO調(diào)度，將任務(wù)進(jìn)入多級隊列進(jìn)行模擬，任務(wù)從

2、優(yōu)先級高的隊列到優(yōu)先級地的隊列的順序逐一進(jìn)入，還用了算法支持搶占式，最后完成模擬，得到各個任務(wù)先后完成的順序，還有得到各個任務(wù)的響應(yīng)時間、離開時間、周轉(zhuǎn)時間?！娟P(guān)鍵詞】 隊列 優(yōu)先級 任務(wù) 時間 1 內(nèi)容與要求【內(nèi)容】 多級反饋隊列調(diào)度算法是操作系統(tǒng)中CPU處理機(jī)調(diào)度算法之一，該算法既能使高優(yōu)先級的進(jìn)程（任務(wù)）得到響應(yīng)又能使短進(jìn)程（任務(wù)）迅速完成。UNIX操作系統(tǒng)便采取這種算法，本次試驗就是試用C語言模擬某多級反饋隊列調(diào)度算法，通過輸入任務(wù)號、到達(dá)時間、運(yùn)行時間，求出任務(wù)完成的先后順序以及各個任務(wù)的響應(yīng)時間、離開時間、周轉(zhuǎn)時間。【要求】多級反饋隊列調(diào)度算法描述：1、該調(diào)度算法設(shè)置四級就緒隊列：

3、前三級就緒隊列采用時間片輪轉(zhuǎn)法，時間片大小分別為2、4和8；最后一級就緒隊列采用FIFO調(diào)度。2、任務(wù)在進(jìn)入待調(diào)度的隊列等待時，首先進(jìn)入優(yōu)先級最高的隊列等待。3、首先調(diào)度優(yōu)先級高的隊列中的任務(wù)。若高優(yōu)先級中隊列中已沒有調(diào)度的任務(wù)，則調(diào)度次優(yōu)先級隊列中的任務(wù)，依次類推。4、對于同一個隊列中的各個任務(wù)，按照隊列指定調(diào)度方法調(diào)度。每次任務(wù)調(diào)度執(zhí)行后，若沒有完成任務(wù)，就被降到下一個低優(yōu)先級隊列中。5、在低優(yōu)先級的隊列中的任務(wù)在運(yùn)行時，又有新到達(dá)的任務(wù)，CPU馬上分配給新到達(dá)的任務(wù)。（注：與原來的題目不同，原題是在低優(yōu)先級的隊列中的任務(wù)在運(yùn)行時，又有新到達(dá)的任務(wù)時，要在運(yùn)行完這個時間片后，CPU馬上分配

4、給新到達(dá)的任務(wù)，而本題不需要在運(yùn)行完這個時間片，即正在進(jìn)行的任務(wù)立刻停止，CPU馬上分配給新到達(dá)的任務(wù)）6、為方便實現(xiàn)，時間以1為單位，用整數(shù)數(shù)據(jù)表示；且每個時間點，最多只有一個任務(wù)請求服務(wù)（即輸入）。2 總體設(shè)計2.1 算法總體思路：這是建立在一個時間軸上的，即時刻，一個一個時刻（時間點）進(jìn)行。 2.1.1 主函數(shù)思路：先初始化所有隊列，再輸入任務(wù)個數(shù)，如果輸入個數(shù)為0，則重新輸入，然后輸入各個任務(wù)的信息，即任務(wù)號、到達(dá)時間、運(yùn)行時間，再當(dāng)時刻到任務(wù)的到達(dá)時間時，就創(chuàng)建任務(wù)，然后運(yùn)行任務(wù)，時刻自動加1 ，創(chuàng)建任務(wù)與運(yùn)行任務(wù)進(jìn)行循環(huán)，直到所有任務(wù)進(jìn)行完或所有隊列為空才跳出循環(huán)，最后清空所有隊列

5、。2.1.2 功能函數(shù)思路：void create(LinkQueue* x,Job job)：使任務(wù)的已運(yùn)行時間為0，再使任務(wù)進(jìn)入第一個隊列。void function(LinkQueue* x, int timing)：四個隊列從第一個到第四個，即從最高優(yōu)先級開始，任務(wù)在4個隊列中逐個進(jìn)行，根據(jù)任務(wù)是否為第一次執(zhí)行，求出響應(yīng)時間，任務(wù)完成時，求出離開時間和周轉(zhuǎn)時間輸出信息，在前3個隊列，如果任務(wù)剛完成一個就緒隊列的時間片，就降低優(yōu)先級，使任務(wù)進(jìn)入下一個隊列。2.2 功能模塊介紹：void main ()函數(shù)功能：主函數(shù)void InitQueue(LinkQueue& HQ)：隊列

6、的初始化void EnQueue(LinkQueue& HQ,ElemType item) 函數(shù)功能：向隊列中插入一個元素ElemType OutQueue(LinkQueue& HQ) 函數(shù)功能：從隊列中刪除一個元素 ElemType *PeekQueue(LinkQueue& HQ) 函數(shù)功能：讀取隊首元素bool EmptyQueue(LinkQueue& HQ) 函數(shù)功能：檢查隊列是否為空void ClearQueue(LinkQueue& HQ) 函數(shù)功能：清除鏈隊中的所有元素，使之變?yōu)榭贞爒oid create(LinkQueue* x,Jo

7、b job) 函數(shù)功能：創(chuàng)建任務(wù)。void function(LinkQueue* x, int timing) 函數(shù)功能：任務(wù)運(yùn)行。2.3 輸入輸出輸入：任務(wù)號 到達(dá)時間 運(yùn)行時間輸出：任務(wù)號 響應(yīng)時間 離開時間 周轉(zhuǎn)時間、2.4 文件介紹main.cpp:主函數(shù)的存放，功能函數(shù)的調(diào)用。queue.h:隊列的各個基本功能函數(shù)，任務(wù)的創(chuàng)建函數(shù)與運(yùn)行函數(shù)。3 詳細(xì)設(shè)計3.1存儲結(jié)構(gòu)描述struct Job int jobnum; /任務(wù)號 int arrivetime; /到達(dá)時間 int burst; /運(yùn)行時間 int retime; /響應(yīng)時間 int leavetime; /離開時間 i

8、nt roundtime; /周轉(zhuǎn)時間 int runtime; /已運(yùn)行時間;/任務(wù)的存儲結(jié)構(gòu)typedef Job ElemType;/任務(wù)的類型定義struct LNodeElemType data;/值域LNode* next;/鏈接指針域;struct LinkQueueLNode* front;/隊首指針LNode* rear;/隊尾指針;3.2 參數(shù)說明timing是時刻，時間軸；Job *jobing：任務(wù)數(shù)組（動態(tài)分配）int leatime4;/時間片大小到達(dá)時間：任務(wù)請求的時刻運(yùn)行時間：任務(wù)運(yùn)行完需要的時間響應(yīng)時間：任務(wù)從到達(dá)時間到任務(wù)第一次執(zhí)行的時間差周轉(zhuǎn)時間：任務(wù)從開

9、始請求（到達(dá)時間）到任務(wù)完成離開的時間已運(yùn)行時間：任務(wù)已運(yùn)行的時間離開時間：任務(wù)運(yùn)行完后離開隊列的時刻3.3 具體算法void InitQueue(LinkQueue& HQ)算法：隊首隊尾設(shè)置為空。void EnQueue(LinkQueue& HQ,ElemType item)算法：得到一個新結(jié)點，把item的值賦給新結(jié)點的值域，再把新結(jié)點的指針域置空，若鏈隊為空，則新結(jié)點既是隊首又是隊尾，若鏈隊非空，則新結(jié)點被鏈接到隊尾并修改隊尾指針。ElemType OutQueue(LinkQueue& HQ)算法：若鏈隊為空則中止運(yùn)行，暫存隊首元素以便返回，暫存隊首指針以便

10、收回隊首節(jié)點，使隊首指針指向下一個結(jié)點，若刪除后鏈隊為空，則使隊尾指針為空，然后回收原隊首節(jié)點，返回被刪除的隊首元素。ElemType *PeekQueue(LinkQueue& HQ)算法：若鏈隊為空則中止運(yùn)行，返回隊首元素指針（Job*）。bool EmptyQueue(LinkQueue& HQ)算法：判斷隊首或隊尾任一個指針是否為空即可。void ClearQueue(LinkQueue& HQ)算法：隊首指針賦給p，依次刪除隊列中的每個結(jié)點，然后循環(huán)結(jié)束后隊首指針已經(jīng)變空，置隊尾指針為空。void create(LinkQueue* x,Job job)算法：

11、使任務(wù)的已運(yùn)行時間為0，再使任務(wù)進(jìn)入第一個隊列。void function(LinkQueue* x, int timing) 算法：將4個隊列設(shè)為循環(huán)，從第一個隊列開始到第四個隊列逐個進(jìn)行以下操作。判斷隊列是否為空，當(dāng)隊列不為空時，則繼續(xù)，若該隊列的已運(yùn)行時間為1并且時刻已等于或大于任務(wù)的到達(dá)時間，即判斷任務(wù)是否為第一次執(zhí)行，若是，求出任務(wù)響應(yīng)時間=當(dāng)前時刻-任務(wù)到達(dá)時間，即發(fā)出請求到任務(wù)開始的時間差。如果運(yùn)行完，求出任務(wù)離開時間=當(dāng)前時刻+1，周轉(zhuǎn)時間=離開時間-到達(dá)時間，輸出任務(wù)信息，再判斷該任務(wù)是否完成該隊列的時間片，若是，則降低優(yōu)先級，任務(wù)進(jìn)入下一級隊列。所有隊列遍歷完，任務(wù)均完成，

12、循環(huán)結(jié)束。4 程序測試測試一：測試數(shù)據(jù)：1 0 82 6 43 9 12測試二：測試數(shù)據(jù)：1 0 72 5 43 7 134 12 9測試三：當(dāng)輸入錯誤，輸入任務(wù)個數(shù)是0，重新輸入測試數(shù)據(jù)：1 0 72 5 43 7 134 12 9測試四：測試數(shù)據(jù)：1 1 52 4 2測試五：測試數(shù)據(jù)：1 2 82 3 23 7 54 9 105 14 6選作（同個時間點多個任務(wù)請求）測試六：測試數(shù)據(jù)：1 2 32 2 43 6 94 6 75 總結(jié) 這次實驗用了多級反饋隊列調(diào)度算法，這個算法我們沒有學(xué)過，所以理解有點困難，但是，這個算法中涉及到了隊列，它是隊列的升級，是多級隊列，因此，我在此不僅學(xué)到了新的

13、知識，還是對數(shù)據(jù)結(jié)構(gòu)中隊列部分的熟悉與加深，更好的掌握了隊列知識。這次實驗我的題目與原題有點差別，在低優(yōu)先級的隊列中的任務(wù)在運(yùn)行時，又有新到達(dá)的任務(wù)，那么在運(yùn)行完這個時間片后，CPU馬上分配給新到達(dá)的任務(wù)，即算法支持搶占式，但我的程序確是在新到達(dá)的任務(wù)，那么這個任務(wù)立即中止，CPU馬上分配給新到達(dá)的任務(wù)，我覺得這樣更好。當(dāng)然，這次編程中遇到過許多困難，比如存儲結(jié)構(gòu)順序的錯誤，又比如ElemType *PeekQueue(LinkQueue& HQ)，這是與隊列的原基礎(chǔ)功能函數(shù)有所區(qū)別，它需要的是返回元素指針（Job*），我原來返回的是元素，后來經(jīng)過調(diào)試，錯誤提示，才改正確等等。多級反饋

14、隊列調(diào)度算法是操作系統(tǒng)中CPU處理機(jī)調(diào)度算法之一，該算法既能使高優(yōu)先級的進(jìn)程（任務(wù)）得到響應(yīng)又能使短進(jìn)程（任務(wù)）迅速完成。UNIX操作系統(tǒng)便采取這種算法?，F(xiàn)實中，我們在計算機(jī)中打開各種程序，就是多級反饋隊列調(diào)度算法的應(yīng)用，這次是我們對操作系統(tǒng)操作的模擬，與實際相聯(lián)系，增加了趣味性。這次是我們第一次接觸操作系統(tǒng)，對操作系統(tǒng)原理有了一定的了解，為我們將來學(xué)習(xí)操作系統(tǒng)打下了基礎(chǔ)。參考文獻(xiàn)數(shù)據(jù)結(jié)構(gòu)實用教程附錄main.cpp#include<iostream.h >#include<stdio.h>#include<stdlib.h> #include "

15、queue.h"void main () LinkQueue* x; int n,i; int timing=0;/時刻 Job *jobing;/任務(wù)數(shù)組（動態(tài)分配） x = (LinkQueue*)malloc(sizeof(LinkQueue)*5); for(i=1; i<=4; i+)/初始化所有隊列InitQueue(xi); cout<<"請輸入任務(wù)個數(shù)："<<endl; cin>>n; if(n=0) cout<<"沒有任務(wù)，請重新輸入"<<endl; cin&g

16、t;>n; jobing = new Jobn;/動態(tài)空間分配 cout<<"請輸入各個任務(wù)信息："<<endl; cout<<"任務(wù)號 到達(dá)時間 運(yùn)行時間"<<endl; for(i=0;i<n;i+) cin>>jobingi.jobnum>>jobingi.arrivetime>>jobingi.burst; i=0; while(i!=n|!(EmptyQueue(x1)&&EmptyQueue(x2) && Empty

17、Queue(x3)&& EmptyQueue(x4) while(timing=jobingi.arrivetime) create(x,jobingi);/創(chuàng)建任務(wù) i+; function(x,timing);/任務(wù)運(yùn)行 timing+; for(i=1; i<=4; i+)ClearQueue(xi);/清空隊列 queue.hstruct Job int jobnum; /任務(wù)號 int arrivetime; /到達(dá)時間 int burst; /運(yùn)行時間 int retime; /響應(yīng)時間 int leavetime; /離開時間 int roundtime;

18、/周轉(zhuǎn)時間 int runtime; /已運(yùn)行時間;typedef Job ElemType;struct LNodeElemType data;LNode* next;struct LinkQueueLNode* front;LNode* rear;void InitQueue(LinkQueue& HQ)HQ.front=HQ.rear=NULL;void EnQueue(LinkQueue& HQ,ElemType item) LNode* newptr=new LNode; newptr->data=item; newptr->next=NULL; if (

19、HQ.rear=NULL) HQ.front=HQ.rear=newptr; else HQ.rear=HQ.rear->next=newptr;ElemType OutQueue(LinkQueue& HQ) if (HQ.front=NULL) cerr<<"Queue NULL."<<endl; exit(1); ElemType temp=HQ.front->data; LNode* p=HQ.front; HQ.front=p->next; if (HQ.front=NULL) HQ.rear=NULL; dele

20、te p; return temp; ElemType *PeekQueue(LinkQueue& HQ) if (HQ.front=NULL) cerr<<"隊列為空無首元素。"<<endl;exit(1); return &HQ.front->data; bool EmptyQueue(LinkQueue& HQ) return HQ.front=NULL;void ClearQueue(LinkQueue& HQ) LNode* p=HQ.front; while(p!=NULL) HQ.front=HQ.front->next; delete p; p=HQ.front; HQ.rear=NULL;void function(LinkQueue* x, int timing)/任務(wù)運(yùn)行 int leatime4;/時間片的大小 leatime0=0; leatime1=2; leatime2=6; leatime3=14; Job *t=NULL; int i=1; while(i<5) if(EmptyQueue(xi)=false)/如果隊列不為空 t=PeekQueue(xi);/讀取隊首元素 t