操作系統(tǒng)精髓與設(shè)計(jì)原理-第11章IO管理和磁盤(pán)調(diào)度.doc

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