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