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

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

2、持一個(gè)方向，故稱為循環(huán)掃描算法?！緮?shù)據(jù)結(jié)構(gòu)和符號(hào)說(shuō)明】（1）數(shù)據(jù)結(jié)構(gòu)和符號(hào)說(shuō)明編譯語(yǔ)言： C+數(shù)據(jù)結(jié)構(gòu)：結(jié)構(gòu)體數(shù)組符號(hào)定義：typedef struct Track/ 磁道結(jié)構(gòu)體int id;/磁道序列int state=0;/是否訪問(wèn)過(guò)，未被訪問(wèn)置狀態(tài)為 0 Track;Track trackN;/最大磁道數(shù)為 100Track track1N;/復(fù)制的磁道數(shù)組用于輸出int stepN;/ 移動(dòng)距離int num,i,current_track,num1; / 當(dāng)前磁道即部分中間變量 函數(shù)說(shuō)明：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算 法：CSCAI算法(與SCAN算法基本類(lèi)似)：代

4、碼：#include#define N 100typedef struct Trackint id;/ 磁道序列int state=0;/ 是否訪問(wèn)過(guò)，未被訪問(wèn)置狀態(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 置為 1track1i.state=-1;stepi=-1;/ 移動(dòng)距離為 -1void input()/ 輸入函數(shù)pr

5、intf（ 輸入當(dāng)前磁道 n）;scanf(%d,¤t_track);num1=current_track;printf( 輸入要訪問(wèn)的磁道數(shù)目 n);scanf(%d,&num);printf( 輸入要訪問(wèn)磁道序列 n);for(i=0; inum; i+)scanf(%d,&tracki.id);void FCFS()/ 先來(lái)先服務(wù)for(i=0; inum; i+)求移動(dòng)距離取絕對(duì)值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)先f(wàn)or(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)志printf(nnn,numl);p

7、rintf(=n);/ 排班 printf( 被訪問(wèn)的下一個(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+)printf(sum+=stepi;平均尋道長(zhǎng)度 %3.2fnnn,sum/num);/ 輸出int show()/ 顯示用戶界面int choose;/ 選擇printf(n*早期的磁盤(pán)調(diào)度算法*n);printf(tt1 、先來(lái)先

8、服務(wù) (FCFS)n);printf(tt2、最短尋道時(shí)間優(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;截圖：主界面開(kāi)始，輸入選擇先來(lái)先服務(wù)還是最短尋道優(yōu)先， 輸入當(dāng)前磁道， 輸入要訪問(wèn)的磁道， 輸入要訪問(wèn)的磁道序列。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é)果正確。CSCAI算法輸入 當(dāng)前磁道 100 ,9 個(gè)磁道，分別為 55 58 39 18 90 160 150 38 184 ，此時(shí)選擇方 向向上結(jié)果正確。輸入 當(dāng)前磁道 100 ,9 個(gè)

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