磁盤移臂調(diào)度過程模擬設(shè)計(jì)電梯算法最短尋道時(shí)間優(yōu)先

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

1、-學(xué) 號(hào)：課 程 設(shè) 計(jì)題 目磁盤移臂調(diào)度過程模擬設(shè)計(jì)-電梯算法、最短尋道時(shí)間優(yōu)先算法學(xué) 院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院專 業(yè)班 級(jí)姓 名指導(dǎo)教師吳利軍2013年1月15日課程設(shè)計(jì)任務(wù)書學(xué)生：指導(dǎo)教師：吳利軍 工作單位： 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 題 目: 磁盤移臂調(diào)度過程模擬設(shè)計(jì)電梯算法、最短尋道時(shí)間優(yōu)先算法初始條件：1預(yù)備容：閱讀操作系統(tǒng)的文件管理章節(jié)容，理解有關(guān)文件組織形式、存儲(chǔ)設(shè)備的概念。2實(shí)踐準(zhǔn)備：掌握一種計(jì)算機(jī)高級(jí)語言的使用。要求完成的主要任務(wù): 包括課程設(shè)計(jì)工作量及其技術(shù)要求，以及說明書撰寫等具體要求1編程序模擬磁盤調(diào)度的過程，采用指定算法，模擬并輸出存取臂的移動(dòng)順序，并計(jì)算存取臂移動(dòng)的磁道

2、總數(shù)。 能夠處理以下的情形： 可根據(jù)需要輸入當(dāng)前磁頭的位置，磁頭移動(dòng)方向；能夠輸入柱面數(shù)，磁道訪問序列等參數(shù)，并能夠顯示調(diào)度結(jié)果磁盤訪問請(qǐng)求的磁道號(hào)以及磁頭移動(dòng)的總磁道數(shù)。2設(shè)計(jì)報(bào)告容應(yīng)說明：課程設(shè)計(jì)目的與功能；需求分析，數(shù)據(jù)構(gòu)造或模塊說明(功能與框圖)；源程序的主要局部；測(cè)試用例，運(yùn)行結(jié)果與運(yùn)行情況分析；自我評(píng)價(jià)與總結(jié)：i你認(rèn)為你完成的設(shè)計(jì)哪些地方做得比擬好或比擬出色；ii什么地方做得不太好，以后如何改正；iii從本設(shè)計(jì)得到的收獲在編寫，調(diào)試，執(zhí)行過程中的經(jīng)歷和教訓(xùn)；iv完成此題是否有其他的其他方法如果有，簡(jiǎn)要說明該方法；v對(duì)實(shí)驗(yàn)題的評(píng)價(jià)和改良意見，請(qǐng)你推薦設(shè)計(jì)題目。時(shí)間安排：設(shè)計(jì)安排一周：

3、周1、周2：完成程序分析及設(shè)計(jì)。周2、周3：完成程序調(diào)試及測(cè)試。周4、周5：驗(yàn)收，撰寫課程設(shè)計(jì)報(bào)告?？记绊氈簢?yán)禁抄襲，一旦發(fā)現(xiàn)，抄與被抄的一律按0分記指導(dǎo)教師簽名： 年 月 日系主任或責(zé)任教師簽名： 年 月 日磁盤移臂調(diào)度過程模擬設(shè)計(jì)電梯算法、最短尋道時(shí)間優(yōu)先算法1 課程設(shè)計(jì)目的與功能操作系統(tǒng)課程設(shè)計(jì)，主要是在學(xué)習(xí)操作系統(tǒng)課程并完成操作系統(tǒng)各局部實(shí)驗(yàn)的根底上，對(duì)操作系統(tǒng)的整體進(jìn)展一個(gè)模擬，通過實(shí)踐加深對(duì)各個(gè)局部的管理功能的認(rèn)識(shí)，進(jìn)一步分析各個(gè)局部之間的聯(lián)系，以到達(dá)對(duì)完整系統(tǒng)的理解。有助于提高運(yùn)用操作系統(tǒng)知識(shí)解決實(shí)際問題的能力；鍛煉實(shí)際的編程能力及創(chuàng)新能力；提高調(diào)查研究、查閱技術(shù)文獻(xiàn)、資料以及

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

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

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

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

8、當(dāng)前移動(dòng)方向。例如，當(dāng)磁頭正在自里向外移動(dòng)時(shí)，掃描算法所選擇的下一個(gè)訪問對(duì)象應(yīng)是其欲訪問的磁道既在當(dāng)前磁道之外，又是距離最近的。這樣自里向外地訪問，直到再無更外的磁道需要訪問才將磁臂換向，自外向里移動(dòng)。這時(shí)，同樣也是每次選擇這樣的進(jìn)程來調(diào)度，即其要訪問的磁道，在當(dāng)前磁道之，從而防止了饑餓現(xiàn)象的出現(xiàn)。由于這種算法中磁頭移動(dòng)的規(guī)律頗似電梯的運(yùn)行，故又稱為電梯調(diào)度算法。此算法根本上克制了最短尋道時(shí)間優(yōu)先算法的效勞集中于中間磁道和響應(yīng)時(shí)間變化比擬大的缺點(diǎn)，而具有最短尋道時(shí)間優(yōu)先算法的優(yōu)點(diǎn)即吞吐量較大，平均響應(yīng)時(shí)間較小，但由于是擺動(dòng)式的掃描方法，兩側(cè)磁道被訪問的頻率仍低于中間磁道。(4)循環(huán)掃描算法(C

9、SCAN):循環(huán)掃描算法是對(duì)掃描算法的改良。如果對(duì)磁道的訪問請(qǐng)均勻分布的， 當(dāng)磁頭到達(dá)磁盤的一端，并反向運(yùn)動(dòng)時(shí)落在磁頭之后的訪問請(qǐng)求相對(duì)較少。這是由于這些磁道剛被處理，而磁盤另一端的請(qǐng)求密度相當(dāng)高，且這些訪問請(qǐng)求等待的時(shí)間較長，為了解決這種情況，循環(huán)掃描算法規(guī)定磁頭單向移動(dòng)。例如，只自里向外移動(dòng)，當(dāng)磁頭移到最外的被訪問磁道時(shí)，磁頭立即返回到最里的欲訪磁道，即將最小磁道號(hào)緊接著最大磁道號(hào)構(gòu)成循環(huán)，進(jìn)展掃描。3數(shù)據(jù)構(gòu)造或模塊說明3.1數(shù)據(jù)構(gòu)造程序中涉及到的主要數(shù)據(jù)構(gòu)造如下：變量名類型說明totalint磁盤柱面總數(shù)locationint磁頭初始位置directionint磁頭初始移動(dòng)方向nint申

10、請(qǐng)?jiān)L問的磁道序列數(shù)組的元素個(gè)數(shù)aint臨時(shí)存儲(chǔ)訪問序列的數(shù)組，長度為MAXMAX=100mint磁頭移動(dòng)的總磁道數(shù)3.2函數(shù)程序中有三個(gè)函數(shù)：void sorting( )初始化柱面總數(shù)、磁頭初始位置、磁頭初始移動(dòng)方向、申請(qǐng)?jiān)L問的磁道序列。void sstf( )對(duì)磁盤移臂調(diào)度的最短尋道時(shí)間優(yōu)先算法進(jìn)展模擬，輸出磁道訪問序列和磁頭移動(dòng)的總磁道數(shù)。void scan( )對(duì)磁盤移臂調(diào)度的電梯算法進(jìn)展模擬，輸出磁道訪問序列和磁頭移動(dòng)的總磁道數(shù)。3.3模塊框圖程序分為四大模塊，分別為數(shù)據(jù)初始化、訪問序列排序，電梯算法調(diào)度和最短尋道時(shí)間優(yōu)先算法調(diào)度，依靠sorting，scan，sstf三個(gè)函數(shù)實(shí)現(xiàn)。

11、程序總流程如下：開場(chǎng)是否開場(chǎng)程序設(shè)置磁盤柱面數(shù)total設(shè)置當(dāng)前磁頭的位置locationLocationtotal設(shè)置要訪問的磁道數(shù)nnMAX報(bào)錯(cuò)報(bào)錯(cuò)設(shè)置此道訪問序列anaitotal或ai0報(bào)錯(cuò)調(diào)用sorting調(diào)用sstf調(diào)用scan完畢YNNYNYNY初始化4 源程序#include#include#define MAX 20int run_number; /記錄實(shí)際柱面數(shù)int runMAX; /記錄每道的磁道序列int run_jiluMAX;int daoshu;bool FLAG_USEDMAX;int abs_LONGTHMAX;int abs_number(int a,in

12、t b)if(ab)return a-b;elsereturn b-a;int cmp(const void *a,const void *b)int x=*(int *)a;int y=*(int *)b;return (xy1: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; /如果開場(chǎng)位置在序列中就繼續(xù)執(zhí)行，否那么參加其中 for( i=0;irun_number;i+) if(run_begin=runi) bre

13、ak; if(i=run_number) run_number+=1;runrun_number-1=run_begin; /快排序 qsort(run,run_number,sizeof(int),cmp); for(i=0;i=0;i-) run_jiluj=runi;j+;if(i0)flag_t=true;if(flag_t=true)for(i=jilu+1;irun_number;i+) run_jiluj=runi; j+; daoshu=run_begin-run0+runrun_number-1-run0; if(flag=true) j=0; for(i=jilu;irun

14、_number;i+) run_jiluj=runi; j+; if(i=0;i-) run_jiluj=runi; j+; daoshu=runrun_number-1-run_begin+runrun_number-1-run0; /bool end_not(bool a)for(int i=0;irun_number;i+)if(ai=false)return false;return true;/最短尋道時(shí)間算法void SSTF(int run,int run_jilu,int run_begin)int jilu,temp,flag,i,j;flag=0;run_jiluflag=

15、run_begin;daoshu=0; /如果開場(chǎng)位置在序列中就繼續(xù)執(zhí)行，否那么參加其中for( i=0;irun_number;i+)if(run_begin=runi)break;if(i=run_number)run_number+=1;runrun_number-1=run_begin;for(i=0;irun_number;i+)FLAG_USEDi=false;for(i=0;irun_number;i+)if(run_begin=runi)jilu=i;break;FLAG_USEDjilu=true;/當(dāng)沒走完時(shí)while(!end_not(FLAG_USED)for( j=0

16、;jrun_number;j+) abs_LONGTHj=abs_number(run_begin,runj);for(j=0;jrun_number;j+)if(FLAG_USEDj=false)temp=abs_LONGTHj;break; for(i=0;iabs_LONGTHi&FLAG_USEDi=false)temp=abs_LONGTHi;for(i=0;irun_number;i+)if(temp=abs_LONGTHi&FLAG_USEDi=false) run_begin=runi;flag+; run_jiluflag=run_begin;FLAG_USEDi=true;

17、break;for(flag=0;flagrun_number-1;flag+)daoshu+=abs_number(run_jiluflag+1,run_jiluflag);int main()int run_begin,as,at,i;bool flag;printf(請(qǐng)輸入柱面數(shù):);scanf(%d,&run_number);printf(請(qǐng)輸入各道磁道數(shù)n); for( i=0;irun_number;i+)scanf(%d,&runi);printf(請(qǐng)輸入開場(chǎng)磁道數(shù):);scanf(%d,&run_begin);printf(請(qǐng)選擇尋道方式(1-電梯算法，2-最短尋道);scan

18、f(%d,&at);while(at!=1&at!=2)printf(請(qǐng)選擇尋道方式(1-電梯算法，2-最短尋道);scanf(%d,&at); if(at=1) printf(請(qǐng)輸入走向1-上，2下:); 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_begin); printf(走道次序:

19、); for(i=0;itotal實(shí)現(xiàn)報(bào)錯(cuò)，但在VC+6.0環(huán)境中不能運(yùn)行，故還是沒有解決?？偟恼f來，與之涉及的很多方面并沒有學(xué)過，自己還需要去自學(xué)和實(shí)踐檢驗(yàn)。所以在以后的學(xué)習(xí)中一方面我要不斷的穩(wěn)固自己所學(xué)的理論知識(shí)，一方面還要多參加實(shí)際操作工作以便提高自己的實(shí)際操作能力。本科生課程設(shè)計(jì)成績?cè)u(píng)定表序號(hào)評(píng)分工程總分值實(shí)得分1學(xué)習(xí)態(tài)度認(rèn)真、遵守紀(jì)律102設(shè)計(jì)分析合理性103設(shè)計(jì)方案正確性、可行性、創(chuàng)造性204設(shè)計(jì)結(jié)果正確性405設(shè)計(jì)報(bào)告的規(guī)性106設(shè)計(jì)驗(yàn)收10總得分/等級(jí)評(píng)語：注：最終成績以五級(jí)分制記。優(yōu)90-100分、良80-89分、中70-79分、及格60-69分、60分以下為不及格指導(dǎo)教師簽名： 2013 年 1月15 日 . z.