操作系統(tǒng)課件-07主存管理

第七章主存管理（一）主存的共享方式（二）主存管理的功能（三）分區(qū)存儲管理技術(shù)（四）頁式存儲管理技術(shù)（五）段式及段頁式存儲管理技術(shù)計算機(jī)系統(tǒng)存儲結(jié)構(gòu)（了解）（一）主存的共享方式內(nèi)存儲器（簡稱內(nèi)存、主存、物理存儲器）處理機(jī)能直接訪問的存儲器。用來存放系統(tǒng)和用戶的程序和數(shù)據(jù)，其特點是存取速度快，斷電丟失。主存的共享方式包含三種：分區(qū)存儲管理（重點） 頁式存儲管理（重點）段頁式存儲管理（現(xiàn)代操作系統(tǒng)使用的）(二)主存管理的功能1.地址映射

邏輯地址變換成物理地址2.主存分配

按照一定的算法把某一空閑的主存區(qū)分配給進(jìn)程。3.存儲保護(hù)

保證用戶程序(或進(jìn)程映象)在各自的存儲區(qū)域內(nèi)操作，互不干擾。4.主存擴(kuò)充（提供虛擬存儲技術(shù)）

向用戶提供一種不受物理存儲器大小和結(jié)構(gòu)限制的用戶編程時使用的存儲器。即使在用戶程序比主存容量還要大的情況下，程序也能正確運行。物理地址（絕對地址、實地址）：把內(nèi)存分成若干個大小相等的存儲單元，每個單元給一個編號，這個編號稱為內(nèi)存地址，是計算機(jī)主存單元的真實地址。存儲單元占8位，稱作字節(jié)（byte）。物理地址空間：物理地址的集合稱為物理地址空間（主存地址空間），它是一個一維的線性空間。1.主存功能——地址映射邏輯地址（又稱為虛地址）:用戶編程序時所用的地址?；締挝豢膳c內(nèi)存的基本單位相同，也可以不相同。邏輯地址空間（又稱為虛地址空間）:一個用戶程序地址的集合稱為邏輯地址空間，它的編址總是從0開始的。程序地址空間01n-1主存空間01m-1程序1邏輯地址空間01n-1程序i邏輯地址空間01k-1┆

┆為什么要進(jìn)行地址映射

程序的相應(yīng)進(jìn)程在處理機(jī)上運行時，所要訪問的指令和數(shù)據(jù)的物理地址和作業(yè)地址空間中的地址是不同的。movr1,[500]123movr1,[500]123010050059901000110015001599256k-1程序邏輯地址空間存儲空間將500號單元處的數(shù)據(jù)123送到寄存器r1中地址映射的定義

將程序地址空間中使用的邏輯地址變換成主存中的地址的過程稱為地址映射。有時也稱為地址重定位。地址映射的三種方式編程或編譯時確定地址映射關(guān)系靜態(tài)地址映射動態(tài)地址映射靜態(tài)地址映射：

在作業(yè)裝入過程中隨即進(jìn)行的地址變換方式稱為靜態(tài)重定位或靜態(tài)地址映射。movr1,[500]123movr1,[500+m]12301005005990mm+100256k-1作業(yè)地址空間存儲空間m+500重定位裝入程序動態(tài)地址映射定義：在程序運行時確定地址映射關(guān)系。在程序執(zhí)行期間，隨著每條指令和數(shù)據(jù)的訪問自動地連續(xù)地進(jìn)行地址映射。movr1,[500]1230100500599程序邏輯地址空間0

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

1000500邏輯地址+靜態(tài)地址映射與動態(tài)地址映射的區(qū)別靜態(tài)地址映射動態(tài)地址映射在程序裝入過程中進(jìn)行地址映射在程序執(zhí)行期間進(jìn)行地址映射需軟件變換機(jī)構(gòu)重定位裝入程序需硬件地址變換機(jī)構(gòu)重定位裝入程序地址變換慢地址變換快不靈活靈活分配步驟：構(gòu)造分配用的數(shù)據(jù)結(jié)構(gòu)制定分配策略實施主存分配與回收

2、主存功能——主存分配主存擴(kuò)充也就是提供虛擬存儲器

1）問題的提出物理存儲器容量是有限的，用戶程序的大小，可能比內(nèi)存容量小，也可能比內(nèi)存容量大，有時候要大得多。在主存容量十分緊張的情況下， 如何讓用戶使用計算機(jī)不受主存容量的限制？3、主存功能——主存擴(kuò)充2）實現(xiàn)方法

程序的全部代碼和數(shù)據(jù)存放在輔存中；

將程序當(dāng)前執(zhí)行所涉及的那部分程序代碼放入主存中；

程序執(zhí)行時，當(dāng)所需信息不在主存，由操作系統(tǒng)和硬件相配合來完成主存從輔存中調(diào)入信息，程序繼續(xù)執(zhí)行。

3)什么是虛擬存儲器

由操作系統(tǒng)和硬件相配合來完成主存和輔存之間的信息的動態(tài)調(diào)度。這樣的計算機(jī)系統(tǒng)好像為用戶提供了一個其存儲容量比實際主存大得多的存儲器（虛擬存儲器）。

4)實現(xiàn)虛擬存儲器的物質(zhì)基礎(chǔ)

有相當(dāng)容量的輔存

足以存放多用戶的作業(yè)的地址空間

有一定容量的主存

存放運行進(jìn)程的當(dāng)前信息

地址變換機(jī)構(gòu)（邏輯地址物理地址）4、存儲保護(hù)1）什么是存儲保護(hù)

系統(tǒng)中有系統(tǒng)程序（OS）和多個用戶程序同時存在，為了保證用戶程序不破壞系統(tǒng)程序，以及用戶程序之間不相互干擾，由硬件(軟件配合)保證每道程序只能在給定的存儲區(qū)域內(nèi)活動，這種措施叫做存儲保護(hù)。2）常用存儲保護(hù)方法

1、上下界保護(hù)2、基址+限長保護(hù)

(1)上、下界防護(hù)

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

20KB上界寄存器

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

(2)基地址、限長防護(hù)

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

20KB限長寄存器

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

程序越界判別方式：基址寄存器≤物理地址＜基址+限長寄存器作業(yè)第7章

第2題（第一版）（三）分區(qū)存儲管理分區(qū)存儲管理通常分為兩種：1.固定分區(qū)管理2.動態(tài)分區(qū)管理固定分區(qū)：操作系統(tǒng)預(yù)先把內(nèi)存空間分成若干個大小不等的區(qū)域，稱為分區(qū)。根據(jù)用戶程序（作業(yè)）大小調(diào)入其中一個分區(qū)，區(qū)的大小大于程序大小。缺點：內(nèi)存空間浪費太大,且程序并發(fā)度受影響。動態(tài)分區(qū)分配

操作系統(tǒng)在處理程序（作業(yè)）的過程中，依用戶程序（作業(yè)）請求的大小動態(tài)分配分區(qū)。分區(qū)的大小、數(shù)量和位置隨內(nèi)存中程序（作業(yè)）的大小和數(shù)量動態(tài)變化。

(1)動態(tài)分區(qū)的分配過程20KB

0

os

作業(yè)1

作業(yè)2

作業(yè)3

作業(yè)4

52KB66KB130KB230KB256KB1主存20KB

0

os

作業(yè)1

作業(yè)2

作業(yè)3

52KB66KB130KB256KB1主存20KB

0

os

作業(yè)1

52KB256KB1主存

0

os

256KB1主存20KB20KB

0

os

作業(yè)1

作業(yè)2

52KB66KB256KB1主存作業(yè)1申請

32KB作業(yè)2申請

14KB作業(yè)3申請

64KB作業(yè)4申請

100KB作業(yè)5申請

50KB

(2)動態(tài)分區(qū)的回收過程20KB

0

os

作業(yè)1

作業(yè)2

作業(yè)3

作業(yè)4

52KB66KB130KB230KB256KB1主存20KB

0

os

作業(yè)1

作業(yè)3

作業(yè)4

52KB66KB130KB230KB256KB1主存作業(yè)2完成作業(yè)4完成20KB

0

os

作業(yè)1

作業(yè)3

52KB66KB130KB230KB256KB1主存2、動態(tài)分區(qū)分配機(jī)構(gòu)

1)主存資源信息塊（M_RIB）在動態(tài)分區(qū)方法中，描述主存資源的數(shù)據(jù)結(jié)構(gòu)是主存資源信息塊等待隊列指針空閑區(qū)隊列頭指針主存分配程序入口地址2)分區(qū)描述器主存中的每一個分區(qū)都有相應(yīng)的分區(qū)描述器（pd）說明分區(qū)的特征信息。flag：為0—空閑區(qū);為1—已分配區(qū)size：分區(qū)大小next：指向下一個空閑分區(qū)（只對空閑分區(qū)有用）m_ribpd分配標(biāo)志flag分區(qū)大小size勾鏈字next空閑區(qū)隊列結(jié)構(gòu)

020KB

os

作業(yè)1

作業(yè)3

作業(yè)4

52KB66KB130KB230KB256KB1主存52KB空閑隊列頭指針

014KB230KB

026KB

空閑區(qū)隊列結(jié)構(gòu) 空閑區(qū)表的組織有兩種方法：

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

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

?

分區(qū)分配就是在空閑區(qū)隊列中找一個滿足程

序運行需要的空閑塊

?

若找到，則返回所分配區(qū)域的首址，否則，

告之不能滿足要求。2）放置策略

選擇空閑區(qū)的策略，稱為放置策略。

放置策略三種：

首次適應(yīng)算法

最佳適應(yīng)算法

最壞適應(yīng)算法

1）首次適應(yīng)算法

首先把空閑區(qū)隊列按起始地址遞增的順序排列，將作業(yè)放到最先找到的空閑分區(qū)。

2）最佳適應(yīng)算法

首先把空閑區(qū)隊列按分區(qū)大小由小到大的順序排列，將作業(yè)放到滿足要求的最小的空閑分區(qū)。

3）最壞適應(yīng)算法

首先把空閑區(qū)按分區(qū)大小由大到小的順序排列，將作業(yè)放到滿足要求的最大的空閑分區(qū)。

某時刻系統(tǒng)中有三個空閑區(qū)，其大小和首地址分別為：(35KB，100KB)、(12KB，156KB)、(28KB，200KB)

有一作業(yè)隊列，其所需內(nèi)存大小如下：

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

用首次適應(yīng)算法、最佳適應(yīng)算法和最壞適應(yīng)算法來處理該作業(yè)序列，看哪種算法合適？

os在使用在使用在使用在使用12KB28KB0KB100KB35KB156KB200KB228KB-1注：分配時從空閑區(qū)的高地址分割，以保持剩余空閑區(qū)的起始地址不變。例題035KB156KB首次適應(yīng)算法012KB200KB028KBNULL100KB作業(yè)1（12KB）首先放到首址100KB的空閑區(qū)，然后調(diào)整空閑隊列排序023KB156KB012KB200KB028KBNULL100KB作業(yè)2（30KB）不能分配作業(yè)3（28KB）放到首址200KB的空閑區(qū)012KB200KB最佳適應(yīng)算法028KB100KB035KBNULL156KB028KB100KB035KBNULL200KB作業(yè)2（30KB）放到首址100KB的空閑區(qū)作業(yè)3（28KB）放到首址200KB的空閑區(qū)05KB200KB028KBNULL100KB作業(yè)1（12KB）首先放到首址156KB的空閑區(qū)，然后調(diào)整空閑隊列排序035KB200KB最壞適應(yīng)算法028KB156KB012KBNULL100KB作業(yè)1（12KB）放到首址100KB的空閑區(qū)作業(yè)2（30KB）不能繼續(xù)分配作業(yè)3（28KB）放到首址200KB的空閑區(qū)028KB100KB023KB156KB012KBNULL200KB4、碎片問題及拼接技術(shù)1.什么是碎片問題

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

如何解決碎片問題？2.拼接技術(shù)

所謂拼接技術(shù)是指移動存儲器中某些已分配區(qū)中的信息，使本來分散的空閑區(qū)連成一個大的空閑區(qū)。40OS400KBJOB1(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的作業(yè)需要運行!!!空閑(24KB)（四）頁式存儲管理一.頁式存儲管理的目的 解決分區(qū)存儲管理中的碎片問題。二.相關(guān)基本概念1.頁面

程序的邏輯地址空間被等分成大小相等的片，稱為頁面，

又稱為虛頁。2.主存塊

主存被等分成大小相等的片，稱為主存塊，又稱為實頁。當(dāng)一個用戶頁面的大小是為2n,通常為1KB，2KB，nKB等程序裝入內(nèi)存時，以頁面為單位進(jìn)行分配。相等

作業(yè)頁面與主存塊的關(guān)系3.頁表

為了實現(xiàn)程序從邏輯地址空間到物理主存的映象，系統(tǒng)建立的記錄頁與內(nèi)存塊之間對應(yīng)關(guān)系的地址變換的機(jī)構(gòu)稱為頁面映像表，簡稱頁表。頁表包括：

用戶程序空間的頁面與內(nèi)存塊的對應(yīng)關(guān)系

頁面的存儲保護(hù)信息

存取控制方面的信息等等。三.頁式存儲管理地址變換（映射）1.虛地址結(jié)構(gòu)它包括頁號和頁內(nèi)地址（頁內(nèi)位移）。

虛地址=頁號B×頁大小+頁內(nèi)位移W問：知道虛地址，如果求出其所在的頁號P和頁內(nèi)位移W：情形一：虛地址以十進(jìn)制數(shù)給出：

頁號P=邏輯地址除以頁大小的商 頁內(nèi)位移W=邏輯地址除以頁大小的余數(shù)情形二：邏輯地址以十六進(jìn)制、八進(jìn)制或二進(jìn)制的形式給出：首先將虛地址轉(zhuǎn)換成二進(jìn)制（按預(yù)先制定的位數(shù)擴(kuò)展）；其次，按頁大小分離出頁號P和位移量W（低位部分是

位移量，高位部分是頁號）。【例】設(shè)虛地址長度為16位，頁面大小為1KB：頁號頁內(nèi)地址（位移量，由頁面大小確定其位數(shù)）

PW 151090【十進(jìn)制虛地址舉例】：設(shè)頁大小為2KB。求虛地址3412的頁號和頁內(nèi)位移頁號P＝3412％2048＝1頁內(nèi)偏移W＝3412mod2048＝1364求虛地址7145的頁號和頁內(nèi)位移：頁號P＝7145％2048＝3頁內(nèi)偏移W＝7145mod2048＝1001【十六進(jìn)制虛地址舉例】設(shè)頁大小為2KB，虛地址長度為16位。求虛地址為0x0AFE的頁號和頁內(nèi)位移：0000

101011111110頁號P＝1頁內(nèi)偏移W＝01011111110求虛地址0x1ADD的頁號和頁內(nèi)位移：0001101011011101頁號P＝3頁內(nèi)偏移W＝01011011101例1頁面大小1KB，虛地址是3BADH，虛地址長度16位；例2頁面大小2KB，虛地址是3BADH，虛地址長度16位；2、地址變換虛地址映射到物理地址的步驟：1）求出頁號P和頁內(nèi)位移W：2）根據(jù)頁號查頁表得塊號B；3）物理地址=塊號B×頁大小+頁內(nèi)位移W虛地址=頁號P×頁大小+頁內(nèi)位移W【例】：有一作業(yè)大小是8KB，頁大小為2KB，依次裝入內(nèi)存的第7、9、10、5塊，將虛地址7145，3412轉(zhuǎn)換成物理地址。解：1、虛地址3412頁號P＝3412%2048＝1頁內(nèi)偏移W＝3412mod2048＝1364物理地址=9*2048+1364=197962、虛地址7145：頁號P＝7145％2048＝3頁內(nèi)偏移W＝7145mod2048＝1001物理地址=5*2048+1001=11241【例】：有一作業(yè)大小是8KB，頁大小為2KB，依次裝入內(nèi)存的第7、9、A、5塊，試將虛地址0AFEH，1ADDH轉(zhuǎn)換成內(nèi)存地址。解：求虛地址0AFEH的物理地址：0000

101011111110頁號P＝1頁內(nèi)偏移W＝01011111110物理地址＝0100

1010

11111110＝4AFEH求虛地址1ADDH的物理地址：0001101011011101頁號P＝3頁內(nèi)偏移W＝01011011101物理地址＝00101010

11011101＝2ADDH課堂練習(xí)：1、某作業(yè)J的邏輯空間為4頁，每頁2KB，已知該作業(yè)J的頁表如下： 頁號：0123

塊號：2468

求：邏輯地址為0A65H的物理地址。2、某作業(yè)有4個頁面，分別裝入主存的3、4、6、8塊中，設(shè)頁面尺寸為1KB（1）寫出頁表；（2）求虛地址2100和3100的物理地址。四.請調(diào)頁面的機(jī)制1、請調(diào)策略定義：

在頁式存儲管理系統(tǒng)中，允許一個作業(yè)程序只裝入部分頁面即可投入運行，需要信息時動態(tài)調(diào)入，這種裝入信息的策略稱為請調(diào)策略。

(1)怎樣發(fā)現(xiàn)所訪問的頁面在不在主存？

(2)當(dāng)發(fā)現(xiàn)所需訪問的頁面不在主存時如何處理?2.擴(kuò)充頁表功能

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

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

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

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

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

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

006802

3KB設(shè)頁面大小為1KB

當(dāng)程序執(zhí)行“movr1，[2120］”時

虛地址2120要轉(zhuǎn)換成物理地址通過計算求得頁號p=2，頁內(nèi)偏移w=72

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

006802

3KB設(shè)m為系統(tǒng)分配給作業(yè)的塊數(shù)，n代表作業(yè)已經(jīng)使用了的塊數(shù)情景一：nm，則從外存中直接調(diào)入放入空白塊中；

情景二：n

m，則首先淘汰某一頁，在從外存中調(diào)入。4.淘汰策略1、什么是淘汰策略

用來選擇淘汰哪一頁的規(guī)則就叫做置換策略，或稱淘汰算法。介紹三種：1）最優(yōu)算法OPT:(optimalreplacementalgorithm)置換在最長時間內(nèi)不會使用的頁)2）先進(jìn)先出算法FIFO：淘汰先調(diào)入內(nèi)存的頁3）最近最少使用淘汰算法LRU：淘汰未被訪問的頁中時間最長的頁;(LeastRecentlyUsed)使用缺頁中斷率f’衡量頁面淘汰算法的優(yōu)劣：

f’＝f／a（a是總的頁面訪問次數(shù)，f是缺頁中斷次數(shù)）顛簸(thrashing)，又稱為“抖動”。

簡單地說，導(dǎo)致系統(tǒng)效率急劇下降的主存和輔存之間的頻繁頁面置換現(xiàn)像稱為“抖動”。

2、進(jìn)一步擴(kuò)充頁表（配合淘汰算法）頁表又增加了兩項內(nèi)容：

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

1表示最近有被訪問

改變位：0該頁調(diào)入內(nèi)存后沒有修改

1該頁調(diào)入內(nèi)存后修改過頁號主存塊號中斷位輔存地址改變位引用位OPT原理（難實現(xiàn)）：所淘汰的那一頁是在最長的時間以后才會用到的那頁，或者以后不再要用的。

缺頁率的計算若程序p在運行中:成功的訪問次數(shù)：s

不成功的訪問次數(shù)（缺頁中斷次數(shù)）：f

則缺頁中斷率：f′=f/(s+f)*100%頁面置換算法（一）——OPT算法例：假設(shè)系統(tǒng)為某進(jìn)程分配了3個物理塊，并考慮有以下的訪問串，求缺頁率。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%777222222222222227770000004440000000000111333333331111111缺頁缺頁缺頁缺頁缺頁缺頁缺頁缺頁缺頁

1)什么是先進(jìn)先出淘汰算法選擇在主存中居留時間最長(即最老)的一頁淘汰。

2)先進(jìn)先出淘汰算法的實現(xiàn)方法

建立一個頁面進(jìn)入主存的先后次序表；

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

當(dāng)需要置換一頁時，選擇替換指向的那一頁，然

后調(diào)整替換指針的內(nèi)容。頁面置換算法（二）：FIFO算法（先進(jìn)先出）【例】某進(jìn)程的頁面訪問序列：1、2、3、4、1、2、5、1、2、3、4、5，指出在系統(tǒng)分給該作業(yè)的內(nèi)存塊數(shù)大

小分別為3和4時，使用FIFO置換算法的缺頁率？123412512345t1111111122222222333333444445555551512341251345t1114334522244511332334432455122232234151112采用FIFO算法(實際采用壓棧的方式)總是選擇最長時間未被使用的那一頁淘汰。

LRU算法的實現(xiàn)方法

用引用位考察頁面的使用情況；

當(dāng)訪問頁面時，將引用位置1，并開始或重新開始計時；

當(dāng)計時結(jié)束后，引用位置0。

頁面置換算法（三）：LRU算法（最久未使用）【例】某進(jìn)程的頁面訪問序列：1、2、3、4、1、2、5、1、2、3、4、5，指出