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

第七章主存管理（一）主存的共享方式（二）主存管理的功能（三）分區(qū)存儲(chǔ)管理技術(shù)（四）頁式存儲(chǔ)管理技術(shù)（五）段式及段頁式存儲(chǔ)管理技術(shù)2計(jì)算機(jī)系統(tǒng)存儲(chǔ)結(jié)構(gòu)內(nèi)存管理的目的操作系統(tǒng)的“方便”性便于用戶裝入程序，無須了解底層細(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)度過程，實(shí)現(xiàn)系統(tǒng)運(yùn)行的穩(wěn)定（一）主存的共享方式內(nèi)存儲(chǔ)器（簡稱內(nèi)存、主存、物理存儲(chǔ)器）處理機(jī)能直接訪問的存儲(chǔ)器。用來存放系統(tǒng)和用戶的程序和數(shù)據(jù)，其特點(diǎn)是存取速度快，斷電信息丟失。主存的共享方式包含三種：

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

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

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

段頁式存儲(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.地址映射

將程序地址空間中使用的邏輯地址變換成主存中的地址的過程。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í)，所要訪問的指令和數(shù)據(jù)的物理地址和作業(yè)地址空間中的地址是不同的。movr1,[500]123movr1,[500]123010050059901000110015001599256k-1作業(yè)地址空間存儲(chǔ)空間將500號(hào)單元處的數(shù)據(jù)123送到寄存器r1中（2）地址映射的定義

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

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

在作業(yè)裝入過程中隨即進(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ù)的訪問自動(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è)裝入過程中進(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）問題的提出3、主存擴(kuò)充

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

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

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

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

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

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

由操作系統(tǒng)和硬件相配合來完成主存和輔存之間的信息的動(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)基地址、限長防護(hù)

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

20KB限長寄存器

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

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

（末地址）∴判別式：基址寄存器≤物理地址＜基址+限長寄存器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è)的過程中，建立分區(qū)，依用戶請求的大小分配分區(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ū)的分配過程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)動(dòng)態(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主存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）說明分區(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ū)分配

?

用戶請求分配一個(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)算法來處理該作業(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四、碎片問題及拼接技術(shù)1.什么是碎片問題

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

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

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

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

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

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

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

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

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

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

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

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

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

PW

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

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

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

15109000011101110001007×1024+452=762055【例】：有一系統(tǒng)采用頁式存儲(chǔ)管理，有一作業(yè)大小是8KB，頁大小為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)采用頁式存儲(chǔ)管理，有一作業(yè)大小是8KB，頁大小為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頁，每頁2048B，已知該作業(yè)J的頁表如下： 頁號(hào)：0123

塊號(hào)：2468

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

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

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

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

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

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

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

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

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

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

006802

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

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

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

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

006802

3KB

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

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

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

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

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

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

從外存讀入所需的頁

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

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

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

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

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

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

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

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

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

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

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

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

缺頁率

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

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

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

4.頁面置換算法——OPT算法例：假設(shè)系統(tǒng)為某進(jìn)程分配了3個(gè)物理塊，并考慮有以下的訪問串：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)先進(jìn)先出淘汰算法(FIFO算法)1)什么是先進(jìn)先出淘汰算法原理：總是選擇在主存中居留時(shí)間最長(即最老)的一頁淘汰。

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

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

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

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

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