第4章內存管理【教學要求】·

熟悉存儲管理目的和功能，掌握地址重定位的概念?！?/p>

熟悉單一連續分配、固定分區、可變分區實現原理，掌握可變分區分配的數據結構和分配回收算法?！?/p>

熟悉覆蓋與交換的概念?！?/p>

熟練掌握分頁存儲管理原理，熟練掌握基本的地址變換機構和具有快表的地址變換機構?！?/p>

掌握虛擬存儲器的理論基礎和定義，熟悉虛擬存儲器實現方式和特征?！?/p>

掌握請求分頁的頁表機制、缺頁中斷機構和地址變換機構，熟悉頁面的分配和置換策略、頁面的分配的算法?！?/p>

熟練掌握最佳置換算法、先進先出（FIFO）置換算法、最近最少使用置換算法LRU、最近未使用算法NUR、和最優置換算法OPT；掌握有效訪問時間、缺頁率的計算·

熟悉工作集概念?！?/p>

掌握請求分段的段表機制、缺段中斷機構和地址變換機構，熟悉分段的共享和保護。·

掌握分段存儲管理原理和分段地址變換機構，掌握分頁和分段比較，熟悉分頁和分段的共享，掌握段頁式存儲管理原理和地址變換機構。4.1內存管理功能4.2分區管理4.3頁式管理4.4段式管理4.5段頁式管理

3/8/2023第4章內存管理4.1內存管理的功能

●內存空間的分配和回收●地址轉換●內存空間的共享和保護●內存空間的邏輯擴充3/8/2023第4章內存管理4.1.1內存的分配與回收內存分配按分配時機的不同，可分為三種方式：1.直接分配這種方式是指程序員采用物理內存地址編寫程序。使用這種方式，必須事先劃定內存的使用空間，因此，這種方式下的內存利用率不高，用戶使用較困難。2.靜態分配指內存分配是在作業運行之前各目標模塊連接后，把整個作業一次性全部裝入內存，并在作業的整個運行過程中，不允許作業再申請其他內存，或在內存中移動位置。也就是說，內存分配是在作業運行前一次性完成的。

3.動態分配作業要求的基本內存空間是在目標模塊裝入內存時分配的，但在作業運行過程中，允許作業申請附加的內存空間，或是在內存中移動，即分配工作可以在作業運行前及運行過程中逐步完成。3/8/2023第4章內存管理4.1.2地址轉換把用戶程序裝入內存時對有關指令的地址部分的修改定義為從程序地址到內存地址的地址轉換，或稱為地址重定位。1.物理地址與邏輯地址

物理地址也稱內存地址，它是用于唯一標識一個內存單元的編號。所有的物理地址構成了物理空間。

邏輯地址也稱程序地址，它是指在源程序經過匯編或編譯后形成的目標代碼中，用于反映目標代碼中指令或數據的相對位置關系的地址。邏輯地址都是以“0”為基址順序進行編址的，這樣生成的目標程序占據一定的地址空間，稱為程序的邏輯地址空間，簡稱邏輯空間。用符號地址（符號名）表示的程序空間稱為名空間。

地址重定位的原因是因為程序在裝入內存后，其邏輯地址和內存地址不一致。3/8/2023第4章內存管理地址映射LoadA2003456。。1200物理地址空間LoadAdata1data13456源程序LoadA20034560100200編譯連接邏輯地址空間BA=1000（名空間）3/8/2023第4章內存管理2.地址重定位的方式●靜態重定位是在程序執行之前由操作系統的連接裝入程序完成地址轉換

優點：不需要硬件的支持。

缺點：程序必須占用連續的內存空間；一旦程序裝入后不能移動。

●動態重定位

是在程序執行期間進行的地址轉換，是由專門的硬件機構來完成的。

優點：程序占用的內存空間是動態可變的，當程序從某個存儲區移到另一個區域時，只需要修改相應的寄存器BR的內容即可。缺點：需要硬件的支持；實現存儲管理的軟件算法較為復雜。3/8/2023第4章內存管理03456......LOADA200......0100200300.........LOADA2003456110012001300200VR+1000BR動態重定位示意圖3/8/2023第4章內存管理4.1.3內存的保護1.上、下界存儲保護：系統可為每個作業設置一對上、下界寄存器，分別用來存放當前運行作業在內存空間的上、下邊界地址，用它們來限制用戶程序的活動范圍。

2.基址－限長存儲保護：上、下界保護的一個變種是采用基址—限長存儲保護。

3/8/2023第4章內存管理4.1.4內存空間的邏輯擴充

對內存進行邏輯上的擴充，現在普遍采用覆蓋、交換和虛擬存儲器技術。

虛擬存儲器是具有請求調入功能和置換功能，能僅把作業的一部分裝入內存便可運行作業的存儲器系統，它是一種能從邏輯上對內存容量進行擴充的虛構的存儲器系統。虛擬存儲器的理論基礎是程序的局部性原理。包括時間局部性和空間局部性。虛擬存儲器的基本思想是把有限的內存空間與大容量的外存統一管理，構成一個遠大于實際內存的、虛擬的存儲器。此時，外存是作為內存的直接延伸，用戶并不會感覺到內、外存的區別，即把兩級存儲器當作一級存儲器來看待。一個作業運行時，其全部信息裝入虛存，實際上可能只有當前運行的必需一部分信息存入內存，其他則存于外存，當所訪問的信息不在內存時，系統自動將其從外存調入內存。3/8/2023第4章內存管理4.2.1單分區管理4.2.2固定分區4.2.3可變分區4.2.4覆蓋與交換4.2分區管理3/8/2023第4章內存管理4.2.1單分區管理

這是一種最簡單的連續存儲管理方式。但只能用于單用戶、單任務的操作系統中?！裣到y區:僅提供給操作系統使用，通常設置在內存的低址部分；●用戶區:指除系統區以外的全部內存空間，提供給用戶使用?！窨臻e區:指剩余部分存儲區。3/8/2023第4章內存管理4.2.2固定分區

把可用空間劃分成若干個固定大小的存儲區，除操作系統占用一個區域外，其余區域為系統中多個用戶共享，因為在系統運行期間，分區大小、數目都不變，所以固定分區也稱為靜態分區。3/8/2023第4章內存管理分區說明表3/8/2023第4章內存管理4.2.3可變分區

分區大小、數目可變，所以可變分區也稱為動態分區?？勺兎謪^內存使用情況示意圖3/8/2023第4章內存管理1．空閑分區的組織形式

空閑(自由)區表、空閑(自由)區鏈、空閑(自由)區隊列3/8/2023第4章內存管理2．內存的分配與回收

當某一個用戶作業完成釋放所占分區時，系統應進行回收。在可變式分區中，應該檢查回收區與內存中前后空閑區是否相鄰，若相鄰，則應進行合并，形成一個較大的空閑區，并對相應的鏈表指針進行修改；若不相鄰，應將空閑區插入到空閑區鏈表的適當位置。3/8/2023第4章內存管理●首次適應算法

按空閑區地址遞增的次序分配●最佳適應算法

按空閑區由小到大的次序分配●最壞適應算法

按空閑區由大到小的次序分配3．內存的分配算法

3/8/2023第4章內存管理例：有作業序列：作業A要求18K；作業B要求25K，作業C要求30K。系統中空閑區按三種算法組成的空閑區隊列如下，經分析可知：最佳適應法對這個作業序列是合適的，而其它兩種對該作業序列是不合適的。3/8/2023第4章內存管理3/8/2023第4章內存管理有作業序列：作業A要求21K；作業B要求30K，作業C要求25K。課堂練習3/8/2023第4章內存管理4.2.4覆蓋與交換1.覆蓋把程序劃分為若干個功能上相對獨立的程序段，按照其自身的邏輯結構將那些不會同時執行的程序段共享同一塊內存區域。程序段先保存在磁盤上，當有關程序段的前一部分執行結束，把后續程序段調入內存，覆蓋前面的程序段（內存“擴大”了）覆蓋：一個作業的若干程序段，或幾個作業的某些部分共享某一個存儲空間一般要求作業各模塊之間有明確的調用結構，程序員要向系統指明覆蓋結構，然后由由操作系統完成自動覆蓋。3/8/2023第4章內存管理A8KE4KF10KC10KB8KD12K作業X的調用結構作業X的常駐區

A（8K）覆蓋區0（10K）覆蓋區1（12K）BCDEF3/8/2023第4章內存管理為什么引入交換技術？當內存空間緊張時，系統將內存中某些進程暫時移到外存，把外存中某些進程換進內存，占據前者所占用的區域，這種技術是進程在內存與外存之間的動態調度。多用于分時系統中與覆蓋技術相比，交換技術不要求用戶給出程序段之間的邏輯覆蓋結構；交換發生在進程或作業之間，而覆蓋發生在同一進程或作業內。覆蓋只能覆蓋那些與覆蓋段無關的程序段2.交換3/8/2023第4章內存管理4.3頁式管理

4.3.1頁式管理概述1.基本原理：分頁存儲管理是將一個進程的地址空間劃分成若干個大小相等的區域，稱為頁。相應地，將內存空間劃分成與頁相同大小的若干個物理塊，稱為塊或頁幀。在為進程分配內存時，將進程中若干頁分別裝入多個不相鄰接的塊中。2.地址結構：分頁系統的地址結構由兩部分組成：前一部分為頁號P；后一部分為位移量W，即頁內位移。在下圖中地址為32位，其中0～11位為頁內位移（每頁的大小為4K），12～31位為頁號，所以允許地址空間的大小最多為1M個頁。

3/8/2023第4章內存管理地址結構示例3112110

頁號P

位移量W3/8/2023第4章內存管理4.3.2靜態分頁

1.基本思想：必須裝入作業的全部頁面后才能執行該作業。

2.地址轉換：系統為每個進程建立了一張頁面映射表，簡稱頁表。每個頁在頁表中占一個表項，記錄該頁在內存中對應的物理塊號。進程在執行時，通過查找頁表，就可以找到每頁所對應的物理塊號。頁表的作用是實現從頁號到物理塊號的地址映射。3/8/2023第4章內存管理頁號塊號021328頁表3/8/2023第4章內存管理3/8/2023第4章內存管理頁表始址頁表長度頁表寄存器頁號P頁內地址W邏輯地址越界中斷＞塊號p`塊內地址W物理地址頁表頁號塊號頁號P塊號p`＋分頁中的地址轉換機構3/8/2023第4章內存管理例：設頁長為1K，程序地址字長為16位，作業2空間和頁表如下圖所示。

移3/8/2023第4章內存管理p’頁表地址越界

L比較P>=Lpp’...快表

b+頁號p

頁內地址dP’d物理地址頁表地址寄存器頁表長度寄存器邏輯地址3.快表與聯想存儲器3/8/2023第4章內存管理4.二級頁表頁目錄地址目錄位移頁表位移頁位移虛擬地址頁表地址...頁目錄(每進程一個)塊號...頁表代碼或數據...內存塊++3/8/2023第4章內存管理3/8/2023第4章內存管理5.多級頁表對于32位的機器，采用兩級頁表結構是合適的；但對于64位的機器，如果頁面大小仍采用4KB即212

B，那么還剩下52位，假定仍按物理塊的大小(212位)來劃分頁表，則將余下的42位用于外層頁號。此時在外層頁表中可能有4096G個頁表項，要占用16384GB的連續內存空間。必須采用多級頁表，將外層頁表再進行分頁，也是將各分頁離散地裝入到不相鄰接的物理塊中，再利用第2級的外層頁表來映射它們之間的關系。對于64位的計算機，如果要求它能支持2６４(=1844744TB)規模的物理存儲空間，則即使是采用三級頁表結構也是難以辦到的；而在當前的實際應用中也無此必要。3/8/2023第4章內存管理多級頁表的地址轉換3/8/2023第4章內存管理4.3.3動態分頁(請求分頁)

1.基本思想：采用虛擬存儲技術，只需裝入作業的部分頁面就能啟動作業的運行。以后再通過調頁功能和頁面置換功能，陸續把將要運行的頁面調入內存，同時把暫不運行的頁面置換到外存上，置換時以頁面為單位。

3/8/2023第4章內存管理2.頁表結構頁號塊號狀態位訪問位修改位外存地址010110

120114100

1232151201343－0－－1353/8/2023第4章內存管理3.缺頁中斷

在請求分頁系統中，每當所要訪問的頁面不在內存時，便要產生一缺頁中斷，請求OS將所缺頁調入內存。與一般中斷的主要區別在于：●缺頁中斷在指令執行期間產生和處理中斷信號，而一般中斷在一條指令執行完后檢查和處理中斷信號。

●缺頁中斷返回到該指令的開始重新執行該指令，而一般中斷返回到該指令的下一條指令執行。

●一條指令在執行期間，可能產生多次缺頁中斷。

3/8/2023第4章內存管理4.地址變換機構 請求分頁系統中的地址變換機構，是在分頁系統的地址變換機構的基礎上，再為實現虛擬存儲器而增加了某些功能所形成的，如產生和處理缺頁中斷，以及從內存中換出一頁的功能等等。3/8/2023第4章內存管理5.頁面置換算法●最優置換算法（OPT算法）從內存中移出以后不再使用的頁面；如無這樣的頁面，則選擇以后最長時間內不需要訪問的頁。這就是最優算法的思想。這種算法本身不是一種實際的方法，因為頁面訪問的順序是很難預知的?！裣冗M先出算法（FIFO算法）

總是先淘汰那些駐留在內存時間最長的頁面，即先進入內存的頁面先被置換掉。理由是：最先進入內存的頁面不再被訪問的可能性最大。

3/8/2023第4章內存管理●最近最少使用算法（LRU算法）當需要置換一頁時，選擇在最近一段時間最少使用的頁面予以淘汰。近似算法：最近最久未使用算法。3/8/2023第4章內存管理OPT算法性能分析（M=3）時刻0123456789101112頁面123412512345塊11111133塊2222224塊334555缺頁√√√√√√√缺頁率＝7/123/8/2023第4章內存管理FIFO算法性能分析（m=3）時刻0123456789101112頁面123412512345塊1123412534塊212341253塊31234125缺頁√√√√√√√√√缺頁率＝9/123/8/2023第4章內存管理LRU算法性能分析（M=3）時刻0123456789101112頁面123412512345塊11114445333塊2222111144塊333322225缺頁√√√√√√√√√√缺頁率＝10/123/8/2023第4章內存管理4.4段式管理4.4.1分段管理的基本思想1、用戶程序劃分按程序自身的邏輯關系劃分為若干個程序段，每個程序段都有一個段名，且有一個段號。段號從0開始，每一段段內也從0開始編址，段內地址是連續的3/8/2023第4章內存管理3、內存分配以段為單位分配內存，每一個段在內存中占據連續空間（內存隨機分割，需要多少分配多少），但各段之間可以不連續存放段號段內地址2、邏輯地址結構3/8/2023第4章內存管