【正文】 512字節(jié) ? 物理地址形式： ? 柱面號 ? 磁頭號 ? 扇區(qū)號 柱面、磁頭、扇區(qū) 102 第七章 設(shè)備管理 典型參數(shù) ? 20G： ? 39813 柱面 ? 16 頭 ? 63 扇區(qū) ? 60G： ? 28733 柱面 ? 16 頭 ? 255 扇區(qū) 103 第七章 設(shè)備管理 ? 由三個動作組成： ?尋道 ：磁頭移動定位到指定磁道 ?旋轉(zhuǎn)延遲：等待指定扇區(qū)從磁頭下旋轉(zhuǎn)經(jīng)過 ?數(shù)據(jù)傳輸：數(shù)據(jù)在磁盤與內(nèi)存之間的實際傳輸 磁盤的訪問過程 104 第七章 設(shè)備管理 ? 尋道時間 Ts： 大約幾 ms到幾十 ms ? 旋轉(zhuǎn)延遲時間 Tr： 對于 7200轉(zhuǎn) /分，平均延遲時間為 ? 數(shù)據(jù)傳輸時間 Tt： 目前磁盤的傳輸速度一般有幾十 M/s， 傳輸一個扇區(qū)的時間小于 磁盤的訪問時間 105 第七章 設(shè)備管理 思考 ? 要提高磁盤的數(shù)據(jù)訪問速度，主要應(yīng)在哪方面下功夫？ 106 第七章 設(shè)備管理 分析 ? 要提高磁盤的訪問速度主要應(yīng)從以下兩方面入手： ? 數(shù)據(jù)的合理組織 ? 磁盤的調(diào)度算法 107 第七章 設(shè)備管理 磁盤調(diào)度算法 ? 當多個訪盤請求在等待時，采用一定的策略，對這些請求的服務(wù)順序調(diào)整安排，旨在降低平均磁盤服務(wù)時間，達到公平、高效 ? 公平：一個 I/O請求在有限時間內(nèi)滿足 ? 高效：減少設(shè)備機械運動所帶來的時間浪費 ? 先來先服務(wù) ? 最短尋道時間優(yōu)先 ? 掃描算法 ? 單向掃描調(diào)度算法 108 第七章 設(shè)備管理 ? 按訪問請求到達的先后次序服務(wù) ? 優(yōu)點：簡單，公平； ? 缺點：效率不高，相鄰兩次請求可能會造成最內(nèi)到最外的柱面尋道，使磁頭反復(fù)移動，增加了服務(wù)時間，對機械也不利 先來先服務(wù) 109 第七章 設(shè)備管理 ? 假設(shè)磁盤訪問序列： 98， 183， 37， 122，14， 124， 65， 67 ? 讀寫頭起始位置： 53 ? 安排磁頭服務(wù)序列 ? 計算磁頭移動總距離（道數(shù)） 例 110 第七章 設(shè)備管理 圖解 98， 183， 37， 122， 14， 124， 65， 67 磁頭走過的總道數(shù)： 640 111 第七章 設(shè)備管理 ? 優(yōu)先選擇距當前磁頭最近的訪問請求進行服務(wù)，主要考慮尋道優(yōu)先 ? 優(yōu)點：改善了磁盤平均服務(wù)時間； ? 缺點：造成某些訪問請求長期等待得不到服務(wù) 最短尋道時間優(yōu)先 112 第七章 設(shè)備管理 圖解 65， 67 ， 37， 14， 98， 122， 124， 183 磁頭走過的總道數(shù)： 236 98， 183， 37， 122， 14， 124， 65， 67 113 第七章 設(shè)備管理 ? 克服了最短尋道優(yōu)先的缺點，既 考慮了距離 ，同時又 考慮了方向 ? 具體做法：當設(shè)備無訪問請求時，磁頭不動；當有訪問請求時，磁頭按一個方向移動，在移動過程中對遇到的訪問請求進行服務(wù)，然后判斷該方向上是否還有訪問請求，如果有則繼續(xù)掃描；否則改變移動方向，并為經(jīng)過的訪問請求服務(wù)，如此反復(fù) 掃描算法（電梯算法） 114 第七章 設(shè)備管理 圖 115 第七章 設(shè)備管理 圖解 37， 14， 65， 67 ， 98， 122， 124， 183 磁頭走過的總道數(shù)： 208 98， 183， 37， 122， 14， 124， 65， 67 116 第七章 設(shè)備管理 ? 也稱循環(huán)掃描算法。 ? 電梯算法杜絕了饑餓，但當請求對磁道的分布是均勻時，磁頭回頭，近磁頭端的請求很少（因為磁頭剛經(jīng)過），而遠端請求較多，這些請求等待時間要長一些。 ? 總是從 0號柱面開始向里掃描。移動臂到達最后個一個柱面后，立即帶動讀寫磁頭快速返回到 0號柱面。返回時不為任何的等待訪問者服務(wù)。返回后可再次進行掃描 單向掃描調(diào)度算法 117 第七章 設(shè)備管理 圖解 118 第七章 設(shè)備管理 調(diào)度算法的選擇 ? 實際系統(tǒng)相當普遍采用 最短尋道時間優(yōu)先算法，因為它簡單有效，性價比好。 ? 掃描算法更適于磁盤負擔重的系統(tǒng)。 ? 磁盤負擔很輕的系統(tǒng)也可以采用先來先服務(wù)算法 ? 一般要將磁盤調(diào)度算法作為操作系統(tǒng)的單獨模塊編寫，利于修改和更換。 119 第七章 設(shè)備管理 外存空間管理 ? 外存空間管理主要就是空閑塊的管理 ， 有以下方法： ? 空閑表法 ? 空閑鏈表法 ? 位圖法 ? 成組鏈接法 120 第七章 設(shè)備管理 空閑表法 ? 與內(nèi)存管理中的動態(tài)分區(qū)分配方式相同 。 ? 空閑盤塊的分配與內(nèi)存的動態(tài)分配類似 ， 同樣可以用首次 、 最佳 、 最壞適應(yīng)法 。 盤塊的回收也同內(nèi)存的回收方式類似 。 起始空閑盤塊號 盤塊數(shù) 2 4 9 3 15 5 。 。 121 第七章 設(shè)備管理 空閑鏈表法 ? 空閑塊鏈是另一種空閑塊的組織方法 ， 它用一種鏈結(jié)構(gòu)把所有空閑塊鏈接在一起 。 ? 分配：當系統(tǒng)建立文件需分配空閑塊時 ， 從鏈中摘取所需的空閑塊 ， 然后調(diào)整鏈首指針 。 ? 回收：反之 ， 當回收空閑塊時 。把釋放的空閑塊逐個插入鏈首 。 122 第七章 設(shè)備管理 ? 這種方法只需在系統(tǒng)中保留一個鏈首指針 ，令其指向第一個空閑塊 。 ? 這種方法的優(yōu)點是簡單 ， 但工作效率較低 ，因為每次在鏈上增加和移出空閑塊時 ， 需要做 I/O操作 。 ? 例如把一空閑塊插入鏈時 ， 要把鏈首指針 (原指向第一個空閑塊 )寫該空閑塊中 ， 然后讓鏈首指針指向該空閑塊 。 從鏈中摘取空閑塊時也要讀取下一個空閑塊的指針 。 123 第七章 設(shè)備管理 位圖法 ? 系統(tǒng)為磁盤建立一張位圖 ， 在位圖中每個物理塊占 1位 ， 按物理塊的順序排列 。 1表示對應(yīng)的物理塊已占用 ， 0表示空閑 。 ? 。 124 第七章 設(shè)備管理 ? 分配時首先在位圖中找到為 0的位 ， 然后轉(zhuǎn)換成對應(yīng)的物理塊號 ， 分配給申請者 ， 并把相應(yīng)的位置為 1。 ? 回收時先將釋放的物理塊號轉(zhuǎn)換成相應(yīng)的位 ，并把這一位置為 0。 ? 位圖的大小依據(jù)物理磁盤的容量而定 。 如360KB的軟盤 ， 每個物理塊為 512字節(jié) ， 位圖只占用 90個字節(jié) 125 第七章 設(shè)備管理 成組鏈接法 ? UNIX采用此法 126 第七章 設(shè)備管理 原理 ? 在 UNIX中中有一個整型數(shù)組 s_free[l00] 和一個整型變量 s_nfree。 ? 將所有的空閑盤塊分組，每 100個空閑盤塊為一組。最后一組的塊號填入 s_free[ ]、 塊數(shù)賦于 s_nfree。 其余各組的塊號則分別存放在它的下一組的第一個盤塊中。 127 第七章 設(shè)備管理 圖解 ? 假設(shè)共有 387個空閑塊 128 第七章 設(shè)備管理 分配 ? 分 配 空 閑 盤 塊 時 ， 總 是 分 配s_free[s_nfree] 所指的盤塊 ， 并且s_nfree減 1 。 當發(fā)現(xiàn)是直接管理的最后一個盤塊時 ， 即 s_nfree=l時 ， 就將該盤塊中的索引表寫入到 s_nfree和 s_free[]中 ， 使得下一組變?yōu)橹苯庸芾?。 如此類推直到最后一組 。 129 第七章 設(shè)備管理 釋放 ? 釋放空閑盤塊 時，將其塊號登記在s_free[]表中第一個未被占用的項。例如，若 s_nfree的原先值為 87，則將釋放塊號登記在 s_free[88]中，然后s_nfree加 1。若在登記之前發(fā)現(xiàn) s_free已滿，則將 s_free[1]至 s_free[100]的內(nèi)容復(fù)寫到要釋放的盤塊中。這樣原來直接管理的 100空閑盤塊變?yōu)橛舍尫艍K間接管理。然后將此該釋放塊的塊號填入s_free[１ ]， 把 s_nfree置為 1。