操作系統(tǒng)實驗磁盤調(diào)度掃描算法循環(huán)掃描算法

1、學(xué)號 P1514032 專業(yè)計算機(jī)科學(xué)與技術(shù)姓名實驗日期 2017.12.7教師簽字 成績實驗名稱】磁盤調(diào)度（二）【實驗?zāi)康摹看疟P調(diào)度中尋道時間直接影響到數(shù)據(jù)訪問的快慢，處理好磁盤尋道時間是關(guān)鍵。分別 米用掃描策略、循環(huán)掃描策略處理?！緦嶒炘怼?. 掃描算法（SCAh算法）SCAN算法，也就是很形象的電梯調(diào)度算法。先按照一個方向（比如從外向內(nèi)掃描）, 掃描的過程中依次調(diào)度經(jīng)過的磁道。當(dāng)掃描到最里層的一個磁道時反向掃描直至所有磁 道都被調(diào)度。2. 循環(huán)掃描算法（CSCAI算法）CSCAN算法，循環(huán)掃描算法，它的思想是，訪問完最里面一個要求服務(wù)的序列之后， 從最外層的序號開始往里走。也就是始終保

2、持一個方向，故稱為循環(huán)掃描算法?！緮?shù)據(jù)結(jié)構(gòu)和符號說明】（1）數(shù)據(jù)結(jié)構(gòu)和符號說明編譯語言： C+數(shù)據(jù)結(jié)構(gòu)：結(jié)構(gòu)體數(shù)組符號定義：typedef struct Track/ 磁道結(jié)構(gòu)體int id;/磁道序列int state=0;/是否訪問過，未被訪問置狀態(tài)為 0 Track;Track trackN;/最大磁道數(shù)為 100Track track1N;/復(fù)制的磁道數(shù)組用于輸出int stepN;/ 移動距離int num,i,current_track,num1; / 當(dāng)前磁道即部分中間變量 函數(shù)說明：void init()/ 初始化程序void input()/ 輸入函數(shù)void sort1()

3、/ 從小到大排序int abs(int a,int b)/相減的絕對值int find_first_bignum()/ 尋找第一個最大值int find_first_smallnum()/ 尋找第一個最小值void SCAN(int up_or_down) / 掃描算法 void CSCAN(int up_or_down) / 循環(huán)掃描算法void output(Track a)/ 輸出函數(shù)void output_average_track()/ 輸出平均尋道時間int show()/ 顯示用戶界面 / 返回值為輸入的選擇項 流程圖：SCAN算 法：CSCAI算法(與SCAN算法基本類似)：代

4、碼：#include#define N 100typedef struct Trackint id;/ 磁道序列int state=0;/ 是否訪問過，未被訪問置狀態(tài)為 0 Track;Track trackN;/ 最大磁道數(shù)為 100Track track1N;int stepN;/ 移動距離int num,i,current_track,num1;void init()/ 初始化程序num=0;for (i=0; inum; i+)tracki.state=-1;/id 置為 1track1i.state=-1;stepi=-1;/ 移動距離為 -1void input()/ 輸入函數(shù)pr

5、intf（ 輸入當(dāng)前磁道 n）;scanf(%d,¤t_track);num1=current_track;printf( 輸入要訪問的磁道數(shù)目 n);scanf(%d,&num);printf( 輸入要訪問磁道序列 n);for(i=0; inum; i+)scanf(%d,&tracki.id);void FCFS()/ 先來先服務(wù)for(i=0; inum; i+)求移動距離取絕對值if(current_track-tracki.id)0?a-b:b-a;int Serch_min_pos()/ 尋找到當(dāng)前磁道最短的需求磁道int min=45536;/ 最小距離標(biāo)志int

6、pos;for(int i=0; iabs(tracki.id,current_track)/min=abs(tracki.id,current_track);pos=i;trackpos.state=1;return pos;/ 返回在數(shù)組中的位置void SSTF()/ 最短尋道優(yōu)先for(i=0; inum; i+)/ 計數(shù)器track1i=trackSerch_min_pos();/ 更新到要輸出的數(shù)組中 stepi=abs(track1i.id,current_track);/ 移動距離 current_track= track1i.id;/ 標(biāo)志printf(nnn,numl);p

7、rintf(=n);/ 排班 printf( 被訪問的下一個磁道 tt 移動距離(磁道數(shù)) n);for(i=0; inum; i+)printf(t%4dtt|t%4dn,ai.id,stepi);printf(=n); void output_average_track()/ 輸出平均尋道時間double sum=0;/ 和for(i=0; inum; i+)printf(sum+=stepi;平均尋道長度 %3.2fnnn,sum/num);/ 輸出int show()/ 顯示用戶界面int choose;/ 選擇printf(n*早期的磁盤調(diào)度算法*n);printf(tt1 、先來先

8、服務(wù) (FCFS)n);printf(tt2、最短尋道時間優(yōu)先( SSTF)n);printf(tt3、退出( EXIT) n);scanf(%d,&choose);return choose;int main()doinit();case 1:/FCFSinput();FCFS();output(track);output_average_track();break;case 2:/ 最短尋道input();SSTF();output(track1);output_average_track();break;case 3:/ 退出return 0;default:break;while(1)

9、;return 0;截圖：主界面開始，輸入選擇先來先服務(wù)還是最短尋道優(yōu)先， 輸入當(dāng)前磁道， 輸入要訪問的磁道， 輸入要訪問的磁道序列。SCAN算法輸入 當(dāng)前磁道 100 ,9 個磁道，分別為 55 58 39 18 90 160 150 38 184 ，此時選擇方 向向上結(jié)果正確。輸入 當(dāng)前磁道 100 ,9 個磁道，分別為 55 58 39 18 90 160 150 38 184 ，此時選擇方 向向下結(jié)果正確。CSCAI算法輸入 當(dāng)前磁道 100 ,9 個磁道，分別為 55 58 39 18 90 160 150 38 184 ，此時選擇方 向向上結(jié)果正確。輸入 當(dāng)前磁道 100 ,9 個

10、磁道，分別為 55 58 39 18 90 160 150 38 184 ，此時選擇方 向向上結(jié)果正確?！拘〗Y(jié)與討論】1、掃描算法又稱為電梯算法，其原理與電梯運行情況相似，即運行方向上的請求優(yōu)先，若 是訪問方向向上，則先依次訪問較大的磁道號至頂，再向下訪問嬌小的磁道號；若是訪問 方向向下，則先依次訪問較小的磁道號至底，再向上訪問嬌大的磁道號。2、循環(huán)掃描算法又稱為單向電梯算法，若是訪問方向向上，則向上依次訪問完較大的磁道 號后，返回最低端，依次向上訪問較小的磁道號；若是訪問方向向下，則向下依次訪問完 較小的磁道號后，返回最頂端，依次向下訪問較大的磁道號。3、此次實驗我用兩個數(shù)組分別存放了一個磁道表和復(fù)制的磁道表，根據(jù)兩個算法的原理， 只要將其進(jìn)行排序，然后分別對兩個數(shù)組進(jìn)行正向和逆向的訪問即可。4、具體實現(xiàn)時，我將兩種算法的兩種初始掃描方向?qū)懺诹艘粋€函數(shù)之中，調(diào)用時通過參數(shù) scan 和參數(shù) up_or_down 設(shè)置。并設(shè)置了尋找大于當(dāng)前數(shù)組的最近最小值和最近的大值進(jìn) 行選擇結(jié)果，這是因為初始磁道號將磁道數(shù)組分成上下（高低地址）兩塊，這兩塊根據(jù)不 同的掃描方向重新選擇高低地址，又結(jié)合不同的算