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

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

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

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

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

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

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

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

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

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

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

11、使任務(wù)的已運(yùn)行時(shí)間為0，再使任務(wù)進(jìn)入第一個(gè)隊(duì)列。void function(LinkQueue* x, int timing) 算法：將4個(gè)隊(duì)列設(shè)為循環(huán)，從第一個(gè)隊(duì)列開始到第四個(gè)隊(duì)列逐個(gè)進(jìn)行以下操作。判斷隊(duì)列是否為空，當(dāng)隊(duì)列不為空時(shí)，則繼續(xù)，若該隊(duì)列的已運(yùn)行時(shí)間為1并且時(shí)刻已等于或大于任務(wù)的到達(dá)時(shí)間，即判斷任務(wù)是否為第一次執(zhí)行，若是，求出任務(wù)響應(yīng)時(shí)間=當(dāng)前時(shí)刻-任務(wù)到達(dá)時(shí)間，即發(fā)出請求到任務(wù)開始的時(shí)間差。如果運(yùn)行完，求出任務(wù)離開時(shí)間=當(dāng)前時(shí)刻+1，周轉(zhuǎn)時(shí)間=離開時(shí)間-到達(dá)時(shí)間，輸出任務(wù)信息，再判斷該任務(wù)是否完成該隊(duì)列的時(shí)間片，若是，則降低優(yōu)先級(jí)，任務(wù)進(jìn)入下一級(jí)隊(duì)列。所有隊(duì)列遍歷完，任務(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)輸入錯(cuò)誤，輸入任務(wù)個(gè)數(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選作（同個(gè)時(shí)間點(diǎn)多個(gè)任務(wù)請求）測試六：測試數(shù)據(jù)：1 2 32 2 43 6 94 6 75 總結(jié) 這次實(shí)驗(yàn)用了多級(jí)反饋隊(duì)列調(diào)度算法，這個(gè)算法我們沒有學(xué)過，所以理解有點(diǎn)困難，但是，這個(gè)算法中涉及到了隊(duì)列，它是隊(duì)列的升級(jí)，是多級(jí)隊(duì)列，因此，我在此不僅學(xué)到了新的

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

14、隊(duì)列調(diào)度算法是操作系統(tǒng)中CPU處理機(jī)調(diào)度算法之一，該算法既能使高優(yōu)先級(jí)的進(jìn)程（任務(wù)）得到響應(yīng)又能使短進(jìn)程（任務(wù)）迅速完成。UNIX操作系統(tǒng)便采取這種算法。現(xiàn)實(shí)中，我們在計(jì)算機(jī)中打開各種程序，就是多級(jí)反饋隊(duì)列調(diào)度算法的應(yīng)用，這次是我們對操作系統(tǒng)操作的模擬，與實(shí)際相聯(lián)系，增加了趣味性。這次是我們第一次接觸操作系統(tǒng)，對操作系統(tǒng)原理有了一定的了解，為我們將來學(xué)習(xí)操作系統(tǒng)打下了基礎(chǔ)。參考文獻(xiàn)數(shù)據(jù)結(jié)構(gòu)實(shí)用教程附錄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;/時(shí)刻 Job *jobing;/任務(wù)數(shù)組（動(dòng)態(tài)分配） x = (LinkQueue*)malloc(sizeof(LinkQueue)*5); for(i=1; i<=4; i+)/初始化所有隊(duì)列InitQueue(xi); cout<<"請輸入任務(wù)個(gè)數(shù)："<<endl; cin>>n; if(n=0) cout<<"沒有任務(wù)，請重新輸入"<<endl; cin&g

16、t;>n; jobing = new Jobn;/動(dòng)態(tài)空間分配 cout<<"請輸入各個(gè)任務(wù)信息："<<endl; cout<<"任務(wù)號(hào) 到達(dá)時(shí)間 運(yùn)行時(shí)間"<<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);/清空隊(duì)列 queue.hstruct Job int jobnum; /任務(wù)號(hào) int arrivetime; /到達(dá)時(shí)間 int burst; /運(yùn)行時(shí)間 int retime; /響應(yīng)時(shí)間 int leavetime; /離開時(shí)間 int roundtime;

18、/周轉(zhuǎn)時(shí)間 int runtime; /已運(yùn)行時(shí)間;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<<"隊(duì)列為空無首元素。"<<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;/時(shí)間片的大小 leatime0=0; leatime1=2; leatime2=6; leatime3=14; Job *t=NULL; int i=1; while(i<5) if(EmptyQueue(xi)=false)/如果隊(duì)列不為空 t=PeekQueue(xi);/讀取隊(duì)首元素 t