第四章第五章存儲管理習題編輯課件1、某系統采用動態分區存儲管理技術，某時刻內存中有三個空閑區，它們的首地址和大小分別為：空閑區1(100KB,10KB)空閑區2(200KB,30KB)空閑區3(300KB,15KB)(1)畫出該時刻內存分配圖；(2)用首次適應法和最正確適應法畫出此時的空閑分區鏈；(3)有如下作業序列：作業1需求15KB，作業2需求16KB，作業3需求10KB，用哪種算法能將該作業序列裝入內存？(給出簡要分配過程)編輯課件100K(1)110K200K230K300K315K10KB30KB15KB編輯課件(2)100K10KB200K30KB300K15KB^首次適應法最正確適應法100K10KB300K15KB200K30KB^編輯課件100K110K200K230K300K315K10KB30KB15KB(3)100K110K200K230K300K315K10KB15KB15KB作業1215K首次適應法編輯課件100K110K200K230K300K315K作業314KB作業1作業2216K100K110K200K230K300K315K10KB30KB15KB最正確適應法編輯課件2、考慮一個由8個頁面，每頁1K字節組成的邏輯空間，把它映射到由32個物理塊組成的存儲器。問：〔1〕有效的邏輯地址有多少位？〔2〕有效的物理地址有多少位？解此題的關鍵是要知道在分頁管理中，“頁〞和“塊〞是一樣大小的，這樣才知道物理存儲器是32K。〔1〕邏輯地址有13位〔2〕物理地址有15位編輯課件3、假設在一分頁存儲管理系統中，某作業的頁表如下所示。頁面大小為1024字節，試將邏輯地址1011，2148，3000，5012轉化為相應的物理地址。

頁號塊號01232316編輯課件為了描述方便，設頁號為P，頁內位移為W，邏輯地址為A，內存地址為M，頁面大小為L，根據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〕假定某時刻系統用戶的第0，1，2，3頁分別分配的物理塊號為5，10，4，7，試將虛地址0A5C和093C變換為物理地址。

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

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

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

設內存的讀寫周期為1us,

內外存之間傳送一個頁面的平均時間為5ms，

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

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

問：為了保證有效存取時間不超過2us，問可接受的最大缺頁率是多少？編輯課件設可接受的最大缺頁率為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、在分頁存儲管理系統中，存取一次內存的時間是8us，查詢一次快表的時間是1us，缺頁中斷的時間是20us。

假設頁表的查詢與快表的查詢同時進行，當查詢頁表時，如果該頁在內存但快表中沒有頁表項，系統將自動把該頁頁表項送入快表。

一個作業最多可保存3個頁面在內存。

現開始執行一作業，系統連續對作業的２、４、5、２、7、6、4、2各頁面的數據進行1次存取，如分別采用FIFO算法和最優頁面置換算法，求每種算法下存取這些數據需要的總時間？編輯課件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、在某分頁虛存系統中，測得CPU和磁盤的利用率如下，試指出每種情況下的問題和措施。*

(1)

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

(2)

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

(3)

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

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

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

(1)

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

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

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

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

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

(1)

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

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

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

分段系統的共享是通過兩個〔或多個〕進程的段表之相應表目都指向同一個物理段，并設置共享計數來實現的。

編輯課件什么是抖動現象？如何消除這種現象？

抖