操作系統(tǒng)專業(yè)課程設(shè)計(jì)磁盤調(diào)度算法樣本

操作系統(tǒng)專業(yè)課程設(shè)計(jì)磁盤調(diào)度算法前 言摘要：本課程設(shè)計(jì)的目的是通過設(shè)計(jì)一個(gè)磁盤調(diào)度模擬系統(tǒng)， 從而使磁盤調(diào)度算法更加形象化，使磁盤調(diào)度的特點(diǎn)更簡(jiǎn)單明了，這里主要實(shí)現(xiàn)磁盤調(diào)度的四種算法，分別是：1、先來先服務(wù)算法（FCFS）2、最短尋道時(shí)間優(yōu)先算法（SSTF）3、掃描算法SCAN）4、循環(huán)掃描算法（CSCAN）。啟動(dòng)磁盤執(zhí)行輸入輸出操作時(shí)，要把移動(dòng)臂移動(dòng)到指定的柱面，再等待指定扇區(qū)的旋轉(zhuǎn)到磁頭位置下，然后讓指定的磁頭進(jìn)行讀寫，完成信息傳送；因此，執(zhí)行一次輸入輸出所花的時(shí)間有：尋找時(shí)間——磁頭在移動(dòng)臂帶動(dòng)下移動(dòng)到指定柱面所花的時(shí)間。延遲時(shí)間——指定扇區(qū)旋轉(zhuǎn)到磁頭下所需的時(shí)間。傳送時(shí)間——由磁頭進(jìn)程讀寫完成信息傳送的時(shí)間，尋道時(shí)間——指計(jì)算機(jī)在發(fā)出一個(gè)尋址命令，到相應(yīng)目標(biāo)數(shù)據(jù)被找到所需時(shí)間；其中傳送信息所花的時(shí)間，是在硬件設(shè)計(jì)時(shí)固定的，而尋找時(shí)間和延遲時(shí)間是與信息在磁盤上的位置有關(guān)；然后設(shè)計(jì)出磁盤調(diào)度的設(shè)計(jì)方式，包括算法思路、步驟，以及要用到的主要數(shù)據(jù)結(jié)構(gòu)、函數(shù)模塊及其之間的調(diào)用關(guān)系等，并給出詳細(xì)的算法設(shè)計(jì)，對(duì)編碼進(jìn)行了測(cè)試與分析。最后進(jìn)行個(gè)人總結(jié)與設(shè)計(jì)體會(huì)。關(guān)鍵詞：最短尋道時(shí)間優(yōu)先算法、掃描算法、總尋道長(zhǎng)度 .目錄前言....................................................22.課程設(shè)計(jì)任務(wù)及要求......................................4設(shè)計(jì)任務(wù).............................................4設(shè)計(jì)要求.............................................43.算法及數(shù)據(jù)結(jié)構(gòu)..........................................4（流程）..............................................4實(shí)現(xiàn)過程中用到的數(shù)據(jù)結(jié)構(gòu).............................5實(shí)現(xiàn)過程中用到的系統(tǒng)調(diào)用............................104.程序設(shè)計(jì)與實(shí)現(xiàn).........................................10最短尋道時(shí)間優(yōu)先算法（SSTF）模塊....................10...............................................10程序說明......................................12程序關(guān)鍵代碼..................................12（SCAN）模塊.........................................13程序流程圖..........................................13程序說明......................................15程序關(guān)鍵代碼..................................16實(shí)驗(yàn)結(jié)果............................................165.結(jié)論...................................................296.參考文獻(xiàn)...............................................297.收獲、體會(huì)和建議.......................................29課程設(shè)計(jì)任務(wù)及要求設(shè)計(jì)任務(wù)，加強(qiáng)對(duì)所學(xué)各種調(diào)度算法及相應(yīng)算法的特點(diǎn)了解。，深刻體會(huì)各個(gè)算法的優(yōu)缺點(diǎn)，以及算法間的相似點(diǎn)。設(shè)計(jì)要求定義與算法相關(guān)的數(shù)據(jù)結(jié)構(gòu)，如PCB、隊(duì)列等；2）實(shí)現(xiàn)2種不同的調(diào)度算法（可使用偽代碼或流程圖進(jìn)行分析） ；3）算法執(zhí)行結(jié)束時(shí)，應(yīng)給出總的尋道長(zhǎng)度；4）磁道訪問序列隨機(jī)生成，且要滿足一定的數(shù)量要求（不少于 100個(gè)）；5）系統(tǒng)實(shí)現(xiàn)必須提供一定的交互性，所需測(cè)試數(shù)據(jù)應(yīng)當(dāng)以文件形式提供或者由用戶在測(cè)試過程中給出，不可將測(cè)試數(shù)據(jù)“寫死”在系統(tǒng)實(shí)現(xiàn)代碼中；6）必須給出足夠的注釋，注釋量不得少于代碼量的一半；7）對(duì)于系統(tǒng)中所使用到的系統(tǒng)調(diào)用（API函數(shù)），必須給出函數(shù)的定義原型、使用方法，參數(shù)較為復(fù)雜的，還應(yīng)該給出參數(shù)的具體描述；算法及數(shù)據(jù)結(jié)構(gòu)（流程）總流程圖開始輸入磁道的個(gè)數(shù)Y NY N實(shí)現(xiàn)過程中用到的數(shù)據(jù)結(jié)構(gòu)SSTF）（從100號(hào)磁道開始）被訪問的下一個(gè)磁道號(hào) 移動(dòng)距離（磁道數(shù)）5545583391918219072160701501038112184146平均尋道長(zhǎng)度：55.3圖a SSTF調(diào)度算法示例圖ciidao[]={55,58,39,18,90,160,150,38,184} （可隨機(jī)生成多個(gè)）用冒泡法對(duì)磁道數(shù)組進(jìn)行排序用戶輸入當(dāng)前磁道號(hào) now，比較當(dāng)前返回內(nèi)側(cè)（外側(cè)）掃描將當(dāng)前磁道號(hào)與剩余沒有圖bSSTF算法流程示例圖原磁道號(hào)隨機(jī)組成的數(shù)組： cidao[]={55,58,39,18,90,160,150,38,184}排序后的數(shù)組={18,38,39,5,58,90,150,160,184} ；輸入當(dāng)前磁道號(hào)：now=100；

；3839 3955 55 5558 58 58 5890 90 90 90 90now值:100 90 58 55 39184160 160150 150 15018 18 18 1838 38 38 3839 39 39 3955 55 55 5558 58 58 5890 90 90 90now值：18 150 160 184圖c SSTF 算法隊(duì)列示意圖(按磁道訪問順序)SCAN）算法（從100號(hào)磁道開始，向磁道號(hào)增加方向訪問）被訪問的下一個(gè)磁道號(hào) 移動(dòng)距離（磁道數(shù)）1505016010184249094583255339163811820平均尋道長(zhǎng)度：

27.8圖dSCAN算法示例圖原磁道號(hào)隨機(jī)組成的數(shù)組：

cidao[]={55,58,39,18,90,160,150,38,184}

；排序后的數(shù)組

={18,38,39,5,58,90,150,160,184}

；輸入當(dāng)前磁道號(hào)：

now=100；選擇磁道移動(dòng)方向；以磁道號(hào)增加的方向移動(dòng)為例：5558 5890 90 90184 184 184 184160 160 160 160 160150150150150150150now值：1001501601849058183838393939555555585858909090184184184160160160150150150now值:5539 38圖e SCAN算法隊(duì)列示意圖（按磁道訪問順序）實(shí)現(xiàn)過程中用到的系統(tǒng)調(diào)用系統(tǒng)模塊調(diào)用關(guān)系圖磁盤調(diào)度算法最掃退短描出尋算道法程序設(shè)計(jì)與實(shí)現(xiàn)最短尋道時(shí)間優(yōu)先算法（ SSTF）模塊開始輸入磁道號(hào)串調(diào)用SSTF()函數(shù)用冒泡法將磁道號(hào)從大到小排序輸入當(dāng)前磁道號(hào) now判斷now的大小now<=cidao[0] cidao[0]<now<cidao[m-1]now>=cidao[m-1]直接從小到大給找到離now尋道直接從大到小給予磁道服務(wù)時(shí)間最短的磁道予磁道服務(wù)優(yōu)先服務(wù)離now最近的 磁道移動(dòng)方向，再掉頭服務(wù)計(jì)算總尋道長(zhǎng)度，并輸出移動(dòng)的平均尋道長(zhǎng)度結(jié)束程序說明算法分析優(yōu)點(diǎn)：相較于先來先服務(wù)算法（FCFS）有更好的尋道性能，使每次的尋道時(shí)間最短。缺點(diǎn)：易造成某個(gè)進(jìn)程發(fā)生“饑餓”現(xiàn)象。最短尋找時(shí)間優(yōu)先調(diào)度算法總是從等待訪問者中挑選尋找時(shí)間最短的那個(gè)請(qǐng)求先執(zhí)行的，而不管訪問者到來的先后次序。例如，如果現(xiàn)在讀寫磁頭正在100號(hào)柱面上執(zhí)行輸出操作，而等待訪問者依次要訪問的柱面為55,58,39,18,90,160,150,38,184 ，那么，當(dāng)100號(hào)柱面的操作結(jié)束后，應(yīng)該先處理90號(hào)柱面的請(qǐng)求，然后到達(dá)58號(hào)柱面執(zhí)行操作，隨后處理55號(hào)柱面請(qǐng)求，后繼操作的次序應(yīng)該是39,38,18,150,160,，讀寫磁頭總共移動(dòng)多個(gè)柱面的距離，與先來先服務(wù)、算法比較，大幅度地減少了尋找時(shí)間，具有更好的尋道性能，因而縮短了為各訪問者請(qǐng)求服務(wù)的平均時(shí)間，也就提高了系統(tǒng)效率。但最短查找時(shí)間優(yōu)先（SSTF）調(diào)度，F(xiàn)CFS會(huì)引起讀寫頭在盤面上的大范圍移動(dòng)，SSTF查找距離磁頭最短（也就是查找時(shí)間最短）的請(qǐng)求作為下一次服務(wù)的對(duì)象。SSTF查找模式有高度局部化的傾向，會(huì)推遲一些請(qǐng)求的服務(wù)，甚至引起無限拖延（又稱饑餓）。算法流程：輸入磁頭初始磁道號(hào)，序列長(zhǎng)度，磁道號(hào)序列。選擇磁盤調(diào)度算法（最短尋道時(shí)間優(yōu)先調(diào)度 (SSTF)）或（掃描調(diào)度算法(SCAN)）中的任意一個(gè)，若選擇SSTF，則輸出各進(jìn)程被調(diào)度的順序，并計(jì)算總的尋道長(zhǎng)度和平均尋道長(zhǎng)度，選擇關(guān)閉則結(jié)束磁盤調(diào)度。程序關(guān)鍵代碼for(i=0;i<m;i++)

/*使用冒泡法按從小到大順序排列

*/for(j=i+1;j<m;j++){if(array[i]>

array[j]){temp=

array[i];array[i]=arrayarray[j]=temp;

[j];}}if(array[m-1]<=now)

/*

若當(dāng)前磁道號(hào)大于請(qǐng)求序列中最大者，

則直接由外向內(nèi)依次給予各請(qǐng)求服務(wù)*/{for(i=m-1;i>=0;i--)cout<< array[i]<< "";sum=now- array[0];}elseif(array[0]>=now)

/*若當(dāng)前磁道號(hào)小于請(qǐng)求序列中最小者，則直接由內(nèi)向外依次給予各請(qǐng)求服務(wù)*/while((l>=0)&&(r<m)) /*當(dāng)前磁道在請(qǐng)求序列范圍內(nèi) */{if((now-array[l])<=( array[r]-now)) /*選擇與當(dāng)前磁道最近的請(qǐng)求給予服務(wù) */{cout<< array[l]<< "";sum+=now- array[l];now= array[l];l=l-1;}SCAN）模塊程序流程圖開始輸入磁道號(hào)串d=1d=0程序說明算法分析優(yōu)點(diǎn)：排除了磁頭在盤面局部位置上的往復(fù)移動(dòng)，SCAN算法在很大程度上消除了SSTF算法的不公平性，但仍有利于對(duì)中間磁道的請(qǐng)求。缺點(diǎn)：新進(jìn)來的訪問此磁道的進(jìn)程的請(qǐng)求會(huì)被大大地推遲。增加延遲。SCAN算法又稱電梯調(diào)度算法。SCAN算法是磁頭前進(jìn)方向上的最短查找時(shí)間優(yōu)先算法。注：“電梯調(diào)度”算法是從移動(dòng)臂當(dāng)前位置開始沿著臂的移動(dòng)方向去選擇離當(dāng)前移動(dòng)臂最近的那個(gè)柱訪問者，如果沿臂的移動(dòng)方向無請(qǐng)求訪問時(shí)，就改變臂的移動(dòng)方向再選擇。這好比乘電梯，如果電梯已向上運(yùn)動(dòng)到4層時(shí)，依次有3位乘客張一、張二、張三在等候乘電梯。他們的要求是：張一在2層等待去10層；張二在5層等待去底層；張三在8層等待去15層。由于電梯目前運(yùn)動(dòng)方向是向上，所以電梯的形成是先把乘客張三從8層帶到15層，然后電梯換成下行方向，把乘客張二從5層帶到底層，電梯最后再調(diào)換方向，把乘客張一從2層送到10層。我們?nèi)杂们笆龅耐焕觼碛懻摬捎谩半娞菡{(diào)度”算法的情況。由于磁盤移動(dòng)臂的初始方向有兩個(gè)，而該算法是與移動(dòng)臂方向有關(guān)，所以分成兩種情況來討論。這里是：移動(dòng)臂先由里向外移動(dòng)，再由外向里移動(dòng)。開始時(shí)，，在100號(hào)柱面執(zhí)行操作的讀寫磁頭的移動(dòng)臂方向是由里向外，趨向32號(hào)柱面的位置，因此，當(dāng)訪問100號(hào)柱面的操作結(jié)束后，沿臂移動(dòng)方向最近的柱面是150號(hào)柱面。所以應(yīng)先為150號(hào)柱面的訪問者服務(wù)，然后是為160號(hào)柱面的訪問者服務(wù)。之后，由于在向外移方向已無訪問等待者，故改變移動(dòng)臂的方向，由外向里依次為各訪問者服務(wù)。在這種情況下為等待訪問者服務(wù)的次序是184,90,58,55,39,38,18。算法流程：輸入磁頭初始磁道號(hào)，序列長(zhǎng)度，磁道號(hào)序列。選擇磁盤調(diào)度算法（最短尋道時(shí)間優(yōu)先調(diào)度 (SSTF)）或（掃描調(diào)度算法(SCAN)）中的任意一個(gè)，若選擇SCAN，則需要選擇磁頭移動(dòng)方向是“向磁道號(hào)增加方向訪問”或“向磁道號(hào)減少方向訪問”，之后，輸出各進(jìn)程被調(diào)度的順序，并計(jì)算總的尋道長(zhǎng)度和平均尋道長(zhǎng)度，選擇關(guān)閉則結(jié)束磁盤調(diào)度。程序關(guān)鍵代碼if

(d==0)

/*選擇移動(dòng)臂方向向內(nèi)，則先向內(nèi)掃描

*/{for(j=l;j>=0;j--){cout<<

array[j]<<

"";

/*

輸出向內(nèi)掃描的序列

*/}for

(j=r;j<m;j++)

/*磁頭移動(dòng)到最小號(hào)，則改變方向向外掃描未掃描的磁道

*/{cout<<

array[j]<<

"";

/*

輸出向外掃描的序列

*/}sum=now-2* array[0]+array[m-1];}else /*選擇移動(dòng)臂方向向外，則先向外掃描 */{for(j=r;j<m;j++){cout<< array[j]<< ""; /*輸出向外掃描的序列 */}for(j=l;j>=0;j--)

/*磁頭移動(dòng)到最大號(hào)，則改變方向向內(nèi)掃描未掃描的磁道

*/{cout<<

array[j]<<

"";}sum=-now-

array[0]+2*

array[m-1];}ave=(float

)(sum)/(

float

)(m);實(shí)驗(yàn)結(jié)果運(yùn)行界面截圖及相應(yīng)代碼主界面voiddisplay(){cout<<"\n\n\n\nOperatingSystemsCurriculumDesign\n";cout<<"\n ╔———————————————————————————————╗";cout<<"\n

││";cout<<"\n

│

名稱

:磁盤調(diào)度

│";cout<<"\n

││";cout<<"\n

│

工具

:VisualStudio2010

│";cout<<"\n

││";cout<<"\n

│

班級(jí)│";

:1205cout<<"\n

││";cout<<"\n

│

作者

:施靜

│";cout<<"\n

││";cout<<"\n

│

學(xué)號(hào)：│";cout<<"\n │";cout<<"\n ╚———————————————————————————————╝\n";system("pause");system("cls");2. 前言 提示用戶此程序?qū)崿F(xiàn)的算法cout<<"【載入完成】"<<endl<<endl;cout<<"前言"<<endl<<endl;cout<<" 歡迎使用『磁盤調(diào)度算法系統(tǒng)』，本程序?qū)崿F(xiàn)了常用的磁盤調(diào)度算法如下所示：\n\n";cout<<" ①最短尋道時(shí)間優(yōu)先（ SSTF）：最短尋道時(shí)間優(yōu)先算法要求訪問的磁盤與當(dāng)前磁頭所在的\n";cout<<"磁盤距離最近，以使每次的尋道時(shí)間最短。\n\n";cout<<" ②掃描算法(SCAN)電梯調(diào)度：掃描算法不僅考慮到欲訪問的磁道與當(dāng)前磁道的距離\n";cout<<" 更優(yōu)先考慮的是磁頭的當(dāng)前移動(dòng)方向。\n\n";system("pause");system("cls");// 清屏用戶選擇所使用的算法（先隨機(jī)生成101個(gè)磁道號(hào)）voidshowMenu(intcidao[],intn){intchoice;while(true){cout<<" 請(qǐng)您選擇喜歡的算法來實(shí)現(xiàn)調(diào)度(輸入1-3):";cout<<"\n ╔—————————————╗";cout<<"\n │";cout<<"\n

│

(SSTF)|";cout<<"\n

│";cout<<"\n │ (SCAN)";cout<<"\n │";cout<<"\n │ (EXIT)";cout<<"\n │";cout<<"\n ╚—————————————╝\n";cout<<endl;while(true){cout<<" 現(xiàn)在您選擇的算法號(hào)是（ 1-3）：";cin>>choice;switch(choice){/*case1:FCFS(a,n);break;*/case1:SSTF(cidao,n);break;case2:SCAN(cidao,n);break;case3:cout<<"\n 要退出系統(tǒng)了歡迎使用本系統(tǒng)\n";exit(0);}}}}最短尋道時(shí)間優(yōu)先算法/**********************voidSSTF(intcidao[],

最短尋道時(shí)間優(yōu)先調(diào)度算法intm)

********************/{system( "cls" );int k=1;int now,l,r;int i,j,sum=0;int a;charstr[100];float ave;cidao=bubble(cidao,m);

//調(diào)用冒泡排序算法排序cout<< "請(qǐng)輸入當(dāng)前的磁道號(hào)： ";C:cin>>str; //對(duì)輸入數(shù)據(jù)進(jìn)行有效性判斷a=decide(str);if(a==0){cout<<"輸入數(shù)據(jù)的類型錯(cuò)誤 ,請(qǐng)重新輸入！"<<endl;gotoC;}elsenow=trans(str,a);

//輸入當(dāng)前磁道號(hào)if(cidao[m-1]<=now)

//若當(dāng)前磁道號(hào)大于請(qǐng)求序列中最大者，

則直接由外向內(nèi)依次給予各請(qǐng)求服務(wù){(diào)cout<< "磁盤掃描序列為：";for(i=m-1;i>=0;i--)cout<<cidao[i]<< "";sum=now-cidao[0];}if(cidao[0]>=now) //若當(dāng)前磁道號(hào)小于請(qǐng)求序列中最小者，則直接由內(nèi)向外依次給予各請(qǐng)求服務(wù){(diào)cout<< "磁盤掃描序列為：";for(i=0;i<m;i++)cout<<cidao[i]<<sum=cidao[m-1]-now;

"";}if(now>cidao[0]&&now<cidao[m-1]) //若當(dāng)前磁道號(hào)大于請(qǐng)求序列中最小者且小于最大者{cout<< "磁盤掃描序列為： ";while(cidao[k]<now)

//確定當(dāng)前磁道在已排的序列中的位置，后面的算法都用到了，可以直接復(fù)制后少量修改，節(jié)省時(shí)間。{k++;}l=k-1;r=k;while((l>=0)&&(r<m))

//當(dāng)前磁道在請(qǐng)求序列范圍內(nèi){if((now-cidao[l])<=(cidao[r]-now)){cout<<cidao[l]<< "";sum+=now-cidao[l];now=cidao[l];l=l-1;}else{cout<<cidao[r]<< "";sum+=cidao[r]-now;

//選擇與當(dāng)前磁道最近的請(qǐng)求給予服務(wù)now=cidao[r];r=r+1;}}if(l==-1) //磁頭移動(dòng)到序列的最小號(hào)，返回外側(cè)掃描仍未掃描的磁道{for(j=r;j<m;j++){cout<<cidao[j]<< "";}sum+=cidao[m-1]-cidao[0];}else //磁頭移動(dòng)到序列的最大號(hào)，返回內(nèi)側(cè)掃描仍未掃描的磁道{for(j=l;j>=0;j--){cout<<cidao[j]<< "";}sum+=cidao[m-1]-cidao[0];}}ave=( float )(sum)/( float )(m);//求平均尋道長(zhǎng)度cout<<endl;cout<< "總的尋道長(zhǎng)度： "<<sum<<endl;cout<< "平均尋道長(zhǎng)度： "<<ave<<endl;cout<< "請(qǐng)按任意鍵返回系統(tǒng)菜單 "<<endl;getch();showMenu(cidao,m); //回到主界面}最 短 尋 道 時(shí) 間 優(yōu) 先 （ SSTF ） 算 法 實(shí) 現(xiàn) 界 面（2）掃描（SCAN）算法/***************************** 掃描調(diào)度算法*******************************/voidSCAN(int cidao[], int n)//先要給出當(dāng)前磁道號(hào)和移動(dòng)臂的移動(dòng)方向{int temp;int i,j;int now;int sum;for(i=0;i<n;i++)for(j=i+1;j<n;j++){if(cidao[i]>cidao[j]){

//給磁道號(hào)排序temp=cidao[i];cidao[i]=cidao[j];cidao[j]=temp;}}cout<<"\n按非遞減順序排列好的磁道 :\n" ;for(i=0;i<n;i++)

//輸出排好序的磁道號(hào)cout<<cidao[i]<<

"";cout<<endl;cout<<"\n請(qǐng)輸入當(dāng)前的磁道號(hào)cin>>now;if(cidao[n-1]<=now){

:";

//用戶自定義當(dāng)前磁道號(hào)for(i=n-1;i>=0;i--)cout<<cidao[i]<<sum=now-cidao[0];}

"";else

//cidao[n-1]>nowif(cidao[0]>=now){for(i=0;i<n;i++)cout<<cidao[i]<< "";sum=cidao[n-1]-now;}else

//cidao[0]<now&&cidao[n-1]>now{int pointer;int location=1;int left,right;while(cidao[location]<now)location++;left=location-1;right=location;cout<< "\n請(qǐng)輸入當(dāng)前磁頭想要移動(dòng)的方向

(1

磁道號(hào)增加方向，

0磁道號(hào)減小方向):" ;loop:cin>>pointer;cout<<

"\n磁盤調(diào)度順序?yàn)?\n" ;if(pointer==0||pointer==1){if(pointer==0) //磁頭向左移動(dòng)到最小號(hào)，再改變方向向外掃描未掃描的磁道{for(j=left;j>=0;j--)cout<<cidao[j]<<

""

;for(j=right;j<n;j++)c