磁盤移臂調度過程模擬設計-電梯算法_最短尋道時間優(yōu)先

武漢理工大學操作系統(tǒng)課程設計學 號： 課 程 設 計題 目磁盤移臂調度過程模擬設計-電梯算法、最短尋道時間優(yōu)先算法學 院計算機科學與技術學院專 業(yè)班 級姓 名指導教師吳利軍2013年1月15日課程設計任務書學生姓名： 指導教師：吳利軍 工作單位： 計算機科學與技術學院 題 目: 磁盤移臂調度過程模擬設計電梯算法、最短尋道時間優(yōu)先算法初始條件：1預備內容：閱讀操作系統(tǒng)的文件管理章節(jié)內容，理解有關文件組織形式、存儲設備的概念。2實踐準備：掌握一種計算機高級語言的使用。要求完成的主要任務: （包括課程設計工作量及其技術要求，以及說明書撰寫等具體要求）1編程序模擬磁盤調度的過程，采用指定算法，模擬并輸出存取臂的移動順序，并計算存取臂移動的磁道總數(shù)。 能夠處理以下的情形： 可根據(jù)需要輸入當前磁頭的位置，磁頭移動方向； 能夠輸入柱面數(shù)，磁道訪問序列等參數(shù)，并能夠顯示調度結果（磁盤訪問請求的磁道號以及磁頭移動的總磁道數(shù)）。2設計報告內容應說明： 課程設計目的與功能； 需求分析，數(shù)據(jù)結構或模塊說明(功能與框圖)； 源程序的主要部分； 測試用例，運行結果與運行情況分析； 自我評價與總結：i）你認為你完成的設計哪些地方做得比較好或比較出色；ii）什么地方做得不太好，以后如何改正；iii）從本設計得到的收獲（在編寫，調試，執(zhí)行過程中的經(jīng)驗和教訓）；iv）完成本題是否有其他的其他方法（如果有，簡要說明該方法）；v）對實驗題的評價和改進意見，請你推薦設計題目。時間安排：設計安排一周：周1、周2：完成程序分析及設計。周2、周3：完成程序調試及測試。周4、周5：驗收，撰寫課程設計報告。（注意事項：嚴禁抄襲，一旦發(fā)現(xiàn)，抄與被抄的一律按0分記）指導教師簽名： 年 月 日系主任（或責任教師）簽名： 年 月 日磁盤移臂調度過程模擬設計電梯算法、最短尋道時間優(yōu)先算法1 課程設計目的與功能操作系統(tǒng)課程設計，主要是在學習操作系統(tǒng)課程并完成操作系統(tǒng)各部分實驗的基礎上，對操作系統(tǒng)的整體進行一個模擬，通過實踐加深對各個部分的管理功能的認識，進一步分析各個部分之間的聯(lián)系，以達到對完整系統(tǒng)的理解。有助于提高運用操作系統(tǒng)知識解決實際問題的能力；鍛煉實際的編程能力及創(chuàng)新能力；提高調查研究、查閱技術文獻、資料以及編寫軟件設計文檔的能力。本課程設計是通過設計一個磁盤調度模擬系統(tǒng)，深入理解磁盤的工作原理，從而使磁盤調度更加形象化，容易使人理解，使磁盤調度的特點更簡單明了，能使使用者加深對磁盤調度算法的理解。具體實現(xiàn)為，運用一門高級編程語言編寫程序模擬磁盤調度的過程，采用先來先服務算法和電梯算法，模擬并輸出存取臂的移動順序，并計算存取臂移動的磁道總數(shù)。能夠處理以下的情形： (1)可根據(jù)需要輸入當前磁頭的位置，磁頭移動方向； (2)能夠輸入柱面數(shù)，磁道訪問序列等參數(shù)，并能夠顯示調度結果（磁盤訪問請求的磁道號以及磁頭移動的總磁道數(shù)）。2 需求分析2.1磁盤的工作原理磁盤是最典型的直接存取設備。磁盤設備允許文件系統(tǒng)直接存取磁盤上的任意物理塊。為了存取一個特定的物理塊，磁頭將直接移動到所要求的位置上，而不需要像順序存取那樣事先存取其他的物理塊。磁盤機各類很多，但一般由一些磁盤片組成的磁盤組組成。其中每個磁盤片對應一個裝有讀寫磁頭的磁頭臂，磁頭臂上的兩個讀寫磁頭分別對磁盤片的上下兩面進行讀寫。系統(tǒng)在對磁盤進行初始化處理時，把每個磁盤片分割成一些大小相等的扇區(qū)。在磁盤轉動時經(jīng)過讀寫磁頭所形成的圓形軌跡稱為磁道。由于磁頭臂可沿半徑方向移動，因此，磁盤上有多條磁道。另外，人們通常把所有磁盤片的相同磁道稱為一個柱面，因此，磁盤上每個物理塊的位置可以用柱面號、磁頭號和扇區(qū)號表示，這些地址和物理塊號一一對應。2.2磁盤的調度算法操作系統(tǒng)中，對磁盤的訪問要求來自多方面，常常需要排隊。這時，對眾多的訪問要求按一定的次序響應，會直接影響磁盤的工作效率，進而影響系統(tǒng)的性能。訪問磁盤的時間因子由3部分構成，它們是查找（查找磁道）時間、等待（旋轉等待扇區(qū)）時間和數(shù)據(jù)傳輸時間，其中查找時間是決定因素。因此，磁盤調度算法先考慮優(yōu)化查找策略，需要時再優(yōu)化旋轉等待策略。主要的磁盤調度算法有下面四種：(1)先來先服務算法(FCFS):這是一種比較簡單的磁盤調度算法。它根據(jù)進程請求訪問磁盤的先后次序進行調度。此算法的優(yōu)點是公平、簡單，且每個進程的請求都能依次得到處理，不會出現(xiàn)某一進程的請求長期得不到滿足的情況。此算法由于未對尋道進行優(yōu)化，在對磁盤的訪問請求比較多的情況下，此算法將降低設備服務的吞吐量，致使平均尋道時間可能較長，但各進程得到服務的響應時間的變化幅度較小。(2)最短尋道時間優(yōu)先算法(SSTF):該算法選擇這樣的進程，其要求訪問的磁道與當前磁頭所在的磁道距離最近，以使每次的尋道時間最短，該算法可以得到比較好的吞吐量，但卻不能保證平均尋道時間最短。其缺點是對用戶的服務請求的響應機會不是均等的，因而導致響應時間的變化幅度很大。在服務請求很多的情況下，對內外邊緣磁道的請求將會無限期的被延遲，有些請求的響應時間將不可預期。(3)掃描算法(SCAN)，即電梯算法:掃描算法不僅考慮到欲訪問的磁道與當前磁道的距離，更優(yōu)先考慮的是磁頭的當前移動方向。例如，當磁頭正在自里向外移動時，掃描算法所選擇的下一個訪問對象應是其欲訪問的磁道既在當前磁道之外，又是距離最近的。這樣自里向外地訪問，直到再無更外的磁道需要訪問才將磁臂換向，自外向里移動。這時，同樣也是每次選擇這樣的進程來調度，即其要訪問的磁道，在當前磁道之內，從而避免了饑餓現(xiàn)象的出現(xiàn)。由于這種算法中磁頭移動的規(guī)律頗似電梯的運行，故又稱為電梯調度算法。此算法基本上克服了最短尋道時間優(yōu)先算法的服務集中于中間磁道和響應時間變化比較大的缺點，而具有最短尋道時間優(yōu)先算法的優(yōu)點即吞吐量較大，平均響應時間較小，但由于是擺動式的掃描方法，兩側磁道被訪問的頻率仍低于中間磁道。(4)循環(huán)掃描算法(CSCAN):循環(huán)掃描算法是對掃描算法的改進。如果對磁道的訪問請求是均勻分布的， 當磁頭到達磁盤的一端，并反向運動時落在磁頭之后的訪問請求相對較少。這是由于這些磁道剛被處理，而磁盤另一端的請求密度相當高，且這些訪問請求等待的時間較長，為了解決這種情況，循環(huán)掃描算法規(guī)定磁頭單向移動。例如，只自里向外移動，當磁頭移到最外的被訪問磁道時，磁頭立即返回到最里的欲訪磁道，即將最小磁道號緊接著最大磁道號構成循環(huán)，進行掃描。3數(shù)據(jù)結構或模塊說明3.1數(shù)據(jù)結構程序中涉及到的主要數(shù)據(jù)結構如下：變量名類型說明totalint磁盤柱面總數(shù)locationint磁頭初始位置directionint磁頭初始移動方向nint申請訪問的磁道序列數(shù)組的元素個數(shù)aint臨時存儲訪問序列的數(shù)組，長度為MAX（MAX=100）mint磁頭移動的總磁道數(shù)3.2函數(shù)程序中有三個函數(shù)： void sorting( )初始化柱面總數(shù)、磁頭初始位置、磁頭初始移動方向、申請訪問的磁道序列。 void sstf( )對磁盤移臂調度的最短尋道時間優(yōu)先算法進行模擬，輸出磁道訪問序列和磁頭移動的總磁道數(shù)。 void scan( )對磁盤移臂調度的電梯算法進行模擬，輸出磁道訪問序列和磁頭移動的總磁道數(shù)。3.3模塊框圖程序分為四大模塊，分別為數(shù)據(jù)初始化、訪問序列排序，電梯算法調度和最短尋道時間優(yōu)先算法調度，依靠sorting，scan，sstf三個函數(shù)實現(xiàn)。程序總流程如下： 開始是否開始程序設置磁盤柱面數(shù)total設置當前磁頭的位置locationLocation>total設置要訪問的磁道數(shù)nn>MAX報錯報錯設置此道訪問序列anai>total或ai<0報錯調用sorting（）調用sstf（）調用scan（）結束YNNYNYNY初始化4 源程序#include<stdio.h>#include<stdlib.h>#define MAX 20int run_number; /記錄實際柱面數(shù)int runMAX; /記錄每道的磁道序列int run_jiluMAX;int daoshu;bool FLAG_USEDMAX;int abs_LONGTHMAX;int abs_number(int a,int b)if(a>b)return a-b;elsereturn b-a;int cmp(const void *a,const void *b)int x=*(int *)a;int y=*(int *)b;return (x<y?-1:x>y?1:0);/電梯算法，當flag=false向下走void SCAN(int run,int run_jilu,int run_begin,bool flag) int jilu,j,i; bool flag_t=false; /如果開始位置在序列中就繼續(xù)執(zhí)行，否則加入其中 for( i=0;i<run_number;i+) if(run_begin=runi) break; if(i=run_number) run_number+=1;runrun_number-1=run_begin; /快排序 qsort(run,run_number,sizeof(int),cmp); for(i=0;i<run_number;i+) if(run_begin=runi)jilu=i;break; if(flag=false) j=0; for(i=jilu;i>=0;i-) run_jiluj=runi;j+;if(i<0)flag_t=true;if(flag_t=true)for(i=jilu+1;i<run_number;i+) run_jiluj=runi; j+; daoshu=run_begin-run0+runrun_number-1-run0; if(flag=true) j=0; for(i=jilu;i<run_number;i+) run_jiluj=runi; j+; if(i<0)flag_t=true; if(flag_t=true) for(i=jilu-1;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;i<run_number;i+)if(ai=false)return false;return true;/最短尋道時間算法void SSTF(int run,int run_jilu,int run_begin)int jilu,temp,flag,i,j;flag=0;run_jiluflag=run_begin;daoshu=0; /如果開始位置在序列中就繼續(xù)執(zhí)行，否則加入其中for( i=0;i<run_number;i+)if(run_begin=runi)break;if(i=run_number)run_number+=1;runrun_number-1=run_begin;for(i=0;i<run_number;i+)FLAG_USEDi=false;for(i=0;i<run_number;i+)if(run_begin=runi)jilu=i;break;FLAG_USEDjilu=true;/當沒走完時while(!end_not(FLAG_USED)for( j=0;j<run_number;j+) abs_LONGTHj=abs_number(run_begin,runj);for(j=0;j<run_number;j+)if(FLAG_USEDj=false)temp=abs_LONGTHj;break; for(i=0;i<run_number;i+)if(temp>abs_LONGTHi&&FLAG_USEDi=false)temp=abs_LONGTHi;for(i=0;i<run_number;i+)if(temp=abs_LONGTHi&&FLAG_USEDi=false) run_begin=runi;flag+; run_jiluflag=run_begin;FLAG_USEDi=true;break;for(flag=0;flag<run_number-1;flag+)daoshu+=abs_number(run_jiluflag+1,run_jiluflag);int main()int run_begin,as,at,i;bool flag;printf("請輸入柱面數(shù):");scanf("%d",&run_number);printf("請輸入各道磁道數(shù)n"); for( i=0;i<run_number;i+)scanf("%d",&runi);printf("請輸入開始磁道數(shù):");scanf("%d",&run_begin);printf("請選擇尋道方式(1-電梯算法，2-最短尋道)");scanf("%d",&at);while(at!=1&&at!=2)printf("請選擇尋道方式(1-電梯算法，2-最短尋道)");scanf("%d",&at); if(at=1) printf("請輸入走向（1-上，2下）:"); scanf("%d",&as); while(as!=1&&as!=2) printf("請輸入走向（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("走道次序:"); for(i=0;i<run_number;i+) printf("%dt",run_jilui); printf("n走過總道數(shù):%dn",daoshu);system("pause");return 0;4 自我評價與總結通過這次的課程設計，我認識到要將操作系統(tǒng)這門計算機專業(yè)課學好的不易不僅僅是要把書上的基本知識學好，而且還要不斷進行實踐，將所學與實踐操作結合起來才能更好地鞏固所學，才能提高自己實踐能力?？梢哉f，此課程設計的理論難度并不大，但是若要增強程序的健壯性并且實際去編程實現(xiàn)，就遇到了相當大的難度。例如測試中提到的對int型數(shù)據(jù)的非法輸入的報錯等，都是可以改進的部分，為此也翻閱過資料，網(wǎng)絡上提供的修改方案是利用while（！cin>>total）實現(xiàn)報錯，但在VC+6.0環(huán)境中不能運行，故還是沒有解決。總的說來，與之涉及的很多方面并沒有學過，自己還需要去自學和實踐檢驗。所以在以后的學習中一方面我要不斷的鞏固自己所學的理論知識，一方面還要多參加實際操作工作以便提高自己的實際操作能力。本科生課程設計成績評定表序號評分項目滿分實得分1學習態(tài)度認真、遵守紀律102設計分析合理性103設計方案正確性、可行性、創(chuàng)造性204設計結果正確性405設計報告的規(guī)范性106設計驗收10總得分/等級評語：注：最終成績以五級分制記。優(yōu)（90-100分）、良（80-89分）、中（70-79分）、及格（60-69分）、60分以下為不及格指導教師簽名： 2013 年 1月15 日