1、哈爾濱理工大學課程設計（操作系統）題目： N-Step-SCAN 磁盤調度 班級： 計算機科學與技術學院 計算機系10-8班姓名：唐 楷 航 指導教師：高 雪 瑤系主任： 林克正 2013年03月01日目 錄1N-Step-SCAN 磁盤調度課程設計1.1 題目分析11.2 數據結構11.3 流程圖11.4 實現技術21.5 設計結論和心得22 Linux代碼分析42.1 功能說明182.2 接口說明.182.3 局部數據結構.202.4 流程圖.21 2.5 以實例說明運行過程.22第1章 2.5 以實例說明運行過程51N-Step-SCAN磁盤調度課程設計1.1 題目分析當有一個或者幾個進

2、程對某一磁道有較高的訪問頻率，即這些進程反復請求對某一磁道的I/O操作，從而壟斷整個磁盤設備。在高密度的磁盤上容易出現此情況。N步SCAN算法是將磁道請求隊列若干個長度為N的子隊列。而每處理一個隊列時又是按SCAN算法，對一個隊列處理完后，再處理其他隊列。1.2 數據結構N-Step-SCAN磁盤調度中涉及的數據結構包括N個隊列、隊列緩沖區、表示空緩沖區的信號量、表示滿緩沖區的信號量等。用偽代碼表示如下：#includestdio.h#includestdlib.h/#includeiostream.h#define maxsize 100 /定義最大數組域int now,s;void SST

3、F(int array,int m)int temp;int k=1;int now,l,r; /當前磁道號now；找出的當前磁道左側的磁道l，右側的磁道rint i,j,sum=0;int avg;for(i=0;im;i+)for(j=i+1;jarrayj)/兩磁道號之間比較temp=arrayi;arrayi=arrayj;arrayj=temp;for( i=0;im;i+)/輸出排序后的磁道號數組printf(%d ,arrayi);printf(n 請輸入當前的磁道號：);scanf(%d,&now);printf(n SSTF調度結果: );if(arraym-1=0;i-)/

4、將數組磁道號從大到小輸出printf(%d ,arrayi);sum=now-array0;/計算移動距離else if(array0=now)/判斷整個數組里的數是否都大于當前磁道號 for(i=0;im;i+)/將磁道號從小到大輸出printf(%d ,arrayi);sum=arraym-1-now;/計算移動距離elsewhile(arrayk=0)&(rm)if(now-arrayl)=(arrayr-now)/判斷最短距離 printf(%d ,arrayl);sum+=now-arrayl;/計算移動距離now=arrayl;l=l-1;else printf(%d ,array

5、r);sum+=arrayr-now;/計算移動距離now=arrayr;r=r+1;if(l=-1) for(j=r;j=0;j-) printf(%d ,arrayj);sum+=arraym-1-array0;/計算移動距離avg=sum/m;printf(n 移動的總道數： %d n,sum);printf( 平均尋道長度： %d n,avg);void SCAN(int array,int m,int d)/先要給出當前磁道號和移動臂的移動方向int k=1;int l,r;int i,j,sum=0;int avg;int temp; /用于排序的臨時參數int q; for(i=

6、0;im;i+)for(j=i+1;jarrayj)/對磁道號進行從小到大排列temp=arrayi;arrayi=arrayj;arrayj=temp; if(arraym-1=0;i-)printf(%d ,arrayi);/將數組磁道號從大到小輸出 q=arrayi;sum=now-q;/計算移動距離s=s+sum;now=q;else if(array0=now)/判斷整個數組里的數是否都大于當前磁道號 printf(n SCAN調度結果: );for(i=0;im;i+)printf(%d ,arrayi);/將磁道號從小到大輸出 q=arrayi;sum=arraym-1-now;

7、/計算移動距離 s=s+sum;now=q;elsewhile(arrayk=0;j-)printf(%d ,arrayj); q=arrayj;for(j=r;jm;j+)printf(%d ,arrayj); q=arrayj;sum=now-2*array0+arraym-1;/計算移動距離 s=s+sum;now=q;/磁道號減小方向elsefor(j=r;j=0;j-)printf(%d ,arrayj); q=arrayj;sum=-now-array0+2*arraym-1;/計算移動距離 s=s+sum;now=q;/磁道號增加方向avg=sum/m;printf(n 該子隊列

8、移動的總道數： %d n,sum);printf( 該子隊列平均尋道長度： %d n,avg);void NStepSCAN(int array,int m) int sn,N,d; /sn標記每一子隊列的長度，N記錄子隊列個數，now標記當前磁道號int b100,c100; /b100儲存前幾個子隊列，c100儲存最后一個子隊列int i=0,j=0,k=0,n=1;int ave; printf(請輸入當前磁道號：n);scanf(%d,&now);printf(請輸入子隊列的個數：n);scanf(%d,&N);while(Nm)printf(超出范圍，文件中的磁道數不夠分組，請重新輸

9、入：n); scanf(%d,&N); printf(請輸入當前移動臂的移動的方向 (1 磁道號增加方向，0磁道號減小方向) : );scanf(%d,&d); sn=m/N; while(N!=1) /當不是最后一個子隊列時，循環進行SCAN調度j=0;for(i=k;isn*n;i=k,j+)bj=arrayi;k=k+1; printf(n第%d個隊列的排序結果為：n,n); SCAN(b,sn,d);N=N-1;n=n+1; if(N=1) /最后一個子隊列時進行SCAN調度for(i=k,j=0;im;i+,j+)cj=arrayi; printf(n最后一個隊列的調度結果為：n);

10、 SCAN(c,m-k,d);ave=s/m;printf(n該調度總的結果為：n);printf(n 移動的總道數： %d n,s);printf( 平均尋道長度： %d n,ave); int main()int c;int C=1;FILE *fp;/定義指針文件int cidaomaxsize;/定義磁道號數組int i=0,count;fp=fopen(cidao.txt,r+);/讀取cidao.txt文件if(fp=NULL)/判斷文件是否存在printf(n 請 先 設 置 磁 道! n);exit(0);while(!feof(fp)/如果磁道文件存在fscanf(fp,%d

11、,&cidaoi);/調入磁道號i+;count=i;printf(n -n);printf( 磁盤調度算法模擬);printf(n -n); printf(n 磁道讀取結果：n);for(i=0;icount;i+)printf(%5d,cidaoi);/輸出讀取的磁道的磁道號printf(n );while(C=1) printf( 操作系統課程設計 n); printf( 磁盤調度算法 n ); printf( 1.返回 n); printf( 2.N步掃描算法(NStepScan) n); printf( 請輸入你的選擇的算法(輸入0離開) n); scanf(%d,&c); if(c

12、=0) exit(0); printf( );while(c!=1&c!=2)printf(輸入數據超出范圍，請重新輸入您想進行的調度算法：n); scanf(%d,&c);switch(c) case 1: SSTF(cidao,count);/最短尋道時間優先算法 printf(n); break; case 2:i=0; fp=fopen(cidao.txt,r+);/讀取cidao.txt文件 if(fp=NULL)/判斷文件是否存在printf(n 請 先 設 置 磁 道! n); exit(0); while(!feof(fp)/如果磁道文件存在 fscanf(fp,%d,&cid

13、aoi);/調入磁道號 i+; count=i; printf(n 磁道讀取結果：n); for(i=0;icount;i+) printf(%5d,cidaoi);/輸出讀取的磁道的磁道號 printf(n );NStepSCAN(cidao,count);/N步掃描算法 printf(n); break;printf( 是否繼續(按0結束,按1繼續)?);scanf(%5d,&C);return(0);1.3 流程圖將磁道號從小到大排序arraym-1=0(array0=now輸出磁盤調度序列arrayjim磁頭移動總距離sum=arrayi-now確定當前磁道在已排的序列中的位置swit

14、ch(d)case 0:移動臂向磁道號減小方向訪問case 1:移動臂向磁道號增加方向訪問訪問輸出磁盤調度序列輸出磁盤調度序列輸出子隊列尋道總道數sum輸出子隊列平均尋道長度avg=sum/(m) 流程圖1.4 實現技術為實現上述設計，采用C+語言，VS2008開發環境。運行結果如下：1.5 設計結論和心得通過課程設計得到如下結論：在N步掃描算法中，還出現了這樣一個問題。就是，在對磁道號進行分組時，最后一列的處理問題。在開始時由于籠統地進行了平均分組，而沒有考慮無法完全分盡的情況，進而導致最后一個甚至一些磁道號丟失的問題。不過最后，在單列最后一組后（即將最后一組與前面各組分開后）問題得到了解決

15、。將余下的一個或一些磁道號全部加至最后一列末尾，很好地處理了數據丟失問題有如下幾點心得體會：通過這次的課程設計使我認識到要將操作系統這門計算機專業的課學好不僅僅是要把書上的基本知識學好而且還要不斷進行實踐，將所學的跟實踐操作結合起來才能更好地鞏固所學，才能提高自己實踐能力.通過這次的設計使我認識到只停留在表面理解問題是很難使問題得到很好的解決的，實踐能力與理論知識同樣重要?？梢哉f此課程設計的理論難度并不大，但是若要深入發掘其中的東西，并且實際去編程實現，就遇到了相當大的難度。因為與之涉及的很多方面并沒有學過，需要自己去自學和實踐檢驗。通過模擬磁盤調度及進程排隊算法來加深對操作系統中各個磁臂調度

16、算法概念的理解。模擬磁盤調度算法(SSTF,NstepSCAN)，實現各種不同調度算法的過程，并計算各算法的平均尋道長度，以便于我們判斷各種算法的優劣以及各種算法使用的場合。2 Linux代碼分析為了進一步了解操作系統內核，學習了Linux操作系統的進程同步程序，主要程序源代碼如下：#!/bin/sh # Author: Guo Wenxue() # Date: Wen Mar 5 17:56:44 CST 2013 # Version: 1.0.0 # Description: This shell script used to format all th

17、e source code in current forlder # and convert source code file format from windows to linux find -iname *.c -exec dos2unix ; find -iname *.h -exec dos2unix ; find -iname makefile -exec dos2unix ; find -iname Makefile -exec dos2unix ;# -npro 不要讀取indent的配置文件. # -kr 使用Kernighan&Ritchie的格式 #

18、-i4 設置縮排的格數為4 # -di28 將聲明區段的變量置于指定的欄位(28) # -ts4 設置tab的長度為4 # -bls 定義結構，struct和分行 # -bl if(或是else,for等等)與后面執行區段的”“不同行，且”自成一行。 # -bli0 設置 縮排的格數為0 # -cli2 使用case時，switch縮排的格數 # -ss 若for或whiile區段只有一行時，在分號前加上空格 # -bad 在聲明區段后加上空白行 # -bbb 塊注釋前加空行 # -bap 函數結束后加空行 # -sc 在每行注釋左側加上星號(*)。 # -bc 在聲明區段中，若出現逗號即換行

19、。 # -sob 刪除多余的空白行 # -l100 非注釋行最長100 # -ncs 不要在類型轉換后面加空格 # -nce 不要將else置于”之后 # -nut 不要使用tab來縮進 INDET_FORMAT=-npro -kr -i4 -ts4 -bls -bl -bli0 -cli2 -ss -bap -sc -sob -l100 -ncs -nce -nut find -iname *.c -exec indent $INDET_FORMAT ; find -iname *.h -exec indent $INDET_FORMAT ; find -iname *.h | xargs rm -rf ;2.1 功能說明這一段程序的主要功能為：（1）在 /usr/sbin/目錄下創建format_sg文件（2）更改其屬性為7772.2 接口說明本程序的輸入參數為：INDET_FORMAT=-npro -kr -i4 -ts4 -bls -bl -bli0 -cli2 -ss -bap -sc -sob -l100 -ncs -nce -nut 2.3 局部數據結構本程序