操作系統(tǒng)課程設計實驗報告用C++實現驅動調度算法

1、操 作 系 統(tǒng)實驗報告(4)學院：計算機科學與技術學院班級：計091學號： 2姓名：時間：2011/12/31目 錄1. 實驗名稱32. 實驗目的33. 實驗內容34. 實驗要求35. 實驗原理36. 實驗環(huán)境47. 實驗設計47.1數據結構設計47.2算法設計57.3功能模塊設計68. 實驗運行結果109. 實驗心得10附錄：源代碼（部分）11一、實驗名稱：用c+實現驅動調度算法二、實驗目的：通過自己編程來實現驅動調度算法，進一步理解驅動調度算法的概念及含義，提高對驅動調度算法的認識，同時提高自己的動手實踐能力。加強我們對磁盤調度的理解，有利于我們了解先來先服務算法、最短作業(yè)優(yōu)先算法、響應比

2、最高優(yōu)先者優(yōu)先算法。三、實驗內容：利用c+,實現驅動調度算法1. 先來先服務算法（fcfs）2. 最短作業(yè)優(yōu)先算法（sjf）3. 響應比最高優(yōu)先者優(yōu)先算法（hrrf）四、實驗要求：1.完成驅動調度算法的設計2.分別計算每種算法的經過磁道數五、實驗原理：作為操作系統(tǒng)的輔助存儲器，用來存放文件的磁盤是一類高速大容量旋轉型存儲設備，在繁重的i/o負載下，同時會有若干傳輸請求來到并等待處理，系統(tǒng)必須采用一種調度策略，按照最佳次序執(zhí)行要求訪問的諸多請求，減少為若干i/o請求服務所需消耗的總時間。磁盤驅動調度對磁盤的效率有重要影響。磁盤驅動調度算法的好壞直接影響輔助存儲器的效率，從而影響計算機系統(tǒng)的整體效

3、率。1. 先入先出算法（fifo）：總是嚴格按時間順序對磁盤請求予以處理。算法實現簡單、易于理解并且相對公平，不會發(fā)生進程餓死現象。但該算法可能會移動的柱面數較多并且會經常更換移動方向，效率有待提高2. 電梯調度算法：總是將一個方向上的請求全部處理完后，才改變方向繼續(xù)處理其他請求。3. 掃描算法（scan algorithm）：總是從最外向最內（或最內向最外）進行掃描，然后在從最內向最外（或最外向最內）掃描。該算法與電梯調度算法的區(qū)別是電梯調度在沒有最外或最內的請求時不會移動到最外或最內柱面。六、實驗環(huán)境：win-7系統(tǒng)visual c+ 6.0七、實驗設計：1.數據結構設計定義結構體：str

4、uct magnetichead/磁頭構成int site;/當前位置int count;/已掃描磁道數bool direct;/磁頭移動方向;struct range/磁盤磁道范圍int mstart;/起始值(0)int mend;/結束值();struct requestlist/請求序列int site;/請求磁道號bool state;/處理狀態(tài):true處理,false未處理;struct data/基本數據集合magnetichead magnetichead;/磁頭requestlist *requestlist;/請求序列int *executelist;/執(zhí)行序列range

5、 range;/磁盤磁道數范圍int length;/請求數量;定義類對象：class display/封裝顯示方法private:public:display()/構造函數void displayexecutelist(data *db)/輸出執(zhí)行列cout執(zhí)行列: ;for(int i=0;ilength;i+)coutexecutelisti ;coutexecutelisti;coutendl;cout經過磁道數: magnetichead.count;coutendl;void displayrequestlist(data *db)/輸出請求列cout請求列: ;for(int i

6、=0;ilength;i+)coutrequestlisti.site ;coutendl;2.算法設計 2.1 fcfs算法void fcfs(data *db)/先來先服務算法int t=0;for(int i=0;ilength;i+)db-executelisti+1=db-requestlisti.site;db-magnetichead.site=db-requestlisti.site;t=db-executelisti-db-requestlisti.site;if(tmagnetichead.count+=t;2.2 電梯調度算法void elevator(data *db)

7、/電梯算法int *a;a=new intdb-length;for(int i = 0; ilength;i+)ai=db-requestlisti.site;int t;/冒泡排序if(db-magnetichead.direct=false)/方向從小到大for( i = 1; ilength;i+)for(int j=0;jlength-i;j+)if(ajaj+1)t=aj;aj=aj+1;aj+1=t;int j;/生成執(zhí)行序列for( i = 0; ilength;i+)if(db-magnetichead.site=ai)j=i;for(int k=0;klength;k+,i

8、+)db-executelistk+1=ai;for(int l=db-length-j+1, i = 0; iexecutelistl=aj-i-1;db-magnetichead.count=a0+db-magnetichead.site-2*adb-length-1;else /方向從大到小for( i = 1; ilength;i+)for(int j=0;jlength-i;j+)if(ajaj+1)t=aj;aj=aj+1;aj+1=t;int j;/生成執(zhí)行序列for( i = 0; ilength;i+)if(db-magnetichead.site=ai)j=i;for(in

9、t k=0;klength;k+,i+)db-executelistk+1=ai;for(int l=db-length-j+1, i = 0; iexecutelistl=aj-i-1;db-magnetichead.count=2*adb-length-1-a0-db-magnetichead.site;/計算掃描磁道數2.3 掃描算法void scan(data *db)/掃描算法int *a;a=new intdb-length;for(int i = 0; ilength;i+)ai=db-requestlisti.site;int t;if(db-magnetichead.dire

10、ct=true)for( i = 1; ilength;i+)for(int j=0;jlength-i;j+)if(ajaj+1)t=aj;aj=aj+1;aj+1=t;int j;for( i = 0; ilength;i+)if(db-magnetichead.site=ai)j=i;for(int k=0;klength;k+,i+)db-executelistk+1=ai;for(int l=db-length-j+1, i = 0; iexecutelistl=aj-i-1;db-magnetichead.count=a0+db-magnetichead.site-2*db-ran

11、ge.mstart;elsecoutaan;for( i = 1; ilength;i+)for(int j=0;jlength-i;j+)if(ajaj+1)t=aj;aj=aj+1;aj+1=t;int j;for( i = 0; ilength;i+)if(db-magnetichead.site=ai)j=i;for(int k=0;klength;k+,i+)db-executelistk+1=ai;for(int l=db-length-j+1, i = 0; iexecutelistl=aj-i-1;db-magnetichead.count=2*db-range.mend-a0

12、-db-magnetichead.site; ;3.功能模塊設計struct data/基本數據集合class display/封裝顯示方法class initdata/設置基本參數struct magnetichead/磁頭構成class movemethod/封裝調度方法struct range/磁盤磁道范圍struct requestlist/請求序列void main() /主函數8、 實驗運行結果：1.選擇 fcfs算法實現：2.選擇電梯調度算法實現3. 選擇掃描算法實現九、實驗心得：經過本次實驗，我更加了解了磁盤調度算法。先來先服務算法磁盤臂是隨機移動的，進程等待i/o請求的時間會

13、很長，尋道性較差。電梯調度算法，磁盤柱面號通常由外向里遞增，磁頭越向外，所處的柱面號越小。最短查找時間優(yōu)先算法，總是先執(zhí)行查找時間最短的請求，有較好的尋道性能。當然在實驗過程中，我也遇到了一些困難，但是我通過及時請教同學，查詢相關資料，及時解決了問題，但仍有不足之處，我將會在今后學習中更加努力。附錄：源代碼（部分）#includeusing namespace std;struct magnetichead/磁頭構成int site;/當前位置int count;/已掃描磁道數bool direct;/磁頭移動方向;struct range/磁盤磁道范圍int mstart;/起始值(0)in

14、t mend;/結束值();struct requestlist/請求序列int site;/請求磁道號bool state;/處理狀態(tài):true處理,false未處理;struct data/基本數據集合magnetichead magnetichead;/磁頭requestlist *requestlist;/請求序列int *executelist;/執(zhí)行序列range range;/磁盤磁道數范圍int length;/請求數量;class initdata/設置基本參數private:public:initdata()/構造函數void setrange(data *db)/設置磁道

15、范圍int s=0,e=100;cout設置磁道范圍: n;/coutse;db-range.mstart=s;db-range.mend=e;void setrequestlist(data *db)/設置請求列int len;int site=0;coutlen;/len=10;db-length=len;db-requestlist=new requestlistlen;db-executelist=new intlen+1;for(int i=0;ilen;i+)cout設置請求 isite;db-requestlisti.site=site;for( i=0;iexecutelist

16、i= db-magnetichead.site;db-requestlist9.state=false;void setmagnetichead(data *db)/設置當前磁道位置及方向int s,c,d;/cout預置當前磁道位置:25, 方向: 從大到小n;c=0;/d=0;couts;coutd;db-magnetichead.site=s;db-magnetichead.count=c;db-magnetichead.direct=d;class movemethod/封裝調度方法private:public:movemethod()/構造函數void fcfs(data *db)/

17、先來先服務算法int t=0;for(int i=0;ilength;i+)db-executelisti+1=db-requestlisti.site;db-magnetichead.site=db-requestlisti.site;t=db-executelisti-db-requestlisti.site;if(tmagnetichead.count+=t;void elevator(data *db)/電梯算法int *a;a=new intdb-length;for(int i = 0; ilength;i+)ai=db-requestlisti.site;int t;/冒泡排序i

18、f(db-magnetichead.direct=false)/方向從小到大for( i = 1; ilength;i+)for(int j=0;jlength-i;j+)if(ajaj+1)t=aj;aj=aj+1;aj+1=t;int j;/生成執(zhí)行序列for( i = 0; ilength;i+)if(db-magnetichead.site=ai)j=i;for(int k=0;klength;k+,i+)db-executelistk+1=ai;for(int l=db-length-j+1, i = 0; iexecutelistl=aj-i-1;db-magnetichead.c

19、ount=a0+db-magnetichead.site-2*adb-length-1;else /方向從大到小for( i = 1; ilength;i+)for(int j=0;jlength-i;j+)if(ajaj+1)t=aj;aj=aj+1;aj+1=t;int j;/生成執(zhí)行序列for( i = 0; ilength;i+)if(db-magnetichead.site=ai)j=i;for(int k=0;klength;k+,i+)db-executelistk+1=ai;for(int l=db-length-j+1, i = 0; iexecutelistl=aj-i-1

20、;db-magnetichead.count=2*adb-length-1-a0-db-magnetichead.site;/計算掃描磁道數void scan(data *db)/掃描算法int *a;a=new intdb-length;for(int i = 0; ilength;i+)ai=db-requestlisti.site;int t;if(db-magnetichead.direct=true)for( i = 1; ilength;i+)for(int j=0;jlength-i;j+)if(ajaj+1)t=aj;aj=aj+1;aj+1=t;int j;for( i =

21、0; ilength;i+)if(db-magnetichead.site=ai)j=i;for(int k=0;klength;k+,i+)db-executelistk+1=ai;for(int l=db-length-j+1, i = 0; iexecutelistl=aj-i-1;db-magnetichead.count=a0+db-magnetichead.site-2*db-range.mstart;elsecoutaan;for( i = 1; ilength;i+)for(int j=0;jlength-i;j+)if(ajaj+1)t=aj;aj=aj+1;aj+1=t;i

22、nt j;for( i = 0; ilength;i+)if(db-magnetichead.site=ai)j=i;for(int k=0;klength;k+,i+)db-executelistk+1=ai;for(int l=db-length-j+1, i = 0; iexecutelistl=aj-i-1;db-magnetichead.count=2*db-range.mend-a0-db-magnetichead.site; ;class display/封裝顯示方法private:public:display()/構造函數void displayexecutelist(data *db)/輸出執(zhí)行列cout執(zhí)行列: ;for(int i=0;ilength;i+)coutexecutelisti ;coutexecutelisti;coutendl;cout經過磁道數: magnetichead.count;coutendl;void displayreque