【正文】 個進(jìn)程讀磁盤上一個大的連續(xù)分配文件時，盡管看起來對磁盤的訪問請求很多，但由于各信息塊鏈在一起，磁頭的移動距離卻很小，而鏈接文件和索引文件的數(shù)據(jù)塊可能會散布在整個盤上，使磁盤的磁臂大幅度移動， I/O負(fù)擔(dān)加重。 磁盤 I/O訪問時間的組成 例子：讀一個 128KB大小的文件 (1)文件由 8個連續(xù)磁道 (每個磁道 32個扇區(qū) )上的256 個扇區(qū)構(gòu)成： 20ms+(+)*8=220ms。 其中，柱面定位時間為 20ms，旋轉(zhuǎn)延遲時間為 ， 32扇區(qū)數(shù)據(jù)傳送時間為 ； (2)文件由 256個隨機(jī)分布的扇區(qū)構(gòu)成： (20ms++)*256=7373ms。 其中， 1扇區(qū)數(shù)據(jù)傳送時間為 ； 隨機(jī)分布時的訪問時間為連續(xù)分布時的 。 磁盤 I/O調(diào)度策略 有若干個訪問者請求磁盤執(zhí)行輸入輸出操作 ， 應(yīng)先讓哪一個訪問者完成操作 ？ （ 為了保證信息的安全 ，系統(tǒng)在任一時刻只允許一個訪問者啟動磁盤執(zhí)行輸入輸出操作 ， 其余的訪問者必須等待 。 ） 當(dāng)多個訪盤請求在等待時 ， 采用一定的策略 ， 對這些請求的服務(wù)順序調(diào)整安排 ， 旨在降低平均磁盤服務(wù)時間 ， 達(dá)到公平 、 高效 公平：一個 I/O請求在有限時間內(nèi)滿足 高效：減少設(shè)備機(jī)械運動所帶來的時間浪費 1. 問題的提出 2. 磁盤調(diào)度考慮的問題 為了提高系統(tǒng)效率 ， 降低若干個訪問者執(zhí)行輸入輸出操作的總時間 （ 平均服務(wù)時間 ） ， 增加單位時間內(nèi)的輸入輸出操作次數(shù) ， 應(yīng)根據(jù)移動臂的當(dāng)前位臵使尋找時間和延遲時間盡可能小的那個訪問者優(yōu)先得到服務(wù) 。 一次訪盤時間 = 尋道時間 +旋轉(zhuǎn)延遲時間 +存取時間 (1) 減少尋道時間 （ 活動頭磁盤 ） (2) 減少延遲時間 （ 固定頭磁盤 ） 3. 磁盤調(diào)度算法－移臂調(diào)度 先進(jìn)先出算法 優(yōu)先級算法 后進(jìn)先出算法 短查找時間優(yōu)先算法 掃描 (SCAN)算法 循環(huán)掃描 (CSCAN)算法 N步掃描 (NstepSCAN)算法 雙隊列掃描 (FSCAN)算法 3. 磁盤調(diào)度算法－移臂調(diào)度 先進(jìn)先出 (FIFO, First In First Out)算法 原理：磁盤 I/O執(zhí)行順序為磁盤 I/O請求的先后順序。 該算法的特點是公平性；在磁盤 I/O負(fù)載較輕且每次讀寫多個連續(xù)扇區(qū)時，性能較好。 缺點：效率不高，未考慮訪問者要求訪問的物理位臵，相臨兩次請求可能會造成最內(nèi)到最外的柱面尋道，使磁頭反復(fù)移動，增加了服務(wù)時間，對機(jī)械也不利； 3. 磁盤調(diào)度算法－移臂調(diào)度 先進(jìn)先出 (FIFO, First In First Out)算法 ? 例：假設(shè)磁盤訪問序列： 98， 183， 37， 122， 14， 124， 65， 67 讀寫頭起始位臵： 53 安排磁頭服務(wù)序列 計算磁頭移動總距離（道數(shù)） 3. 磁盤調(diào)度算法－移臂調(diào)度 先進(jìn)先出 (FIFO, First In First Out)算法 3. 磁盤調(diào)度算法－移臂調(diào)度 優(yōu)先級算法 依據(jù)進(jìn)程優(yōu)先級來調(diào)整磁盤 I/O請求的執(zhí)行順序。 該算法反映進(jìn)程在系統(tǒng)的優(yōu)先級特征，目標(biāo)是系統(tǒng)目標(biāo)的實現(xiàn)，而不是改進(jìn)磁盤I/O性能。 3. 磁盤調(diào)度算法－移臂調(diào)度 后進(jìn)先出 (LIFO, Last In First Out)算法 后產(chǎn)生的磁盤 I/O請求，先執(zhí)行。 該算法是基于事務(wù)系統(tǒng)中順序文件中磁盤 I/O的局部性特征，相鄰訪問的位臵也相鄰。 它的問題在于系統(tǒng)負(fù)載重時，可能有進(jìn)程的磁盤 I/O永遠(yuǎn)不能執(zhí)行，處于饑餓狀態(tài)。 3. 磁盤調(diào)度算法－移臂調(diào)度 短查找時間優(yōu)先 (SSTF, Shortest Service Time First)算法 考慮磁盤 I/O請求隊列中各請求的磁頭定位位臵 ，選擇從當(dāng)前磁頭位臵出發(fā)，移動最少的磁盤 I/O請求。 該算法的目標(biāo)是使每次磁頭移動時間最少。它不一定是最短平均柱面定位時間，但比FIFO算法有更好的性能。 對中間的磁道有利，可能會有進(jìn)程處于饑餓狀態(tài)。 不公平：未考慮訪問者到來的先后次序。 3. 磁盤調(diào)度算法－移臂調(diào)度 短查找時間優(yōu)先 (SSTF, Shortest Service Time First)算法 98， 183， 37， 122， 14， 124， 65， 67 3. 磁盤調(diào)度算法－移臂調(diào)度 掃描 (SCAN)算法－電梯式算法 ? 在磁頭前進(jìn)方向上，選擇從當(dāng)前位臵移動最少的磁盤 I/O請求執(zhí)行，沒有前進(jìn)方向上的請求時才改變方向。 ? 該算法是對 SSTF算法的改進(jìn)，磁盤 I/O較好，且沒有進(jìn)程會餓死。 ? SSTF不考慮臂的移動方向，可能導(dǎo)致移動臂來回改變移動方向，速度相對較慢。相比之下，電梯調(diào)度算法是一種簡單、實用且高效的調(diào)度算法，但是，實現(xiàn)時除了要記住讀寫磁頭的當(dāng)前位臵外，還必須記住移動臂的移動方向。 3. 磁盤調(diào)度算法－移臂調(diào)度 掃描 (SCAN)算法－電梯式算法 98， 183， 37， 122， 14， 124， 65， 67 3. 磁盤調(diào)度算法－移臂調(diào)度 掃描 (SCAN)算法－電梯式算法 3. 磁盤調(diào)度算法－移臂調(diào)度 循環(huán)掃描 (CSCAN)算法（單向掃描算法） ? 在一個方向上使用掃描算法，當(dāng)?shù)竭_(dá)邊沿時直接移動到另一沿的第一個位臵。 ? 總是從 0號柱面開始向里掃描，依次選擇所遇到的訪問者；移動臂到達(dá)最后一個柱面時，立即帶動讀寫磁頭快速返回到 0號柱面，返回時不為任何訪問者服務(wù)，返回后再次進(jìn)行掃描。 單向反復(fù)地掃描，將磁盤各磁道視為一個環(huán)形緩沖區(qū)，首尾相 連，最后一個磁道與第一個磁道相連 ? 該算法可改進(jìn)掃描算法對中間磁道的偏好。實驗表明，該算法在中負(fù)載或重負(fù)載時，磁盤 I/O性能比掃描算法好。 3. 磁盤調(diào)度算法－移臂調(diào)度 N步掃描 (NstepSCAN)算法 ? 把磁盤 I/O請求隊列分成長度為 N的段，每次使用掃描算法處理這 N個請求。當(dāng)N=1時，該算法退化為 FIFO算法。 ? 該算法的目標(biāo)是改進(jìn)前幾種算法可能在多磁頭系統(tǒng)中出現(xiàn)磁頭靜止在一個磁道上，導(dǎo)致其它進(jìn)程無法及時進(jìn)行磁盤I/O。 3. 磁盤調(diào)度算法－移臂調(diào)度 雙隊列掃描 (FSCAN)算法： ? 把磁盤 I/O請求分成兩個隊列，交替使用掃描算法處理一個隊列，新生成的磁盤 I/O請求放入另一隊列中。 ? 該算法的目標(biāo)與 N步掃描算法一致。 4. 磁盤調(diào)度算法 －旋轉(zhuǎn)調(diào)度 根據(jù)延遲時間來決定執(zhí)行次序的調(diào)度稱 為 “ 旋轉(zhuǎn)調(diào)度 ” 。 即：當(dāng)移動臂定位后 ， 決定同一柱面訪問者的執(zhí)行次序 ？ 從減 少輸入輸出操作總時間為目標(biāo)考慮 ， 應(yīng) 優(yōu)先選擇延遲時間最短的訪問者進(jìn)行服 務(wù) 。 4. 磁盤調(diào)度算法 －旋轉(zhuǎn)調(diào)度 進(jìn)行旋轉(zhuǎn)調(diào)度時應(yīng)分析下列情況： （ 1） 若干等待訪問者請求訪問同一磁道上的不同扇區(qū) 。 （ 2） 若干等待訪問者請求訪問不同磁道上的不同編號的扇區(qū) 。 （ 3） 若干等待訪問者請求訪問不同磁道上具有相同編號的扇區(qū) 。 4. 磁盤調(diào)度算法 －旋轉(zhuǎn)調(diào)度 對于前兩種情況 ， 旋轉(zhuǎn)調(diào)度總是讓首先到達(dá)讀寫磁頭位臵下的扇區(qū)先進(jìn)行傳送操作 。 對于第三種情況 ， 這些扇區(qū)同時到達(dá)讀寫磁頭位臵下 ， 旋轉(zhuǎn)調(diào)度可任意選擇一個讀寫磁頭進(jìn)行傳送操作 。 磁盤緩存臵換算法 1. 訪問頻率臵換算法 (Frequencybased Replacement) 磁盤緩存是磁盤扇區(qū)在內(nèi)存中的緩沖區(qū)。 磁盤緩存的調(diào)度算法很類似虛擬存儲調(diào)度算法，但由于磁盤的訪問頻率遠(yuǎn)低于虛擬存儲，它們又存在區(qū)別。 通常磁盤緩存調(diào)度算法會比虛擬存儲復(fù)雜。 磁盤緩存臵換算法 它是對 LRU(最近最久未使用 )算法和 LFU(最不常用 )算法的改進(jìn)；它要解決的主要問題是在 LFU算法中的引用計數(shù)問題。 磁盤訪問可能會十分集中，在一段密集使用后，引用計數(shù)的變化就不能反映當(dāng)前的引用情況。需要考慮磁盤訪問的這種密集特征，對密集引用不計數(shù)。 其基本思想是在短周期中使用 LRU算法，而在長周期中使用 LFU算法。 磁盤緩存臵換算法 訪問頻率臵換算法 把 LRU算法中的特殊棧分成三部分，并在每個緩存塊增 加一個引用計數(shù)。 新區(qū)域 (New Section) 中間區(qū)域 (Middle Section) 舊區(qū)域 (Old Section) 新區(qū)域 中間區(qū)域 舊區(qū)域引用計數(shù)不變引用計數(shù)加1新讀入數(shù)據(jù)塊，引用計數(shù)為1棧頂棧底 磁盤緩存臵換算法 訪問頻率臵換算法 ? 棧中緩存塊被訪問時移到棧頂；如果該塊在新區(qū)域，引用計數(shù)不變；否則，引用計數(shù)加 1。 在新區(qū)域中引用計數(shù)不變的目的是避免密集訪問對引用計數(shù)不利影響； 在中間區(qū)域和舊區(qū)域中引用計數(shù)加 1是為了使用 LFU算法； ? 未緩存數(shù)據(jù)塊讀入后放在棧頂，引用計數(shù)為 1； ? 在舊區(qū)域中引用計數(shù)最小的緩存塊被臵換；中間區(qū)域的定義是為了避免新讀入的緩存塊在第一次出現(xiàn)在新區(qū)域時馬上被臵換，有一個過渡期；