第4章存儲器管理

第四章存儲器管理4.1存儲管理的概念4.2分區(qū)式存儲管理4.3分頁式存儲管理4.4

分段式存儲管理4.5

段頁式存儲管理14.1存儲管理的概念存儲管理的對象：主存儲器以及作為主存擴(kuò)展和延伸的輔助存儲器（外存儲器）。存儲管理的目標(biāo)是：為用戶提供方便、安全和充分大的存儲空間。一、存儲管理的功能

1、存儲空間的分配與回收2、地址重定位3、主存的共享與保護(hù)4、主存的擴(kuò)充2（一）主存的分配與回收要完成內(nèi)存的分配和回收工作，做到合理有效地利用內(nèi)存，要求設(shè)計(jì)者選擇和確定以下幾種策略。1、放置策略——用戶程序要調(diào)入內(nèi)存時(shí)，確定將其放置在何處的策賂。也就是選擇空閑區(qū)的原則。2、調(diào)入策略——用戶程序在何時(shí)調(diào)入內(nèi)存的策略。目前常用的有請求調(diào)入和預(yù)調(diào)入兩種。3、淘汰策略——當(dāng)要將某個(gè)用戶程序調(diào)入內(nèi)存而又無空閑內(nèi)存空間時(shí)，既要確定哪些用戶程序可以從內(nèi)存中移走。分配結(jié)構(gòu)——記錄內(nèi)存的分配情況3（二）地址重定位為了保證作業(yè)的正確執(zhí)行，必須根據(jù)分配給用戶作業(yè)的主存區(qū)域?qū)ψ鳂I(yè)中的指令和數(shù)據(jù)的存放地址進(jìn)行地址重定位

。1、地址重定位：將程序使用的邏輯地址轉(zhuǎn)換為主存空間的物理地址的工作。

（地址轉(zhuǎn)換、地址映射）42、物理地址（空間）和邏輯地址（空間）物理地址空間：物理地址的集合。由主存物理單元組成，是一維線性空間，其大小取決于實(shí)際的主存容量。

（存儲空間、主存空間）邏輯地址空間：用戶所使用的編程空間（目標(biāo)程序的邏輯地址的集合）?？梢允且痪S的，也可以是二維的。

（地址空間、程序空間）物理地址：主存中存儲單元的編號。

（絕對地址、實(shí)地址）邏輯地址：用戶目標(biāo)程序中所使用的相對地址。

（相對地址、虛地址）5

符號地址

(變量)源程序符號（名）空間連接裝配

編譯

邏輯地址0n目標(biāo)程序邏輯地址（程序）空間

物理地址可執(zhí)行程序物理地址（主存）空間B

B+n

3、地址重定位方式：1）靜態(tài)重定位；2）動態(tài)重定位。61）靜態(tài)重定位

在一個(gè)作業(yè)裝入主存時(shí)，根據(jù)其所獲得的空間區(qū)域，由連接裝配程序?qū)⒃摮绦虻倪壿嫷刂忿D(zhuǎn)換為相應(yīng)的物理地址。地址一旦確定就不再改變。+

032

3465

3465+1320832124100108132224邏輯地址空間主存

例如：邏輯關(guān)系：物理地址=起始地址+邏輯地址7缺點(diǎn)：要求給每個(gè)作業(yè)分配一個(gè)連續(xù)的存儲區(qū)域，且在其整個(gè)執(zhí)行期間必須限定在這個(gè)區(qū)域內(nèi)。也就是說，在作業(yè)執(zhí)行期間程序不能“浮動”。這對提高主存的利用率是不利的。用戶必須事先確定所需的存儲量，若所需的存儲量超過可用存儲空間時(shí)，用戶必須考慮覆蓋結(jié)構(gòu)。用戶之間難以共享主存中的同一程序。若要共享同一程序，則每個(gè)用戶應(yīng)各自使用一個(gè)分開的副本。優(yōu)點(diǎn)：簡單，無需硬件支持，因而可在一般計(jì)算機(jī)上實(shí)現(xiàn)。82）動態(tài)重定位在作業(yè)執(zhí)行過程中，每當(dāng)執(zhí)行一條指令時(shí)都由硬件地址轉(zhuǎn)換機(jī)構(gòu)將指令中的邏輯地址轉(zhuǎn)換成物理地址。（在作業(yè)執(zhí)行時(shí)動態(tài)完成）動態(tài)重定位時(shí)，處理機(jī)每執(zhí)行一條指令都會把指令中的邏輯地址與重定位寄存器中的數(shù)值相加得到物理地址，然后按物理地址訪問主存儲器。重定位寄存器的值是根據(jù)作業(yè)分配到的存儲空間起始地址來設(shè)定的。采用動態(tài)重定位技術(shù)后，程序中所有指令和數(shù)據(jù)的實(shí)際地址是在程序運(yùn)行過程中最后訪問指令和數(shù)據(jù)的時(shí)刻確定的。因此，在作業(yè)運(yùn)行過程中臨時(shí)申請分配附加的存儲區(qū)域或釋放巳占用的部分存儲空間是允許的。9動態(tài)重定位的實(shí)現(xiàn)動態(tài)重定位示意圖

10優(yōu)點(diǎn)：主存的使用更加靈活有效。一個(gè)用戶的作業(yè)不一定要分配在一個(gè)連續(xù)的存儲區(qū)，因而可以使用較小的分配單位。而且在作業(yè)開始之前也不一定把它的地址空間中的信息全部裝入主存，而可以在作業(yè)執(zhí)行期間根據(jù)請求動態(tài)地進(jìn)行。缺點(diǎn)：需要附加硬件支持；實(shí)現(xiàn)存儲器管理的軟件比較復(fù)雜。幾個(gè)作業(yè)共享一程序段的單個(gè)副本比較容易。有可能向用戶提供一個(gè)比主存的存儲空間大用多的地址空間。11（三）存儲的共享與保護(hù)在多道程序設(shè)計(jì)的環(huán)境中，要保證各道程序只能在自己的存儲區(qū)中活動，不對別的程序產(chǎn)生干擾和破壞，必須對存儲信息采用各種保護(hù)措施。常用的保護(hù)手段：上、下界寄存器法和存儲(保護(hù))鍵法。1.上、下界寄存器法：由硬件為系統(tǒng)中的每個(gè)作業(yè)或進(jìn)程設(shè)置一對上、下界寄存器。當(dāng)某一作業(yè)的程序裝入內(nèi)存后，系統(tǒng)就將該程序所占存儲空間的首地址和末地址分別裝入相應(yīng)的一對上、下界寄存器中。在程序的運(yùn)行過程中若要對內(nèi)存進(jìn)行存訪操作時(shí)，必須先進(jìn)行存訪地址合法性的檢測。非法存訪，將產(chǎn)生越界中斷。12上、下界寄存器保護(hù)法的另一個(gè)變種是基址----限長寄存器保護(hù)法。其為每個(gè)作業(yè)(或進(jìn)程)設(shè)置一個(gè)基地址寄存器BA和一個(gè)限長寄存器LA。程序執(zhí)行過程中，每執(zhí)行一次存訪操作之前必須做存訪地址合法性的檢查。120K154K154K120K120K154K120K34K上界寄存器≤物理地址＜下界寄存器

0≤邏輯地址＜限長寄存器

132.存儲(保護(hù))鍵保護(hù)法。為每一個(gè)被保護(hù)的存儲塊分配一個(gè)單獨(dú)的保護(hù)鍵，在當(dāng)前程序狀態(tài)字（PSW）中設(shè)置相應(yīng)的保護(hù)鍵開關(guān)字段，對不同的進(jìn)程賦予不同的開關(guān)代碼以與被保護(hù)的存儲塊中的保護(hù)鍵匹配，若不匹配則產(chǎn)生越界中斷。例如：在IBM/360系統(tǒng)中

0

塊i

1

0

0

1

塊i+1

0

1

0

111001

開關(guān)字段（鑰）0—共享（只讀）

共享位

1—匹配（可讀可寫）

保護(hù)鍵

0—系統(tǒng)

1～15

—用戶

當(dāng)前程序狀態(tài)字（PSW）14（四）主存的擴(kuò)充借助于主存擴(kuò)充技術(shù)為用戶提供比主存空間大的地址空間，從而實(shí)現(xiàn)擴(kuò)充主存容量的目的。主存擴(kuò)充技術(shù)覆蓋技術(shù)對（交）換技術(shù)虛擬存儲技術(shù)154.2分區(qū)存儲管理一、概述分區(qū)式存儲管理基本思想：把主存空間靜態(tài)地或動態(tài)地劃分為若干個(gè)大小不等的區(qū)域，每個(gè)作業(yè)分配一片連續(xù)的存儲空間，程序一次性整體裝入。二、分區(qū)式存儲管理的方式：固定分區(qū)(靜態(tài)分區(qū))存儲管理可變分區(qū)(動態(tài)分區(qū))存儲管理16（一）固定分區(qū)(靜態(tài)分區(qū))

1.基本原理：把主存儲器中可分配的用戶區(qū)域預(yù)先（靜態(tài)）劃分為若干個(gè)大小不等的連續(xù)的區(qū)域（分區(qū)），每個(gè)分區(qū)中裝入一個(gè)作業(yè)。分區(qū)的劃分由計(jì)算機(jī)操作員或者由操作系統(tǒng)作出。并給出分區(qū)說明表。2.主存空間的分配與回收分配結(jié)構(gòu)：分區(qū)說明表（MBT）區(qū)號分區(qū)長度起始地址狀態(tài)17例：該系統(tǒng)的內(nèi)存容量為256KB，操作系統(tǒng)占用低地址的40KB，其余空間劃分成5個(gè)固定大小的分區(qū)。112K18在固定分區(qū)方法中，當(dāng)某個(gè)用戶程序要裝入運(yùn)行時(shí)，向系統(tǒng)提出分配內(nèi)存的請求，并給出要求存儲空間的大小。系統(tǒng)根據(jù)用戶的請求查詢分區(qū)說明表，從中找出一個(gè)滿足要求的，并且是空閑的分區(qū)給申請者，然后修改相應(yīng)的表目的狀態(tài)位,即把狀態(tài)位置為“正在使用”，最后向用戶返回分區(qū)號或分區(qū)首地址。3.地址轉(zhuǎn)換與存儲保護(hù)地址轉(zhuǎn)換：靜態(tài)重定位。存儲保護(hù)：上下界寄存器法。下界地址≤物理地址≤上界地址4.特點(diǎn)：簡單、空間浪費(fèi)較大。19（二）可變分區(qū)(動態(tài)分區(qū))1.基本原理：是指在系統(tǒng)運(yùn)行的過程中，當(dāng)作業(yè)要求裝入主存儲器時(shí)，根據(jù)作業(yè)需要的主存容量（動態(tài)地）劃分出一個(gè)分區(qū)分配給該作業(yè)，使分區(qū)的大小剛好與作業(yè)的大小相等。2.主存空間的分配與回收分配結(jié)構(gòu)：（1）空閑區(qū)說明表（FBT）。區(qū)號分區(qū)長度起始地址狀態(tài)40K

40K16K78K

24K

100K

78K┇（2）自由鏈(空閑區(qū)隊(duì)列)20OS作業(yè)1，32K作業(yè)3，64K作業(yè)4，100K20KB052KB66KB130KB230KB256KB-1主存分布52KB230KB14KB^26KB首指針自由鏈(空閑區(qū)隊(duì)列)21主存分配與回收過程：（設(shè)系統(tǒng)主存容量為256K，OS占用20K）

進(jìn)程A(64K）進(jìn)程B(16K）進(jìn)程C(8K）進(jìn)程D(24K）進(jìn)程A

OS進(jìn)程A

OS進(jìn)程A進(jìn)程B進(jìn)程C

OS進(jìn)程C進(jìn)程B

OS

進(jìn)程D進(jìn)程B

進(jìn)程C

進(jìn)程A

OS進(jìn)程D進(jìn)程C22常用的分區(qū)分配算法(放置策略)放置策略：自由鏈(空閑區(qū)隊(duì)列)的排序原則?？臻e區(qū)的組織方法有兩種：按空閑區(qū)大小的遞增和遞減的次序組織空閑區(qū)隊(duì)列。按空閑區(qū)首址的增加或減少的次序組織空閑區(qū)隊(duì)列。（1）最佳適應(yīng)算法(BFA)

為一個(gè)作業(yè)選擇分區(qū)時(shí)總是尋找大小最接近于作業(yè)所要求的存儲區(qū)域。換句話說，把作業(yè)放入這樣的分區(qū)后剩下的部分最小。存儲空間中所有的空白區(qū)按其大小遞增的順序鏈接起來。23優(yōu)點(diǎn)：首先選擇正好是所要求大小的空白區(qū)；其次選擇比要求稍大的空白區(qū)劃分，而不會去劃分一個(gè)更大的空白區(qū)。因此，其后遇到大的作業(yè)到來時(shí)，作業(yè)要求的存儲區(qū)域就比較容易得到滿足。缺點(diǎn)：在每次分配時(shí)，容易產(chǎn)生較小的空白區(qū)，由于其太小而無法使用，從而形成“碎片”。因此，經(jīng)過一段時(shí)期后，存儲空間中可能留下許多這樣的“碎片”

。在回收一個(gè)分區(qū)時(shí)，為了把它插入到空白區(qū)鏈中合適的位置上也頗為費(fèi)時(shí)。改進(jìn)：可設(shè)置一參數(shù)G，用它來確定最小分區(qū)的大小。當(dāng)選擇一個(gè)分區(qū)時(shí)，如果選中的空白區(qū)與要求的大小之差小于G，則不再對它劃分，而把整個(gè)這個(gè)空白區(qū)分配給申請的作業(yè)。24（2）最壞適應(yīng)算法(WFA)

在為作業(yè)選擇存儲區(qū)域時(shí)，總是尋找最大的空閑區(qū)?？臻e區(qū)以大小遞減的順序鏈接起來。

優(yōu)點(diǎn)：

在劃分后剩下的空閑區(qū)較大，因而對以后的分配很可能仍然是有用的。缺點(diǎn)：由于最大的空閑區(qū)總是首先被分配而進(jìn)行劃分，當(dāng)有大的作業(yè)時(shí)，其存儲空間的申請往往得不到滿足。25（3）首次(最先)適應(yīng)算法(FFA)

在為作業(yè)分配存儲區(qū)域時(shí)，從空閑區(qū)鏈的始端開始查找，選擇第一個(gè)滿足請求的空閑區(qū)．而不管它究竟有多大。每個(gè)空閑區(qū)按其在存儲空間中地址遞增的順序鏈在一起。即每個(gè)后繼空閑區(qū)的起始地址總是比前者的大。特點(diǎn)：傾向于優(yōu)先利用存儲空間中低址部分的空白區(qū)。26缺點(diǎn)：這種算法可能會利用一個(gè)大的空閑區(qū)適應(yīng)小作業(yè)的請求。由于所有的請求都是從空白區(qū)鏈的始端開始查找，因而這些小的甚至無用的空閑區(qū)集中在這個(gè)鏈的前端，相應(yīng)地，一些較大的空閑區(qū)在鏈的后端才能發(fā)現(xiàn)。這種情況使找到合適空閑區(qū)的速度降低。優(yōu)點(diǎn)：算法簡單，查找速度快。留在高地址部分的大的空閑區(qū)被劃分的機(jī)會較少，因而在大作業(yè)到來時(shí)也比較容易得到滿足。27

動態(tài)分區(qū)分配的過程中選擇的空閑區(qū)被分成兩部分：一部分與請求的大小相等，分配給作業(yè)；剩下的部分作為空閑區(qū)仍留在空閑區(qū)鏈中。28（c）最壞適應(yīng)法中的空閑區(qū)隊(duì)列（a）首次適應(yīng)法中的空閑區(qū)隊(duì)列（b）最佳適應(yīng)法中的空閑區(qū)隊(duì)列標(biāo)志0標(biāo)志0標(biāo)志0標(biāo)志0標(biāo)志0標(biāo)志0標(biāo)志0標(biāo)志0標(biāo)志0標(biāo)志0標(biāo)志0標(biāo)志029

作業(yè)

A18KB

os30KB在使用20KB在使用5KB在使用46KB020KB100KB160KB210KB256KB－1首次適應(yīng)算法

作業(yè)

A18KB

os30KB在使用20KB在使用5KB在使用46KB020KB100KB160KB210KB256KB－1最佳適應(yīng)算法

作業(yè)

A18KB

os30KB在使用20KB在使用5KB在使用46KB020KB100KB160KB210KB256KB－1最壞適應(yīng)算法3031回收一個(gè)主存塊——空閑區(qū)的拼接具體工作：檢查釋放區(qū)是否與系統(tǒng)中的空閑區(qū)相鄰，若相鄰則把釋放區(qū)合并到相鄰的空閑區(qū)中，否則把釋放區(qū)作為一個(gè)空閑區(qū)插入到自由主存隊(duì)列的適當(dāng)位置。釋放區(qū)與空閑區(qū)相鄰有四種情況：占用區(qū)TIHTI占用區(qū)占用區(qū)IH占用區(qū)I釋放區(qū)與空閑區(qū)相鄰情況其中：I：釋放區(qū)H：前空閑區(qū)T：后空閑區(qū)32(1)釋放區(qū)與前空閑區(qū)相鄰：如圖所示。對這種情況是將釋放區(qū)與前空閑區(qū)合并為一個(gè)空閑區(qū)，其首址仍為前空閑區(qū)首址，大小為釋放區(qū)大小與空閑區(qū)大小之和。H占用區(qū)I判斷相鄰空閑區(qū)：addr(I)=addr(H)+size(H)則前鄰為空閑區(qū)：釋放區(qū)與空閑區(qū)的拼接：

addr=addr(H)

size=size(H)+size(I)

（修改H的登記項(xiàng)）33判斷相鄰空閑區(qū)：

addr(T)=addr(I)+size(I)則后鄰為空閑區(qū)：釋放區(qū)與空閑區(qū)的拼接：

addr=addr(I)

size=size(T)+size(I)

（修改T的登記項(xiàng)）

(2)釋放區(qū)與后空閑區(qū)相鄰：如圖所示。對這種情況是把釋放區(qū)合并到后空閑區(qū)，首地址為釋放區(qū)首地址，大小為二者大小之和。占用區(qū)TI34HTI判斷相鄰空閑區(qū)：addr(I)=addr(H)+size(H)，則前鄰為空閑區(qū)addr(T)=addr(I)+size(I)，則后鄰為空閑區(qū)釋放區(qū)與空閑區(qū)的拼接：

addr=addr(H)

size=size(H)+size(I)

+size(T)

（修改H的登記項(xiàng)，并刪除T的登記項(xiàng)）

(3)釋放區(qū)與前后兩個(gè)空閑區(qū)相鄰：如圖所示。在這種情況下將這三個(gè)區(qū)合為一個(gè)空閑區(qū)，其首地址為前空閑區(qū)首地址，大小為這三個(gè)區(qū)大小之和。35

(4)釋放區(qū)不與任何空閑區(qū)相鄰：如圖所示。這種情況下把釋放區(qū)作為一個(gè)空閑區(qū)，將其插入到自由鏈的適當(dāng)位置。占用區(qū)占用區(qū)I釋放區(qū)作為一個(gè)新的空閑區(qū)：

addr=addr(I)size=size(I)（增加一個(gè)新的登記項(xiàng)）36三、碎片問題及拼接技術(shù)

碎片：主存中不連續(xù)的極小的空閑區(qū)。解決方法：采用“拼接技術(shù)”（移動技術(shù)或緊湊技術(shù)）使分散的空閑區(qū)集中起來，以容納新的作業(yè)。緊湊的示意

37優(yōu)缺點(diǎn)：（1）集中分散的空閑區(qū)，提高了主存空間的利用率；（2）移動會增加系統(tǒng)的開銷，花費(fèi)大量的CPU時(shí)間；（盡量減少移動）（3）移動是有條件的。（正等待外圍設(shè)備進(jìn)行信息傳輸?shù)倪M(jìn)程不能移動）（4）當(dāng)系統(tǒng)進(jìn)行拼接時(shí)，它必須停止所有其它的工作；（5）拼接需要重新定位已裝入主存的作業(yè)。

384.3分頁式存儲管理

一、基本原理將主存空間按固定大小等分為若干個(gè)大小相等的塊（頁面），并給以從“0”開始的順序的編號——塊號（頁框號）（頁架號）。將作業(yè)的地址空間等分為若干個(gè)與塊相等的頁，并給以從“0”開始的順序的編號——頁號（頁面號）。

存儲分配時(shí)，將作業(yè)信息按頁存放到塊中（存儲分配時(shí)，以塊為單位），一個(gè)作業(yè)所占用的若干個(gè)主存塊可以是不相鄰的（塊號可以是不連續(xù)的）。39

┆主存空間

00000HFFFFFH

2#

0#

1#地址空間

0

3K-1┆40（一）邏輯地址結(jié)構(gòu)在分頁存貯管理中，程序的邏輯地址包含兩部分內(nèi)容：頁號和頁內(nèi)地址（頁內(nèi)偏移量）。（設(shè)：頁長=1KB=210B）

頁內(nèi)地址的位數(shù)由頁長決定，邏輯地址字中除去頁內(nèi)地址所占的低位部分外，其余高位部分為頁號。例如一個(gè)系統(tǒng)的邏輯地址字為16位，頁長為1KB，則頁長占10位，占邏輯地址字的第0—9位，余下的第10—15位為頁號。頁號P頁內(nèi)地址ｄ091015

二、頁式地址轉(zhuǎn)換41則：頁長（L）=212B=4ＫＢ最大分頁數(shù)＝2２０頁=１Ｍ頁頁號P頁內(nèi)地址ｄ0111231若邏輯地址的長度為32位，其中0~11為頁內(nèi)地址，12~31位為頁號

42

對某特定機(jī)器，其地址結(jié)構(gòu)是一定的。若給定一個(gè)邏輯地址空間中的地址為A，頁面的大小為L，則頁號P和頁內(nèi)地址d可按下式求得：在系統(tǒng)進(jìn)行存訪操作時(shí)，由硬件地址轉(zhuǎn)換機(jī)構(gòu)自動地取出頁號和頁內(nèi)地址，然后進(jìn)行頁地址變換。43系統(tǒng)為每個(gè)進(jìn)程建立一個(gè)頁表，頁表的起始地址和它的長度存放在進(jìn)程的進(jìn)程控制塊(PCB)中。占用處理機(jī)的現(xiàn)行進(jìn)程的頁表必須駐留在內(nèi)存，其首地址和長度由地址映射機(jī)構(gòu)的頁表起址和頁表長度寄存器指示。（二）頁表頁表：指出邏輯地址中的頁號與該頁所在主存的塊號的對應(yīng)關(guān)系。

頁號

塊號4421程序地址空間頁號塊號頁號作業(yè)1作業(yè)2作業(yè)3作業(yè)3作業(yè)1作業(yè)1作業(yè)2作業(yè)2作業(yè)1頁表結(jié)構(gòu)頁表內(nèi)存21222623272945（三）頁地址轉(zhuǎn)換過程例：設(shè)頁面大小為1KB，機(jī)器的地址長度為16位。作業(yè)2的進(jìn)程在CPU上運(yùn)行，執(zhí)行指令Movr1,[2500]頁表始址寄存器頁號p頁內(nèi)位移d0000100111000100091015

2500＝（100111000100）2Movr1,[2500]12301KB2KB3KB-1地址空間

（1110111000100）2＝7620P=2d=452①M(fèi)ovr1,[2500]12302KB4KB7KB256KB-1主存頁號塊號頁表

0

1

2

2

4

7塊號p’頁內(nèi)位移d0001110111000100091015③123②＋物理地址＝

p’

*L+d46（四）快表在每次地址變換時(shí)要訪問內(nèi)存頁表，然后產(chǎn)生內(nèi)存地址，這樣執(zhí)行一條訪問內(nèi)存的指令至少要訪問兩次內(nèi)存，運(yùn)行速度降低一倍。解決這個(gè)問題的一種方法是把頁表放在一組快速存儲器中，而不是內(nèi)存中。轉(zhuǎn)換過程:①將當(dāng)前指令中的邏輯地址（2500）分解為頁號P（2）和頁內(nèi)地址d（452）。②根據(jù)頁號P（2）查頁表，取得相應(yīng)的塊號P’（7）。③將塊號P’（7）與頁內(nèi)地址d（452）拼接為物理地址（7620）。47聯(lián)想方式：是用聯(lián)想線路連接各寄存器，查詢時(shí)不再用查詢內(nèi)存表格的方法一個(gè)表目一個(gè)表目地查詢，而是通過電子線路同時(shí)查詢所有的快表寄存器。在具有高速聯(lián)想存儲器的地址變換過程中，首先檢查這個(gè)高速存儲器，確定需要的頁表目是否在其中。如果沒有發(fā)現(xiàn)，再訪問主存儲器中的頁表。在訪問內(nèi)存中頁表的同時(shí)，把從頁表中讀出的頁表目存入一個(gè)寄存器單元中，以替代一個(gè)老的、認(rèn)為不再需要的頁表目。快表：將當(dāng)前執(zhí)行進(jìn)程中最常用的頁表目（頁號與對應(yīng)的塊號）存入高速聯(lián)想存儲器構(gòu)成一張快表，以減少訪問主存的次數(shù)，提高存取的速度。慢表：內(nèi)存中存放的頁表。48頁表始址寄存器分頁機(jī)構(gòu)聯(lián)想寄存器塊號頁表(在主存中)物理地址apdbdbapb首先選擇這條路a+p僅在聯(lián)想映像不匹配時(shí)進(jìn)行＋49（五）兩級頁表及多級頁表結(jié)構(gòu)

現(xiàn)代的大多數(shù)計(jì)算機(jī)系統(tǒng)，都支持非常大的邏輯地址空間(232～264)。在這樣的環(huán)境下，頁表就變得非常大，要占用相當(dāng)大的內(nèi)存空間。例如，對于一個(gè)具有32位邏輯地址空間的分頁系統(tǒng)，規(guī)定頁面大小為4KB即212B，則在每個(gè)進(jìn)程頁表中的頁表項(xiàng)可達(dá)220個(gè)，1M個(gè)之多。又因?yàn)槊總€(gè)頁表項(xiàng)占用4個(gè)字節(jié)，故每個(gè)進(jìn)程僅僅其頁表就要占用4MB的內(nèi)存空間，而且還要求是連續(xù)的。50

1、兩級頁表結(jié)構(gòu)邏輯地址為32位時(shí),邏輯地址空間為4GB(即232B)設(shè):頁面大小為4KB(即212B)則:最多頁面數(shù)為1MB(即220B)兩極頁表結(jié)構(gòu)的邏輯地址字:主頁號P1次級頁號P2頁內(nèi)地址d

3122211211051兩級頁表結(jié)構(gòu)

主頁表次級頁表52具有兩級頁表的地址變換機(jī)構(gòu)頁內(nèi)地址主頁表次級頁表主頁號次級頁號主頁表寄存器53（一）分配結(jié)構(gòu)：位示圖三、主存空間的分配與回收100000110010000110001101111110151413121143210（二）頁的分配與回收分配：字號（行）

掃描位示圖，找是“0”的位修改該位為：“1”，位號（列）塊號=字號×字長+位號，返回塊號。

54回收:

字號=[塊號/字長]取整

根據(jù)塊號位號={塊號/字長}求余掃描位示圖，根據(jù)（字號，位號）找對應(yīng)的位，將該位修改為“0”。100000110010000110001101111110151413121143210分配結(jié)構(gòu)：位示圖55四、頁的共享與保護(hù)作業(yè)1的頁表

頁號標(biāo)志塊號

0

E12

1

E13

2

W14

3

R8頁號標(biāo)志塊號

0

E

2

1

W

3

2

R

8作業(yè)2的頁表

頁的共享：對作業(yè)中涉及共享信息的頁，使其在頁表中的有關(guān)表目指向共享信息所在的主存塊。頁的保護(hù)：在頁表中增加一些標(biāo)志位指出對該頁信息可執(zhí)行的操作。56五、分頁式存儲管理特點(diǎn)1.解決了碎片問題，提高了存儲空間的利用率。2.但作業(yè)大小仍受內(nèi)存可用頁面數(shù)的限制。由于分頁存儲分配有效地解決了存儲器的零頭問題，因而能同時(shí)為更多的作業(yè)提供存儲空間，能在更高的程度上進(jìn)行多道程序設(shè)計(jì)，從而相應(yīng)地提高了存儲器和處理機(jī)的利用率。574.4分段式存儲管理問題：

1）前面介紹的各種存儲管理方案，如分區(qū)分配，分頁等，它們的主要差別在于對內(nèi)存的利用方法不同，目的都在于如何有效地利用內(nèi)存。為了更有效地利用存儲器同時(shí)又便于程序員使用，引進(jìn)了分段存貯管理。

2）實(shí)際用戶處理問題，往往出現(xiàn)模塊化程序，且有主程序、子程序、分程序、過程等結(jié)構(gòu)，它們基本上是以段(模塊)出現(xiàn)的。程序員都希望把信息按其內(nèi)容或函數(shù)關(guān)系分成段，每段有自己的名字，且可以根據(jù)名字來訪問相應(yīng)的程序或數(shù)據(jù)段。一、段式系統(tǒng)的特點(diǎn)58分段式存儲管理基本原理

1）一個(gè)用戶程序通常由一個(gè)主程序、若干個(gè)子程序和數(shù)據(jù)區(qū)組成，按信息的邏輯關(guān)系分為段，每一段從“0”開始給以順序的編號（段號）。

2）程序的地址空間按段組織。（把整個(gè)作業(yè)的邏輯地址空間分為若干段，每一段的段內(nèi)從“0”開始順序形成邏輯地址）。

3）存儲分配時(shí)，以段為單位分配一片連續(xù)的存儲空間。注意：“段”是信息的邏輯單位，是由程序設(shè)計(jì)人員決定的，其長度隨程序的不同而變化；“頁”是由操作系統(tǒng)規(guī)定的，確定頁長、進(jìn)行分頁等，都是由操作系統(tǒng)和硬件相互配合完成。59一個(gè)段是一組邏輯信息，如子程序，數(shù)組或數(shù)據(jù)區(qū)，工作區(qū)等。每個(gè)作業(yè)的地址空間由一些分段構(gòu)成的，每段都有自己的名字，且都是一段連續(xù)的地址空間。每個(gè)段從0開始編址，整個(gè)作業(yè)的地址空間是二維的。二、段式地址變換分段MAIN（主程序）分段X（子程序）分段A（數(shù)組）分段B（工作區(qū)）60一旦段號字段和位移量字段的長度確定后，一個(gè)作業(yè)地址空間中允許的最多段數(shù)及段的最大長度也就限定了。上述地址結(jié)構(gòu)表明，該系統(tǒng)可允許一個(gè)作業(yè)有256段，最大段長為64K字節(jié)。程序的地址空間按段組織，每段有個(gè)標(biāo)識符，稱為段名，由程序員給出。程序經(jīng)過編譯連接后，段名轉(zhuǎn)換成段號。各段的長度一般情況下不相等，但段內(nèi)編址是一維的。因此程序的邏輯地址由段號和段內(nèi)地址組成，即二維地址。段號S位移量W23150邏輯地址字:61段地址映射的數(shù)據(jù)結(jié)構(gòu)有段表、段表首址指針和段表的長度。段表首址指針一般存放在所在進(jìn)程的PCB中。段表存放程序各段的長度、位置和存取狀態(tài)等信息。每個(gè)進(jìn)程有一個(gè)段表，每個(gè)程序段的有關(guān)信息占用一個(gè)表目。62段地址轉(zhuǎn)換通常由硬件的地址轉(zhuǎn)換機(jī)構(gòu)完成：1）程序地址字送入虛地址寄存器VR，取出段號S和段內(nèi)位移W。(分解)2）根據(jù)段表首址指針找到段表，查找段號為S的表目，得到該段的首地址b。(查段表)3）把段首地址與段內(nèi)地址相加，形成物理地址，并以此地址存訪內(nèi)存。(相加)在段地址變換的過程中，與頁地址變換一樣，也有兩次訪問內(nèi)存的問題。為加快訪問內(nèi)存的速度也可采用聯(lián)想存儲器組成快表。63段地址轉(zhuǎn)換過程控制寄存器段表始址段表長度

6000段表

段始址

段大小

300

500

4000

300

8000

段號

0

1

2+

②W(292)S(2）①

邏輯地址

LOAD1，2|292

┇

Data主存4128

物理地址8292

+③

64三、段的動態(tài)連接

1.連接裝配方式(1)靜態(tài)連接（要求有統(tǒng)一編址的相對地址空間時(shí)采用。如：分頁存儲管理）(2)動態(tài)連接（不要求有統(tǒng)一編址的相對地址空間時(shí)采用。如：分段存儲管理）

2.連接間接字機(jī)器指令的尋址方式

(1)直接尋址ADD4001320400

(2)間接尋址（包含直接地址的字——間接字）ADD*400140013201320400（直接地址）（直接地址）（間接字）（間接地址）（直接地址）653.編譯程序的連接準(zhǔn)備工作（程序段的編譯原則）

訪問本段程序——直接尋址

訪問外段程序——間接尋址（設(shè)置連接間接字，地址指向本段的一個(gè)用來存放段名的存儲單元）。(3)連接間接字：

連接標(biāo)志位L1——>未連接——>硬件自動判斷L位，觸發(fā)連接中斷信號。

0——>已連接——>繼續(xù)執(zhí)行。直接地址L664.連接中斷處理

·根據(jù)連接間接字找出“段名”；

·判斷該段是否在主存；

·在主存，找出段號并修改連接間接字中的地址場和連接標(biāo)志，返回?cái)帱c(diǎn)處繼續(xù)執(zhí)行。

·不在主存，分配主存，調(diào)入主存，分配段號，重復(fù)上一步驟。67例如：編譯后：

連接后：A段：

┇CALLX│Y┇

X段：

┇

X│Y┇

┇CALL*1|2000┇┇

┇

1

1|2400

X│Y1#

段：

┇CALL*1|2000┇┇

┇

0

4|100

X│Y1#

段：

4#段：

┇

4|100┇68四、分段的共享采用分段管理并配合動態(tài)鏈接方法，可以避免在每個(gè)作業(yè)的地址空間中均需保留共享子程序的一個(gè)副本。若兩個(gè)作業(yè)共享一子程序分段，只要在作業(yè)段表的相應(yīng)表目的段首址一項(xiàng)中填入相同的主存地址。6970

五、分段管理主要優(yōu)點(diǎn)：1）便于程序模塊化處理。在分段系統(tǒng)中，我們把每個(gè)程序模塊構(gòu)成各自獨(dú)立的分段，賦與不同的名字(或段號)，并可采用段的保護(hù)措施。所以，一個(gè)程序模塊不會受到其它模塊的影響和干擾，因而對模塊化程序的處理也比較好解決。

2）便于處理動態(tài)的數(shù)據(jù)結(jié)構(gòu)。在實(shí)際應(yīng)用中，有些表格或數(shù)據(jù)段的長度隨輸入數(shù)據(jù)多少而變。在這種情況下，要求能動態(tài)擴(kuò)大一個(gè)分段。為了節(jié)省主存空間，對于這種變化的數(shù)據(jù)段，開始確定的長度剛好滿足當(dāng)前的需要。當(dāng)程序員企圖往該段中添加新的數(shù)據(jù)時(shí)，便產(chǎn)生一個(gè)越界中斷，操作系統(tǒng)得到控制權(quán)后，判別該段是否允許增補(bǔ)，如可以增補(bǔ)，則增加段的長度。這可通過拼接或移去相鄰的一個(gè)分段來實(shí)現(xiàn)。713）便于動態(tài)鏈接。由于分段地址空間是二維的，且每一分段是一組有意義的信息或具有獨(dú)立功能的程序段。因而，可以在作業(yè)運(yùn)行過程中調(diào)用到一程序段或數(shù)據(jù)段時(shí)，再進(jìn)行動態(tài)鏈接。4）便于共享分段。和分頁不同，分段是一組有一定意義的信息集合，且由于能實(shí)現(xiàn)分段的動態(tài)鏈接，一個(gè)分段在共享它的作業(yè)之間可以有不同的段號。5）可以實(shí)現(xiàn)多段式虛擬存儲器，“擴(kuò)充”主存容量?；蛘哒f作業(yè)的地址空間不受主存容量的限制，只要一段的長度不超過主存的大小。72分段管理的缺點(diǎn)：1）和分頁管理一樣，處理機(jī)要為地址變換花費(fèi)時(shí)間，要為表格提供附加的存儲空間，這使操作系統(tǒng)復(fù)雜化。2）為滿足分段的動態(tài)增長和減少外零頭，要采用拼接手段。3）在輔存中管理不定長度的分段困難較多。例如，存儲位置不易確定，存儲空間利用率不易提高。732）頁的大小固定不變，由系統(tǒng)決定。段的大小是不固定的，它由其完成的功能決定。3）由于段是信息的邏輯單位，因此便于存貯保護(hù)和信息的共享，頁的保護(hù)和共享受到限制。4）段式管理與分區(qū)管理一樣可能產(chǎn)生主存碎片，而頁式管理則很好的消除了碎片。六、段式與頁式管理的比較：雖然段式管理與頁式管理的地址變換機(jī)構(gòu)非常相似，但兩者有著概念上的根本差別。1）段是信息的邏輯單位，它是根據(jù)用戶的需要?jiǎng)澐值?；頁是信息的物理單位，是為了管理主存的方便而劃分的?44.5

段頁式存儲管理一、基本原理：作業(yè)的地址空間采用分段方式，而作業(yè)的每一段又采用分頁方式。整個(gè)主存分成大小相等的塊，主存以塊為單位分配給每個(gè)作業(yè)。一段二段三段0頁0頁0頁1頁2頁3頁1頁1頁2頁4K0004K4K4K8K12K8K8K1