磁盤調(diào)度算法資料

磁盤調(diào)度算法先來先服務(wù)（ FCFS）最短尋道時(shí)間優(yōu)先 （SSTF）掃描算法（SCAN）或電梯算法循環(huán)掃描算法（CSCAN）先來先服務(wù)（FCFS）按請(qǐng)求訪問的先后次序來訪問，而不考慮它們要訪問的物理位置。（這種算法平均尋道時(shí)間較長(zhǎng)，僅適合磁盤請(qǐng)求較少的場(chǎng)合）例：一個(gè)有40個(gè)磁道的磁盤，現(xiàn)在要求讀取第11、1、36、16、34、9、12磁道上的數(shù)據(jù)，那么讀取順序?yàn)椋旱谝徊剑捍蓬^由第第一步：磁頭由第11磁道移到第1磁道NN36 34 16 1211 9 10第一步：磁頭由第第一步：磁頭由第11磁道移到第1磁道NN36 34 16 1211 9 10N36 34 16 1211 9 10第二步：磁頭由第1磁道移到第36磁道N36 34 16 1211 9 10第三步：磁頭由第36磁道移到第16磁道第四步：磁頭由第第四步：磁頭由第16磁道移到第34磁道NN36 34 16 1211 9 10第四步：磁頭由第第四步：磁頭由第16磁道移到第34磁道NN36 34 16 1211 9 10第五步：磁頭由第34磁道移到第9磁道第六步：磁頭由第9磁道移到第12磁道最短尋道時(shí)間優(yōu)先（SSTF）先訪問離當(dāng)前磁道最近的那個(gè)磁道,（即：讓查找時(shí)間最短的那個(gè)作業(yè)先執(zhí)行，而不考慮請(qǐng)求訪問者到達(dá)的先后次序，這樣就克服了先來先服務(wù)算法中的磁頭移動(dòng)過大的問題）例：一個(gè)有40個(gè)磁道的磁盤，現(xiàn)在要求讀取第11、1、36、16、34、9、12磁道上的數(shù)據(jù)，那么讀取順序?yàn)椋旱谝徊剑捍蓬^開始時(shí)位于第11磁道，而離第11磁道最近的是第12磁道,所以把磁頭由第11磁道移到第12磁道第二步：磁頭此時(shí)位于第12磁道，而離第12磁道最近的是第9磁道,所以把磁頭由第12磁道移到第9磁道第六步：磁頭此時(shí)位于第第六步：磁頭此時(shí)位于第34磁道，而離第34磁道最近的是第36磁道,第六步：磁頭此時(shí)位于第第六步：磁頭此時(shí)位于第34磁道，而離第34磁道最近的是第36磁道,第三步：磁頭此時(shí)位于第第三步：磁頭此時(shí)位于第9磁道，而離第9磁道最近的是第16磁道，所NN36 34 16 1211 9 10以把磁頭由第9磁道移到第16磁道N36 34N36 3416 1211 9第四步：磁頭此時(shí)位于第16磁道，而離第16磁道最近的是第1磁道,所以把磁頭由第16磁道移到第1磁道N36 34N36 3416 1211 9第五步：磁頭此時(shí)位于第1磁道，而離第1磁道最近的是第34磁道，所以把磁頭由第1磁道移到第34磁道

所以把磁頭由第34磁道移到第36磁道N36 34N36 3416 1211 9掃描算法（SCAN）又叫“電梯算法”是具有方向性的“最短尋道時(shí)間優(yōu)先”。像電梯一樣，沿磁頭的移動(dòng)方向去訪問離當(dāng)前磁頭最近的那個(gè)磁道，只有當(dāng)沿磁頭方向再無請(qǐng)求訪問時(shí)，才改變磁頭的移動(dòng)方向。（即：如果離當(dāng)前磁頭最近的磁道在左邊，則先把左邊的所有磁道都訪問完，再改變方向，訪問右邊的所有磁道；如果離當(dāng)前磁頭最近的磁道在右邊，則先把右邊的所有磁道都訪問完，再改變方向，訪問左邊的所有磁道。 ）例：一個(gè)有40個(gè)磁道的磁盤，現(xiàn)在要求讀取第11、1、36、16、34、9、12磁道上的數(shù)據(jù)，那么讀取順序?yàn)椋旱谝徊剑捍蓬^開始時(shí)位于第11磁道，而離第11磁道最近的是第12磁道,所以把磁頭由第11磁道移到第12磁道N36 34 16 1211 9 10第二步：此時(shí)磁頭的移動(dòng)方向是向左，所以要先把左邊的所有磁道都訪第二步：此時(shí)磁頭的移動(dòng)方向是向左，所以要先把左邊的所有磁道都訪第二步：此時(shí)磁頭的移動(dòng)方向是向左，所以要先把左邊的所有磁道都訪第二步：此時(shí)磁頭的移動(dòng)方向是向左，所以要先把左邊的所有磁道都訪問完，才改變方向，訪問右邊的所有磁道。在左邊方向上，離第 12磁道最近的是第16磁道，所以把磁頭由第12磁道移到第16磁道N36 34N36 3416 1211 9第三步：此時(shí)在左邊方向上，離第16磁道最近的是第34磁道，所以把磁頭由第16磁道移到第34磁道N36 34 16 1211 9 10第四步：此時(shí)在左邊方向上，離第34磁道最近的是第36磁道，所以把磁頭由第34磁道移到第36磁道N36 34N36 3416 1211 9第五步：此時(shí)在左邊方向上，已再無要訪問的磁道了，所以改變磁頭的移動(dòng)方向，開始訪問右邊的所有磁道。此時(shí)，在右邊方向上，離第36磁道最近的是第9磁道，所以把磁頭由第36磁道移到第9磁道N36 3416 1211 9N36 3416 1211 9第六步：此時(shí)，在右邊方向上，離第9磁道最近的是第1磁道，所以把磁頭由第9磁道移到第1磁道36341612113634161211第二步：此時(shí)磁頭位于第第二步：此時(shí)磁頭位于第90磁道，在向右方向上，離第90磁道最近的循環(huán)掃描算法（CSCAN）相當(dāng)于：?jiǎn)畏较虻碾娞菟惴?。磁頭只向一個(gè)方向移動(dòng)（要么是從左到右，要么是從右到左），例如，磁頭只從左到右移動(dòng)，那么從當(dāng)前位置出發(fā)，向右先訪問離當(dāng)前磁頭位置最近的磁道，然后繼續(xù)向右訪問離當(dāng)前磁頭位置最近的磁道，直到把右邊所有的磁道都訪問完，然后磁頭返回到最左邊，繼續(xù)向右訪問。題目：一個(gè)有200個(gè)磁道的磁盤，磁頭開始位置位于第100磁道，現(xiàn)在要求讀取第50、90、30、120磁道上的數(shù)據(jù)，移動(dòng)方向?yàn)閺淖蟮接?，那么讀取順序?yàn)椋旱谝徊剑捍蓬^開始時(shí)位于第100磁道，在向右方向上，離第100磁道最近的是第90磁道，所以把磁頭由第100磁道移到第90磁道。N120 100 90 50 300是第50磁道，所以把磁頭由第90磁道移到第50磁道N120 1009050N120 1009050300第二步：此時(shí)磁頭位于第50磁道，在向右方向上，離第50磁道最近的是第30磁道，所以把磁頭由第50磁道移到第30磁道N120 1009050N120 1009050300第三步：此時(shí)磁頭位于第30磁道，在向右的方向上，已再無需要訪問的磁道了，于是磁頭返回到最左邊，繼續(xù)向右訪問。此時(shí)，離最左端磁道最近的是第120磁道，所以把磁頭由最左端磁道移到第 120磁道N120 100 90 50 300.在以下磁盤調(diào)度中，算法可能出現(xiàn)饑餓現(xiàn)象?！尽铩铩緼.電梯調(diào)度 B.最短尋道時(shí)間優(yōu)先C.循環(huán)掃描算法 D.先來先服務(wù)解：最短尋道時(shí)間優(yōu)先調(diào)度算法可能出現(xiàn)饑餓現(xiàn)象，其他算法不會(huì)。本題答案為B。.在以下磁盤調(diào)度中，算法可能會(huì)隨時(shí)改變磁頭的運(yùn)動(dòng)方向。A.電梯調(diào)度 B.先來先服務(wù)C.循環(huán)掃描算法 D.都不會(huì)解：先來先服務(wù)調(diào)度算法可能會(huì)隨時(shí)改變磁頭的運(yùn)動(dòng)方向，因?yàn)橄葋淼恼?qǐng)求可能在當(dāng)前磁頭位置的左邊或右邊。本題答案為Bo ---.假設(shè)磁頭當(dāng)前位于第105道，正在向磁道序號(hào)增加的方向移動(dòng)?，F(xiàn)有一個(gè)破道訪問請(qǐng)求序列為35、45、12、68、100、180、170、195。采用SCAN調(diào)度（電梯調(diào)度）算法得到的磁道訪問序列是。110、170、180、195、68、45>35、12 .4110、68、45、35、12、170、180、195C110、170、180、195、12、35、45、68D.12、35、45、68、110、170、180、195本題為2009年全國(guó)考研題?解：采用SCAN調(diào)度算法的結(jié)果如圖18.19所示。本題答案為A。27,設(shè)磁盤的I/O請(qǐng)求隊(duì)列中的柱面號(hào)為19、376、205、134、18、56、193、396、29、3、19、40,磁頭的起始位置為100,若采用SCAN（電梯調(diào)度）算法（磁頭的運(yùn)行方向是向內(nèi)的），則磁頭移動(dòng)個(gè)磁道?！尽铩铩緼.2O5 B.480 C.490 D.512解：對(duì)SCAN算法,尋道順序?yàn)椋?00、56、40、29、19、18、3、134、193、205、376、396,移動(dòng)磁道次數(shù)分別為44、16、11、10、1、15、131、59、12、171、20,總數(shù)為490.本題答案為Co —28,嫻盤的I/O請(qǐng)求隊(duì)列中的柱面號(hào)為55、58、39、18、90、160、150、38、184,磁頭艇始位置為100,若采用SSTF（最短尋道時(shí)間優(yōu)先）算法,則磁頭移動(dòng)一個(gè)磁道?！尽铩铩緼8 B.184 C.200 D.248解：對(duì)SSTF算法，尋道順序?yàn)椋?00、90、58、55、39、38、18、150、160、184,移動(dòng)磁道次數(shù)分別為10、32、3、16、1、20、132、10、24,總數(shù)為248。本題答案為D。29.如果當(dāng)前讀寫磁頭正在53號(hào)柱面上執(zhí)行輸入輸出操作，依次有4個(gè)等待者分別要訪問的柱面號(hào)為98、37、124、65,當(dāng)采用調(diào)度算法時(shí)下一次讀寫磁頭才可能到達(dá)37號(hào)柱面?！尽铩铩緼.先來先服務(wù)B,最短尋找時(shí)間優(yōu)先 Sc.電梯調(diào)度（初始磁頭移動(dòng)方向向著小磁道方向） JJMD,循環(huán)掃描算法（磁頭移動(dòng)方向向著大磁道方向） J解：若采用先來先服務(wù)調(diào)度算法，卜.?個(gè)應(yīng)為98c若采用最短尋找時(shí)間優(yōu)先調(diào)度算法，離53號(hào)柱面最近的是65。若采用電梯調(diào)度算法（在初始磁頭移動(dòng)方向向著小磁道方同時(shí)），卜?一個(gè)應(yīng)為37。若循環(huán)掃描算法（磁頭移動(dòng)方向向著大磁道方向），下一個(gè)應(yīng)為65o本題答案為Co38.假設(shè)計(jì)算機(jī)系統(tǒng)采用CSCAN（循環(huán)掃描）磁盤調(diào)度策略，使用2KB的內(nèi)存空間記錄16384個(gè)磁盤塊的空閑狀態(tài)?！尽铩铩铩铩浚?）請(qǐng)說明在上述條件下如何進(jìn)行磁盤塊的空閑狀態(tài)管理。 ［工，（2）設(shè)某單面磁盤的旋轉(zhuǎn)速度為每分鐘6000轉(zhuǎn),每個(gè)磁道有100個(gè)扇區(qū),相鄰磁道間的平均移動(dòng)時(shí)間為1ms。若在某時(shí)刻，磁頭位于100號(hào)磁道處,并沿蓑磁道號(hào)增大的方向移動(dòng)（如圖18.21所示），磁道號(hào)的請(qǐng)求隊(duì)列為50,90,30,1記一再請(qǐng)求M列中的每個(gè)磁道需要讀取］個(gè)隨機(jī)分布的扇區(qū)，則讀完這幅區(qū)點(diǎn)病要多少時(shí)間?要求給出計(jì)算過程。隨機(jī)分布的某扇區(qū)0號(hào)磁道磁頭運(yùn)行方向100號(hào)磁道圖18.21 一個(gè)磁盤結(jié)構(gòu)（3）如果將磁盤替換為隨機(jī)訪問的Flash半導(dǎo)體存儲(chǔ)器（如U盤、SSD等），是否有比CSCAN更高效的磁盤調(diào)度策略？若有，給出磁盤調(diào)度策略的名稱并說明理由；若無，也說明理由。 .一M；本題為2010年全國(guó)考研題.- 解：（1）使用位小圖法表示磁盤的空閑狀態(tài)，每一位表示一個(gè)磁道塊是否為空閑,共需要16384/32=512個(gè)字=512x4個(gè)字節(jié)=2KB,正好可放在系統(tǒng)提供的內(nèi)存中。（2）采用CSCAN調(diào)度算法，訪問磁道的順序?yàn)?20、30、50、90,則移動(dòng)磁道長(zhǎng)度力20+90+20+40=170,總的移動(dòng)磁麗間萬而而行菽每分鐘6000轉(zhuǎn)，則平均旋轉(zhuǎn)