操作系統(tǒng)精髓與設計原理-第11章IO管理和磁盤調(diào)度.docVIP

第十一章 I/O管理和磁盤調(diào)度 復習題11.1列出并簡單定義執(zhí)行I/O的三種技術(shù)。 可編程I/O：處理器代表進程給I/O模塊發(fā)送給一個I/O命令，該進程進入忙等待，等待操作的完成，然后才可以繼續(xù)執(zhí)行。 中斷驅(qū)動I/O：處理器代表進程向I/O模塊發(fā)送一個I/O命令，然后繼續(xù)執(zhí)行后續(xù)指令，當I/O模塊完成工作后，處理器被該模塊中斷。如果該進程不需要等待I/O完成，則后續(xù)指令可以仍是該進程中的指令，否則，該進程在這個中斷上被掛起，處理器執(zhí)行其他工作。 直接存儲器訪問（DMA）：一個DMA模塊控制主存和I/O模塊之間的數(shù)據(jù)交換。為傳送一塊數(shù)據(jù)，處理器給DMA模塊發(fā)送請求，只有當整個數(shù)據(jù)塊傳送完成后，處理器才被中斷。11.2邏輯I/O和設備I/O有什么區(qū)別？ 邏輯I/O：邏輯I/O模塊把設備當作一個邏輯資源來處理，它并不關(guān)心實際控制設備的細節(jié)。邏輯I/O模塊代表用戶進程管理的一般I/O功能，允許它們根據(jù)設備標識符以及諸如打開、關(guān)閉、讀、寫之類的簡單命令與設備打交道。 設備I/O：請求的操作和數(shù)據(jù)（緩沖的數(shù)據(jù)、記錄等）被轉(zhuǎn)換成適當?shù)腎/O指令序列、通道命令和控制器命令。可以使用緩沖技術(shù)，以提高使用率。11.3面向塊的設備和面向流的設備有什么區(qū)別？請舉例說明。 面向塊的設備將信息保存在塊中，塊的大小通常是固定的，傳輸過程中一次傳送一塊。通常可以通過塊號訪問數(shù)據(jù)。磁盤和磁帶都是面向塊的設備。 面向流的設備以字節(jié)流的方式輸入輸出數(shù)據(jù)，其末使用塊結(jié)構(gòu)。終端、打印機通信端口、鼠標和其他指示設備以及大多數(shù)非輔存的其他設備，都屬于面向流的設備。11.4為什么希望用雙緩沖區(qū)而不是單緩沖區(qū)來提高I/O的性能？ 雙緩沖允許兩個操作并行處理，而不是依次處理。典型的，在一個進程往一個緩沖區(qū)中傳送數(shù)據(jù)（從這個緩沖區(qū)中取數(shù)據(jù)）的同時，操作系統(tǒng)正在清空（或者填充）另一個緩沖區(qū)。11.5在磁盤讀或?qū)憰r有哪些延遲因素？ 尋道時間，旋轉(zhuǎn)延遲，傳送時間11.6簡單定義圖11.7中描述的磁盤調(diào)度策略。FIFO:按照先來先服務的順序處理隊列中的項目。SSTF:選擇使磁頭臂從當前位置開始移動最少的磁盤I/O請求。SCAN:磁頭臂僅僅沿一個方向移動，并在途中滿足所有未完成的請求，直到它到達這個方向上最后一個磁道，或者在這個方向上沒有其他請求為止。接著反轉(zhuǎn)服務方向，沿相反方向掃描，同樣按順序完成所有請求。C-SCAN:類似于SCAN，11.7簡單定義圖7層RAID。 0：非冗余1：被鏡像；每個磁盤都有一個包含相同數(shù)據(jù)的鏡像磁盤。2：通過漢明碼實現(xiàn)冗余；對每個數(shù)據(jù)磁盤中的相應都計算一個錯誤校正碼，并且這個碼位保存在多個奇偶校驗磁盤中相應的文件。3：交錯位奇偶校驗；類似于第二層，不同之處在于RAID3為所有數(shù)據(jù)磁盤中同一位置的位的集合計算一個簡單的奇偶校驗位，而不是錯誤校正碼。4：交錯塊分布奇偶校驗；對每個數(shù)據(jù)磁盤中相應的條帶計算一個逐位奇偶。5：交錯塊分布奇偶校驗；類似于第四層，但把奇偶校驗條帶分布在所有磁盤中。6：交錯塊雙重分布奇偶校驗；兩種不同的奇偶校驗計算保存在不同磁盤的不同塊中。11.8典型的磁盤扇區(qū)大小是多少？ 512比特習題11.1考慮一個程序訪問一個I/O設備，并比較無緩沖的I/O和使用緩沖區(qū)的I/O。說明使用緩沖區(qū)最多可以減少2倍的運行時間。如果計算的時間正好等于它的I/O時間（它是最佳環(huán)境），操作者和外圍設備同時運行。如果單獨運行，只要花費他們的一半時間，設C是整個程序的計算時間，T為所要求總的I/O時間，因而寄存器最好的運行時間是 max(C,T)，不需要寄存器的運行時間是C+T，顯然（(C+T)/2）max(C,T)(C+T).11.2把習題11.1的結(jié)論推廣到訪問n個設備的程序中。 最佳比是（n+1）n11.3使用與表11.2類似的方式，分析下列磁道請求：27，129，110，186，147，41，10，64，120。假設磁頭最初定位在磁道100處，并且沿著磁道號減小的方向移動。假設磁頭沿著磁道增大的方向移動，請給出同樣的分析。FIFOSSTFSCANC-SCAN下一個被訪問的磁道27 129 110 186 147 41 10 64 120平均尋道長度橫跨的磁道數(shù) 73 102 19 76 39 106 31 54 56 61.8下一個被訪問的磁道 110 120 129 147 186 64 41 27 10平均尋道長度橫跨的磁道數(shù) 10 10 9 18 39 122 23 14 17 29.1下一個被訪問的磁道 64 41 27 10 110 120 129 147 186平均尋道長度橫跨的磁道數(shù) 36 23 14 17 100 10 9 18 39 29.6下一個被訪問的磁道 64 41 27 10 186 147 129 120 110平均尋道長度橫跨的磁道數(shù) 36 23 14 17 176 39 18 9 10 38如果磁頭沿著增大的方向，只有SCAN和C-SCAN的結(jié)果有變化SCANC-SCAN下一個被訪問的磁道 110 120 129 147 186 64 41 27 10平均尋道長度橫跨的磁道數(shù) 10 10 9 18 39 122 23 14 17 29.1下一個被訪問的磁道 110 120 129 147 186 10 27 41 64平均尋道長度橫跨的磁道數(shù) 10 10 9 18 39 176 17 14 23 35.111.4考慮一個磁盤，有N個磁道，磁道號從0到(N-1)，并且假設請求的扇區(qū)隨機地均勻分布在磁盤上?，F(xiàn)在要計算一次尋道平均跨越的磁道數(shù)。 a.首先，計算當磁頭當前位于磁道t時，尋道長度為j的可能性。提示：這是一個關(guān)于確定所有組合數(shù)目的問題，所有磁道位置作為尋道目標的可能性是相等的。 b.接下來計算尋道長度為K的可能性。提示：這包括所有移動了K個磁道的可能性之和。 c.使用下面計算期望值得公式，計算一次尋道平均跨越的磁道數(shù)目： N-1 EX=iPrx=i i=0 d說明檔N比較大時，一次尋道平均跨越的磁道數(shù)接近N/3. （a）設Pj/t表示位于磁道t，尋道長度為j的概率，知隨機訪問一個任何一個磁道的可能性為相等為1/N，因此我們有Pj/t=1/N,t=N-j;Pj/t=2/N,j-1tN-j.前一種情況下，當前磁道接近于磁盤的兩端。因此只有一個相距j長度的磁道，故為2/N。 （b）令Pk=Pk/t*Pt=1/NPk/t,由（a）可知，取值1/N的有2k個磁道，取值為2/N有（N-k）個， 所以有 Pk=（2k/N+2(N-k)/N）/N=2(N-k)/N*N (c)Ek=k*Pk=2k(N-k)/N*N =(N*N-1)/3N (d)當N比較大時，從上文可以看出一次尋道平均跨越磁道數(shù)接近N/311.5下面的公式適用于高速緩沖存儲器和磁盤高速緩存： Ts=Tc+MTd 請把這個公式推廣到N級存儲器結(jié)構(gòu)，而不是僅僅2級。 定義： Ai=從i級存儲器找到信息的時間； Hi=消息在第i級存儲器并且沒有在更高級存儲器的概率； Bi=從第（i+1）級向第i級傳送一塊數(shù)據(jù)的時間。 假設緩存在1級存儲上，主存在2級存儲上，如此下去，形成一個N級存儲結(jié)構(gòu)，因此有 Ts=AiHi 若消息在M1層，可以立即被讀，如果在M2中，不在M1中，那么這塊數(shù)據(jù)從M2傳到M1中再讀。 因此 A2=B1+A1 進而有 A3=B2+A2=B1+B2+A1 即有 Ai=A1+Bj 所以 Ts=T1Hi+BjHi 因為 Hi=1 最后可得 Ts=T1+BjHi11.6對基于頻率的替換算法（見圖11.12），定義Fnew,Fmiddle和Fold分別為包含新區(qū)，中間區(qū)和的高速緩存片段，顯然Fnew+Fmiddle+Fold=1.如果有 aFold=1Fnew b. Fold=1/（高速緩存大?。?請分別描述該策略。a 圖11.11的中間區(qū)是空的，因此這種策略退化為圖11.11a的策略。b 老區(qū)由一塊組成，并且我們有LRU替換策略。11.7對于一個有9個磁道的磁帶，磁帶速度為120英寸每秒，磁帶密度為1600線位/英寸，請問它的傳送率為多少？密度可表示為1600線位每英寸，因此傳送速率為16001200=192000線位每秒。11.8假設有一個2400英寸的磁帶盤，記錄間的間隙為0.6英寸，這個間隙是磁帶在讀操作之間的停止；在間隙期間磁帶速度成線性增加或減小，磁帶的其他與習題11.7相同。磁帶上的數(shù)據(jù)按物理記錄組織，每個物理記錄包含固定數(shù)目的由用戶定義的單元，稱為邏輯記錄。a.在磁帶上讀取分裝在10個物理記錄中的120個邏輯記錄需要多少時間？b同樣。如果是分裝在30個物理記錄中，則需要多少時間？c.對于上述每種分塊方案，整個磁帶分別可以保存多少個邏輯記錄？d對于上述每種分塊方案，有效的總傳速率分別是多少？e.磁帶的容量是多少？假設每個記錄由30塊組成。b我們先定義從一個物理塊加間隙到了另一塊的讀取時間物理塊的大小=（30個邏輯記錄每物理記錄）（120比特每邏輯記錄） =3600字節(jié)物理塊的長度=3600字節(jié)/（1600比特/英寸）=2.35英寸間隙的長度=0.6英寸傳輸一個塊加間隙的傳輸時間=2.25/120+0.6/60=0.02875秒磁帶上塊的數(shù)目=（240012）/（2.25+0.6）=10105物理塊因此，讀取時間為 101050.02875=291秒 c.如果分裝在30個物理記錄中，磁帶包含10105個物理記錄和3010105=303150個邏輯記錄。d.分裝在30個物理記錄中的有效傳輸數(shù)率： R=（303150120）/291=125010字節(jié)/秒e容量=303150120=36378000字節(jié)11.9如果磁盤中扇區(qū)大小固定為每扇區(qū)為512字節(jié)，并且每磁道96個磁區(qū)，每面110個磁道，一共有8個可用的面，對于習題11.8（b），計算存儲這些邏輯記錄需要多少磁盤空間（扇區(qū)、磁道和面）。忽略文件頭記錄和磁道索引，并假設記錄不能跨越兩個扇區(qū)。每個扇區(qū)能容納4個記錄，所需扇區(qū)數(shù)=303150/4=75788 所需磁道數(shù)=75788/96=790所需面數(shù)=790/110=811.10考慮習題11.9所描述的磁盤系統(tǒng)，假設該磁盤的旋轉(zhuǎn)速度為360r/m。一個處理器使用中斷驅(qū)動I/O從磁盤中讀取一個扇區(qū)，每個字節(jié)一個中斷。如果處理每個中斷需要2.5us，處理器花費在處理I/O上的時間占多少百分比（忽略尋道時間）？每扇區(qū)512字節(jié)，每字節(jié)一個中斷，所以每扇區(qū)512個中斷。中斷總時間=2.5512=1280us。每個扇區(qū)讀取時間=60s/m360r/m96扇區(qū)/磁道=1736us處理器花費在處理I/O上的時間百分比=1001280/1736=7411.11如果使用DMA策略并假設每個扇區(qū)一個中斷，重做習題11.10。使用DMA策略，中斷總時間=2.5us處理器花費在處理I/O上的時間百分比=1002.5/1736=0.1411.12一個32位計算機有兩個選擇通道和一個多路通道，每個選擇通道支持兩個磁盤和兩個磁帶部件。多路通道有兩個行式打印機、兩個卡片閱讀機，并連接著10個VDT終端。假設有以下的傳送率： 磁盤驅(qū)動器 800KB/s 磁帶驅(qū)動器 200KB/s 行式打印機 6.6KB/s 卡片閱讀機 1.2KB/s VDT 1KB/s系統(tǒng)中的最大合計傳送率為多少？每次只有一個驅(qū)動設備能在選擇通道上得到服務，因此 ， 最大速率=800+800+26.6+21.2+101=1625.