1、5.4緩沖技術(shù)5.4.1 單緩沖 5.4.2 雙緩沖 5.4.3 多緩沖5.4緩沖技術(shù)(1) 引入緩沖技術(shù)的目的 改善中央處理器與外圍設(shè)備之間速度不配的矛盾， 協(xié)調(diào)邏輯記錄大小與物理記錄大小不一致， 提高CPU和I/O設(shè)備的并行性。緩沖技術(shù)(2)緩沖技術(shù)實(shí)現(xiàn)基本思想 進(jìn)程執(zhí)行寫操作輸出數(shù)據(jù)時(shí)，向系統(tǒng)申請一個(gè)緩沖區(qū)，若為順序?qū)懻埱?，則不斷把數(shù)據(jù)填到緩沖區(qū)，直到被裝滿。此后，進(jìn)程繼續(xù)它的計(jì)算，系統(tǒng)將緩沖區(qū)內(nèi)容寫到I/O設(shè)備上。 進(jìn)程執(zhí)行操作輸入數(shù)據(jù)時(shí)，向系統(tǒng)申請一個(gè)緩沖區(qū)，系統(tǒng)將一個(gè)物理記錄的內(nèi)容讀到緩沖區(qū)，根據(jù)進(jìn)程要求，把當(dāng)前需要的邏輯記錄從緩沖區(qū)中選出并傳送給進(jìn)程。 在輸出數(shù)據(jù)時(shí)，只有在系統(tǒng)還

2、來不及騰空緩沖而進(jìn)程又要寫數(shù)據(jù)時(shí)，它才需要等待； 在輸入數(shù)據(jù)時(shí)，僅當(dāng)緩沖區(qū)空而進(jìn)程又要從中讀取數(shù)據(jù)時(shí)，它才被迫等待。 5.4.1 單緩沖 對于塊設(shè)備,單緩沖機(jī)制如下工作： C為數(shù)據(jù)計(jì)算時(shí)間，T為外設(shè)與緩沖區(qū)傳輸時(shí)間，M為用戶區(qū)與緩沖區(qū)傳輸時(shí)間， 數(shù)據(jù)處理時(shí)間約為maxC，T+M， 對于字符設(shè)備,單緩沖機(jī)制如下工作： 緩沖區(qū)可存放一行數(shù)據(jù)。5.4.2 雙緩沖(1) 輸入數(shù)據(jù)時(shí)，首先填滿緩沖區(qū)1,操作系統(tǒng)可從緩沖區(qū)1把數(shù)據(jù)送到用戶進(jìn)程區(qū),用戶進(jìn)程便可對數(shù)據(jù)進(jìn)行加工計(jì)算;與此同時(shí)，輸入設(shè)備填充緩沖區(qū)2 當(dāng)緩沖區(qū)1空出后，輸入設(shè)備再次向緩沖區(qū)1輸入。操作系統(tǒng)又可把緩沖區(qū)2的數(shù)據(jù)傳送到用戶進(jìn)程區(qū),用戶進(jìn)

3、程開始加工緩沖2的數(shù)據(jù)。 雙緩沖(2) 傳輸和處理一塊的時(shí)間(1) 如果計(jì)算時(shí)間CT，當(dāng)上一塊數(shù)據(jù)計(jì)算完畢后，需把一個(gè)緩沖區(qū)中的數(shù)據(jù)傳送到用戶區(qū)，花費(fèi)時(shí)間為M，再對這塊數(shù)據(jù)進(jìn)行計(jì)算，花費(fèi)時(shí)間為C，所以，一塊數(shù)據(jù)的傳輸和處理時(shí)間為C+M、即max(C,T)+M，這種情況下進(jìn)程不必要等待I/O。5.4.3 多緩沖(1) 操作系統(tǒng)從主存區(qū)域中分配一組緩沖區(qū)組成循環(huán)緩沖，每個(gè)緩沖區(qū)的大小等于物理記錄的大小。多緩沖的緩沖區(qū)是系統(tǒng)的公共資源，可供各個(gè)進(jìn)程共享，并由系統(tǒng)統(tǒng)一分配和管理。 緩沖區(qū)可用途分為：輸入緩沖區(qū)，處理緩沖區(qū)和輸出緩沖區(qū)。 多緩沖(2) Unix I/O字符緩存隊(duì)列5.4.4緩沖區(qū)高速緩存

4、 (1) 內(nèi)核建立數(shù)據(jù)緩沖區(qū)高速緩存，專門用于保存最近被使用過的磁盤數(shù)據(jù)塊。 數(shù)據(jù)緩沖區(qū)高速緩存實(shí)現(xiàn)思想： 1 當(dāng)請求從指定文件讀寫數(shù)據(jù)時(shí)，給定設(shè)備號和盤塊號，必須能快速查詢該數(shù)據(jù)塊是否在高速緩存中，如果在的話，是在哪個(gè)緩沖區(qū)并能獲得其內(nèi)容； 2高速緩存中的每個(gè)緩沖區(qū)鏈表都有一個(gè)緩沖控制塊，包含：邏輯設(shè)備號、盤塊號、高速緩存虛擬地址、數(shù)據(jù)所屬文件描述符、數(shù)據(jù)在文件內(nèi)的位移等等；如果數(shù)據(jù)塊不在高速緩存中，則需要從磁盤上讀數(shù)據(jù)，并將其緩沖起來，系統(tǒng)采用合適的算法把盡可能多的數(shù)據(jù)保存在緩沖區(qū)高速緩存。 緩沖區(qū)高速緩存 (2) 3向磁盤上寫的數(shù)據(jù)也被暫存于數(shù)據(jù)緩沖區(qū)高速緩存中，以供回寫磁盤之前再次使用

5、。內(nèi)核還會判定數(shù)據(jù)是否真的需要回寫，或數(shù)據(jù)是否很快就要被回寫，盡量采用延遲寫來減少I/O次數(shù)。 4當(dāng)有文件關(guān)閉或撤銷時(shí)，可采用策略(如LRU)把單獨(dú)的緩沖區(qū)鏈在一起，于是，最不可能被再次訪問的緩沖區(qū)將被最先重用。 5 提供一組高速緩存操作，為文件驅(qū)動(dòng)程序?qū)崿F(xiàn)讀寫文件數(shù)據(jù)。5.5 驅(qū)動(dòng)調(diào)度技術(shù)(1)5.5.1 存儲設(shè)備的物理結(jié)構(gòu) 5.5.2 循環(huán)排序 5.5.3 優(yōu)化分布5.5.4 搜查定位 5.5.5 獨(dú)立磁盤冗余陣列 5.5.6 提高磁盤I/O速度的一些方法 驅(qū)動(dòng)調(diào)度技術(shù)(2) 驅(qū)動(dòng)調(diào)度:能按最佳次序執(zhí)行訪問請求的調(diào)度。相應(yīng)有驅(qū)動(dòng)調(diào)度算法。 驅(qū)動(dòng)調(diào)度能減少為若干個(gè)I/O請求服務(wù)所需的總時(shí)間，

6、提高系統(tǒng)效率、除了I/O請求的優(yōu)化排序外，信息在輔助存儲器上的排列方式，存儲空間分配方法都能影響存取訪問速度。5.5.1 存儲設(shè)備的物理結(jié)構(gòu)(1) 順序存取存儲設(shè)備是嚴(yán)格依賴信息的物理位置進(jìn)行定位和讀寫的存儲設(shè)備 具有存儲容量大、穩(wěn)定可靠、卷可裝卸和便于保存等優(yōu)點(diǎn) 始點(diǎn)塊1間隙塊2間隙塊3間隙塊i間隙塊i+1末點(diǎn) 磁頭(正走,反走,正讀,反讀,正寫,反寫,倒帶)存儲設(shè)備的物理結(jié)構(gòu)(2)直接存取存儲設(shè)備 磁盤是一種直接(隨機(jī))存取存儲設(shè)備。每個(gè)物理記錄有確定的位置和唯一的地址，存取任何一個(gè)物理塊所需的時(shí)間幾乎不依賴于此信息的位置。 訪問磁盤記錄參數(shù)：柱面號、磁頭號、塊號5.5.2循環(huán)排序(1)

7、考慮磁道保存4個(gè)記錄的旋轉(zhuǎn)型設(shè)備，假定收到四個(gè)I/O請求。 請求次序 記錄號 （1） 讀記錄4 （2） 讀記錄3 （3） 讀記錄2 （4） 讀記錄1循環(huán)排序(2)多種I/O請求排序方法 方法1：按照I/O請求次序讀記錄4、3、2、1，平均用1/2周定位，再加上1/4周讀出記錄，總處理時(shí)間等于3周，即60毫秒。 方法2：如果次序?yàn)樽x記錄1、2、3、4。總處理時(shí)間等于1.5周，即30毫秒。 方法3：如果知道當(dāng)前讀位置是記錄3，則采用次序?yàn)樽x記錄4、1、2、3?？偺幚頃r(shí)間等于周，即20毫秒。5.5.3 優(yōu)化分布(1) 信息在存儲空間的排列方式會影響存取等待時(shí)間。考慮10個(gè)邏輯記錄A，B，J被存于旋轉(zhuǎn)

8、型設(shè)備上，每道存放10個(gè)記錄，每塊需2毫秒，安排如下： 物理塊 邏輯紀(jì)錄 1-10 A-J 處理10個(gè)記錄的總時(shí)間(未優(yōu)化) 10毫秒(移動(dòng)到記錄A的平均時(shí)間)+ 2毫秒(讀記錄A)+4毫秒(處理記錄A)+916毫秒(訪問下一記錄) +2毫秒(讀記錄)+4毫秒(處理記錄) 214毫秒 優(yōu)化分布(2)按照下面方式對信息優(yōu)化分布物理塊 邏輯紀(jì)錄1 A2 H3 E4 B5 I6 F7 C8 J9 G10 D優(yōu)化分布(3)處理10個(gè)記錄的總時(shí)間為 10毫秒(移動(dòng)到記錄A的平均時(shí)間)+102毫秒（讀記錄）4毫秒（處理記錄） =70毫秒5.5.4 搜查定位(1) 移臂調(diào)度有若干策略 (1)“電梯調(diào)度”算法

9、 (2)“最短查找時(shí)間優(yōu)先”算法 (3)“掃描”算法 (4)“分步掃描”算法 (5)“單向掃描”算法 搜查定位(2) “電梯調(diào)度”算法 電梯調(diào)度算法有等待請求?結(jié)束請求與當(dāng)前 柱面相同?處理有最近塊號的請求啟動(dòng)C CC C是向里或向外移?是否否向外向里有比當(dāng)前柱面小的請求?改變移動(dòng)方向A A有比當(dāng)前柱面大的請求?改變移動(dòng)方向否否處理大于當(dāng)前柱面號請求中柱面號最小的請求處理小于當(dāng)前柱面號請求中的柱面號最大的請求移動(dòng)磁頭到指定柱面，登記當(dāng)前位置啟動(dòng)C CB BB BA A搜查定位(4) “最短查找時(shí)間優(yōu)先最短查找時(shí)間優(yōu)先”算法算法 本算法考慮了各個(gè)請求之間的區(qū)別，總是先執(zhí)行查找時(shí)間最短的那個(gè)磁盤請

10、求，從而，較“先來先服務(wù)”算法有較好的尋道性能。 搜查定位(5) “掃描掃描”算法算法 磁盤臂每次沿一個(gè)方向移動(dòng)，掃過所有柱面，遇到最近的I/O請求便進(jìn)行處理，直到最后一個(gè)柱面后，再向相反方向移動(dòng)回來。 搜查定位(6) “分步掃描分步掃描 ” ”算法算法 為避免掃描算法進(jìn)程重復(fù)請求一為避免掃描算法進(jìn)程重復(fù)請求一個(gè)磁道被個(gè)磁道被“粘住粘住”，將I/O請求分成組，每組不超過N個(gè)請求，每次選一個(gè)組進(jìn)行掃描，處理完一組后再選下一組。 搜查定位(7) “循環(huán)掃描循環(huán)掃描”算法算法 移動(dòng)臂總從0號柱面至最大號柱面順序掃描，然后，直接返回0號柱面重復(fù)進(jìn)行，歸途中不再服務(wù)，構(gòu)成了一個(gè)循環(huán)。 7Linux磁盤調(diào)

11、度算法 Linux 2.4磁盤調(diào)度采用電梯調(diào)度算法。 Linux2.6增加兩種新磁盤調(diào)度算法：最終期限調(diào)度算法和預(yù)期調(diào)度算法。 時(shí)限調(diào)度算法 實(shí)現(xiàn)思想：若任務(wù)到期則可優(yōu)先服務(wù)。 預(yù)期調(diào)度算法實(shí)現(xiàn)思想：在服務(wù)一個(gè)讀請求時(shí)適當(dāng)延時(shí)，看是否有相鄰的請求發(fā)生，如有，馬上服務(wù)。5.5.5 獨(dú)立磁盤冗余陣列(1) 獨(dú)立磁盤冗余陣列是利用一臺磁盤陣列控制器統(tǒng)一管理和控制一組磁盤驅(qū)動(dòng)器,組成一個(gè)速度快 、可靠性高、性能價(jià)格比好的大容量磁盤系統(tǒng)。 RAID填補(bǔ)CPU速度快與磁盤設(shè)備速度慢之間的間隙,其策略是:獨(dú)立磁盤冗余陣列(2) RAID共同特性 RAID是一組物理磁盤驅(qū)動(dòng)器，可被操作系統(tǒng)看作是單一邏輯磁盤驅(qū)

12、動(dòng)器; 數(shù)據(jù)被分布存儲在陣列橫跨的物理驅(qū)動(dòng)器上; 冗余磁盤的作用是保存奇偶校驗(yàn)信息，當(dāng)磁盤出現(xiàn)失誤時(shí)它能確保數(shù)據(jù)的恢復(fù)。 獨(dú)立磁盤冗余陣列(3) Strip0Strip4Strip8Strip12Strip1Strip5Strip9Strip13Strip10Strip3Strip7Strip15Strip10Strip11Strip2Strip6Strip14Strip10RAID Level 0(1) Strip0Strip4Strip8Strip12Strip1Strip5Strip9Strip13Strip10Strip3Strip7Strip15Strip10Strip11Strip

13、2Strip6Strip14Strip10Data mapping for a RAID Level0 ArrayStrip0Strip1Strip2Strip3Strip4Strip5Strip6Strip7Strip8. . . .ArrayManagementsoftware獨(dú)立磁盤冗余陣列(4) RAID level 0(2) RAID level 0(2) RAID Level 1 (Mirrored)Strip0Strip4Strip8Strip12Strip1Strip5Strip9Strip13Strip3Strip7Strip15Strip11Strip2Strip6Stri

14、p14Strip10Strip0Strip4Strip8Strip12Strip1Strip5Strip9Strip13Strip3Strip7Strip15Strip11Strip2Strip6Strip14Strip10獨(dú)立磁盤冗余陣列(5) RAID level 1 RAID level 1 鏡像備份鏡像備份 b0b1b2b3f0(b)f1(b)f2(b)RAID Level 2 (Redundancy through Hamming Code海明校驗(yàn)碼)獨(dú)立磁盤冗余陣列(6) RAID level 2RAID level 2 b0b1b2b3P(b) RAID Level 3 (Bit

15、 interleaved Parity奇偶校驗(yàn)位)獨(dú)立磁盤冗余陣列(7) RAID level 3 RAID level 3 block0block4block8block12block1block5block9block13block3block7block15block11block2block6block14block10P(0-3)P(4-7)90P(8-11)P(12-15)RAID Level 4 (Block level Parity)獨(dú)立磁盤冗余陣列(8) RAID level 4 獨(dú)立磁盤冗余陣列(9) RAID level 5block0block4block8block1

16、2block1block5block9P(12-15)block3P(4-7)block14block10block2block6block13P(8-11)P(0-3)block7Block11Block15block0block4block8block12RAID Level 5 (Block level Distributed parity)5.5.6提高磁盤I/O速度的方法 提前讀:提前把下一塊數(shù)據(jù)讀入緩沖區(qū) 延遲寫：寫出的數(shù)據(jù)先掛到空閑緩沖區(qū)隊(duì)尾，需要這塊分配時(shí)再寫盤。 虛擬盤 ：RAM盤，易失數(shù)據(jù)。5.6 設(shè)備分配 5.6.1 設(shè)備獨(dú)立性5.6.2 設(shè)備分配和設(shè)備分配數(shù)據(jù)結(jié)構(gòu) 5.

17、6.1 設(shè)備獨(dú)立性 通常用戶不指定特定的設(shè)備，而指定邏輯設(shè)備，使得用戶作業(yè)和物理設(shè)備獨(dú)立開來，再通過其它途徑建立邏輯設(shè)備和物理設(shè)備之間的對應(yīng)關(guān)系，稱這種特性為“設(shè)備獨(dú)立性”。 設(shè)備獨(dú)立性帶來的好處 用戶與物理的外圍設(shè)備無關(guān)，系統(tǒng)增減或變更外圍設(shè)備時(shí)程序不必修改；易于對付輸入輸出設(shè)備的故障。5.6.2 設(shè)備分配(1) 從設(shè)備的特性來看，可以把設(shè)備分成獨(dú)占設(shè)備、共享設(shè)備和虛擬設(shè)備三類： 管理和分配外圍設(shè)備的技術(shù)可分成：獨(dú)占方式、共享方式和虛擬方式 。 常用的I/O設(shè)備分配算法 先請求先服務(wù)，優(yōu)先級高者先服務(wù)等。此外，在多進(jìn)程請求I/O設(shè)備分配時(shí)，應(yīng)防止因循環(huán)等待對方所占用的設(shè)備而產(chǎn)生死鎖，應(yīng)預(yù)先進(jìn)

18、行性檢查。設(shè)備分配(2)I/O設(shè)備分配的實(shí)現(xiàn)(1) 設(shè)備分配的數(shù)據(jù)結(jié)構(gòu)：設(shè)備類表和設(shè)備表。 系統(tǒng)中擁有一張?jiān)O(shè)備類表，每類設(shè)備對應(yīng)于表中一欄，包括內(nèi)容有：設(shè)備類、總臺數(shù)、空閑臺數(shù)和設(shè)備表起始地址等。 每一類設(shè)備都有各自的設(shè)備表，用來登記這類設(shè)備中每一臺設(shè)備的狀態(tài)，包含的內(nèi)容有：物理設(shè)備名、邏輯設(shè)備名、占有設(shè)備的進(jìn)程號、已分配/未分配、好/壞等。設(shè)備分配(3)I/O設(shè)備分配的實(shí)現(xiàn)(2) 采用通道結(jié)構(gòu)的系統(tǒng)中，設(shè)備分配的數(shù)據(jù)結(jié)構(gòu)設(shè)置：系統(tǒng)設(shè)備表、通道控制表、控制器控制表和設(shè)備控制表。 系統(tǒng)建立一張系統(tǒng)設(shè)備表，記錄配置在系統(tǒng)中的所有物理設(shè)備的情況。 每個(gè)通道、控制器、設(shè)備各設(shè)置一張表，記錄各自的地址(標(biāo)識符)、狀態(tài)(忙/閑)、等待獲得此部件的進(jìn)程隊(duì)列指針、及一次分配后相互勾鏈的指針，以備分配和執(zhí)行I/O時(shí)使用。5.7 虛擬設(shè)備5.7.1 問題的提出 5.7.2 SPOOLING的設(shè)計(jì)和實(shí)現(xiàn) 5.7.3 SPOOLING應(yīng)用例子 5.7.15.7.1問題的提出 靜態(tài)分配方式是