第七章主存管理（一）主存的共享方式（二）主存管理的功能（三）分區存儲管理技術（四）頁式存儲管理技術（五）段式及段頁式存儲管理技術2計算機系統存儲結構內存管理的目的操作系統的“方便”性便于用戶裝入程序，無須了解底層細節可實現動態的存儲空間伸縮，適應不同程序的需要操作系統的“合理”性合理分配內存空間，保證多道程序的順利運行合理保護內存空間，防止各種可能的破壞泄漏操作系統的“有效性”有效保持內存空間的可用性，防止對資源的浪費有效實現“小空間大容量”，提高計算機的適應性有效配合CPU的調度過程，實現系統運行的穩定（一）主存的共享方式內存儲器（簡稱內存、主存、物理存儲器）處理機能直接訪問的存儲器。用來存放系統和用戶的程序和數據，其特點是存取速度快，斷電信息丟失。主存的共享方式包含三種：

大小不等的區域——

分區存儲管理 分段存儲管理大小相等的片——

頁式存儲管理兩者結合 ——

段頁式存儲管理（二）主存管理的功能一.幾個概念1、物理地址（絕對地址、實地址）：把內存分成若干個大小相等的存儲單元，每個單元給一個編號，這個編號稱為內存地址，是計算機主存單元的真實地址。存儲單元占8位，稱作字節（byte）。2.物理地址空間：物理地址的集合稱為物理地址空間（主存地址空間），它是一個一維的線性空間。3.邏輯地址（相對地址、虛地址）:用戶編程序時所用的地址?；締挝豢膳c內存的基本單位相同，也可以不相同。4.邏輯地址空間（作業地址空間、虛地址空間）:用戶的程序地址的集合稱為邏輯地址空間，它的編址總是從0開始的。作業地址空間01n-1二.主存管理的功能1.地址映射

將程序地址空間中使用的邏輯地址變換成主存中的地址的過程。2.主存分配

按照一定的算法把某一空閑的主存區分配給作業或進程。3.存儲保護

保證用戶程序(或進程映象)在各自的存儲區域內操作，互不干擾。4.主存擴充（提供虛擬存儲技術）

向用戶提供一種不受物理存儲器大小和結構限制的用戶編程時使用的存儲器。即使在用戶程序比主存容量還要大的情況下，程序也能正確運行。1.主存功能——地址映射主存空間01m-1作業1地址空間01n-1作業i地址空間01k-1┆

┆（1）為什么要進行地址映射

作業的相應進程在處理機上運行時，所要訪問的指令和數據的物理地址和作業地址空間中的地址是不同的。movr1,[500]123movr1,[500]123010050059901000110015001599256k-1作業地址空間存儲空間將500號單元處的數據123送到寄存器r1中（2）地址映射的定義

將程序地址空間中使用的邏輯地址變換成主存中的地址的過程稱為地址映射。有時也稱為地址重定位。

（3）地址映射的方式編程或編譯時確定地址映射關系靜態地址映射動態地址映射靜態地理映射定義：

在作業裝入過程中隨即進行的地址變換方式稱為靜態重定位或靜態地址映射。movr1,[500]123movr1,[500+m]12301005005990mm+100256k-1作業地址空間存儲空間m+500重定位裝入程序動態地址映射定義：在程序運行時確定地址映射關系。在程序執行期間，隨著每條指令和數據的訪問自動地連續地進行地址映射。movr1,[500]1230100500599作業地址空間0

movr1,[500]1231000256k-1存儲空間110015001600重定位寄存器

1000500邏輯地址+靜態地址映射與動態地址映射的區別靜態地址映射動態地址映射在作業裝入過程中進行地址映射在程序執行期間進行地址映射需軟件變換機構重定位裝入程序需硬件地址變換機構重定位裝入程序需花費較多CPU時間地址變換快不靈活靈活構造分配用的數據結構

主存資源信息塊（M_RIB）、空閑區隊列等等制定分配策略

2、主存功能——主存分配實施主存分配與回收主存擴充也就是提供虛擬存儲器

1）問題的提出3、主存擴充

物理存儲器容量是有限的，用戶程序的大小，可能比內存容量小，也可能比內存容量大，有時候要大得多。在主存容量十分緊張的情況下， 如何讓用戶使用計算機不受主存容量的限制？2）解決問題的思路

裝入部分程序地址空間，它還能正確地執行？3）實現方法

程序的全部代碼和數據存放在輔存中；

將程序當前執行所涉及的那部分程序代碼放入主存中；

程序執行時，當所需信息不在主存，由操作系統和硬件相配合來完成主存從輔存中調入信息，程序繼續執行。

4.什么是虛擬存儲器

由操作系統和硬件相配合來完成主存和輔存之間的信息的動態調度。這樣的計算機系統好像為用戶提供了一個其存儲容量比實際主存大得多的存儲器（虛擬存儲器）。5.虛擬存儲器的核心

邏輯地址與物理地址分開

主存空間與地址空間分開

提供地址變換機構

6.實現虛擬存儲器的物質基礎

有相當容量的輔存

足以存放多用戶的作業的地址空間

有一定容量的主存

存放運行進程的當前信息

地址變換機構4、存儲保護1）什么是存儲保護

在多道程序設計的環境下，系統中有系統程序和多個用戶程序同時存在，如何保證用戶程序不破壞系統程序，用戶程序之間不相互干擾？

——主存儲器按區分配給各用戶程序使用。為了互不影響，由硬件(軟件配合)保證每道程序只能在給定的存儲區域內活動，這種措施叫做存儲保護。2）存儲保護方法

通常的存儲保護方法——

界地址保護和存儲鍵保護（不介紹）

(1)上、下界防護

movr1,[500]123020KB256KB1存儲空間24KB下界寄存器

20KB上界寄存器

24KB下界寄存器：存放程序裝入內存后的開始地址上界寄存器：存放程序裝入內存后的末地址判別式：下界寄存器≤物理地址＜上界寄存器

(2)基地址、限長防護

movr1,[500]123020KB256KB1存儲空間24KB基址寄存器

20KB限長寄存器

4KB基址寄存器=下界寄存器

（首地址）限長寄存器：存放程序長度基址+限長=上界寄存器

（末地址）∴判別式：基址寄存器≤物理地址＜基址+限長寄存器23作業第7章

第2題（三）分區存儲管理分區存儲管理分為：1.固定分區2.動態分區（可變分區）25固定分區固定分區一.動態分區分配1.什么是動態分區分配

在處理作業的過程中，建立分區，依用戶請求的大小分配分區。思想：分區的大小、數量和位置隨內存中進程的大小和數量動態變化（根據作業的實際需要在裝入內存時動態地分配連續的內存空間）。

(1)動態分區的分配過程20KB

0

os

作業1

作業2

作業3

作業4

52KB66KB130KB230KB256KB1主存20KB

0

os

作業1

作業2

作業3

52KB66KB130KB256KB1主存20KB

0

os

作業1

52KB256KB1主存

0

os

256KB1主存20KB20KB

0

os

作業1

作業2

52KB66KB256KB1主存作業1申請

32KB作業2申請

14KB作業3申請

64KB作業4申請

100KB作業5申請

50KB

(2)動態分區的回收過程20KB

0

os

作業1

作業2

作業3

作業4

52KB66KB130KB230KB256KB1主存20KB

0

os

作業1

作業3

作業4

52KB66KB130KB230KB256KB1主存作業2完成作業4完成20KB

0

os

作業1

作業3

52KB66KB130KB230KB256KB1主存292、分區分配機構

1)主存資源信息塊在動態分區方法中，描述主存資源的數據結構是主存資源信息塊等待隊列指針空閑區隊列指針主存分配程序入口指針2)分區描述器和空閑隊列主存中的每一個分區都有相應的分區描述器（pd）說明分區的特征信息。flag：為0—空閑區;為1—已分配區size：分區大小next：空閑區—自由主存隊列中的勾鏈字;已分配區—此項為零m_ribpd分配標志flag分區大小size勾鏈字next30自由主存隊列(或空閑區隊列)結構在主存分配中，主要討論空閑區描述器和空閑區隊列。下面是在t時刻的主存分布、空閑區描述器的內容和空閑區隊列結構。

020KB

os

作業1

作業3

作業4

52KB66KB130KB230KB256KB1主存52KBm-rib

014KB230KB

026KB

空閑區隊列結構 空閑區表的組織有兩種方法：

1、按空閑區大小的升序（降序）組織；

2、按空閑區首址升序（降序）組織。3、分區的分配與放置策略1）分區分配

?

用戶請求分配一個主存塊

?

分區分配程序在自由主存隊列中找一個滿足用戶需要的空閑塊

?

若找到，則返回所分配區域的首址，否則，告之不能滿足要求。2）放置策略

選擇空閑區的策略，稱為放置策略。

空閑區表的組織有兩種方法：

1、按空閑區大小的升序（降序）組織；

2、按空閑區首址升序（降序）組織。

根據空閑區表組織的方法的不同，有不同的放置策略：首次適應算法、最佳適應算法和最壞適應算法三種。33

1）首次適應算法

空閑區按起始地址遞增的順序排列，將作業放到最先找到的空閑分區。34

2）最佳適應算法

空閑區按由小到大的順序排列，將作業放到滿足要求的最小的空閑分區。

35

3）最壞適應算法

空閑區按由大到小的順序排列，將作業放到滿足要求的最大的空閑分區。幾種放置策略的比較

例如：某時刻系統中有三個空閑區，其大小和首址為：(35KB，100KB)、(12KB，156KB)、(28KB，200KB)

有一作業系列：

(JOB1，12KB)、(JOB2，30KB)、(JOB3，28KB)

用首次適應算法、最佳適應算法和最壞適應算法來處理該作業序列，看哪種算法合適？注：設分配時從空閑區的高地址分割，以保持剩余空閑區的起始地址不變。

os在使用在使用在使用在使用12KB28KB0KB100KB35KB156KB200KB228KB-1035KB156KB首次適應算法012KB200KB028KBNULL100KB作業1（12KB）放到首址100KB的空閑區023KB156KB012KB200KB028KBNULL100KB作業2（30KB）不能分配作業3（28KB）放到首址200KB的空閑區012KB200KB最佳適應算法028KB100KB035KBNULL156KB作業1（12KB）放到首址156KB的空閑區028KB100KB035KBNULL200KB作業2（30KB）放到首址100KB的空閑區作業3（28KB）放到首址200KB的空閑區05KB200KB028KBNULL100KB035KB200KB最壞適應算法028KB156KB012KBNULL100KB作業1（12KB）放到首址100KB的空閑區作業2（30KB）不能繼續分配作業3（28KB）放到首址200KB的空閑區028KB100KB023KB156KB012KBNULL200KB四、碎片問題及拼接技術1.什么是碎片問題

在已分配區之間存在著的一些沒有被充分利用的空閑區。

如何解決碎片問題？2.拼接技術

所謂拼接技術是指移動存儲器中某些已分配區中的信息，使本來分散的空閑區連成一個大的空閑區。41OS400KBJOB1(100KB)JOB2(200KB)0300KBJOB6(100KB)800KB700KB900KBJOB5(100KB)JOB4(100KB)JOB7(100KB)600KB1000KB1024KBOS400KBJOB2(200KB)0300KBJOB6(100KB)800KB700KB900KBJOB5(100KB)JOB4(100KB)JOB7(100KB)600KB1000KB空閑(24KB)1024KB空閑(100KB)OS400KBJOB2(200KB)0300KB800KB700KB900KBJOB5(100KB)JOB7(100KB)600KB1000KB空閑(24KB)1024KB空閑(100KB)空閑(100KB)空閑(100KB)有一大小為200K的作業需要運行!!!空閑(24KB)分區管理的優缺點優點：實現了多道程序共享主存。實現分區管理的系統設計相對簡單，不需要更多的系統軟硬件開銷。實現存儲保護的手段也比較簡單。缺點：主存利用不夠充分。系統中總有一部分存儲空間得不到利用，這部分被浪費的空間叫碎片。沒有實現主存的擴充問題。當作業的地址空間大于存儲空間時，作業無法運行。也即作業的地址空間受實際存儲空間限制。（四）頁式存儲管理一.問題的提出

分區存儲管理的主要問題是碎片問題。

在采用分區存儲管理的系統中，會形成一些非常小的分區，最終這些非常小的分區不能被系統中的任何用戶（程序）利用而浪費。

造成這樣問題的主要原因是用戶程序裝入內存時是整體裝入的，為解決這個問題，提出了分頁存儲管理技術。二.頁式系統的基本概念1.頁面

程序的地址空間被等分成大小相等的片，稱為頁面，又稱為虛頁。2.主存塊

主存被等分成大小相等的片，稱為主存塊，又稱為實頁。

作業頁面與主存塊的關系02KB4KB254KB256KB102KB4KB6KB0頁1頁2頁3頁主存作業地址空間頁表地址映射3.頁表（1）什么是頁表

為了實現從地址空間到物理主存的映象，系統建立的記錄頁與內存塊之間對應關系的地址變換的機構稱為頁面映像表，簡稱頁表。包括用戶程序空間的頁面與內存塊的對應關系、頁面的存儲保護和存取控制方面的信息。01KB01KB2KB3KB1主存作業2地址空間2KB3KB4KB5KB6KB7KB8KB9KB10KB101KB2KB1作業1地址空間01KB1作業3地址空間0516頁號塊號02140827作業1頁表作業2頁表作業3頁表osos三.頁式地址變換1.虛地址結構

虛地址是用戶程序中的邏輯地址，它包括頁號和頁內地址（頁內位移）。

區分頁號和頁內地址的依椐是頁的大小，頁內地址占虛地址的低位部分，頁號占虛地址的高位部分。

【例】設虛地址長度為16位，頁面大小為1KB： 頁號頁內地址（位移量）

PW

15109049如何方便將邏輯地址線性分割求出頁號P和頁內位移W：邏輯地址以十進制數給出：

頁號P=邏輯地址%頁大小 頁內位移W=邏輯地址mod頁大小邏輯地址以十六進制、八進制、二進制的形式給出：將邏輯地址轉換成二進制；按頁的大小分離出頁號P和位移量W（低位部分是位移量，高位部分是頁號）；50【例】：有一系統采用頁式存儲管理，有一作業大小是8KB，頁大小為2KB。解：求虛地址3412P＝3412％2048＝1W＝3412mod2048＝1364求虛地址7145：P＝7145％2048＝3W＝7145mod2048＝100151【例】：有一系統采用頁式存儲管理，有一作業大小是8KB，頁大小為2KB。虛地址0AFEH：0000

101011111110P＝1W＝01011111110虛地址1ADDH：0001101011011101P＝3W＝01011011101例1頁面大小是1KB，虛地址是3BADH例2頁面大小是2KB，虛地址是3BADH532、地址變換根據邏輯地址求物理地址的步驟：1）將邏輯地址線性分割求出頁號P和頁內位移W：2）根據頁號查頁表得塊號B；3）物理地址=塊號B×頁大小+頁內位移W54頁表始址寄存器movr1,[2500]12301KB2KB3KB1作業2地址空間+021427頁表0000100111000100151090頁號頁內位移W250001KB主存2KB3KB4KB5KB6KB7KB8KB9KB10KB1ososmovr1,[2500]123第1頁塊號塊內位移W

15109000011101110001007×1024+452=762055【例】：有一系統采用頁式存儲管理，有一作業大小是8KB，頁大小為2KB，依次裝入內存的第7、9、10、5塊，試將虛地址7145，3412轉換成內存地址。解：求虛地址3412P＝3412％2048＝1W＝3412mod2048＝1364MR=9*2048+1364=19796求虛地址7145：P＝7145％2048＝3W＝7145mod2048＝1001MR=5*2048+1001=1124156【例】：有一系統采用頁式存儲管理，有一作業大小是8KB，頁大小為2KB，依次裝入內存的第7、9、A、5塊，試將虛地址0AFEH，1ADDH轉換成內存地址。解：求虛地址0AFEH的物理地址：0000

101011111110P＝1W＝01011111110MR＝0100

1010

11111110＝4AFEH求虛地址1ADDH的物理地址：0001101011011101P＝3W＝01011011101MR＝00101010

11011101＝2ADDH57課堂練習：1、某作業J的邏輯空間為4頁，每頁2048B，已知該作業J的頁表如下： 頁號：0123

塊號：2468

求：邏輯地址為0A65H的物理地址。2、某作業有4個頁面，分別裝入主存的3、4、6、8塊中，設頁面尺寸為1024B（1）、寫出該作業的頁表；（2）、求mov2100,3100指令中兩個操作數的物理地址。四.請調策略1、請調策略定義：

在頁式系統中，允許一個作業程序只裝入部分頁面即可投入運行，需要信息時動態調入，這種裝入信息的策略稱為請調策略。

(1)怎樣發現所訪問的頁面在不在主存？

(2)當發現所需訪問的頁面不在主存時如何處理?2.擴充頁表功能

中斷位i——標識該頁是否在主存 若i=1，表示此頁不在主存 若i=0，表示該頁在主存

輔存地址——該頁面在輔存的位置

頁號主存塊號中斷位輔存地址

3.缺頁處理過程（舉例說明）

01KB主存2KB3KB4KB5KB6KB7KB8KB9KB10KB102142作業2頁表osos作業2第1頁作業2第0頁3頁號輔存地址中斷位塊號

0011地址地址地址地址01KB2KB4KB1作業2地址空間movr1,[2120]addr1,[3410]006251

006802

3KB作業2的主存塊數為m2=3，頁面大小為1KB。

當程序執行“movr1，[2120］”時

CPU產生的虛地址為2120分頁機構得p=2，w=72

查頁表。該頁中斷位i=1，則發生缺頁中斷01KB2KB4KB1作業2地址空間movr1,[2120]addr1,[3410]006251

006802

3KB

如主存中有空白塊，且nm則直接調入如主存中無空白塊，或n

m，則需淘汰該作業在主存中的一頁（其中n代表作業已分配到的主存塊數，m為內存為作業準備的物理塊數）。缺頁處理流程

啟動要處理的指令給出虛地址

得到頁號該頁在主存?有空閑塊?

缺頁中斷執行完該指令

準備執行下條指令選一頁淘汰

從外存讀入所需的頁

調整存儲分配表和頁表

重新啟動被中斷的指令

調整存儲分配表和頁表要重寫入?該頁寫入外存YNNY硬件軟件YN4.淘汰策略1.什么是淘汰策略

用來選擇淘汰哪一頁的規則就叫做置換策略，或稱淘汰算法。常用算法：1、最優算法OPT:(optimalreplacementalgorithm)置換在最長時間內不會使用的頁)2、先進先出算法FIFO：淘汰先調入內存的頁3、最近最少使用淘汰算法LRU：淘汰未被訪問的頁中時間最長的頁;(LeastRecentlyUsed)

使用缺頁中斷率f’衡量頁面淘汰算法的優劣：

f’＝f／a（a是總的頁面訪問次數，f是缺頁中斷次數）2.擴充頁表的功能頁表應增加相應的內容，反映該頁是否在內存，在外存的位置，在內存的時間的長短等。

引用位：0表示最近沒有進程訪問

1表示最近有進程訪問

改變位：0該頁調入內存后沒有修改

1該頁調入內存后修改過頁號主存塊號中斷位輔存地址改變位引用位3.顛簸顛簸(thrashing)，又稱為“抖動”。

簡單地說，導致系統效率急劇下降的主存和輔存之間的頻繁頁面置換現像稱為“抖動”。

OPT原理（難實現）：當要調入一新頁而必須先淘汰一舊頁時，所淘汰的那一頁應是以后不再要用的，或者是在最長的時間以后才會用到的那頁。

缺頁率

假定程序p共有n頁，系統分配m塊，有1≤m≤n若程序p在運行中:成功的訪問次數：s

不成功的訪問次數：f

則缺頁中斷率：f′=f/(s+f)*100%f′=f(r，m，p)

4.頁面置換算法——OPT算法例：假設系統為某進程分配了3個物理塊，并考慮有以下的訪問串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1，求缺頁率。7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1缺頁率f′=(9/20)*100%=45%

(2)先進先出淘汰算法(FIFO算法)1)什么是先進先出淘汰算法原理：總是選擇在主存中居留時間最長(即最老)的一頁淘汰。

2)先進先出淘汰算法的實現方法

建立一個頁面進入主存的先后次序表；

建立一個替換指針，指向最早進入主存的頁面；

當需要置換一頁時，選擇替換指向的那一頁，然

后調整替換指針的內容。69【例】某進程的頁面訪問序列：1、2