操作系統(tǒng)實(shí)驗(yàn)磁盤調(diào)度掃描算法循環(huán)掃描算法（干貨分享）

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

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

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

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

5、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 pos; for(int i=0; iabs

6、(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+)/計(jì)數(shù)器 track1i=trackSerch_min_pos();/更新到要輸出的數(shù)組中 stepi=abs(track1i.id,current_track);/移動(dòng)距離 current_track= track1i.id;/標(biāo)志 void output(Track a)/輸出函數(shù) printf

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

8、intf(tt1、先來先服務(wù)(FCFS)n); printf(tt2、最短尋道時(shí)間優(yōu)先（SSTF)n); printf(tt3、退出（EXIT）n); scanf(%d,&choose); return choose;int main() do init(); switch(show()/返回值是選擇 case 1:/FCFS input(); FCFS(); output(track); output_average_track(); break; case 2:/最短尋道 input(); SSTF(); output(track1); output_average_track(); br

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

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