第4章存儲管理

第4章存儲管理

在計算機系統(tǒng)中，內存是關鍵資源，對內存如何處理在很大程度上將影響整個系統(tǒng)的性能。存儲管理目前仍是人們研究操作系統(tǒng)的中心問題之一，甚至操作系統(tǒng)的命名也往往取決于存儲管理的策略。學習目標1、掌握：動態(tài)分區(qū)法，分頁的概念和地址映射，分段的概念；請求分頁存儲管理技術，常用頁面置換算法。

2、理解：重定位、固定分區(qū)法，碎片和抖動。3、了解：存儲器層次；用戶程序地址空間；程序的裝入方式。本章要點●連續(xù)分配存儲管理方式

●段式存儲管理

●頁式存儲管理

●虛擬頁式存儲管理

第4章基本存儲管理4.1地址空間與重定位內存（MainMemory或PrimaryMemory或RealMemory）也稱主存，是指CPU能直接存取指令和數(shù)據(jù)的存儲器。內存在計算機系統(tǒng)中的地位4.1.1用戶程序的地址空間1．存儲器的層次2．用戶程序的地址空間■主要處理階段

編輯編譯連接裝入運行■有關概念●裝入程序——其功能是將程序模塊放入內存，并進行重定位。●相對地址或邏輯地址

●絕對地址或物理地址2．用戶程序的地址空間■程序裝入內存的方式

①絕對裝入方式②可重定位裝入方式③動態(tài)運行時裝入方式4.1.2重定位概念邏輯地址空間（簡稱地址空間）

由程序中邏輯地址組成的地址范圍。內存空間（也稱物理空間或絕對空間）由內存中一系列存儲單元所限定的地址范圍。重定位程序和數(shù)據(jù)裝入內存時，需對目標程序中的地址進行修改。這種把邏輯地址轉變?yōu)閮却嫖锢淼刂返倪^程稱作重定位。重定位方式(1)

靜態(tài)重定位(2)動態(tài)重定位1．靜態(tài)重定位：目標程序裝入內存時進行地址變換程序裝入內存時的情況

靜態(tài)重定位示意圖

1．靜態(tài)重定位

目標程序裝入內存時進行地址變換?！鴥?yōu)點：無需增加硬件地址轉換機構。●主要缺點：位置“釘死”；不便共享。2．動態(tài)重定位：程序執(zhí)行期間進行重定位●主要優(yōu)點：位置可變，不必連續(xù)；易于共享?！饕秉c：需要附加硬件支持。4.1.3對換技術對換兩個進程示意圖

4.1.3對換技術早期的對換技術用于單用戶系統(tǒng)。

●主要優(yōu)點：利用外存來解決內存不足的問題。

▲主要缺點：效率很低；不能保證充分利用內存。在多道程序環(huán)境中也采用對換技術！4.2分區(qū)管理技術4.2.1分區(qū)法分區(qū)分配是為支持多道程序運行而設計的一種最簡單的存儲管理方式。1．固定分區(qū)法分區(qū)個數(shù)固定不變，各個分區(qū)的大小固定不變，不同分區(qū)的大小可以不同。系統(tǒng)建立一張分區(qū)說明表。每個分區(qū)對應表中的一項。各表項包含每個分區(qū)的起始地址、分區(qū)大小以及狀態(tài)（是否正被使用）。▲分區(qū)的申請和釋放

（1）單一分區(qū)存儲管理

單一分區(qū)存儲管理的系統(tǒng)，任何時刻只有一個用戶程序駐留內存。因此內存為兩個部分?！罟┎僮飨到y(tǒng)使用的系統(tǒng)區(qū);☆供用戶程序使用的用戶區(qū)。

(2)用戶區(qū)分為“使用區(qū)”和“空閑區(qū)”兩部分。使用區(qū)是用戶作業(yè)程序真正占用的連續(xù)存儲區(qū)域；空閑區(qū)是分配給了用戶、但未被用戶使用的區(qū)域，稱為“內部碎片”。

單一分區(qū)存儲管理系統(tǒng)的特點：(1)總是把一個連續(xù)的用戶區(qū)分配給一個用戶使用。

(3)這種系統(tǒng)只適用于單用戶的情況。單一分區(qū)存儲管理系統(tǒng)的特點：(4)進入內存的作業(yè)，獨享系統(tǒng)中的所有資源，包括內存中的整個用戶區(qū)。(5)由于整個用戶區(qū)都分配給了一個用戶，因此作業(yè)程序進入用戶區(qū)后，沒有移動的必要。所以采用這種存儲管理策略，對用戶程序實行靜態(tài)重定位。單一分區(qū)存儲管理系統(tǒng)的存儲保護

實行靜態(tài)重定位，不能阻止用戶有意無意地通過不恰當?shù)闹噶铌J入操作系統(tǒng)所占用的存儲區(qū)域。

在單一分區(qū)存儲管理中，為有效阻止用戶程序指令中的地址闖入操作系統(tǒng)所占用的區(qū)域，在CPU中會設置一個用于存儲保護的專用寄存器——“界限寄存器”。

界限寄存器：存放內存用戶區(qū)的起始地址。CPU在用戶態(tài)下工作時，對內存的每一次訪問，都要將所訪問的地址與界限寄存器中的內容進行比較。一旦發(fā)現(xiàn)所訪問的地址小于界限寄存器中的地址，產生“地址越界”中斷，阻止這次訪問的進行。(1)每次只能有一個作業(yè)進入內存，故不適用于多道程序設計，整個系統(tǒng)的工作效率不高，資源利用率低下；單一分區(qū)存儲管理的缺點：(2)只要作業(yè)比用戶區(qū)小，那么在用戶區(qū)里就會形成碎片，如果用戶作業(yè)很小，那么這種浪費是巨大的；(3)若用戶作業(yè)的相對地址空間比用戶區(qū)大，那么該作業(yè)就無法投入運行，因為大作業(yè)無法在小內存上運行。（2）固定分區(qū)存儲管理

系統(tǒng)初啟時將內存劃分成n個分區(qū)（尺寸大小可以不等），系統(tǒng)運行過程中，分區(qū)的個數(shù)及尺寸保持不變，每個分區(qū)里只裝入一個作業(yè)運行。這就是“固定分區(qū)”存儲管理。對作業(yè)的組織

系統(tǒng)可以為每個分區(qū)設置一個后備作業(yè)隊列，形成多隊列的管理方式：對作業(yè)的組織

對作業(yè)的組織

也可采用多個分區(qū)只設置一個后備作業(yè)隊列的辦法。在固定分區(qū)存儲管理中，每個分區(qū)只允許裝入一個作業(yè)，作業(yè)在運行期間不會移動。因此，這時應該對程序實行靜態(tài)重定位。在固定分區(qū)存儲管理中，要防止用戶程序對操作系統(tǒng)形成的侵擾，也要防止用戶程序與用戶程序之間形成的侵擾。因此必須在CPU中設置一對專用的寄存器，用于實現(xiàn)存儲保護。固定分區(qū)管理的地址映射和存儲保護

兩個專用寄存器起名為“基址寄存器”和“界限寄存器”。調度程序調度某個作業(yè)運行時，就把該作業(yè)所在分區(qū)的起始地址裝入基址寄存器，把分區(qū)長度裝入界限寄存器。

固定分區(qū)存儲管理的特點：它是最簡單的、具有“多道”色彩的存儲管理方案。

作業(yè)程序將一次性地全部被裝入到分配給它的連續(xù)分區(qū)里。(3)實行靜態(tài)重定位，在分區(qū)內的程序不能隨意移動，否則運行就會出錯。(4)每個分區(qū)都有可能產生內部碎片，引起內存資源的浪費。(5)如果到達作業(yè)的尺寸比任何一個分區(qū)的長度都大，那么它就無法運行。固定分區(qū)管理示意圖

分區(qū)說明表

分區(qū)的管理動態(tài)分區(qū)存儲管理的基本思想

動態(tài)分區(qū)存儲管理的基本思想是：作業(yè)要求裝入內存時，若內存有足夠的連續(xù)存儲空間供使用，那就依作業(yè)相對地址空間的大小，劃分出一個分區(qū)分配給它。2．動態(tài)分區(qū)法圖（a）表明后備作業(yè)隊列里，作業(yè)A需要內存15KB，作業(yè)B需要20KB，作業(yè)C需要10KB，等等。圖（b）表示系統(tǒng)初啟時的情形，整個系統(tǒng)里沒有作業(yè)運行，用戶區(qū)空閑。圖（c）表示作業(yè)A裝入內存時，為它劃分了尺寸為15KB的分區(qū)。用戶區(qū)被分成兩個分區(qū)，一個是已分配的，一個是空閑區(qū)。圖（d）表示作業(yè)B裝入內存時，為它劃分了尺寸為20KB的分區(qū)，此時的用戶區(qū)被分成了三個分區(qū)；圖（e）表示作業(yè)C裝入內存時，為它劃分了一個尺寸為10KB的分區(qū)，此時的用戶區(qū)被分成了四個分區(qū)。⑴動態(tài)分區(qū)的分配隨著作業(yè)對存儲區(qū)域的不斷申請與釋放，發(fā)展趨勢是：分區(qū)的數(shù)目會逐漸增加，有的分區(qū)尺寸在逐漸減小，甚至有可能出現(xiàn)內存里有空閑區(qū)、但每個都滿足不了作業(yè)程序的要求而無法分配出去的情形。在存儲管理中，把那些無法滿足作業(yè)存儲請求的空閑區(qū)稱為“外部碎片”。動態(tài)分區(qū)存儲管理模式引發(fā)了許多新的問題。只有解決這些問題，動態(tài)分區(qū)存儲管理才能付之以實現(xiàn)。實行動態(tài)分區(qū)存儲管理必須解決的問題：

(1)采用地址動態(tài)重定位技術，使程序能在內存中移動，為空閑區(qū)的合并提供保證。(2)

記住各個分區(qū)的使用情況，當一個分區(qū)被釋放時，能方便地判定它的前、后分區(qū)是否為空閑區(qū)。若是空閑區(qū)，就進行合并，形成一個大的空閑區(qū)。

(3)給出分區(qū)分配算法。●動態(tài)分區(qū)的優(yōu)點

管理方式簡單，所需操作系統(tǒng)軟件和處理開銷都小。▲動態(tài)分區(qū)的缺點

①內存空間利用率不高，碎片嚴重；②活動進程數(shù)目受限；③無法預知所需內存大小。動態(tài)分區(qū)法舉例動態(tài)分區(qū)法舉例（2）數(shù)據(jù)結構常用的數(shù)據(jù)結構形式有以下兩種：

①空閑分區(qū)表⑵數(shù)據(jù)結構②空閑分區(qū)鏈：使用鏈指針把所有的空閑分區(qū)鏈接成一條鏈。（3）動態(tài)分區(qū)管理中空閑區(qū)的合并

內存中一個分區(qū)被釋放時，與它前后相鄰接的分區(qū)會有四種關系，如圖所示。約定：位于一個分區(qū)左邊的分區(qū)，稱為它的“后鄰接”分區(qū)，位于一個分區(qū)右邊的分區(qū)，稱為它的“前鄰接”分區(qū)。（3）動態(tài)分區(qū)管理中空閑區(qū)的合并

圖(a)表示釋放區(qū)的前、后鄰接分區(qū)都是使用區(qū)，不存在合并問題。此時釋放區(qū)形成一個新空閑區(qū)，該空閑區(qū)的起址就是該釋放區(qū)的起址，長度就是該釋放區(qū)的長度。

圖(b)表示釋放區(qū)的前鄰接分區(qū)是空閑區(qū)，后鄰接分區(qū)是使用區(qū)，釋放區(qū)應和前鄰接的空閑區(qū)合并成新的空閑區(qū)，它的起址是該釋放區(qū)的起址，長度是這兩個合并分區(qū)的長度之和。

圖(c)表示釋放區(qū)的前鄰接分區(qū)是使用區(qū)，后鄰接分區(qū)是空閑區(qū)，釋放區(qū)應和后鄰接的空閑區(qū)合并成為新的空閑區(qū)，它的起址是原前鄰接空閑區(qū)的起址，長度是這兩個合并分區(qū)的長度之和。

圖(d)表示釋放區(qū)的前、后鄰接分區(qū)都是空閑區(qū)，釋放區(qū)應該和這兩個鄰接的空閑區(qū)合并成新的空閑區(qū)，它的起址是原后鄰接空閑區(qū)的起址，長度是這三個合并分區(qū)的長度之和。（4）分配算法①最先適應算法（First-fit）空閑表是按地址排列的（即空閑塊地址小的，在表中的序號也小）。②最佳適應算法（Best-fit）空閑表是以空閑分區(qū)的大小為序、按增量形式排列的，即小塊在前，大塊在后。（4）分配算法③循環(huán)適應算法（Next-fit）最先適應算法的變種。它不從空閑表的開頭查找，而從上次找到的可用分區(qū)的下一個空閑分區(qū)開始查找，從中選擇滿足大小要求的第一個空閑分區(qū)。④最壞適應算法（Worst-fit）空閑表是以空閑塊的大小為序，且大塊在前、小塊在后。

（5）硬件支持通常用一對寄存器分別表示用戶進程在內存空間的上界地址值和下界地址值。這對寄存器是所有用戶進程共用的。（6）碎片“碎片”或“零頭”：內存中這種容量太小、無法利用的小分區(qū)。內部碎片：在一個分區(qū)內部出現(xiàn)的碎片（即被浪費的空間），如固定分區(qū)法會產生內部碎片。外部碎片：在所有分區(qū)之外新增的碎片。（7）總結分區(qū)分配的優(yōu)缺點

●主要優(yōu)點：有利于多道程序設計，所需硬件支持很少，管理算法簡單，易于實現(xiàn)。

▲主要缺點：碎片問題嚴重，內存利用率低，不利于大作業(yè)運行，作業(yè)大小受內存總量限制。作業(yè)一次性地全部裝入到內存中；固定分區(qū)實行指令地址的靜態(tài)重定位；動態(tài)分區(qū)實行指令地址的動態(tài)重定位；

4.2.2可重定位分區(qū)分配■緊縮（或拼湊）——移動某些已分配區(qū)的內容，使所有進程的分區(qū)緊挨在一起，而把空閑區(qū)留在另一端。■可重定位分區(qū)法動態(tài)重定位經常是用硬件實現(xiàn)的。緊縮時機 ●釋放所占分區(qū)時 ●分配進程分區(qū)時

動態(tài)重定位分區(qū)分配算法

址可重定位分區(qū)分配中的進程移動■動態(tài)重定位的實現(xiàn)過程動態(tài)重定位經常用硬件實現(xiàn)硬件支持

基址寄存器（下界地址值）限長寄存器（上界地址值=下界+長度）■動態(tài)重定位的實現(xiàn)過程■可重定位分區(qū)法的優(yōu)缺點●優(yōu)點

可以消除碎片，能夠分配更多的分區(qū)，有助于多道程序設計，提高內存的利用率?！秉c

◎緊縮花費了大量CPU時間；

◎當進程大于整個空閑區(qū)時，仍要浪費一定的內存；

◎進程的存儲區(qū)內可能放有從未使用的信息；

◎進程之間無法對信息共享。4.3分頁技術4.3.1分頁的基本概念■分頁存儲管理的基本方法

①邏輯空間分頁——若干大小相等的頁面。②內存空間分塊——又稱內存塊或頁框，由硬件（系統(tǒng)）確定。③邏輯地址表示。

④內存分配原則

⑤設立頁表

⑥建立內存塊表4.3.1分頁的基本概念分頁技術的地址結構示意圖

▲給定的邏輯地址是A，頁面的大小為L，則頁號p和頁內地址d可按下式求得：

p=INT(A/L),

d=AMODL式中，INT是向下整除的函數(shù)，MOD是取余函數(shù)。

④內存分配原則

▲以塊為單位；▲每個頁面對應一個內存塊；▲分配的內存塊可不連續(xù)。分頁存儲管理系統(tǒng)示意圖

⑤設立頁表——系統(tǒng)為每個進程設立一張頁面映像表，簡稱頁表

●實現(xiàn)從頁號到物理塊號的地址映射⑥建立內存塊表整個系統(tǒng)有一個內存塊表。每個內存塊在內存塊表中占一項，表明該塊當前空閑還是已分出去了。內存頁幀使用情況圖(a)內存塊表圖(b)4.3.2分頁系統(tǒng)中的地址映射分頁系統(tǒng)的地址轉換機構▲每個進程平均有半個頁面的內部碎片。4.3.3頁的共享和保護頁面共享共享的方法是使這些相關進程的邏輯空間中的頁指向相同的內存塊（該塊中放有共享程序或數(shù)據(jù)）

★在分頁系統(tǒng)中實現(xiàn)頁的共享比較困難！2.頁面保護（1）利用頁表本身進行保護；（2）設置存取控制位；（3）設置合法標志。4.3.4頁表的構造1．多級頁表

大多數(shù)現(xiàn)代計算機系統(tǒng)都支持非常大的邏輯地址空間，如232～264。在這種情況下，只用一級頁表會使頁表變得非常大。一種方法是利用兩級頁表，即把頁表本身也分頁。

兩級頁表地址結構示意圖兩級頁表結構示意圖

兩級頁表結構的地址轉換2．散列頁表（HashedPageTable）以頁號作為參數(shù)形成散列值。散列表中每一項有一個鏈表，它把有相同散列值的元素鏈接起來。每個鏈表元素由三部分組成：①頁號；②對應的內存塊號；③指向鏈表中下一個元素的指針。散列頁表構成及地址轉換過程

2．散列頁表（HashedPageTable）3．倒置頁表它是按內存塊號排序的，每個內存塊占有一個表項。每個表項包括存放在該內存塊中頁面的虛擬頁號和擁有該頁面的進程標識符。倒置頁表構成及地址轉換過程

4.4分段技術4.4.1分段的基本概念分段地址空間1．分段▲段是一組邏輯信息的集合?！慷味加凶约旱拿?、長度和▲段號。2．程序的地址結構邏輯地址要用兩個成分來表示：

段號：s和段內地址：d進程的邏輯地址空間是二維的。分段技術地址結構示意圖

4.4.1分段的基本概念3．段表和段表地址寄存器系統(tǒng)為每個進程建立一個段映射表，簡稱“段表”。每個段在段表中占有一項，段表項中包含段號、段長和段起始地址（又稱“基址”）等。系統(tǒng)還要建立一個段表地址寄存器。有兩部分：●該段表在內存的起始地址

●該段表的長度。4.4.1分段的基本概念4．分頁和分段的主要區(qū)別①頁是信息的物理單位；

段是信息的邏輯單位。②頁的大小是由系統(tǒng)確定的；

段的長度因段而異。③分頁的進程地址空間是一維的；

分段的進程地址空間是二維的。④分頁系統(tǒng)很難實現(xiàn)過程和數(shù)據(jù)的分離；

分段系統(tǒng)卻可以很容易實現(xiàn)這些功能。4.4.2分段系統(tǒng)中的地址映射分段地址轉換過程

分段地址轉換過程

4.4.3段的共享和保護1．段的共享共享是在段一級實現(xiàn)的，任何共享信息可以單獨成為一段。也可以只共享部分程序。2．段的保護段的保護措施包括以下三種：①存取控制②段表本身可起保護作用

●表項中設置該段的長度限制；

●段表地址寄存器中有段表長度的信息；③保護環(huán)2．段的保護段的保護措施包括以下三種：③保護環(huán)一個程序可以訪問駐留在相同環(huán)或較低特權環(huán)中的數(shù)據(jù)。一個程序可以調用駐留在相同環(huán)或較高特權環(huán)中的服務。環(huán)保護機構

4.5虛擬存儲管理4.5.1虛擬存儲器的概念▲進程在執(zhí)行之前要全部裝入內存，這種限制是不合理的。

①程序中往往含有不會被執(zhí)行的代碼；②分配的內存空間會大于它們的實際需要；③一個程序的某些選項和特性可能很少使用。程序的執(zhí)行過程也顯示出局部性。按需分別調入內存會帶來兩點好處：①用戶編制程序時不必考慮內存容量的限制；②在一定容量的內存中就可同時裝入更多的進程。虛擬存儲器（VirtualMemory）

●用戶能作為可編址內存對待的虛擬存儲空間，它使用戶邏輯存儲器與物理存儲器分離，是操作系統(tǒng)給用戶提供的一個比真實內存空間大得多的地址空間。實現(xiàn)虛擬存儲技術的物質基礎

●二級存儲器結構；

●動態(tài)地址轉換機構（DAT）。虛擬存儲器實質上是把用戶地址空間和實際的存儲空間區(qū)分開來。它主要受到兩方面的限制

①指令中表示地址的字長②外存的容量。4.5.2虛擬存儲器的特征①虛擬擴充；②部分裝入；③離散分配；④多次對換。

4.6請求分頁技術4.6.1請求分頁的基本思想是在單純分頁技術基礎上發(fā)展起來的。二者的根本區(qū)別在于請求分頁提供虛擬存儲器?！锘舅枷耄寒斠粋€進程的部分頁面在內存時就可調度它運行；在運行過程中若用到的頁面尚未在內存，則把它們動態(tài)換入內存?！绻刂忿D換機構遇到一個具有“N”狀態(tài)的頁表項時，便產生一個缺頁中斷。4.6.2硬件支持及缺頁處理1．頁表機制★頁表項不僅要包含該頁在內存的基址，還含有下列信息：

①每一項增加一個狀態(tài)位，指示該頁面是否在內存中。②還要記載該頁面在外存的地址（又稱文件地址）。③在頁表中還要增加一些位，記錄該頁的使用情況。頁表項通常包含下列信息：典型的頁表表項示意圖

頁號物理塊號狀態(tài)位P訪問字段A修改位M外存地址2．缺頁中斷機構指令執(zhí)行步驟與缺頁中斷處理過程

3．頁面置換過程

▲實現(xiàn)請求分頁必須解決內存塊的分配算法和頁面置換算法兩個主要問題。主要包括以下4個步驟：①找出所需頁面在磁盤上的位置。②找出一個空閑內存塊。③把所需頁面讀入內存塊（剛剛得到的空閑塊），修改頁表和存儲塊表。④重新啟動該用戶進程。頁面置換流程示例

4．具有快表的地址轉換機構在內存中放置頁表也帶來存取速度下降的矛盾?？毂恚ɑ騎ranslationLookasideBuffer,TLB）：專用的、高速小容量的聯(lián)想存儲器。快表每項包括鍵號和值兩部分。程序局部化：一個程序在一段時間內總是相對集中在一個有限地址空間的某個區(qū)域中執(zhí)行。

4．具有快表的地址轉換機構請求分頁中的地址變換過程

4.6.3頁面置換算法1．有效存取時間和頁面走向⑴有效存取時間缺頁率p：表示缺頁中斷的概率（0≤p≤1）

等于缺頁次數(shù)與全部訪問內存次數(shù)之比有效存取時間可表示為：

有效存取時間=(1-p)×ma+p×缺頁處理時間▲缺頁中斷處理所花費的時間主要有以下三部分：①處理缺頁中斷的時間。②調入該頁的時間。③重新啟動該進程的時間?！鴮㈨撁鎻谋P上讀到內存所花費的時間包括：

●磁盤尋道時間（即磁頭從當前磁道移至指定磁道所用的時間）

●旋轉延遲時間（即磁頭從當前位置落到指定扇區(qū)開頭所用的時間）

●數(shù)據(jù)傳輸時間典型磁盤的旋轉延遲時間約為8ms，尋道時間約為15ms，傳輸時間是1ms。⑵頁面走向抖動頻繁地更換頁面,以致系統(tǒng)的大部分時間花費在頁面的調度和傳輸上。

盡量避免系統(tǒng)“抖動”。存儲訪問序列也叫頁面走向

①對于給定的頁面大小，僅考慮其頁號，不關心完整的地址。②如果當前對頁面p進行了訪問，那么，馬上又對該頁訪問就不會缺頁。這樣連續(xù)出現(xiàn)的同一頁號就簡化為一個頁號。⑵頁面走向存儲訪問序列也叫頁面走向▲如下地址序列（用十進制數(shù)表示）：

0100，0432，0101，0612，0102，0103，0104，0101，0611，0102，0103，0104，0101，0610，0102，0103，0104，0101，0609，0102，0105

若每頁100個字節(jié)，則頁面走向簡化為：1，4，1，6，1，6，1，6，1，6，1一般，隨著可用塊數(shù)的增加，缺頁數(shù)將減少。缺頁量與內存塊數(shù)關系圖▲統(tǒng)一采用下述頁面走向：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1并且，假定每個作業(yè)只有三個內存塊可供使用。2．常用的頁面置換算法⑴先進先出總是淘汰在內存中停留時間最長（年齡最老）的一頁，即先進入內存的頁，先被換出。FIFO頁面置換序列

▲總共有15次缺頁！2．常用的頁面置換算法⑴先進先出●優(yōu)點：容易理解，方便程序設計?！秉c：性能并不很好，效率不高；存在Belady異?，F(xiàn)象，即缺頁率隨內存塊增加而增加。⑵最佳置換法最佳置換算法（OptimalReplacement,OPT）其實質是：為調入新頁面而必須預先淘汰某個老頁面時，所選擇的老頁面應在將來不被使用，或者是在最遠的將來才被訪問。▲保證有最小缺頁率！

▲OPT算法在實現(xiàn)上有困難！最佳頁面置換序列僅出現(xiàn)9次缺頁中斷！

⑶最近最少使用置換法以“最近的過去”作為“不久將來”的近似，把最近最長一段時間里不曾使用的頁面淘汰掉。實質是：當需要置換一頁時，選擇在最近一段時間里最久沒有使用過的頁面予以淘汰。最近最少使用算法頁面置換序列

▲產生12次缺頁！LRU算法需要實際硬件的支持。實現(xiàn)時的問題是：怎樣確定最后訪問以來所經歷時間的順序。有以下兩種可行的辦法：①計數(shù)器②棧。利用棧記錄目前訪問最多的頁面示例

⑷最近未使用置換法最近未使用（NotRecentlyUsed，NRU）算法是LRU算法的近似方法。

不(5)Clock置換算法(6)改進型Clock置換算法

由訪問位A和修改位M可以組合成下面四種類型的頁面：1類(A=0,M=0):表示該頁最近既未被訪問，又未被修改，是最佳淘汰頁。2類(A=0,M=1):表示該頁最近未被訪問，但已被修改，并不是很好的淘汰頁。3類(A=1,M=0)：最近已被訪問，但未被修改，該頁有可能再被訪問。4類(A=1,M=1):最近已被訪問且被修改，該頁可能再被訪問。(6)改進型Clock置換算法

由訪問位A和修改位M可以組合成下面四種類型的頁面,其執(zhí)行過程可分成以下三步：(1)從當前位置開始掃描循環(huán)隊列，尋找A=0且M=0的頁面，將所遇到的第一個頁面作為所選中的淘汰頁。在第一次掃描期間不改變訪問位A。(2)如果查找一周后未遇到第一類頁面，則開始第二輪掃描，尋找A=0且M=1的頁面，將遇到的第一個這類頁面作為淘汰頁。將所有掃描過的頁面的訪問位都置0。(3)如果第二步也失敗，則將指針返回到開始的位置，并將所有的訪問位復0。然后重復第一步，如果仍失敗，必要時再重復第二步，此時就一定能找到被淘汰的頁。4.7內存塊分配和抖動問題4.7.1內存塊分配

1．最少內存塊數(shù)分給每個進程的最少內存塊數(shù)是指保證進程正常運行所需的最少內存塊數(shù)，它是由指令集結構決定的。2．內存塊的分配

①固定分配策略分配給進程的內存塊數(shù)是固定的，且在最初裝入時（即進程創(chuàng)建時）確定塊數(shù)。②可變分配策略允許分給進程的內存塊數(shù)隨進程的活動而改變。3.頁面置換范圍

●全局置換允許一個進程從全體存儲塊的集合中選取淘汰塊，盡管該塊當前分配給其他進程，還是能強行占用?！窬植恐脫Q是每個進程只能從分給它的一組內存塊中選擇淘汰塊?！鼍植恐脫Q可與固定分配策略相結合；■局部置換可與可變分配策略相結合；

■全局置換只能與可變分配策略相結合。

4．分配算法（1）等分法——內存塊按進程平分。

（2）比例法設進程pi的地址空間大小為si，則總地址空間為：

S=∑si若可用塊的總數(shù)是m，則分給進程pi的塊數(shù)是：

ai

≈m.si

/S（3）優(yōu)先權法——給高優(yōu)先級進程分配較多內存。

4.7.2抖動問題■整個系統(tǒng)的頁面替換非常頻繁，以致大部分機器時間都用在來回進行的頁面調度上，只有一小部分時間用于進程的實際運算。這種局面稱為系統(tǒng)“抖動（Thrashing）”。1．產生抖動的原因▲內存不足；▲多道程序度高；▲CPU的利用率太低。

CPU利用率與多道程序度之間的關系2．防止抖動的方法

①采用局部置換策略②利用工作集策略防止抖動③掛起某些進程④采用缺頁頻度法（PageFaultFrequency,PFF）缺頁頻度的上限和下限

4.8段式虛擬存儲器4.8.1基本工作過程

▲一個進程的所有分段的副本都保存在外存上。當它運行時，先把當前需要的一段或幾段裝入內存，其他段僅在調用時才裝入。

▲當所訪問的段不在內存時，便產生缺段中斷各段表項中要增加一位，以表明該段的存在狀態(tài)。還要增加另外一些控制位，如：

▲修改位；▲保護位；▲共享位缺段中斷機構--請求分段系統(tǒng)中的中斷處理過程

4.8.2動態(tài)鏈接和鏈接中斷處理1．動態(tài)鏈接僅當用到某個分段時才對它進行鏈接，從而避免不必要的鏈接。間接編址間接字鏈接故障指示位

4.8.2動態(tài)鏈接和鏈接中斷處理直接編址與間接編址示意圖

2．鏈接中斷處理段的動態(tài)鏈接示意圖

程序MAIN中有一條指令LOAD*1，3|100

方式功能單一連續(xù)區(qū)分區(qū)式頁式段式段頁式固定動態(tài)適用環(huán)境單道多道多道多道多道虛擬空間一維一維一維二維二維重定位方式靜態(tài)靜態(tài)動態(tài)動態(tài)動態(tài)動態(tài)分配方式連續(xù)連續(xù)非連續(xù)非連續(xù)非連續(xù)釋放全部分區(qū)淘汰算法淘汰算法淘汰算法保護界限寄存器界限寄存器對頁表段表、段長段表、段長、頁表內存擴充覆蓋與交換覆蓋與交換虛存虛存虛存共享不能不能較難方便方便硬件支持保護保護地址變換機構、保護地址變換機構、保護地址變換機構、保護4.9工作集

測試表明，虛擬存儲系統(tǒng)的有效操作依賴于程序中訪問的局部化程度。

1.局部性模型時間局部化是指一旦某條指令或數(shù)據(jù)被訪問過，它往往很快又被再次訪問?？臻g局部化是指一旦某個位置被訪問過，它附近的位置也可能很快要用到。4.9工作集2.工作集模型工作集，就是一個進程在某一小段時間內訪問頁面的集合。工作集模型

▲工作集依賴于程序的行為，并且其大小與的取值有關。每個進程的工作集大小為WSSi，那么D就是系統(tǒng)中全部（n個）進程對內存塊的總請求量。▲如果請求值D大于可用內存塊的總量m(D＞m)，將出現(xiàn)抖動。

伙伴系統(tǒng)是對固定分區(qū)和可變分區(qū)兩種存儲管理“揚長避短”后，提出的一種折中方案。

伙伴系統(tǒng)中，可用內存分區(qū)的大小為： 2K，L≤K≤U其中：2L表示分配的最小分區(qū)的尺寸；2U表示分配的最大分區(qū)的尺寸?；锇橄到y(tǒng)

C(64KB)64KBA(128KB)128KBB(256KB)512KBA(128KB)B(256KB)512KBA(128KB)128KB256KB512KB1MBC(64KB)64KBA(128KB)B(256KB)D(256KB)C(64KB)64KBA(128KB)256KBD(256KB)256KB256KBC(64KB)64KB128KB256KBD(256KB)256KBC(64KB)64KBE(128KB)256KBD(256KB)256KBE(128KB)128KB256KBD(256KB)256KB512KBD(256KB)256KB1MB1MB初啟：A請求100KB：B請求240KB：C請求64KB：D請求256KB：B釋放256KB：A釋放128KB：E請求128KB：C釋放64KB：E釋放