第3章存儲管理要求學(xué)生了解存儲管理的一般性概念;重點掌握分區(qū)式管理、分頁式管理、分段式管理以及段頁式管理的原理，在學(xué)習(xí)中要注意每種管理方式提出的背景和解決的問題，還要了解系統(tǒng)內(nèi)部提供的軟硬件支持。第3章存儲管理3.1概述

3.2簡單的存儲管理

3.3

分頁存儲管理

3.4

請求分頁存儲管理

3.5

分段存儲管理

3.6

段頁式存儲管理

3.6

小結(jié)計算機系統(tǒng)中存儲器一般分為主存儲器和輔助存儲器兩級。3.1.1存儲管理的功能

1．主存分配

2．地址映射:把邏輯地址轉(zhuǎn)換成物理地址的過程

3．主存擴充:借助虛擬存儲器或自動覆蓋技術(shù)來“擴充”主存容量

4．存儲保護3.1概述3.1.2內(nèi)存的分配與回收按分配時機的不同，內(nèi)存分配可分為兩種方式：

1．靜態(tài)存儲分配：裝入內(nèi)存前一次分配

2．動態(tài)存儲分配：裝入內(nèi)存后在運行中分配

內(nèi)存分配與回收時應(yīng)考慮的幾個問題：1)如何選擇內(nèi)存中空閑區(qū);2)置換問題;3)回收問題3.1概述3.1.3地址重定位1．邏輯地址空間

地址空間是指程序用來訪問信息所用的一系列地址單元的集合。邏輯地址又叫相對地址3.1概述符號指令數(shù)據(jù)說明I/O說明名空間目標(biāo)程序作業(yè)X地址空間物理空間0B0AA+B512K作業(yè)X的源程序圖3-1名空間、地址空間、物理空間3.1.3地址重定位2．物理空間

物理空間（也稱存儲空間）是指主存中物理單元的集合。這些單元的編號稱為物理地址或絕對地址

3．地址重定位作業(yè)地址空間中使用的邏輯地址變換成主存中的物理地址的過程,也叫地址映射。

4．重定位的類型靜態(tài)重定位和動態(tài)重定位3.1概述3.1.3地址重定位4．重定位的類型

1)靜態(tài)重定位程序運行之前進行重定位,如圖3-3（a）缺點：①它要求分配給程序的內(nèi)存空間連續(xù),且一旦程序裝入后，不能在內(nèi)存中移動或重分配②用戶需要事先確定所需存儲量③用戶之間難以共享主存中同一程序副本3.1概述2）動態(tài)重定位程序執(zhí)行過程中由硬件地址變換機構(gòu)實現(xiàn),如圖3-3（b）

動態(tài)重定位的主要優(yōu)點有：（1）用戶作業(yè)不要求分配連續(xù)的存儲空間。（2）用戶作業(yè)在執(zhí)行過程中，可以動態(tài)申請存儲空間和在主存中移動。（3）有利于程序段的共享。

動態(tài)重定位的主要缺點有：（1）需要附加的硬件支持。（2）實現(xiàn)存儲管理的軟件算法比較復(fù)雜。3.1概述3.1概述50001000Load1,1006Add1,1008Store1,1010XY（a）靜態(tài)重定位…Load1,5000…X……Load1,5000…X…100005000+011000150000存儲空間地址空間(b)動態(tài)重定位圖3-3重定位類型3.1.4虛擬存儲器

虛擬存儲技術(shù)的基本思想是:將有限的內(nèi)存空間與大容量的外存進行統(tǒng)一管理，構(gòu)成一個遠(yuǎn)大于實際內(nèi)存的、虛擬的存儲器。但實際上這樣大容量的內(nèi)存并不存在，而是虛擬的，因此把具有這種功能的存儲管理技術(shù)稱為虛擬存儲管理。3.1概述3.2.1固定分區(qū)存儲管理

基本思想是:在作業(yè)未進入內(nèi)存之前，把內(nèi)存可用空間劃分成若干個固定大小的存儲區(qū)，除操作系統(tǒng)占用一個區(qū)域外，其余區(qū)域為系統(tǒng)中多個用戶共享。也稱為靜態(tài)分區(qū)

舉例:假設(shè)某系統(tǒng)有256K內(nèi)存，剛開始運行時，內(nèi)存分區(qū)劃分如圖3-4（a）所示。

優(yōu)點:是簡單，要求的硬件支持少，軟件算法也簡單，

缺點:是容易產(chǎn)生內(nèi)部碎片。3.2簡單的存儲管理3.2.1固定分區(qū)存儲管理操作系統(tǒng)空閑分區(qū)作業(yè)Y碎片（2K）空閑分區(qū)作業(yè)X40K48K80K144K256K0K第一分區(qū)（8K）第二分區(qū)（32K）第三分區(qū)（64K）第四分區(qū)（112K）（a）內(nèi)存分配示意圖分區(qū)號起始地址分區(qū)大小狀態(tài)140K8K0248K32K1380K64K04144K112K1圖3-4固定分區(qū)存儲管理(b)固定式分區(qū)說明3.2.2可變式分區(qū)存儲管理

可變式分區(qū):又叫動態(tài)分區(qū)是指在作業(yè)裝入時，根據(jù)它對內(nèi)存空間實際的需求量來劃分主存的分區(qū)，因此，每個分區(qū)的尺寸與進入它的作業(yè)大小相同。它能有效解決固定式分區(qū)的內(nèi)部碎片問題。

舉例:如圖3-5所示，假設(shè)某系統(tǒng)采用可變式分區(qū)存儲管理3.2簡單的存儲管理3.2.2可變式分區(qū)存儲管理256K256K操作系統(tǒng)空閑分區(qū)操作系統(tǒng)作業(yè)一(48K)作業(yè)二(24K)作業(yè)三(38K)作業(yè)四(40K)空閑(50K)操作系統(tǒng)空閑1(48K)作業(yè)二(24K)空閑2(38K)作業(yè)四(40K)空閑3(50K)206K166K128K104K56K0K0K206K166K128K104K56K0K（a）可變式分區(qū)運行開始(b)作業(yè)1.2.3.4進入（c）作業(yè)1.3釋放后圖3-5可變式分區(qū)內(nèi)存使用情況示意圖3.2.2可變式分區(qū)存儲管理

1．空閑分區(qū)的組織形式常把空閑區(qū)組成空閑分區(qū)表或空閑分區(qū)鏈表的形式2．內(nèi)存的分配與回收

當(dāng)作業(yè)請求存儲空間時,檢索空閑區(qū),分配相應(yīng)的空間

當(dāng)作業(yè)完成并釋放所占分區(qū)時，系統(tǒng)應(yīng)進行回收。若回收區(qū)與內(nèi)存中前后空閑區(qū)相鄰，則合并成一個較大的空閑區(qū)，并修改相應(yīng)的鏈表指針;若不相鄰，應(yīng)將空閑區(qū)插入到空閑區(qū)鏈表的適當(dāng)位置。3.2簡單的存儲管理3.2.2可變式分區(qū)存儲管理

3．常用的算法常用的分配算法有以下三種：

（1）首次適應(yīng)算法：選擇第一個滿足要求的空閑分區(qū)分配；優(yōu)點是查找速度快

（2）最佳適應(yīng)算法：找到滿足要求的最接近作業(yè)大小的空閑分區(qū)（由小到大存儲）

（3）最差適應(yīng)算法：把空閑區(qū)按大小遞減，總是檢查空閑區(qū)鏈表的第一個空閑區(qū)是否滿足要求。優(yōu)點是查詢簡單3.2簡單的存儲管理3.2.2可變式分區(qū)存儲管理4．分區(qū)管理的地址重定位和存儲器保護（1）地址重定位固定分區(qū)采用靜態(tài)重定位；可變式分區(qū)采用動態(tài)重定位。實現(xiàn)方法是設(shè)置基址（或重定位）寄存器

（2）存儲器保護

實現(xiàn)方法是：系統(tǒng)可以增設(shè)一個限長寄存器，用來存放運行程序的大小。若地址在范圍內(nèi)，正常運行；若不在，產(chǎn)生地址越界中斷，終止程序運行3.2簡單的存儲管理3.2.2可變式分區(qū)存儲管理5．分區(qū)管理的優(yōu)缺點主要優(yōu)點有：1）實現(xiàn)了多道程序共享主存。2）系統(tǒng)設(shè)計相對簡單，不需要更多的軟、硬件開銷。3）存儲保護的手段比較簡單。主要缺點有：1）主存利用不夠充分。2）沒有實現(xiàn)主存的擴充。3.2簡單的存儲管理3.2.3覆蓋與交換技術(shù)1．覆蓋（Overlay）

覆蓋:是指同一主存區(qū)可以被不同的程序段重復(fù)使用。

覆蓋段:可以相互覆蓋的程序段覆蓋區(qū):可共享的主存區(qū)覆蓋段與覆蓋區(qū)一一對應(yīng)。覆蓋的基本原理可用圖3-6所示例子說明

作用:解決了小主存運行大進程的矛盾，在邏輯上擴充了主存，3.2簡單的存儲管理3.2簡單的存儲管理主程序（60K）子程序1（25K）子程序2（35K）子程序11(20K)子程序21（25K）子程序22

（15K）主程序（60K）覆蓋區(qū)1（35K）覆蓋區(qū)2（25K）常駐段覆蓋段0覆蓋段1（a）程序內(nèi)部結(jié)構(gòu)（b）內(nèi)存圖3-6用戶程序的覆蓋結(jié)構(gòu)3.2.3覆蓋與交換技術(shù)2．交換（Swapping）

交換:就是系統(tǒng)根據(jù)需要把主存中暫時不運行的某個（或某些）進程中的部分或全部信息移到外存，而把外存中的某個（或某些）進程移到相應(yīng)的主存區(qū)，并使其投入運行。

交換通常在以下情況下發(fā)生：1）進程用完分配的時間片或等待輸入／輸出時；2）進程要求擴充其占用的存儲區(qū)卻得不到滿足時。

3.2簡單的存儲管理3.3.1分頁存儲管理的基本思想

分頁存儲管理的基本思想是:把內(nèi)存空間分成大小相等、位置固定的若干個小分區(qū)，每個小分區(qū)稱為一個存儲塊，簡稱塊，并依次編號為0,1,2,3…n塊，每個存儲塊的大小由不同的系統(tǒng)決定，一般是2的n次冪，如1K，2K，4K等，通常不超過4K。而把用戶的邏輯地址空間分成與存儲塊大小相等的若干頁，依次為0，1，2，3，…m頁。作業(yè)按存儲塊大小劃分為若干頁

3.3分頁存儲管理3.3.1分頁存儲管理的基本思想

簡單分頁存儲管理:作業(yè)一次全部裝入內(nèi)存

請求式分頁存儲管理:根據(jù)作業(yè)運行時的實際要求裝入

3.3分頁存儲管理3.3.2主存分配原則系統(tǒng)以存儲塊為單位把主存分給作業(yè)或進程,并且分給一個作業(yè)的各存儲塊，不一定是相鄰和連續(xù)的。3.3.3頁表和頁表地址寄存器系統(tǒng)為每個裝入主存的作業(yè)建立一張相應(yīng)的頁表，如圖3-7所示。它的起始地址及大小保存在該作業(yè)中。一旦這個作業(yè)被調(diào)度執(zhí)行，即把它的頁表始址及大小裝入特定頁表寄存器中。

3.3分頁存儲管理頁號塊號存取控制021325圖3-7頁表3.3.4簡單分頁存儲管理

1．主存的分配與回收頁表:如圖3-7所示。存儲分塊表：整個系統(tǒng)一張表2．分配算法首先分配設(shè)置頁表，將分到的主存塊號添入頁表中

3．地址變換采用重定位寄存器方式

3.3分頁存儲管理3.3分頁存儲管理邏輯地址物理地址02132524525LOAD1,2500DATA頁號塊號45221485572內(nèi)存圖3-8分頁動態(tài)地址變換下面從兩個例子來說明地址變換過程。如圖3-8、3-9和3-10所示3.3分頁存儲管理2K0K1K3K2K作業(yè)一0K0頁1頁0頁1頁2頁作業(yè)二1K頁號塊號05180617210

空閑作業(yè)1（0頁）作業(yè)2（0頁）作業(yè)2（1頁）作業(yè)1（1頁）空閑作業(yè)2（2頁）

空閑圖3-9簡單分頁存儲管理示意圖3.3分頁存儲管理圖3-10簡單分頁存儲管理地址轉(zhuǎn)換實現(xiàn)過程塊內(nèi)地址w塊號p000010011100010000101001110001000172106頁號p頁內(nèi)地址w026815塊號頁號W=1C4H09C4H29C4H

內(nèi)存3.3.5聯(lián)想存儲器

從上面介紹的地址變換過程可以看出：如果把頁表全部放在內(nèi)存，那么存取一個數(shù)據(jù)時，至少要訪問兩次內(nèi)存。一次是訪問頁表，形成實際內(nèi)存地址；另一次是根據(jù)形成的內(nèi)存地址存取數(shù)據(jù)。為了提高查表的速度，人們在分頁地址變換機構(gòu)中加入一組高速緩沖存儲器，用來存放當(dāng)前作業(yè)最常用的頁號和與之相應(yīng)的物理塊號。通常稱這樣的寄存器組為快表或聯(lián)想存儲器。工作原理見圖3-11

3.3分頁存儲管理3.3分頁存儲管理圖3-11采用快表和頁表相結(jié)合的分頁地址變換過程示意圖②物理地址①①③②a頁表始地址寄存器pw頁號塊號pb頁號塊號pbbw邏輯地址聯(lián)想寄存器頁表1）利用快表查找2）利用頁表查找3）利用頁表中查找的頁號、塊號更新塊表3.3.6存儲保護1.在進行地址變換時，產(chǎn)生的頁號應(yīng)小于頁表長度，否則視為越界訪問，這類似于基址限長存儲保護；2.在頁表中增加存取控制和存儲保護的信息，對每一個存儲塊，可允許四種保護方式：①禁止做任何操作，②只能執(zhí)行，③只能讀，④能讀／寫，當(dāng)要訪問某頁時，先判斷該頁的存取控制和存儲保護信息是否允許。

3.3分頁存儲管理頁號塊號存取控制信息3.3.7簡單分頁存儲管理的優(yōu)缺點

最大優(yōu)點:是有效解決碎片問題，主存利用率高，內(nèi)存分配與回收算法也比較簡單

缺點:是采用動態(tài)地址變換機構(gòu)增加了硬件成本，也降低了處理機速度。

3.3分頁存儲管理3.4.1請求分頁存儲管理的地址變換

解決兩個問題:1.要訪問的某頁不在內(nèi)存時，如何發(fā)現(xiàn)這種缺頁情況？發(fā)現(xiàn)后應(yīng)如何處理？

解決:增加一個狀態(tài)位和當(dāng)前頁在輔存的地址。狀態(tài)位用以表示當(dāng)前頁是否在內(nèi)存中。

2．當(dāng)需要把外存上的某個頁面調(diào)入內(nèi)存時，此時內(nèi)存中沒有空閑塊應(yīng)怎么辦？

解決:頁面置換

3.4請求分頁存儲管理圖3-12是請求式分頁存儲管理的存儲映像。

3.4請求分頁存儲管理0…1…2…3412……461010頁號輔存地址狀態(tài)位塊號作業(yè)1其他作業(yè)MoveR1作業(yè)1圖3-12請求式分頁存儲管理示意圖頁號內(nèi)存塊號狀態(tài)位改變位引用位輔存地址存取控制其他頁表的表目3.4.2頁面置換算法1．最優(yōu)算法（OPT算法）：如圖(a)選擇距下次被引用時間間隔最大的頁來淘汰2．先進先出算法（FIFO算法）：如圖(b)3．最久未使用頁面置換算法（LRU算法）：如圖(c)所示,把到目前為止最長時間沒有被使用的頁淘汰;近似的LRU算法：如圖(d)所示4．時鐘算法時鐘算法是尋找一個從上次檢查以來沒有被訪問過的頁面3.4請求分頁存儲管理2321524532522222224442223333333333315

5555555FFF2222315522433331522443515

2443352FFFFFF2222315245333331524532515

2453252FFFFF22223152433333315243225152455552FFFFF（a）最佳算法（b）先進先出算法（c）最近最久未使用算法（d）近似的LRU算法圖不同淘汰算法對同一頁面請求序列的效果3.4.3請求頁式存儲管理的特點

1.請求頁式管理的優(yōu)點

1）由于它不要求作業(yè)或進程的程序段和數(shù)據(jù)在主存中連續(xù)存放，從而有效地解決了碎片問題。

2）請求分頁管理提供了虛擬存儲器。提高了主存的利用率，有利于多道程序的運行和方便用戶，特別是大作業(yè)用戶。3.4請求分頁存儲管理3.4.3請求頁式存儲管理的特點

2．請求頁式管理的缺點

1）必須有相應(yīng)的硬件支持。

2）為處理缺頁中斷，增加了處理機時間的開銷

3）可能因作業(yè)地址空間的過大或多道程序的道數(shù)過多，以及其他原因而造成系統(tǒng)抖動，

4）雖然消除了碎片，但每個作業(yè)或進程的最后一頁內(nèi)存總還有一部分空間得不到利用。3.4請求分頁存儲管理3.5.1分段管理的基本思想

基本思想:在分段存儲管理中，作業(yè)的地址空間由若干個邏輯分段組成，每一分段是一組邏輯意義完整的信息集合，并有自己的名字（段名）。每一段都是以0開始的連續(xù)的一維地址空間,整個作業(yè)則構(gòu)成了二維地址空間分段存儲管理是以段為基本單位分配內(nèi)存，且每一段必須在連續(xù)的內(nèi)存空間中，但各段之間不要求連續(xù)。

分段存儲管理的邏輯地址結(jié)構(gòu)如下：3.5分段存儲管理段號S段內(nèi)位移W3.5.2地址變換為了實現(xiàn)段的邏輯地址到物理地址的轉(zhuǎn)換，系統(tǒng)為每個作業(yè)設(shè)置了一張段表SMT。每個表目至少有4個數(shù)據(jù)項：段號、段長、內(nèi)存始址和存取控制。分段存儲管理系統(tǒng)的地址變換過程如圖3-15所示。

3.5分段存儲管理3.5分段存儲管理段表起始地址段表長度段號段長hang1內(nèi)存始址08001231K6502K60008000400010K24004400<<段號段內(nèi)位移邏輯地址越界中斷物理地址段表控制寄存器圖3-15分段存儲管理的地址變換示意圖3.5.2地址變換例如：在一個分段存儲管理系統(tǒng)中，其段表如表3-1所示。求表3-2中所示邏輯地址對應(yīng)的物理地址。

3.5分段存儲管理段號內(nèi)存起始地址段長02105001235020210090表3-1段表段號段內(nèi)位移04301102500表3-2邏輯地址分析：在由表3-1可知，段號為0的段的內(nèi)存地址起始地址為210，段長為500。由表3-2知，邏輯地址的段內(nèi)位移為430。因為400<500，所以該邏輯地址是合法的。其對應(yīng)的物理地址為：210+430=640

3.5分段存儲管理由表3-1知，段號為1的段的內(nèi)存起始地址為2350，段長為20。由表3-2知，邏輯地址的段內(nèi)位移為10。因為10<20，所以該邏輯地址是合法的。其對應(yīng)的物理地址為：2350+10=2360。

由表3-1知，段號為2的段的內(nèi)存起始地址為100，段長為90。由表3-2知，邏輯地址的段內(nèi)位移為500。因為500>90即邏輯地址的段內(nèi)位移500已經(jīng)超過了段長90，所以該邏輯地址是非法的。

3.5.3段的共享與保護

1.段的共享:

用戶使用相同的段名并置以適當(dāng)?shù)淖x寫控制權(quán),即可共享

2.分段存儲管理系統(tǒng)的保護措施：

1）在段表中設(shè)置一個段長值。當(dāng)存儲訪問時，將段地址的位移量與段長進行比較2）在段表的每個表目中建立存取控制3）采用存儲保護鍵

3.5分段存儲管理3.5.4分段與分頁的區(qū)別（1）頁是信息的物理單位。分頁的目的是實現(xiàn)離散分配，減少內(nèi)存的外零頭，提高內(nèi)存利用率。段是信息的邏輯單位。每一段在邏輯上是一組相對完整的信息。（2）分頁存儲管理的作業(yè)地址空間是一維的，而分段存儲管理的作業(yè)地址空間是二維的。（3）頁的大小固定且由系統(tǒng)確定，是等長的。而段的長度不定，它是由具有相對完整意義的信息長度確定。（4）分頁的優(yōu)點體現(xiàn)在內(nèi)存空間的管理上，而分段的優(yōu)點體現(xiàn)在地址空間的管理上。

3.5分段存儲管理3.5.5段式存儲管理的優(yōu)缺點

1.段式管理的主要優(yōu)點如下：

（1）便于程序模塊化處理和便于處理變換的數(shù)據(jù)結(jié)構(gòu)。（2）便于動態(tài)連接。（3）便于共享分段。（4）可以實現(xiàn)虛擬存儲器，使作業(yè)的地址空間不受主存容量的限制。

3.5分段存儲管理3.5.5段式存儲管理的優(yōu)缺點

2.段式管理的主要缺點如下：（1）和分頁管理一樣，處理機要為地址變換花費時間；要為表格提供附加的存