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

學生實習報告 課程名稱_ 數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)處理應用訓練 題目名稱 多級反饋隊列調(diào)度算法的實現(xiàn) 學生學院 計算機與計算科學 專業(yè)班級 學 號 學生姓名 指導教師 2012 年 2 月 16 日多級反饋隊列調(diào)度算法的實現(xiàn) 【摘要】 多級反饋隊列調(diào)度算法是操作系統(tǒng)中CPU處理機調(diào)度算法之一，該算法既能使高優(yōu)先級的進程（任務）得到響應又能使短進程（任務）迅速完成。UNIX操作系統(tǒng)便采取這種算法，而本次試驗就是試用C語言模擬某多級反饋隊列調(diào)度算法。本次試驗中前三級就緒隊列采用時間片輪轉(zhuǎn)法，時間片大小分別為2、4和8，最后一級就緒隊列采用FIFO調(diào)度，將任務進入多級隊列進行模擬，任務從優(yōu)先級高的隊列到優(yōu)先級地的隊列的順序逐一進入，還用了算法支持搶占式，最后完成模擬，得到各個任務先后完成的順序，還有得到各個任務的響應時間、離開時間、周轉(zhuǎn)時間。 【關(guān)鍵詞】 隊列 優(yōu)先級 任務 時間 1 內(nèi)容與要求【內(nèi)容】 多級反饋隊列調(diào)度算法是操作系統(tǒng)中CPU處理機調(diào)度算法之一，該算法既能使高優(yōu)先級的進程（任務）得到響應又能使短進程（任務）迅速完成。UNIX操作系統(tǒng)便采取這種算法，本次試驗就是試用C語言模擬某多級反饋隊列調(diào)度算法，通過輸入任務號、到達時間、運行時間，求出任務完成的先后順序以及各個任務的響應時間、離開時間、周轉(zhuǎn)時間。【要求】多級反饋隊列調(diào)度算法描述：1、該調(diào)度算法設置四級就緒隊列：前三級就緒隊列采用時間片輪轉(zhuǎn)法，時間片大小分別為2、4和8；最后一級就緒隊列采用FIFO調(diào)度。2、任務在進入待調(diào)度的隊列等待時，首先進入優(yōu)先級最高的隊列等待。3、首先調(diào)度優(yōu)先級高的隊列中的任務。若高優(yōu)先級中隊列中已沒有調(diào)度的任務，則調(diào)度次優(yōu)先級隊列中的任務，依次類推。4、對于同一個隊列中的各個任務，按照隊列指定調(diào)度方法調(diào)度。每次任務調(diào)度執(zhí)行后，若沒有完成任務，就被降到下一個低優(yōu)先級隊列中。5、在低優(yōu)先級的隊列中的任務在運行時，又有新到達的任務，CPU馬上分配給新到達的任務。（注：與原來的題目不同，原題是在低優(yōu)先級的隊列中的任務在運行時，又有新到達的任務時，要在運行完這個時間片后，CPU馬上分配給新到達的任務，而本題不需要在運行完這個時間片，即正在進行的任務立刻停止，CPU馬上分配給新到達的任務）6、為方便實現(xiàn)，時間以1為單位，用整數(shù)數(shù)據(jù)表示；且每個時間點，最多只有一個任務請求服務（即輸入）。2 總體設計2.1 算法總體思路：這是建立在一個時間軸上的，即時刻，一個一個時刻（時間點）進行。 2.1.1 主函數(shù)思路：先初始化所有隊列，再輸入任務個數(shù)，如果輸入個數(shù)為0，則重新輸入，然后輸入各個任務的信息，即任務號、到達時間、運行時間，再當時刻到任務的到達時間時，就創(chuàng)建任務，然后運行任務，時刻自動加1 ，創(chuàng)建任務與運行任務進行循環(huán)，直到所有任務進行完或所有隊列為空才跳出循環(huán)，最后清空所有隊列。2.1.2 功能函數(shù)思路：void create(LinkQueue* x,Job job)：使任務的已運行時間為0，再使任務進入第一個隊列。void function(LinkQueue* x, int timing)：四個隊列從第一個到第四個，即從最高優(yōu)先級開始，任務在4個隊列中逐個進行，根據(jù)任務是否為第一次執(zhí)行，求出響應時間，任務完成時，求出離開時間和周轉(zhuǎn)時間輸出信息，在前3個隊列，如果任務剛完成一個就緒隊列的時間片，就降低優(yōu)先級，使任務進入下一個隊列。2.2 功能模塊介紹：void main ()函數(shù)功能：主函數(shù)void InitQueue(LinkQueue& HQ)：隊列的初始化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,Job job) 函數(shù)功能：創(chuàng)建任務。void function(LinkQueue* x, int timing) 函數(shù)功能：任務運行。2.3 輸入輸出輸入：任務號 到達時間 運行時間輸出：任務號 響應時間 離開時間 周轉(zhuǎn)時間、2.4 文件介紹main.cpp:主函數(shù)的存放，功能函數(shù)的調(diào)用。queue.h:隊列的各個基本功能函數(shù)，任務的創(chuàng)建函數(shù)與運行函數(shù)。3 詳細設計3.1存儲結(jié)構(gòu)描述struct Job int jobnum; /任務號 int arrivetime; /到達時間 int burst; /運行時間 int retime; /響應時間 int leavetime; /離開時間 int roundtime; /周轉(zhuǎn)時間 int runtime; /已運行時間;/任務的存儲結(jié)構(gòu)typedef Job ElemType;/任務的類型定義struct LNodeElemType data;/值域LNode* next;/鏈接指針域;struct LinkQueueLNode* front;/隊首指針LNode* rear;/隊尾指針;3.2 參數(shù)說明timing是時刻，時間軸；Job *jobing：任務數(shù)組（動態(tài)分配）int leatime4;/時間片大小到達時間：任務請求的時刻運行時間：任務運行完需要的時間響應時間：任務從到達時間到任務第一次執(zhí)行的時間差周轉(zhuǎn)時間：任務從開始請求（到達時間）到任務完成離開的時間已運行時間：任務已運行的時間離開時間：任務運行完后離開隊列的時刻3.3 具體算法void InitQueue(LinkQueue& HQ)算法：隊首隊尾設置為空。void EnQueue(LinkQueue& HQ,ElemType item)算法：得到一個新結(jié)點，把item的值賦給新結(jié)點的值域，再把新結(jié)點的指針域置空，若鏈隊為空，則新結(jié)點既是隊首又是隊尾，若鏈隊非空，則新結(jié)點被鏈接到隊尾并修改隊尾指針。ElemType OutQueue(LinkQueue& HQ)算法：若鏈隊為空則中止運行，暫存隊首元素以便返回，暫存隊首指針以便收回隊首節(jié)點，使隊首指針指向下一個結(jié)點，若刪除后鏈隊為空，則使隊尾指針為空，然后回收原隊首節(jié)點，返回被刪除的隊首元素。ElemType *PeekQueue(LinkQueue& HQ)算法：若鏈隊為空則中止運行，返回隊首元素指針（Job*）。bool EmptyQueue(LinkQueue& HQ)算法：判斷隊首或隊尾任一個指針是否為空即可。void ClearQueue(LinkQueue& HQ)算法：隊首指針賦給p，依次刪除隊列中的每個結(jié)點，然后循環(huán)結(jié)束后隊首指針已經(jīng)變空，置隊尾指針為空。void create(LinkQueue* x,Job job)算法：使任務的已運行時間為0，再使任務進入第一個隊列。void function(LinkQueue* x, int timing) 算法：將4個隊列設為循環(huán)，從第一個隊列開始到第四個隊列逐個進行以下操作。判斷隊列是否為空，當隊列不為空時，則繼續(xù)，若該隊列的已運行時間為1并且時刻已等于或大于任務的到達時間，即判斷任務是否為第一次執(zhí)行，若是，求出任務響應時間=當前時刻-任務到達時間，即發(fā)出請求到任務開始的時間差。如果運行完，求出任務離開時間=當前時刻+1，周轉(zhuǎn)時間=離開時間-到達時間，輸出任務信息，再判斷該任務是否完成該隊列的時間片，若是，則降低優(yōu)先級，任務進入下一級隊列。所有隊列遍歷完，任務均完成，循環(huán)結(jié)束。4 程序測試測試一：測試數(shù)據(jù)：1 0 82 6 43 9 12測試二：測試數(shù)據(jù)：1 0 72 5 43 7 134 12 9測試三：當輸入錯誤，輸入任務個數(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選作（同個時間點多個任務請求）測試六：測試數(shù)據(jù)：1 2 32 2 43 6 94 6 75 總結(jié) 這次實驗用了多級反饋隊列調(diào)度算法，這個算法我們沒有學過，所以理解有點困難，但是，這個算法中涉及到了隊列，它是隊列的升級，是多級隊列，因此，我在此不僅學到了新的知識，還是對數(shù)據(jù)結(jié)構(gòu)中隊列部分的熟悉與加深，更好的掌握了隊列知識。這次實驗我的題目與原題有點差別，在低優(yōu)先級的隊列中的任務在運行時，又有新到達的任務，那么在運行完這個時間片后，CPU馬上分配給新到達的任務，即算法支持搶占式，但我的程序確是在新到達的任務，那么這個任務立即中止，CPU馬上分配給新到達的任務，我覺得這樣更好。當然，這次編程中遇到過許多困難，比如存儲結(jié)構(gòu)順序的錯誤，又比如ElemType *PeekQueue(LinkQueue& HQ)，這是與隊列的原基礎(chǔ)功能函數(shù)有所區(qū)別，它需要的是返回元素指針（Job*），我原來返回的是元素，后來經(jīng)過調(diào)試，錯誤提示，才改正確等等。多級反饋隊列調(diào)度算法是操作系統(tǒng)中CPU處理機調(diào)度算法之一，該算法既能使高優(yōu)先級的進程（任務）得到響應又能使短進程（任務）迅速完成。UNIX操作系統(tǒng)便采取這種算法?，F(xiàn)實中，我們在計算機中打開各種程序，就是多級反饋隊列調(diào)度算法的應用，這次是我們對操作系統(tǒng)操作的模擬，與實際相聯(lián)系，增加了趣味性。這次是我們第一次接觸操作系統(tǒng)，對操作系統(tǒng)原理有了一定的了解，為我們將來學習操作系統(tǒng)打下了基礎(chǔ)。參考文獻/ask/question.php?id=1985/view/290c15293169a4517723a350.html/u/20120213/14/642df43b-1fe4-4091-91d5-6d26cbaa591c.html數(shù)據(jù)結(jié)構(gòu)實用教程附錄main.cpp#include#include#include #include queue.hvoid main () LinkQueue* x; int n,i; int timing=0;/時刻 Job *jobing;/任務數(shù)組（動態(tài)分配） x = (LinkQueue*)malloc(sizeof(LinkQueue)*5); for(i=1; i=4; i+)/初始化所有隊列InitQueue(xi); cout請輸入任務個數(shù)：n; if(n=0) cout沒有任務，請重新輸入n; jobing = new Jobn;/動態(tài)空間分配 cout請輸入各個任務信息：endl; cout任務號 到達時間 運行時間endl; for(i=0;ijobingi.jobnumjobingi.arrivetimejobingi.burst; i=0; while(i!=n|!(EmptyQueue(x1)&EmptyQueue(x2) & EmptyQueue(x3)& EmptyQueue(x4) while(timing=jobingi.arrivetime) create(x,jobingi);/創(chuàng)建任務 i+; function(x,timing);/任務運行 timing+; for(i=1; idata=item; newptr-next=NULL; if (HQ.rear=NULL) HQ.front=HQ.rear=newptr; else HQ.rear=HQ.rear-next=newptr;ElemType OutQueue(LinkQueue& HQ) if (HQ.front=NULL) cerrQueue NULL.data; LNode* p=HQ.front; HQ.front=p-next; if (HQ.front=NULL) HQ.rear=NULL; delete p; return temp; ElemType *PeekQueue(LinkQueue& HQ) if (HQ.front=NULL) cerr隊列為空無首元素。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)/任務運行 int leatime4;/時間片的大小 leatime0=0; leatime1=2; leatime2=6; leatime3=14; Job *t=NULL; int i=1; while(iruntime+;/已運行時間+1 if(t-runtime=1&timing=t-arrivetime)t-retime=timing - t-arrivetime;