第 3 章 內存管理

【考綱內容】

1.內存管理基礎：

????????1.內存管理的基本概念：邏輯地址空間與物理地址空間；地址變換；內存共享；內存保護；內存分配與回收；

????????2.連續分配管理方式；

????????3.頁式管理；

????????4.段式管理；

????????5.段頁式管理

2.虛擬內存管理：

????????1.虛擬內存基本概念；

????????2.請求頁式管理；

????????3.頁框分配與回收；

????????4.頁置換算法；

????????5.內存映射文件 (Memory - Mapped Flics)；

????????6.虛擬存儲器性能的影響因素及改進方法

【考情統計】

年份	單選題	綜合題	總分值	考點
2009	2	1	12	內存保護、地址變換、EAT、LRU、駐留集、分頁
2010	2	1	12	動態分區、二級頁表、分頁、地址變換、置換算法
2011	3	0	18	缺頁中斷、抖動、地址變換、TLB
2012	1	1	10	虛存概念、駐留集、置換算法、局部性原理
2013	1	1	10	缺頁中斷、分頁、地址變換、二級頁表
2014	3	0	6	地址變換、TLB、置換算法、多級頁表
2015	2	1	10	LRU、頁框分配、分頁、二級頁表、地址變換
2016	3	1	20	置換算法、分段、地址變換、工作集、分頁、TLB、缺頁中斷
2017	1	1	9	內存回收、分頁、二級頁表、地址變換
2018	0	1	8	分頁、地址變換、置換算法
2019	4	0	8	段共享、LRU、二級頁表、地址變換、動態分區、外部碎片
2020	1	1	10	EAT、二級頁表、地址變換、局部性原理
2021	2	1	12	置換算法、二級頁表、分頁、地址變換、TLB、LRU
2022	2	0	4	缺頁中斷、置換算法
2023	2	0	4	虛擬內存管理、頁框分配
2024	1	1	9	空閑分區分配與回收、內存管理綜合題

【考點解讀】

????????基本概念和連續存儲多以選擇題形式考查，非連續分配的段式和段頁式往年也多以選擇題形式考查。非連續分配中的分頁式往年會結合虛擬存儲和計算機組成原理進行考查，也有單獨考查的情況，但一般會深入到多級頁表層次的內容。

????????虛擬存儲中虛存概念往年多以選擇題形式考查。頁框分配、置換算法和性能分析都是屬于有時單獨以選擇題形式考查，也有時會結合請求分頁進行綜合性大題考查的內容。請求分頁在往年考查中，多以大題形式出現，往往會與計算機組成原理結合考查。

【復習建議】

對于本章內容提出以下建議：

????????1.基本概念一節概念性知識較多，考生要宏觀把握內存管理的目的和功能，重點把握邏輯地址和物理地址、程序的裝入和鏈接、內存保護三部分內容。

????????2.連續存儲一節，考生應宏觀把握各種分區方法的優缺點及適用場景，重點掌握固定分區和動態分區。重點理解固定分區的分區方法和所需數據結構。重點掌握動態分區的分配與回收流程，做到能夠自己詳細地口述這一過程并對設定情景進行模擬。

????????3.對于非連續方式，考生應宏觀把握各種分區方法的優缺點及適用場景。考生需要重點掌握不含 TLB 和含 TLB 的地址變換流程，并熟練掌握一級及多級頁表的地址變換計算。分段和段頁式重點在理解概念。

????????4.虛擬存儲器概念一節，考生應著重理解虛擬內存概念和局部性原理，并清楚虛擬內存的容量是如何決定的。

????????5.請求分頁一節是本章考查重點，多以大題形式考查，該類大題一般可分為兩種。其一是結合多級頁表進行考查，其二是結合虛擬內存和組成原理中 cache 部分內容綜合考查。考生需了解請求分頁方式下頁表各個字段的含義和用處，重點掌握地址變換及缺頁中斷流程，并能夠對特定情境按照流程手動模擬。

????????6.頁框分配一節極少單獨考查，一般放入題干中作為條件，考生需要理解三種分配策略和兩類調入策略的相關概念。

????????7.頁面置換算法一節，考生應宏觀把握各個算法的優缺點及適用場景，并能夠手動模擬算法流程。著重理解 LRU 和 CLOCK 系列算法，并理解 FIFO 算法所存在的 Belady 異常現象。

????????8.內存映射方法是考綱中較新的內容，考生應了解該方式的相關概念。

????????9.虛擬存儲器性能分析一節也是本章的重點內容，考生應當能夠熟練進行內存訪問有效時間的計算，并對計算過程進行分析。重點了解抖動與工作集的概念，理解工作集的評估是如何利用局部性原理的。

以下問題需要讀者在學習的過程中著重思考：

????????1.為什么要進行內存管理？內存管理有哪些功能？

????????2.各非連續存儲管理方式中，邏輯地址變換為物理地址的流程是如何的？

????????3.為什么要引入虛擬存儲器？虛擬存儲器為什么有效？

????????4.影響虛擬存儲器性能的因素主要有哪些？

3.1 基本內存管理

3.1.1 基本概念

1.內存管理
????????內存是計算機中一種有限的重要資源。雖然隨著計算機硬件技術的發展，計算機的內存容量有了巨大的提高，但想要放入全部的程序和數據依舊是不可能的，正如帕金森定律所述：“不管存儲器有多大，程序都可以把它填滿。” 所以對計算機內存進行合理且有效的管理是必要的。

內存管理主要包括以下內容：
????????(1)?內存的分配與回收：采取不同的分配與回收策略，記錄內存的使用情況，使計算機系統可以合理高效地利用內存資源。
????????(2)?地址轉換：由于進程的邏輯地址與其在內存中的物理地址可能存在不一致，系統需要對進程的地址進行轉換，即將進程的邏輯地址轉換為物理地址。
????????(3)?內存空間的邏輯擴充：采用虛擬存儲器技術將內存從邏輯上進行擴充，從而高效利用內存并解決了大程序無法裝入內存的問題。
????????(4)?內存共享：使不同的進程之間共享同一部分內存。共享內存的用途在于讓不同進程之間相互通信，以及減少內存的占用。
????????(5)?內存保護：采用界地址保護和存取訪問控制等方式，控制進程只能訪問自己有權訪問的內存部分，從而防止用戶進程對操作系統的干擾或用戶進程之間的相互干擾。

????????內存管理由操作系統執行，上層程序用戶并不需要關心其實現細節，這有效提高了計算機系統的易用性，提高了上層編程人員的開發效率。接下來從現代存儲系統的多層結構開始，逐一對內存管理的各項功能做詳細介紹。

2.多層結構存儲系統
????????存儲系統的層次結構如圖 3.1 所示，在層次結構中，越上層的存儲器越接近 CPU，傳輸速度越快。本章主要介紹的層次為 CPU 寄存器、主存儲器和輔存儲器，其中的寄存器和主存儲器可稱為可執行存儲器。可執行存儲器與 CPU 直接交互，系統可以在較少的時鐘周期內使用一條 load 或 store 指令對其進行訪問，相較于輔存儲器一般能快 3 個數量級甚至更多。

????????【提示】固定磁盤和可移動存儲介質都屬于輔存儲器，也可稱外存。

????????主存儲器：又稱主存或內存，程序在運行前需要先裝入到主存中。主存與 CPU 直接交互，其運行速度與 CPU 相比較慢。為了緩和二者之間的速度差異，在主存儲器之上引入了寄存器和高速緩存，其中高速緩存（Cache）與快表（Translation Lookaside Buffer, TLB）原理相似，其設置在主存和 CPU 寄存器之間。TLB 和 Cache 的存取速度快，TLB 中存儲部分頁表以加快 CPU 對頁表的訪問，Cache 中存儲部分內存塊中的內容以加快 CPU 對進程文件的訪問。

????????寄存器：寄存器造價高昂，在計算機中數量較少。其存取速度與 CPU 相近，多用于存放操作數等運行時數據，從而減少進程的訪存耗時。

3.內存空間結構
????????內存由一系列大小相同的存儲單元組成，存儲單元從 0 開始依次編址，一般來說編址單位可以是字節或字。按照字節（字）編址，是指該內存以一個字節（字）為一個存儲單元，從 0 開始依次編址。

????????【提示】考生在內存相關題目中務必認真審題，仔細看清題干中對編址方式的說明。若不做特殊說明，在本文接下來的敘述中，內存默認按照字節編址。

????????內存大小中常見的單位換算：1T=2^10G=2^20M=2^30K=2^40

????????內存空間通常還會被劃分為系統區和用戶區。系統區僅供操作系統使用，位于內存的低址部分，本文講述的內存分配任務大都在用戶區進行。

????????【舉例】《古劍奇譚?夢付千秋星垂野》大小為 35GB。其中 35G 為數字，B（字節）為單位。若內存單元是以字節編址的，則該游戲要占用35×2^30個內存單元。每個內存單元對應一個地址，依次為，則至少需要[log2?35G]=36位的二進制數才能完全表示。

????????考生可以發現，大多數家用計算機都沒有 35GB 的內存，并不能將該游戲裝入內存之中，但卻可以運行該游戲（游戲官方給出的最低內存要求是 8GB）。這其中的原委將在虛擬內存一節敘述，考生可以在此之前思考一下。

4.進程的內存映像
????????進程的內存映像是指系統在內存中存放可執行程序文件的方式。

? ? ? 進程初始化時，系統為進程分配存儲空間，并在系統區為進程建立進程控制塊（PCB）。PCB 是系統用以控制和管理進程的文件，其中記錄了該進程的各種信息，之后將提到的進程頁表起始地址就被記錄在其中。

通常進程在內存中的存儲情況如圖 3.2 所示，主要被分為如下四個部分：
????????(1)?代碼段：代碼段又稱文本段，是程序裝入內存的二進制代碼，通常不可修改。代碼段可重入，適合實現多進程共享。
????????(2)?數據段：存放全局變量和靜態變量等程序數據的部分，可讀寫。數據段在進程初始化后就具有一定大小，data 部分以確定的值初始化，隨后在運行中被更改。
????????(3)?堆：堆區初始化為空，c 語言中可用 malloc 和 free 動態地申請和釋放該部分空間。
????????(4)?棧：棧區初始化為空，隨著程序的運行增長和縮減。如果調用函數需要的存儲空間較大，寄存器不能滿足需求，系統則會在進程棧區為其開辟一個棧幀，用以存儲傳遞的參數、返回地址及各種局部變量等信息。

5.邏輯地址和物理地址
????????邏輯地址寬泛來講是指與當前數據在內存中的實際物理分配地址無關的訪問地址，邏輯地址的范圍稱作邏輯地址空間，但需要注意的是在計算機中講邏輯地址就等同于在講相對地址。相對地址是邏輯地址的一種特例，指當前存儲單元相對于程序開始處的存儲單元的位置。邏輯地址是一個十分重要的概念，它將操作系統的上層用戶從內存管理任務中解放出來，編程人員在編寫程序的時候不再需要關心程序在內存中的實際存放位置。

????????【提示】若不做特殊聲明，接下來講述中所提到的邏輯地址都是指相對地址。

????????物理地址又稱絕對地址，是指數據在內存中存放的實際位置，物理地址的范圍則稱作物理地址空間。系統需要使用物理地址來訪問內存中的程序數據，所以在進行訪存時需要進行地址變換。地址變換指的便是將數據的邏輯地址轉換為物理地址的這一過程。

????????圖 3.3 和圖 3.4 分別展示了沒有邏輯地址和引入了邏輯地址的內存訪問流程（圖中的虛擬地址是邏輯地址的一種，這將在虛擬內存部分詳細說明）。

????????【舉例】編程人員編寫程序時，需要訪問數組的某個元素。此時編程人員只需要使用高級程序語言說明，現在需要訪問數組的第 n 個元素，系統就能據此結合數組起始地址來訪問到該元素，而不需要指定其在內存中的實際內存地址。這里的第 n 個元素實際就是一種邏輯地址的概念（實際的邏輯地址是在編譯后形成的），而數組元素被存放的實際內存地址就是物理地址。

????????在各種內存管理方式中，分頁存儲管理方式和分段存儲管理方式可以較好地體現邏輯地址到物理地址的轉換，并且較為重要。圖 3.5 和圖 3.6 分別給出了這兩種方式的地址轉換簡圖，這將在對應章節詳細講解，此處了解即可。

6.重定位
????????重定位是指將程序文件裝入到與其文件內部地址空間不一致的外部地址空間時，需要完成的地址修改過程。這個過程可能發生在程序文件裝入、內存置換和緊湊等過程中。重定位可分為靜態重定位和動態重定位。

????????靜態重定位是指程序文件在被裝入內存時，一次性完成地址的修改，重定位在程序運行前就已經完成。下一節介紹的可重定位裝入方式就是采用了靜態重定位。

????????動態重定位是指在 CPU 訪問文件時使用動態地址變換機構這類硬件來自動完成地址變換，重定位發生在程序執行時。下一節介紹的動態運行時裝入方式就是采用了動態重定位。

7.程序的裝入和鏈接
????????從源程序到執行進程主要需經過三個步驟：編譯、鏈接和裝入，源程序經過編譯成為一組目標模塊（此時形成邏輯地址），然后經過不同的鏈接和裝入過程成為執行進程。

? ? ? ? ?(1)?編譯：使用相關編譯程序編譯源程序，形成一系列的目標模塊 。
????????(2)?鏈接：使用鏈接程序將編譯所形成的目標模塊連同所需要的相關庫函數鏈接在一起，形成一個完整的裝入模塊。這期間需要對目標模塊內的地址數據做修改 ，形成邏輯地址。
????????(3)?裝入：使用裝入程序把鏈接形成的裝入模塊裝入到內存 ，形成物理地址。

(1)?程序的裝入
????????①?絕對裝入方式：絕對裝入方式是指在預先知道裝入位置時，在編譯過程中就將邏輯地址轉換為物理地址。這一裝入方式只適合于單道程序系統，因為在大多數系統中，程序的裝入位置都是無法預先知道的。
????????②?可重定位裝入方式：可重定位裝入方式是指在裝入的過程中，根據裝入位置將裝入模塊中的邏輯地址修改為物理地址，即裝入前是邏輯地址，裝入后是物理地址。可重定位裝入方式克服了絕對裝入方式的缺點，不再需要預先知道裝入位置，但該方式不允許程序在運行時移動位置。
????????③?動態運行時裝入方式：動態運行時裝入是指模塊被裝入內存后不更改其中的邏輯地址，邏輯地址轉換為物理地址的過程被推遲到模塊執行時。系統需要提供一個基址寄存器（記錄程序起始地址 ）來支持這一地址變換過程，即物理地址 = 基址寄存器中的程序起始地址 + 邏輯地址。目標模塊在裝入后有可能還會調動位置，動態運行裝入方式可以很好地應對這一情況。

????????【提示】采用動態運行時裝入方式，程序在裝入內存后，所有地址依然是邏輯地址；只有在程序執行時，才會進行邏輯地址到物理地址的轉換。

(2)?程序的鏈接
????????(1) 如圖 3.9 所示，靜態鏈接方式是指將編譯獲得的目標模塊在裝入前鏈接成一個完整的裝配模塊后，再將其裝入內存。
????????(2) 裝入時動態鏈接是指將目標模塊一邊裝入內存一邊進行鏈接，優點如下：
????????(a) 由于目標模塊并未被提前鏈接為一個整體，方便單獨修改其中的一個或幾個目標模塊，而不需要重新打開整個裝入模塊。
????????(b) 方便對其中的一個或幾個目標模塊進行重用，多個不同的裝入模塊可以使用同一個目標模塊。
????????(3) 運行時動態鏈接是指在運行前不將目標模塊鏈接成整體，而是在程序運行過程中需要用到某一模塊時，再將該模塊調入內存進行鏈接。此方式可以加快程序裝入過程，同時節省內存空間。

8.內存保護
????????在多道程序處理系統中，為了保證進程運行的確定性和穩定性，需要為進程設置內存保護機制，以防止用戶進程對操作系統的干擾及用戶進程之間的互相干擾。內存保護是指設置一定的機構來保證進程在未被允許的情況下，不能訪問分配給其他進程的內存空間，從而保護進程數據不受外界干擾，實現存儲安全。

????????內存保護中檢查進程所要訪問的內存單元是否屬于自己，通常需要在運行時來檢查所有的內存訪問。在分頁分段等存儲方式中，統一在地址變換機構中實現了內存保護。

通常的內存保護機構有以下兩種：
????????(1) 一對上下限寄存器，分別記錄當前作業的起始地址和尾址。CPU 訪存時驗證訪問地址是否處于二者之間。
????????(2) 一個重定位寄存器（或基址寄存器）和界地址寄存器（限長寄存器）。重定位寄存器記錄作業的起始地址，界地址寄存器記錄作業的長度，CPU 訪存時比較訪問地址是否處于起始地址和尾址（尾址 = 起始地址 + 長度 ）之間。

9.內存共享
????????在多道程序處理系統中，幾個不同的用戶可能同時運行相同的程序，此時若在內存中為每一個用戶進程都保留該程序的一個副本，則較為浪費內存空間。采取內存共享則可以有效地避免同一程序的不同副本帶來的內存浪費。

????????內存共享是指當多個用戶進程需要用到同一個程序文件時，只在內存中保留該程序文件的一個副本，令共享該程序文件的進程都指向其所在的內存空間。由于進程運行時可能會對程序文件進行修改，這會造成不同進程之間的互相影響。所以被共享的內容應當是那些不會被修改的部分，這部分代碼被稱之為可重入代碼又稱為 純代碼。

????????通常可將程序分為指令部分 I 和數據部分 D，其中的指令部分通常不會被修改。若程序能做到 I 和 D 的分離，將有利于進行內存共享。

????????但是對 I 部分的共享依舊存在一定的問題，雖然 I 部分不會被修改，但當某個共享進程不再使用共享內容時，該部分文件將會被調出內存，這會造成其他共享進程的大量缺頁。所以，對于被共享的文件內容，應當在所有共享進程都不再需要其時，再將其調出內存。要確定該文件內容是否已被所有共享進程所釋放，系統需要遍歷所有進程的頁表，這一操作的代價較大。所以，系統中通常需要為此設立一個新的數據結構，用以記錄內存中的共享內容、當前有多少進程共享該內容等信息，段式內存管理方式中介紹的共享段表便是這類數據結構的一種。

3.1.2 連續分配管理方式

????????連續分配管理方式指系統為需要運行的程序分配一片連續的內存空間，并將其裝入到這片空間中。該類方式需要將程序文件完整地放入到內存的一片連續空間里，即意味著對于單個程序，其文件的物理地址是相鄰的。

????????連續分配管理這一類方法的想法比較直接，是最早出現的內存管理方式，主要包括單一連續分配、固定分區分配、動態分區分配。其中的動態分區分配如果使用了動態重定位實現緊湊來解決外部碎片問題，則被稱為動態可重定位分區分配。

1. 單一連續分配

????????單一連續分配方式是指系統將用戶區整體分配給一個進程單獨使用，該方式只適用于單道程序環境。

????????在單用戶單任務的操作系統中，機器由一個用戶獨占，不存在其他用戶的干擾，所以可以不設置存儲器保護措施，該方式安全性較高且容易實現。

????????單一連續分配方式下操作系統不能并發，CPU 有大量時間處于空閑狀態（如等待 I/O），機器運作效率低下。
????????(1)?優點：無外部碎片，無需內存保護，安全性較高且容易實現。
????????(2)?缺點：有內部碎片，存儲器利用率低，無法運行多道程序，操作系統效率低。

????????【提示】內部碎片和外部碎片將在本章的后續部分闡明，此處只需對此有一定印象即可。

2. 固定分區分配

????????20 世紀 60 年代及之后出現的多道程序系統，能同時將多個程序裝入到內存之中。為了使程序之間互不影響，需要為這些程序各分配一片獨立的內存空間，固定分區分配方式就是可以滿足多道程序系統要求的內存管理方式之一。

????????固定分區分配方式是指在初始化時將內存空間分割成固定大小的區域，當有程序需要運行時，系統從內存中尋找一片合適的空閑分區分配給該程序。等程序運行結束后，系統再將這片區域回收，并從待運行程序隊列中選擇一個合適大小的程序裝入。

(1)?分區方法

????????·分區大小相等：所有用戶空間的內存分區大小是一樣的，這種方式靈活性較差，程序較小則會產生內部碎片，程序較大則無法裝入。

????????·分區大小不等：根據用戶運行程序大小的統計分布規律來決定用戶空間的分區大小比例。內存通常被分為較多的小區域，適量多的中等區域，較少的大區域。裝入程序時，根據程序的大小選擇合適的分區，從而減少內部碎片造成的浪費，也在一定程度上緩解了大型程序無法裝入運行的棘手問題。

(2)?內存分配方法

·需要的數據結構
????????為了實現固定分區分配方法，系統需建立一張分區說明表，用以記錄用戶空間的區域分配情況。如下表所示，分區說明表包括分區號、分區大小、起始地址和分配狀態四個表項，通過大小和起始地址兩項可以完全描述分區的開始位置、結束位置以及空間大小。

·程序裝入過程
????????具體的程序裝入過程：當待運行程序隊列非空時，系統檢查分區說明表，為隊頭程序尋找一片合適大小的空閑分區，然后將其分配給該程序。
其中合適分區的尋找如下：

????????·對于等分區的方式來說，任何一個可以裝下該程序的區域都是等效的合適分區。

????????·對于不等分區的方式來說，常用策略是每次都選擇可以裝入該程序的最小分區。

(3)?優缺點分析

????????·優點：固定分區策略不存在外部碎片且實現簡單，是系統開銷很小的一種多道程序系統內存分配方法。

????????·缺點：① 預先劃分區域會導致一些大程序無法裝入。② 會產生較多的內部碎片。雖然使用分區大小不等的方法能使這種情況有所緩解，不過只有在系統初期就知道程序的大小分布時，該方式才能發揮出好的效果。

????????【提示】程序在裝入某個分區后，可能不會占滿該分區的所有空間，被浪費的這部分分區內部空間就被稱之為內部碎片。對于 “外部碎片” 的解釋見下一節。

3. 動態分區分配

????????動態分區方法是指系統在有待運行程序時，再從內存空間中劃分出一塊與程序大小相當的連續區域分配出去，而不是在初始化時就將內存劃分好。

(1)?外部碎片和緊湊
????????圖 3.11 表示內存空間的某個局部狀態，圖 a - d 表示我們在這片區域相鄰地裝入 A、B、C 三個進程，圖 e 和圖 f 表示 B 進程運行完成后被略小一些的 D 進程替換出內存。從 f 圖中可以看出此時在 D 進程和 C 進程之間有一塊僅 4MB 的小內存空間，這樣的空間就被稱為外部碎片，它很難再裝入一個完整的程序文件。這樣的過程可能在內存的各個局部頻繁發生，隨著機器運行，整個內存中會存在越來越多這樣的碎片。

????????假設系統中存在十個 4MB 大小的外部碎片，此時有個 20MB 大小的程序文件需要裝入內存，剩余內存空間大小是足夠的，但剩余空間的不連續導致這個 20MB 的程序無法裝入。

????????如果使用了動態重定位實現緊湊來解決外部碎片問題，則該方式被稱為動態可重定位分區分配。緊湊：操作系統移動內存中的程序，從而使程序之間相互連成一片。

????????緊湊方法將小空間合并成大空間，消除了外部碎片。但每次移動程序文件都要進行讀寫，并修改地址信息，系統開銷很大。因而操作系統需要設計巧妙的內存分配方法來盡量減少外部碎片的產生。

????????【提示】實際上為了避免產生太多細小的外部碎片，部分系統在分配內存空間時會設定一個閾值，在某一片連續空間中裝入程序文件后，當剩余的空間小于閾值時，將不再切割這片連續的內存空間，直接將這一片區域全部分配出去。

(2)?需要的數據結構

????????空閑分區表：在系統中設置一個空閑分區表來管理內存，一個連續的空閑空間占用一個表目。如下表所示，表中包括分區號、分區大小、分區起始地址、分區狀態等表項。

?

????????空閑分區鏈：下圖所示為空閑分區鏈，其在所有空閑分區頭尾都添加了有關分區狀態的信息以及指向上個、下個空閑分區的指針，用雙向鏈表的方式將所有的連續空閑空間串起來。

(3)?分配算法
????????不同于先前提到的固定分區方法，動態分區方法的每次空間分配都在改變內存空間的分區情況。所以在為用戶程序分配內存空間時，需要充分考慮到這次分配對內存空間分區的影響。這就要求系統采取合適的策略來為程序選擇裝入分區，以達到高效利用內存空間的目的（主要是避免外部碎片）。常見的分配算法如下：
①?首次適應算法 (First Fit, FF)
????????首次適應算法是指將空閑分區按照地址升序排序，每一次都從頭向后查找，在第一個足以容納該程序的連續空間中劃分出程序所需的空間。
????????該方法傾向于使用低址空間，優點：保留了高址空間的大連續空間，利于后續到來的大程序裝入。缺點：① 頻繁在低址部分劃分空間，容易在這部分區域留下較多的外部碎片。② 每次查找都從低址開始，查找開銷偏大（低址空間被優先分配出去了，但被查找的頻率卻最為頻繁）。
②?循環首次適應算法 (Next Fit, NF)
????????循環首次適應算法是指將空閑分區按照地址升序排序，設置一個查找指針從頭向后查找，隨后的每一次查找都從上次查找后指針的停留位置開始。
????????優點：該方法可以在一定程度上緩解首次適應算法的兩個弊端，使得空閑分區分布的更為均勻。缺點：該方法會將本可保存在內存末尾的大空閑區域分裂為小空閑區域，會造成缺少大空閑分區的狀況。
③?最佳適應算法 (Best Fit, BF)
????????最佳適應算法是指將空閑分區按大小升序排列，依次查找，選擇第一個可以容納程序的空間分配出去。該方法選取最小的可以容納程序的空閑分區進行分配。
????????優點：能留下更多大分區以滿足大進程需求，缺點：該方式從整體空間的利用效率來看不一定是真正的最佳，因為這樣劃分容易留下許多小空間分區，其外部碎片是這四種方法中最多的。該算法需要對空閑分區按大小排序，開銷大。
④?最壞適應算法 (Worst Fit, WF)
????????最壞適應算法指選擇所有空閑分區中最大的分區來分配給程序，若最大的空閑分區不夠大，則分配失敗。優點：可以減少外部碎片的產生，缺點：使得內存中缺少大空閑分區。

????????無論何種方法，都有各自的優點和缺點。為了減少外部碎片往往會造成大空閑分區的缺失，而反過來也是相同。所以在選擇方法時，需要在這二者之間尋得一個合適的平衡點。實際上，看起來最簡單的首次適應法在實際使用中的效果最好，它實現起來簡單，需要的額外開銷小，并且處于最佳適應和最壞適應之間，較為均衡。

(4)?回收內存
????????程序運行完成后要釋放相應的內存空間，系統需要將該空間回收，并加入到空閑分區表（鏈）中。下面以空閑分區表作為被使用的數據結構來詳細介紹一下內存回收的過程。
回收的內存空間可能出現以下四種情況：
????????(a) 回收空間的頭與尾都不與任何空閑區域相鄰，則在空閑分區表中增加一個表項來記錄該回收空間。
????????(b) 回收空間的頭部與一個空閑區域相鄰，則在該空閑區域表目中的空間大小數據項里加上所回收空閑區域的大小。
????????(c) 回收空間的尾部與一個空閑區域相鄰，則除了在該空閑區域表目中的空間大小數據項上加上所回收空間區域的大小，還要將起始地址數據項改為回收空間的起始地址。
????????(d) 回收空間的頭部及尾部都與現有空閑區域相鄰，則要合并這兩個空閑區域的表項，新表項的起始地址為低地址的空閑區域的起始地址，空間大小為三者的和。

【例 3.1】某計算機按字節編址，其動態分區內存管理采用最佳適應算法，每次分配和回收內存后都對空閑分區鏈重新排序。當前空閑分區信息如下表所示。回收起始地址為 60K、大小為 140KB 的分區后，系統中空閑分區的數量、空閑分區鏈第一個分區的起始地址和大小分別是 ()
A. 3、20 K、380 KB
B. 3、500 K、80 KB
C. 4、20 K、180 KB
D. 4、500 K、80 KB

????????????????????????????????????????????????表 3.3 空閑分區情況

分區起始地址	20K	500K	1000K	200K
分區大小	40KB	80KB	100KB	200KB

????????解：應選 B，回收分區的起始地址是 60K 與起始地址為 20K 的分區相鄰，尾部地址是 60 + 140 = 200K 與起始地址為 200K 的分區相鄰。所以應當將這三個分區合并成一個起始地址為 20K，大小為 380KB 的空閑分區。所以系統中此時存在三個空閑分區。
????????題目說明了，每次回收內存后都對空閑分區鏈重新排序。根據題目給出的空閑分區信息可以看出，空閑分區鏈是按照分區大小升序排序的。所以第一個即是最小的分區，該分區的起始地址為 500K 大小為 80KB。

連續存儲管理方式相關總結如下表所示。

【提示】建議考生在學到此處時，先將本節末的 1 - 16 小題完成，以鞏固相關知識。

3.1.3 非連續分配管理方式

1. 非連續存儲概述

????????非連續分配管理方式是指將一個完整的程序分割開，放入不相鄰的空閑分區中。
????????非連續分配管理方式有效地解決了連續存儲方式中存在的內存浪費（外部碎片）問題。不過由于需要存儲額外的索引信息，該種方式下內存的存儲密度比連續存儲管理方式更低。

????????【提示】存儲密度是指有效信息在所有存儲信息中的占比。

????????按照程序邏輯空間分割大小是否固定，可分為分頁存儲管理方式、分段存儲管理方式以及將二者相互結合的段頁式存儲管理方式。分頁（段）存儲管理方式按照是否有請求調入和頁面置換功能，可以分為基本分頁（段）存儲管理方式和請求分頁（段）存儲管理方式。

????????分頁存儲管理和分段存儲管理方式將在本章接下來的內容中講解，而請求分頁管理方式則會在下一章節再做敘述。

內存管理方式分類如圖 3.13 所示。

2. 分頁存儲管理方式

頁面（Page）：將程序空間（即邏輯地址空間）分割成大小固定的塊，這些塊稱為頁面。
頁框（Frame）：將內存空間（即物理地址空間）分割成大小固定的塊，這些塊稱為頁框（頁框的大小與頁面相同）。

????????【提示】應選擇適中的頁面大小，并且該大小應是 2 的指數倍，主要選擇設定在 1KB - 8KB 這個范圍內。因為頁面設置過大會導致內部碎片的增加，而頁面設置過小則會使得一個程序占據過多的頁面，使頁表變得過于龐大，降低存儲密度。

????????分頁存儲管理方式是指將程序地址空間分割成一定大小的頁面，按照一定的策略將這些頁面調入到內存的頁框中。同一個程序的頁面被調入到的頁框不一定相鄰，系統為了管理這些分散的頁面，需要為分頁管理方式建立一個稱之為頁表的索引。

(1)?地址結構

????????如圖所示，系統按字節編址，用 32 位二進制數來表示程序的邏輯地址。32 位的二進制數可以表示的范圍是～，每個數字對應一個內存單元，共可編址 4G 個內存單元。每個內存單元的大小是 1B，所以這一長度的地址可表示的程序最大應為 4GB。

????????現在將頁面大小選定為 4KB，即進程最多有4GB/4KB=1M頁。其中第 0 頁所占的地址號為：0x00000000?0x00000fff，可以看到，地址的高 20 位（可以表示 1M 頁）所表示的數字便是頁號，低 12 位（可以表示 4KB 空間）表示的數字則是該內容在頁內的偏移量。

(2)?頁表
????????在連續分配方式中，只需要在進程的 PCB 里記錄其在內存中的首地址及程序大小，就可以輕松地找到該程序。但在分頁存儲管理方式中，程序文件的頁面被分配在了內存中不相鄰的分區中。于是系統需要提供一種被稱為頁表的數據結構來記錄頁面與頁框的對應關系，每一個進程都有自己的頁表。如圖 3.15 所示，頁表內包含一系列大小固定的頁表項，頁表項中記錄了進程某一頁所對應的頁框號，頁號則隱含在頁表項相對頁表起始地址的偏移量中。

(3)?地址變換
????????由于地址變換的發生頻率較高，理論上使用硬件來完成地址的變換能有效提高系統的運行效率。但是，為每一個頁面都分配一個寄存器用以實現頁表結構的代價十分昂貴，所以，系統通常只好將頁表置于內存空間中，在系統中只設置一個頁表寄存器來存放頁表的起始地址。

????????【提示】多核 CPU 中，每個核心都有一套寄存器，其中就包括頁表寄存器。所以在多核 CPU 中頁表寄存器不只有一個，CPU 中的每個核心都有一個頁表寄存器。

????????頁表的起始地址在程序裝入時被記錄在該頁表進程的 PCB 中，當該程序上處理器時，才將頁表起始地址存入頁表寄存器（PTR），這樣的實現方式下，所有進程可以共用一個頁表寄存器。

接下來詳細地介紹將程序的邏輯地址轉換為物理地址的過程。
①?基本的地址變換機構
如圖 3.16 所示，當進程需要訪問某個邏輯地址時，從邏輯地址到物理地址的變換過程如下：

? ? ? ??將邏輯地址的頁號與頁表長度做比較，若頁號大于頁表長度，則越界。

? ? ? ? 若未越界，則通過頁號在頁表中定位到相應的頁表項，再從該頁表項中獲得對應的頁框號（塊號）。

????????最后將頁框號和邏輯地址中的頁內偏移量組合在一起，形成對應的物理地址。

②?具有快表（TLB）的變換機構
????????從前面的變換流程中可以看到，系統想要訪問一個邏輯地址時，需要訪問兩次內存；第一次從內存里的頁表中取出頁框號，第二次根據物理地址取出相應的數據。
????????系統的訪存開銷相較于連續分配管理方式增加了很多，這是因為多出了一次對內存中頁表的訪問。如果可以把頁表存放在一個訪問速度更快的存儲器件中，就可以大大減小這一開銷。
????????為了提高訪問效率，系統可以在 CPU 的 Cache 中設置一個具有并行查找能力的高速緩存來存儲頁表，這個存儲器被稱之為快表（也稱 TLB），使用相聯存儲器實現。由于高速緩存造價昂貴無法做到很大，所以快表只是存儲了頁表的一小部分。

????????加入快表后的變換過程如圖 3.17 所示。該變換過程與未加入快表時的不同之處，在于系統會先從快表中查找該邏輯地址所對應的頁框號。若快表中未找到就去內存中的頁表里查詢（也可實現為同時查找），并將查詢到的頁表項存入到快表中。當快表存滿時就涉及如何選擇合適的頁表項換出的問題，這與虛擬內存中的頁面置換方法相似，將在下一章中再做詳細介紹。

????????接下來分析設置快表對系統帶來的影響，先引入內存的有效訪問時間（Effective Access Time，EAT）這一概念，它代表從進程發出地址訪問請求到從內存中獲得該地址對應物理地址中所存數據的這一段時間。
????????在只有一級頁表的分頁管理方式中，EAT 主要包括第一次訪問內存從頁表中獲得頁框號，以及第二次訪問內存獲得所需要的文件內容這兩部分。在引入快表后，第一次訪存時間以一定概率被替換成訪問快表的時間，這個概率稱之為快表命中率，即每次地址變換能直接從快表中獲得頁框號的幾率。采用合適的調度算法，可以將快表的命中率控制在 90% 以上，而快表的訪問時間遠遠低于訪存時間，從而使得內存的有效訪問時間大大減小。

????????【舉例】假設系統訪問快表用時 2μs，訪問頁表用時 500μs，快表的命中率為 90%，計算該系統訪問一個邏輯地址的 EAT。

????????快表和頁表串行訪問：(2+500)×0.9+(2+500+500)×0.1=552μs

????????快表和頁表并行訪問：(2+500)×0.9+(500+500)×0.1=551.8μs

若不使用快表，該系統的EAT=1000μs。可見，快表的引入較大地提高了系統的訪存效率。

????????【提示】實際上這里的快表機制與組成原理中的 Cache 方法是十分相似的，考生可以將二者放在一起閱讀學習，并且也可與后續的虛擬內存結合在一起分析對比。

(4)?兩級和多級頁表
????????如前所述，操作系統在進程的 PCB 中記錄頁表起始地址和大小，這意味著系統默認頁表只有一頁，但當進程較大時頁表也會很大，頁表本身也需要被劃分為許多頁，這些用來存儲頁表的頁在內存中同樣會是分散不連續的，此種情況下只在 PCB 中記錄頁表的起始地址將行不通。此外，現如今大多數家用計算機都是 64 位機器，大多使用 48 位二進制數表示程序的邏輯地址。如果頁的大小為 4KB，每個頁表項長 8B，那么每個進程的頁表都會占據驚人的248B/4KB×8B=512GB。這顯然是無法接受的。

????????因此設計者需要通過二級頁表的組織形式來映射這些較大的程序，以及減少對內存的占用。內層頁表是程序文件的索引，外層頁表是內層頁表的索引，PCB 中記錄的內容也就相應更改為外層頁表的起始地址。當然這依舊要求外層頁表只能有一頁，否則需要繼續向上疊加索引，最終保證最外層頁表只有一頁。

????????如圖 3.18 所示，外層頁表與內層頁表都是邏輯地址到物理地址的映射。二者的主要區別在于外層頁表所指向頁框中的內容是內層頁表，而內層頁表所指向頁框中的內容是程序文件。

????????使用二級頁表組織形式時，邏輯地址可被分割為圖 3.19 所示的三部分。使用頁目錄號從外層頁表中獲得包含所需內層頁表項的頁框，再根據頁號獲得包含所需內容的頁框，后續步驟則與單級頁表無異。當然，使用二級頁表組織形式時，外層頁表依舊可能很大，但設計者可以像套娃一樣不斷向上疊加頁表層次，直到最高層頁表不大于一個頁面，這就是多級頁表。

????????【提示】在敘述多級頁表時，不方便直接使用外層與內層來描述頁表層次。所以在接下來的內容中，將頁表按層次由內到外依次命名為 1 級至 n 級頁表。
????????需要注意的是，在題目中判斷頁表相對層次時，需要根據題目中出現的明確表述或者是地址結構形式。因為上述命名只是出于方便考慮，并無統一規定。但就 21 年 408 真題的第 29 題來說，未作說明應當以最內層作為 1 級頁表。
????????而本文是以最內層作為 1 級頁表來做敘述的，這是因為這一命名方式下，改變頁表總層次時，內層頁表名稱不會產生變更，有利于筆者描述計算過程和考生理解多級頁表的機制。

????????接下來以 16GB（邏輯地址共 34 位）的程序文件為例做一次具體的計算。假設系統按字節編址，頁面大小為 4KB，頁表項大小為 4B，那么該程序文件共分為16GB/4KB=4M頁。同樣可以計算出一個頁面所能存入的頁表項為4KB/4B=1K個，因此頁表應占據4M/1K=4K頁。將頁表使用二級頁表索引起來，則共有4K/1K=4頁二級頁表。因此系統應當進一步使用三級頁表來索引二級頁表，三級頁表只有一頁，其中包含有四個頁表項目，分別指向四個存儲有二級頁表的頁框。

????????多級頁表的內存訪問有效時間與一級頁表情況下的計算過程是相似的。前面分析中一級頁表需要一次訪問內存查找頁表的時間，那么從二級頁表的機制可知，二級頁表是一級頁表的頁表，即二級頁表需要有兩次訪問內存查頁表的時間，更高級別的時間只需類推即可。如上一段例子所述，該例中存在三級頁表，則需要三次訪問內存查頁表時間，得到物理地址后再訪問一次內存獲得數據，全程共四次訪問內存。

????????【提示】假設頁表有 n 級，訪問 n - 2 級頁表都是在獲得其低一級頁表中對應頁面的頁框號。而訪問 1 級頁表獲得的則是所需內容存儲位置的頁框號，這時將該頁框號與邏輯地址的頁內偏移量組合在一起得到的就是所需內容的物理地址。最后需要根據該物理地址再進行一次內存訪問，從而獲得所需要的程序內容。

3. 分段存儲管理方式

????????先前所介紹的這些內存管理方式都由操作系統來完成，其對工作于操作系統之上的用戶來說是透明的。分段存儲管理方式雖然在方法設計上與分頁存儲管理方式大同小異，但因其分段大小劃分的靈活性，可以較好地滿足用戶在編程和使用上的自組織需求，也因如此，這個方式對于用戶來說是不透明的。

????????【提示】計算機系統中的透明一詞的意思是指該過程對上層用戶不可見。上層用戶無需關注其實現細節，只需要知道該過程實現了什么功能，怎么使用這一功能即可。

????????我們容易將透明理解為某一過程的上層遮擋物是透明的，從而將某一過程透明理解為對上層用戶可見。實際上這里的透明與不透明指的是該過程本身而不是其上層遮擋物，所以透明是指某一過程對上層用戶不可見，就好像該過程穿上了隱身衣一般。

(1)?分段存儲管理方式的特點
????????分段系統是指將程序（邏輯地址）劃分為大小不等的塊，這些塊稱為段。分段管理方式方便用戶編程，利于編程人員組織程序的邏輯結構。該方式最根本的優點便是其管理方式的動態性和段的邏輯單位性，以下具體介紹其特點及優勢之處。
(a)?方便編程
????????匯編程序編寫通常按照自身邏輯關系被劃分為幾個段，這與分段管理方式的邏輯地址空間形式十分契合，所以分段管理極大地便利了程序員的程序編寫工作。
(b)?信息共享
????????分段中的段不同于分頁的頁面，這里的段是一個有內容共性的邏輯單位體，這個特性有效提高了程序段的可復用性，多個進程可以方便地共享某段內存文件的內容。

????????【提示】將段稱為有內容共性的邏輯單位體是指每一個段都有其明確的完整作用，而不會像分頁一樣，完成某個內容的程序文件可能被分割在不同頁中。

(c)?信息保護
????????同樣是因為程序段是一個邏輯單位的這一特性，系統可以方便地對特定的函數、數據等邏輯單位設定其讀寫方式和權限列表，有效保證進程的信息安全。
(d)?動態增長
????????進程在運行的過程中，有部分內容會隨著運行而增長，較為明顯的就是數據段。這種情況下，分頁存儲管理方式比較適合預先分配，不利于應對這一狀況，而分段系統中段長度可變，不需要確定各個段共同的固定大小，從而容易實現動態分配，可以較好地解決這一問題。
(e)?動態鏈接
????????動態鏈接中，為了提高內存的利用率，系統只將進程當前需要用到的程序內容裝入內存。對于實現這種動態鏈接的程序而言，該程序是一邊運行一邊進行鏈接的，其鏈接單元應當是一個個實現某一功能的獨立邏輯單位，這恰符合分段管理方式中段的劃分原則。所以分段管理方式十分利于實現動態鏈接。

(2)?分段系統的基本原理
(a)?地址結構
????????如圖 3.20 所示，分段管理方式中，程序文件被劃分為一個個邏輯單元，每個邏輯單元單獨成段。所以，與分頁系統相似，其地址結構由段號和段內地址兩部分組成。

(b)?段表
????????由于段與段之間的大小并不相等，所以想要記錄一個段的信息必須要有兩個變量，通常以段長和起始地址作為記錄變量。如圖 3.21 所示，段表中記錄了從段號到（段長，起始地址）數據對的映射，所以一個段表項應要同時包含以上三個信息，其中的段號隱含在段表項與段表起始地址的相對位置中（段表項的大小是相等的）。

????????段表項中包含該段在內存中的起始地址和段長兩個數據項，而其段號為該表項在段表中所處的位置次序。（段表項從 0 開始依次編號 ）

(c)?地址變換機構
分段存儲管理方式的地址變換機構如圖 3.22 所示。地址轉換過程如下：
????????① 將邏輯地址的高位段號取出，與段表長作比較，段號大于表長則越界。
????????② 若未越界，則找到相應段表項，將段長與邏輯地址低位的段內偏移量比較，若偏移量大于段長則越界。
????????③ 若未越界，則將段表項中的段起始地址與邏輯地址的段內偏移量組合起來，獲得對應的物理地址。

(d)?段的共享與保護
????????段的保護：由于分頁與分段的保護方式大致相同，在此做統一說明。分頁和分段的主要保護方式都為界地址保護和存取控制保護。
????????界地址保護通過邏輯地址與段（頁）表信息的比較來防止進程的越界訪問。在分頁方式中，將頁號與頁表的長度做比較，若頁號 > 頁表長度則產生越界中斷。需要說明的是分頁方式的頁內偏移量與頁表大小嚴格對應，不會造成越界。在分段方式中，段號和段內偏移量需要同時顯性給出，判斷訪問是否越界也需要進行兩次：1）若段號 ≥ 段表長度，則產生越界中斷。2）查詢段表時，若段內偏移量 > 段長，則產生越界中斷。
????????存取訪問控制通過對進程段（頁）進行訪問權限設置以保護其信息。系統內存中的段頁設置只讀、讀 / 寫、不可訪問等限制，訪問相關頁面時進行權限檢查。

????????段的共享：實現段共享時，除了每個進程自身的段表外，系統還設置了一個供相關進程共同使用的共享段表。如圖 3.23 所示，共享段表的表項中除記錄該共享段的物理地址等相關信息外，還設置了一個 count 字段用于記錄共享該段的進程數。

????????當P1?進程與P2?進程共享段S時，段S在內存中只有一份，P1?與P2?的段表中對該共享段的記錄與正常段相同，二者分別有一個段表項記錄該段的物理地址。同時共享段表中也會有一個表項記錄段S的物理地址等信息，并記錄共享段S的進程數及相關信息。需要注意的是，段S的物理地址是唯一的，但其在P1?和P2?中的邏輯地址是不同的。自然，段S在P1?段表、P2?段表與共享段表中的段號是不一定相同的，三者沒有必然關聯。
????????由于共享段被多個進程共享，在其中某一個進程釋放該段時，系統并不會直接調出該段，而是將共享段表中的 count 減去 1。只有當共享段的 count 減至 0 時，系統才會將該段調出內存。

????????【提示】在相關教材中，稱分頁的地址空間是一維的，而分段的地址空間是二維的。容易令考生產生困惑的是：分頁與分段的地址結構都被分為頁（段）號和頁（段）內偏移量兩個部分，而二者的空間維度卻不同。
????????從這兩種方式的地址結構來看，它們都由兩個變量組合而成，所以看上去都是二維空間。而之所以分頁的地址空間為一維，是由于頁號和頁內偏移量并不是兩個獨立變量。我們可以只給出某一數據在邏輯地址空間中的相對位置這一個變量，根據頁面大小來直接計算出數據處于的頁號和頁內偏移量。而分段系統中的段大小不等，所以段號和段內偏移量這兩個變量是獨立的，必須顯性給出。
????????例如，8086 CPU 就使用了分段式內存管理，其程序計數器 PC 就保存在 CS 和 IP 兩個寄存器中，寫作 CS:IP。CS（Code Segment，代碼段寄存器）存儲代碼段的地址，IP（Instruction Pointer，指令指針寄存器）存儲下一條指令在代碼段中的段內偏移。這就是 “二維” 的體現。

4. 段頁式存儲管理方式

如圖 3.24 所示，段頁式存儲管理方式是分頁式存儲管理方式和段式存儲管理方式的結合。段頁式存儲管理方式先將進程空間分段，再對進程空間的每一段進行分頁，所以進程空間被劃分的最小單位仍舊是頁，這些頁分屬于進程的某一段。按此邏輯，物理內存空間也應當是要被劃分為與頁具有相同大小的內存塊，實際上也確實如此。

(1)?地址結構
????????如圖 3.25 所示，段頁式存儲方式的地址結構由高位部分的段號、中間部分的頁號和低位部分的頁內偏移量三個部分共同組成。

(2)?地址變換機構
段頁式存儲方式需要為整個進程提供一個段表，并為每一個段提供一個頁表。如圖 3.26 所示，地址變換過程如下：
(a) 用虛擬地址中的段號部分到段表中進行查詢，獲得該段號對應頁表的首地址。
(b) 通過該首地址找到相應的頁表。
(c) 用虛擬地址中的頁號部分到頁表中進行查詢，獲得該頁號所對應的內存塊號。
(d) 使用該內存塊號與虛擬地址中頁內偏移量拼接獲得對應的物理地址。

????????雖然段頁式存儲管理方式結合了分頁式存儲方式和分段式存儲方式，克服了分段式的外部碎片問題。但該方式相較于頁式存儲管理方式來說，具有更多的內存碎片，且需要段表和大量的頁表，實現復雜。所以，各種內存管理方式都有其適用的場合。

????????【提示】段頁式內存管理方式中，每個進程只有一張段表，但頁表可能不只一張。每一個段都擁有一張頁表，頁表數與段數相同。

3.1.4 習題精編

1.在以下四條與存儲管理相關的敘述中，正確的一條是（ ）。
A. 虛擬內存管理方式需要有對應的硬件支持才能實現
B. 在虛擬存儲系統中，作業的編址空間只與磁盤空間大小有關
C. 在多用戶的分時系統中，用戶平分所有的內存空間
D. 限制內存分配是內存保護的目的

1.【參考答案】?A
【解析】A 選項。虛存大小與磁盤和內存容量和以及系統的尋址空間都有關系，B 錯誤。分時系統中用戶劃分的是時間，C 錯誤。內存保護的目的是防止進程之間的互相干擾，D 選項錯誤。

2.下列對存儲管理目的的相關敘述中，完整且正確的是（ ）。
A. 增加物理內存實際容量
B. 方便用戶和提高物理內存的利用率
C. 方便用戶且增加物理內存實際容量
D. 提高物理內存的利用率

2.【參考答案】?B
【解析】存儲管理的目的是提高物理內存的利用率并且方便用戶使用，所以 B 正確。

3.在多道程序環境中，用戶程序的相對地址與裝入內存后的實際物理地址不同，把相對地址轉換為物理地址，這個功能是（ ）的。
A. 進程調度
B. 設備管理
C. 地址重定位
D. 資源管理

3.【參考答案】?C
【解析】在程序裝入時，可采用地址重定位將程序內部相對地址重定位成物理內存中的絕對地址（物理地址）。C 正確。

4.在適合多道程序運行的分區存儲管理系統中，存儲保護是為了（ ）。
A. 防止多道作業占用同一處理機
B. 防止各道作業相互干擾
C. 防止一道作業占用多個分區
D. 防止作業非法訪問磁盤文件

4.【參考答案】?B
【解析】內存保護通過界地址保護和訪問權限設置的方式，防止用戶進程對操作系統和用戶進程對其他用戶進程的干擾。所以內存保護的目的是防止進程之間的互相干擾，所以 B 正確。

5.內存管理的基本任務是提高內存的利用率，使多道程序能在不受干擾的環境中運行，這主要是通過下列哪種功能實現的（ ）。
A. 內存分配
B. 內存擴充
C. 內存保護
D. 對換

5.【參考答案】?C
【解析】內存保護通過界地址保護和訪問權限設置的方式，防止用戶進程對操作系統和用戶進程對其他用戶進程的干擾。所以內存保護的目的是防止進程之間的互相干擾，所以 C 正確。

6.采用動態重定位方式裝入作業，在執行中允許（ ）將其移走。
A. 用戶有條件地
B. 用戶無條件地
C. 操作系統有條件地
D. 操作系統無條件地

6.【參考答案】?C
【解析】動態重定位是指 CPU 訪問內存時由地址變換機構自動將相對地址轉換為絕對地址。采用動態重定位裝入方式時，進程裝入后仍保持其相對地址，訪問時再重定位轉換。并且在必要的時候可以由操作系統有條件地將裝入后的進程移走，所以 C 選項正確。

7.系統按字節編址，采用動態分區分配方式和最佳適應算法。某一時刻內存的使用情況如下圖所示（操作系統從地址 0 開始存放），此時有一 85KB 的程序需要裝入內存，則該程序分配到的分區首址為（ ）。

A. 100K
B. 190K
C. 330K
D. 410K

7.【參考答案】?B
【解析】最佳適配算法是指，每次都從可裝入該程序的最小空閑區域中，劃分出和該程序大小相等的內存空間給該程序。根據題目要求，要分配一個 85KB 大小的內存空間給該程序，其空閑分區首地址為100+80+10=190K。

8.計算機系統采用動態分區內存管理方式，某一時刻內存中存在五個空閑區域，按地址由低至高排列為：110KB、430KB、230KB、180KB 和 500KB。地址分配指針指向內存地址的起始點，接下來依次有 216KB、420KB、115KB 和 428KB 共四個進程將申請使用內存。以下算法中能夠成功分配的是（ ）。
A. 首次適應算法
B. 最佳適應算法
C. 最壞適應算法
D. 鄰近適應算法

8.【參考答案】?B
【解析】當使用首次適應算法和鄰近適應算法進行分配時，會導致 430KB 的空閑分區分配給 216KB，使得后面的 420KB 和 428KB 的進程無法分配。最壞適應算法也會優先占據大的空閑分區，導致 420KB 和 428KB 的進程無法分配，最佳適應算法能夠成功分配。

9.計算機系統按字節編址采用可變分區分配存儲管理方法，用空閑分區表管理空閑分區，分配內存采用首次適應算法，并將分區的高地址部分分配出去。內存低地址部分的 200KB 由操作系統占據，用戶區從 200K 開始，大小為 386KB，初始時為空。接下來一段時間里內存中進行了以下操作：進程 A 申請 80KB，進程 B 申請 56KB，進程 C 申請 120KB，進程 A 釋放 80KB，進程 C 釋放 120KB，進程 D 申請 156KB，進程 E 申請 81KB。問完成這些操作后內存中最小空閑塊的大小為（ ）。
A. 56KB
B. 13KB
C. 12KB
D. 89KB

9.【參考答案】?B
【解析】目前已有的空閑分區為 200K~586K，大小為 386KB，在進程 A 申請 80KB，進程 B 申請 56KB，進程 C 申請 120KB 后，此時的空閑分區為 586K~456K = 130K。此后進程 A 釋放 80KB，進程 C 釋放 120KB，此時的空閑分區為 200K~280K，336K~586K 兩個空閑分區，進程 D 申請 156KB 分配在 336K~586K 的空閑分區，滿足進程 E 申請的 81KB 的空閑分區為 492K~586K，此時最小的空閑分區為 586K~573K = 13KB。

10.某計算機系統按字節編址采用動態分區存儲管理方式，內存分配采用最佳適應算法。內存低 32MB 被操作系統占據，用戶區大小為 55MB，初始為空。接下來一段時間里內存中進行了以下操作：進程 A 分配 15MB，進程 B 分配 30MB，進程 A 釋放 15MB，進程 C 分配 8MB，進程 D 分配 6MB。問完成上述操作后內存中最大的空閑分區大小是（ ）。
A. 15MB
B. 7MB
C. 9MB
D. 10MB

10.【參考答案】?C
【解析】最佳適應算法，每次都從可裝入該程序的最小空閑區域中，劃分出和該程序大小最相近的空閑分區分配給該程序。當給進程 A 分配 15MB，進程 B 分配 30MB 后，空閑分區是 45M~55M，大小為 10MB，此時將進程 A 釋放，再為進程 C 分配 8MB，進程 D 分配 6MB。根據最佳適配算法，進程 C 分配的 8MB 為 45M~55M 的空閑分區，進程 D 分配的 6MB 為 0M~15M 的空閑分區，此時的最大空閑分區為 15MB - 6MB = 9MB。

11.系統采用動態分區方式管理內存，空閑分區使用空閑分區表記錄，問什么情況下回收一個空閑分區，反而會使得系統的空間分區數減少 1（ ）。
A. 有下鄰空閑區但無上鄰空閑區
B. 有上鄰空閑區也有下鄰空閑區
C. 無上鄰空閑區也無下鄰空閑區
D. 有上鄰空閑區但無下鄰空閑區

11.【參考答案】?B
【解析】有上鄰空閑區也有下鄰空閑區時，這三個分區會合成一個分區，所以最終總分區數減一。選項 B 正確。

12.在固定分區分配的方法中，每個分區的大小（ ）。
A. 相同
B. 隨作業長度變化
C. 可以不同但預先固定
D. 可以不同但根據作業長度固定

12.【參考答案】?C
【解析】固定分區分配方法在初始化時就劃分好分區，該方法的分區方式包括等分區和不等分區，所以選擇 C。

13.在請求頁面式管理中，缺頁中斷率與以下哪種（ ）因素有關。
A. 頁表的位置
B. 置換算法
C. 外存管理算法
D. 進程調度算法

13.【參考答案】?B
【解析】選擇調出頁面的算法稱為頁面置換算法。好的頁面置換算法會有較低的頁面缺失率（缺頁中斷率）。頁表的位置，外存管理算法，進程調度算法與缺頁中斷率無關。

14.采用動態分區算法回收內存時，如果回收分區僅與空閑分區鏈插入點的前一個分區相鄰接，那么需要在空閑分區表中（ ）。
A. 增加一個新表項
B. 修改前一個分區表項的大小
C. 修改前一個分區表項的起始地址
D. 修改前一個分區表項的大小和起始地址

14.【參考答案】?B
【解析】當即將回收的空閑分區與前一個空閑分區相鄰時，只需要在空閑分區表中，修改前一個空閑分區表項的大小即可。

15.在動態分區存儲系統中，空閑表的內容如下：

????????此時，進程 P 請求 50KB 內存，系統從第一個空閑塊開始查找，結果把第 4 個空閑塊分配給了進程 P。請問系統采用的分區分配算法是（ ）。
A. 首次適應法
B. 最佳適應法
C. 最差適應法
D. 循環首次適應法

15.【參考答案】?C
【解析】從第一個空閑塊優先查找。若使用首次適應算法，小地址空閑塊優先分配，則會把空閑塊 1 分配給進程 P，A 錯誤。若使用最佳適應算法，最小塊優先分配，則會把空閑塊 3 分配給進程 P，B 錯誤。若使用最差適應算法，最大塊優先分配，則會把空閑塊 4 分配給進程 P，C 正確。若使用循環首次適應法，當前地址優先分配，則也會把空閑塊 1 分配給進程 P，D 錯誤。

16.某系統采用固定分區分配存儲管理，內存空間為 430K，其中地址 0 到 30K 被系統占用，其他空間按分區大小相等的方法劃為 4 個分區，則當有大小分別為 7KB、90KB、30KB、20KB 的作業進入內存時，浪費的內存為（ ）。
A. 53KB
B. 200KB
C. 253KB
D. 280KB

16.【參考答案】?C
【解析】系統占據了 30KB 的內存空間，將余下的 400KB 等分成 4 個分區，每個分區大小為 100KB，在固定分區分配管理中，每個分區只裝入一道作業，浪費的內存大小為(100?7)+(100?90)+(100?30)+(100?20)=253KB，選項 C 正確。

17.以下對分頁存儲管理方式的描述中，正確的是（ ）。
I. 在不使用快表（TLB）的分頁存儲管理方式中（不考慮多級頁表），CPU 每次取指令都需要訪問兩次內存
II. 分頁存儲管理方式不會產生外部碎片，但會產生內部碎片
III. 分頁存儲管理方式對用戶是不透明的
IV. 分頁存儲管理方式不能采用靜態重定位
A. I、II、IV
B. I、IV
C. 僅 I
D. 全都正確

17.【參考答案】?A
【解析】分頁存儲管理方式對用戶透明，分段存儲管理方式對用戶不透明，所以 III 錯誤。不使用快表時，CPU 取指令需要先訪問一次內存中的頁表獲得物理地址，之后再訪問一次內存存取相應指令，I 正確。分頁存儲管理方式不存在外部碎片，但在進程最后一頁會存在內部碎片，II 正確。分頁存儲管理方式下，進程裝入內存后可能會改變位置，不能采用靜態重定位，IV 正確。

18.可以采用靜態重定位的內存管理方式有（ ）。
I. 固定分區
II. 可變分區
III. 頁式
IV. 段式
A. I、II、IV
B. I、IV
C. 僅 I
D. 全部

18.【參考答案】?C
【解析】固定分區方式中，程序裝入后位置不再改變，可以采用靜態重定位。其余三種方式均可能在運行過程中改變程序位置，不能采用靜態重定位。所以只有 I 可以，選擇 C 選項。

19.以下內存管理方式中，最適合采用動態鏈接的是（ ）。
A. 單一連續分配管理方式
B. 分段存儲管理方式
C. 固定分區管理方式
D. 分頁存儲管理方式

19.【參考答案】?B
【解析】分段存儲管理方式中每個段都是一個獨立的邏輯單位，程序中完成某一功能的代碼不會被分割在不同段中，方便需要時動態鏈接。選 B 選項。

20.下面關于內存保護的描述不正確的是（ ）。
A. 一個進程不能未被授權就訪問另外一個進程的內存單元
B. 內存保護可以僅通過操作系統（軟件）來滿足，不需要處理器（硬件）的支持
C. 內存保護的方法有界地址保護和存儲鍵保護
D. 一個進程中的程序不能跳轉到另一個進程的指令地址中

20.【參考答案】?B
【解析】內存保護需要上下限寄存器或界地址寄存器和重定位寄存器的支持，需要硬件。所以 B 選項錯誤，A、C、D 均正確。

21.不會產生內部碎片的存儲管理系統是（ ）。
A. 分頁式存儲管理
B. 固定分區式存儲管理
C. 可變式存儲管理
D. 段頁式存儲管理

21.【參考答案】?C
【解析】可變式分區管理方式中，進程需要多大的空間就劃分出多大的內存分區給進程，所以不存在內部碎片。其他三種方式都存在內部碎片。選擇 C 選項。

22.頁式存儲管理方式、段式存儲管理方式和段頁式存儲管理方式這三者的虛擬地址空間維度依次是（ ）。
A. 一維、一維、二維
B. 一維、二維、二維
C. 一維、二維、一維
D. 二維、一維、一維

22.【參考答案】?B
【解析】頁式存儲管理方式中頁大小相同，頁號和頁內偏移量可直接通過邏輯地址計算得出，地址空間是一維的。而分段式和段頁式中的段號和段內地址都要顯式給出，地址空間是二維的。

23.系統按字節編址，采用分頁式存儲管理方式管理內存。在該系統中邏輯地址空間大小 256TB，頁表項大小 8B，頁面大小 4KB。請問系統頁表組織需要使用（ ）級頁表。
A. 2
B. 3
C. 4
D. 5

23.【參考答案】?C
【解析】一個頁面中能裝入的頁表項數N=4KB/8B=512=29。邏輯地址空間頁面數M=256TB/4KB=236個。最外層頁表只能占一頁，所以需要?36/9?=4級頁表。C 正確。

24.以下對分頁存儲管理方式中頁面大小的說法中正確的是（ ）。
I. 選擇較大的頁面可以降低頁表的大小，提高有效數據存儲密度
II. 選擇較小的頁面可以減少內部碎片，從而更充分地利用內存空間
III. 選擇較大的頁面可以減小頁表，并減少內部碎片，所以頁面越大越好
A. I、II
B. I、II、III
C. I
D. II、III

24.【參考答案】?A
【解析】進程最后一頁中會產生平均半頁的內部碎片，選擇較小的頁面時，可以減小這一內部碎片浪費。選擇較大的頁面可以降低頁表的大小，提高有效數據存儲密度。但頁面太大會增加內部碎片，造成內存空間的浪費。所以應當選擇大小均衡的頁面大小，而不是越大越好。所以 I、II 正確，III 錯誤。

25.在下列內存管理方式中，會產生內部碎片的有（ ）。
I. 分段存儲管理
II. 動態分區存儲管理
III. 請求分頁存儲管理
IV. 段頁式存儲管理
A. I、II
B. I、II、III
C. 僅 I
D. III、IV

25.【參考答案】?D
【解析】分頁存儲管理方式中，進程的最后一頁可能出現內部碎片。段頁式存儲管理方式中，段內的最后一頁可能出現內部碎片。其他兩種方式不存在內部碎片，所以選擇 D。

26.某具有請求調入和頁面置換功能的存儲器中，CPU 給出邏輯地址到其被轉換為物理地址的這一段過程中，不會出現以下哪一種情況（ ）。
A. 缺頁
B. 訪問權限錯誤
C. 地址越界
D. 內存溢出

26.【參考答案】?D
【解析】地址變換時若內存中無需要訪問的頁則造成缺頁。當頁（段）號大于頁（段）表長度，會造成越界。當指令執行的操作與頁面權限不符則會產生訪問權限錯誤。所以 A、B、C 都有可能發生。而內存溢出是不會發生的，所以選擇 D。

27.下列措施中，能加快虛實地址轉換的是（ ）。
I. 增大快表（TLB）
II. 讓頁表常駐內存
III. 增大交換區
A. 僅 I
B. 僅 II
C. 僅 I、II
D. 僅 II、III

27.【參考答案】?C
【解析】增大快表可以提高快表命中率，從而減少訪存次數，所以 I 正確。頁表常駐內存可以提高查詢頁表的速度，從而加速轉換，所以 II 正確。增大交換區是內存不夠用時的手段，與加速地址轉換無關。所以 III 錯誤。

28.系統按字節編址，采用分頁式存儲管理方式管理內存，邏輯地址結構如下圖所示。假設邏輯地址空間大小為2^26B，頁面大小為2^10B，頁表項大小為 2B。問該系統的頁目錄表中至少需要包含多少個頁表項（ ）。

A. 32
B. 128
C. 64
D. 256

28.【參考答案】?B
【解析】本題采用兩級頁表，一個頁面可放置頁表項數N=210/2=29，邏輯地址空間頁數M=226/210=216。所以頁表大小為216/29=27頁。因此頁目錄表中應有27=128個表項。

29.系統按字節編址，采用請求分頁存儲方式管理內存，系統的邏輯地址空間大小為2^48B，頁面大小為2^13B，頁表項大小為 8B，則該系統頁表的級數應當是（ ）。
A. 5
B. 3
C. 4
D. 2

29.【參考答案】?C
【解析】一個頁面中能裝入的頁表項數N=213B/8B=210。邏輯地址空間頁面數M=248B/213B=235個。最外層頁表只能占一頁，所以需要?35/10?=4級頁表。C 正確。

30.采用分段存儲管理的系統，若地址用 24 位表示，其中 8 位表示段號，則允許每段的最大長度是（ ）。
A.?2^16
B.?2^24
C.?2^28
D.?2^32

30.【參考答案】?A
【解析】段內偏移量所占位數 = 地址位數 - 段號位數=24?8=16。所以最大段長為216。

31.關于分段系統與分頁系統的區別，描述不正確的是（ ）。
A. 頁幀是信息的物理單位，段是信息的邏輯單位
B. 頁和段的大小都是固定的
C. 分頁對用戶是透明的，分段對用戶是可見的
D. 分段存儲管理容易實現內存共享，分頁存儲管理較難實現內存共享

31.【參考答案】?B
【解析】頁的大小是預先固定的，并且每一頁大小相同，但段的大小是不定劃分的，每個段的大小也不一定相同，B 錯誤。頁幀是物理內存上的單位，是信息的物理單位，段是信息邏輯獨立單位。分頁由操作系統完成，分段需要編程人員劃分，所以分頁透明，分段不透明。由于段是獨立邏輯單位，所以分段有利于共享，但分頁中頁不是。所以 A、C、D 錯誤。

32.某系統使用 32 位邏輯地址，頁大小為 4Kbytes，以及 36 位物理地址。那么該系統中的頁表大小為（ ）。
A.?2^20個頁表項
B.?2^24個頁表項
C.?2^4個頁表項
D.?2^12個頁表項

32.【參考答案】?A
【解析】邏輯地址空間大小為2^32B，頁大小為4KB=2^12B，所以共有2^32B/2^12B=2^20頁，因此頁表有2^20個頁表項。

33.一個進程的頁表如下表所示，頁的大小為 1024B。指令 MOV AX,[2586] 中地址 2586（十進制）對應的物理地址是（ ）。

A. 2586
B. 10240
C. 10778
D. 31258

33.【參考答案】?C
【解析】頁號=?2586/1024?=2，頁內偏移量=2586%1024=538。2 號頁面對應 10 號物理塊，該物理塊起始地址為10×1024=10240，所以物理地址為10240+538=10778，選 C。

34.在分頁式存儲方式中，頁面這一概念是（ ）。
A. 對鏈接程序不透明，對操作系統透明
B. 對編譯系統不透明，對操作系統透明
C. 對用戶透明，對操作系統不透明
D. 對鏈接程序透明，對用戶透明

34.【參考答案】?C
【解析】分頁存儲管理方式對操作系統不透明，對運行在操作系統之上的程序及工作在其上的編程人員透明。

35.在分頁式存儲管理方式的計算機系統中，用于組織頁面的頁表的起始地址一般存放在（ ）。
A. 快表（TLB）
B. 頁表寄存器（PTR）
C. 物理內存
D. 虛擬內存

35.【參考答案】?B
【解析】分頁存儲管理方式中每個進程的頁表起始地址存放在各自的 PCB 中，當進程上處理機時，將頁表起始地址調入 PTR。

36.對于采用分段式存儲管理方式的計算機系統來說，以下相關描述中正確的是（ ）。
A. 程序分段對裝入程序是可見的，程序如何分段在裝入時決定
B. 程序分段對用戶是可見的，程序如何分段在用戶編程時決定
C. 程序分段對操作系統是可見的，程序如何分段在分配內存時決定
D. 程序分段對操作系統是可見的，程序如何分段在程序運行時決定

36.【參考答案】?B
【解析】程序分段對用戶和操作系統都可見，但其分段多在用戶編程時決定。

37.在采用分段式存儲管理方式的計算機系統中，從 CPU 給出邏輯地址到取得內存中相應的數據，這一過程中總共需要進行（ ）次內存訪問。
A. 1
B. 2
C. 3
D. 4

37.【參考答案】?B
【解析】分段需要一次訪問內存查詢段表，獲得物理地址后再訪問一次內存獲取數據。共兩次。選擇選項 B。

38.在采用段頁式存儲管理方式的計算機系統中，從 CPU 給出邏輯地址到取得內存中相應的數據，這一過程中總共需要進行（ ）次內存訪問。
A. 1
B. 2
C. 3
D. 4

38.【參考答案】?C
【解析】段頁式需要一次內存訪問來查詢段表，獲得該段頁表起始地址，隨后訪問內存查詢該頁表。獲得物理地址后，訪問內存獲取數據。共三次。

39.以下對分頁式存儲管理方式的敘述中正確的是（ ）。
A. 計算機系統中只有一張頁表，頁表起始地址存放在寄存器中
B. 計算機系統中只有一張頁表，頁表起始地址存放在進程 PCB 中
C. 計算機系統為每一個進程都創建一張頁表，每個進程都有專屬寄存器存放頁表起始地址
D. 計算機系統為每一個進程都創建一張頁表，頁表起始地址存放在各自進程的 PCB 中，運行時被寫入寄存器

39.【參考答案】?D
【解析】分頁存儲管理方式中每個進程的頁表起始地址存放在各自的 PCB 中，當進程上處理機時，將頁表起始地址調入 PTR。選 D。

40.某虛擬存儲器的邏輯地址空間大小為 512 頁，頁大小為 4KB，且該存儲器的物理地址空間大小為 64 頁。則邏輯地址和物理地址分別是多少位（ ）。
A. 9,18
B. 9,6
C. 21,6
D. 21,18

40.【參考答案】?D
【解析】頁內偏移量位數=log2?4K=12，頁號位數=log2?512=9，頁框號位數=log2?64=6。所以邏輯地址位數=9+12=21，物理地址位數=6+12=18。

41.某系統采用分頁式存儲管理方式，以下關于該系統的說法中正確的有（ ）。
I. 分頁存儲系統不會產生外部碎片，但是會產生內部碎片
II. 若該計算機系統不使用快表（TLB），且頁表只有一級，則進程訪問內存數據時，需要進行至少兩次內存訪問
III. 分頁存儲管理系統可以采用靜態重定位方式
IV. 分頁存儲管理系統中的頁面概念對用戶是透明的
A. I、II
B. II、III
C. 全部
D. I、II、IV

41.【參考答案】?D
【解析】分頁存儲管理方式下，進程裝入內存后可能會改變位置，不能采用靜態重定位，所以 III 錯誤。I、IV 正確。分頁存儲不用 TLB 時至少需要一次訪存查頁表，和一次訪存取數據，所以 II 正確。

42.計算機系統按字節編址，采取分頁存儲管理方式管理內存。虛擬地址 64 位，頁面大小為 4KB，頁表的頁表項大小為 4B。據此可以計算出該系統需要將頁表組織成（ ）級。
A. 4
B. 5
C. 6
D. 7

42.【參考答案】?C
【解析】頁面數=264B/4KB=252，一頁可存放的頁表項數=4KB/4B=210。所以應組織成?52/10?=6級。

43.在分頁存儲管理系統中，頁表內容如下表所示 (均從 0 開始編號)。若頁面大小為 4KB，則地址轉換機構將邏輯地址 0 轉換成物理地址（ ）。

A. 8192
B. 4096
C. 2048
D. 1024

43.【參考答案】?A
【解析】頁面大小4KB=4096B，邏輯地址 0 對應頁號 0，查表知該頁存放在 2 號物理塊。2 號物理塊的起始地址為4096×2=8192，頁內偏移量為 0。故物理地址為 8192 。

44.在內存管理中，內存利用率高且保護和共享容易的是（ ）方式。
A. 分區存儲管理
B. 分頁存儲管理
C. 分段存儲管理
D. 段頁式存儲管理

44.【參考答案】?D
【解析】分頁存儲有效解決了外部碎片問題，內存利用率高。分段存儲系統的段具有獨立邏輯單位性，易于共享和保護，但存在外部碎片。段頁存儲系統結合了分頁和分段的優點，不存在外部碎片，內存利用率高，且易于共享和保護。

45.下列關于分頁和分段的描述，正確的是（ ）。
A. 分段是信息的邏輯單位，段長由系統決定
B. 分段引入的主要目的是實現分散分配并提高主存利用率
C. 分頁是信息的物理單位，頁長由用戶決定
D. 分頁系統中，頁面在物理內存中只能從頁面大小的整數倍地址開始存放

45.【參考答案】?D
【解析】段式管理系統按照用戶的設定去劃分邏輯地址空間，段長由用戶決定，選項 A 錯誤。分頁是信息的物理單位，頁長由系統決定且大小固定，選項 C 錯誤。分頁的主要目的是為了實現離散分配，提高內存利用率，選項 B 錯誤。在頁式存儲管理中，將虛擬內存空間和物理內存空間劃分為大小相同的頁面，因此，頁面在物理內存中只能從頁面大小的整數倍地址開始存放，選項 D 正確。

46.在采用分頁存儲管理的系統中，地址結構長度為 18 位，其中 11 至 17 位表示頁號，0 至 10 位表示頁內偏移量，則主存容量最大可為（ ）KB，主存可分為（ ）個塊。若有一作業依次被放入 2、3、7 號物理塊，相對地址 1500 處有一條指令 “store 1,12500”，那么，該指令地址所在頁的頁號為 0，指令的物理地址為（ ），該指令數據的存儲地址所在頁的頁號為（ ）。
A. 256、256、5596、7
B. 256、128、500、7
C. 256、128、5596、6
D. 256、128、5500、6

46.【參考答案】?C
【解析】由題意可知，共有 7 位來表示頁號，因此共有27個頁面，頁面大小為211B（2KB），主存最大容量為27×2KB=256KB，在分頁存儲管理系統中，內存塊數 = 頁面數=27。由于該指令所在頁的頁號為 0，其分配的物理塊號為 2，采用的是相對地址，所以該指令的物理地址 = 基地址 + 相對地址=2×2KB+1500=5596。該指令數據的存儲地址為 12500，其所在頁的頁號為12500/2KB=6，選項 C 正確。

47.某計算機按字節編址，并從 0 開始進行編號，采用動態分區管理的方式來管理空閑區，采用空閑分區表來記錄空閑區。其主存中的用戶區大小為 60MB（初始為空），分配時優先分配到空閑區的小地址部分。分配和釋放的操作序列為：分配 20MB，分配 12MB，分配 4MB，分配 15MB，釋放 12MB，分配 8MB，釋放 15MB，分配 6MB。已知空閑分區表的表項為 <分區始址，分區大小>，則當執行完操作后：
(1) 若采用的是首次適應（First Fit）算法，請畫出此時的空閑分區表？
(2) 若采用的是最佳適應（Best Fit）算法，請畫出此時的空閑分區表？

47.【參考答案】
(1) 由題知，分配時優先分配到空閑分區的小地址部分，采用首次適應算法，會將符合分區大小的低地址部分分配出去，見表 3.6。
| 分區起始地址 | 分區大小 |
| ---- | ---- |
|28M|4MB|
|42M|18MB|

表 3.6 首次適應算法

(2) 由題知，采用最佳適應算法時，會將空閑分區按大小進行排序，在進行分配時，查找已排好序的空閑分區鏈，找到第一個能滿足大小的空閑分區，見表 3.7。

分區起始地址	分區大小
59M	1MB
26M	6MB
36M	15MB

表 3.7 最佳適應算法

48.計算機系統按字節編址，存儲器采用分頁式存儲管理方式，內存被劃分為 64B 大小的內存塊，進程 A 的大小為 702B。進程頁表如下表 (a) 所示，進程快表如下表 (b) 所示。請分別說明系統遇到八進制邏輯地址 0205,0645,0723,02311 時的處理過程。

48.【參考答案】
注意該邏輯地址為八進制邏輯地址。
當訪問 0205 時，對應的二進制地址為：00 1000 0101B，由于內存塊大小 64B，故低 6 位為塊內地址，其頁號為 2，訪問快表得到其塊號為 F3，將塊號和頁內地址合成，訪問其物理地址。
訪問 0645 時，對應的二進制地址為：01 1010 0101B，其頁號為 6，訪問快表缺失，訪問頁表得到其塊號為 FA，將塊號和頁內地址合成，訪問其物理地址。
訪問 0723 時，對應的二進制地址為：01 1101 0011B，其頁號為 7，訪問快表缺失，訪問頁表得到其塊號為 FB，將塊號和頁內地址合成，訪問其物理地址。
訪問 02311 時，地址越界。

49.在一個分頁存儲管理系統中，地址空間分頁 (每頁 1KB)，物理空間分塊，設主存總容量是 256KB，描述主存分配情況的位示圖如圖 3.27 所示 (0 表示未分配，1 表示已分配) 此時作業調度程序選中一個長為 5.2KB 的作業投入內存。試問：
(1) 為該作業分配內存后 (分配內存時，先分配低地址的內存空間)，填寫該作業的頁表內容。
(2) 頁式存儲管理有無內存碎片存在？若有，會存在哪種內存碎片？為該作業分配內存后，會產生內存碎片嗎？如果產生，那么大小為多少？
(3) 假設一個 64MB 內存容量的計算機，采用頁式存儲管理 (頁面大小為 4KB)，內存分配采用位示圖方式管理，請問位示圖將占用多大的內存？

49.【參考答案】
(1) 頁面大小為 1KB，由題意可知，作業大小為 5.2KB，管理系統為該作業分配 6 個頁面。根據位示圖可得，前 6 個空閑塊號為 21、27、28、29、34、35。
(2) 頁式存儲管理會存在內部碎片。因為該作業的大小為 5.2KB，需要為其分配 6 個頁面，最后一個頁面會產生0.8KB的內部碎片。
(3) 64MB 內存，頁面大小為 4KB，共有214個頁面，位示圖通過 1bit 表示 1 個頁面，共需要214個 bit，也就是214/8=2KB大小的內存來表示位示圖。

3.1.5 真題演練

50.【2009】分區分配內存管理方式的主要保護措施是（ ）。
A. 界地址保護
B. 程序代碼保護
C. 數據保護
D. 棧保護

50.【參考答案】?A
【解析】分區分配內存管理方式的主要保護措施是界地址保護。為保證進程之間互不干擾，每個進程擁有自己獨立的內存空間，其他進程不可以隨意訪問。通過設置界地址寄存器來檢測進程訪問是否越界。

51.【2011】在虛擬內存管理中，地址變換機構將邏輯地址變換為物理地址，形成該邏輯地址的階段是（ ）。
A. 編輯
B. 編譯
C. 鏈接
D. 裝載

51.【參考答案】?C
【解析】在虛擬內存管理中，地址變換機構將邏輯地址變換為物理地址，形成該邏輯地址的階段是鏈接。

52.【2010】某基于動態分區存儲管理的計算機，其主存容量為 55MB (初始為空)，采用最佳適配 (Best Fit) 算法，分配和釋放的順序為：分配 15MB，分配 30MB，釋放 15MB，分配 8MB，分配 6MB，此時主存中最大空閑分區的大小是（ ）。
A. 7MB
B. 9MB
C. 10MB
D. 15MB

52.【參考答案】?B
【解析】最佳適配算法是指，每次都從可裝入該程序的最小空閑區域中，劃分出和該程序大小相等的內存空間給該程序。經過題述的分配釋放過程后，此時有開頭15?6=9MB和末尾 2MB 兩個空閑區域。所以答案選 B。過程如下圖所示。
| 開始 | 55MB|
| ---- | ---- |
| 分配 15MB|15MB、40MB|
| 分配 30MB|15MB、30MB、10MB|
| 釋放 15MB|15MB、30MB、10MB*|
| 分配 8MB|15MB*、30MB、8MB、2MB|
| 分配 6MB|6MB、9MB、30MB、8MB、2MB|

53.【2017】某計算機按字節編址，其動態分區內存管理采用最佳適應算法，每次分配和回收內存后都對空閑分區鏈重新排序。當前空閑分區信息如下表所示。

回收起始地址為 60K、大小為 140KB 的分區后，系統中空閑分區的數量、空閑分區鏈第一個分區的起始地址和大小分別是（ ）。
A. 3、20K、380KB
B. 3、500K、80KB
C. 4、20K、180KB
D. 4、500K、80KB

53.【參考答案】?B
【解析】回收分區的起始地址是 60K 與起始地址為 20K 的分區相鄰，回收分區的尾部地址是60+140=200K與起始地址為 200K 的分區相鄰。所以應當將這三個分區合并成一個起始地址為 20K，大小為 380KB 的空閑分區。所以系統中此時存在三個空閑分區。
題目說明了，每次回收內存后都對空閑分區鏈重新排序。根據題目給出的空閑分區信息可以看出，空閑分區鏈是按照分區大小升序排序的。所以第一個即是最小的分區，該分區的起始地址為 500K 大小為 80KB。

54.【2019】在下列動態分區分配算法中，最容易產生內存碎片的是（ ）。
A. 首次適應算法
B. 最壞適應算法
C. 最佳適應算法
D. 循環首次適應算法

54.【參考答案】?C
【解析】最佳適應算法總是從符合裝入程序大小的空閑區域中選擇最小的分配出去，最為容易產生外部碎片。

55.【2009】一個分段存儲管理系統中，地址長度為 32 位，其中段號占 8 位，則最大段長是（ ）。
A.?2^8字節
B.?2^16字節
C.?2^24字節
D.?2^32字節

55.【參考答案】?C
【解析】邏輯地址共 32 位，去掉 8 位段號，剩下 24 位表示段內地址，最多表示224字節，這同時也就是最大段長。

56.【2010】某計算機采用二級頁表的分頁存儲管理方式，按字節編址，頁大小為210字節，頁表項大小為 2 字節，邏輯地址結構如下圖所示。邏輯地址空間大小為216頁，則表示邏輯地址空間的頁目錄表中表項的個數至少是（ ）。

A. 64
B. 128
C. 256
D. 512

56.【參考答案】?B
【解析】一頁可以放210/2=29個頁表項，而邏輯地址空間大小為216頁。頁表最多可占216/29=27頁。因此頁目錄表至少要能存27=128個表項，這樣才能保證一定能記錄所有頁表。

57.【2014】下列選項中，屬于多級頁表優點的是（ ）。
A. 加快地址變換速度
B. 減少缺頁中斷次數
C. 減少頁表項所占字節數
D. 減少頁表所占的連續內存空間

57.【參考答案】?D
【解析】多級頁表需要對各級頁表分別進行一次查詢，降低了地址變換速度。頁面的缺頁與內存容量、內存進程數以及置換算法相關，而多級頁表并不能影響頁面的缺頁，且若多級頁表未被調入內存，反而會增加缺頁次數。頁表項字段數量和各字段大小都與多級頁表不相關，所以減小頁表項大小不是多級頁表的優點。多級頁表中，外層頁表索引內層頁表，從而令內層頁表可以不連續存放，所以減少了頁表所占的連續空間。

58.【2016】某進程的段表內容如下表所示。當訪問段號為 2、段內地址為 400 的邏輯地址時，進行地址轉換的結果是（ ）。

A. 段缺失異常
B. 得到內存地址 4400
C. 越權異常
D. 越界異常

58.【參考答案】?D
【解析】段號為 2，所以查詢到段表的第 3 行（編號由 0 開始）。比較段內地址和段長，發現段內地址 > 段長，所以產生了越界異常。

59.【2019】在分段存儲管理系統中，用共享段表描述所有被共享的段。若進程P1?和P2?共享段S，下列敘述中，錯誤的是（ ）。
A. 在物理內存中僅保存一份段S的內容
B. 段S在P1?和P2?中應該具有相同的段號
C.?P1?和P2?共享段S在共享段表中的段表項
D.?P1?和P2?都不再使用段S時才回收段S所占的內存空間

59.【參考答案】?B
【解析】段共享時，內存中只保留一份段 S 的內容，共享段表中記錄該段的物理地址和共享該段的進程數等相關信息。共享進程P1?和P2?的段表中各有一個表項指向該物理內存位置。二者各自對應的段表項所指向的物理空間位置相同，但邏輯地址不一定相同，即段號是不一定相同的。所以 B 選項錯誤，A、C 選項正確。被共享的段，在共享段表中記錄的共享該段的進程數為 0 時才回收該段的內存空間。D 選項正確。

60.【2019】某計算機主存按字節編址，采用二級分頁存儲管理，地址結構如下圖所示。虛擬地址 20501225H 對應的頁目錄號、頁號分別是（ ）。

A. 081H、101H
B. 081H、401H
C. 201H、101H
D. 201H、401H

60.【參考答案】?A
【解析】將虛擬地址轉換為 2 進制形式：0010 0000 0101 0000 0001 0010 0010 0101。取出前十位轉回 16 進制即是頁目錄號：00 1000 0001 = 081H。取出中間對應頁號的十位轉回 16 進制即是頁號：01 0000 0001 = 101H。

61.【2021】在采用二級頁表的分頁系統中，CPU 頁表基址寄存器中的內容是（ ）。
A. 當前進程的一級頁表的起始虛擬地址
B. 當前進程的一級頁表的起始物理地址
C. 當前進程的二級頁表的起始虛擬地址
D. 當前進程的二級頁表的起始物理地址

61.【參考答案】?B
【解析】頁表寄存器應當存放多級頁表中最外層頁表的起始物理地址。這里 408 中的命名是將最外層稱為一級頁表，所以應當選擇 B。

【2013】某計算機主存按字節編址，邏輯地址和物理地址都是 32 位，頁表項大小為 4 字節。請回答下列問題：
(1) 若使用一級頁表的分頁存儲管理方式，邏輯地址結構如下：

則頁的大小是多少字節？頁表最大占用多少字節？
(2) 若使用二級頁表的分頁存儲管理方式，邏輯地址結構如下：

設邏輯地址為 LA，請分別給出其對應的頁目錄號和頁表索引的表達式。
(3) 采用 (1) 中的分頁存儲管理方式，一個代碼段起始邏輯地址為 0000 8000H，其長度為 8KB，被裝載到從物理地址 0090 0000H 開始的連續主存空間中。頁表從主存 0020 0000H 開始的物理地址處連續存放，如下圖所示 (地址大小自下向上遞增)。請計算出該代碼段對應的兩個頁表項的物理地址、這兩個頁表項中的頁框號以及代碼頁面 2 的起始物理地址。

62.【參考答案】

頁內偏移量占 12 位，按字節編址，所以頁大小為212B=4KB。頁號占 20 位，所以最多有220頁，意味著需要220個頁表項，每個頁表項 4B，所以頁表最多占220×4B=4MB。

頁目錄號：((unsigned int) LA)/4M，頁表索引號：((unsigned int) LA>>12)%1K。

由題目給的圖可知，頁框號 1 對應的這個頁表項的頁面被裝入到 0090 0000H (頁框號：00900H)，所以該頁為題目所述邏輯地址為 0000 8000H 的頁面。0000 8000H 的頁號為高 20 位，即 0 0008H = 8 頁。所以此頁面對應表項為頁表的第 8 項，可計算出物理地址 1 為 0020 0000H + 8×4 = 0020 0020H。
頁框號 2 在頁框號 1 的下一頁，故頁框號 2 為 00900H + 1H = 00901H。
物理地址 2 與物理地址 1 相差一個表項，所以物理地址 2 為 0020 0020H + 4 = 0020 0024H。
代碼頁面 1 與代碼頁面 2 相差一個頁面，所以物理地址 3 為 0090 0000H + 4K = 0090 1000H。