操作系統(tǒng)五、六章補(bǔ)充題

1、1、某文件系統(tǒng)為一級目錄結(jié)構(gòu)，文件的數(shù)據(jù)一次性寫入磁盤，已經(jīng)寫入的文件不能修改，但是可以多次創(chuàng)建新文件。請回答以下問題：1）在連續(xù)、鏈?zhǔn)?、索引三種文件的數(shù)據(jù)塊組織方式中，哪種更適合？請說明理由。2）為了快速找到文件，對于FCB，是集中存儲好，還是與對應(yīng)的文件數(shù)據(jù)塊連續(xù)存儲好？請說明理由。解答：1）連續(xù)更合適。因?yàn)橐淮涡詫懭氩淮嬖诓迦雴栴}，連續(xù)的數(shù)據(jù)塊組織方式完全可以滿足一次性寫入磁盤。同時(shí)連續(xù)文件組織方式減少了其他不必要的空間開銷，而連續(xù)的組織方式順序查找讀取文件的速度是最快的。2）為了快速找到文件，F(xiàn)CB是集中存儲好。目錄是存在磁盤上的，所以檢索目錄的時(shí)候需要訪問磁盤，速度很慢：集中存儲是將

2、文件控制塊的一部分?jǐn)?shù)據(jù)分解出去，存在另一個數(shù)據(jù)結(jié)構(gòu)中，而在目錄中僅留下文件的基本信息和指向該數(shù)據(jù)結(jié)構(gòu)的指針，這樣就有效縮短了目錄的容量，減少了目錄在磁盤中的塊數(shù)，于是檢索目錄時(shí)讀取次哦的次數(shù)也就減少了，于是加快了目錄檢索的速度。2、某計(jì)算機(jī)存儲器按字節(jié)編址，虛擬（邏輯）地址空間大小為16MB，主存（物理）地址空間為1MB，頁面大小為4KB：Cache采用直接映射方式，共8行；主存與Cache中間交換的塊大小為32B。系統(tǒng)運(yùn)行到某一時(shí)刻時(shí)，頁表的部分內(nèi)容和Cache的部分內(nèi)容為下圖所示，圖中頁框號及標(biāo)記字段的內(nèi)容為十六進(jìn)制形式。虛頁號有效位頁框號010611042115310240-512B60

3、-7132頁表的部分內(nèi)容行號有效位標(biāo)記0102010-2101D31105410645114D60-7127ACache的部分內(nèi)容請回答下列問題：1）虛擬地址共有幾位，哪幾位表示虛頁號？物理地址有幾位，哪幾位表示頁框號（物理頁號）？2）使用物理地址訪問Cache時(shí)，物理地址應(yīng)該劃分為哪幾個字段？要求說明每個字段的位數(shù)及在物理地址中的位置。3）虛擬地址001C60H所在的頁面是否在主存中？如在，則該虛擬地址對應(yīng)得物理地址是什么？訪問該地址時(shí)是否Cache命中？要說明理由。4）假定為該機(jī)配置一個4路組相聯(lián)的TLB，共可以存放8個頁表項(xiàng)，若當(dāng)前內(nèi)容（十六進(jìn)制）如下圖所示，則此時(shí)虛擬地址024BACH

4、所在的頁面是否存在主存中？請說明理由。解答：1）24位，前12位；20位，前8位2）主存字塊標(biāo)記（12位），Cache字塊標(biāo)記（3位）,字塊內(nèi)地址（5位）物理地址20位，其中塊大小為32B=25B，故塊內(nèi)地址為5位，Cache共8=23行，故塊標(biāo)記為3位，20-5-3=12，故主存字塊標(biāo)記為12位。3）在主存中，004C60H；不命中，因?yàn)闆]有04CH的標(biāo)記字段001C60H中虛頁號為001H=1，經(jīng)過查找頁表知道其有效位是1，在內(nèi)存中；該頁對應(yīng)的頁框號為04H，故物理地址為004C60H；物理地址為004C60H在直接映射方式下，對應(yīng)的行號為4，有效位是1，但是標(biāo)記為是064H不等于04CH

5、,故不命中。4）在，012的那個標(biāo)記是對的思路：標(biāo)記11位，組地址1位，頁內(nèi)地址12位，前12位是0000 0010 0100，組地址為0，第0組存在標(biāo)記為012的頁，其頁框號為1F，故024BACH所在的頁面在內(nèi)存中。3、假設(shè)一個文件系統(tǒng)使用索引結(jié)構(gòu)（索引僅包含磁盤塊號）組織文件內(nèi)容塊，每塊的大小為16KB，磁盤空間為1GB?，F(xiàn)在假設(shè)一個目錄中包含3個文件，其大小分別為10KB，1089KB，129MB，請問這些文件總共在磁盤中占用了多大的空間？（不計(jì)其目錄項(xiàng)占據(jù)的空間）解答：一個文件占用的磁盤空間是和采用的索引結(jié)構(gòu)密切相關(guān)的，解決這類問題是一定要設(shè)計(jì)合適的索引結(jié)構(gòu)。1GB的磁盤空間共有1G

6、B/16KB=65536塊，在此設(shè)索引塊中每個索引項(xiàng)需要16位，因此一個索引塊最多有1K個索引項(xiàng)，最大索引16MB。10KB大小的文件占用一個數(shù)據(jù)塊，占用磁盤空間為16KB；1089KB的文件共需要一個索引塊和69個數(shù)據(jù)塊，占用空間為69x16+16=1120KB；129MB的文件需要1個一級索引塊和9個二級索引塊以及129MB/16KB=8256個數(shù)據(jù)塊，共需要磁盤空間=（1+9+8256）x16=132256KB。當(dāng)然，還可以采用其他方法來設(shè)計(jì)索引結(jié)構(gòu)。4、旋轉(zhuǎn)型存儲設(shè)備上的信息優(yōu)化分布能夠減少若干輸入/輸出服務(wù)的總時(shí)間。例如，有10個記錄A,BJ存放在磁盤的某一個磁道上，假定這個磁道劃分

7、成10個扇區(qū)，每個扇區(qū)存放一個記錄，安排如下表所示：扇區(qū)12345678910記錄號ABCDEFGHIJ現(xiàn)在要從該磁道中順序?qū)J這10個記錄讀出，如果磁盤旋轉(zhuǎn)一周需要時(shí)間20ms，處理程序每讀出1個記錄后花4ms的時(shí)間進(jìn)行處理，試問處理完這10個記錄需要的總時(shí)間是多少（從找到A開始計(jì)算）？為了縮短處理時(shí)間，應(yīng)進(jìn)行優(yōu)化分布，試問應(yīng)該如何安排這10個記錄？并計(jì)算優(yōu)化后的總的處理時(shí)間是多少（從找到記錄A開始）？解答：1）沒有優(yōu)化時(shí)，需要的總時(shí)間是6+9x22=204ms2）優(yōu)化方案扇區(qū)12345678910記錄號AHEBIFCJGD優(yōu)化后需要的總時(shí)間：10x(2+4)=60ms5、為什么磁盤調(diào)度算

8、法通常不考慮旋轉(zhuǎn)延遲？解答：大多數(shù)磁盤并沒有將旋轉(zhuǎn)位置信息輸出給主機(jī)，因此在大多數(shù)情況下操作系統(tǒng)在進(jìn)行磁盤調(diào)度時(shí)無法得到旋轉(zhuǎn)信息，也就沒有辦法在調(diào)度算法中考慮它的影響。即使是磁盤系統(tǒng)可以提供旋轉(zhuǎn)位置信息，但是由于磁盤依然在旋轉(zhuǎn)，因此這個信息到達(dá)主機(jī)時(shí)往往是不準(zhǔn)確的，而且處理時(shí)間也往往是變化的，所以操作系統(tǒng)在進(jìn)行調(diào)度時(shí)獲得的旋轉(zhuǎn)位置信息是不正確的。另外，磁盤請求往往是以邏輯塊的形式作為參數(shù)，而邏輯塊和物理塊之間的映射比較復(fù)雜，若在調(diào)度中計(jì)算這種映射會大大增加系統(tǒng)開銷。總之，無論是從可行性上還是從性能上進(jìn)行考慮，調(diào)度算法都不考慮磁盤旋轉(zhuǎn)的位置。6、一個軟盤的扇區(qū)安排采用如下圖（c）所示的形式。這個

9、軟盤的每個磁道有8個扇區(qū)，每個扇區(qū)可以存放512B數(shù)據(jù)，軟盤的旋轉(zhuǎn)速率為300rpm，如果旋轉(zhuǎn)臂已經(jīng)在合適的位置了，那么順序讀完一個磁道上的扇區(qū)需要多長時(shí)間？如果扇區(qū)安排使用圖（a）和圖（b）呢？解答：旋轉(zhuǎn)延遲為60000÷300=200ms，假設(shè)處理數(shù)據(jù)的速度為k B/ms。則：在（a）圖中讀取一個磁道的時(shí)間是8 x（200 ÷（512/k）x200ms。在（b）圖中為：8 x（400 ÷（512/k）x 200ms在（c）圖中為：8 x（600 ÷（512/k）x200ms7、某個文件系統(tǒng)管理一個4GB多的磁盤，它可以管理一個大小為4GB的文件，也可

10、以管理一個包含4000個10KB文件的目錄樹。但是在測試中，如果順序讀取4GB的大文件，只需要2min，而當(dāng)遍歷4000個10KB的文件時(shí)幾乎需要運(yùn)行1h，請分析引起這種性能差異的原因。解答：順序讀取磁盤上的一個文件，幾乎沒有旋轉(zhuǎn)延遲和尋找時(shí)間；而讀取多個文件則需要大量的尋找時(shí)間和旋轉(zhuǎn)延遲（包括文件塊和目錄塊）。8、在設(shè)備子系統(tǒng)中，引入緩沖可以有效改善CPU和I/O設(shè)備之間的速度不匹配的矛盾，但是也可能損失CPU與I/O設(shè)備之間的帶寬，請問為什么？解答：使用緩沖的主要原因是因?yàn)橹鞔娴膸捯话愣歼h(yuǎn)遠(yuǎn)高于I/O設(shè)備的帶寬，主存和CPU之間的帶寬差小于CPU和I/O設(shè)備之間的帶寬差，因此可以使用緩存

11、來改善CPU和I/O設(shè)備之間 速度不匹配的矛盾。但是這種改善是以減少I/O次數(shù)為基礎(chǔ)的，如果緩存命中率低，那么管理緩存所帶來的開銷可能比緩存得到的收益還要高，此時(shí)CPU與I/O設(shè)備的帶寬就受到了損失。例如：1）個人計(jì)算機(jī)上視頻和音頻播放器就是一個典型的例子。因?yàn)檫@些文件都是順序訪問的，緩存命中率永遠(yuǎn)為0，此時(shí)緩存是損害CPU和I/O設(shè)備之間帶寬的主要原因。2）高速網(wǎng)絡(luò)適配器。目前高速網(wǎng)絡(luò)適配器的帶寬都達(dá)到了Gb級別，幾乎與CPU的帶寬相當(dāng)，是高于主存帶寬的，此時(shí)不存在CPU和I/O設(shè)備之間速度不匹配的矛盾，因此內(nèi)存訪問成了瓶頸。為了解決視頻和音頻等多媒體數(shù)據(jù)的處理，現(xiàn)代操作系統(tǒng)中都提供了無緩沖

12、（或者稱“直接”）的I/O方式。9、某用戶文件共有10個邏輯記錄，每個邏輯記錄的長度為480個字符，現(xiàn)在把該文件放到磁帶上，若磁帶的記錄密度是800字符/英寸，塊與塊之間的間隙為0.6英寸，回答下面的問題：1）不采用記錄的成組操作時(shí)磁帶的空間利用率是多少？2）采用成組操作且塊因子為5時(shí)磁帶空間的利用率是多少？3）當(dāng)按上述方式（成組）把文件存放到磁帶后，用戶要求每讀一個記錄到他的工作區(qū)，當(dāng)對該記錄處理完畢后再讀下一個記錄到工作區(qū)中，直至10個記錄處理結(jié)束。系統(tǒng)應(yīng)該如何為用戶服務(wù)？解答：1）利用率為50%2）利用率為83%3）設(shè)置長度為2400字符的主存緩沖區(qū)；找到該文件的存放位置，啟動磁帶機(jī)讀出第一塊內(nèi)容存入主存緩沖器；進(jìn)行記錄的分解，按照用戶要求依次把主存緩沖區(qū)中的5個記錄傳送到用戶工作區(qū)中；啟動磁帶機(jī)讀第二塊內(nèi)容存入主存緩沖區(qū)，