操作系統(tǒng)課程設(shè)計實(shí)驗(yàn)報告用C++實(shí)現(xiàn)驅(qū)動調(diào)度算法

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

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

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

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

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

6、=0;ilength;i+)coutrequestlisti.site ;coutendl;2.算法設(shè)計 2.1 fcfs算法void fcfs(data *db)/先來先服務(wù)算法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 電梯調(diào)度算法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;/計算掃描磁道數(shù)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.功能模塊設(shè)計struct data/基本數(shù)據(jù)集合class display/封裝顯示方法class initdata/設(shè)置基本參數(shù)struct magnetichead/磁頭構(gòu)成class movemethod/封裝調(diào)度方法struct range/磁盤磁道范圍struct requestlist/請求序列void main() /主函數(shù)8、 實(shí)驗(yàn)運(yùn)行結(jié)果：1.選擇 fcfs算法實(shí)現(xiàn)：2.選擇電梯調(diào)度算法實(shí)現(xiàn)3. 選擇掃描算法實(shí)現(xiàn)九、實(shí)驗(yàn)心得：經(jīng)過本次實(shí)驗(yàn)，我更加了解了磁盤調(diào)度算法。先來先服務(wù)算法磁盤臂是隨機(jī)移動的，進(jìn)程等待i/o請求的時間會

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

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

15、范圍int s=0,e=100;cout設(shè)置磁道范圍: n;/coutse;db-range.mstart=s;db-range.mend=e;void setrequestlist(data *db)/設(shè)置請求列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設(shè)置請求 isite;db-requestlisti.site=site;for( i=0;iexecutelist

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

17、先來先服務(wù)算法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;/計算掃描磁道數(shù)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()/構(gòu)造函數(shù)void displayexecutelist(data *db)/輸出執(zhí)行列cout執(zhí)行列: ;for(int i=0;ilength;i+)coutexecutelisti ;coutexecutelisti;coutendl;cout經(jīng)過磁道數(shù): magnetichead.count;coutendl;void displayreque