一、內(nèi)存管理基本概念

• 操作系統(tǒng)對內(nèi)存的劃分和動態(tài)分配，就是內(nèi)存管理的概念。有效的內(nèi)存管理在多道程序設(shè)計中非常重要，不僅方便用戶使用存儲器、提高內(nèi)存利用率，還可以通過虛擬技術(shù)從邏輯上擴(kuò)充存儲器。
• 內(nèi)存管理的功能有：

（1）內(nèi)存空間的分配與回收：由操作系統(tǒng)完成主存儲器空間的分配和管理，使程序員擺脫存儲分配的麻煩，提高編程效率。
（2）地址轉(zhuǎn)換：在多道程序環(huán)境下，程序中的邏輯地址與內(nèi)存中的物理地址不可能一致，因此存儲管理必須提供地址變換功能，把邏輯地址轉(zhuǎn)換成相應(yīng)的物理地址。
（3）內(nèi)存空間的擴(kuò)充：利用虛擬存儲技術(shù)或自動覆蓋技術(shù)，從邏輯上擴(kuò)充內(nèi)存。
（4）存儲保護(hù)：保證各道作業(yè)在各自的存儲空間內(nèi)運行，.互不干擾。

1、程序裝入和鏈接

• 創(chuàng)建進(jìn)程首先要將程序和數(shù)據(jù)裝入內(nèi)存。將用戶源程序變?yōu)榭稍趦?nèi)存中執(zhí)行的程序，通常需要以下幾個步驟：

編譯：由編譯程序?qū)⒂脩粼创a編譯成若干個目標(biāo)模塊。
鏈接：由鏈接程序?qū)⒕幾g后形成的一組目標(biāo)模塊，以及所需庫函數(shù)鏈接在一起，形成一個完整的裝入模塊。
裝入：由裝入程序?qū)⒀b入模塊裝入內(nèi)存運行。

程序裝入和鏈接流程

（1）鏈接：

靜態(tài)鏈接：在程序運行之前，先將各目標(biāo)模塊及它們所需的庫函數(shù)鏈接成一個完整的可執(zhí)行程序，以后不再拆開。
裝入時動態(tài)鏈接：將用戶源程序編譯后所得到的一組目標(biāo)模塊，在裝入內(nèi)存時，釆用邊裝入邊鏈接的鏈接方式。
運行時動態(tài)鏈接：對某些目標(biāo)模塊的鏈接，是在程序執(zhí)行中需要該目標(biāo)模塊時，才對它進(jìn)行的鏈接。其優(yōu)點是便于修改和更新，便于實現(xiàn)對目標(biāo)模塊的共享。

（2）裝入

** 絕對裝入**。在編譯時，如果知道程序?qū)Ⅰv留在內(nèi)存的某個位置，編譯程序?qū)a(chǎn)生絕對地址的目標(biāo)代碼。絕對裝入程序按照裝入模塊中的地址，將程序和數(shù)據(jù)裝入內(nèi)存。由于程序中的邏輯地址與實際內(nèi)存地址完全相同，故不需對程序和數(shù)據(jù)的地址進(jìn)行修改。
可重定位裝入。在多道程序環(huán)境下，多個目標(biāo)模塊的起始地址通常都是從0開始，程序中的其他地址都是相對于起始地址的,此時應(yīng)釆用可重定位裝入方式。根據(jù)內(nèi)存的當(dāng)前情況，將裝入模塊裝入到內(nèi)存的適當(dāng)位置。裝入時對目標(biāo)程序中指令和數(shù)據(jù)的修改過程稱為重定位，地址變換通常是在裝入時一次完成的，所以又稱為靜態(tài)重定位
動態(tài)運行時裝入，也稱為動態(tài)重定位，程序在內(nèi)存中如果發(fā)生移動，就需要釆用動態(tài)的裝入方式。裝入程序在把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中的相對地址轉(zhuǎn)換為絕對地址，而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時才進(jìn)行。因此，裝入內(nèi)存后的所有地址均為相對地址。

2、邏輯地址空間與物理地址空間

邏輯地址：編譯后，每個目標(biāo)模塊都是從0號單元開始編址，稱為該目標(biāo)模塊的相對地址（或邏輯地址)。當(dāng)鏈接程序?qū)⒏鱾€模塊鏈接成一個完整的可執(zhí)行目標(biāo)程序時，鏈接程序順序依次按各個模塊的相對地址構(gòu)成統(tǒng)一的從0號單元開始編址的邏輯地址空間。用戶程序和程序員只需知道邏輯地址，而內(nèi)存管理的具體機制則是完全透明的，它們只有系統(tǒng)編程人員才會涉及。不同進(jìn)程可以有相同的邏輯地址，因為這些相同的邏輯地址可以映射到主存的不同位置。
物理地址：物理地址空間是指內(nèi)存中物理單元的集合，它是地址轉(zhuǎn)換的最終地址，進(jìn)程在運行時執(zhí)行指令和訪問數(shù)據(jù)最后都要通過物理地址從主存中存取。當(dāng)裝入程序?qū)⒖蓤?zhí)行代碼裝入內(nèi)存時，必須通過地址轉(zhuǎn)換將邏輯地址轉(zhuǎn)換成物理地址，這個過程稱為地址重定位。

3、內(nèi)存保護(hù)

• 內(nèi)存分配前，需要保護(hù)操作系統(tǒng)不受用戶進(jìn)程的影響，同時保護(hù)用戶進(jìn)程不受其他用戶進(jìn)程的影響。通過釆用重定位寄存器和界地址寄存器來實現(xiàn)這種保護(hù)。重定位寄存器含最小的物理地址值，界地址寄存器含邏輯地址值。每個邏輯地址值必須小于界地址寄存器；內(nèi)存管理機構(gòu)動態(tài)地將邏輯地址與界地址寄存器進(jìn)行比較，如果未發(fā)生地址越界，則加上重定位寄存器的值后映射成物理地址，再送交內(nèi)存單元

  
  
  重定位和界地址寄存器的硬件支持

二、內(nèi)存覆蓋與內(nèi)存交換

• 覆蓋與交換技術(shù)是在多道程序環(huán)境下用來擴(kuò)充內(nèi)存的兩種方法。
• 交換技術(shù)主要是在不同進(jìn)程（或作業(yè)）之間進(jìn)行，而覆蓋則用于同一個程序或進(jìn)程中。由于覆蓋技術(shù)要求給出程序段之間的覆蓋結(jié)構(gòu)，使得其對用戶和程序員不透明，所以對于主存無法存放用戶程序的矛盾，現(xiàn)代操作系統(tǒng)是通過虛擬內(nèi)存技術(shù)來解決的，覆蓋技術(shù)則已成為歷史；而交換技術(shù)在現(xiàn)代操作系統(tǒng)中仍具有較強的生命力。

1、內(nèi)存覆蓋

• 覆蓋的基本思想是：由于程序運行時并非任何時候都要訪問程序及數(shù)據(jù)的各個部分（尤其是大程序），因此可以把用戶空間分成一個固定區(qū)和若干個覆蓋區(qū)。將經(jīng)?；钴S的部分放在固定區(qū)，其余部分按調(diào)用關(guān)系分段。首先將那些即將要訪問的段放入覆蓋區(qū)，其他段放在外存中，在需要調(diào)用前，系統(tǒng)再將其調(diào)入覆蓋區(qū)，替換覆蓋區(qū)中原有的段

2、內(nèi)存交換

• 交換（對換）的基本思想是，把處于等待狀態(tài)（或在CPU調(diào)度原則下被剝奪運行權(quán)利） 的程序從內(nèi)存移到輔存，把內(nèi)存空間騰出來，這一過程又叫換出；把準(zhǔn)備好競爭CPU運行的程序從輔存移到內(nèi)存，這一過程又稱為換入。（例如，有一個CPU釆用時間片輪轉(zhuǎn)調(diào)度算法的多道程序環(huán)境。時間片到，內(nèi)存管理器將剛剛執(zhí)行過的進(jìn)程換出，將另一進(jìn)程換入到剛剛釋放的內(nèi)存空間中。同時，CPU調(diào)度器可以將時間片分配給其他已在內(nèi)存中的進(jìn)程。每個進(jìn)程用完時間片都與另一進(jìn)程交換。理想情況下，內(nèi)存管理器的交換過程速度足夠快，總有進(jìn)程在內(nèi)存中可以執(zhí)行。
  ）

三、內(nèi)存連續(xù)分配管理方式

• 連續(xù)分配方式，是指為一個用戶程序分配一個連續(xù)的內(nèi)存空間。它主要包括單一連續(xù)分配、固定分區(qū)分配和動態(tài)分區(qū)分配。

  
  
  三種內(nèi)存分配方法比較

四、內(nèi)存非連續(xù)分配管理方式

• 非連續(xù)分配允許一個程序分散地裝入到不相鄰的內(nèi)存分區(qū)中，根據(jù)分區(qū)的大小是否固定分為分頁存儲管理方式和分段存儲管理方式。分頁存儲管理方式中，又根據(jù)運行作業(yè)時是否要把作業(yè)的所有頁面都裝入內(nèi)存才能運行分為基本分頁存儲管理方式和請求分頁存儲管理方式。
• 固定分區(qū)會產(chǎn)生內(nèi)部碎片，動態(tài)分區(qū)會產(chǎn)生外部碎片，這兩種技術(shù)對內(nèi)存的利用率都比較低。我們希望內(nèi)存的使用能盡量避免碎片的產(chǎn)生，這就引入了分頁的思想：把主存空間劃分為大小相等且固定的塊，塊相對較小，作為主存的基本單位。每個進(jìn)程也以塊為單位進(jìn)行劃分，進(jìn)程在執(zhí)行時，以塊為單位逐個申請主存中的塊空間。分頁的方法從形式上看，像分區(qū)相等的固定分區(qū)技術(shù)，分頁管理不會產(chǎn)生外部碎片。但它又有本質(zhì)的不同點：塊的大小相對分區(qū)要小很多，而且進(jìn)程也按照塊進(jìn)行劃分，進(jìn)程運行時按塊申請主存可用空間并執(zhí)行。這樣，進(jìn)程只會在為最后一個不完整的塊申請一個主存塊空間時，才產(chǎn)生主存碎片，所以盡管會產(chǎn)生內(nèi)部碎片，但是這種碎片相對于進(jìn)程來說也是很小的，每個進(jìn)程平均只產(chǎn)生半個塊大小的內(nèi)部碎片（也稱頁內(nèi)碎片）。

1、基本分頁存儲管理方式

（1）分頁存儲的幾個基本概念
①頁面和頁面大小。進(jìn)程中的塊稱為頁(Page)，內(nèi)存中的塊稱為頁框（Page Frame，或頁幀）。外存也以同樣的單位進(jìn)行劃分，直接稱為塊(Block)。進(jìn)程在執(zhí)行時需要申請主存空間，就是要為每個頁面分配主存中的可用頁框，這就產(chǎn)生了頁和頁框的一一對應(yīng)。（為方便地址轉(zhuǎn)換，頁面大小應(yīng)是2的整數(shù)冪。同時頁面大小應(yīng)該適中，如果頁面太小，會使進(jìn)程的頁面數(shù)過多，這樣頁表就過長，占用大量內(nèi)存，而且也會增加硬件地址轉(zhuǎn)換的開銷，降低頁面換入/換出的效率；頁面過大又會使頁內(nèi)碎片增大，降低內(nèi)存的利用率。）
②地址結(jié)構(gòu)。地址結(jié)構(gòu)包含兩部分：前一部分為頁號P，后一部分為頁內(nèi)偏移量W。地址長度為32 位，其中0_{11位為頁內(nèi)地址，即每頁大小為4KB；12}31位為頁號，地址空間最多允許有220頁。
③頁表。為了便于在內(nèi)存中找到進(jìn)程的每個頁面所對應(yīng)的物理塊，系統(tǒng)為每個進(jìn)程建立一張頁表，記錄頁面在內(nèi)存中對應(yīng)的物理塊號，頁表一般存放在內(nèi)存中。

頁表作用

（2）、基本地址變換機構(gòu)

• 地址變換機構(gòu)的任務(wù)是將邏輯地址轉(zhuǎn)換為內(nèi)存中物理地址，地址變換是借助于頁表實現(xiàn)的。
• 在系統(tǒng)中通常設(shè)置一個頁表寄存器(PTR)，存放頁表在內(nèi)存的始址F和頁表長度M。進(jìn)程未執(zhí)行時，頁表的始址和長度存放在進(jìn)程控制塊中，當(dāng)進(jìn)程執(zhí)行時，才將頁表始址和長度存入頁表寄存器。整個地址變換過程均是由硬件自動完成的。
• 需要解決的兩個問題：

• 每次訪存操作都需要進(jìn)行邏輯地址到物理地址的轉(zhuǎn)換，地址轉(zhuǎn)換過程必須足夠快，否則訪存速度會降低；
• 每個進(jìn)程引入了頁表，用于存儲映射機制，頁表不能太大，否則內(nèi)存利用率會降低。

（3）、具有快表的地址變換機構(gòu)

• 若頁表全部放在內(nèi)存中，則存取一個數(shù)據(jù)或一條指令至少要訪問兩次內(nèi)存：一次是訪問頁表，確定所存取的數(shù)據(jù)或指令的物理地址，第二次才根據(jù)該地址存取數(shù)據(jù)或指令。顯然，這種方法比通常執(zhí)行指令的速度慢了一半。為此，在地址變換機構(gòu)中增設(shè)了一個具有并行查找能力的高速緩沖存儲器——快表，又稱聯(lián)想寄存器(TLB)，用來存放當(dāng)前訪問的若干頁表項，以加速地址變換的過程。
• 一般快表的命中率可以達(dá)到90%以上，這樣，分頁帶來的速度損失就降低到10%以下。

（4）、兩級頁表

2、基本分段存儲管理方式

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

（1）分段

• 段式管理方式按照用戶進(jìn)程中的自然段劃分邏輯空間。例如，用戶進(jìn)程由主程序、兩個子程序、棧和一段數(shù)據(jù)組成，于是可以把這個用戶進(jìn)程劃分為5個段，每段從0 開始編址，并分配一段連續(xù)的地址空間（段內(nèi)要求連續(xù)，段間不要求連續(xù)，因此整個作業(yè)的地址空間是二維的）。其邏輯地址由段號S與段內(nèi)偏移量W兩部分組成。
• 一個作業(yè)最多可有216=65536個段，最大段長為64KB。
• 在頁式系統(tǒng)中，邏輯地址的頁號和頁內(nèi)偏移量對用戶是透明的，但在段式系統(tǒng)中，段號和段內(nèi)偏移量必須由用戶顯示提供，在髙級程序設(shè)計語言中，這個工作由編譯程序完成。

（2）段表

• 每個進(jìn)程都有一張邏輯空間與內(nèi)存空間映射的段表，其中每一個段表項對應(yīng)進(jìn)程的一個段，段表項記錄該段在內(nèi)存中的起始地址和段的長度。在配置了段表后，執(zhí)行中的進(jìn)程可通過查找段表，找到每個段所對應(yīng)的內(nèi)存區(qū)?？梢?，段表用于實現(xiàn)從邏輯段到物理內(nèi)存區(qū)的映射。

（3）地址變換機構(gòu)

• 為了實現(xiàn)進(jìn)程從邏輯地址到物理地址的變換功能，在系統(tǒng)中設(shè)置了段表寄存器，用于存放段表始址F和段表長度M。

（4） 段的共享與保護(hù)

• 在分段系統(tǒng)中，段的共享是通過兩個作業(yè)的段表中相應(yīng)表項指向被共享的段的同一個物理副本來實現(xiàn)的。不能修改的代碼稱為純代碼或可重入代碼（它不屬于臨界資源)，這樣的代碼和不能修改的數(shù)據(jù)是可以共享的，而可修改的代碼和數(shù)據(jù)則不能共享。
• 與分頁管理類似，分段管理的保護(hù)方法主要有兩種：一種是存取控制保護(hù)，另一種是地址越界保護(hù)。

3、段頁式存儲管理方式

• 頁式存儲管理能有效地提高內(nèi)存利用率，而分段存儲管理能反映程序的邏輯結(jié)構(gòu)并有利于段的共享。如果將這兩種存儲管理方法結(jié)合起來，就形成了段頁式存儲管理方式。
• 在段頁式系統(tǒng)中，作業(yè)的地址空間首先被分成若干個邏輯段，每段都有自己的段號，然后再將每一段分成若干個大小固定的頁。對內(nèi)存空間的管理仍然和分頁存儲管理一樣，將其分成若干個和頁面大小相同的存儲塊，對內(nèi)存的分配以存儲塊為單位。

在一個進(jìn)程中，段表只有一個，而頁表可能有多個。

段頁式管理方式