26考研——內存管理_內存管理策略（3）

408答疑

文章目錄

一、內存管理策略
- 1、內存管理的基本原理和要求
- - 1.1、相關概念
  - 1.2、邏輯地址與物理地址
  - 1.3、程序的鏈接與裝入
  - 1.4、進程的內存映像
  - 1.5、內存保護
  - 1.6、內存共享
  - 1.7、內存分配與回收
  - 1.8、在存儲管理中涉及到兩個問題
- 2、連續分配管理方式
- - 2.1、相關概念
  - 2.2、單一連續分配
  - 2.3、固定分區分配
  - 2.4、動態分區分配
  - - 2.4.1、基于順序搜索的分配算法
    - 2.4.2、基于索引搜索的分配算法
- 3、非連續分配管理方式
- - 3.1、基本分頁存儲管理
  - - 3.1.1、分頁思想的由來
    - 3.1.2、分頁存儲的幾個基本概念
    - 3.1.3、基本地址變換機構
    - 3.1.4、具有快表的地址變換機構
    - 3.1.5、兩級頁表
  - 3.2、基本分段存儲管理
  - - 3.2.1、分段
    - 3.2.2、段表
    - 3.2.3、地址變換機構
    - 3.2.4、分頁和分段的對比
    - 3.2.5、段的共享與保護
  - 3.3、段頁式存儲管理
三、參考資料
- 鮑魚科技課件
- 26王道考研書

一、內存管理策略

在這里插入圖片描述

1、內存管理的基本原理和要求

1.1、相關概念

內存管理（Memory Management）是操作系統設計中最重要和最復雜的內容之一。
雖然計算機硬件技術一直在飛速發展，內存容量也在不斷增大，但仍然不可能將所有用戶進程和系統所需要的全部程序與數據放入主存，因此操作系統必須對內存空間進行合理的劃分和有效的動態分配。
操作系統對內存的劃分和動態分配，就是內存管理的概念。
有效的內存管理在多道程序設計中非常重要，它不僅可以方便用戶使用存儲器、提高內存利用率，還可以通過虛擬技術從邏輯上擴充存儲器。
內存管理的主要功能有：
- 內存空間的分配與回收。由操作系統負責內存空間的分配和管理，記錄內存的空閑空間、內存的分配情況，并回收已結束進程所占用的內存空間。
- 地址轉換。程序的邏輯地址與內存中的物理地址不可能一致，因此存儲管理必須提供地址變換功能，將邏輯地址轉換成相應的物理地址。
- 內存空間的擴充。利用虛擬存儲技術從邏輯上擴充內存。
- 內存共享。指允許多個進程訪問內存的同一部分。例如，多個合作進程可能需要訪問同一塊數據，因此必須支持對內存共享區域進行受控訪問。
- 存儲保護。保證各個進程在各自的存儲空間內運行，互不干擾。

在進行具體的內存管理之前，需要了解進程運行的基本原理和要求。

1.2、邏輯地址與物理地址

進程虛擬地址空間的特點：
- 編譯后，每個目標模塊都從 0 號單元開始編址，這稱為該目標模塊的相對地址（或邏輯地址）。當鏈接程序將各個模塊鏈接成一個完整的可執行目標程序時，鏈接程序順序依次按各個模塊的相對地址，構成統一的從 0 號單元開始編址的邏輯地址空間（或虛擬地址空間）。對于 32 位系統，邏輯地址空間的范圍為 $\sim 2^{32}-1$ 。進程在運行時，看到和使用的地址都是邏輯地址。用戶程序和程序員只需知道邏輯地址，而內存管理的具體機制（如頁表查詢、地址重定位、權限檢查等）對上層完全透明。不同進程可以有相同的邏輯地址，因為這些相同的邏輯地址會通過頁表映射到主存的不同物理位置，實現進程間的地址空間隔離。
- 物理地址空間是指內存中物理單元的集合，它是地址轉換的最終地址，進程在運行時執行指令和訪問數據，最后都要通過物理地址從主存中存取。當裝入程序將可執行代碼裝入內存時，必須通過地址轉換將邏輯地址轉換成物理地址，這個過程稱為地址重定位。
- 操作系統通過內存管理部件（MMU）將進程使用的邏輯地址轉換為物理地址。進程使用虛擬內存空間中的地址，操作系統在相關硬件的協助下，將它“轉換”成真正的物理地址。邏輯地址通過頁表映射到物理內存，頁表由操作系統維護并被處理器引用。
如下圖右側所示，邏輯上，我們可以把物理內存看成一個大數組，其中每個字節都可以通過與之唯一對應的地址進行訪問，這個地址就是物理地址（physical address）。在應用程序或操作系統運行過程中，CPU 通過總線發送訪問物理地址的請求，從內存中讀取數據或者向其中寫入數據。
- 在引入虛擬內存的抽象后，應用程序使用虛擬地址（virtual address）訪問存儲在內存中的數據和代碼。在程序執行過程中，CPU 會把虛擬地址轉換成物理地址，然后通過后者訪問物理內存。虛擬地址轉換成物理地址的過程，通常被稱為地址翻譯。
- CPU 中的重要部件，內存管理單元（Memory Management Unit，MMU），負責虛擬地址到物理地址的轉換。
- 如上圖所示，程序在 CPU 核心上運行期間，它使用的虛擬地址都會由 MMU 進行翻譯。當需要訪問物理內存設備的時候，MMU 翻譯出的物理地址將會通過總線傳到相應的物理內存設備，從而完成相應的物理內存讀寫請求。
以運行 Hello World 程序的第一條指令為例：
- 操作系統首先把程序從磁盤 /SSD 加載到物理內存中，然后讓 CPU 去執行程序的第一條指令，但是此時該指令存在于內存中。
- 在使用虛擬內存的情況下，CPU 取指令時發出的是指令的虛擬地址，該虛擬地址被 MMU 翻譯為對應的物理地址，包含該物理地址的內存讀請求被發送到物理內存設備，然后物理內存設備把該物理地址對應的內容（即 Hello World 程序的第一條指令）發送給 CPU。
相關概念：
- 邏輯地址：也叫相對地址、用戶地址。邏輯地址是程序中編程使用的。實際中 C 語言的指針，讀取指針變量的值，實際上這個值是邏輯地址，是相對于當前進程數據段的地址。
- 物理地址：也叫絕對地址、內存地址。是最終加載到內存地址寄存器中的地址，內存單元的真正地址。編號從 0 開始一直到物理內存的最大值，映射到實際的內存條上。
- 邏輯地址空間：也稱用戶地址空間或相對地址空間，是由程序中邏輯地址組成的地址范圍，邏輯地址空間大小（即最大可尋址空間）由系統總線中地址總線的寬度決定。
- 物理地址空間：也稱內存地址空間或絕對地址空間，是由內存中一系列存儲單元限定的地址范圍，由實際的物理內存大小決定。
- 重定位：程序和數據裝入內存時，需對目標程序中的邏輯地址進行修改，把程序數據中的邏輯地址轉變為實際內存存放的物理地址的過程稱作重定位。重定位方式：分為靜態重定位和動態重定位。
- 系統總線：又稱內總線或板級總線，是用來連接微機各功能部件從而構成一個完整系統的。常說的微機總線就是指系統總線，如 ISA 總線、EISA 總線、PCI 總線等。系統總線上傳送的信息包括數據信息、地址信息、控制信息，所以包含有三種不同功能的總線，即數據總線 DB、地址總線 AB 和控制總線 CB。
  - 數據總線 DB 用于傳送數據信息。實現 CPU 和存儲器或 I/O 接口等其它部件間的數據通信。數據總線的位數也代表微型計算機的處理性能，稱為字長。
  - 地址總線 AB 是用來傳送地址的，地址只能從 CPU 傳向存儲器或 I/O 端口。地址總線的位數決定了 CPU 可直接尋址的內存空間大小，比如 32 位地址總線可尋址空間為 4GB 的位址。
  - 控制總線 CB 用來傳送控制信號和時序信號。如讀寫信號、中斷響應信號、中斷申請信號、復位信號等。

1.3、程序的鏈接與裝入

1.4、進程的內存映像

不同于存放在硬盤上的可執行程序文件，當一個程序調入內存運行時，就構成了進程的內存映像。一個進程的內存映像一般有幾個要素：
- 代碼段：即程序的二進制代碼，代碼段是只讀的，可以被多個進程共享。
- 數據段：即程序運行時加工處理的對象，包括全局變量和靜態變量。
- 進程控制塊（PCB）：存放在系統區。操作系統通過 PCB 來控制和管理進程。
- 堆：用來存放動態分配的變量。通過調用 malloc 函數動態地向高地址分配空間。
- 棧：用來實現函數調用。從用戶空間的最大地址往低地址方向增長。
代碼段和數據段在程序調入內存時就指定了大小，而堆和棧不一樣。當調用像 malloc 和 free 這樣的 C 標準庫函數時，堆可以在運行時動態地擴展和收縮。用戶棧在程序運行期間也可以動態地擴展和收縮，每次調用一個函數，棧就會增長；從一個函數返回時，就會收縮。
下圖是一個進程在內存中的映像。
- 其中，共享庫用來存放進程用到的共享函數庫代碼，如 printf() 函數等。
- 在只讀代碼段中，
  - .init 是程序初始化時調用的 _init 函數；
  - .text 是用戶程序的機器代碼；
  - .rodata是只讀數據。
- 在讀/寫數據段中，
  - .data 是已初始化的全局變量和靜態變量；
  - .bss 是未初始化及所有初始化為 0 的全局變量和靜態變量。

1.5、內存保護

確保每個進程都有一個單獨的內存空間。內存分配前，需要保護操作系統不受用戶進程的影同時保護用戶進程不受其他用戶進程的影響。內存保護可采取兩種方法：
1. 在 CPU 中設置一對上、下限寄存器，存放用戶進程在主存中的下限和上限地址，每當 CPU 要訪問一個地址時，分別和兩個寄存器的值相比，判斷有無越界，如下圖所示。
2. 采用重定位寄存器（也稱基地址寄存器）和界地址寄存器（也稱限長寄存器）進行越界檢查。
  - 重定位寄存器中存放的是進程的起始物理地址，界地址寄存器中存放的是進程的最大邏輯地址。
  - 內存管理部件將邏輯地址與界地址寄存器進行比較，若未發生地址越界則加上重定位寄存器的值后映射成物理地址，再送交內存單元，如下圖所示。
實現內存保護需要重定位寄存器和界地址寄存器，因此要注意兩者的區別。
- 重定位寄存器是用來“加”的，邏輯地址加上重定位寄存器中的值就能得到物理地址；
- 界地址寄存器是用來“比”的，通過比較界地址寄存器中的值與邏輯地址的值來判斷是否越界。
加載重定位寄存器和界地址寄存器時必須使用特權指令，只有操作系統內核才可以加載這兩個存儲器。這種方案允許操作系統內核修改這兩個寄存器的值，而不允許用戶程序修改。
對于靜態重定位方式：在處理器中設置 “下界寄存器” 和“上界寄存器”。當一個已經裝入主存儲器的進程得到處理器運行時，進程調度計算得到該進程的上界地址（起始地址）和下界地址（最大地址），分別送入上界寄存器和下界寄存器中。處理器執行該進程的指令時，將處理器的物理地址分別與上界寄存器和下界寄存器進行比較，確定是否越界，越界則為地址越界，出錯。如果不越界，則訪問相應內存單元。
對于動態重定位方式：在處理器設置設置 “基址寄存器” 和“限長寄存器”。當一個已經裝入主存儲器的進程得到處理器運行時，進程調度計算得到該進程的長度和起始地址，分別送入限長寄存器（也叫界限寄存器）和基址寄存器（也叫重定位寄存器）中。處理器執行該進程的指令時，首先將邏輯地址與限長寄存器的值作比較，確定是否越界，越界則為地址越界，出錯。如果不越界，再將邏輯地址與基址寄存器運算得到實際的物理地址，然后通過地址總線找到對應的內存單元讀取指令或數據。

1.6、內存共享

并不是所有的進程內存空間都適合共享，只有那些只讀的區域才可以共享。可重入代碼也稱純代碼，是一種允許多個進程同時訪問但不允許被任何進程修改的代碼。但在實際執行時，也可以為每個進程配以局部數據區，將在執行中可能改變的部分復制到該數據區，這樣，程序在執行時只需對該私有數據區中的內存進行修改，并不去改變共享的代碼。
下面通過一個例子來說明內存共享的實現方式。
- 考慮一個可以同時容納 40 個用戶的多用戶系統，他們同時執行一個文本編輯程序，若該程序有 160KB 代碼區和 40KB 數據區，則共需 8000KB 的內存空間來支持 40 個用戶。
- 若 160KB 代碼是可分享的純代碼，則不論是在分頁系統中還是在分段系統中，整個系統只需保留一份副本即可，此時所需的內存空間僅為 $40 K B \times 40 + 160 K B = 1760 K B$ 。
對于分頁系統，假設頁面大小為 4KB，則代碼區占用 40 個頁面、數據區占用 10 個頁面。為實現代碼共享，應在每個進程的頁表中都建立 40 個頁表項，它們都指向共享代碼區的物理頁號。此外，每個進程還要為自己的數據區建立 10 個頁表項，指向私有數據區的物理頁號。
對于分段系統，由于是以段為分配單位的，不管該段有多大，都只需為該段設置一個段表項（指向共享代碼段始址，以及段長 160KB）。由此可見，段的共享非常簡單易行。

1.7、內存分配與回收

存儲管理方式隨著操作系統的發展而發展。在操作系統由單道向多道發展時，存儲管理方式便由單一連續分配發展為固定分區分配。為了能更好地適應不同大小的程序要求，又從固定分區分配發展到動態分區分配。為了更好地提高內存的利用率，進而從連續分配方式發展到離散分配方式——頁式存儲管理。
引入分段存儲管理的目的，主要是滿足用戶在編程和使用方面的要求，其中某些要求是其他幾種存儲管理方式難以滿足的。

1.8、在存儲管理中涉及到兩個問題

是否要把作業全部（一次性）裝入內存，分為兩種：
- 全部（一次性）裝入：非虛擬存儲。
- 部分（多次性）裝入：虛擬存儲。
裝入內存時是否要放在內存連續地址空間，分為兩種：
- 連續分配：必須放在內存連續的地址空間。
- 不連續分配：可以放在內存不連續的地址空間。

采用全部裝入和連續分配，進程執行時速度快、效率高，采用部分裝入和非連續分配都是為了進一步提高內存的利用率，使有限的內存裝入更多更大的作業。

2、連續分配管理方式

2.1、相關概念

連續分配方式是指為一個用戶程序分配一個連續的內存空間，譬如某用戶需要 100MB 的內存空間，連續分配方式就在內存空間中為用戶分配一塊連續的 100MB 空間。連續分配方式主要包括單一連續分配、固定分區分配和動態分區分配。

2.2、單一連續分配

在單一連續分配方式中，內存被分為系統區和用戶區，系統區僅供操作系統使用，通常在低地址部分；用戶區內存中僅有一道用戶程序，即用戶程序獨占整個用戶區，如下圖所示。
- 在用戶區內存中，僅有一道用戶程序，即整個內存的用戶空間由該程序獨占。是一種最簡單的存儲管理方式，在早期的單道批處理系統中使用這種管理方案。
- 采用這種管理方案時，內存被分成兩個區域，一個是系統區域，僅供操作系統使用，可以駐留在內存的低地址部分, 也可以駐留在高地址部分（通常設置在內存的低端）；另一個是用戶區，它是除系統區以外的全部內存區域，這部分區域是提供給用戶使用的區域，任何時刻主存儲器中最多只有一個作業，作業放在從用戶區起始地址開始的連續地址區域。
- 所以，單用戶連續存儲管理只適用于單用戶的情況。
這種方式的優點是簡單、無外部碎片；不需要進行內存保護，因為內存中永遠只有一道程序。缺點是只能用于單用戶、單任務的操作系統中；有內部碎片；存儲器的利用率極低。
單一連續分區存儲管理的地址變換與地址保護。單一連續分區使用靜態重定位，不需要專門硬件進行地址變換，但是會有硬件保護機構，以確保不干擾系統區中的信息，方法有：
1. 上界寄存器和下界寄存器：上界寄存器和下界寄存器中存放用戶區的起始地址和終止地址，運行時檢查指令或數據的地址，若不在上界寄存器和下界寄存器的范圍內，則發生越界中斷。
2. 內核態（系統態 / 管態）與用戶態（目態）工作：如果當前在用戶態下工作，內存訪問時對硬件進行校驗，以保證系統區不被訪問，如果系統區被訪問則產生中斷，控制權交給操作系統。在內核態下工作，能訪問整個存儲空間。用戶態是用戶進程的工作方式，而系統態是系統進程的工作方式。
3. 不做特別管理：如 MS-DOS 等單用戶單任務微機操作系統。
單一連續分區存儲管理的管理特點：
- 管理簡單。容易記住存儲器的狀態，不是全部空閑就是全部已分配；當作業被調度時就獲得全部用戶空間；全部主存空間都分配給一個作業使用；作業運行完后，全部主存空間又恢復成空閑（以上所指的全部主存空間是用戶區空間）。
- 資源利用率低。存儲器沒有得到充分利用，作業的大小與存儲器的可用空間的大小不一定一致，作業的全部信息都裝入主存，占用主存空間。處理機的利用率較低，因為是單道處理，一旦一個作業提出 I/O 請求，則 CPU 空閑。
- 不支持覆蓋技術、對換技術、虛擬存儲等技術，作業地址空間大于內存可用空間就無法運行。

2.3、固定分區分配

固定分區分配是最簡單的一種多道程序存儲管理方式，它將用戶內存空間劃分為若干固定大小的分區，每個分區只裝入一道作業。當有空閑分區時，便可再從外存的后備作業隊列中選擇適當大小的作業裝入該分區，如此循環。在劃分分區時有兩種不同的方法，如下圖所示。
- 分區大小相等。程序太小會造成浪費，程序太大又無法裝入，缺乏靈活性。這種劃分方式常被用于利用一臺計算機控制多個相同對象的場合，因為這些對象所需的內存空間是大小相等的。例如，爐溫群控系統，就是利用一臺計算機去控制多臺相同的冶煉爐。
- 分區大小不等。劃分為多個較小的分區、適量的中等分區和少量大分區。這樣，便可根據作業的大小為之分配適當的分區。
為了便于分配和回收，建立一張分區使用表，通常按分區大小排隊，各表項包括對應分區的始址、大小及狀態（是否已分配），如下圖所示。
- 分配內存時，便檢索該表，以找到一個能滿足要求且尚未分配的分區分配給裝入程序，并將對應表項的狀態置為“已分配”；若找不到這樣的分區，則拒絕分配。
- 回收內存時，只需將對應表項的狀態置為“未分配”即可。
固定分區中的地址轉換與存儲保護。固定分區存儲管理實際中可采用可重定位裝入（靜態重定位）方式，也可采用運行時動態裝入（動態重定位）方式：
1. 靜態重定位方式：裝入內存后所有地址轉換為物理地址，通過上界寄存器和下界寄存器進行地址保護。
2. 動態重定位方式：裝入內存后地址仍然是邏輯地址，通過限長寄存器和基址寄存器進行地址轉換和地址保護。在執行的時候，首先將邏輯地址與限長寄存器的值作比較，確定是否越界，越界則出錯。不越界時再與基址寄存器的值運算轉換為物理地址，然后通過地址總線找到對應的內存單元讀取指令或數據。
這種方式存在兩個問題：
1. 程序太大而放不進任何一個分區；
2. 當程序小于固定分區大小時，也要占用一個完整的內存分區，這樣分區內部就存在空間浪費，這種現象稱為內部碎片。固定分區方式無外部碎片，但不能實現多進程共享一個主存區，所以存儲空間利用率低。

2.4、動態分區分配

當進程裝入或換入主存時，若內存中有多個足夠大的空閑塊，則操作系統必須確定分配哪個內存塊給進程使用，這就是動態分區的分配策略。
動態分區分配的基本原理
- 如下圖所示，系統有 64MB 內存空間，其中低 8MB 固定分配給操作系統，其余為用戶可用內存。
  - 開始時裝入前三個進程，它們分別分配到所需的空間后，內存僅剩 4MB，進程 4 無法裝入。
  - 在某個時刻，內存中沒有一個就緒進程，CPU 出現空閑，操作系統就換出進程 2，換入進程 4。由于進程 4 比進程 2 小，這樣在主存中就產生了一個 6MB 的內存塊。
  - 之后 CPU 又出現空閑，需要換入進程 2，而主存無法容納進程 2，操作系統就換出進程 1，換入進程 2。
- 動態分區在開始時是很好的，但是隨著時間的推移，內存中會產生越來越多的小內存塊，內存的利用率也隨之下降。這些小內存塊被稱為外部碎片，它存在于所有分區的外部，與固定分區中的內部碎片正好相對。外部碎片可通過緊湊技術來克服，即操作系統不時地對進程進行移動和整理。但是，這需要動態重定位寄存器的支持，且相對費時。緊湊過程實際上類似于 Windows 系統中的磁盤碎片整理程序，只不過后者是對外存空間的緊湊。
- 動態分區分配的內存回收方法：在動態分區分配中，與固定分區分配類似，設置一張空閑分區鏈（表），可以按始址排序。
  - 分配內存時，檢索空閑分區鏈，找到所需的分區，若其大小大于請求大小，則從該分區中按請求大小分割一塊空間分配給裝入進程（若剩余部分小到不足以劃分，則不需要分割），余下部分仍然留在空閑分區鏈中。
  - 回收內存時，系統根據回收分區的始址，從空閑分區鏈中找到相應的插入點，此時可能出現四種情況：
    1. 回收區與插入點的前一空閑分區相鄰，此時將這兩個分區合并，并修改前一分區表項的大小為兩者之和；
    2. 回收區與插入點的后一空閑分區相鄰，此時將這兩個分區合并，并修改后一分區表項的始址和大小；
    3. 回收區同時與插入點的前、后兩個分區相鄰，此時將這三個分區合并，修改前一分區表項的大小為三者之和，并取消后一分區表項；
    4. 回收區沒有相鄰的空閑分區，此時應該為回收區新建一個表項，填寫始址和大小，并插入空閑分區鏈。

以上三種內存分區管理方法有一個共同特點，即用戶程序在主存中都是連續存放的。

2.4.1、基于順序搜索的分配算法

將作業裝入主存時，需要按照一定的分配算法從空閑分區鏈（表）中選出一個分區，以分配給該作業。按分區檢索方式，可分為順序分配算法和索引分配算法。順序分配算法是指依次搜索空閑分區鏈上的空閑分區，以尋找一個大小滿足要求的分區，順序分配算法有以下四種。

首次適應（First Fit）算法。空閑分區按地址遞增的次序排列。
- 每次分配內存時，順序查找到第一個能滿足大小的空閑分區，分配給作業。首次適應算法保留了內存高地址部分的大空閑分區，有利于后續大作業的裝入。
- 但它會使內存低地址部分出現許多小碎片，而每次分配查找時都要經過這些分區，因此增加了開銷。
鄰近適應（Next Fit）算法。也稱循環首次適應算法，由首次適應算法演變而成。
- 不同之處是，分配內存時從上次查找結束的位置開始繼續查找。鄰近適應算法試圖解決該問題。
- 它讓內存低、高地址部分的空閑分區以同等概率被分配，劃分為小分區，導致內存高地址部分沒有大空閑分區可用。通常比首次適應算法更差。
最佳適應（Best Fit）算法。空閑分區按容量遞增的次序排列。
- 每次分配內存時，順序查找到第一個能滿足大小的空閑分區，即最小的空閑分區，分配給作業。
- 最佳適應算法雖然稱為最佳，能更多地留下大空閑分區，但性能通常很差，因為每次分配會留下越來越多很小的難以利用的內存塊，進而產生最多的外部碎片。
最壞適應（Worst Fit）算法。空閑分區按容量遞減的次序排列。
- 每次分配內存時，順序查找到第一個能滿足要求的之空閑分區，即最大的空閑分區，從中分割一部分空間給作業。
- 與最佳適應算法相反，最壞適應算法選擇最大的空閑分區，這看起來最不容易產生碎片，但是把最大的空閑分區劃分開，會很快導致沒有大空閑分區可用，因此性能也很差。

綜合來看，首次適應算法的開銷小，性能最好，回收分區也不需要對空閑分區重新排序。

2.4.2、基于索引搜索的分配算法

當系統很大時，空閑分區鏈可能很長，此時采用順序分配算法可能很慢。因此，在大、中型系統中往往采用索引分配算法。
索引分配算法的思想是，根據其大小對空閑分區分類，對于每類（大小相同）空閑分區，單獨設立一個空閑分區鏈，并設置一張索引表來管理這些空閑分區鏈。當為進程分配空間時，在索引表中查找所需空間大小對應的表項，并從中得到對應的空閑分區鏈的頭指針，從而獲得一個空閑分區。
索引分配算法有以下三種。
1. 快速適應算法。空閑分區的分類根據進程常用的空間大小進行劃分。
  - 分配過程分為兩步：
    - 首先根據進程的長度，在索引表中找到能容納它的最小空閑分區鏈表；
    - 然后從鏈表中取出第一塊進行分配。
  - 優點是查找效率高、不產生內部碎片；
  - 缺點是回收分區時，需要有效地合并分區，算法比較復雜，系統開銷較大。
2. 伙伴系統。規定所有分區的大小均為 2 的 k 次冪（k 為正整數）。
  - 當需要為進程分配大小為 n 的分區時 $（2i?1<n≤2i）（2^{i-1} < n \leq 2^i）$ ，在大小為 $2^i$ 的空閑分區鏈中查找。
    - 若找到，則將該空閑分區分配給進程。否則，表示大小為 $2^i$ 的空閑分區已耗盡，需要在大小為 $2^{i+1}$ 的空閑分區鏈中繼續査找。
    - 若存在大小為 $2^{i+1}$ 的空閑分區，則將其等分為兩個分區，這兩個分區稱為一對伙伴，其中一個用于分配，而將另一個加入大小為 $2^i$ 的空閑分區鏈。若不存在，則繼續查找，直至找到為止。
  - 回收時，也可能需要對伙伴分區進行合并。
3. 哈希算法。
  - 根據空閑分區鏈表的分布規律，建立哈希函數，構建一張以空閑分區大小為關鍵字的哈希表，每個表項記錄一個對應空閑分區鏈的頭指針。
  - 分配時，根據所需分區大小，通過哈希函數計算得到哈希表中的位置，從中得到相應的空閑分區鏈表。

注意：

在連續分配方式中，我們發現，即使內存有超過 1GB 的空閑空間，但若沒有連續的 1GB 空間，則需要 1GB 空間的作業仍然是無法運行的；但若采用非連續分配方式，則作業所要求的 1GB 內存空間可以分散地分配在內存的各個區域，當然，這也需要額外的空間去存儲它們（分散區域）的索引，使得非連續分配方式的存儲密度低于連續分配方式。
非連續分配方式根據分區的大小是否固定，分為分頁存儲管理和分段存儲管理。在分頁存儲管理中，又根據運行作業時是否要將作業的所有頁面都裝入內存才能運行，分為基本分頁存儲管理和請求分頁存儲管理。

3、非連續分配管理方式

連續分配存儲管理方式產生的問題：要求連續的存儲區、碎片問題。
離散分配，允許將作業離散放到多個不相鄰接的分區中。
- 分頁式存儲管理：離散分配的基本單位是頁。
- 分段式存儲管理：離散分配的基本單位是段。
- 段頁式存儲管理：離散分配的基本單位是段、頁。

3.1、基本分頁存儲管理

3.1.1、分頁思想的由來

固定分區會產生內部碎片，動態分區會產生外部碎片，這兩種技術對內存的利用率都比較低。
我們希望內存的使用能盡量避免碎片的產生，這就引入了分頁的思想：將內存空間分為若干固定大小（如 4KB）的分區，稱為頁框、頁幀或物理塊。進程的邏輯地址空間也分為與塊大小相等的若干區域，稱為頁或頁面。操作系統以頁框為單位為各個進程分配內存空間。
從形式上看，分頁的方法像是分區相等的固定分區技術，分頁管理不產生外部片。但它又有本質的不同點：塊的大小相對分區要小很多，而且進程也按照塊進行劃分，進程運行時按塊申請主存可用空間并執行。這樣，進程只會在為最后一個不完整的塊申請一個主存塊空間時，才產生主存碎片，所以盡管會產生內部碎片，但這種碎片相對于進程來說也是很小的，每個進程平均只產生半個塊大小的內部碎片（也稱頁內碎片）。

3.1.2、分頁存儲的幾個基本概念

頁面和頁面大小
- 進程的邏輯地址空間中的每個頁面有一個編號，稱為頁號，從 0 開始；內存空間中的每個頁框也有一個編號，稱為頁框號（或物理塊號），也從 0 開始。進程在執行時需要申請內存空間，即要為每個頁面分配內存中的可用頁框，這就產生了頁號和頁框號的一一對應。
- 為方便地址轉換，頁面大小應是 2 的整數次冪。同時頁面大小應該適中，頁面太小會使進程的頁面數過多，這樣頁表就會過長，占用大量內存，而且也會增加硬件地址轉換的開銷，降低頁面換入/換出的效率；頁面過大又會使頁內碎片增多，降低內存的利用率。
地址結構
- 某個分頁存儲管理的邏輯地址結構如下圖所示。
- 地址結構包含兩部分：前一部分為頁號 P，后一部分為頁內偏移量 W。
  - 地址長度為 32 位，其中 $0～110\sim11$ 位為頁內地址，即每頁大小為 $2^{12}$ B；
  - $12～3112\sim31$ 位為頁號，即最多允許 $2^{20}$ B。

注意，地址結構決定了虛擬內存的尋址空間有多大。在實際問題中，頁號、頁內偏移、邏輯地址可能是用十進制數給出的，若題目用二進制數給出時，讀者要會轉換。

頁表
- 為了便于找到進程的每個頁面在內存中存放的位置，系統為每個進程建立一張頁面映射表，簡稱頁表。
- 進程的每個頁面對應一個頁表項，每個頁表項由頁號和塊號組成，它記錄了頁面在內存中對應的物理塊號，如下圖所示。
- 進程執行時，通過查找頁表，即可找到每頁在內存中的物理塊號。可見，頁表的作用是實現從頁號到物理塊號的地址映射。

3.1.3、基本地址變換機構

地址變換機構的任務是將邏輯地址轉換為內存中的物理地址。地址變換是借助于頁表實現的。下圖給出了分頁存儲管理系統中的地址變換機構。

在頁表中，頁表項連續存放，因此頁號可以是隱含的，不占用存儲空間。

為了提高地址變換的速度，在系統中設置一個頁表寄存器（PTR），存放頁表在內存的始址 F 和頁表長度 M。寄存器的造價昂貴，因此在單 CPU 系統中只設置一個頁表寄存器。平時，進程未執行時，頁表的始址和頁表長度存放在本進程的 PCB 中。當進程被調度執行時，才將頁表始址和頁表長度裝入頁表寄存器中。
設頁面大小為 L，邏輯地址 A 到物理地址 E 的變換過程如下（假設邏輯地址、頁號、每頁的長度都是十進制數）：
1. 根據邏輯地址計算出頁號 $P = A / L$ 、頁內偏移量 $W=A%LW=A\%L$ 。
2. 判斷頁號是否越界，若 $\geq 頁表長度 M$ ，則產生越界中斷，否則繼續執行。
3. 在頁表中查詢頁號對應的頁表項，確定頁面存放的物理塊號。 $頁號 P 對應的頁表項地址 = 頁表始址 F + 頁號 P \times 頁表項長度$ ，取出該頁表項內容 b，即為物理塊號。
4. 計算物理地址 $E = b L + W$ ，用物理地址 E 去訪存。注意， $物理地址 = 頁面在內存中的始址 + 頁內偏移量$ ， $頁面在內存中的始址 = 塊號 \times 塊大小（頁面大小）$ 。
以上整個地址變換過程均是由硬件自動完成的。例如，若頁面大小為 1KB，頁號 2 對應的物理塊為 $b = 8$ ，計算邏輯地址 $A = 2500$ 的物理地址 E 的過程如下： $P = 2500/1 K = 2$ ， $W=2500%1K=452W=2500\%1K=452$ ，查找得到頁號 2 對應的物理塊的塊號為 8， $E = 8 \times 1024 + 452 = 8644$ 。

計算條件用十進制數和用二進制數給出，過程會稍有不同。頁式管理只需給出一個整數就能確定對應的物理地址，因為頁面大小 L 是固定的。因此，頁式管理中地址空間是一維的。

頁表項的大小不是隨意規定的，而是有所約束的。如何確定頁表項的大小?
- 頁表項的作用是找到該頁在內存中的位置。
- 以 32 位內存地址空間、按字節編址、一頁 4KB 為例，地址空間內一共有 $2^{32}B/4KB=2^{20}$ 頁，因此需要 $log_2 2^{20} = 20$ 位才能保證表示范圍能容納所有頁面，又因為內存以字節作為編址單位，即 $\geq \lceil 20 / 8 \rceil = 3 \text{B}$ 。
- 所以在這個條件下，為了保證頁表項能夠指向所有頁面，頁表項的大小應大于或等于 3B。當然，也可以選擇更大的頁表項，讓一個頁面能夠正好容納整數個頁表項，或便于增加一些其他信息。
下面討論分頁管理方式存在的兩個主要問題：① 每次訪存操作都需要進行邏輯地址到物理地址的轉換，地址轉換過程必須足夠快，否則訪存速度會降低；② 每個進程引入頁表，用于存儲映射機制，頁表不能太大，否則內存利用率會降低。

3.1.4、具有快表的地址變換機構

由上面介紹的地址變換過程可知，若頁表全部放在內存中，則存取一個數據或一條指令至少要訪問兩次內存：第一次是訪問頁表，確定所存取的數據或指令的物理地址；第二次是根據該地址存取數據或指令。顯然，這種方法比通常執行指令的速度慢了一半。
為此，在地址變換機構中增設一個具有并行查找能力的高速緩沖存儲器——快表（TLB），也稱相聯存儲器，用來存放當前訪問的若干頁表項，以加速地址變換的過程。與此對應，主存中的頁表常稱為慢表。具有快表的地址變換機構如下圖所示。
在具有快表的分頁機制中，地址的變換過程如下：
1. CPU 給出邏輯地址后，由硬件進行地址轉換，將頁號與快表中的所有頁號進行比較。
2. 若找到匹配的頁號，說明要訪問的頁表項在快表中有副本，則直接從中取出該頁對應的頁框號，與頁內偏移量拼接形成物理地址。這樣，存取數據僅一次訪存即可實現。
3. 若未找到匹配的頁號，則需要訪問主存中的頁表，讀出頁表項后，應同時將其存入快表，以便后面可能的再次訪問。若快表已滿，則須按照特定的算法淘汰一個舊頁表項。
一般快表的命中率可達 90% 以上，這樣分頁帶來的速度損失就可降低至 10% 以下。快表的有效性基于著名的局部性原理。

3.1.5、兩級頁表

引入分頁管理后，進程在執行時不需要將所有頁調入內存頁框，而只需將保存有映射關系的頁表調入內存，但仍需考慮頁表的大小。
以 32 位邏輯地址空間、頁面大小 4KB、頁表項大小 4B 為例：頁內偏移為 $log_24K=12$ 位，頁號部分為 20 位，則每個進程頁表中的頁表項數可達 $2^{20}$ 之多僅頁表就要占用 $2^{20}×4B/4KB=1K$ 個頁，而且還要求是連續的。顯然這是不切實際的。
解決上述問題的方法有兩種：① 對于頁表所需的內存空間，采用離散分配方式，用一張索引表來記錄各個頁表的存放位置，這就解決了頁表占用連續內存空間的問題；② 只將當前需要的部分頁表項調入內存，其余的頁表項仍駐留磁盤，需要時再調入（虛擬內存的思想），這就解決了頁表占用內存過多的問題。
讀者也許發現這個方案就和當初引進頁表機制的思路一模一樣，實際上就是為離散分配的頁表再建立一張頁表，稱為外層頁表（或頁目錄）。仍以上面的條件為例，當采用兩級分頁時，對頁表再進行分頁，則外層頁表需要 1K 個頁表項，剛好占用 4KB 的內存空間，使得外層頁表的大小正好等于一頁，這樣就得到了邏輯地址空間的格式，如下圖所示。
兩級頁表是在普通頁表結構上再加一層頁表，其結構如下圖所示。
在頁表的每個表項中，存放的是進程的某頁對應的物理塊號，如 0 號頁存放在 1 號物理塊中，1 號頁存放在 5 號物理塊中。在外層頁表的每個表項中，存放的是某個頁表分頁的始址，如 0 號頁表存放在 3 號物理塊中。可以利用外層頁表和頁表來實現進程從邏輯地址到物理地址的變換。
為了方便實現地址變換，需要在系統中增設一個外層頁表寄存器（也稱頁目錄基址寄存器），用于存放頁目錄始址。
- 將邏輯地址中的頁目錄號作為頁目錄的索引，從中找到對應頁表的始址；
- 再用二級頁號作為頁表分頁的索引，從中找到對應的頁表項；
- 將頁表項中的物理塊號和頁內偏移拼接，即為物理地址，再用該地址訪問內存單元。共進行了 3 次訪存。
對于更大的邏輯地址空間，以 64 位為例，若采用兩級分頁，則頁面大小為 4KB，頁表項大小為 4B；若按物理塊大小劃分頁表，則有 42 位用于外層頁號，此時外層頁表有 4096G 個頁表項，需占用 16384GB 的連續內存空間，顯然這是無法接受的，因此必須采用多級頁表，再對外層頁表分頁。建立多級頁表的目的在于建立索引，以免浪費內存空間去存儲無用的頁表項。

3.2、基本分段存儲管理

分段思想的由來：分段存儲管理方式的引入是為了滿足用戶的要求。
1. 方便編程：通常一個作業是由多個程序段和數據段組成的，一般情況下，用戶希望按邏輯關系對作業分段，并能根據名字來訪問程序段和數據段。
2. 信息共享：共享是以信息的邏輯單位為基礎的。頁是存儲信息的物理單位，段卻是信息的邏輯單位。頁式管理中地址空間是一維的，主程序，子程序都順序排列，共享公用子程序比較困難，一個共享過程可能需要幾十個頁面。
3. 信息保護：頁式管理中，一個頁面中可能裝有 2 個不同的子程序段的指令代碼，不能通過頁面共享實現共享一個邏輯上完整的子程序或數據塊。段式管理中，可以以信息的邏輯單位進行保護。
4. 動態增長：實際應用中，某些段（數據段）會不斷增長，前面的存儲管理方法均難以實現。
5. 動態鏈接：動態鏈接在程序運行時才把主程序和要用到的目標程序（程序段）鏈接起來。

分頁管理方式是從計算機的角度考慮設計的，目的是提高內存的利用率，提升計算機的性能。分頁通過硬件機制實現，對用戶完全透明。分段管理方式的提出則考慮了用戶和程序員，以滿足方便編程、信息保護和共享、動態增長及動態鏈接等多方面的需要。

3.2.1、分段

分段系統將用戶進程的邏輯地址空間劃分為大小不等的段。
例如，用戶進程由主程序段、兩個子程序段、棧段和數據段組成，于是可以將這個進程劃分為 5 段，每段從 0 開始編址，并分配一段連續的地址空間（段內要求連續，段間不要求連續，進程的地址空間是二維的）。
分段存儲管理的邏輯地址結構由段號 S 與段內偏移量 W 兩部分組成。在下圖中，段號為 16 位，段內偏移量為 16 位，因此一個進程最多有 $2^{16}=65536$ 段，最大段長為 64KB。
在頁式系統中，邏輯地址的頁號和頁內偏移量對用戶是透明的，但在分段系統中，段號和段內偏移量必須由用戶顯式提供，在高級程序設計語言中，這個工作由編譯程序完成。

3.2.2、段表

每個進程都有一張邏輯空間與內存空間映射的段表，進程的每個段對應一個段表項，段表項記錄了該段在內存中的始址和段的長度。
段表的內容如下圖所示。
配置段表后，執行中的進程可以通過查找段表，找到每段所對應的內存區。可見，段表用于實現從邏輯段到物理內存區的映射，如下圖所示。

3.2.3、地址變換機構

分段系統的地址變換過程如下圖所示。
為了實現進程從邏輯地址到物理地址的變換功能，在系統中設置了一個段表寄存器，用于存放段表始址 F 和段表長度 M。從邏輯地址 A 到物理地址 E 之間的地址變換過程如下：
1. 從邏輯地址 A 中取出前幾位為段號 S，后幾位為段內偏移量 W。
2. 判斷段號是否越界，若 $\geq 段表長度 M$ ，則產生越界中斷，否則繼續執行。
3. 在段表中査詢段號對應的段表項， $段號 S 對應的段表項地址 = 段表始址 F + 段號 S \times 段表項長度$ 。取出段表項中該段的段長 C，若 $\geq C$ ，則產生越界中斷，否則繼續執行。
4. 取出段表項中該段的始址 b，計算物理地址 $E = b + W$ ，用物理地址 E 去訪存。

3.2.4、分頁和分段的對比

分頁和分段有許多相似之處，兩者都是非連續分配方式，都要通過地址映射機構實現地址變換。但是，在概念上兩者完全不同，主要表現在以下三個方面：

頁是信息的物理單位，分頁的主要目的是提高內存利用率，分頁完全是系統的行為，對用戶是不可見的。段是信息的邏輯單位，分段的主要目的是更好地滿足用戶需求，用戶按照邏輯關系將程序劃分為若干段，分段對用戶是可見的。
頁的大小固定且由系統決定。段的長度不固定，具體取決于用戶所編寫的程序。
分頁管理的地址空間是一維的。段式管理不能通過給出一個整數便確定對應的物理地址，因為每段的長度是不固定的，無法通過除法得出段號，無法通過求余得出段內偏移，所以一定要顯式給出段號和段內偏移，因此分段管理的地址空間是二維的。

3.2.5、段的共享與保護

在分頁系統中，雖然也能實現共享，但遠不如分段系統來得方便。若被共享的代碼占 N 個頁框，則每個進程的頁表中都要建立 N 個頁表項，指向被共享的 N 個頁框。在分段系統中，不管該段有多大，都只需為該段設置一個段表項，因此非常容易實現共享。
為了實現段共享，在系統中配置一張共享段表，所有共享的段都在共享段表中占一個表項。
- 表項中記錄了共享段的段號、段長、內存始址、狀態（存在）位、外存始址和共享進程計數 count 等信息。
- 共享進程計數 count 記錄有多少進程正在共享該段，僅當所有共享該段的進程都不再需要它時，此時其 $co u n t = 0$ ，才回收該段所占的內存區。
- 對于一個共享段，在不同的進程中可以具有不同的段號，每個進程用自己進程的段號去訪問該共享段。
不能被任何進程修改的代碼稱為可重入代碼或純代碼，它是一種允許多個進程同時訪問的代碼。為了防止程序在執行時修改共享代碼，在每個進程中都必須配以局部數據區，將在執行過程中可能改變的部分復制到數據區，這樣，進程就可對該數據區中的內容進行修改。
與分頁管理類似，分段管理的保護方法主要有兩種：一種是存取控制保護，另一種是地址越界保護。地址越界保護將段表寄存器中的段表長度與邏輯地址中的段號比較，若段號大于段表長度，則立生越界中斷:再將段表項中的段長和邏輯地址中的段內偏移進行比較，若段內偏移大于段長，也會產生越界中斷。分頁管理只需要判斷頁號是否越界，頁內偏移是不可能越界的。

3.3、段頁式存儲管理

分頁存儲管理能有效地提高內存利用率，而分段存儲管理能反映程序的邏輯結構并有利于段的共享和保護。將這兩種存儲管理方法結合起來，便形成了段頁式存儲管理方式。
在段頁式系統中，進程的地址空間首先被分成若干邏輯段，每段都有自己的段號，然后將每段分成若干大小固定的頁。對內存空間的管理仍然和分頁存儲管理一樣，將其分成若干和頁面大小相同的存儲塊，對內存的分配以存儲塊為單位，如下圖所示。
在段頁式系統中，進程的邏輯地址分為三部分：段號、頁號和頁內偏移量，如下圖所示。
為了實現地址變換，系統為每個進程建立一張段表，每個段對應一個段表項，每個段表項至少包括段號、頁表長度和頁表始址：每個段有一張頁表，每個頁表項至少包括頁號和塊號。此外，系統中還應有一個段表寄存器，指出進程的段表始址和段表長度（段表寄存器和頁表寄存器的作用都有兩個，一是在段表或頁表中尋址，二是判斷是否越界）。