N-Step-SCAN-磁盤(pán)調(diào)度-操作系統(tǒng)課程設(shè)計(jì)

1、哈爾濱理工大學(xué)課程設(shè)計(jì)（操作系統(tǒng)）題目： N-Step-SCAN 磁盤(pán)調(diào)度 班級(jí)： 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 計(jì)算機(jī)系10-8班姓名：唐 楷 航 指導(dǎo)教師：高 雪 瑤系主任： 林克正 2013年03月01日目 錄1N-Step-SCAN 磁盤(pán)調(diào)度課程設(shè)計(jì)1.1 題目分析11.2 數(shù)據(jù)結(jié)構(gòu)11.3 流程圖11.4 實(shí)現(xiàn)技術(shù)21.5 設(shè)計(jì)結(jié)論和心得22 Linux代碼分析42.1 功能說(shuō)明182.2 接口說(shuō)明.182.3 局部數(shù)據(jù)結(jié)構(gòu).202.4 流程圖.21 2.5 以實(shí)例說(shuō)明運(yùn)行過(guò)程.22第1章 2.5 以實(shí)例說(shuō)明運(yùn)行過(guò)程51N-Step-SCAN磁盤(pán)調(diào)度課程設(shè)計(jì)1.1 題目分析當(dāng)有一個(gè)或者幾個(gè)進(jìn)

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

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

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

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

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

7、/計(jì)算移動(dòng)距離 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;/計(jì)算移動(dòng)距離 s=s+sum;now=q;/磁道號(hào)減小方向elsefor(j=r;j=0;j-)printf(%d ,arrayj); q=arrayj;sum=-now-array0+2*arraym-1;/計(jì)算移動(dòng)距離 s=s+sum;now=q;/磁道號(hào)增加方向avg=sum/m;printf(n 該子隊(duì)列

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

9、入：n); scanf(%d,&N); printf(請(qǐng)輸入當(dāng)前移動(dòng)臂的移動(dòng)的方向 (1 磁道號(hào)增加方向，0磁道號(hào)減小方向) : );scanf(%d,&d); sn=m/N; while(N!=1) /當(dāng)不是最后一個(gè)子隊(duì)列時(shí)，循環(huán)進(jìn)行SCAN調(diào)度j=0;for(i=k;isn*n;i=k,j+)bj=arrayi;k=k+1; printf(n第%d個(gè)隊(duì)列的排序結(jié)果為：n,n); SCAN(b,sn,d);N=N-1;n=n+1; if(N=1) /最后一個(gè)子隊(duì)列時(shí)進(jìn)行SCAN調(diào)度f(wàn)or(i=k,j=0;im;i+,j+)cj=arrayi; printf(n最后一個(gè)隊(duì)列的調(diào)度結(jié)果為：n);

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

11、,&cidaoi);/調(diào)入磁道號(hào)i+;count=i;printf(n -n);printf( 磁盤(pán)調(diào)度算法模擬);printf(n -n); printf(n 磁道讀取結(jié)果：n);for(i=0;icount;i+)printf(%5d,cidaoi);/輸出讀取的磁道的磁道號(hào)printf(n );while(C=1) printf( 操作系統(tǒng)課程設(shè)計(jì) n); printf( 磁盤(pán)調(diào)度算法 n ); printf( 1.返回 n); printf( 2.N步掃描算法(NStepScan) n); printf( 請(qǐng)輸入你的選擇的算法(輸入0離開(kāi)) n); scanf(%d,&c); if(c

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

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

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

15、。將余下的一個(gè)或一些磁道號(hào)全部加至最后一列末尾，很好地處理了數(shù)據(jù)丟失問(wèn)題有如下幾點(diǎn)心得體會(huì)：通過(guò)這次的課程設(shè)計(jì)使我認(rèn)識(shí)到要將操作系統(tǒng)這門(mén)計(jì)算機(jī)專業(yè)的課學(xué)好不僅僅是要把書(shū)上的基本知識(shí)學(xué)好而且還要不斷進(jìn)行實(shí)踐，將所學(xué)的跟實(shí)踐操作結(jié)合起來(lái)才能更好地鞏固所學(xué)，才能提高自己實(shí)踐能力.通過(guò)這次的設(shè)計(jì)使我認(rèn)識(shí)到只停留在表面理解問(wèn)題是很難使問(wèn)題得到很好的解決的，實(shí)踐能力與理論知識(shí)同樣重要?？梢哉f(shuō)此課程設(shè)計(jì)的理論難度并不大，但是若要深入發(fā)掘其中的東西，并且實(shí)際去編程實(shí)現(xiàn)，就遇到了相當(dāng)大的難度。因?yàn)榕c之涉及的很多方面并沒(méi)有學(xué)過(guò)，需要自己去自學(xué)和實(shí)踐檢驗(yàn)。通過(guò)模擬磁盤(pán)調(diào)度及進(jìn)程排隊(duì)算法來(lái)加深對(duì)操作系統(tǒng)中各個(gè)磁臂調(diào)度

16、算法概念的理解。模擬磁盤(pán)調(diào)度算法(SSTF,NstepSCAN)，實(shí)現(xiàn)各種不同調(diào)度算法的過(guò)程，并計(jì)算各算法的平均尋道長(zhǎng)度，以便于我們判斷各種算法的優(yōu)劣以及各種算法使用的場(chǎng)合。2 Linux代碼分析為了進(jìn)一步了解操作系統(tǒng)內(nèi)核，學(xué)習(xí)了Linux操作系統(tǒng)的進(jìn)程同步程序，主要程序源代碼如下：#!/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 設(shè)置縮排的格數(shù)為4 # -di28 將聲明區(qū)段的變量置于指定的欄位(28) # -ts4 設(shè)置tab的長(zhǎng)度為4 # -bls 定義結(jié)構(gòu)，struct和分行 # -bl if(或是else,for等等)與后面執(zhí)行區(qū)段的”“不同行，且”自成一行。 # -bli0 設(shè)置 縮排的格數(shù)為0 # -cli2 使用case時(shí)，switch縮排的格數(shù) # -ss 若for或whiile區(qū)段只有一行時(shí)，在分號(hào)前加上空格 # -bad 在聲明區(qū)段后加上空白行 # -bbb 塊注釋前加空行 # -bap 函數(shù)結(jié)束后加空行 # -sc 在每行注釋左側(cè)加上星號(hào)(*)。 # -bc 在聲明區(qū)段中，若出現(xiàn)逗號(hào)即換行

19、。 # -sob 刪除多余的空白行 # -l100 非注釋行最長(zhǎng)100 # -ncs 不要在類(lèi)型轉(zhuǎn)換后面加空格 # -nce 不要將else置于”之后 # -nut 不要使用tab來(lái)縮進(jìn) 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 功能說(shuō)明這一段程序的主要功能為：（1）在 /usr/sbin/目錄下創(chuàng)建format_sg文件（2）更改其屬性為7772.2 接口說(shuō)明本程序的輸入?yún)?shù)為：INDET_FORMAT=-npro -kr -i4 -ts4 -bls -bl -bli0 -cli2 -ss -bap -sc -sob -l100 -ncs -nce -nut 2.3 局部數(shù)據(jù)結(jié)構(gòu)本程序