緩沖技術(shù)55驅(qū)動(dòng)調(diào)度技術(shù)設(shè)備培訓(xùn)課件

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)申請(qǐng)一個(gè)緩沖區(qū)，若為順序?qū)懻?qǐng)求，則不斷把數(shù)據(jù)填到緩沖區(qū)，直到被裝滿。此后，進(jìn)程繼續(xù)它的計(jì)算，系統(tǒng)將緩沖區(qū)內(nèi)容寫到I/O設(shè)備上。進(jìn)程執(zhí)行操作輸入數(shù)據(jù)時(shí)，向系統(tǒng)申請(qǐng)一個(gè)緩沖區(qū)，系統(tǒng)將一個(gè)物理記錄的內(nèi)容讀到緩沖區(qū)，根據(jù)進(jìn)程要求，把當(dāng)前需要的邏輯記錄從緩沖區(qū)中選出并傳送給進(jìn)程。在輸出數(shù)據(jù)時(shí)，只有在系統(tǒng)還來不及騰空緩沖而進(jìn)程又要寫數(shù)據(jù)時(shí)，它才需要等待；在輸入數(shù)據(jù)時(shí)，僅當(dāng)緩沖區(qū)空而進(jìn)程又要從中讀取數(shù)據(jù)時(shí)，它才被迫等待。

第三頁，共五十頁。5.4.1單緩沖

對(duì)于塊設(shè)備,單緩沖機(jī)制如下工作：數(shù)據(jù)處理過程數(shù)據(jù)處理時(shí)間約為max[C，T]+M，

進(jìn)程系統(tǒng)設(shè)備

TMC第四頁，共五十頁。5.4.2雙緩沖(1)

輸入數(shù)據(jù)時(shí)，首先填滿緩沖區(qū)1,操作系統(tǒng)可從緩沖區(qū)1把數(shù)據(jù)送到用戶進(jìn)程區(qū),用戶進(jìn)程便可對(duì)數(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)程開始加工緩沖2的數(shù)據(jù)。第五頁，共五十頁。雙緩沖(2)

傳輸和處理一塊的時(shí)間(1)如果C<T，由于M遠(yuǎn)小于T，在將磁盤上的一塊數(shù)據(jù)傳送到緩沖區(qū)其間，計(jì)算機(jī)已完成將另一個(gè)緩沖區(qū)中的數(shù)據(jù)傳送到用戶區(qū)并對(duì)這塊數(shù)據(jù)進(jìn)行計(jì)算的工作，一塊數(shù)據(jù)的傳輸和處理時(shí)間為T、即max(C,T)，顯然，這種情況下可保證塊設(shè)備連續(xù)工作；第六頁，共五十頁。雙緩沖(3)

傳輸和處理一塊的時(shí)間(2)如果C>T，當(dāng)上一塊數(shù)據(jù)計(jì)算完畢后，需把一個(gè)緩沖區(qū)中的數(shù)據(jù)傳送到用戶區(qū)，花費(fèi)時(shí)間為M，再對(duì)這塊數(shù)據(jù)進(jìn)行計(jì)算，花費(fèi)時(shí)間為C，所以，一塊數(shù)據(jù)的傳輸和處理時(shí)間為C+M、即max(C,T)+M，這種情況下進(jìn)程不必要等待I/O。第七頁，共五十頁。雙緩沖(4)

進(jìn)程系統(tǒng)設(shè)備

(1)C<T，M<<Tmax(C,T)=T，保證設(shè)備連續(xù)工作。(2)C>T,M<<Tmax(C,T)+M=C+M，保證進(jìn)程不等I/O。CMT第八頁，共五十頁。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ū)。第九頁，共五十頁。5.5驅(qū)動(dòng)調(diào)度技術(shù)(1)

5.5.1存儲(chǔ)設(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)度和驅(qū)動(dòng)調(diào)度算法。驅(qū)動(dòng)調(diào)度能減少為若干個(gè)I/O請(qǐng)求服務(wù)所需的總時(shí)間，提高系統(tǒng)效率、除了I/O請(qǐng)求的優(yōu)化排序外，信息在輔助存儲(chǔ)器上的排列方式，存儲(chǔ)空間分配方法都能影響存取訪問速度。第十一頁，共五十頁。5.5.1存儲(chǔ)設(shè)備的物理結(jié)構(gòu)(1)

順序存取存儲(chǔ)設(shè)備是嚴(yán)格依賴信息的物理位置進(jìn)行定位和讀寫的存儲(chǔ)設(shè)備具有存儲(chǔ)容量大、穩(wěn)定可靠、卷可裝卸和便于保存等優(yōu)點(diǎn)■始點(diǎn)塊1間隙塊2間隙塊3間隙塊i間隙塊i+1■末點(diǎn)…………磁頭(正走,反走,正讀,反讀,正寫,反寫,倒帶)第十二頁，共五十頁。存儲(chǔ)設(shè)備的物理結(jié)構(gòu)(2)

直接存取存儲(chǔ)設(shè)備磁盤是一種直接(隨機(jī))存取存儲(chǔ)設(shè)備。每個(gè)物理記錄有確定的位置和唯一的地址，存取任何一個(gè)物理塊所需的時(shí)間幾乎不依賴于此信息的位置。訪問磁盤記錄參數(shù)：柱面號(hào)、磁頭號(hào)、塊號(hào)第十三頁，共五十頁。5.5.2循環(huán)排序(1)

考慮磁道保存4個(gè)記錄的旋轉(zhuǎn)型設(shè)備，假定收到四個(gè)I/O請(qǐng)求。請(qǐng)求次序記錄號(hào)（1）讀記錄4（2）讀記錄3（3）讀記錄2（4）讀記錄11234第十四頁，共五十頁。循環(huán)排序(2)

多種I/O請(qǐng)求排序方法

?方法1：按照I/O請(qǐng)求次序讀記錄4、3、2、1，平均用1/2周定位，再加上1/4周讀出記錄，總處理時(shí)間等于3周，即60毫秒。

?方法2：如果次序?yàn)樽x記錄1、2、3、4?？偺幚頃r(shí)間等于1.5周，即30毫秒。

?方法3：如果知道當(dāng)前讀位置是記錄3，則采用次序?yàn)樽x記錄4、1、2、3。總處理時(shí)間等于１周，即20毫秒。第十五頁，共五十頁。5.5.3優(yōu)化分布(1)

考慮10個(gè)邏輯記錄A，B……，J被存于旋轉(zhuǎn)型設(shè)備上，每道存放10個(gè)記錄，安排如下：

物理塊邏輯紀(jì)錄1-10A-J(ABCDE…..)處理10個(gè)記錄的總時(shí)間10毫秒(移動(dòng)到記錄A的平均時(shí)間)+2毫秒(讀記錄A)+4毫秒(處理記錄A)+9×[16毫秒(訪問下一記錄)+2毫秒(讀記錄)+4毫秒(處理記錄)]＝214毫秒

第十六頁，共五十頁。優(yōu)化分布(2)

按照下面方式對(duì)信息優(yōu)化分布

物理塊邏輯紀(jì)錄1A2H3E4B5I6F7C8J9G10D第十七頁，共五十頁。優(yōu)化分布(3)

處理10個(gè)記錄的總時(shí)間為10毫秒(移動(dòng)到記錄A的平均時(shí)間)+10×[2毫秒（讀記錄）×4毫秒（處理記錄）]=70毫秒第十八頁，共五十頁。5.5.4交替地址

每個(gè)記錄重復(fù)記錄在設(shè)備的多個(gè)區(qū)域，讀相同的數(shù)據(jù)，有幾個(gè)交替地址，也稱為多重副本或折迭。成功與否取決于下列因素：數(shù)據(jù)記錄總是讀出使用，不需修改寫入；數(shù)據(jù)記錄占用的存儲(chǔ)空間總量不太大；數(shù)據(jù)使用極為頻繁。第十九頁，共五十頁。5.5.5搜查定位(1)

移臂調(diào)度有若干策略(1)“電梯調(diào)度”算法(2)“最短查找時(shí)間優(yōu)先”算法(3)“掃描”算法(4)“分步掃描”算法(5)“單向掃描”算法

第二十頁，共五十頁。搜查定位(2)

“電梯調(diào)度”算法

電梯調(diào)度算法有等待請(qǐng)求?結(jié)束請(qǐng)求與當(dāng)前柱面相同?處理有最近塊號(hào)的請(qǐng)求啟動(dòng)CC是向里或向外移?是否否向外向里有比當(dāng)前柱面小的請(qǐng)求?改變移動(dòng)方向A有比當(dāng)前柱面大的請(qǐng)求?改變移動(dòng)方向否否處理大于當(dāng)前柱面號(hào)請(qǐng)求中柱面號(hào)最小的請(qǐng)求處理小于當(dāng)前柱面號(hào)請(qǐng)求中的柱面號(hào)最大的請(qǐng)求移動(dòng)磁頭到指定柱面，登記當(dāng)前位置啟動(dòng)CBBA第二十一頁，共五十頁。搜查定位(4)

“最短查找時(shí)間優(yōu)先”算法

本算法考慮了各個(gè)請(qǐng)求之間的區(qū)別，總是先執(zhí)行查找時(shí)間最短的那個(gè)磁盤請(qǐng)求，從而，較“先來先服務(wù)”算法有較好的尋道性能。

第二十二頁，共五十頁。搜查定位(5)

“掃描”算法

磁盤臂每次沿一個(gè)方向移動(dòng)，掃過所有柱面，遇到最近的I/O請(qǐng)求便進(jìn)行處理，直到最后一個(gè)柱面后，再向相反方向移動(dòng)回來。

第二十三頁，共五十頁。搜查定位(6)

“分步掃描”算法

將I/O請(qǐng)求分成組，每組不超過N個(gè)請(qǐng)求，每次選一個(gè)組進(jìn)行掃描，處理完一組后再選下一組。第二十四頁，共五十頁。搜查定位(7)

“循環(huán)掃描”算法

移動(dòng)臂總從0號(hào)柱面至最大號(hào)柱面順序掃描，然后，直接返回0號(hào)柱面重復(fù)進(jìn)行，歸途中不再服務(wù)，構(gòu)成了一個(gè)循環(huán)。

第二十五頁，共五十頁。5.5.6獨(dú)立磁盤冗余陣列(1)

獨(dú)立磁盤冗余陣列是利用一臺(tái)磁盤陣列控制器統(tǒng)一管理和控制一組磁盤驅(qū)動(dòng)器,組成一個(gè)速度快、可靠性高、性能價(jià)格比好的大容量磁盤系統(tǒng)。RAID填補(bǔ)CPU速度快與磁盤設(shè)備速度慢之間的間隙,其策略是:第二十六頁，共五十頁。獨(dú)立磁盤冗余陣列(2)

RAID共同特性

①RAID是一組物理磁盤驅(qū)動(dòng)器，可被操作系統(tǒng)看作是單一邏輯磁盤驅(qū)動(dòng)器;②數(shù)據(jù)被分布存儲(chǔ)在陣列橫跨的物理驅(qū)動(dòng)器上;③冗余磁盤的作用是保存奇偶校驗(yàn)信息，當(dāng)磁盤出現(xiàn)失誤時(shí)它能確保數(shù)據(jù)的恢復(fù)。第二十七頁，共五十頁。

獨(dú)立磁盤冗余陣列(3)

Strip0Strip4Strip8Strip12Strip1Strip5Strip9Strip13Strip10Strip3Strip7Strip15Strip10Strip11Strip2Strip6Strip14Strip10RAIDLevel0(1)第二十八頁，共五十頁。

Strip0Strip4Strip8Strip12Strip1Strip5Strip9Strip13Strip10Strip3Strip7Strip15Strip10Strip11Strip2Strip6Strip14Strip10DatamappingforaRAIDLevel0ArrayStrip0Strip1Strip2Strip3Strip4Strip5Strip6Strip7Strip8...ArrayManagementsoftware獨(dú)立磁盤冗余陣列(4)RAIDlevel0(2)第二十九頁，共五十頁。

RAIDLevel1(Mirrored)Strip0Strip4Strip8Strip12Strip1Strip5Strip9Strip13Strip3Strip7Strip15Strip11Strip2Strip6Strip14Strip10Strip0Strip4Strip8Strip12Strip1Strip5Strip9Strip13Strip3Strip7Strip15Strip11Strip2Strip6Strip14Strip10獨(dú)立磁盤冗余陣列(5)

RAIDlevel1第三十頁，共五十頁。

b0b1b2b3f0(b)f1(b)f2(b)RAIDLevel2(RedundancythroughHammingCode)獨(dú)立磁盤冗余陣列(6)

RAIDlevel2第三十一頁，共五十頁。

b0b1b2b3P(b)RAIDLevel3(BitinterleavedParity)獨(dú)立磁盤冗余陣列(7)RAIDlevel3第三十二頁，共五十頁。

block0block4block8block12block1block5block9block13block3block7block15block11block2block6block14block10P(0-3)P(4-7)90P(8-11)P(12-15)RAIDLevel4(BlocklevelParity)獨(dú)立磁盤冗余陣列(8)

RAIDlevel4

第三十三頁，共五十頁。

獨(dú)立磁盤冗余陣列(9)

RAIDlevel5block0block4block8block12block1block5block9P(12-15)block3P(4-7)block14block10block2block6block13P(8-11)P(0-3)block7Block11Block15block0block4block8block12RAIDLevel5(BlocklevelDistributedparity)第三十四頁，共五十頁。5.5.6提高磁盤I/O速度的方法

提前讀延遲寫虛擬盤

UNIX/Linux提供兩種讀盤和三種寫盤方式：正常讀-把磁盤塊信息塊讀入主存緩沖區(qū)；提前讀-讀磁盤當(dāng)前塊時(shí)，下一磁盤塊也讀入主存緩沖區(qū)；正常寫-把主存緩沖區(qū)中的信息寫到磁盤塊，且寫進(jìn)程應(yīng)等待寫操作完成；異步寫-寫進(jìn)程無需等待寫盤結(jié)束就可返回工作；延遲寫-僅在緩沖區(qū)首部設(shè)置延遲寫標(biāo)志，然后，釋放此緩沖區(qū)，并把該緩沖區(qū)鏈入空閑緩沖區(qū)鏈表的尾部，當(dāng)其他進(jìn)程申請(qǐng)到該緩沖區(qū)時(shí)，才真正把緩沖區(qū)信息寫回磁盤塊。第三十五頁，共五十頁。5.6設(shè)備分配

5.6.1設(shè)備獨(dú)立性5.6.2設(shè)備分配和設(shè)備分配數(shù)據(jù)結(jié)構(gòu)

第三十六頁，共五十頁。5.6.1設(shè)備獨(dú)立性

通常用戶不指定特定的設(shè)備，而指定邏輯設(shè)備，使得用戶作業(yè)和物理設(shè)備獨(dú)立開來，再通過其它途徑建立邏輯設(shè)備和物理設(shè)備之間的對(duì)應(yīng)關(guān)系，稱這種特性為“設(shè)備獨(dú)立性”。設(shè)備獨(dú)立性帶來的好處用戶與物理的外圍設(shè)備無關(guān)，系統(tǒng)增減或變更外圍設(shè)備時(shí)程序不必修改；易于對(duì)付輸入輸出設(shè)備的故障。第三十七頁，共五十頁。5.6.2設(shè)備分配(1)

從設(shè)備的特性來看，可以把設(shè)備分成獨(dú)占設(shè)備、共享設(shè)備和虛擬設(shè)備三類：相應(yīng)的管理和分配外圍設(shè)備的技術(shù)可分成：獨(dú)占方式、共享方式和虛擬方式。常用的I/O設(shè)備分配算法先請(qǐng)求先服務(wù)，優(yōu)先級(jí)高者先服務(wù)等。此外，在多進(jìn)程請(qǐng)求I/O設(shè)備分配時(shí)，應(yīng)防止因循環(huán)等待對(duì)方所占用的設(shè)備而產(chǎn)生死鎖，應(yīng)預(yù)先進(jìn)行性檢查。第三十八頁，共五十頁。設(shè)備分配(2)

I/O設(shè)備分配的實(shí)現(xiàn)(1)設(shè)備分配的數(shù)據(jù)結(jié)構(gòu)：設(shè)備類表和設(shè)備表。系統(tǒng)中擁有一張?jiān)O(shè)備類表，每類設(shè)備對(duì)應(yīng)于表中一欄，包括內(nèi)容有：設(shè)備類、總臺(tái)數(shù)、空閑臺(tái)數(shù)和設(shè)備表起始地址等。每一類設(shè)備都有各自的設(shè)備表，用來登記這類設(shè)備中每一臺(tái)設(shè)備的狀態(tài)，包含的內(nèi)容有：物理設(shè)備名、邏輯設(shè)備名、占有設(shè)備的進(jìn)程號(hào)、已分配/未分配、好/壞等。第三十九頁，共五十頁。設(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)識(shí)符)、狀態(tài)(忙/閑)、等待獲得此部件的進(jìn)程隊(duì)列指針、及一次分配后相互勾鏈的指針，以備分配和執(zhí)行I/O時(shí)使用。第四十頁，共五十頁。5.7虛擬設(shè)備5.7.1問題的提出5.7.2SPOOLING的設(shè)計(jì)和實(shí)現(xiàn)5.7.3SPOOLING應(yīng)用例子第四十一頁，共五十頁。5.7.1問題的提出

靜態(tài)分配方式是不利于提高系統(tǒng)效率采用脫機(jī)外圍設(shè)備操作（SPOOLING）聯(lián)機(jī)同時(shí)外圍設(shè)備操作(又稱作假脫機(jī)操作)第四十二頁，共五十頁。5.7.2斯普林系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)(1)

“井”是用作緩沖的存儲(chǔ)區(qū)域，采用井的技術(shù)能調(diào)節(jié)供求之間的矛盾，消除人工干預(yù)帶來的損失?！邦A(yù)輸入程序”“緩輸出程序”“井管理程序”第四十三頁，共五十頁。

預(yù)輸入程序作業(yè)1信息…作業(yè)n信息輸入井作業(yè)1結(jié)果…作業(yè)n結(jié)果輸出井緩輸出程序井管理程序運(yùn)行作業(yè)輸入設(shè)備輸出設(shè)備作業(yè)調(diào)度程序斯普林系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)(2)

SPOOLING組成和結(jié)構(gòu)

第四十四頁，共五十頁。斯普林系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)(3)

輸入井中作業(yè)狀態(tài)

?輸入狀態(tài)：作業(yè)信息正在從輸入設(shè)備上預(yù)輸入；?收容收態(tài)：作業(yè)預(yù)輸入結(jié)束，但未被選中執(zhí)行；?執(zhí)行狀態(tài)：正在執(zhí)行，可讀數(shù)據(jù)也可以寫數(shù)據(jù)；?完成狀態(tài)：作業(yè)已經(jīng)撤離，結(jié)果等待輸出。第四十五頁，共五十頁。斯普林系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)(4)

SPOOLING數(shù)據(jù)結(jié)構(gòu)

?作業(yè)表登記進(jìn)入系統(tǒng)的所有作業(yè)的作業(yè)名、狀態(tài)、預(yù)輸入表位置等信息。預(yù)輸入表每個(gè)用戶作業(yè)有一張用來登記該作業(yè)的各個(gè)文件的情