《磁盤(pán)移臂調(diào)度過(guò)程模擬設(shè)計(jì)-電梯算法_最短尋道時(shí)間優(yōu)先》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《磁盤(pán)移臂調(diào)度過(guò)程模擬設(shè)計(jì)-電梯算法_最短尋道時(shí)間優(yōu)先（16頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、武漢理工大學(xué)《操作系統(tǒng)》課程設(shè)計(jì) 學(xué) 號(hào)： 課 程 設(shè) 計(jì) 題 目 磁盤(pán)移臂調(diào)度過(guò)程模擬設(shè)計(jì) --電梯算法、最短尋道時(shí)間優(yōu)先算法 學(xué) 院 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 專(zhuān) 業(yè) 班 級(jí) 姓 名 指導(dǎo)教師 吳利軍 2013 年 1 月 15 日 課程設(shè)計(jì)任務(wù)書(shū) 學(xué)生姓名： 指導(dǎo)教師：吳利軍 工作單位： 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 題 目: 磁盤(pán)移臂調(diào)度過(guò)程模擬設(shè)計(jì)——電梯算法、最短尋道時(shí)間優(yōu)先算法 初始條件： 1．預(yù)備內(nèi)容：閱

2、讀操作系統(tǒng)的文件管理章節(jié)內(nèi)容，理解有關(guān)文件組織形式、存儲(chǔ)設(shè)備的概念。 2．實(shí)踐準(zhǔn)備：掌握一種計(jì)算機(jī)高級(jí)語(yǔ)言的使用。 要求完成的主要任務(wù): （包括課程設(shè)計(jì)工作量及其技術(shù)要求，以及說(shuō)明書(shū)撰寫(xiě)等具體要求） 1．編程序模擬磁盤(pán)調(diào)度的過(guò)程，采用指定算法，模擬并輸出存取臂的移動(dòng)順序，并計(jì)算存取臂移動(dòng)的磁道總數(shù)。 能夠處理以下的情形： ⑴ 可根據(jù)需要輸入當(dāng)前磁頭的位置，磁頭移動(dòng)方向； ⑵ 能夠輸入柱面數(shù)，磁道訪(fǎng)問(wèn)序列等參數(shù)，并能夠顯示調(diào)度結(jié)果（磁盤(pán)訪(fǎng)問(wèn)請(qǐng)求的磁道號(hào)以及磁頭移動(dòng)的總磁道數(shù)）。 2．設(shè)計(jì)報(bào)告內(nèi)容應(yīng)說(shuō)明： ⑴ 課程設(shè)計(jì)目的與功能； ⑵ 需求分析，數(shù)據(jù)結(jié)構(gòu)或模塊說(shuō)明(功能與框圖)

3、； ⑶ 源程序的主要部分； ⑷ 測(cè)試用例，運(yùn)行結(jié)果與運(yùn)行情況分析； ⑸ 自我評(píng)價(jià)與總結(jié)： i）你認(rèn)為你完成的設(shè)計(jì)哪些地方做得比較好或比較出色； ii）什么地方做得不太好，以后如何改正； iii）從本設(shè)計(jì)得到的收獲（在編寫(xiě)，調(diào)試，執(zhí)行過(guò)程中的經(jīng)驗(yàn)和教訓(xùn)）； iv）完成本題是否有其他的其他方法（如果有，簡(jiǎn)要說(shuō)明該方法）； v）對(duì)實(shí)驗(yàn)題的評(píng)價(jià)和改進(jìn)意見(jiàn)，請(qǐng)你推薦設(shè)計(jì)題目。 時(shí)間安排： 設(shè)計(jì)安排一周：周1、周2：完成程序分析及設(shè)計(jì)。 周2、周3：完成程序調(diào)試及測(cè)試。 周4、周5：驗(yàn)收，撰寫(xiě)課程設(shè)計(jì)報(bào)告。 （注意事項(xiàng)：嚴(yán)禁抄襲，一旦發(fā)現(xiàn)，抄與被抄的一律按0分記） 指導(dǎo)教師簽

4、名： 年 月 日 系主任（或責(zé)任教師）簽名： 年 月 日 磁盤(pán)移臂調(diào)度過(guò)程模擬設(shè)計(jì) ——電梯算法、最短尋道時(shí)間優(yōu)先算法 1 課程設(shè)計(jì)目的與功能 操作系統(tǒng)課程設(shè)計(jì)，主要是在學(xué)習(xí)操作系統(tǒng)課程并完成操作系統(tǒng)各部分實(shí)驗(yàn)的基礎(chǔ)上，對(duì)操作系統(tǒng)的整體進(jìn)行一個(gè)模擬，通過(guò)實(shí)踐加深對(duì)各個(gè)部分的管理功能的認(rèn)識(shí)，進(jìn)一步分析各個(gè)部分之間的聯(lián)系，以達(dá)到對(duì)完整系統(tǒng)的理解。有助于提高運(yùn)用操作系統(tǒng)知識(shí)解決實(shí)際問(wèn)題的能力；鍛煉實(shí)際的編程能力及創(chuàng)新能力；提高調(diào)查研究、查閱技術(shù)文獻(xiàn)、資料以及編寫(xiě)軟件設(shè)計(jì)文檔的能力。 本課程

5、設(shè)計(jì)是通過(guò)設(shè)計(jì)一個(gè)磁盤(pán)調(diào)度模擬系統(tǒng)，深入理解磁盤(pán)的工作原理，從而使磁盤(pán)調(diào)度更加形象化，容易使人理解，使磁盤(pán)調(diào)度的特點(diǎn)更簡(jiǎn)單明了，能使使用者加深對(duì)磁盤(pán)調(diào)度算法的理解。具體實(shí)現(xiàn)為，運(yùn)用一門(mén)高級(jí)編程語(yǔ)言編寫(xiě)程序模擬磁盤(pán)調(diào)度的過(guò)程，采用先來(lái)先服務(wù)算法和電梯算法，模擬并輸出存取臂的移動(dòng)順序，并計(jì)算存取臂移動(dòng)的磁道總數(shù)。能夠處理以下的情形： (1)可根據(jù)需要輸入當(dāng)前磁頭的位置，磁頭移動(dòng)方向； (2)能夠輸入柱面數(shù)，磁道訪(fǎng)問(wèn)序列等參數(shù)，并能夠顯示調(diào)度結(jié)果（磁盤(pán)訪(fǎng)問(wèn)請(qǐng)求的磁道號(hào)以及磁頭移動(dòng)的總磁道數(shù)）。 2 需求分析 2.1磁盤(pán)的工作原理 磁盤(pán)是最典型的直接存取設(shè)備。磁盤(pán)設(shè)備允許

6、文件系統(tǒng)直接存取磁盤(pán)上的任意物理塊。為了存取一個(gè)特定的物理塊，磁頭將直接移動(dòng)到所要求的位置上，而不需要像順序存取那樣事先存取其他的物理塊。 磁盤(pán)機(jī)各類(lèi)很多，但一般由一些磁盤(pán)片組成的磁盤(pán)組組成。其中每個(gè)磁盤(pán)片對(duì)應(yīng)一個(gè)裝有讀寫(xiě)磁頭的磁頭臂，磁頭臂上的兩個(gè)讀寫(xiě)磁頭分別對(duì)磁盤(pán)片的上下兩面進(jìn)行讀寫(xiě)。系統(tǒng)在對(duì)磁盤(pán)進(jìn)行初始化處理時(shí)，把每個(gè)磁盤(pán)片分割成一些大小相等的扇區(qū)。在磁盤(pán)轉(zhuǎn)動(dòng)時(shí)經(jīng)過(guò)讀寫(xiě)磁頭所形成的圓形軌跡稱(chēng)為磁道。由于磁頭臂可沿半徑方向移動(dòng)，因此，磁盤(pán)上有多條磁道。另外，人們通常把所有磁盤(pán)片的相同磁道稱(chēng)為一個(gè)柱面，因此，磁盤(pán)上每個(gè)物理塊的位置可以用柱面號(hào)、磁頭號(hào)和扇區(qū)號(hào)表示，這些地址和物理塊號(hào)一一對(duì)應(yīng)

7、。 2.2磁盤(pán)的調(diào)度算法 操作系統(tǒng)中，對(duì)磁盤(pán)的訪(fǎng)問(wèn)要求來(lái)自多方面，常常需要排隊(duì)。這時(shí)，對(duì)眾多的訪(fǎng)問(wèn)要求按一定的次序響應(yīng)，會(huì)直接影響磁盤(pán)的工作效率，進(jìn)而影響系統(tǒng)的性能。訪(fǎng)問(wèn)磁盤(pán)的時(shí)間因子由3部分構(gòu)成，它們是查找（查找磁道）時(shí)間、等待（旋轉(zhuǎn)等待扇區(qū)）時(shí)間和數(shù)據(jù)傳輸時(shí)間，其中查找時(shí)間是決定因素。因此，磁盤(pán)調(diào)度算法先考慮優(yōu)化查找策略，需要時(shí)再優(yōu)化旋轉(zhuǎn)等待策略。主要的磁盤(pán)調(diào)度算法有下面四種： (1)先來(lái)先服務(wù)算法(FCFS): 這是一種比較簡(jiǎn)單的磁盤(pán)調(diào)度算法。它根據(jù)進(jìn)程請(qǐng)求訪(fǎng)問(wèn)磁盤(pán)的先后次序進(jìn)行調(diào)度。此算法的優(yōu)點(diǎn)是公平、簡(jiǎn)單，且每個(gè)進(jìn)程的請(qǐng)求都能依次得到處理，不會(huì)出現(xiàn)某一進(jìn)程的請(qǐng)求長(zhǎng)期得不到滿(mǎn)足

8、的情況。此算法由于未對(duì)尋道進(jìn)行優(yōu)化，在對(duì)磁盤(pán)的訪(fǎng)問(wèn)請(qǐng)求比較多的情況下，此算法將降低設(shè)備服務(wù)的吞吐量，致使平均尋道時(shí)間可能較長(zhǎng)，但各進(jìn)程得到服務(wù)的響應(yīng)時(shí)間的變化幅度較小。 (2)最短尋道時(shí)間優(yōu)先算法(SSTF): 該算法選擇這樣的進(jìn)程，其要求訪(fǎng)問(wèn)的磁道與當(dāng)前磁頭所在的磁道距離最近，以使每次的尋道時(shí)間最短，該算法可以得到比較好的吞吐量，但卻不能保證平均尋道時(shí)間最短。其缺點(diǎn)是對(duì)用戶(hù)的服務(wù)請(qǐng)求的響應(yīng)機(jī)會(huì)不是均等的，因而導(dǎo)致響應(yīng)時(shí)間的變化幅度很大。在服務(wù)請(qǐng)求很多的情況下，對(duì)內(nèi)外邊緣磁道的請(qǐng)求將會(huì)無(wú)限期的被延遲，有些請(qǐng)求的響應(yīng)時(shí)間將不可預(yù)期。 (3)掃描算法(SCAN)，即電梯算法: 掃描算法不僅

9、考慮到欲訪(fǎng)問(wèn)的磁道與當(dāng)前磁道的距離，更優(yōu)先考慮的是磁頭的當(dāng)前移動(dòng)方向。例如，當(dāng)磁頭正在自里向外移動(dòng)時(shí)，掃描算法所選擇的下一個(gè)訪(fǎng)問(wèn)對(duì)象應(yīng)是其欲訪(fǎng)問(wèn)的磁道既在當(dāng)前磁道之外，又是距離最近的。這樣自里向外地訪(fǎng)問(wèn)，直到再無(wú)更外的磁道需要訪(fǎng)問(wèn)才將磁臂換向，自外向里移動(dòng)。這時(shí)，同樣也是每次選擇這樣的進(jìn)程來(lái)調(diào)度，即其要訪(fǎng)問(wèn)的磁道，在當(dāng)前磁道之內(nèi)，從而避免了饑餓現(xiàn)象的出現(xiàn)。由于這種算法中磁頭移動(dòng)的規(guī)律頗似電梯的運(yùn)行，故又稱(chēng)為電梯調(diào)度算法。此算法基本上克服了最短尋道時(shí)間優(yōu)先算法的服務(wù)集中于中間磁道和響應(yīng)時(shí)間變化比較大的缺點(diǎn)，而具有最短尋道時(shí)間優(yōu)先算法的優(yōu)點(diǎn)即吞吐量較大，平均響應(yīng)時(shí)間較小，但由于是擺動(dòng)式的掃描方法，

10、兩側(cè)磁道被訪(fǎng)問(wèn)的頻率仍低于中間磁道。 (4)循環(huán)掃描算法(CSCAN): 循環(huán)掃描算法是對(duì)掃描算法的改進(jìn)。如果對(duì)磁道的訪(fǎng)問(wèn)請(qǐng)求是均勻分布的， 當(dāng)磁頭到達(dá)磁盤(pán)的一端，并反向運(yùn)動(dòng)時(shí)落在磁頭之后的訪(fǎng)問(wèn)請(qǐng)求相對(duì)較少。這是由于這些磁道剛被處理，而磁盤(pán)另一端的請(qǐng)求密度相當(dāng)高，且這些訪(fǎng)問(wèn)請(qǐng)求等待的時(shí)間較長(zhǎng)，為了解決這種情況，循環(huán)掃描算法規(guī)定磁頭單向移動(dòng)。例如，只自里向外移動(dòng)，當(dāng)磁頭移到最外的被訪(fǎng)問(wèn)磁道時(shí)，磁頭立即返回到最里的欲訪(fǎng)磁道，即將最小磁道號(hào)緊接著最大磁道號(hào)構(gòu)成循環(huán)，進(jìn)行掃描。 3數(shù)據(jù)結(jié)構(gòu)或模塊說(shuō)明 3.1數(shù)據(jù)結(jié)構(gòu) 程序中涉及到的主要數(shù)據(jù)結(jié)構(gòu)如下： 變量名 類(lèi)型 說(shuō)明 total

11、 int 磁盤(pán)柱面總數(shù) location int 磁頭初始位置 direction int 磁頭初始移動(dòng)方向 n int 申請(qǐng)?jiān)L問(wèn)的磁道序列數(shù)組的元素個(gè)數(shù) a int[] 臨時(shí)存儲(chǔ)訪(fǎng)問(wèn)序列的數(shù)組，長(zhǎng)度為MAX（MAX=100） m int 磁頭移動(dòng)的總磁道數(shù) 3.2函數(shù) 程序中有三個(gè)函數(shù)： void sorting( )——初始化柱面總數(shù)、磁頭初始位置、磁頭初始移動(dòng)方向、申請(qǐng)?jiān)L問(wèn)的磁道序列。 void sstf( )——對(duì)磁盤(pán)移臂調(diào)度的最短尋道時(shí)間優(yōu)先算法進(jìn)行模擬，輸出磁道訪(fǎng)問(wèn)序列和磁頭移動(dòng)的總磁道數(shù)。 void scan( )——

12、對(duì)磁盤(pán)移臂調(diào)度的電梯算法進(jìn)行模擬，輸出磁道訪(fǎng)問(wèn)序列和磁頭移動(dòng)的總磁道數(shù)。 3.3模塊框圖 程序分為四大模塊，分別為數(shù)據(jù)初始化、訪(fǎng)問(wèn)序列排序，電梯算法調(diào)度和最短尋道時(shí)間優(yōu)先算法調(diào)度，依靠sorting，scan，sstf三個(gè)函數(shù)實(shí)現(xiàn)。 程序總流程如下： 開(kāi)始 是否開(kāi)始程序 設(shè)置磁盤(pán)柱面數(shù)total 設(shè)置當(dāng)前磁頭的位置location Location>total 設(shè)置要訪(fǎng)問(wèn)的磁道數(shù)n n>MAX 報(bào)錯(cuò) 報(bào)錯(cuò) 設(shè)置此道訪(fǎng)問(wèn)序列a[n] a[i]>total或a[i]<0 報(bào)錯(cuò) 調(diào)用sorting（） 調(diào)用sstf（） 調(diào)用scan（） 結(jié)束

13、 Y N N Y N Y N Y 初 始 化 4 源程序 #include #include #define MAX 20 int run_number; //記錄實(shí)際柱面數(shù) int run[MAX]; //記錄每道的磁道序列 int run_jilu[MAX]; int daoshu; bool FLAG_USED[MAX]; int abs_LONGTH[MAX]; int abs_number(int a,int b) { if(a>b) return a

14、-b; else return b-a; } int cmp(const void *a,const void *b) { int x=*(int *)a; int y=*(int *)b; return (xy?1:0); } //電梯算法，當(dāng)flag=false向下走 void SCAN(int run[],int run_jilu[],int run_begin,bool flag) { int jilu,j,i; bool flag_t=false; //如果開(kāi)始位置在序列中就繼續(xù)執(zhí)行，否則加入其中 for

15、( i=0;i

16、 } } if(flag==false) { j=0; for(i=jilu;i>=0;i--) { run_jilu[j]=run[i]; j++; } if(i<0)flag_t=true; if(flag_t=true) { for(i=jilu+1;i

17、run[0]; } if(flag==true) { j=0; for(i=jilu;i=0;i--) { run_jilu[j]=run[i]; j++; } } daoshu=run[run_number-

18、1]-run_begin+run[run_number-1]-run[0]; } } // bool end_not(bool a[]) { for(int i=0;i

19、un_begin; daoshu=0; //如果開(kāi)始位置在序列中就繼續(xù)執(zhí)行，否則加入其中 for( i=0;i

20、 { if(run_begin==run[i]) { jilu=i; break; } } FLAG_USED[jilu]=true; //當(dāng)沒(méi)走完時(shí) while(!end_not(FLAG_USED)) { for( j=0;j

21、s_LONGTH[j]; break; } } for(i=0;iabs_LONGTH[i]&&FLAG_USED[i]==false) temp=abs_LONGTH[i]; } for(i=0;i

22、_begin; FLAG_USED[i]=true; break; } } } for(flag=0;flag

23、i=0;i

24、 scanf("%d",&as); while(as!=1&&as!=2) { printf("請(qǐng)輸入走向（1--上，2——下）:"); scanf("%d",&as); } if(as==1) { flag=true; } if(as==2) { flag=false; } SCAN(run,run_jilu,run_begin,flag); } if(at==2) { SSTF(run,run_jilu,run_begi

25、n); } printf("走道次序:"); for(i=0;i

26、要增強(qiáng)程序的健壯性并且實(shí)際去編程實(shí)現(xiàn)，就遇到了相當(dāng)大的難度。例如測(cè)試中提到的對(duì)int型數(shù)據(jù)的非法輸入的報(bào)錯(cuò)等，都是可以改進(jìn)的部分，為此也翻閱過(guò)資料，網(wǎng)絡(luò)上提供的修改方案是利用while（！cin>>total）實(shí)現(xiàn)報(bào)錯(cuò)，但在VC++6.0環(huán)境中不能運(yùn)行，故還是沒(méi)有解決?？偟恼f(shuō)來(lái)，與之涉及的很多方面并沒(méi)有學(xué)過(guò)，自己還需要去自學(xué)和實(shí)踐檢驗(yàn)。所以在以后的學(xué)習(xí)中一方面我要不斷的鞏固自己所學(xué)的理論知識(shí)，一方面還要多參加實(shí)際操作工作以便提高自己的實(shí)際操作能力。 本科生課程設(shè)計(jì)成績(jī)?cè)u(píng)定表 序號(hào) 評(píng)分項(xiàng)目 滿(mǎn)分 實(shí)得分 1 學(xué)習(xí)態(tài)度認(rèn)真、遵守紀(jì)律 10 2 設(shè)計(jì)分析合理性 10 3 設(shè)計(jì)方案正確性、可行性、創(chuàng)造性 20 4 設(shè)計(jì)結(jié)果正確性 40 5 設(shè)計(jì)報(bào)告的規(guī)范性 10 6 設(shè)計(jì)驗(yàn)收 10 總得分/等級(jí) 評(píng)語(yǔ)： 注：最終成績(jī)以五級(jí)分制記。優(yōu)（90-100分）、良（80-89分）、中（70-79分）、 及格（60-69分）、60分以下為不及格 指導(dǎo)教師簽名： 2013 年 1月　15 日