【正文】 160 70 150 10 38 112 184 146 平均尋道長度 : OS 2． 最短尋道時(shí)間優(yōu)先 (SSTF， Shortest Seek Time First) 該算法選擇這樣的進(jìn)程：其要求訪問的磁道與當(dāng)前磁頭所在的磁道距離最近，以使每次的尋道時(shí)間最短。但這種算法不能保證平均尋道時(shí)間最短。 OS 圖 526 SSTF調(diào)度算法 ( 從 100 號(hào)磁道開始 ) 被訪問的下 一個(gè)磁道號(hào) 移動(dòng)距離 ( 磁道數(shù) ) 90 10 58 32 55 3 39 16 38 1 18 20 150 132 160 10 184 24 平均尋道長度 : OS 3． 掃描 (SCAN)算法 1) 進(jìn)程 “ 饑餓 ” 現(xiàn)象 SSTF算法雖然能獲得較好的尋道性能，但卻可能導(dǎo)致某個(gè)進(jìn)程發(fā)生 “ 饑餓 ” (Starvation)現(xiàn)象。因?yàn)橹灰粩嘤行逻M(jìn)程的請(qǐng)求到達(dá)，且其所要訪問的磁道與磁頭當(dāng)前所在磁道的距離較近，這種新進(jìn)程的 I/O請(qǐng)求必然優(yōu)先滿足。對(duì) SSTF算法略加修改后所形成的 SCAN算法，即可防止老進(jìn)程出現(xiàn)“ 饑餓 ” 現(xiàn)象。 OS 2) SCAN算法 該算法不僅考慮到欲訪問的磁道與當(dāng)前磁道間的距離，更優(yōu)先考慮的是磁頭當(dāng)前的移動(dòng)方向。 由于在這種算法中磁頭移動(dòng)的規(guī)律頗似電梯的運(yùn)行，因而又常稱之為電梯調(diào)度算法。圖 527示出了按 SCAN算法對(duì) 9個(gè)進(jìn)程進(jìn)行調(diào)度及磁頭移動(dòng)的情況。 OS 圖 527 SCAN調(diào)度算法示例 ( 從 100 磁道開始，向磁道號(hào)增加方向訪問 ) 被訪問的下 一個(gè)磁道號(hào) 移動(dòng)距離 ( 磁道數(shù) ) 150 50 160 10 184 24 90 94 58 32 55 3 39 16 38 1 18 20 平均尋道長度： OS 4． 循環(huán)掃描 (CSCAN)算法 CSCAN算法規(guī)定磁頭單向移動(dòng)，例如，只是自里向外移動(dòng)，當(dāng)磁頭移到最外的磁道并訪問后，磁頭立即返回到最里的欲訪問的磁道，亦即將最小磁道號(hào)緊接著最大磁道號(hào)構(gòu)成循環(huán)，進(jìn)行循環(huán)掃描。 OS 圖 528 CSCAN調(diào)度算法示例 ( 從 100 磁道開始，向磁道號(hào)增加方向訪問 ) 被訪問的下 一個(gè)磁道號(hào) 移動(dòng)距離 ( 磁道數(shù) ) 150 50 160 10 184 24 18 166 38 20 39 1 55 16 58 3 90 32 平均尋道長度 : OS 5． NStepSCAN和 FSCAN調(diào)度算法 1) NStepSCAN算法 在 SSTF、 SCAN及 CSCAN幾種調(diào)度算法中有 “ 磁臂粘著 ”現(xiàn)象 (Armstickiness)。 N步 SCAN算法是將磁盤請(qǐng)求隊(duì)列分成若干個(gè)長度為 N的子隊(duì)列，磁盤調(diào)度將按 FCFS算法依次處理這些子隊(duì)列。而每處理一個(gè)隊(duì)列時(shí)又是按 SCAN算法，對(duì)一個(gè)隊(duì)列處理完后，再處理其他隊(duì)列。當(dāng)正在處理某子隊(duì)列時(shí)，如果又出現(xiàn)新的磁盤 I/O請(qǐng)求，便將新請(qǐng)求進(jìn)程放入其他隊(duì)列，這樣就可避免出現(xiàn)粘著現(xiàn)象。當(dāng) N值取得很大時(shí)，會(huì)使 N步掃描法的性能接近于 SCAN算法的性能；當(dāng) N=1時(shí)， N步 SCAN算法便蛻化為FCFS算法。 OS 2) FSCAN算法 FSCAN算法實(shí)質(zhì)上是 N步 SCAN算法的簡化，即 FSCAN只將磁盤請(qǐng)求隊(duì)列分成兩個(gè)子隊(duì)列。一個(gè)是由當(dāng)前所有請(qǐng)求磁盤 I/O的進(jìn)程形成的隊(duì)列，由磁盤調(diào)度按 SCAN算法進(jìn)行處理。在掃描期間，將新出現(xiàn)的所有請(qǐng)求磁盤 I/O的進(jìn)程，放入另一個(gè)等待處理的請(qǐng)求隊(duì)列。這樣，所有的新請(qǐng)求都將被推遲到下一次掃描時(shí)處理。 OS 磁盤高速緩存 1． 磁盤高速緩存的形式 利用內(nèi)存中的存儲(chǔ)空間來暫存從磁盤中讀出的一系列盤塊中的信息。因此，這里的高速緩存是一組在邏輯上屬于磁盤，而物理上是駐留在內(nèi)存中的盤塊。 高速緩存在內(nèi)存中可分成兩種形式。 第一種是在內(nèi)存中開辟一個(gè)單獨(dú)的存儲(chǔ)空間來作為磁盤高速緩存，其大小是固定的，不會(huì)受應(yīng)用程序多少的影響； 第二種是把所有未利用的內(nèi)存空間變?yōu)橐粋€(gè)緩沖池，供請(qǐng)求分頁系統(tǒng)和磁盤 I/O時(shí) (作為磁盤高速緩存 )共享。 OS 2． 數(shù)據(jù)交付方式 數(shù)據(jù)交付 (Data Delivery)是指將磁盤高速緩存中的數(shù)據(jù)傳送給請(qǐng)求者進(jìn)程。 系統(tǒng)可以采取兩種方式將數(shù)據(jù)交付給請(qǐng)求進(jìn)程： (1) 數(shù)據(jù)交付 。 這是直接將高速緩存中的數(shù)據(jù) ， 傳送到請(qǐng)求者進(jìn)程的內(nèi)存工作區(qū)中 。 (2) 指針交付 。 這是只將指向高速緩存中某區(qū)域的指針交付給請(qǐng)求者進(jìn)程 。 OS 3． 置換算法 如同請(qǐng)求調(diào)頁 (段 )一樣 ， 在將磁盤中的盤塊數(shù)據(jù)讀入高速緩存時(shí) ， 同樣會(huì)出現(xiàn)因高速緩存中已裝滿盤塊數(shù)據(jù)而需要將該數(shù)據(jù)先換出的問題 。 相應(yīng)地 ， 也必然存在著采用哪種置換算法的問題 。 較常用的置換算法仍然是最近最久未使用算法 LRU、 最近未使用算法 NRU及最少使用算法 LFU等 。 由于請(qǐng)求調(diào)頁中的聯(lián)想存儲(chǔ)器與高速緩存 (磁盤 I/O中 )的工作情況不同，因而使得在置換算法中所應(yīng)考慮的問題也有所差異。因此，現(xiàn)在不少系統(tǒng)在設(shè)計(jì)其高速緩存的置換算法時(shí)，除了考慮到最近最久未使用這一原則外，還考慮了以下幾點(diǎn)： OS 1) 訪問頻率 通常，每執(zhí)行一條指令時(shí)，便可能訪問一次聯(lián)想存儲(chǔ)器，亦即聯(lián)想存儲(chǔ)器的訪問頻率，基本上與指令執(zhí)行的頻率相當(dāng)。而對(duì)高速緩存的訪問頻率，則與磁盤 I/O的頻率相當(dāng)。因此，對(duì)聯(lián)想存儲(chǔ)器的訪問頻率遠(yuǎn)遠(yuǎn)高于對(duì)高速緩存的訪問頻率。 OS 2) 可預(yù)見性 在高速緩存中的各盤塊數(shù)據(jù)，有哪些數(shù)據(jù)可能在較長時(shí)間內(nèi)不會(huì)再被訪問，又有哪些數(shù)據(jù)可能很快就再被訪問，會(huì)有相當(dāng)一部分是可預(yù)知的。例如，對(duì)二次地址及目錄塊等，在它被訪問后，可能會(huì)很久都不再被訪問。又如，正在寫入數(shù)據(jù)的未滿盤塊，可能會(huì)很快又被訪問。 OS 3) 數(shù)據(jù)的一致性 由于高速緩存是做在內(nèi)存中的 ， 而內(nèi)存一般又是一種易失性的存儲(chǔ)器 ， 一旦系統(tǒng)發(fā)生故障 ， 存放在高速緩存中的數(shù)據(jù)將會(huì)丟失；而其中有些盤塊 (如索引結(jié)點(diǎn)盤塊 )中的數(shù)據(jù)已被修改 ， 但尚未拷回磁盤 ， 因此 ， 當(dāng)系統(tǒng)發(fā)生故障后 ， 可能會(huì)造成數(shù)據(jù)的不一致性 。 OS 4． 周期性地寫回磁盤 還有一種情況值得注意 : 那就是根據(jù) LRU算法，那些經(jīng)常要被訪問的盤塊數(shù)據(jù)，可能會(huì)一直保留在高速緩存中，長期不會(huì)被寫回磁盤。例如，一位學(xué)者一上班便開始撰寫論文，并邊寫邊修改，他正在寫作的論文就一直保存在高速緩存的LRU鏈中。如果在快下班時(shí)，系統(tǒng)突然發(fā)生故障，這樣，存放在高速緩存中的已寫論文將隨之消失，致使他枉費(fèi)了一天的勞動(dòng)。 辦法：強(qiáng)制性地將所有在高速緩存中已修改的盤塊數(shù)據(jù)寫回磁盤。一般是把兩次調(diào)用 SYNC的時(shí)間間隔定為 30 s。這樣，因系統(tǒng)故障所造成的工作損失不會(huì)超過 30 s的勞動(dòng)量。 OS 提高磁盤 I/O速度的其它方法 1． 提前讀 (Readahead) 用戶 (進(jìn)程 )對(duì)文件進(jìn)行訪問時(shí)，經(jīng)常采用順序訪問方式，即順序地訪問文件各盤塊的數(shù)據(jù)。在這種情況下，在讀當(dāng)前塊時(shí)可以預(yù)知下一次要讀的盤塊。因此，可以采取預(yù)先讀方式，即在讀當(dāng)前塊的同時(shí)，還要求將下一個(gè)盤塊 (提前讀的塊 )中的數(shù)據(jù)也讀入緩沖區(qū)。這樣，當(dāng)下一次要讀該盤塊中的數(shù)據(jù)時(shí)，由于該數(shù)據(jù)已被提前讀入緩沖區(qū)，因而此時(shí)便可直接從緩沖區(qū)中取得下一盤塊的數(shù)據(jù)，而不需再去啟動(dòng)磁盤 I/O，從而大大減少了讀數(shù)據(jù)的時(shí)間。 OS 2． 延遲寫 延遲寫是指在緩沖區(qū) A中的數(shù)據(jù)，本應(yīng)立即寫回磁盤，但考慮到該緩沖區(qū)中的數(shù)據(jù)在不久之后可能還會(huì)再被本進(jìn)程或其它進(jìn)程訪問 (共享資源 )，因而并不立即將該緩沖區(qū) A中的數(shù)據(jù)寫入磁盤，而是將它掛在空閑緩沖區(qū)隊(duì)列的末尾。隨著空閑緩沖區(qū)的使用，緩沖區(qū)也緩緩?fù)耙苿?dòng)，直至移到空閑緩沖隊(duì)列之首。當(dāng)再有進(jìn)程申請(qǐng)到該緩沖區(qū)時(shí)，才將該緩沖區(qū)中的數(shù)據(jù)寫入磁盤，而把該緩沖區(qū)作為空閑緩沖區(qū)分配出去。當(dāng)該緩沖區(qū) A仍在隊(duì)列中時(shí)，任何訪問該數(shù)據(jù)的進(jìn)程，都可直接讀出其中的數(shù)據(jù)而不必去訪問磁盤。 OS 3． 優(yōu)化物理塊的分布 如果將一個(gè)文件的多個(gè)物理塊安排得過于分散，會(huì)增加磁頭的移動(dòng)距離。 位示圖方式：將同屬于一個(gè)文件的盤塊安排在同一條磁道上或相鄰的磁道上是十分容易的事。 線性表 (鏈 )法：將在同一條磁道上的若干個(gè)盤塊組成一簇，例如，一簇包括 4個(gè)盤塊，在分配存儲(chǔ)空間時(shí)，以簇為單位進(jìn)行分配。 OS 4． 虛擬盤 所謂虛擬盤，是指利用內(nèi)存空間去仿真磁盤，又稱為RAM盤。該盤的設(shè)備驅(qū)動(dòng)程序也可以接受所有標(biāo)準(zhǔn)的磁盤操作，但這些操作的執(zhí)行，不是在磁盤上而是在內(nèi)存中。這些對(duì)用戶都是透明的。 虛擬盤的主要問題是：它是易失性存儲(chǔ)器，故一旦系統(tǒng)或電源發(fā)生故障，或系統(tǒng)再啟動(dòng)時(shí)，原來保存在虛擬盤中的數(shù)據(jù)將會(huì)丟失。 虛擬盤與磁盤高速緩存的主要區(qū)別在于 : 虛擬盤中的內(nèi)容完全由用戶控制，而高速磁盤緩存中的內(nèi)容則是由 OS控制的。 OS 廉價(jià)磁盤冗余陣列 1． 并行交叉存取 為了提高對(duì)磁盤的訪問速度，已把在大、中型機(jī)中應(yīng)用的交叉存取 (Interleave)技術(shù)應(yīng)用到了磁盤存儲(chǔ)系統(tǒng)中。在該系統(tǒng)中，有多臺(tái)磁盤驅(qū)動(dòng)器，系統(tǒng)將每一盤塊中的數(shù)據(jù)分為若干個(gè)子盤塊數(shù)據(jù)，再把每一個(gè)子盤塊的數(shù)據(jù)分別存儲(chǔ)到各個(gè)不同磁盤中的相同位置上。 在以后，當(dāng)要將一個(gè)盤塊的數(shù)據(jù)傳送到內(nèi)存時(shí)，采取并行傳輸方式，將各個(gè)盤塊中的子盤塊數(shù)據(jù)同時(shí)向內(nèi)存中傳輸，從而使傳輸時(shí)間大大減少。 OS 圖 529 磁盤并行交叉存取方式 1 2 3…NOS 2． RAID的分級(jí) RAID在剛被推出時(shí) ， 是分成 6級(jí)的 ， 即 RAID 0級(jí)至 RAID 5級(jí) ， 后來又增加了 RAID 6級(jí)和 RAID 7級(jí) 。 (1) RAID 0級(jí)。本級(jí)僅提供了并行交叉存取。它雖能有效地提高磁盤 I/O速度，但并無冗余校驗(yàn)功能，致使磁盤系統(tǒng)的可靠性不好。只要陣列中有一個(gè)磁盤損壞，便會(huì)造成不可彌補(bǔ)的數(shù)據(jù)丟失，故較少使用。 OS (2) RAID 1級(jí) 。 它具有磁盤鏡像功能 ， 例如 ， 當(dāng)磁盤陣列中具有 8個(gè)盤時(shí) ， 可利用其中 4個(gè)作為數(shù)據(jù)盤 ， 另外 4 個(gè)作為鏡像盤 ， 在每次訪問磁盤時(shí) ， 可利用并行讀 、 寫特性 ， 將數(shù)據(jù)分塊同時(shí)寫入主盤和鏡像盤 。 故其比傳統(tǒng)的鏡像盤速度快 ， 但其磁盤容量的利用率只有 50%， 它是以犧牲磁盤容量為代價(jià)的 。 (3) RAID 3級(jí)。這是具有并行傳輸功能的磁盤陣列。它利用一臺(tái)奇偶校驗(yàn)盤來完成數(shù)據(jù)的校驗(yàn)功能，比起磁盤鏡像，它減少了所需要的冗余磁盤數(shù)。例如，當(dāng)陣列中只有 7個(gè)盤時(shí)，可利用 6個(gè)盤作數(shù)據(jù)盤，一個(gè)盤作校驗(yàn)盤。磁盤的利用率為 6/7。RAID 3級(jí)經(jīng)常用于科學(xué)計(jì)算和圖像處理。 OS (4) RAID 5級(jí) 。 這是一種具有獨(dú)立傳送功能的磁盤陣列 。 每個(gè)驅(qū)動(dòng)器都各有自己獨(dú)立的數(shù)據(jù)通路 ， 獨(dú)立地進(jìn)行讀/寫 ， 且無專門的校驗(yàn)盤 。 用來進(jìn)行糾錯(cuò)的校驗(yàn)信息 ， 是以螺旋 (Spiral)方式散布在所有數(shù)據(jù)盤上 。 RAID 5級(jí)常用于I/O較頻繁的事務(wù)處理中 。 (5) RAID 6級(jí)和 RAID 7級(jí)。這是強(qiáng)化了的 RAID。在RAID 6級(jí)的陣列中，設(shè)置了一個(gè)專用的、可快速訪問的異步校驗(yàn)盤。該盤具有獨(dú)立的數(shù)據(jù)訪問通路，具有比 RAID 3級(jí)及RAID 5級(jí)更好的性能，但其性能改進(jìn)得很有限，且價(jià)格昂貴。RAID 7級(jí)是對(duì) RAID 6級(jí)的改進(jìn)，在該陣列中的所有磁盤，都具有較高的傳輸速率和優(yōu)異的性能，是目前最高檔次的磁盤陣列，但其價(jià)格也較高。 OS 3． RAID的優(yōu)點(diǎn) (1) 可靠性高 。 RAID最大的特點(diǎn)就是它的高可靠性 。 除了 RAID 0級(jí)外 ， 其余各級(jí)都采用了容錯(cuò)技術(shù) 。 (2) 磁盤 I/O速度高 。 由于磁盤陣列可采取并行交叉存取方式 ， 故可將磁盤 I/O速度提高 N1倍 (N為磁盤數(shù)目 )。 或者說 ， 磁盤陣列可將磁盤 I/O速度提高數(shù)倍至數(shù)十倍 。 (3) 性能 /價(jià)格比高。利用 RAID技術(shù)來實(shí)現(xiàn)大容量高速存儲(chǔ)器時(shí)，其體積與具有相同容量和速度的大型磁盤系統(tǒng)相比，只是后者的 1/3，價(jià)格也只是后者的 1/3，且可靠性高。