1/19第七章內存管理內存管理的功能程序的加載和鏈接連續分配方式基本分頁分配方式基本分段分配方式虛擬頁式分配頁面置換算法虛擬段式分配段頁式分配方式2/197.1內存管理的功能 存儲管理主要是對主存的管理。不論何種操作系統的存儲管理都必須能夠實現內存分配、地址變換、存儲保護、存儲共享和存儲擴充等功能。3/197.1.1內存分配直接指定方式：編寫程序時確定地址靜態分配方式：程序裝入內存時確定地址動態分配方式：程序執行時確定地址4/197.1.2地址變換地址空間：程序編譯時還沒有裝入主存，還不能確定它在主存中的實際位置，所以都是從０開始。相對于０位置開始的地址稱為邏輯地址，也稱為相對地址。地址空間是指邏輯地址的集合。

存儲空間：一個程序在主存中的實際位置稱為物理地址。物理地址的集合就是存儲空間。5/197.1.2地址變換地址轉換：作業邏輯地址到物理地址的轉換，又稱為重定位。

目標程序地址空間0n目標程序主存的存儲空間0K+nK圖7.1一個作業的地址空間和存儲空間6/197.1.3

存儲保護

地址保護

：一個進程不能跳到另一個進程地址上去執行。權限保護：對于不同的進程有不同的存取權限，確保不能越權執行。7/197.1.4存儲共享

任何保護機制必須具有一定的靈活性，以允許多個進程訪問主存的同一部分。例如，許多進程正在執行同一個程序，則允許每個進程訪問該程序的同一個副本要比讓每個進程有自己單獨的副本更具優勢。合作完成同一個任務的進程可能需要共享訪問同一個數據結構。因此內存管理系統必須允許對內存共享區域進行受控訪問，而不會損害基本的保護。

8/197.1.5存儲擴充

請求調入功能：把程序的一部分裝入內存，使其先運行，在運行的過程中隨時請求操作系統把需要的部分調入內存。

置換功能：把不需要的部分換出主存，以裝載需要的部分。9/197.2程序的加載和鏈接

源模塊1目標模塊1源模塊2目標模塊2源模塊n

目標模塊n

……加載模塊（在外存）

加載模塊（在內存）

編譯

鏈接

加載

運行

圖7.2程序轉換

10/197.2.1程序的加載

絕對裝入方式:在編譯時，如果知道程序將駐留在內存的什么位置，那么，編譯程序將產生絕對地址的目標代碼。絕對裝入程序按照裝入模塊中的地址，將程序和數據裝入內存。裝入模塊被裝入內存后，由于程序中的邏輯地址與實際內存中的地址完全相同，故不需對程序和數據的地址進行修改。

11/197.2.1程序的加載可重定位方式：0LOAD1，250036510002500500010000LOAD1，2500365110001250015000……作業地址空間物理地址空間12/197.2.1程序的加載動態運行時裝入方式：在把裝入模塊裝入到內存后，并不立即把裝入模塊中的相對地址轉換成絕對地址，而是把這種地址轉換推遲到程序真正執行時才進行。因此，裝入內存后的所有地址都仍然是相對地址。

13/197.2.2程序的鏈接

模塊A調用B；返回模塊B調用C；返回模塊C返回模塊B的外部引用長度L長度M長度N模塊AJSR“L”返回模塊BJSR“L+M”返回模塊C返回相對地址0L-1LL+M-1L+ML+M+N-1（a）目標模塊（b）加載模塊14/197.2.2程序的鏈接鏈接編輯程序：靜態鏈接動態鏈接器：動態鏈接

15/197.3連續分配方式

連續分配方式指的是為一個用戶程序劃分連續的內存空間，這種分配方式廣泛應用于20世紀60~70年代，它至今在內存分配方式中還占有一席之地。我們又可以把連續分配方式進一步分為單一連續分配、固定分區分配、動態分區分配和可重定位分區分配四種方式。16/197.3.1單一連續分配

位于ROM中操作系統用戶程序（a）（b）位于RAM中的操作系統ROM中的設備驅動程序用戶程序位于RAM中的操作系統（c）用戶程序17/197.3.2固定分區分配

把內存空間劃分為多個分區，這些分區的大小在操作系統初始化的時候就確定了，并且運行時不會改變，這種機制稱為固定分區分配。劃分分區的方法：分區大小相同分區大小不同18/197.3.2固定分區分配內存管理:分區號起始地址長度狀態進程名內存管理：設置內存分配表內存分配：每個區分配一個進程內存回收：簡單缺點：內存利用率不高如何記錄系統的狀況呢？19/197.3.2固定分區分配分配策略

分區4分區3分區2分區1操作系統0100K200K400K700K800K多個輸入隊列分區4分區3分區2分區1操作系統0100K200K400K700K800K單個輸入隊列（a）有若干獨立輸入隊列的固定式分區（b）只有單個輸入隊列的固定式分區20/197.3.3動態分區分配

事先不劃定分區的大小，根據進程的大小動態的為之分配內存空間。

A操作系統ABA操作系統BC操作系統BCD操作系統BCD操作系統CD操作系統EC（a）（b）（c）（d）（e）（f）（g）內存分配情況隨著進程進出內存而變化，陰影表示的區域是未使用的內存操作系統21/197.3.3動態分區分配內存管理：空閑分區表：在系統中設置一張空閑分區表，記錄每個空閑分區的情況，每個空閑分區占有一個表目。空閑分區鏈：在每個分區的起始部分，設置一些用于控制分區的信息，以及用于鏈接各分區所用的前向指針；在分區尾部則設置一后向指針，通過前后向鏈接指針，可以將所有的空閑分區鏈接成一個雙向鏈。22/197.3.3動態分區分配分配策略首次適應算法（First-Fit）下次適應算法（Next-Fit）最佳適應算法（Best-Fit）最壞適應算法（Worst-Fit）

23/197.3.3動態分區分配空閑區表始址長度標志15K23K未分配48K6K未分配60K15K未分配80K130K0K15K38K48K75K80K210K220K54K60K作業序列：

P1，3K、 P2，20K、 P3，10K、 P4，100K。24/197.3.4可重定位分區分配

內存緊湊：把系統中小的、離散的分區合并成一個大的分區的過程。操作系統用戶程序1用戶程序5用戶程序3用戶程序816K24K30K8K操作系統用戶程序1用戶程序5用戶程序3用戶程序878K操作系統用戶程序1用戶程序5用戶程序3用戶程序816K62K（a）初始狀態（b）完全緊湊（c）部分緊湊25/197.3.4可重定位分區分配重定位：邏輯地址

物理地址靜態重定位：在程序被加載到內存之前已經知道了它將要加載到內存的開始地址，這樣就可以事先進行地址轉換，把相對地址轉換成絕對地址。

動態重定位：作業裝入內存后所有的地址仍然是相對地址，將相對地址轉換成絕對地址的過程被推遲到程序指令要真正執行時進行。26/197.3.4可重定位分區分配…LOADA200…3465…02001002003001000+…LOADA200…3465…0110012001300…邏輯地址空間物理地址空間重定位寄存器動態重定位示意圖相對地址27/197.3.5交換和覆蓋

交換：把內存中暫時不用的程序和數據換出到外存上，以釋放內存空間，當換到外存的數據再次使用時，再把它們換入內存。

覆蓋：是指把程序劃分成若干個功能相對獨立的程序段，按照其自身的邏輯結構將那些不會同時執行的程序段共享同一塊內存區域。

28/197.3.5交換和覆蓋A（8K）B（8K）C（10K）D（12K）E（4K）F（10K）ABABDACEACF（a）函數調用結構（b）地址分配圖7.10程序覆蓋29/197.4基本分頁分配方式

分區分配方式有很多不足，首先會產生很多碎片，其次要求一段較大并且連續的空間。

針對分區分配的不足，提出把作業離散分配到內存中的思想。30/197.4.1頁面與頁表

頁面：分頁存儲管理是將作業的邏輯地址劃分成一系列同等大小的部分，稱為頁。把可用的物理內存也劃分成同樣大小的連續的部分，稱之為塊或頁框。在為進程分配內存空間時，以頁為單位，每個內存中的塊存放一頁用戶作業。31/197.4.1頁面與頁表0123456作業的地址空間內存01234567891011121332/197.4.1頁面與頁表地址結構：頁號p偏移量w頁號p偏移量w22位10位20位12位0910310111231（b）頁面大小為4K（a）頁面大小為1K33/197.4.1頁面與頁表頁表

0123456作業的地址空間塊號頁號頁表內存012345601234567891011121311289541334/197.4.2地址變換機構

基本地址變換

Load1,2500100Load1,2500100用戶空間內存空間35/197.4.2地址變換機構

基本地址變換

頁號p頁內偏移量w頁表始址頁表長度邏輯地址A越界中斷+1n0123頁表頁號塊號塊號塊內偏移量圖7.13頁式存儲的地址變換機構>=36/197.4.2地址變換機構 一分頁系統，頁架的大小為1KB，邏輯地址為4101（十進制數）頁表如下：

要求把邏輯地址轉換成物理地址。012341552039182217請你幫我把邏輯地址3100轉換為物理地址37/197.4.2地址變換機構快表：介于內存與寄存器之間的存儲機制用來保存正在運行進程的頁表的子集p’頁表地址越界

l比較P>=lpp’...快表

b+頁號p頁內地址dP’d物理地址頁表地址寄存器頁表長度寄存器邏輯地址38/197.4.2地址變換機構多級頁表

0111221外層頁內地址頁內位移量外層頁號2231外部頁表第1頁頁表頁表內存012…0123…115116146831115………第n頁頁表012…21161468…0n…3115…39/197.4.2地址變換機構外層頁號內層頁號偏移量0122231PTBR有位，二級地址有位，頁框地址物理頁框號偏移量01231選定的二級頁表一級頁表多級頁表

40/197.4.3頁面大小 假設平均進程大小是s字節，頁面大小是p字節，每個頁表項需要e字節。開銷=es/p+p/2 在頁面比較小時，第一項（頁表大小）大，在頁面比較大時，第二項（內碎片大小）大。把上邊公式兩邊對p求導，我們得到如下方程式：-es/p2+1/2=0p=√2es 對于s=128k和每個頁表項e=8個字節，最優頁面大小為1448字節。大部分計算機使用的頁面尺寸在512字節到64K之間。41/197.5基本分段分配方式

引入分段的必要性：邏輯上完整動態增長動態鏈接信息共享信息保護42/197.5.1段表

分段管理邏輯地址結構

段表0151631段號段內地址段號012段首址段長度58K20K100K110K260K140K43/197.5.1段表作業空間（MAIN），0030K00020K10K15K（X），1（D），2（S），3段表30K40K20K80K10K120K15K150K段長基址段號0123內存空間（MAIN），0（X），0（D），0（S），0040K80K120K150K圖7.17段表的作用44/197.5.2地址變換機構

段號段內地址段表始址段表長度邏輯地址A>=越界中斷+1K5002006000123基址段號段長用戶程序8292段式存儲的地址變換機構2100+6K8K92004K45/197.5.3共享與保護

例子：有一個多用戶系統，可以容納40個用戶，他們都執行一個文本編輯程序，如果文本編輯程序有160K的代碼和40K的數據區，則需要：（160+40）*40=8M的內存空間，如果160K的代碼是可重入的，則在內存中只保存一個副本就可以了，則需要：160+40*40=1760K內存空間。46/197.5.3共享與保護進程1頁表ed1ed2…ed40data1data10…ed1ed2…ed40data1data10…2122…606170…2122…607180…進程2頁表ed1ed2…ed40data1data10…主存editordata1data1data10……212260617007180editordata1段長16016040基址8080380editordata1data140240…80420240280380進程1進程2段表（a）分頁系統中共享editor示意圖（b）分段系統中共享editor示意圖分頁與分段分配方式共享代碼段的比較47/197.5.3共享與保護分頁存儲管理和分段存儲管理的主要區別如下：頁是信息的物理單位，段是信息的邏輯單位；頁的大小是固定的，段的長度是不固定的；分頁的地址空間是一維的，分段的地址空間是二維的；頁存在內碎片，段存在外碎片；48/197.6虛擬頁式分配

分頁內存分配和分段內存分配方法可以解決程序在內存中離散存放的問題，但是，這兩種方式都要求程序整個裝入內存。事實上，很多時候，程序本身比內存要大得多，那么簡單的分頁和分段的內存方式就無法解決這個問題了。可以采用虛擬存儲器的方法，使用請求分配和置換策略來實現存儲管理。49/197.6.1虛擬存儲器為什么需要虛擬存儲器：程序大于內存程序暫時不執行或運行完是否還要占用內存程序的局部性原理虛擬存儲器的定義：所謂的虛擬存儲器是指請求調入功能和置換功能，能從邏輯上對內存容量加以擴充的一種存儲器系統。50/197.6.1虛擬存儲器

虛擬存儲器的特點：多次性：一個進程的數據會多次裝入內存。

對換性：允許一個程序在運行過程中從內存換入和換出。

虛擬性：不能改變系統中內存的大小

51/197.6.1虛擬存儲器虛擬存儲器技術需要解決的問題：地址映射

分配策略

置換策略

裝載控制

52/197.6.2請求分頁概念

在進程開始運行之前，不是裝入全部頁面，而是裝入幾個頁面，之后根據進程運行的需要，動態裝入其它頁面；當內存空間已滿，而又需要裝入新的頁面時，則根據某種算法淘汰某個頁面，以便裝入新的頁面。53/197.6.2請求分頁概念XXXX7X5XXX34061260K-64K56K-60K52K-56K48K-52K44K-48K40K-44K36K-40K32K-36K28K-32K24K-28K20K-24K16K-20K12K-16K8K-12K4K-8K0K-4K28K-32K24K-28K20K-24K16K-20K12K-16K8K-12K4K-8K0K-4K虛地址空間物理地址空間}虛頁頁框54/197.6.3請求分頁硬件支持頁表

狀態位：表明該頁是否在內存。

訪問位：根據訪問位來決定淘汰哪頁修改位：查看此頁是否在內存中被修改過頁號物理塊號狀態位訪問位修改位外存地址55/197.6.3請求分頁硬件支持缺頁中斷機構：在請求分頁系統中，要訪問的頁不在內存時，便產生了一個缺頁中斷，請求操作系統將該頁面調入內存。缺頁中斷同其它中斷一樣要經歷CPU環境保護、分析中斷原因、轉入中斷處理程序、恢復CPU環境等步驟。但缺頁中斷又是一種特殊的中斷。這種中斷在指令執行期間產生和處理中斷信號。

56/197.6.3請求分頁硬件支持地址變換機構

01001000110010010000010110111….1111….000001251611101101000110010010狀態位頁號為5偏移量不變邏輯地址物理地址57/197.6.4內存分配策略

內存分配要考慮的問題：分配給一個進程的存儲量越小，在任何時候駐留在內存中的進程數就越多，CPU找到就緒進程的機會就大，從而減少了CPU等待的時間。如果一個進程在內存中的頁面數較少，那么，基于局部性原理，它發生缺頁的可能性仍然很高。給進程分配的物理塊超過一定的數目后，由于局部性原理，給該進程分配更多的物理塊對該進程的缺頁率沒有影響。58/197.6.4內存分配策略缺頁率缺頁率（a）頁尺寸（b）分配的物理塊數PNP表示整個進程的大小，N進程中的總頁數頁面大小與物理塊數對缺頁率的影響59/197.6.4內存分配策略分配策略：固定分配策略

可變分配策略

替換策略局部替換全局替換

A0A1A4A3B0B1B2B3B4C1C2局部置換與全局置換A0A1A2A3B0B1B2B3B4C1C267384632974生存時間（a）置換前（b）局部置換A0A1A2A3B0B1B2A4B4C1C2（c）全局置換60/197.6.4內存分配策略固定分配局部置換

可變分配局部置換

可變分配全局置換

61/197.6.5內存分配方法

平均分配：所有的空閑物理塊按照進程數目平均分配。按進程大小比例分配：考慮優先級的分配算法

P=∑Pini=1bi=PiP×m62/197.6.6缺頁處理

訪問的頁在內存產生缺頁中斷內存中有空塊從外存調入要訪問的頁換出某些暫時不用的頁運行NYNY63/197.7頁面置換算法

當需要的頁不在內存時，操作系統必須從內存中選擇一頁并將其移到外存，然后把需要的頁調入內存。在每次缺頁時，不同的選擇會使系統的效率有很大不同。對頁面置換算法的研究已經非常深入，下面介紹幾個重要的算法。這幾個算法都是采用固定分配局部置換的內存分配策略。64/197.7.1最優頁面置換算法

當發生缺頁時，當前內存中的這幾頁中，有的頁可能以后再也不用了，那么把這個頁置換出去是最好的，如果當前內存中的幾頁都要使用，那么就選擇一個最后用到的頁并把它置換出去。（向后看）

65/197.7.1最優頁面置換算法 假定系統為某進程分配了三個物理塊，進程的頁面走向如下：

7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1 現在分配給該作業的三個物理塊為空，采用OPT算法，置換過程如何呢？66/197.7.1最優頁面置換算法70120304230321201701170127037XXX最佳頁面算法（OPT）67/197.7.2先進先出置換算法

置換最先進入內存的頁先進先出算法（FIFO）70120304230321201701170127037XXX68/197.7.2先進先出置換算法頁面走向物理塊012301401234000012300014411123011142222301444233缺頁YYYYYYYYY頁面走向物理塊0123014012340000000123401111111234012222223401233333401234缺頁YYYYYYYYYY69/197.7.3最近最少使用置換算法

最近最少使用（LRU）置換算法的思想是當發生缺頁時，系統會選擇當前內存頁面中沒有被使用時間最久的那一頁，即最少使用的那一頁，并將它置換出去。

70120304230321201701170127037XXX70/197.7.3最近最少使用置換算法最近最久未用算法（LRU）硬件支持R實頁R7R6R5R4R3R2R1R0101010010210101100300000100401101011511010110600101011700000111801101101移位寄存器R=Rn-1Rn-2Rn-3…R2R1R071/197.7.4用軟件模擬LRU算法

最不常用（NFU）算法：該算法將每個頁面與一個軟件記數器相聯，記數器的初值為0。每次時鐘中斷時，由操作系統掃描內存中的所有的頁面，將每個頁面的R位（它的值是0或1）加到它的記數器上。實際上這個記數器是試圖跟蹤各個頁面的訪問頻繁程度。發生頁面失效時，計數器最小的頁面被淘汰。這樣做有沒有問題呢？ 對NFU進行一個簡單的修改來模擬LRU。首先，在R位被加進來之前先將記數器右移一位；然后將R位加到記