武漢理工大學操作系統(tǒng)處理機調度實驗報告

1、學生學號 Xxx實驗課成績學 生 實 驗 報 告 書實驗課程名稱操作系統(tǒng)C開課學院計算機科學與技術學院指導教師姓名xxx學生姓名xxx學生專業(yè)班級xxxx2016-2017學年第1學期14實驗課程名稱： 操作系統(tǒng)C 實驗項目名稱處理機調度報告成績實驗者陳碩專業(yè)班級計算機zy1401組別同組者 完成日期2016年11月25日第一部分：實驗分析與設計（可加頁）一、 實驗目的和要求1. 目的 = 掌握處理機調度的相關內容 = 對進程調度算法有深入的理解2.要求 = 模擬實現進程調度功能 = 任選一種計算機高級語言編程實現= 選擇1-2種進程調度算法，例如：先來先服務、短進程優(yōu)先、最高響應比優(yōu)先、時間

2、片輪轉、優(yōu)先級法等= 能夠輸入進程的基本信息，例如進程名、到達時間和預估運行時間等= 根據選擇的調度算法顯示進程的調度順序= 顯示完成調度后每個進程的開始時間、完成時間和周轉時間、帶權周轉時間= 計算平均周轉時間和平均帶權周轉時間二、 分析與設計1.實驗原理分析(1)先來先服務調度算法的基本原理 按照作業(yè)提交/進程變?yōu)榫途w狀態(tài)放的先后次序，調入系統(tǒng)或分派CPU，(即調度程序每次選擇的作業(yè)或進程是等待時間最久的，而不管其運行時間的長短。)(2) 短進程優(yōu)先調度算法的基本原理 對預計執(zhí)行時間短的作業(yè)（進程）優(yōu)先處理。通常后來的短作業(yè)不搶先正在執(zhí)行的作業(yè)。(3) 優(yōu)先級調度算法的基本原理 對優(yōu)先級高

3、的作業(yè)（進程）優(yōu)先處理。可分為搶占式和非搶占式。本實驗采用非搶占式。(4) 最高響應比優(yōu)先調度算法的基本原理 響應比優(yōu)先算法是介于FCFS算法和SJF算法之間的一種折中算法，同時考慮每個作業(yè)的等待時間和估計需要運行的時間，從中選出響應比最高的作業(yè)投入運行。依據上述的實驗目的與要求，可導出實現處理機調度的流程為： 將作業(yè)信息保存到結構體數組中 設計不同的進程調度算法用while進行循環(huán)控制選擇不同的算法2.數據結構的設計l 記錄不同作業(yè)信息的結構體數組。 struct node job100; = 記錄作業(yè)/進程詳細信息的結構體typedef struct node string name;do

4、uble submit;/提交時間double start;/開始時間double run;/運行時間double end;/完成時間double Ti;/周轉時間double Wi;/帶權周轉時間double H;/響應比int priority;/優(yōu)先級*work;3.核心算法設計(1)按提交時間進行排序的算法Input：work p /指向作業(yè)的指針 int N /作業(yè)的個數Process：void sort (work p,int N)for(int i=0;i<N;i+)for(int j=0;j<i;j+)if(pi.submit<pj.submit)node t

5、emp;temp=pi;pi=pj;pj=temp; （2）先來先服務算法Input：work p /指向作業(yè)的指針 int N /作業(yè)的個數Process：void FCFS(work p,int N)sort(p,N);/調用排序算法for(k=0;k<N;k+)if(k=0)pk.start=pk.submit ;pk.end=pk.start+pk.run ;pk.Ti=pk.end-pk.submit;pk.Wi=pk.Ti/pk.run;elseif(pk.submit<pk-1.end)/選擇在作業(yè)完成之前已將提交了的作業(yè)的計算方法 pk.start =pk-1.en

6、d;pk.end=pk.start+pk.run;pk.Ti=pk.end-pk.submit;pk.Wi=pk.Ti/pk.run; else pk.start=pk.submit;/作業(yè)完成時還沒有提交的作業(yè)計算方法 pk.end=pk.start+pk.run; pk.Ti=pk.end-pk.submit; pk.Wi=pk.Ti/pk.run; sumTi=sumTi+pk.Ti; sumWi=sumWi+pk.Wi;T=sumTi/N; /計算平均周轉時間W=sumWi/N; /計算平均帶權周轉時間output(p,N);/調用輸出函數(3) 短進程優(yōu)先算法Input：work p

7、 /指向作業(yè)的指針 int N /作業(yè)的個數Process：void SJF(work p,int N)sort(p,N);/按提交時間排序for(k=0;k<N;k+)if(k=0)pk.start=pk.submit ;pk.end=pk.start+pk.run ;pk.Ti=pk.end-pk.submit;pk.Wi=pk.Ti/pk.run;for(n=k+1;n<N;n+) if(pn.submit>pk.end)break;for(m=k+1;m<n;m+)for(int l=k+1;l<m;l+)if(pm.run<pl.run)node

8、temp;temp=pm;pm=pl;pl=temp;else if(pk.submit<pk-1.end) pk.start =pk-1.end;pk.end=pk.start+pk.run;pk.Ti=pk.end-pk.submit;pk.Wi=pk.Ti/pk.run; else pk.start=pk.submit; pk.end=pk.start+pk.run; pk.Ti=pk.end-pk.submit; pk.Wi=pk.Ti/pk.run; for(n=k+1;n<N;n+)if(pn.submit>pk.end)break;for(m=k+1;m<

9、n;m+)for(int l=k+1;l<m;l+)if(pm.run<pl.run)node temp;temp=pm;pm=pl;pl=temp; sumTi=sumTi+pk.Ti; sumWi=sumWi+pk.Wi;T=sumTi/N;W=sumWi/N;output(p,N);(4) 最高響應比優(yōu)先算法Input：work p /指向作業(yè)的指針 int N /作業(yè)的個數Process：void HRN(work p,int N)sort(p,N);/按提交時間排序for(k=0;k<N;k+)if(k=0)pk.start=pk.submit ;pk.end=pk

10、.start+pk.run ;pk.Ti=pk.end-pk.submit;pk.Wi=pk.Ti/pk.run;for(n=k+1;n<N;n+) if(pn.submit>pk.end) break; int y=k+1;for(int x=k+1;x<n;x+)px.H=1.00+(py-1.end-px.submit)/px.run);/注意在計算響應比時不能用變量X進行循環(huán)計算。for(m=k+1;m<n;m+)for(int l=k+1;l<m;l+)if(pm.H>pl.H)node temp;temp=pm;pm=pl;pl=temp; el

11、se if(pk.submit<pk-1.end) pk.start =pk-1.end;pk.end=pk.start+pk.run;pk.Ti=pk.end-pk.submit;pk.Wi=pk.Ti/pk.run; else pk.start=pk.submit; pk.end=pk.start+pk.run; pk.Ti=pk.end-pk.submit; pk.Wi=pk.Ti/pk.run; for(n=k+1;n<N;n+) if(pn.submit>pk.end) break; int y=k+1;for(int x=k+1;x<n;x+)px.H= 1

12、.00+(py-1.end-px.submit)/px.run);for(m=k+1;m<n;m+)for(int l=k+1;l<m;l+)if(pm.H>pl.H)node temp;temp=pm;pm=pl;pl=temp; sumTi=sumTi+pk.Ti; sumWi=sumWi+pk.Wi;T=sumTi/N;W=sumWi/N;output(p,N);(5) 優(yōu)先級響應算法Input：work p /指向作業(yè)的指針 int N /作業(yè)的個數Process：void PS(work p,int N)/優(yōu)先級調度算法sort(p,N);/按提交時間排序for(k

13、=0;k<N;k+)if(k=0)/第一個提交的作業(yè)單獨計算相關調度信息 pk.start=pk.submit ;pk.end=pk.start+pk.run ;pk.Ti=pk.end-pk.submit;pk.Wi=pk.Ti/pk.run; /*按優(yōu)先級進行排序*/for(n=k+1;n<N;n+） if(pn.submit>pk.end)break; for(m=k+1;m<n;m+)for(int l=k+1;l<m;l+)if(pm.priority<pl.priority)node temp;temp=pm;pm=pl;pl=temp; els

14、e if(pk.submit<pk-1.end) pk.start =pk-1.end;pk.end=pk.start+pk.run;pk.Ti=pk.end-pk.submit;pk.Wi=pk.Ti/pk.run; else pk.start=pk.submit; pk.end=pk.start+pk.run; pk.Ti=pk.end-pk.submit; pk.Wi=pk.Ti/pk.run; /進行作業(yè)相關調度信息的計算 /*按優(yōu)先級進行排序*/for(n=k+1;n<N;n+)if(pn.submit>pk.end)break;for(m=k+1;m<n;m

15、+)for(int l=k+1;l<m;l+)if(pm.priority<pl.priority)node temp;temp=pm;pm=pl;pl=temp; sumTi=sumTi+pk.Ti; sumWi=sumWi+pk.Wi;T=sumTi/N;W=sumWi/N;output(p,N);3. 測試用例設計（1）（2）三、主要儀器設備及耗材1 安裝了Windows XP或Windows 7或其它版本的Windows操作系統(tǒng)的PC機1臺2 PC機系統(tǒng)上安裝了Microsoft Visual Studio 2010開發(fā)環(huán)境第二部分：實驗過程和結果（可加頁）一、 實現說明

16、在VS2010中創(chuàng)建一個算法調度項目，對于不同的調度算法分別進行算法設計，對于算法的設計要特別注意作業(yè)的提交情況，實驗中存儲作業(yè)信息的結構體是相同的，采用結構體數組保存全部的作業(yè)，每次通過對結構體數組進行遍歷計算不同算法需要的信息，最后在主函數中用while循環(huán)和switch語句進行各個調度算法的選擇，最后經過不斷的調試和運行，實現四個調度算法分別是先來先服務、短進程優(yōu)先、優(yōu)先級和最高響應比優(yōu)先。二、 調試說明（調試手段、過程及結果分析） 調試過程出現的問題比較多，第一個問題是對于不同作業(yè)提交的先后順序要加以考慮，對于作業(yè)提交時間進行排序選擇，必須選擇提交時間在上一個作業(yè)結束時間之前的作業(yè)進行

17、短進程，優(yōu)先級，最高響應比排序，經過排序選擇后，出現的問題是在進行作業(yè)調度完，有的作業(yè)出現了負的結束時間，經過調試分析，發(fā)現不能直接用上一個作業(yè)的結束時間直接當做下一個作業(yè)的開始時間，每次進行作業(yè)調度前要進行提交時間與上一個作業(yè)結束時間的比較，如果在作業(yè)提交前，下一個作業(yè)還沒有提交，那么在下一個作業(yè)的開始時間就是它的提交時間。第二個問題是在計算響應比時，對于循環(huán)變量X的使用出錯，使得最高響應比的計算出錯，導致按最高響應比排序出錯。后來通過子在出錯位置前后進行輸出變量的值，不斷調試，發(fā)現了問題，經過修改算法，調試通過，得到最終正確結果。三、 軟件測試（測試效果.界面、綜合分析和結論）1 測試效果

18、.界面測試用例（1）運行結果測試用例（2）運行結果2綜合分析和結論 實驗結果顯示不同調度算法的不同調度策略，其中短進程優(yōu)先調度算法在平均周轉時間和平均帶權周轉時間上要比先來先服務算法少，可見短進程優(yōu)先算法較先來先服務算法在調度時間上更優(yōu)，其中最高相應比優(yōu)先調度算法則是綜合考慮以上兩種算法來進行調度，其調度過程考慮的更全面。優(yōu)先級調度算法只根據優(yōu)先級進行調度，其在時間上可能不會很合理。第三部分：實驗小結、收獲與體會通過這次試驗，使我對處理機調度的相關算法有了更深入的理解，在實驗過程中首先是對各個算法的基本原理全部掌握，然后進行算法設計和編程。實驗中做得比較出色的地方是提前考慮了作業(yè)的提交時間，對于沒有提交的作業(yè)不能進行排隊調度。試驗中沒有考慮