1、西安文理學院軟件學院 課程設計報告西安文理學院軟件學院課程設計報告設計名稱： 計算機操作系統課程設計 設計題目： 磁盤調度算法 學生學號： 140210112 專業班級： 12級軟件四班 學生姓名： 高 孟 學生成績： 指導教師（職稱）： 孫少波（副教授） 課題工作時間： 2014.10.27 至 2014.12.7 目錄第一章 課題概述31.1課程設計的目的31.2課程設計的要求4第二章 設計簡介及設計方案論述42.1 設計思路與方案4第三章 詳細設計53.1先來先服務算法（FCFS）53.1.1先來先服務算法說明53.1.2先來先服務算法流程圖63.1.3先來先服務算法數據結構63.2最短

2、尋道時間優先算法（SSTF）73.2.1最短尋道時間優先算法說明73.2.2最短尋道時間優先算法流程圖83.2.3最短尋道時間優先算法數據結構83.3掃描算法（SCAN）103.3.1掃描算法說明103.3.2掃描算法流程圖113.3.3掃描算法數據結構113.4循環掃描算法（CSCAN）133.4.1循環掃描算法說明133.4.2循環掃描算法流程圖143.4.3循環掃描算法數據結構14第四章 設計結果及分析174.1先來先服務算法調試結果174.2最短尋道時間算法調試結果174.3掃描算法調試結果184.4循環掃描算法調試結果18總結19參考文獻20附錄：磁盤調度算法源程序21第一章 課題概

3、述1.1課程設計的目的通過設計一個磁盤調度模擬系統，從而使磁盤調度算法更加形象化，容易使人理解，使磁盤調度的特點更簡單明了，加深對先來先服務算法（FCFS）、最短尋道時間優先算法（SSTF）、掃描算法（SCAN）及循環掃描算法（CSCAN）等磁盤調度算法的理解。1.2課程設計的要求編程序實現下述磁盤調度算法，并求出每種算法的平均尋道長度：要求設計主界面可以靈活選擇算法，且以下算法都要實現。（1） 先來先服務算法（FCFS）（2） 最短尋道時間優先算法（SSTF）（3） 掃描算法（SCAN）（4） 循環掃描算法（CSCAN）第二章 設計簡介及設計方案論述2.1 設計思路與方案 磁盤調度算法主要包

4、括四種算法，先來先服務算法（FCFS）、最短尋道時間優先算法（SSTF）、掃描算法（SCAN）、循環掃描算法（CSCAN）。 1.先來先服務算法（FCFS）： 輸入磁道號，按先來先服務的策略輸出磁盤請求序列，求平均尋道長度，輸出移動平均磁道數。 2.最短尋道時間優先算法（SSTF）：磁道號用冒泡法從小到大排序，輸出排好序的磁道序列，輸入當前磁道號，根據當前磁道在已排的序列中的位置，選擇掃描的順序，求出平均尋道長度，輸出移動的平均磁道數。 3.掃描算法（SCAN）：將磁道號用冒泡法從小到大排序，輸出排好序的序列，輸入當前磁道號，選擇移動臂的移動方向，根據當前磁道在已排的序列中的位置，選擇掃描的順

5、序，求出平均尋道長度，輸出移動的平均磁道數。 4.循環掃描算法（CSCAN）：將磁道號用冒泡法從小到大排序，輸出排好序的序列，輸入當前磁道號，規定移動臂單向反復的從內向外移動，根據當前磁道在已排的序列中的位置，選擇掃描的順序，求出平均尋道長度，輸出移動的平均磁道數。第三章 詳細設計3.1先來先服務算法（FCFS）3.1.1先來先服務算法說明這是一種比較簡單的磁盤調度算法。它根據進程請求訪問磁盤的先后次序進行調度。此算法的優點是公平、簡單，且每個進程的請求都能依次得到處理，不會出現某一進程的請求長期得不到滿足的情況。此算法由于未對尋道進行優化，在對磁盤的訪問請求比較多的情況下，此算法將降低設備服

6、務的吞吐量，致使平均尋道時間可能較長，但各進程得到服務的響應時間的變化幅度較小。3.1.2先來先服務算法流程圖圖3-1-2 先來先服務算法流程圖3.1.3先來先服務算法數據結構輸入磁道號，按先來先服務的策略輸出磁盤請求序列，求平均尋道長度，輸出移動平均磁道數。主要代碼：for(i=0;i<m;i+)/輸出FCFS磁盤調度結果printf("%d ",arrayi);for(i=0,j=1;j<m;i+,j+)sum+=abs(arrayj-arrayi);/累計總的移動距離,abs函數取絕對值avg=sum/m;/計算平均尋道長度printf("n 平

7、均尋道長度： %d n",avg);3.2最短尋道時間優先算法（SSTF）3.2.1最短尋道時間優先算法說明該算法選擇這樣的進程，其要求訪問的磁道與當前磁頭所在的磁道距離最近，以使每次的尋道時間最短，該算法可以得到比較好的吞吐量，但卻不能保證平均尋道時間最短。其缺點是對用戶的服務請求的響應機會不是均等的，因而導致響應時間的變化幅度很大。在服務請求很多的情況下，對內外邊緣磁道的請求將會無限期的被延遲，有些請求的響應時間將不可預期。3.2.2最短尋道時間優先算法流程圖圖3-2-2 最短尋道時間優先算法流程圖3.2.3最短尋道時間優先算法數據結構將磁道號用冒泡法從小到大排序，輸出排好序的磁

8、道序列，輸入當前磁道號，根據前磁道在已排的序列中的位置，選擇掃描的順序，求出平均尋道長度，輸出移動的平均磁道數。主要代碼：for(i=0;i<m;i+)for(j=i+1;j<m;j+)/對磁道號進行從小到大排列if(arrayi>arrayj)/兩磁道號之間比較temp=arrayi;arrayi=arrayj;arrayj=temp;printf(" 排序后磁道順序為：");for( i=0;i<m;i+)/輸出排序后的磁道號數組printf("%d ",arrayi);printf("n 請輸入當前的磁道號：&qu

9、ot;);scanf("%d",&now);printf("n SSTF調度結果: ");if(arraym-1<=now)/判斷整個數組里的數是否都小于當前磁道號 for(i=m-1;i>=0;i-)/將數組磁道號從大到小輸出printf("%d ",arrayi);sum=now-array0;/計算移動距離else if(array0>=now)/判斷整個數組里的數是否都大于當前磁道號 for(i=0;i<m;i+)/將磁道號從小到大輸出printf("%d ",arrayi)

10、;sum=arraym-1-now;/計算移動距離elsewhile(arrayk<now)/逐一比較以確定K值k+;l=k-1;r=k;/確定當前磁道在已排的序列中的位置while(l>=0)&&(r<m)/循環的比較，將數組分為兩段，比較最短尋道地址if(now-arrayl)<=(arrayr-now)/判斷最短距離 printf("%d ",arrayl);sum+=now-arrayl;/計算移動距離now=arrayl;l=l-1;else printf("%d ",arrayr);sum+=array

11、r-now;/計算移動距離now=arrayr;r=r+1;if(l=-1)/此時now為array0,需要到達arraym-1,即前半段掃描結束，后半段還有剩余 for(j=r;j<m;j+) printf("%d ",arrayj);sum+=arraym-1-array0;/計算移動距離else/此時now為arraym-1需要到達array0,后半段掃描結束，前半段還有剩余 for(j=l;j>=0;j-) printf("%d ",arrayj);sum+=arraym-1-array0;/計算移動距離avg=sum/m;print

12、f("n 平均尋道長度： %d n",avg);3.3掃描算法（SCAN）3.3.1掃描算法說明掃描算法不僅考慮到欲訪問的磁道與當前磁道的距離，更優先考慮的是磁頭的當前移動方向。例如，當磁頭正在自里向外移動時，掃描算法所選擇的下一個訪問對象應是其欲訪問的磁道既在當前磁道之外，又是距離最近的。這樣自里向外地訪問，直到再無更外的磁道需要訪問才將磁臂換向，自外向里移動。這時，同樣也是每次選擇這樣的進程來調度，即其要訪問的磁道，在當前磁道之內，從而避免了饑餓現象的出現。由于這種算法中磁頭移動的規律頗似電梯的運行，故又稱為電梯調度算法。此算法基本上克服了最短尋道時間優先算法的服務集中

13、于中間磁道和響應時間變化比較大的缺點，而具有最短尋道時間優先算法的優點即吞吐量較大，平均響應時間較小，但由于是擺動式的掃描方法，兩側磁道被訪問的頻率仍低于中間磁道。3.3.2掃描算法流程圖圖3-3-2 掃描算法流程圖3.3.3掃描算法數據結構將磁道號用冒泡法從小到大排序，輸出排好序的序列，輸入當前磁道號，選擇移動臂的移動方向，根據當前磁道在已排的序列中的位置，選擇掃描的順序，求出平均尋道長度，輸出移動的平均磁道數。主要代碼：for(i=0;i<m;i+)for(j=i+1;j<m;j+)if(arrayi>arrayj)/對磁道號進行從小到大排列temp=arrayi;arr

14、ayi=arrayj;arrayj=temp;printf(" 排序后磁道順序為：");for( i=0;i<m;i+)printf("%d ",arrayi);/輸出排序后的磁道號數組printf("n 請輸入當前的磁道號：");scanf("%d",&now);if(arraym-1<=now)/判斷整個數組里的數是否都小于當前磁道號 printf("n SCAN調度結果: ");for(i=m-1;i>=0;i-)printf("%d ",ar

15、rayi);/將數組磁道號從大到小輸出sum=now-array0;/計算移動距離else if(array0>=now)/判斷整個數組里的數是否都大于當前磁道號 printf("n SCAN調度結果: ");for(i=0;i<m;i+)printf("%d ",arrayi);/將磁道號從小到大輸出sum=arraym-1-now;/計算移動距離elsewhile(arrayk<now)/逐一比較以確定K值k+;l=k-1;r=k;printf("n 請輸入當前移動臂的移動的方向 (1 磁道號增加方向，0磁道號減小方向)

16、: ");scanf("%d",&d);printf("n SCAN調度結果: ");if(d=0)/磁道號減小方向<-for(j=l;j>=0;j-)printf("%d ",arrayj);for(j=r;j<m;j+)printf("%d ",arrayj);sum=now-2*array0+arraym-1;/計算移動距離/sum=2(now-array0)+arraym-1-now/根據距離算else/磁道增加方向->for(j=r;j<m;j+)print

17、f("%d ",arrayj);for(j=l;j>=0;j-)printf("%d ",arrayj);sum=-now-array0+2*arraym-1;/計算移動距離/sum=arraym-1-now+arraym-1-array0avg=sum/m;printf("n 平均尋道長度： %d n",avg);3.4循環掃描算法（CSCAN）3.4.1循環掃描算法說明 循環掃描算法是對掃描算法的改進。如果對磁道的訪問請求是均勻分布的，當磁頭到達磁盤的一端，并反向運動時落在磁頭之后的訪問請求相對較少。這是由于這些磁道剛被處理

18、，而磁盤另一端的請求密度相當高，且這些訪問請求等待的時間較長，為了解決這種情況，循環掃描算法規定磁頭單向移動。例如，只自里向外移動，當磁頭移到最外的被訪問磁道時，磁頭立即返回到最里的欲訪磁道，即將最小磁道號緊接著最大磁道號構成循環，進行掃描。3.4.2循環掃描算法流程圖圖3-4-2循環掃描算法流程圖3.4.3循環掃描算法數據結構將磁道號用冒泡法從小到大排序，輸出排好序的序列，輸入當前磁道號，規定移動臂單向反復的從內向外移動，根據當前磁道在已排的序列中的位置，選擇掃描的順序，求出平均尋道長度，輸出移動的平均磁道數。主要代碼：for(i=0;i<m;i+)for(j=i+1;j<m;j

19、+)if(arrayi>arrayj)/對磁道號進行從小到大排列temp=arrayi;arrayi=arrayj;arrayj=temp;printf(" 排序后磁道順序為：");for( i=0;i<m;i+)printf("%d ",arrayi);/輸出排序后的磁道號數組printf("n 請輸入當前的磁道號：");scanf("%d",&now);if(arraym-1<=now)/判斷整個數組里的數是否都小于當前磁道號 printf("n CSCAN調度結果: &qu

20、ot;);for(i=0;i<m;i+) printf("%d ",arrayi);/將磁道號從小到大輸出sum=now-array0+arraym-1;/計算移動距離else if(array0>=now)/判斷整個數組里的數是否都大于當前磁道號 printf("n CSCAN調度結果: ");for(i=0;i<m;i+) printf("%d ",arrayi);/將磁道號從小到大輸出sum=arraym-1-now;/計算移動距離elsewhile(arrayk<now)/逐一比較以確定K值k+;l=k

21、-1;r=k;printf("n 請輸入當前移動臂的移動的方向 (1 磁道號增加方向，0磁道號減小方向) : ");scanf("%d",&d);printf("n CSCAN調度結果: ");if(d=0)/<-for(j=l;j>=0;j-)printf("%d ",arrayj);for(j=m-1;j>=r;j-)printf("%d ",arrayj);sum=2*(arraym-1-array0)-arrayr+now;/計算移動距離/sum=now-arr

22、ay0+arraym-1-array0+arraym-1-arrayr 先<-再<-循環到尾再<-/磁道號減小方向elsefor(j=r;j<m;j+)printf("%d ",arrayj); for(j=0;j<r;j+)printf("%d ",arrayj);sum=2*(arraym-1-array0)+arrayr-1-now;/計算移動距離/sum=arraym-1-now+arraym-1-array0+arrayr-1-array0/先->再循環到尾->再->/磁道號增加方向avg=sum

23、/m;printf("n 平均尋道長度： %d n",avg);第四章 設計結果及分析4.1先來先服務算法調試結果圖4-1 先來先服務算法調試結果4.2最短尋道時間算法調試結果圖4-2 最短尋道時間算法調試結果4.3掃描算法調試結果圖4-3 掃描算法調試結果4.4循環掃描算法調試結果圖4-4 循環掃描算法調試結果總結 通過幾周的課程設計，使我深刻體會到了：只要你想做只要你想學沒有弄不懂得事情，工程里面也不能不在乎細節等等。這次操作系統課程設計，感覺很受益匪淺。懂得了操作系統磁盤調度的四種算法：先來先服務算法（FCFS）、最短尋道時間優先算法（SSTF）、掃描算法（SCAN）

24、和循環掃描算法（CSCAN）。加深了我對這門課程的理解。鍛煉了自己在考慮全局和細節的能力。通過這次實驗，再一次熟悉并深入掌握了程序設計語言和算法設計。 本次課程設計還培養了我們獨立思考的能力，提高了我們的動手操作水平。在具體設計操作中，我們鞏固了本學期所學的數據結構與算法的理論知識，進一步提高了自己的編程能力。這也是課程設計的最終目的所在。通過實際操作，開發了自己的邏輯思維能力，培養了分析問題、解決問題的能力。 但在程序設計的過程中我也深刻的感受到自己實力的不足，無法靈活的運用各種工具和函數，對于課程所講的東西也無法在脫離課本的情況中完成，我意識到自己在今后的學習生活中，一定要勤于思考，扎實掌

25、握理論知識，靈活運用課上所學的東西，做一個優秀的程序員。參考文獻1湯小丹，梁紅兵.計算機操作系統M，西安：西安電子科技大學出版社，2007.2何欽銘，顏暉.C語言程序設計M，北京：高等教育出版社，2008.3嚴蔚敏，吳偉民.數據結構（C語言版）M，北京：清華大學出版社，2011.附錄：磁盤調度算法源程序#include"stdio.h"#include"stdlib.h"#define maxsize 5 /定義最大數組域#include<windows.h>/先來先服務調度算法void FCFS(int array,int m)int su

26、m=0,j,i;int avg;printf("n FCFS調度結果: ");for(i=0;i<m;i+)/輸出FCFS磁盤調度結果printf("%d ",arrayi);for(i=0,j=1;j<m;i+,j+)sum+=abs(arrayj-arrayi);/累計總的移動距離,abs函數取絕對值avg=sum/m;/計算平均尋道長度printf("n 平均尋道長度： %d n",avg);/最短尋道時間優先調度算法void SSTF(int array,int m)int temp;int k=1;int now

27、,l,r;int i,j,sum=0;int avg;for(i=0;i<m;i+)for(j=i+1;j<m;j+)/對磁道號進行從小到大排列if(arrayi>arrayj)/兩磁道號之間比較temp=arrayi;arrayi=arrayj;arrayj=temp;printf(" 排序后磁道順序為：");for( i=0;i<m;i+)/輸出排序后的磁道號數組printf("%d ",arrayi);printf("n 請輸入當前的磁道號：");scanf("%d",&now

28、);printf("n SSTF調度結果: ");if(arraym-1<=now)/判斷整個數組里的數是否都小于當前磁道號 for(i=m-1;i>=0;i-)/將數組磁道號從大到小輸出printf("%d ",arrayi);sum=now-array0;/計算移動距離else if(array0>=now)/判斷整個數組里的數是否都大于當前磁道號 for(i=0;i<m;i+)/將磁道號從小到大輸出printf("%d ",arrayi);sum=arraym-1-now;/計算移動距離elsewhile

29、(arrayk<now)/逐一比較以確定K值k+;l=k-1;r=k;/確定當前磁道在已排的序列中的位置while(l>=0)&&(r<m)/循環的比較，將數組分為兩段，比較最短尋道地址if(now-arrayl)<=(arrayr-now)/判斷最短距離 printf("%d ",arrayl);sum+=now-arrayl;/計算移動距離now=arrayl;l=l-1;else printf("%d ",arrayr);sum+=arrayr-now;/計算移動距離now=arrayr;r=r+1;if(l

30、=-1)/此時now為array0,需要到達arraym-1,即前半段掃描結束，后半段還有剩余 for(j=r;j<m;j+) printf("%d ",arrayj);sum+=arraym-1-array0;/計算移動距離else/此時now為arraym-1需要到達array0,后半段掃描結束，前半段還有剩余 for(j=l;j>=0;j-) printf("%d ",arrayj);sum+=arraym-1-array0;/計算移動距離avg=sum/m;printf("n 平均尋道長度： %d n",avg);

31、/掃描算法void SCAN(int array,int m)/先要給出當前磁道號和移動臂的移動方向,到了端點時磁臂到另一端點int temp;int k=1;int now,l,r,d;int i,j,sum=0;int avg;for(i=0;i<m;i+)for(j=i+1;j<m;j+)if(arrayi>arrayj)/對磁道號進行從小到大排列temp=arrayi;arrayi=arrayj;arrayj=temp;printf(" 排序后磁道順序為：");for( i=0;i<m;i+)printf("%d ",ar

32、rayi);/輸出排序后的磁道號數組printf("n 請輸入當前的磁道號：");scanf("%d",&now);if(arraym-1<=now)/判斷整個數組里的數是否都小于當前磁道號 printf("n SCAN調度結果: ");for(i=m-1;i>=0;i-)printf("%d ",arrayi);/將數組磁道號從大到小輸出sum=now-array0;/計算移動距離else if(array0>=now)/判斷整個數組里的數是否都大于當前磁道號 printf("

33、n SCAN調度結果: ");for(i=0;i<m;i+)printf("%d ",arrayi);/將磁道號從小到大輸出sum=arraym-1-now;/計算移動距離elsewhile(arrayk<now)/逐一比較以確定K值k+;l=k-1;r=k;printf("n 請輸入當前移動臂的移動的方向 (1 磁道號增加方向，0磁道號減小方向) : ");scanf("%d",&d);printf("n SCAN調度結果: ");if(d=0)/磁道號減小方向<-for(j=

34、l;j>=0;j-)printf("%d ",arrayj);for(j=r;j<m;j+)printf("%d ",arrayj);sum=now-2*array0+arraym-1;/計算移動距離/sum=2(now-array0)+arraym-1-now/根據距離算else/磁道增加方向->for(j=r;j<m;j+)printf("%d ",arrayj);for(j=l;j>=0;j-)printf("%d ",arrayj);sum=-now-array0+2*arra

35、ym-1;/計算移動距離/sum=arraym-1-now+arraym-1-array0avg=sum/m;printf("n 平均尋道長度： %d n",avg);/循環掃描算法void CSCAN(int array,int m)int temp;int k=1;int now,l,r,d;int i,j,sum=0;int avg;for(i=0;i<m;i+)for(j=i+1;j<m;j+)if(arrayi>arrayj)/對磁道號進行從小到大排列temp=arrayi;arrayi=arrayj;arrayj=temp;printf(&qu

36、ot; 排序后磁道順序為：");for( i=0;i<m;i+)printf("%d ",arrayi);/輸出排序后的磁道號數組printf("n 請輸入當前的磁道號：");scanf("%d",&now);if(arraym-1<=now)/判斷整個數組里的數是否都小于當前磁道號 printf("n CSCAN調度結果: ");for(i=0;i<m;i+) printf("%d ",arrayi);/將磁道號從小到大輸出sum=now-array0+ar

37、raym-1;/計算移動距離else if(array0>=now)/判斷整個數組里的數是否都大于當前磁道號 printf("n CSCAN調度結果: ");for(i=0;i<m;i+) printf("%d ",arrayi);/將磁道號從小到大輸出sum=arraym-1-now;/計算移動距離elsewhile(arrayk<now)/逐一比較以確定K值k+;l=k-1;r=k;printf("n 請輸入當前移動臂的移動的方向 (1 磁道號增加方向，0磁道號減小方向) : ");scanf("%d&

38、quot;,&d);printf("n CSCAN調度結果: ");if(d=0)/<-for(j=l;j>=0;j-)printf("%d ",arrayj);for(j=m-1;j>=r;j-)printf("%d ",arrayj);sum=2*(arraym-1-array0)-arrayr+now;/計算移動距離/sum=now-array0+arraym-1-array0+arraym-1-arrayr 先<-再<-循環到尾再<-/磁道號減小方向elsefor(j=r;j<m;j+)printf("%d ",arrayj); for(j=0;j<r;j+)printf("%d ",arrayj);sum=2*(arraym-1-array0)+arrayr-1-now;/計算移