記憶體管理
包括記憶體管理和虛拟記憶體管理
記憶體管理包括記憶體管理概念、交換與覆寫、連續配置設定管理方式和非連續配置設定管理方式（分頁管理方式、分段管理方式、段頁式管理方式）。
虛拟記憶體管理包括虛拟記憶體概念、請求分頁管理方式、頁面置換算法、頁面配置設定政策、工作集和抖動。
3.1 記憶體管理的概念
記憶體管理(Memory Management)是作業系統設計中最重要和最複雜的内容之一。雖然計算機硬體一直在飛速發展，記憶體容量也在不斷增長，但是仍然不可能将所有使用者程序和系統所需要的全部程式和資料放入主存中，是以作業系統必須将記憶體空間進行合理地劃分和有效地動态配置設定。作業系統對記憶體的劃分和動态配置設定，就是記憶體管理的概念。
有效的記憶體管理在多道程式設計中非常重要，不僅友善使用者使用存儲器、提高記憶體使用率，還可以通過虛拟技術從邏輯上擴充存儲器。
記憶體管理的功能有：
- 記憶體空間的配置設定與回收：由作業系統完成主存儲器空間的配置設定和管理，使程式員擺脫存儲配置設定的麻煩，提高程式設計效率。
- 位址轉換：在多道程式環境下，程式中的邏輯位址與記憶體中的實體位址不可能一緻，是以存儲管理必須提供位址變換功能，把邏輯位址轉換成相應的實體位址。
- 記憶體空間的擴充：利用虛拟存儲技術或自動覆寫技術，從邏輯上擴充記憶體。
- 存儲保護：保證各道作業在各自的存儲空間内運作，.互不幹擾。
在進行具體的記憶體管理之前，需要了解程序運作的基本原理和要求。
程式裝入和連結
建立程序首先要将程式和資料裝入記憶體。将使用者源程式變為可在記憶體中執行的程式，通常需要以下幾個步驟：
- 編譯：由編譯程式将使用者源代碼編譯成若幹個目标子產品。
- 連結：由連結程式将編譯後形成的一組目标子產品，以及所需庫函數連結在一起，形成一個完整的裝入子產品。
- 裝入：由裝入程式将裝入子產品裝入記憶體運作。
這三步過程如圖3-1所示。
image
圖3-1 對使用者程式的處理步驟
程式的連結有以下三種方式：
- 靜态連結：在程式運作之前，先将各目标子產品及它們所需的庫函數連結成一個完整的可執行程式，以後不再拆開。
- 裝入時動态連結：将使用者源程式編譯後所得到的一組目标子產品，在裝入記憶體時，釆用邊裝入邊連結的連結方式。
- 運作時動态連結：對某些目标子產品的連結，是在程式執行中需要該目标子產品時，才對它進行的連結。其優點是便于修改和更新，便于實作對目标子產品的共享。
記憶體的裝入子產品在裝入記憶體時，同樣有以下三種方式：
- 絕對裝入。在編譯時，如果知道程式将駐留在記憶體的某個位置，編譯程式将産生絕對位址的目标代碼。絕對裝入程式按照裝入子產品中的位址，将程式和資料裝入記憶體。由于程式中的邏輯位址與實際記憶體位址完全相同，故不需對程式和資料的位址進行修改。
絕對裝入方式隻适用于單道程式環境。另外，程式中所使用的絕對位址,可在編譯或彙編時給出，也可由程式員直接賦予。而通常情況下在程式中釆用的是符号位址，編譯或彙編時再轉換為絕對位址。
- 可重定位裝入。在多道程式環境下，多個目标子產品的起始位址通常都是從0開始，程式中的其他位址都是相對于起始位址的,此時應釆用可重定位裝入方式。根據記憶體的目前情況，将裝入子產品裝入到記憶體的适當位置。裝入時對目标程式中指令和資料的修改過程稱為重定位，位址變換通常是在裝入時一次完成的，是以又稱為靜态重定位，如圖3-2(a) 所示。
圖3-2 重定向類型
靜态重定位的特點是在一個作業裝入記憶體時，必須配置設定其要求的全部記憶體空間，如果沒有足夠的記憶體，就不能裝入該作業。此外，作業一旦進入記憶體後，在整個運作期間不能在記憶體中移動，也不能再申請記憶體空間。
- 動态運作時裝入，也稱為動态重定位，程式在記憶體中如果發生移動，就需要釆用動态的裝入方式。裝入程式在把裝入子產品裝入記憶體後，并不立即把裝入子產品中的相對位址轉換為絕對位址，而是把這種位址轉換推遲到程式真正要執行時才進行。是以，裝入記憶體後的所有位址均為相對位址。這種方式需要一個重定位寄存器的支援，如圖3-2(b)所示。
動态重定位的特點是可以将程式配置設定到不連續的存儲區中；在程式運作之前可以隻裝入它的部分代碼即可投入運作，然後在程式運作期間，根據需要動态申請配置設定記憶體；便于程式段的共享，可以向使用者提供一個比存儲空間大得多的位址空間。
邏輯位址空間與實體位址空間
編譯後，每個目标子產品都是從0号單元開始編址，稱為該目标子產品的相對位址（或邏輯位址)。
當連結程式将各個子產品連結成一個完整的可執行目标程式時，連結程式順序依次按各個子產品的相對位址構成統一的從0号單元開始編址的邏輯位址空間。使用者程式和程式員隻需知道邏輯位址，而記憶體管理的具體機制則是完全透明的，它們隻有系統程式設計人員才會涉及。不同程序可以有相同的邏輯位址，因為這些相同的邏輯位址可以映射到主存的不同位置。
實體位址空間是指記憶體中實體單元的集合，它是位址轉換的最終位址，程序在運作時執行指令和通路資料最後都要通過實體位址從主存中存取。當裝入程式将可執行代碼裝入記憶體時，必須通過位址轉換将邏輯位址轉換成實體位址，這個過程稱為位址重定位。
記憶體保護
記憶體配置設定前，需要保護作業系統不受使用者程序的影響，同時保護使用者程序不受其他使用者程序的影響。通過釆用重定位寄存器和界位址寄存器來實作這種保護。重定位寄存器含最小的實體位址值，界位址寄存器含邏輯位址值。每個邏輯位址值必須小于界位址寄存器；記憶體管理機構動态地将邏輯位址與界位址寄存器進行比較，如果未發生位址越界，則加上重定位寄存器的值後映射成實體位址，再送交記憶體單元，如圖3-3所示。
當CPU排程程式選擇程序執行時，派遣程式會初始化重定位寄存器和界位址寄存器。每一個邏輯位址都需要與這兩個寄存器進行核對，以保證作業系統和其他使用者程式及資料不被該程序的運作所影響。
圖3-3 重定位和界位址寄存器的硬體支援
3.2 記憶體覆寫與記憶體交換
覆寫與交換技術是在多道程式環境下用來擴充記憶體的兩種方法。
記憶體覆寫
早期的計算機系統中，主存容量很小，雖然主存中僅存放一道使用者程式，但是存儲空間放不下使用者程序的現象也經常發生，這一沖突可以用覆寫技術來解決。
覆寫的基本思想是：由于程式運作時并非任何時候都要通路程式及資料的各個部分（尤其是大程式），是以可以把使用者空間分成一個固定區和若幹個覆寫區。将經常活躍的部分放在固定區，其餘部分按調用關系分段。首先将那些即将要通路的段放入覆寫區，其他段放在外存中，在需要調用前，系統再将其調入覆寫區，替換覆寫區中原有的段。
覆寫技術的特點是打破了必須将一個程序的全部資訊裝入主存後才能運作的限制，但當同時運作程式的代碼量大于主存時仍不能運作。
記憶體交換
交換（對換）的基本思想是，把處于等待狀态（或在CPU排程原則下被剝奪運作權利）的程式從記憶體移到輔存，把記憶體空間騰出來，這一過程又叫換出；把準備好競争CPU運作的程式從輔存移到記憶體，這一過程又稱為換入。中級排程就是釆用交換技術。
例如，有一個CPU釆用時間片輪轉排程算法的多道程式環境。時間片到，記憶體管理器将剛剛執行過的程序換出，将另一程序換入到剛剛釋放的記憶體空間中。同時，CPU排程器可以将時間片配置設定給其他已在記憶體中的程序。每個程序用完時間片都與另一程序交換。理想情況下，記憶體管理器的交換過程速度足夠快，總有程序在記憶體中可以執行。
有關交換需要注意以下幾個問題：
- 交換需要備份存儲，通常是快速磁盤。它必須足夠大，并且提供對這些記憶體映像的直接通路。
- 為了有效使用CPU，需要每個程序的執行時間比交換時間長，而影響交換時間的主要是轉移時間。轉移時間與所交換的記憶體空間成正比。
- 如果換出程序，必須確定該程序是完全處于空閑狀态。
- 交換空間通常作為磁盤的一整塊，且獨立于檔案系統，是以使用就可能很快。
- 交換通常在有許多程序運作且記憶體空間吃緊時開始啟動，而系統負荷降低就暫停。
- 普通的交換使用不多，但交換政策的某些變種在許多系統中（如UNIX系統）仍發揮作用。
交換技術主要是在不同程序（或作業）之間進行，而覆寫則用于同一個程式或程序中。由于覆寫技術要求給出程式段之間的覆寫結構，使得其對使用者和程式員不透明，是以對于主存無法存放使用者程式的沖突，現代作業系統是通過虛拟記憶體技術來解決的，覆寫技術則已成為曆史；而交換技術在現代作業系統中仍具有較強的生命力。
3.3 記憶體連續配置設定管理方式
連續配置設定方式，是指為一個使用者程式配置設定一個連續的記憶體空間。它主要包括單一連續配置設定、固定分區配置設定和動态分區配置設定。
單一連續配置設定
記憶體在此方式下分為系統區和使用者區，系統區僅提供給作業系統使用，通常在低位址部分；使用者區是為使用者提供的、除系統區之外的記憶體空間。這種方式無需進行記憶體保護。
這種方式的優點是簡單、無外部碎片，可以釆用覆寫技術，不需要額外的技術支援。缺點是隻能用于單使用者、單任務的作業系統中，有内部碎片，存儲器的使用率極低。
固定分區配置設定
固定分區配置設定是最簡單的一種多道程式存儲管理方式，它将使用者記憶體空間劃分為若幹個固定大小的區域，每個分區隻裝入一道作業。當有空閑分區時，便可以再從外存的後備作業隊列中,選擇适當大小的作業裝入該分區，如此循環。
圖3-4 固定分區配置設定的兩種方法
固定分區配置設定在劃分分區時，有兩種不同的方法，如圖3-4所示。
- 分區大小相等：用于利用一台計算機去控制多個相同對象的場合，缺乏靈活性。
- 分區大小不等：劃分為含有多個較小的分區、适量的中等分區及少量的大分區。
為便于記憶體配置設定，通常将分區按大小排隊，并為之建立一張分區說明表，其中各表項包括每個分區的起始位址、大小及狀态（是否已配置設定），如圖3-5(a)所示。當有使用者程式要裝入時，便檢索該表，以找到合适的分區給予配置設定并将其狀态置為”已配置設定”；未找到合适分區則拒絕為該使用者程式配置設定記憶體。存儲空間的配置設定情況如圖3-5(b)所示。
這種分區方式存在兩個問題：一是程式可能太大而放不進任何一個分區中，這時使用者不得不使用覆寫技術來使用記憶體空間；二是主存使用率低，當程式小于固定分區大小時，也占用了一個完整的記憶體分區空間，這樣分區内部有空間浪費，這種現象稱為内部碎片。
固定分區是可用于多道程式設計最簡單的存儲配置設定，無外部碎片，但不能實作多程序共享一個主存區，是以存儲空間使用率低。固定分區配置設定很少用于現在通用的作業系統中，但在某些用于控制多個相同對象的控制系統中仍發揮着一定的作用。
圖3-5 固定分區說明表和記憶體配置設定情況
動态分區配置設定
動态分區配置設定又稱為可變分區配置設定，是一種動态劃分記憶體的分區方法。這種分區方法不預先将記憶體劃分，而是在程序裝入記憶體時，根據程序的大小動态地建立分區，并使分區的大小正好适合程序的需要。是以系統中分區的大小和數目是可變的。
圖3-6動态分區
如圖3-6所示，系統有64MB記憶體空間，其中低8MB固定配置設定給作業系統，其餘為使用者可用記憶體。開始時裝入前三個程序，在它們分别配置設定到所需空間後，記憶體隻剩下4MB，程序4無法裝入。在某個時刻，記憶體中沒有一個就緒程序，CPU出現空閑，作業系統就換出程序2，換入程序4。由于程序4比程序2小，這樣在主存中就産生了一個6MB的記憶體塊。之後CPU又出現空閑，而主存無法容納程序2,作業系統就換出程序1，換入程序2。
動态分區在開始配置設定時是很好的，但是之後會導緻記憶體中出現許多小的記憶體塊。随着時間的推移，記憶體中會産生越來越多的碎片（圖3-6中最後的4MB和中間的6MB，且随着程序的換入/換出，很可能會出現更多更小的記憶體塊)，記憶體的使用率随之下降。
這些小的記憶體塊稱為外部碎片，指在所有分區外的存儲空間會變成越來越多的碎片，這與固定分區中的内部碎片正好相對。克服外部碎片可以通過緊湊（Compaction)技術來解決，就是作業系統不時地對程序進行移動和整理。但是這需要動态重定位寄存器的支援，且相對費時。緊湊的過程實際上類似于Windows系統中的磁盤整理程式，隻不過後者是對外存空間的緊湊。
在程序裝入或換入主存時，如果記憶體中有多個足夠大的空閑塊，作業系統必須确定配置設定哪個記憶體塊給程序使用，這就是動态分區的配置設定政策，考慮以下幾種算法：
- 首次适應(First Fit)算法：空閑分區以位址遞增的次序連結。配置設定記憶體時順序查找，找到大小能滿足要求的第一個空閑分區。
- 最佳适應(Best Fit)算法：空閑分區按容量遞增形成分區鍊，找到第一個能滿足要求的空閑分區。
- 最壞适應(Worst Fit)算法：又稱最大适應(Largest Fit)算法，空閑分區以容量遞減的次序連結。找到第一個能滿足要求的空閑分區，也就是挑選出最大的分區。
- 鄰近适應(Next Fit)算法：又稱循環首次适應算法，由首次适應算法演變而成。不同之處是配置設定記憶體時從上次查找結束的位置開始繼續查找。
在這幾種方法中，首次适應算法不僅是最簡單的，而且通常也是最好和最快的。在UNIX 系統的最初版本中，就是使用首次适應算法為程序配置設定記憶體空間，其中使用數組的資料結構 (而非連結清單）來實作。不過，首次适應算法會使得記憶體的低位址部分出現很多小的空閑分區，而每次配置設定查找時，都要經過這些分區，是以也增加了查找的開銷。
鄰近适應算法試圖解決這個問題，但實際上，它常常會導緻在記憶體的末尾配置設定空間（因為在一遍掃描中，記憶體前面部分使用後再釋放時，不會參與配置設定)，分裂成小碎片。它通常比首次适應算法的結果要差。
最佳适應算法雖然稱為“最佳”，但是性能通常很差，因為每次最佳的配置設定會留下很小的難以利用的記憶體塊，它會産生最多的外部碎片。
最壞适應算法與最佳适應算法相反，選擇最大的可用塊，這看起來最不容易産生碎片，但是卻把最大的連續記憶體劃分開，會很快導緻沒有可用的大的記憶體塊，是以性能也非常差。
Kunth和Shore分别就前三種方法對記憶體空間的利用情況做了模拟實驗，結果表明：
首次适應算法可能比最佳适應法效果好，而它們兩者一定比最大适應法效果好。另外注意,在算法實作時,配置設定操作中最佳适應法和最大适應法需要對可用塊進行排序或周遊查找，而首次适應法和鄰近适應法隻需要簡單查找；回收操作中，當回收的塊與原來的空閑塊相鄰時（有三種相鄰的情況，比較複雜)，需要将這些塊合并。在算法實作時，使用數組或連結清單進行管理。除了記憶體的使用率，這裡的算法開銷也是作業系統設計需要考慮的一個因素。
表3-1三種記憶體分區管理方式的比較
以上三種記憶體分區管理方法有一共同特點，即使用者程序（或作業）在主存中都是連續存放的。這裡對它們進行比較和總結，見表3-1。
3.4 記憶體非連續配置設定管理方式
非連續配置設定允許一個程式分散地裝入到不相鄰的記憶體分區中，根據分區的大小是否固定分為分頁存儲管理方式和分段存儲管理方式。
分頁存儲管理方式中，又根據運作作業時是否要把作業的所有頁面都裝入記憶體才能運作分為基本分頁存儲管理方式和請求分頁存儲管理方式。下面介紹基本分頁存儲管理方式。
基本分頁存儲管理方式
固定分區會産生内部碎片，動态分區會産生外部碎片，這兩種技術對記憶體的使用率都比較低。我們希望記憶體的使用能盡量避免碎片的産生，這就引入了分頁的思想：把主存空間劃分為大小相等且固定的塊，塊相對較小，作為主存的基本機關。每個程序也以塊為機關進行劃分，程序在執行時，以塊為機關逐個申請主存中的塊空間。
分頁的方法從形式上看，像分區相等的固定分區技術，分頁管理不會産生外部碎片。但它又有本質的不同點：塊的大小相對分區要小很多，而且程序也按照塊進行劃分，程序運作時按塊申請主存可用空間并執行。這樣，程序隻會在為最後一個不完整的塊申請一個主存塊空間時，才産生主存碎片，是以盡管會産生内部碎片，但是這種碎片相對于程序來說也是很小的，每個程序平均隻産生半個塊大小的内部碎片（也稱頁内碎片）。
1) 分頁存儲的幾個基本概念
①頁面和頁面大小。程序中的塊稱為頁(Page)，記憶體中的塊稱為頁框（Page Frame，或頁幀）。外存也以同樣的機關進行劃分，直接稱為塊(Block)。程序在執行時需要申請主存空間，就是要為每個頁面配置設定主存中的可用頁框，這就産生了頁和頁框的一一對應。
為友善位址轉換，頁面大小應是2的整數幂。同時頁面大小應該适中，如果頁面太小，會使程序的頁面數過多，這樣頁表就過長，占用大量記憶體，而且也會增加硬體位址轉換的開銷，降低頁面換入/換出的效率；頁面過大又會使頁内碎片增大，降低記憶體的使用率。是以頁面的大小應該适中，考慮到耷間效率和時間效率的權衡。
②位址結構。分頁存儲管理的邏輯位址結構如圖3-7所示。
圖3-7 分頁存儲管理的位址結構
位址結構包含兩部分：前一部分為頁号P，後一部分為頁内偏移量W。位址長度為32 位，其中011位為頁内位址，即每頁大小為4KB；1231位為頁号，位址空間最多允許有2^20頁。
③頁表。為了便于在記憶體中找到程序的每個頁面所對應的實體塊，系統為每個程序建立一張頁表，記錄頁面在記憶體中對應的實體塊号，頁表一般存放在記憶體中。
在配置了頁表後，程序執行時，通過查找該表，即可找到每頁在記憶體中的實體塊号。可見，頁表的作用是實作從頁号到實體塊号的位址映射，如圖3-8所示。
圖3-8 頁表的作用
2) 基本位址變換機構
位址變換機構的任務是将邏輯位址轉換為記憶體中實體位址，位址變換是借助于頁表實作的。圖3-9給出了分頁存儲管理系統中的位址變換機構。
圖3-9 分頁存儲管理的位址變換機構
在系統中通常設定一個頁表寄存器(PTR)，存放頁表在記憶體的始址F和頁表長度M。程序未執行時，頁表的始址和長度存放在程序控制塊中，當程序執行時，才将頁表始址和長度存入頁表寄存器。設頁面大小為L，邏輯位址A到實體位址E的變換過程如下：
- 計算頁号P(P=A/L)和頁内偏移量W (W=A%L)。
- 比較頁号P和頁表長度M，若P >= M，則産生越界中斷，否則繼續執行。
- 頁表中頁号P對應的頁表項位址 = 頁表起始位址F + 頁号P * 頁表項長度，取出該頁表項内容b，即為實體塊号。
- 計算E=b*L+W，用得到的實體位址E去通路記憶體。
以上整個位址變換過程均是由硬體自動完成的。
例如，若頁面大小L為1K位元組，頁号2對應的實體塊為b=8，計算邏輯位址A=2500 的實體位址E的過程如下：P=2500/1K=2，W=2500%1K=452，查找得到頁号2對應的實體塊的塊号為 8，E=8*1024+452=8644。
下面讨論分頁管理方式存在的兩個主要問題：
- 每次訪存操作都需要進行邏輯位址到實體位址的轉換，位址轉換過程必須足夠快，否則訪存速度會降低；
- 每個程序引入了頁表，用于存儲映射機制，頁表不能太大，否則記憶體使用率會降低。
3) 具有快表的位址變換機構
由上面介紹的位址變換過程可知，若頁表全部放在記憶體中，則存取一個資料或一條指令至少要通路兩次記憶體：一次是通路頁表，确定所存取的資料或指令的實體位址，第二次才根據該位址存取資料或指令。顯然，這種方法比通常執行指令的速度慢了一半。
為此，在位址變換機構中增設了一個具有并行查找能力的高速緩沖存儲器——快表，又稱聯想寄存器(TLB)，用來存放目前通路的若幹頁表項，以加速位址變換的過程。與此對應，主存中的頁表也常稱為慢表，配有快表的位址變換機構如圖3-10所示。
圖3-10 具有快表的位址變換機構
在具有快表的分頁機制中，位址的變換過程：
- CPU給出邏輯位址後，由硬體進行位址轉換并将頁号送入高速緩存寄存器，并将此頁号與快表中的所有頁号進行比較。
- 如果找到比對的頁号，說明所要通路的頁表項在快表中，則直接從中取出該頁對應的頁框号，與頁内偏移量拼接形成實體位址。這樣，存取資料僅一次訪存便可實作。
- 如果沒有找到，則需要通路主存中的頁表，在讀出頁表項後，應同時将其存入快表，以便後面可能的再次通路。但若快表已滿，則必須按照一定的算法對舊的頁表項進行替換。
注意：有些處理機設計為快表和慢表同時查找，如果在快表中查找成功則終止慢表的查找。
一般快表的命中率可以達到90%以上，這樣，分頁帶來的速度損失就降低到10%以下。快表的有效性是基于著名的局部性原理，這在後面的虛拟記憶體中将會具體讨論。
4) 兩級頁表
第二個問題：由于引入了分頁管理，程序在執行時不需要将所有頁調入記憶體頁框中，而隻要将儲存有映射關系的頁表調入記憶體中即可。但是我們仍然需要考慮頁表的大小。
以32 位邏輯位址空間、頁面大小4KB、頁表項大小4B為例，若要實作程序對全部邏輯位址空間的映射，則每個程序需要2^20，約100萬個頁表項。也就是說，每個程序僅頁表這一項就需要4MB主存空間，這顯然是不切實際的。而即便不考慮對全部邏輯位址空間進行映射的情況，一個邏輯位址空間稍大的程序，其頁表大小也可能是過大的。
以一個40MB的程序為例，頁表項共40KB,如果将所有頁表項内容儲存在記憶體中，那麼需要10個記憶體頁框來儲存整個頁表。整個程序大小約為1萬個頁面，而實際執行時隻需要幾十個頁面進入記憶體頁框就可以運作，但如果要求10個頁面大小的頁表必須全部進入記憶體，這相對實際執行時的幾十個程序頁面的大小來說，肯定是降低了記憶體使用率的；從另一方面來說，這10頁的頁表項也并不需要同時儲存在記憶體中，因為大多數情況下，映射所需要的頁表項都在頁表的同一個頁面中。
将頁表映射的思想進一步延伸，就可以得到二級分頁：将頁表的10頁空間也進行位址映射，建立上一級頁表，用于存儲頁表的映射關系。這裡對頁表的10個頁面進行映射隻需要10個頁表項，是以上一級頁表隻需要1頁就足夠（可以存儲2^10=1024個頁表項）。在程序執行時，隻需要将這1頁的上一級頁表調入記憶體即可，程序的頁表和程序本身的頁面，可以在後面的執行中再i周入記憶體。
如圖3-11所示，這是Intel處理器80x86系列的硬體分頁的位址轉換過程。在32位系統中，全部32位邏輯位址空間可以分為220(4GB/4KB)個頁面。這些頁面可以再進一步建立頂級頁表，需要210個頂級頁表項進行索引，這正好是一頁的大小，是以建立二級頁表即可。
圖3-11 硬體分頁位址轉換
舉例，32位系統中程序分頁的工作過程：假定核心已經給一個正在運作的程序配置設定的邏輯位址空間是0x20000000到0x2003FFFF，這個空間由64個頁面組成。在程序運作時，我們不需要知道全部這些頁的頁框的實體位址，很可能其中很多頁還不在主存中。這裡我們隻注意在程序運作到某一頁時，硬體是如何計算得到這一頁的頁框的實體位址即可。現在程序需要讀邏輯位址0x20021406中的位元組内容，這個邏輯位址按如下進行處理：
邏輯位址： 0x20021406 (0010 0000 0000 0010 0001 0100 0000 0110 B)
頂級頁表字段：0x80 (00 1000 0000 B)
二級頁表字段：0x21 (00 0010 0001B)
頁内偏移量字段：0x406 (0100 0000 0110 B)
頂級頁表字段的0x80用于選擇頂級頁表的第0x80表項，此表項指向和該程序的頁相關的二級頁表；二級頁表字段0x21用于選擇二級頁表的第0x21表項，此表項指向包含所需頁的頁框；最後的頁内偏移量字段0x406用于在目标頁框中讀取偏移量為0x406中的位元組。
這是32位系統下比較實際的一個例子。看似較為複雜的例子，有助于比較深入地了解，希望讀者能自己動手計算一遍轉換過程。
建立多級頁表的目的在于建立索引，這樣不用浪費主存空間去存儲無用的頁表項，也不用盲目地順序式查找頁表項，而建立索引的要求是最高一級頁表項不超過一頁的大小。在 64位作業系統中，頁表的劃分則需要重新考慮，這是很多教材和輔導書中的常見題目，但是很多都給出了錯誤的分析，需要注意。
我們假設仍然釆用4KB頁面大小。偏移量字段12位，假設頁表項大小為8B。這樣，其上一級分頁時，每個頁框隻能存儲29(4KB/8B)個頁表項，而不再是210個，是以上一級頁表字段為9位。後面同理繼續分頁。64=12+9+9+9+9+9+7，是以需6級分頁才能實作索引。很多書中仍然按4B頁表項分析，雖然同樣得出6級分頁的結果，但顯然是錯誤的。這裡給出兩個實際的64位作業系統的分頁級别（注意：裡面沒有使用全部64位尋址，不過由于位址位元組對齊的設計考慮，仍然使用8B大小的頁表項），了解了表3-2中的分級方式，相信對多級分頁就非常清楚了。
表3-2 兩種系統的分級方式
基本分段存儲管理方式
分頁管理方式是從計算機的角度考慮設計的，以提高記憶體的使用率，提升計算機的性能, 且分頁通過硬體機制實作，對使用者完全透明；而分段管理方式的提出則是考慮了使用者和程式員，以滿足友善程式設計、資訊保護和共享、動态增長及動态連結等多方面的需要。
1) 分段。
段式管理方式按照使用者程序中的自然段劃分邏輯空間。例如，使用者程序由主程式、兩個子程式、棧和一段資料組成，于是可以把這個使用者程序劃分為5個段，每段從0 開始編址，并配置設定一段連續的位址空間（段内要求連續，段間不要求連續，是以整個作業的位址空間是二維的）。其邏輯位址由段号S與段内偏移量W兩部分組成。
在圖3-12中，段号為16位，段内偏移量為16位，則一個作業最多可有2^16=65536個段，最大段長為64KB。
圖3-12 分段系統中的邏輯位址結構
在頁式系統中，邏輯位址的頁号和頁内偏移量對使用者是透明的，但在段式系統中，段号和段内偏移量必須由使用者顯示提供，在髙級程式設計語言中，這個工作由編譯程式完成。
2) 段表。
每個程序都有一張邏輯空間與記憶體空間映射的段表，其中每一個段表項對應程序的一個段，段表項記錄該段在記憶體中的起始位址和段的長度。段表的内容如圖3-13所示。
圖3-13 段表項
在配置了段表後，執行中的程序可通過查找段表，找到每個段所對應的記憶體區。可見，段表用于實作從邏輯段到實體記憶體區的映射，如圖3-14所示。
圖3-14 利用段表實作位址映射
3) 位址變換機構。
分段系統的位址變換過程如圖3-15所示。為了實作程序從邏輯位址到實體位址的變換功能，在系統中設定了段表寄存器，用于存放段表始址F和段表長度M。其從邏輯位址A到實體位址E之間的位址變換過程如下：
- 從邏輯位址A中取出前幾位為段号S，後幾位為段内偏移量W。
- 比較段号S和段表長度M，若S多M，則産生越界中斷，否則繼續執行。
- 段表中段号S對應的段表項位址 = 段表起始位址F + 段号S * 段表項長度，取出該段表項的前幾位得到段長C。若段内偏移量>=C，則産生越界中斷，否則繼續執行。
- 取出段表項中該段的起始位址b，計算 E = b + W，用得到的實體位址E去通路記憶體。
圖3-15 分段系統的位址變換過程
4) 段的共享與保護。
在分段系統中，段的共享是通過兩個作業的段表中相應表項指向被共享的段的同一個實體副本來實作的。當一個作業正從共享段中讀取資料時，必須防止另一個作業修改此共享段中的資料。不能修改的代碼稱為純代碼或可重入代碼（它不屬于臨界資源)，這樣的代碼和不能修改的資料是可以共享的，而可修改的代碼和資料則不能共享。
與分頁管理類似，分段管理的保護方法主要有兩種：一種是存取控制保護，另一種是位址越界保護。位址越界保護是利用段表寄存器中的段表長度與邏輯位址中的段号比較，若段号大于段表長度則産生越界中斷；再利用段表項中的段長和邏輯位址中的段内位移進行比較，若段内位移大于段長，也會産生越界中斷。
段頁式管理方式
頁式存儲管理能有效地提高記憶體使用率，而分段存儲管理能反映程式的邏輯結構并有利于段的共享。如果将這兩種存儲管理方法結合起來，就形成了段頁式存儲管理方式。
在段頁式系統中，作業的位址空間首先被分成若幹個邏輯段，每段都有自己的段号，然後再将每一段分成若幹個大小固定的頁。對記憶體空間的管理仍然和分頁存儲管理一樣，将其分成若幹個和頁面大小相同的存儲塊，對記憶體的配置設定以存儲塊為機關，如圖3-16所示。
圖3-16 段頁式管理方式
在段頁式系統中，作業的邏輯位址分為三部分：段号、頁号和頁内偏移量，如圖3-17 所示。
圖3-17 段頁式系統的邏輯位址結構
為了實作位址變換，系統為每個程序建立一張段表，而每個分段有一張頁表。段表表項中至少包括段号、頁表長度和頁表起始位址，頁表表項中至少包括頁号和塊号。此外，系統中還應有一個段表寄存器，指出作業的段表起始位址和段表長度。
注意：在一個程序中，段表隻有一個，而頁表可能有多個。
在進行位址變換時，首先通過段表查到頁表起始位址，然後通過頁表找到頁幀号，最後形成實體位址。如圖3-18所示，進行一次通路實際需要三次通路主存，這裡同樣可以使用快表以加快查找速度，其關鍵字由段号、頁号組成，值是對應的頁幀号和保護碼。
圖3-18 段頁式系統的位址變換機構