1、學生實習報告課程名稱一數據結構與數據處理應用訓練題目名稱_多級反饋隊列調度算法的實現學生學院 計算機與計算科學專業班級學 號學生姓名扌旨導教師2012年2月16日多級反饋隊列調度算法的實現【摘要】多級反饋隊列調度算法是操作系統中CPU處理機調度算法之一，該算法既能 使高優先級的進程（任務）得到響應又能使短進程（任務）迅速完成。UNIX操作 系統便采取這種算法，而本次試驗就是試用C語言模擬某多級反饋隊列調度算法。 本次試驗中前三級就緒隊列采用時間片輪轉法，時間片大小分別為2、4和8 ,最 后一級就緒隊列采用FIFO調度，將任務進入多級隊列進行模擬，任務從優先級高 的隊列到優先級地的隊列的順序逐一

2、進入，還用了算法支持搶占式，最后完成模 擬，得到各個任務先后完成的順序，還有得到各個任務的響應時間、離開時間、 周轉時間。【關鍵詞】隊列 優先級 任務 時間1內容與要求【內容】多級反饋隊列調度算法是操作系統屮CPU處理機調度算法之一，該算法既能 使高優先級的進程（任務）得到響應又能使短進程（任務）迅速完成。UNIX操作 系統便采取這種算法，木次試驗就是試用C語言模擬某多級反饋隊列調度算法，通過輸入任務號、到達時間、運行時間，求出任務完成的先后順序以及各個任務 的響應時間、離開時間、周轉時間。【要求】多級反饋隊列調度算法描述：1、該調度算法設置四級就緒隊列：前三級就緒隊列采用時間片輪轉法，時間

3、片大小分別為2、4和8；最后一級就緒隊列采用FIFO調度。2、任務在進入待調度的隊列等待時，首先進入優先級最高的隊列等待。3、首先調度優先級高的隊列屮的任務。若高優先級中隊列中已沒有調度的任 務，則調度次優先級隊列中的任務，依次類推。4、對于同一個隊列中的各個任務，按照隊列指定調度方法調度。每次任務調 度執行后，若沒有完成任務，就被降到下一個低優先級隊列屮。5、在低優先級的隊列中的任務在運行時，又有新到達的任務，CPU馬上分配 給新到達的任務。（注：與原來的題目不同，原題是在低優先級的隊列中的任務在 運行時，又有新到達的任務時，要在運行完這個時間片后，CPU馬上分配給新到 達的任務，而本題不需

4、要在運行完這個時間片，即正在進行的任務立刻停止，CPU 馬上分配給新到達的任務）6、為方便實現，時間以1為單位，用整數數據表示；且每個時間點，最多只 有一個任務請求服務（即輸入）。2總體設計算法總體思路：這是建立在一個時間軸上的，即時刻，一個一個時刻（時間點）進行。2. 1. 1主函數思路:先初始化所有隊列，再輸入任務個數，如果輸入個數為0,則重新輸入，然后輸入各個任務的信息，即任務號、到達時間、運行時間，再當時刻到任務的到達 時間時，就創建任務，然后運行任務，時刻自動加1 ,創建任務與運行任務進行 循環，直到所有任務進行完或所有隊列為空才跳出循環，最后清空所有隊列。2. 1. 2功能函數思路

5、：void create (LinkQueue* x, Job job):使任務的已運行時間為0,再使任務進入 第一個隊列。void function(LinkQueue* x, int timing):四個隊列從第一個到第四個，即從 最高優先級開始，任務在4個隊列中逐個進行，根據任務是否為第一次執行，求 出響應時間，任務完成時，求出離開時間和周轉時間輸出信息，在前3個隊列， 如果任務剛完成一個就緒隊列的時間片，就降低優先級，使任務進入下一個隊列。功能模塊介紹：void main ()函數功能：主函數void InitQueue (LinkQueueft HQ):隊列的初始化void EnQu

6、eue(LinkQueue& HQ, ElemType item)函數功能：向隊列中插入一個元素ElemType OutQueue(LinkQueue& HQ)函數功能：從隊列中刪除一個元素ElemType *PeekQueue(LinkQueue& HQ)函數功能：讀取隊首元素bool EmptyQueue(LinkQueue& HQ)函數功能：檢查隊列是否為空void ClearQueue(LinkQueue& HQ)函數功能：清除鏈隊中的所有元素，使之變為空隊void create (LinkQueue* x,Job job)函數功能：創建任務。v

7、oid function(LinkQueue* x, int timing)函數功能：任務運行。輸入輸出輸入：任務號到達時間運行時間輸出：任務號響應時間離開時間周轉時間、文件介紹:主函數的存放，功能函數的調用。:隊列的各個基木功能函數，任務的創建函數與運行函數。3詳細設計存儲結構描述struct Job int jobnum;obnum>>jobingi arrivetime>>jobingi burst;i=0；wh訂e(i!=n |!(EmptyQueue(xl)&&EmptyQueue(x2j)&& EmptyQueue(x3)&a

8、mp;& EmptyQueue(x4) while(timing=jobingi arrivetime)create(x, jobingi) ;<<endl;exit (1);ElemType temp=>data;LNode* p二；=p->next;辻=NULL)=NULL;delete p;return temp;ElemType *PeekQueue(LinkQueue& HQ)zz<<endl ;exit (1) ;辻=NULL) cerr«/z隊列為空無首元素。return &data;bool EmptyQue

9、ue(LinkQueue& HQ)return =NULL;void ClearQueue (LinkQueue& HQ)LNode* p二；while(p!=NULL) =>next;delete p;P=；二NULL;void function(LinkQueue* x, int timing)/任務運行int leatime4;/時間片的大小leatime0二0;leatimel=2;lea ti 11162二6;leatime3=14;Job *t=NULL;int i=l;while (i<5)辻(EmptyQueue (xi)false)/如果隊列不為空

10、t=PeekQueue(xi) ;/讀取隊首元素t->runtime+；/ 已運行時間+1if (t>ru nti me=l&&timing> 二t-冶rrivetime) t->retime=timing 一 t->arrivetime;if(t->runtime = t->burst)t->leavetime=timing+l;t->roundtime =t>leavetime - t>arrivetime;cout<<z，任務號:，z<<t> jobnum<<，z "«"響應時間:，«t->retime<</ .fcout«/?離開時間："<“ 周轉時間：roundtime;cout«end