操作系統(tǒng)存儲(chǔ)管理習(xí)題

第四章第五章存儲(chǔ)管理習(xí)題1、某系統(tǒng)采用動(dòng)態(tài)分區(qū)存儲(chǔ)管理技術(shù)，某時(shí)刻內(nèi)存中有三個(gè)空閑區(qū)，它們的首地址和大小分別為：空閑區(qū)1(100KB,10KB)空閑區(qū)2(200KB,30KB)空閑區(qū)3(300KB,15KB)(1)畫出該時(shí)刻內(nèi)存分配圖；(2)用首次適應(yīng)法和最佳適應(yīng)法畫出此時(shí)的空閑分區(qū)鏈；(3)有如下作業(yè)序列：作業(yè)1需求15KB，作業(yè)2需求16KB，作業(yè)3需求10KB，用哪種算法能將該作業(yè)序列裝入內(nèi)存？(給出簡(jiǎn)要分配過(guò)程)100K(1)110K200K230K300K315K10KB30KB15KB(2)100K10KB200K30KB300K15KB^首次適應(yīng)法最佳適應(yīng)法100K10KB300K15KB200K30KB^100K110K200K230K300K315K10KB30KB15KB(3)100K110K200K230K300K315K10KB15KB15KB作業(yè)1215K首次適應(yīng)法100K110K200K230K300K315K作業(yè)314KB作業(yè)1作業(yè)2216K100K110K200K230K300K315K10KB30KB15KB最佳適應(yīng)法2、考慮一個(gè)由8個(gè)頁(yè)面，每頁(yè)1K字節(jié)組成的邏輯空間，把它映射到由32個(gè)物理塊組成的存儲(chǔ)器。問(wèn)：（1）有效的邏輯地址有多少位？（2）有效的物理地址有多少位？解此題的關(guān)鍵是要知道在分頁(yè)管理中，“頁(yè)”和“塊”是一樣大小的，這樣才知道物理存儲(chǔ)器是32K。（1）邏輯地址有13位（2）物理地址有15位3、若在一分頁(yè)存儲(chǔ)管理系統(tǒng)中，某作業(yè)的頁(yè)表如下所示。已知頁(yè)面大小為1024字節(jié)，試將邏輯地址1011，2148，3000，5012轉(zhuǎn)化為相應(yīng)的物理地址。

頁(yè)號(hào)塊號(hào)01232316為了描述方便，設(shè)頁(yè)號(hào)為P，頁(yè)內(nèi)位移為W，邏輯地址為A，內(nèi)存地址為M，頁(yè)面大小為L(zhǎng)，根據(jù)P=int(A/L)W=AmodL

對(duì)于邏輯地址1011P=int(1011/1024)=0W=1011mod1024=1011A=1101=(0,1101)查頁(yè)表0號(hào)頁(yè)在2號(hào)塊，所以物理地址為M=1024*2+1101=3059。對(duì)于邏輯地址為2148P=2148/1024=2W=2148mod1024=100A=2148=(2,100)查頁(yè)表2號(hào)頁(yè)在1號(hào)塊，所以物理地址為M=1024*1+100=1124。對(duì)于邏輯地址為3000P=3000/1024=2W=3000mod1024=952A=3000=(2,952)查頁(yè)表2號(hào)頁(yè)在1號(hào)塊，所以物理地址為M=1024*1+952=1976

對(duì)于邏輯地址5012P=5012/1024=4W=5012mod1024=916因頁(yè)號(hào)超過(guò)頁(yè)表長(zhǎng)度，該邏輯地址非法。4、某虛擬存儲(chǔ)器的用戶空間共有32個(gè)頁(yè)面，每頁(yè)1KB，主存16KB。試問(wèn)：

（1）邏輯地址的有效位是多少？

（2）物理地址需要多少位？

（3）假定某時(shí)刻系統(tǒng)用戶的第0，1，2，3頁(yè)分別分配的物理塊號(hào)為5，10，4，7，試將虛地址0A5C和093C變換為物理地址。

（1）程序空間的大小為32KB，因此邏輯地址的有效位數(shù)是15位。（2）內(nèi)存儲(chǔ)空間的大小是16KB，因此物理地址至少需要14位。（3）頁(yè)面大小為1KB，虛地址0A5C(000101001011100)表示頁(yè)號(hào)為00010，頁(yè)內(nèi)地址是1001011100。該頁(yè)在內(nèi)存的第4塊，即塊號(hào)為0100，因此0A5C的物理地址是01001001011100，即125CH。（4）用同樣的方法可以求得，093C的物理地址是113CH。5、考慮一個(gè)分頁(yè)存儲(chǔ)器，其頁(yè)表存放在內(nèi)存。(*)（1）若內(nèi)存的存取周期為0.6us，則CPU從內(nèi)存取一條指令（或一個(gè)操作數(shù)）需多少時(shí)間？（2）若使用快表且快表的命中率為75％，則內(nèi)存的平均存取周期為多少？假定訪問(wèn)快表的時(shí)間可以忽略不計(jì)（1）因?yàn)轫?yè)表放在內(nèi)存，故取一條指令（或一個(gè)操作數(shù)）須訪問(wèn)兩次內(nèi)存，所以需0.6us×2=1.2us的時(shí)間。（2）這里假定訪問(wèn)快表的時(shí)間可以忽略不計(jì)，命中快表時(shí)取數(shù)只要一次訪存，故此時(shí)的平均存取周期為0.6us×0.75+1.2us×(1-0.75)=0.75us關(guān)鍵:要知道訪問(wèn)快表的時(shí)間可以忽略不計(jì)和平均存取周期的概念。6、某段式存儲(chǔ)管理系統(tǒng)中，有一作業(yè)的段表（SMT）如下表所示，求邏輯地址[0，65]，[1，55]，[2，90]，[3，20]對(duì)應(yīng)的主存地址（按十進(jìn)制）。（其中方括號(hào)中的第一個(gè)元素為段號(hào)，第二個(gè)元素為段內(nèi)地址）

段號(hào)段長(zhǎng)（容量）主存起始地址狀態(tài)0123200501001506008501000—1110邏輯地址[0，65]：對(duì)應(yīng)的主存地址為600＋65＝665。邏輯地址[1，55]：因段內(nèi)地址超過(guò)段長(zhǎng)，所以產(chǎn)生段地址越界中斷。段號(hào)段長(zhǎng)（容量）主存起始地址狀態(tài)0123200501001506008501000—1110邏輯地址[2，90]：對(duì)應(yīng)的主存地址為1000＋90＝1090。邏輯地址[3，20]：因?yàn)闋顟B(tài)位為0，即該段在輔存中，所以產(chǎn)生缺段中斷。段號(hào)段長(zhǎng)（容量）主存起始地址狀態(tài)0123200501001506008501000—1110虛擬內(nèi)存的實(shí)際大小由系統(tǒng)的邏輯地址結(jié)構(gòu)、主存、輔存容量共同決定。虛擬內(nèi)存容量的理論值是210*220=1G；最大段內(nèi)地址為220=1M，超過(guò)512K的內(nèi)存容量，故最大實(shí)際段長(zhǎng)為512k而不是1M。所以可計(jì)算虛擬存儲(chǔ)容量為210*512K=210*0.5M=0.5G。0.5G<2G，因此虛擬存儲(chǔ)器的實(shí)際容量是0.5G。7、有一計(jì)算機(jī)系統(tǒng)，內(nèi)存容量為512K，輔存容量為2G，邏輯地址形式為：段號(hào)29~20bit段內(nèi)地址19~0bit。求其虛擬存儲(chǔ)器的實(shí)際容量？(*)8、在請(qǐng)求分頁(yè)存儲(chǔ)管理系統(tǒng)中，存取一次內(nèi)存的時(shí)間是8us，查詢一次快表的時(shí)間是1us，缺頁(yè)中斷的時(shí)間是20us，假設(shè)頁(yè)表的查詢與快表的查詢同時(shí)進(jìn)行。當(dāng)查詢頁(yè)表時(shí)，如果該頁(yè)在內(nèi)存但快表中沒(méi)有頁(yè)表項(xiàng)，系統(tǒng)將自動(dòng)把該頁(yè)頁(yè)表項(xiàng)送入快表。(*)1、求對(duì)某一數(shù)據(jù)進(jìn)行一次存取可能需要的時(shí)間？2、連續(xù)對(duì)同一頁(yè)面上的數(shù)據(jù)進(jìn)行4次連續(xù)讀取，求每次讀取數(shù)據(jù)可能需要的時(shí)間?

當(dāng)系統(tǒng)對(duì)數(shù)據(jù)進(jìn)行存取時(shí)，有3種可能性。1、所存取的數(shù)據(jù)的頁(yè)面在內(nèi)存，其頁(yè)表項(xiàng)已經(jīng)存儲(chǔ)到快表，此時(shí)存取數(shù)據(jù)的時(shí)間是：查詢快表的時(shí)間+存取內(nèi)存數(shù)據(jù)的時(shí)間=1us+8us=9us2、所存取的數(shù)據(jù)的頁(yè)面在內(nèi)存，但是其頁(yè)表項(xiàng)沒(méi)有存儲(chǔ)到快表，沒(méi)有命中快表，此時(shí)存取數(shù)據(jù)的時(shí)間是：查詢頁(yè)表的時(shí)間+存取內(nèi)存數(shù)據(jù)的時(shí)間=8us+8us=16us3、所存取的數(shù)據(jù)的頁(yè)面不在內(nèi)存，發(fā)生缺頁(yè)中斷，此時(shí)存取數(shù)據(jù)的時(shí)間是：查詢頁(yè)表的時(shí)間+缺頁(yè)中斷的時(shí)間+訪問(wèn)頁(yè)表的時(shí)間+存取內(nèi)存數(shù)據(jù)的時(shí)間=8us+20us+8us+8us=44us當(dāng)對(duì)某一數(shù)據(jù)進(jìn)行4次連續(xù)讀取時(shí)：第1次可能的時(shí)間分別為：1us+8us=9us；8us+8us=16us；8us+20us+8us+8us=44us。第2次時(shí)，對(duì)應(yīng)頁(yè)面的頁(yè)表項(xiàng)已經(jīng)交換到快表中。因?yàn)榇嫒∈沁B續(xù)的，不存在頁(yè)面被淘汰的可能性，所以第2次、第3次、第4次的存取時(shí)間是一樣的，消耗的時(shí)間為1us+8us=9us。9、考慮一個(gè)有快表的請(qǐng)求分頁(yè)系統(tǒng)

設(shè)內(nèi)存的讀寫周期為1us,

內(nèi)外存之間傳送一個(gè)頁(yè)面的平均時(shí)間為5ms，

其中，80%情況下命中快表，10%情況下頁(yè)面失效（缺頁(yè)）

求內(nèi)存的有效存取時(shí)間。(*)內(nèi)存的有效存取時(shí)間EAT(EfficentAccessTime)也叫平均存取時(shí)間AAT(AverageAccessTime)，其計(jì)算公式如下：EAT＝命中快表時(shí)的存取時(shí)間×快表命中率＋命中內(nèi)存時(shí)的存取時(shí)間×內(nèi)存命中率＋頁(yè)面失效時(shí)的存取時(shí)間×頁(yè)面失效率將題中的已知條件代入可得EAT=1us×80%+2us×（100-80-10）%+(1us+5000us+1us+1us)×10%=0.8us+0.2us+500.3us=501.3us10、一個(gè)使用快表的頁(yè)式虛存，（1）快表的命中率為70％，內(nèi)存的存取周期為1us；（2）缺頁(yè)時(shí)，若內(nèi)存有可用空間或被置換的頁(yè)面在內(nèi)存未被修改過(guò)，則處理一個(gè)缺頁(yè)需8ms，否則需20ms，假定被置換的頁(yè)面60％是屬于后一種情況。

問(wèn)：為了保證有效存取時(shí)間不超過(guò)2us，問(wèn)可接受的最大缺頁(yè)率是多少？設(shè)可接受的最大缺頁(yè)率為p，則有1us×0.7+命中快表2us×(1-0.7-p)+命中頁(yè)表(0.4×8ms+0.6×20ms)×p缺頁(yè)=2us即0.7+0.6-2p+3200p+1200p=215198p=0.7p=0.00004611、在分頁(yè)存儲(chǔ)管理系統(tǒng)中，存取一次內(nèi)存的時(shí)間是8us，查詢一次快表的時(shí)間是1us，缺頁(yè)中斷的時(shí)間是20us。

假設(shè)頁(yè)表的查詢與快表的查詢同時(shí)進(jìn)行，當(dāng)查詢頁(yè)表時(shí)，如果該頁(yè)在內(nèi)存但快表中沒(méi)有頁(yè)表項(xiàng)，系統(tǒng)將自動(dòng)把該頁(yè)頁(yè)表項(xiàng)送入快表。

一個(gè)作業(yè)最多可保留3個(gè)頁(yè)面在內(nèi)存。

現(xiàn)開(kāi)始執(zhí)行一作業(yè)，系統(tǒng)連續(xù)對(duì)作業(yè)的２、４、5、２、7、6、4、2各頁(yè)面的數(shù)據(jù)進(jìn)行1次存取，如分別采用FIFO算法和最優(yōu)頁(yè)面置換算法，求每種算法下存取這些數(shù)據(jù)需要的總時(shí)間？LRU第2頁(yè)面：20＋8*3第4頁(yè)面：20+8*3第5頁(yè)面：20+8*3第2頁(yè)面：8+1第7頁(yè)面：20+8*3第6頁(yè)面：20+8*3第4頁(yè)面：20+8*3

第8頁(yè)面：20+8*3因此總的時(shí)間是（20＋8*3）*7+（8+1）=317OPT第2頁(yè)面：20＋8*3第4頁(yè)面：20+8*3第5頁(yè)面：20+8*3第2頁(yè)面：8+1第7頁(yè)面：20+8*3第6頁(yè)面：20+8*3第4頁(yè)面：8+1

第8頁(yè)面：8+1因此總的時(shí)間是(20＋8*3）*5+(8+1)*3=24712、在某分頁(yè)虛存系統(tǒng)中，測(cè)得CPU和磁盤的利用率如下，試指出每種情況下的問(wèn)題和措施。*

(1)

CPU的利用率為15％，盤利用率為95％；

(2)

CPU的利用率為88％，盤利用率為3％；

(3)

CPU的利用率為13％，盤利用率為5％。

（1）可能已出現(xiàn)了抖動(dòng)現(xiàn)象，應(yīng)減少系統(tǒng)的進(jìn)程數(shù)；（2）系統(tǒng)比較正常，可考慮適當(dāng)增加進(jìn)程數(shù)以提高資源利用率；（3）CPU和磁盤的利用率都較低，必須增加并發(fā)進(jìn)程數(shù)。在內(nèi)存管理中，“內(nèi)零頭”和“外零頭”各指的是什么？在固定式分區(qū)分配、可變式分區(qū)分配、頁(yè)式虛擬存儲(chǔ)系統(tǒng)、段式虛擬存儲(chǔ)系統(tǒng)中，各會(huì)存在何種零頭？為什么？

內(nèi)零頭（又稱內(nèi)部碎片）：給一個(gè)作業(yè)分配的存儲(chǔ)塊長(zhǎng)度為n，在其中存儲(chǔ)的作業(yè)長(zhǎng)度為m，則剩下的長(zhǎng)度為（n-m）的空間，成為該存儲(chǔ)塊的內(nèi)部碎片；若存儲(chǔ)塊長(zhǎng)度為n，在該系統(tǒng)所采用的調(diào)度算法下，較長(zhǎng)時(shí)間內(nèi)無(wú)法選出一道長(zhǎng)度不超過(guò)該塊的作業(yè)，則稱該塊為外零頭（外部碎片）。在固定式分區(qū)分配中兩種零頭均會(huì)存在，因?yàn)榭臻g劃分是固定的，無(wú)論作業(yè)長(zhǎng)短，存儲(chǔ)單元均不會(huì)隨之變化，若作業(yè)短而存儲(chǔ)塊長(zhǎng)則產(chǎn)生內(nèi)零頭，若作業(yè)長(zhǎng)而存儲(chǔ)塊短則產(chǎn)生外零頭。在可變式分區(qū)分配中只有外零頭而無(wú)內(nèi)零頭，因?yàn)榭臻g劃分是依作業(yè)長(zhǎng)度進(jìn)行的，是要多少給多少，但剩下的部分太短而無(wú)法再分，則稱為外零頭。頁(yè)式虛存中會(huì)存在內(nèi)零頭而無(wú)外零頭，因存儲(chǔ)空間與作業(yè)均分為等長(zhǎng)單元，所以不存在無(wú)法分配的單元，但作業(yè)長(zhǎng)度并不剛好為頁(yè)面大小的整數(shù)倍，因此在最后一頁(yè)會(huì)有剩余空間，即為內(nèi)零頭。段式虛存中會(huì)存在外零頭而無(wú)內(nèi)零頭，因段式的空間劃分類似于可變分區(qū)分配，根據(jù)段長(zhǎng)分配，要多少給多少，但會(huì)剩余小空間無(wú)法分配，則為外零頭。為什么要引入邏輯地址？

(1)

使用物理地址的程序只有裝入程序所規(guī)定的內(nèi)存空間上才能正確執(zhí)行，如果程序所規(guī)定內(nèi)存空間不空閑或不存在，程序都無(wú)法執(zhí)行；(2)

使用物理地址編程意味著由程序員分配內(nèi)存空間，程序員無(wú)法事先協(xié)商每個(gè)程序所應(yīng)占的內(nèi)存空間的位置,這在多道程序系統(tǒng)中，勢(shì)必造成程序所占內(nèi)存空間的相互沖突；(3)

在多道程序系統(tǒng)中，系統(tǒng)無(wú)法保證程序執(zhí)行時(shí)，它所需的內(nèi)存空間都空閑。基于上述原因，必須引入一個(gè)統(tǒng)一的、在編程時(shí)使用的地址，它能夠在程序執(zhí)行時(shí)根據(jù)所分配的內(nèi)存空間將其轉(zhuǎn)換為對(duì)應(yīng)的物理地址，這個(gè)地址就是邏輯地址。邏輯地址的引入為內(nèi)存的共享、保護(hù)和擴(kuò)充提供方便。試比較靜態(tài)重定位和動(dòng)態(tài)重定位“重定位”實(shí)際上指的是相互聯(lián)系的兩件事情：一是確定一個(gè)待執(zhí)行程序在內(nèi)存中的位置；二是將程序中的邏輯地址轉(zhuǎn)換成物理地址。后一件事情是由前一件事情決定的。試比較靜態(tài)重定位和動(dòng)態(tài)重定位。

靜態(tài)重定位的特點(diǎn)實(shí)現(xiàn)容易，無(wú)需增加硬件地址變換機(jī)構(gòu)；一般要求為每個(gè)程序分配一個(gè)連續(xù)的存儲(chǔ)區(qū)；在重定位過(guò)程中，裝入內(nèi)存的代碼發(fā)生了改變；在程序執(zhí)行期間不再發(fā)生地址的變換；在程序執(zhí)行期間不能移動(dòng)，且難以做到程序和數(shù)據(jù)的共享，其內(nèi)存利用率低。動(dòng)態(tài)重定位特點(diǎn)實(shí)現(xiàn)要依靠硬件地址變換機(jī)構(gòu)，且存儲(chǔ)管理軟件算法較復(fù)雜；程序代碼是按原樣裝入內(nèi)存的，在重定位的過(guò)程中也不發(fā)生變化(重定位產(chǎn)生的物理地址存放在內(nèi)存地址寄存器中)同一代碼中的同一邏輯地址，每執(zhí)行一次都要重定位一次；只要改變基地址，就可以很容易地實(shí)現(xiàn)代碼在內(nèi)存中的移動(dòng)；動(dòng)態(tài)重定位可以將程序分配到不連續(xù)的存儲(chǔ)區(qū)中；所以，盡管動(dòng)態(tài)重定位需要硬件支持，但支持程序浮動(dòng)，便于利用零散的內(nèi)存空間，利于實(shí)現(xiàn)信息共享和虛擬存儲(chǔ)，所以現(xiàn)代計(jì)算機(jī)大都采用動(dòng)態(tài)重定位。另外，實(shí)現(xiàn)虛擬存儲(chǔ)器需要?jiǎng)討B(tài)重定位技術(shù)的支持。在實(shí)存管理上，管理方法主要分成哪兩種類型？

實(shí)存管理的方法主要分成：(1)連續(xù):用戶程序需要占用連續(xù)的內(nèi)存空間，如分區(qū)存儲(chǔ)管理；(2)離散:用戶程序不需要占用連續(xù)的內(nèi)存空間，如分頁(yè)、分段、段頁(yè)等管理，一個(gè)用戶程序在內(nèi)存可能是不連續(xù)的，如果它有不只一頁(yè)或一段的話。為什么在分頁(yè)和分段管理下取一條指令或一個(gè)操作數(shù)通常需兩次訪存？如何解決這一問(wèn)題？

因?yàn)橛糜诘刂纷儞Q的頁(yè)表或段表也是存放在內(nèi)存的，為了將CPU給出的邏輯地址變成物理地址，首先就要訪問(wèn)內(nèi)存的頁(yè)表和段表，然后，根據(jù)形成的物理地址再取指令或數(shù)據(jù)，這就要兩次訪存。解決這一問(wèn)題的辦法是提供一個(gè)稱之為“快表”的硬件，用以存放當(dāng)前運(yùn)行進(jìn)程的頁(yè)表或段表的部分內(nèi)容，“快表”的訪問(wèn)時(shí)間很快，因此可以節(jié)約訪問(wèn)頁(yè)表和段表的時(shí)間。

存儲(chǔ)器訪問(wèn)具有時(shí)間和空間的“局部性”，因此快表的命中率一般可達(dá)70%到90%；頁(yè)表和段表是在系統(tǒng)執(zhí)行過(guò)程中，每時(shí)每刻都需要訪問(wèn)的，因此，訪問(wèn)時(shí)間的微小縮短，其累計(jì)節(jié)約的時(shí)間卻可以達(dá)到很大。為什么分段管理下的程序共享和保護(hù)比分頁(yè)管理更有意義.因?yàn)槎问且粋€(gè)有意義的邏輯整體，如主程序、子程序、數(shù)據(jù)表格、工作空間等，就如書本上的一章或一個(gè)自然段。而頁(yè)只是一個(gè)物理尺寸，不一定有完整的意義，如書本上的一頁(yè)。程序共享當(dāng)然希望被共享的對(duì)象是一個(gè)有意義的整體，如一個(gè)子程序；至于程序保護(hù)，指的是每個(gè)進(jìn)程都應(yīng)按所擁有的存取權(quán)訪問(wèn)不同的程序，而存取權(quán)(R,W,E等)當(dāng)然對(duì)一個(gè)有完整意義的對(duì)象才更有意義。所以就共享和保護(hù)而言，分段管理比分頁(yè)管理更有意義。為什么說(shuō)分段系統(tǒng)較之分頁(yè)系統(tǒng)更易于實(shí)現(xiàn)信息共享和保護(hù)？如何實(shí)現(xiàn)。

(1)

為了實(shí)現(xiàn)共享，必須在各共享者的段表或頁(yè)表中分別有指向共享內(nèi)存塊的表目。(2)

對(duì)分段式系統(tǒng)，被共享的程序或數(shù)據(jù)可作為單獨(dú)的一段。在物理上它是一段，在不同的進(jìn)程中，可以對(duì)應(yīng)不同的邏輯段，相對(duì)來(lái)說(shuō)比較易于實(shí)現(xiàn)。(3)

對(duì)分頁(yè)管理，則要困難的多。必須保證被共享的程序或數(shù)據(jù)占有整數(shù)塊，以便與非共享部分分開(kāi)。(4)

分段系統(tǒng)的共享是通過(guò)兩個(gè)（或多個(gè)）進(jìn)程的段表之相應(yīng)表目都指向同一個(gè)物理段，并設(shè)置共享計(jì)數(shù)來(lái)實(shí)現(xiàn)的。

什么是抖動(dòng)現(xiàn)象？如何消除這種現(xiàn)象？