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

第四章第五章存儲管理習(xí)題編輯課件1、某系統(tǒng)采用動態(tài)分區(qū)存儲管理技術(shù)，某時刻內(nèi)存中有三個空閑區(qū)，它們的首地址和大小分別為：空閑區(qū)1(100KB,10KB)空閑區(qū)2(200KB,30KB)空閑區(qū)3(300KB,15KB)(1)畫出該時刻內(nèi)存分配圖；(2)用首次適應(yīng)法和最正確適應(yīng)法畫出此時的空閑分區(qū)鏈；(3)有如下作業(yè)序列：作業(yè)1需求15KB，作業(yè)2需求16KB，作業(yè)3需求10KB，用哪種算法能將該作業(yè)序列裝入內(nèi)存？(給出簡要分配過程)編輯課件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、考慮一個由8個頁面，每頁1K字節(jié)組成的邏輯空間，把它映射到由32個物理塊組成的存儲器。問：〔1〕有效的邏輯地址有多少位？〔2〕有效的物理地址有多少位？解此題的關(guān)鍵是要知道在分頁管理中，“頁〞和“塊〞是一樣大小的，這樣才知道物理存儲器是32K?！?〕邏輯地址有13位〔2〕物理地址有15位編輯課件3、假設(shè)在一分頁存儲管理系統(tǒng)中，某作業(yè)的頁表如下所示。頁面大小為1024字節(jié)，試將邏輯地址1011，2148，3000，5012轉(zhuǎn)化為相應(yīng)的物理地址。

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

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

對于邏輯地址5012P=5012/1024=4W=5012mod1024=916因頁號超過頁表長度，該邏輯地址非法。編輯課件4、某虛擬存儲器的用戶空間共有32個頁面，每頁1KB，主存16KB。試問：

〔1〕邏輯地址的有效位是多少？

〔2〕物理地址需要多少位？

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

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

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

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

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

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

其中，80%情況下命中快表，10%情況下頁面失效〔缺頁〕

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

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

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

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

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

第8頁面：20+8*3因此總的時間是〔20＋8*3〕*7+〔8+1〕=317編輯課件OPT第2頁面：20＋8*3第4頁面：20+8*3第5頁面：20+8*3第2頁面：8+1第7頁面：20+8*3第6頁面：20+8*3第4頁面：8+1

第8頁面：8+1因此總的時間是(20＋8*3〕*5+(8+1)*3=247編輯課件12、在某分頁虛存系統(tǒng)中，測得CPU和磁盤的利用率如下，試指出每種情況下的問題和措施。*

(1)

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

(2)

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

(3)

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

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

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

(1)

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

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

在多道程序系統(tǒng)中，系統(tǒng)無法保證程序執(zhí)行時，它所需的內(nèi)存空間都空閑?；谏鲜鲈?，必須引入一個統(tǒng)一的、在編程時使用的地址，它能夠在程序執(zhí)行時根據(jù)所分配的內(nèi)存空間將其轉(zhuǎn)換為對應(yīng)的物理地址，這個地址就是邏輯地址。邏輯地址的引入為內(nèi)存的共享、保護和擴充提供方便。編輯課件試比較靜態(tài)重定位和動態(tài)重定位“重定位〞實際上指的是相互聯(lián)系的兩件事情：一是確定一個待執(zhí)行程序在內(nèi)存中的位置；二是將程序中的邏輯地址轉(zhuǎn)換成物理地址。后一件事情是由前一件事情決定的。編輯課件試比較靜態(tài)重定位和動態(tài)重定位。靜態(tài)重定位的特點實現(xiàn)容易，無需增加硬件地址變換機構(gòu)；一般要求為每個程序分配一個連續(xù)的存儲區(qū)；在重定位過程中，裝入內(nèi)存的代碼發(fā)生了改變；在程序執(zhí)行期間不再發(fā)生地址的變換；在程序執(zhí)行期間不能移動，且難以做到程序和數(shù)據(jù)的共享，其內(nèi)存利用率低。編輯課件動態(tài)重定位特點實現(xiàn)要依靠硬件地址變換機構(gòu)，且存儲管理軟件算法較復(fù)雜；程序代碼是按原樣裝入內(nèi)存的，在重定位的過程中也不發(fā)生變化(重定位產(chǎn)生的物理地址存放在內(nèi)存地址存放器中)同一代碼中的同一邏輯地址，每執(zhí)行一次都要重定位一次；只要改變基地址，就可以很容易地實現(xiàn)代碼在內(nèi)存中的移動；動態(tài)重定位可以將程序分配到不連續(xù)的存儲區(qū)中；所以，盡管動態(tài)重定位需要硬件支持，但支持程序浮動，便于利用零散的內(nèi)存空間，利于實現(xiàn)信息共享和虛擬存儲，所以現(xiàn)代計算機大都采用動態(tài)重定位。另外，實現(xiàn)虛擬存儲器需要動態(tài)重定位技術(shù)的支持。編輯課件在實存管理上，管理方法主要分成哪兩種類型？

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

因為用于地址變換的頁表或段表也是存放在內(nèi)存的，為了將CPU給出的邏輯地址變成物理地址，首先就要訪問內(nèi)存的頁表和段表，然后，根據(jù)形成的物理地址再取指令或數(shù)據(jù)，這就要兩次訪存。解決這一問題的方法是提供一個稱之為“快表〞的硬件，用以存放當(dāng)前運行進程的頁表或段表的局部內(nèi)容，“快表〞的訪問時間很快，因此可以節(jié)約訪問頁表和段表的時間。存儲器訪問具有時間和空間的“局部性〞，因此快表的命中率一般可達70%到90%；頁表和段表是在系統(tǒng)執(zhí)行過程中，每時每刻都需要訪問的，因此，訪問時間的微小縮短，其累計節(jié)約的時間卻可以到達很大。編輯課件為什么分段管理下的程序共享和保護比分頁管理更有意義.因為段是一個有意義的邏輯整體，如主程序、子程序、數(shù)據(jù)表格、工作空間等，就如書本上的一章或一個自然段。而頁只是一個物理尺寸，不一定有完整的意義，如書本上的一頁。程序共享當(dāng)然希望被共享的對象是一個有意義的整體，如一個子程序；至于程序保護，指的是每個進程都應(yīng)按所擁有的存取權(quán)訪問不同的程序，而存取權(quán)(R,W,E等)當(dāng)然對一個有完整意義的對象才更有意義。所以就共享和保護而言，分段管理比分頁管理更有意義。編輯課件為什么說分段系統(tǒng)較之分頁系統(tǒng)更易于實現(xiàn)信息共享和保護？如何實現(xiàn)。

(1)

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

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

對分頁管理，那么要困難的多。必須保證被共享的程序或數(shù)據(jù)占有整數(shù)塊，以便與非共享局局部開。(4)

分段系統(tǒng)的共享是通過兩個〔或多個〕進程的段表之相應(yīng)表目都指向同一個物理段，并設(shè)置共享計數(shù)來實現(xiàn)的。

編輯課件什么是抖動現(xiàn)象？如何消除這種現(xiàn)象？

抖