磁盤的調(diào)度算法探究

《磁盤的調(diào)度算法探究》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、磁盤的調(diào)度算法探究磁盤的調(diào)度算法探究摘要磁盤調(diào)度算法是操作系統(tǒng)對設(shè)備管理的一種非常重要的算法。在訪問磁盤的信息時必須確定信息在磁盤上面的物理的位置,然后等待所指定的扇區(qū)旋轉(zhuǎn)至磁頭位置下讓指定磁頭進行讀或?qū)懀瑥亩瓿尚畔⒌膫鬏?。所以操作系統(tǒng)為提高磁盤的輸入輸出的效率，就要減少尋道時間和旋轉(zhuǎn)延遲時間，使磁盤平均服務(wù)時間最短。故本文主要討論如何減少尋道時間?！娟P(guān)鍵詞】磁盤調(diào)度算法研究磁盤調(diào)度算法，也叫移臂調(diào)度算法。為什么會產(chǎn)生磁盤調(diào)度？這是rti-T,對于移動臂磁盤，執(zhí)行信息傳輸操作時必須確定信息在磁盤上面的物理的位置。因此，每一次對磁盤發(fā)出訪問請求，都

2、應(yīng)給出所耍訪問的磁盤存儲空間的地址：柱面號+磁頭號+扇區(qū)號。在執(zhí)行信息傳輸時，首先將移動臂移動到指定的柱面上，然后等待所指定的扇區(qū)旋轉(zhuǎn)至磁頭位置下，最后讓指定磁頭進行讀或?qū)?，從而完成信息的傳輸。所以?zhí)行一次信息的傳輸操作，花費的時間一共有三部分組成：尋找時間，即磁頭在移動臂的帶動下，耍移動到指定的柱而上所需的時間。這是一個機械動作，要花費較長的時間。延遲時間，即指定的扇區(qū)要旋轉(zhuǎn)至磁頭所在位置需要的時間。這一時間與信息所在的扇區(qū)位置有關(guān)系。數(shù)據(jù)傳輸時間，即磁頭把扇區(qū)屮的信息讀到內(nèi)存，或把內(nèi)存中的信息寫到扇區(qū)需耍的時間。每個扇區(qū)中信息傳送時間是相同的，

3、且是固定的（當(dāng)驅(qū)動器固定時）。數(shù)據(jù)傳輸時間是盤的硬件特性決定的，OS為提高磁盤的I/O的效率，主耍是要減少尋道時間和旋轉(zhuǎn)延遲時間，使磁盤平均服務(wù)時間最短。在這里，主要討論如何減少尋道時間。要減少尋道時間，可以采用磁盤調(diào)度算法，該算法有：先來先服務(wù)算法、最短尋找時間優(yōu)先算法、電梯調(diào)度算法和C-SCAN調(diào)度。1先來先服務(wù)調(diào)度算法(FCFS)最簡單的移臂調(diào)度算法就是“先來先服務(wù)”調(diào)度算法，這一算法就是不考慮訪問者需要訪問的物理位置，但要考慮訪問者在提出訪問請求時的先后順序。根據(jù)輸入輸出請求的到達(dá)次序，逐…完成訪問請求，而不考慮它們要訪問的物理位置。即按請

4、求的時間順序，先來的先服務(wù)。這一算法的原則是各個進程在對磁盤發(fā)出請求時，進行排隊等待,這吋就會按照發(fā)出請求的吋間進行排隊，并按照排隊隊列的順序進行服務(wù)。采用先來先服務(wù)算法決定哪一個訪問者該執(zhí)行輸入輸出操作的順序吋，要來回地移動移動臂。所以這一算法花費的尋找吋間比較長，故而執(zhí)行輸入輸出的操作總吋間就很長。優(yōu)點：算法公平、簡單，不會出現(xiàn)“饑餓”現(xiàn)象缺點：磁頭移動的磁道總數(shù)多，花費時間多。2最短尋道時間(SSTF)優(yōu)先算法這一算法是依據(jù)磁頭當(dāng)前所在位置，選擇距離當(dāng)前磁頭最短的訪問者為之服務(wù)，不管訪問者發(fā)出請求的先后順序。止是因為尋找訪問者的時間與兩次服務(wù)

5、Z間的磁道數(shù)目成正比，所以最短尋道時間優(yōu)先算法有效地減少了查找時間。這一算法的原則是在請求隊列中，選擇訪問者所在柱面號最接近當(dāng)前磁頭所在的柱面的訪問者，作為下一個服務(wù)對象，也就是先為查找吋間最小的那個請求執(zhí)行，不管它是在磁臂的前進還是后退方向上。例了采用FIFS中請求的例了按照SSIF調(diào)度。如果移動臂當(dāng)前在柱面53,采用這種算法磁盤的調(diào)度順序為65,67,37,14,98,122,124,183,移動臂總距離是236道采用SSTF算法，選擇訪問者執(zhí)行操作的等待時間，與FCFS算法比較，很大程度上減少了尋找時間，從而縮短了各個訪問者平均請求服務(wù)的吋間

6、，提高了系統(tǒng)的效率。優(yōu)點：比FCFS有較好的吞吐量，較低的平均響應(yīng)時間，極大的改善了盤平均服務(wù)吋間。缺點：響應(yīng)時間變化幅度很大；可能導(dǎo)致〃饑餓〃。3電梯調(diào)度(SCAN)算法電梯調(diào)度算法是是一種非常簡單而實用的算法。根據(jù)SCAN算法磁頭總是選擇從移動臂當(dāng)前位置開始，然后沿著臂的移動方向選擇距離當(dāng)前移動臂最近的那個柱訪問，若沿著臂的移動方向上沒有請求訪問時，就改變臂的移動方向在相反的方向上相應(yīng)請求訪問，從而使移動頻率最小化。SCAN算法類似乘電梯，比如電梯已經(jīng)向上運行到了5層時，有3位乘客A、B、C依次在等候乘電梯。他們要求：A在3層要去10層；B在6

7、層要去1層；C在7層等待14層。這吋電梯的運行方向是向上的，因此電梯會先把乘客C從7層帶到14層，然后電梯改變運行方向，向下運行，把乘客B從6層帶到1層，最后電梯再改變方向，把乘客A從3層送到10層。“電梯調(diào)度”算法和“最短尋找吋間優(yōu)先”算法的共同點都是盡量地減少移動臂所花的吋間，不同的是“最短尋找吋間優(yōu)先”算法不考慮臂的移動方向只選擇距離當(dāng)前磁頭最近的，但這就會引起移動臂來回的改變移動方向；而“電梯調(diào)度”算法是按照臂的運行方向去選擇離當(dāng)前磁頭最近的訪問者，若無訪問等待者時才改變移動臂的前進方向。去改變移動臂的運行方向是一種機械動作，所以速度相對較

8、慢，故電梯調(diào)度算法比“最短尋找吋間優(yōu)先”算法更簡單高效。優(yōu)點：吞吐量比較大，平均響應(yīng)吋間較小。缺點：兩側(cè)磁道訪問頻率仍低于