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

第七章主存管理（一）主存的共享方式（二）主存管理的功能（三）分區(qū)存儲(chǔ)管理技術(shù)（四）頁(yè)式存儲(chǔ)管理技術(shù)（五）段式及段頁(yè)式存儲(chǔ)管理技術(shù)2計(jì)算機(jī)系統(tǒng)存儲(chǔ)結(jié)構(gòu)內(nèi)存管理的目的操作系統(tǒng)的“方便”性便于用戶裝入程序，無(wú)須了解底層細(xì)節(jié)可實(shí)現(xiàn)動(dòng)態(tài)的存儲(chǔ)空間伸縮，適應(yīng)不同程序的需要操作系統(tǒng)的“合理”性合理分配內(nèi)存空間，保證多道程序的順利運(yùn)行合理保護(hù)內(nèi)存空間，防止各種可能的破壞泄漏操作系統(tǒng)的“有效性”有效保持內(nèi)存空間的可用性，防止對(duì)資源的浪費(fèi)有效實(shí)現(xiàn)“小空間大容量”，提高計(jì)算機(jī)的適應(yīng)性有效配合CPU的調(diào)度過(guò)程，實(shí)現(xiàn)系統(tǒng)運(yùn)行的穩(wěn)定（一）主存的共享方式內(nèi)存儲(chǔ)器（簡(jiǎn)稱內(nèi)存、主存、物理存儲(chǔ)器）處理機(jī)能直接訪問(wèn)的存儲(chǔ)器。用來(lái)存放系統(tǒng)和用戶的程序和數(shù)據(jù)，其特點(diǎn)是存取速度快，斷電信息丟失。主存的共享方式包含三種：

大小不等的區(qū)域——

分區(qū)存儲(chǔ)管理 分段存儲(chǔ)管理大小相等的片——

頁(yè)式存儲(chǔ)管理兩者結(jié)合 ——

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

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

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

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

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

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

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

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

（3）地址映射的方式編程或編譯時(shí)確定地址映射關(guān)系靜態(tài)地址映射動(dòng)態(tài)地址映射靜態(tài)地理映射定義：

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

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

1000500邏輯地址+靜態(tài)地址映射與動(dòng)態(tài)地址映射的區(qū)別靜態(tài)地址映射動(dòng)態(tài)地址映射在作業(yè)裝入過(guò)程中進(jìn)行地址映射在程序執(zhí)行期間進(jìn)行地址映射需軟件變換機(jī)構(gòu)重定位裝入程序需硬件地址變換機(jī)構(gòu)重定位裝入程序需花費(fèi)較多CPU時(shí)間地址變換快不靈活靈活構(gòu)造分配用的數(shù)據(jù)結(jié)構(gòu)

主存資源信息塊（M_RIB）、空閑區(qū)隊(duì)列等等制定分配策略

2、主存功能——主存分配實(shí)施主存分配與回收主存擴(kuò)充也就是提供虛擬存儲(chǔ)器

1）問(wèn)題的提出3、主存擴(kuò)充

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

裝入部分程序地址空間，它還能正確地執(zhí)行？3）實(shí)現(xiàn)方法

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

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

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

4.什么是虛擬存儲(chǔ)器

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

邏輯地址與物理地址分開

主存空間與地址空間分開

提供地址變換機(jī)構(gòu)

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

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

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

有一定容量的主存

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

地址變換機(jī)構(gòu)4、存儲(chǔ)保護(hù)1）什么是存儲(chǔ)保護(hù)

在多道程序設(shè)計(jì)的環(huán)境下，系統(tǒng)中有系統(tǒng)程序和多個(gè)用戶程序同時(shí)存在，如何保證用戶程序不破壞系統(tǒng)程序，用戶程序之間不相互干擾？

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

通常的存儲(chǔ)保護(hù)方法——

界地址保護(hù)和存儲(chǔ)鍵保護(hù)（不介紹）

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

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

20KB上界寄存器

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

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

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

20KB限長(zhǎng)寄存器

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

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

（末地址）∴判別式：基址寄存器≤物理地址＜基址+限長(zhǎng)寄存器23作業(yè)第7章

第2題（三）分區(qū)存儲(chǔ)管理分區(qū)存儲(chǔ)管理分為：1.固定分區(qū)2.動(dòng)態(tài)分區(qū)（可變分區(qū)）25固定分區(qū)固定分區(qū)一.動(dòng)態(tài)分區(qū)分配1.什么是動(dòng)態(tài)分區(qū)分配

在處理作業(yè)的過(guò)程中，建立分區(qū)，依用戶請(qǐng)求的大小分配分區(qū)。思想：分區(qū)的大小、數(shù)量和位置隨內(nèi)存中進(jìn)程的大小和數(shù)量動(dòng)態(tài)變化（根據(jù)作業(yè)的實(shí)際需要在裝入內(nèi)存時(shí)動(dòng)態(tài)地分配連續(xù)的內(nèi)存空間）。

(1)動(dòng)態(tài)分區(qū)的分配過(guò)程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申請(qǐng)

32KB作業(yè)2申請(qǐng)

14KB作業(yè)3申請(qǐng)

64KB作業(yè)4申請(qǐng)

100KB作業(yè)5申請(qǐng)

50KB

(2)動(dòng)態(tài)分區(qū)的回收過(guò)程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主存292、分區(qū)分配機(jī)構(gòu)

1)主存資源信息塊在動(dòng)態(tài)分區(qū)方法中，描述主存資源的數(shù)據(jù)結(jié)構(gòu)是主存資源信息塊等待隊(duì)列指針空閑區(qū)隊(duì)列指針主存分配程序入口指針2)分區(qū)描述器和空閑隊(duì)列主存中的每一個(gè)分區(qū)都有相應(yīng)的分區(qū)描述器（pd）說(shuō)明分區(qū)的特征信息。flag：為0—空閑區(qū);為1—已分配區(qū)size：分區(qū)大小next：空閑區(qū)—自由主存隊(duì)列中的勾鏈字;已分配區(qū)—此項(xiàng)為零m_ribpd分配標(biāo)志flag分區(qū)大小size勾鏈字next30自由主存隊(duì)列(或空閑區(qū)隊(duì)列)結(jié)構(gòu)在主存分配中，主要討論空閑區(qū)描述器和空閑區(qū)隊(duì)列。下面是在t時(shí)刻的主存分布、空閑區(qū)描述器的內(nèi)容和空閑區(qū)隊(duì)列結(jié)構(gòu)。

020KB

os

作業(yè)1

作業(yè)3

作業(yè)4

52KB66KB130KB230KB256KB1主存52KBm-rib

014KB230KB

026KB

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

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

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

?

用戶請(qǐng)求分配一個(gè)主存塊

?

分區(qū)分配程序在自由主存隊(duì)列中找一個(gè)滿足用戶需要的空閑塊

?

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

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

空閑區(qū)表的組織有兩種方法：

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

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

根據(jù)空閑區(qū)表組織的方法的不同，有不同的放置策略：首次適應(yīng)算法、最佳適應(yīng)算法和最壞適應(yīng)算法三種。33

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

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

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

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

35

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

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

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

有一作業(yè)系列：

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

用首次適應(yīng)算法、最佳適應(yīng)算法和最壞適應(yīng)算法來(lái)處理該作業(yè)序列，看哪種算法合適？注：設(shè)分配時(shí)從空閑區(qū)的高地址分割，以保持剩余空閑區(qū)的起始地址不變。

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

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

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

所謂拼接技術(shù)是指移動(dòng)存儲(chǔ)器中某些已分配區(qū)中的信息，使本來(lái)分散的空閑區(qū)連成一個(gè)大的空閑區(qū)。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的作業(yè)需要運(yùn)行!!!空閑(24KB)分區(qū)管理的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：實(shí)現(xiàn)了多道程序共享主存。實(shí)現(xiàn)分區(qū)管理的系統(tǒng)設(shè)計(jì)相對(duì)簡(jiǎn)單，不需要更多的系統(tǒng)軟硬件開銷。實(shí)現(xiàn)存儲(chǔ)保護(hù)的手段也比較簡(jiǎn)單。缺點(diǎn)：主存利用不夠充分。系統(tǒng)中總有一部分存儲(chǔ)空間得不到利用，這部分被浪費(fèi)的空間叫碎片。沒(méi)有實(shí)現(xiàn)主存的擴(kuò)充問(wèn)題。當(dāng)作業(yè)的地址空間大于存儲(chǔ)空間時(shí)，作業(yè)無(wú)法運(yùn)行。也即作業(yè)的地址空間受實(shí)際存儲(chǔ)空間限制。（四）頁(yè)式存儲(chǔ)管理一.問(wèn)題的提出

分區(qū)存儲(chǔ)管理的主要問(wèn)題是碎片問(wèn)題。

在采用分區(qū)存儲(chǔ)管理的系統(tǒng)中，會(huì)形成一些非常小的分區(qū)，最終這些非常小的分區(qū)不能被系統(tǒng)中的任何用戶（程序）利用而浪費(fèi)。

造成這樣問(wèn)題的主要原因是用戶程序裝入內(nèi)存時(shí)是整體裝入的，為解決這個(gè)問(wèn)題，提出了分頁(yè)存儲(chǔ)管理技術(shù)。二.頁(yè)式系統(tǒng)的基本概念1.頁(yè)面

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

主存被等分成大小相等的片，稱為主存塊，又稱為實(shí)頁(yè)。

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

為了實(shí)現(xiàn)從地址空間到物理主存的映象，系統(tǒng)建立的記錄頁(yè)與內(nèi)存塊之間對(duì)應(yīng)關(guān)系的地址變換的機(jī)構(gòu)稱為頁(yè)面映像表，簡(jiǎn)稱頁(yè)表。包括用戶程序空間的頁(yè)面與內(nèi)存塊的對(duì)應(yīng)關(guān)系、頁(yè)面的存儲(chǔ)保護(hù)和存取控制方面的信息。01KB01KB2KB3KB1主存作業(yè)2地址空間2KB3KB4KB5KB6KB7KB8KB9KB10KB101KB2KB1作業(yè)1地址空間01KB1作業(yè)3地址空間0516頁(yè)號(hào)塊號(hào)02140827作業(yè)1頁(yè)表作業(yè)2頁(yè)表作業(yè)3頁(yè)表osos三.頁(yè)式地址變換1.虛地址結(jié)構(gòu)

虛地址是用戶程序中的邏輯地址，它包括頁(yè)號(hào)和頁(yè)內(nèi)地址（頁(yè)內(nèi)位移）。

區(qū)分頁(yè)號(hào)和頁(yè)內(nèi)地址的依椐是頁(yè)的大小，頁(yè)內(nèi)地址占虛地址的低位部分，頁(yè)號(hào)占虛地址的高位部分。

【例】設(shè)虛地址長(zhǎng)度為16位，頁(yè)面大小為1KB： 頁(yè)號(hào)頁(yè)內(nèi)地址（位移量）

PW

15109049如何方便將邏輯地址線性分割求出頁(yè)號(hào)P和頁(yè)內(nèi)位移W：邏輯地址以十進(jìn)制數(shù)給出：

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

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

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

101011111110P＝1W＝01011111110MR＝0100

1010

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

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

塊號(hào)：2468

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

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

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

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

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

輔存地址——該頁(yè)面在輔存的位置

頁(yè)號(hào)主存塊號(hào)中斷位輔存地址

3.缺頁(yè)處理過(guò)程（舉例說(shuō)明）

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

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

006802

3KB作業(yè)2的主存塊數(shù)為m2=3，頁(yè)面大小為1KB。

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

CPU產(chǎn)生的虛地址為2120分頁(yè)機(jī)構(gòu)得p=2，w=72

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

006802

3KB

如主存中有空白塊，且nm則直接調(diào)入如主存中無(wú)空白塊，或n

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

啟動(dòng)要處理的指令給出虛地址

得到頁(yè)號(hào)該頁(yè)在主存?有空閑塊?

缺頁(yè)中斷執(zhí)行完該指令

準(zhǔn)備執(zhí)行下條指令選一頁(yè)淘汰

從外存讀入所需的頁(yè)

調(diào)整存儲(chǔ)分配表和頁(yè)表

重新啟動(dòng)被中斷的指令

調(diào)整存儲(chǔ)分配表和頁(yè)表要重寫入?該頁(yè)寫入外存YNNY硬件軟件YN4.淘汰策略1.什么是淘汰策略

用來(lái)選擇淘汰哪一頁(yè)的規(guī)則就叫做置換策略，或稱淘汰算法。常用算法：1、最優(yōu)算法OPT:(optimalreplacementalgorithm)置換在最長(zhǎng)時(shí)間內(nèi)不會(huì)使用的頁(yè))2、先進(jìn)先出算法FIFO：淘汰先調(diào)入內(nèi)存的頁(yè)3、最近最少使用淘汰算法LRU：淘汰未被訪問(wèn)的頁(yè)中時(shí)間最長(zhǎng)的頁(yè);(LeastRecentlyUsed)

使用缺頁(yè)中斷率f’衡量頁(yè)面淘汰算法的優(yōu)劣：

f’＝f／a（a是總的頁(yè)面訪問(wèn)次數(shù)，f是缺頁(yè)中斷次數(shù)）2.擴(kuò)充頁(yè)表的功能頁(yè)表應(yīng)增加相應(yīng)的內(nèi)容，反映該頁(yè)是否在內(nèi)存，在外存的位置，在內(nèi)存的時(shí)間的長(zhǎng)短等。

引用位：0表示最近沒(méi)有進(jìn)程訪問(wèn)

1表示最近有進(jìn)程訪問(wèn)

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

1該頁(yè)調(diào)入內(nèi)存后修改過(guò)頁(yè)號(hào)主存塊號(hào)中斷位輔存地址改變位引用位3.顛簸顛簸(thrashing)，又稱為“抖動(dòng)”。

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

OPT原理（難實(shí)現(xiàn)）：當(dāng)要調(diào)入一新頁(yè)而必須先淘汰一舊頁(yè)時(shí)，所淘汰的那一頁(yè)應(yīng)是以后不再要用的，或者是在最長(zhǎng)的時(shí)間以后才會(huì)用到的那頁(yè)。

缺頁(yè)率

假定程序p共有n頁(yè)，系統(tǒng)分配m塊，有1≤m≤n若程序p在運(yùn)行中:成功的訪問(wèn)次數(shù)：s

不成功的訪問(wèn)次數(shù)：f

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

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

(2)先進(jìn)先出淘汰算法(FIFO算法)1)什么是先進(jìn)先出淘汰算法原理：總是選擇在主存中居留時(shí)間最長(zhǎng)(即最老)的一頁(yè)淘汰。

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

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

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

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

后調(diào)整替換指針的內(nèi)容。69【例】某進(jìn)程的頁(yè)面訪問(wèn)序列：1、2