1、第4章 存儲管理 輔導與自測4.1 本章知識點存儲器是計算機系統中的關鍵資源，對內存如何處理在很大程度上將影響整個系統的性能。存儲管理即對內存的管理，存儲管理目前仍是人們研究操作系統的中心問題之一，以至操作系統的命名也往往取決于存儲管理的策略。本章的主要知識點為：（1）本章的重要概念本章涉及到的概念比較多，主要有：內存、外存、邏輯地址/相對地址、物理地址/絕對地址、邏輯地址空間/地址空間、內存空間/物理空間/絕對空間、重定位、靜態重定位、動態重定位、對換技術、碎片、緊縮、虛擬存儲器、頁面抖動。存儲器作為計算機系統中最主要的組成部分，按照速度、容量和成本劃分一個層次結構，分別是寄存器、高速緩存、

2、內存、磁盤和磁帶。用戶程序必須裝入到內存才能運行。進程的地址空間不同于內存的物理空間。經過重定位可以把邏輯地址轉變為內存的物理地址。重定位分為靜態和動態兩種方式，現在的計算機系統中都采用動態重定位方法。對換技術可以利用外存來解決內存不足的問題。現在Linux系統中還采用這種技術。（2）分區管理技術分區分配是為支持多道程序運行而設計的一種最簡單的存儲管理方式，可分為固定分區法和動態分區法。固定分區就是內存中分區的個數固定不變，各個分區的大小也固定不變，但不同分區的大小可以不同。每個分區只可裝入一個進程。動態分區是在進程要進入內存時才建立的，使其大小恰好適應進程的大小。動態分區法常用的分配策略有兩

3、種：最先適應算法（First-fit）和最佳適應算法（Best-fit），前者空閑表按位置排列，后者空閑表以空閑分區的大小為序。具有固定大小分配單元的系統，如MFT（具有固定任務數的多道程序設計）或分頁系統，會產生內部碎片；而具有可變大小分配單元的系統，如MVT（具有可變任務數的多道程序設計），會出現外部碎片。為了有效解決碎片問題，實現的方法是移動某些已分配區的內容，使所有進程的分區緊挨在一起，而把空閑區留在另一端。這種技術稱為緊縮。采用緊縮技術的分區方法稱為可重定位分區法。動態重定位由硬件實現，包括基址寄存器和限長寄存器，對CPU生成的所有地址進行合法性檢查，并映像到物理地址。（3）分頁技術

4、除了用緊縮技術解決碎片問題，還可以使用分頁技術，即允許程序的存儲空間不一定連續，可以把一個進程分散地放在各個空閑的內存塊中。分頁存儲管理的基本方法是：邏輯空間分頁，內存空間分塊，塊與頁的大小相等。頁連續而塊離散，用頁號查頁表，由硬件作轉換。分頁存儲管理可以實現頁面的共享，但是這樣做并不實際，因為邏輯上相對完整的內容不見得存在于一個或幾個完整的頁面中（段式存儲管理更便于共享）。此外，還可以在頁表中設置存取控制字段，進行頁面保護，禁止非法訪問。（4）虛擬存儲管理虛擬存儲器是用戶能作為可編址內存對待的虛擬存儲空間，它使用戶邏輯存儲器與物理存儲器分離，是操作系統給用戶提供的一個比真實內存空間大得多的地

5、址空間。虛擬存儲技術允許把大的邏輯地址空間映射到較小的物理內存上，這樣就提高了多道程序并發執行的程度，增加了CPU的利用率。虛擬存儲器的特性包括：虛擬擴充、部分裝入、離散分配和多次對換等。使用虛擬存儲技術的頁式管理為請求分頁式存儲管理。它是根據實際程序執行的順序，動態申請存儲塊。并不是把所有頁面都放入內存。對一個程序的第一次訪問將產生缺頁中斷，轉入操作系統進行相應處理。操作系統依據頁表確定頁面在外存上的位置，然后找一個空閑塊，把該頁面從外存上讀到內存塊中。同時，修改頁表有關項目，以反映這種變化，產生缺頁中斷的那條指令被重新啟動執行。這種方式允許一個程序即使它的整個存儲映像并沒有同時在內存中，也

6、能正確運行。只要缺頁率足夠低，其性能還是很好的。請求分頁可用來減少分配給一個進程的塊數，這就允許更多進程同時執行，而且允許程序所需內存量超出可用內存總量。（5）常用頁面置換算法當總內存的需求量超出實際內存量時，為釋放內存塊給新的頁面，需要進行頁面置換。有各種頁面置換算法可供使用。先進先出法（FIFO）是最容易實現的，但性能不是很好。最佳置換法（OPT）需要未來知識，僅有理論價值。最近最少使用置換法（LRU）是OPT的近似算法，但實現時要有硬件的支持和軟件開銷。最近未使用置換法（NUR）是LRU的近似算法。置換算法的好壞直接影響系統的性能。好的頁面置換算法能夠適當降低頁面更換頻率（減少缺頁率），

7、盡量避免系統“抖動”。（6）Linux系統的存儲管理技術Linux采用對換和請求分頁存儲管理技術，頁面置換采用LRU算法。對換任務是由內核的對換守護進程kswapd完成，以保證系統中有足夠的空閑內存頁。Linux系統采用三級頁表的方式，以節省內存資源。采用位圖和鏈表兩種方法來管理內存頁。4.2 典型例題解析【例1】在目標程序裝入內存時，一次性完成地址修改的方式是（ ）. A靜態重定位 B動態重定位 C靜態連接 D動態連接答案 A分析 回答這道題需要清楚靜態重定位和動態重定位的不同。靜態重定位是在目標程序裝入內存時，由裝入程序對目標程序中的指令和數據的地址進行修改，即把程序的邏輯地址都改成實際的

8、內存地址。對每個程序來說，這種地址變換只是在裝入時一次完成，在程序運行期間不再進行重定位。按照靜態重定位方式，一個程序A裝入內存時的情況就變成圖4.1所示的樣子。從圖中可以看出，經過靜態重定位，原100號單元中的指令放到內存5100號單元，該指令中的相對地址500相應變成5500。以后程序A執行時，CPU是從絕對地址5500號單元中取出數據12345，裝入到寄存器A中。靜態重定位的優點是無須增加硬件地址轉換機構，便于實現程序的靜態連接。在早期計算機系統中大多采用這種方案。它的主要缺點是程序的存儲空間只能是連續的一片區域，而且在重定位之后就不能再移動，這不利于內存空間的有效使用；另外各個用戶進程

9、很難共享內存中的同一程序的副本。 程序A的地址空間 程序A的內存空間圖4.1 靜態重定位示意圖010050070070005000510055005700LOAD A 50012345LOAD A 550012345動態重定位是在程序執行期間每次訪問內存之前進行重定位。這種變換是靠硬件地址變換機構實現的。通常采用一個重定位寄存器，其中放有當前正在執行的程序在內存空間中的起始地址，而地址空間中的代碼在裝入過程中不發生變化。動態重定位的過程如圖4.2所示。這時，操作對象的絕對地址就是重定位寄存器中的內容操作對象的相對地址。Å0100500700700LOAD A 500123450500

10、0510055005700LOAD A 500123455005000 重定位寄存器 相對地址 程序A的地址空間 程序A的內存空間圖4.2 動態重定位示意圖動態重定位的主要優點是程序占用的內存空間動態可變，也不必連續存放在一處；比較容易實現幾個進程對同一程序副本的共享使用。它的主要缺點是需要附加的硬件支持，增加了機器成本，而且實現存儲管理的軟件算法比較復雜。與靜態重定位相比，動態重定位的優點突出。所以現在一般計算機系統中都采用動態重定位方法。【例2】動態分區分配按進程的需求量分配內存分區，所以（ ）。A分區的長度是固定的 B分區的個數是確定的C分區的長度和個數都是確定的 D分區的長度不是預先固

11、定的，分區的個數是不確定的答案 D分析 分區法分為固定分區和動態分區。其中，固定分區內存中分區的個數固定不變，各個分區的大小也固定不變，但不同分區的大小可以不同。動態分區在最初時，除了操作系統占用的分區外，全部內存對用戶進程都是可用的。分區是在進程要進入內存時才建立的，按照進程的需求量劃分內存分區，根本無法預測分區的長度和個數。本題的選項A、B、C是針對固定分區而言的，只有選項D是描述動態分區的。【例3】考慮一個由8個頁面，每頁有1024個字節組成的邏輯空間，把它裝入到有32個物理塊的存儲器中，問： （1）邏輯地址需要多少二進制位表示？ （2）物理地址需要多少二進制位表示？ 解 因為頁面數為8

12、=23，故需要3位二進制數表示。每頁有1024個字節，1024=210，于是頁內地址需要10位二進制數表示。32個物理塊，需要5位二進制數表示（32=25）。（1）頁的邏輯地址由頁號和頁內地址組成，所以需要3+10=13位二進制數表示。（2）頁的物理地址由塊號和頁內地址的拼接，所以需要5+10=15位二進制數表示。分析 在分頁存儲管理中，邏輯地址結構如下圖所示。頁號p頁內地址d 它由兩個部分組成：前一部分表示該地址所在頁面的頁號p；后一部分表示頁內地址（頁內位移）d。頁號的地址位數決定了頁的多少，假設頁號有20位，則地址空間中最多可容納的頁面數為220，即1MB個頁面。頁內地址位數確定了每頁的

13、大小，若頁內地址為12位，則每頁大小為212，即2KB。同理，物理地址中塊號的地址位數決定了塊的多少，由于頁式存儲管理內存空間塊的大小與頁面大小相同，所以物理地址中塊內地址與邏輯地址中的頁內地址位數相同。【例4】若在一分頁存儲管理系統中，某作業的頁表如下所示。已知頁面大小為1024字節，試將邏輯地址1011，2148，4000，5012轉化為相應的物理地址。頁號塊號01232316 解 本題中，為了描述方便，設頁號為p，頁內位移為d，則：（1）對于邏輯地址1011，pint（1011/1024）0，d1011 mod 10241011。查頁表第0頁在第2塊，所以物理地址為1024´2

14、10113059。（2）對于邏輯地址2148，pint（2148/1024）2，d2148 mod 1024100。查頁表第2頁在第1塊，所以物理地址為10241001124。（3）對于邏輯地址4000，pint（4000/1024）3，d4000 mod 1024928。查頁表第3頁在第6塊，所以物理地址為1024´69287072。（4）對于邏輯地址5012，pint（5012/1024）4，d5012 mod 1024916。因頁號超過頁表長度，該邏輯地址非法。 分析 頁式存儲管理的地址結構是一維的，即邏輯地址/物理地址只用一個數值即可表示。若給定的邏輯地址A，頁面的大小為L，

15、則頁號p和頁內地址d可按照下式求得：p=int (A/L) d=A mod L其中，int是取整函數（取值的整數部分），mod是取余函數（取值的余數部分）。圖4.3顯示了頁式管理系統的地址轉換機構。 邏輯地址 物理地址 頁表 p 圖4.3 頁式存儲管理中的地址轉換機構CPUpdfd內存0pf 頁表的作用是實現從頁號到物理塊號的地址映射。以邏輯地址的頁號檢索頁表，得到該頁的物理塊號；同時將頁內地址d直接送入物理地址寄存器的塊內地址字段中。這樣，物理塊號和塊內地址拼接成了實際訪問內存的地址，從而完成了從邏輯地址到物理地址的轉換。【例5】判斷：虛擬存儲器實際上是一種設計技巧，使主存物理容量得到擴大。

16、答案 錯誤。分析 根據程序執行時的互斥性和局部性兩個特點，可以只將作業的一部分裝入主存，其余的部分放在輔存（如磁盤等）上，當需要的時候，再從輔存調入主存，這樣用戶編制程序時可以不必考慮主存的實際容量，允許用戶的邏輯地址空間大于主存的絕對地址空間，對用戶來說，好像計算機具有一個容量很大的主存，這就是“虛擬存儲器”。虛擬存儲器實際上是為擴大主存容量而采用的一種設計技巧。它與實際的主存物理容量無關，而是大小比主存大得多的假想空間，使用戶感覺到所能使用的“主存空間”非常大。【例6】與虛擬存儲技術不能配合使用的是（ ）。A分區管理 B頁式存儲管理C段式存儲管理 D段頁式存儲管理答案 A分析 采用頁式、段

17、式、段頁式管理可以實現虛擬存儲器，但對固定分區、可變分區方式都不能實現虛擬存儲器。我們知道實現虛擬存儲技術的物質基礎是二級存儲結構（主存與輔存）和動態的地址轉換機構（動態重定位）。固定分區方式沒有硬件地址轉換機構。可變分區方式管理主存也不能實現虛擬存儲。因為在這種管理方式下，每次必須將作業完整地調入主存，并要求連續存放，這不符合虛擬存儲器的基本原理；另外，雖然可變分區方式有硬件地址轉換機構，但它把絕對地址超出限定范圍按出錯處理，而不是產生“缺分區中斷”。虛擬存儲器的特征可以歸結為以下16個字：虛擬擴充（并非真正擴充了主存容量）、部分裝入（每個作業不是全部一次性地裝入內存，而是分成若干部分）、離

18、散分配（裝入內存的作業部分不必占有連續的內存空間，而是“見縫插針”）、多次對換（作業運行時，程序和數據多次在主存和輔存之間對換）。【例7】考慮下述頁面走向： 1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6當內存塊數量分別為3時，試問FIFO、LRU、OPT這三種置換算法的缺頁次數各是多少？解 使用FIFO算法，缺頁次數是16；使用LRU算法，缺頁次數是15；使用OPT算法，缺頁次數是11。分析 所有內存塊最初都是空的，所以第一次用到的頁面都產生一次缺頁。當內存塊數量為3時： FIFO 1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6

19、塊1 1 1 1 4 4 4 6 6 6 3 3 3 2 2 2 6塊2 2 2 2 1 1 1 2 2 2 7 7 7 1 1 1塊3 3 3 3 5 5 5 1 1 1 6 6 6 3 3缺頁 ´ ´ ´ ´ ´ ´ ´ ´ ´ ´ ´ ´ ´ ´ ´ ´因此，FIFO算法發生缺頁中斷的次數為16。在FIFO算法中，先進入內存的頁面被先換出。例如，當頁6要調入時，內存的狀態為4、1、5，考查頁6之前調入的頁面，分別為5、1、2、4、

20、，可見4為最先進入內存的，本次應換出，然后把頁6調入內存。 LRU 1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6 塊1 1 1 1 4 4 5 5 5 1 1 7 7 2 2 2 塊2 2 2 2 2 2 6 6 6 3 3 3 3 3 3 塊3 3 3 1 1 1 2 2 2 2 6 6 1 6缺頁 ´ ´ ´ ´ ´ ´ ´ ´ ´ ´ ´ ´ ´ ´ ´因此，LRU算法發生缺頁中斷的次數為15。在LRU算法

21、中，最近最少使用的頁面被先換出。例如，當頁6要調入時，內存的狀態為5、2、1，考查頁6之前調入的頁面，分別為5、1、2、，可見2為最近一段時間內使用最少的，本次應換出，然后把頁6調入內存。 OPT 1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6 塊1 1 1 1 1 1 1 3 3 3 3 6 塊2 2 2 2 2 2 2 7 2 2 2 塊3 3 4 5 6 6 6 6 1 1缺頁 ´ ´ ´ ´ ´ ´ ´ ´ ´ ´ ´因此，OPT算法發生缺頁中斷

22、的次數為11。在OPT算法中，在最遠的將來才被訪問的頁面被先換出。例如，當頁6要調入時，內存的狀態為1、2、5，考查頁6后面要調入的頁面，分別為2、1、2、，可見5為最近一段時間內使用最少的，本次應換出，然后把頁6調入內存。4.3 練習題一、選擇題（選擇一個正確答案的代碼填入括號中）1. 通常，用戶編寫的程序中所使用的地址是（ ）。A邏輯地址 B物理地址 C絕對地址 D內存地址2. 可由CPU調用執行的程序所對應的地址空間為（ ）。A符號名空間 B虛擬地址空間 C物理空間 D邏輯地址空間3. 把邏輯地址轉變為內存物理地址的過程稱作（ ）。 A編譯 B連接 C運行 D重定位4. 經過（ ），目標

23、程序可以不經過任何改動而裝入物理內存單元。A靜態重定位 B動態重定位C編譯或匯編 D存儲擴充5. 動態重定位是在程序（ ）期間，每次訪問內存之前教學重定位。 A執行 B編譯 C裝入 D修改6. 在分時系統中，可將進程不需要或暫時不需要的部分移到外存，讓出內存空間以調入其他所需數據，稱為（ ）。A覆蓋技術 B對換技術 C虛擬技術 D物理擴充7. 分區管理中進行分區的是主存的（ ）。A系統區域 B用戶區域 C程序區域 D整個區域8. 分區管理要求對每一個作業都分配（ ）的內存單元。A地址連續 B若干地址不連續C若干連續的頁面 D若干不連續的頁面9. 固定分區中各分區的大小是（ ）。A相同的 B相同

24、或者不同，但預先固定C根據進程要求確定 D隨進程個數而定10. 動態分區管理方式下，分配作業的主存空間根據（ ）。A 一張分區說明表B 一張分區說明表和一張空閑分區表C 一張“位示圖”構成的分區說明表D 由系統自定11. 在存儲管理中，為實現地址映射，硬件應提供兩個寄存器，一個是基址寄存器。另一個是（ ）。A控制寄存器 B程序狀態字寄存器C限長寄存器 D通用寄存器12. 可重定位分區存儲管理采用的地址轉換公式是（ ）。A 絕對地址=界限寄存器值+邏輯地址B 絕對地址=下限寄存器值+邏輯地址C 絕對地址=基址寄存器值+邏輯地址D 絕對地址=塊號´塊長+頁內地址13. 最先適應分配算法把

25、空閑區（ ）A 按地址順序從小到大登記在空閑區表中B 按地址順序從大到小登記在空閑區表中C 按長度以遞增順序登記在空閑區表中D 按長度以遞減順序登記在空閑區表中14. 最容易形成很多小碎片的可變分區算法是（ ）。A最先適應算法 B最佳適應算法C位示圖法 D以上都不是15. 下列存儲管理方案中，不采用動態重定位的是（ ）。A頁式管理 B可變分區 C固定分區 D段式管理16. 在分頁存儲管理系統中，從頁號到物理塊號的地址映射是通過（ ）實現的。 A段表 B頁表 CPCB DJCB17. 在頁式存儲管理系統中，整個系統的頁表個數是（ ）個。A1個 B2個 C與頁面數相同 D和裝入主存的進程個數相同1

26、8. 虛擬存儲技術是（ ）。A擴充內存空間的技術 B擴充相對地址空間的技術C擴充外存空間的技術 D擴充輸入輸出緩沖區的技術19. 虛擬存儲器的容量是由計算機的地址結構決定的，若CPU有32位地址，則它的虛擬地址空間為（ ）。 A100K B640K C2G D4G20. 在請求分頁虛擬存儲管理中，若所需頁面不在內存中，則會引起（ ）。A輸入輸出中斷 B時鐘中斷C越界中斷 D缺頁中斷21. 下列存儲管理方案中，不要求將進程全部調入并且也不要求連續存儲空間的是（ ）。A固定分區 B可變分區C頁式存儲管理 D請求分頁式存儲管理22. 存儲管理中，頁面抖動是指（ ）。A 使用機器時，屏幕閃爍的現象B 被調出的頁面又立刻被調入所形成的頻繁調入調出現象C 系統盤有問題，致使系統不穩定的現象D 由于主存分配不當，偶然造成主存不夠的現象23. 在頁式虛擬存儲管理系統中，LRU算法是指（ ）。A