第6章虛擬存儲(chǔ)器

■常規(guī)存儲(chǔ)器管理方式要求作業(yè)運(yùn)行前全部裝

入內(nèi)存，作業(yè)裝入內(nèi)存后一直駐留內(nèi)存直至

運(yùn)行結(jié)束。

■這種存儲(chǔ)管理方式限制了大作業(yè)的運(yùn)行。而

物理擴(kuò)充內(nèi)存會(huì)增加成本，故應(yīng)從邏輯上擴(kuò)

充內(nèi)存。

、.6.1虛擬存儲(chǔ)器概念

-rl--------------

■虛擬存儲(chǔ)器的理論基礎(chǔ)是程序執(zhí)行時(shí)的局部

性原理。

■局部性原理是指程序在執(zhí)行過(guò)程中一個(gè)較短

時(shí)間內(nèi)，程序所執(zhí)行的指令地址和操作數(shù)地

址分別局限于一定區(qū)域內(nèi)。

■例如：

-除轉(zhuǎn)移和過(guò)程調(diào)用外，程序主要是順序執(zhí)行。

■過(guò)程調(diào)用使程序從一部分區(qū)域轉(zhuǎn)至另一部分區(qū)

域

■循環(huán)結(jié)構(gòu)

■卜局部性的體現(xiàn)

-局部性體現(xiàn)為：

■時(shí)間局部性：一條指令的一次執(zhí)行和下次執(zhí)行，

一個(gè)數(shù)據(jù)的一次訪問(wèn)和下次訪問(wèn)，都集中在一個(gè)

較短時(shí)間內(nèi)。

■空間局部性：當(dāng)前執(zhí)行的指令和將要執(zhí)行的指令,

當(dāng)前訪問(wèn)的數(shù)據(jù)和將要訪問(wèn)的數(shù)據(jù)，都集中在一

個(gè)較小范圍內(nèi)。

、.虛擬存儲(chǔ)器的基本原理

----——----------

■在程序運(yùn)行之前，將程序的一部分放入內(nèi)存后就

啟動(dòng)程序執(zhí)行。

■在程序執(zhí)行過(guò)程中，當(dāng)所訪問(wèn)的信息不在內(nèi)存時(shí),

由操作系統(tǒng)將所需要的部分調(diào)入內(nèi)存，然后繼續(xù)

執(zhí)行程序。

■另一方面，操作系統(tǒng)將內(nèi)存中暫時(shí)不使用的內(nèi)容

換出到外存上，從而騰出空間存放將要調(diào)入內(nèi)存

的信息。

■從效果上看，這樣的計(jì)算機(jī)系統(tǒng)好像為用戶提供

了一個(gè)存儲(chǔ)容量比實(shí)際內(nèi)存大得多的存儲(chǔ)器，將

這個(gè)存儲(chǔ)器稱為虛擬存儲(chǔ)器。

■卜虛擬存儲(chǔ)器

■虛擬存儲(chǔ)器是指具有請(qǐng)求調(diào)入和置換功能，

能從邏輯上對(duì)內(nèi)存容量加以擴(kuò)充的一種存儲(chǔ)

器系統(tǒng)。

■虛擬存儲(chǔ)器是一種以時(shí)間換空間的技術(shù)。

、］虛擬存儲(chǔ)器的特征

-離散性：不連續(xù)內(nèi)存分配

-多次性：一個(gè)作業(yè)分多次裝入內(nèi)存

■對(duì)換性：允許運(yùn)行中換進(jìn)換出

-虛擬性：邏輯上擴(kuò)充內(nèi)存

、.虛擬存儲(chǔ)器的本質(zhì)

-W-------------------------

■虛擬存儲(chǔ)器的本質(zhì)是將程序的訪問(wèn)地址和內(nèi)

存的可用地址分離，為用戶提供一個(gè)大于實(shí)

際主存的虛擬存儲(chǔ)器。

-虛擬存儲(chǔ)器的容量受限于：

-地址結(jié)構(gòu)

■外存容量

實(shí)現(xiàn)虛擬存儲(chǔ)技術(shù)的物質(zhì)基礎(chǔ)

■相當(dāng)數(shù)量的外存：足以存放多個(gè)用戶的

程序。

■一定容量的內(nèi)存：在處理機(jī)上運(yùn)行的程

序必須有一部分信息存放在內(nèi)存中。

■地址變換機(jī)構(gòu)：動(dòng)態(tài)實(shí)現(xiàn)邏輯地址到物

理地址的變換。

、.虛擬存儲(chǔ)器的實(shí)現(xiàn)方法

---------------

■常用的虛擬存儲(chǔ)技術(shù)有：

■請(qǐng)求分頁(yè)存儲(chǔ)管理

■請(qǐng)求分段存儲(chǔ)管理

、6.2請(qǐng)求分頁(yè)存儲(chǔ)管理?621

-請(qǐng)求分頁(yè)存儲(chǔ)管理方法是在分頁(yè)存儲(chǔ)管理的

基礎(chǔ)上增加了請(qǐng)求調(diào)頁(yè)和頁(yè)面置換功能。

■實(shí)現(xiàn)思想：在作業(yè)運(yùn)行之前只裝入當(dāng)前需要

的一部分頁(yè)面便啟動(dòng)作業(yè)運(yùn)行。在作業(yè)運(yùn)行

過(guò)程中，若發(fā)現(xiàn)所要訪問(wèn)的頁(yè)面不在內(nèi)存，

便由硬件產(chǎn)生缺頁(yè)中斷，請(qǐng)求OS將缺頁(yè)調(diào)入

內(nèi)存。若內(nèi)存無(wú)空閑存儲(chǔ)空間，則根據(jù)某種

置換算法淘汰已在內(nèi)存的某個(gè)頁(yè)面，以騰出

內(nèi)存空間裝入缺頁(yè)。

、［請(qǐng)求分頁(yè)系統(tǒng)中的支持機(jī)構(gòu)

-請(qǐng)求分頁(yè)中的支持機(jī)構(gòu)有：

■頁(yè)表

■缺頁(yè)中斷機(jī)構(gòu)

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

■請(qǐng)求調(diào)頁(yè)和頁(yè)面置換軟件

卜6.2.2頁(yè)表

-請(qǐng)求分頁(yè)系統(tǒng)中使用的主要數(shù)據(jù)結(jié)構(gòu)仍然是

頁(yè)表。

■但由于每次只將作業(yè)的一部分調(diào)入內(nèi)存，還

有一部分內(nèi)容存放在磁盤上，故需要在頁(yè)表

中增加若干項(xiàng)。

■擴(kuò)充后的頁(yè)表項(xiàng)如下所示：

、I擴(kuò)充后的頁(yè)表項(xiàng)

頁(yè)號(hào)物理塊號(hào)存在位訪問(wèn)字段修改位外存地址

■頁(yè)號(hào)和物理塊號(hào)：其定義同分頁(yè)存儲(chǔ)管理。

■狀態(tài)位：用于表示該頁(yè)是否在主存中。

■訪問(wèn)字段：用于記錄本頁(yè)在一段時(shí)間內(nèi)被訪

問(wèn)的次數(shù)，或最近已有多長(zhǎng)時(shí)間未被訪問(wèn)。

■修改位：用于表示該頁(yè)調(diào)入內(nèi)存后是否被修

改過(guò)。

■外存地址：用于指出該頁(yè)在外存上的地址。

、6?2?3缺頁(yè)中斷與地址變換

■在請(qǐng)求分頁(yè)系統(tǒng)中，當(dāng)所訪問(wèn)的頁(yè)不在內(nèi)存

時(shí)，便產(chǎn)生缺頁(yè)中斷，請(qǐng)求os將缺頁(yè)調(diào)入內(nèi)

存。

■缺頁(yè)中斷處理程序根據(jù)該頁(yè)在外存的地址把

它調(diào)入內(nèi)存。在調(diào)頁(yè)過(guò)程中，若內(nèi)存有空閑

空間，則缺頁(yè)中斷處理程序只需把缺頁(yè)裝入

并修改頁(yè)表中的相應(yīng)項(xiàng)；若內(nèi)存中無(wú)空閑物

理塊，則需要先淘汰內(nèi)存中的某些頁(yè)，若淘

汰頁(yè)曾被修改過(guò)，則還要將其寫回外存。

r缺頁(yè)中斷與一般中斷的區(qū)別

■缺頁(yè)中斷與一般中斷的區(qū)別主要

有：

■在指令的執(zhí)行期間產(chǎn)生和處理缺頁(yè)

中斷。

■一條指令可以產(chǎn)生多個(gè)缺頁(yè)中斷。

如：執(zhí)行一條復(fù)制指令copyAtoB

■缺頁(yè)中斷返回時(shí)執(zhí)行產(chǎn)生中斷的指

令，一般中斷返回時(shí)執(zhí)行下條指令

、地址變換

-請(qǐng)求分頁(yè)存儲(chǔ)管理系統(tǒng)的地址變換過(guò)程

類似于分頁(yè)存儲(chǔ)管理，但當(dāng)被訪問(wèn)頁(yè)不

在內(nèi)存時(shí)應(yīng)進(jìn)行缺頁(yè)中斷處理。

、■地址變換流程

-5w------------------------

程序請(qǐng)求訪問(wèn)一頁(yè)

IY

頁(yè)號(hào)〉頁(yè)表長(zhǎng)度？?越界中斷

NI-E形成物理地址

CPU檢索快表t

I修改訪問(wèn)位和修改位

?Y4

頁(yè)表項(xiàng)在快表中？--------------------------4

I2修改快表

INY4

訪問(wèn)頁(yè)表------頁(yè)在內(nèi)存？--------------1

IN

產(chǎn)生缺頁(yè)中斷

、]缺頁(yè)處理流程

缺頁(yè)中?斷處理IQ-]

保留CPU現(xiàn)場(chǎng)〕

修改頁(yè)表

從外存中找到缺頁(yè)I

從外存讀缺頁(yè)入內(nèi)存

內(nèi)存滿否？------------------I

YN將該頁(yè)寫回外存

選擇一頁(yè)換出—?該頁(yè)被修改否？

6.2.4頁(yè)面分配和置換策略

■在為進(jìn)程分配物理塊時(shí)應(yīng)確定:

■進(jìn)程需要的最少物理塊數(shù)

■進(jìn)程的物理塊數(shù)是固定還是可變

■按什么原則為進(jìn)程分配物理塊數(shù)

'.最小物理塊數(shù)的確定

-rl--------------

■最小物理塊數(shù)是指能保證進(jìn)程正常運(yùn)行所需

的最少物理塊數(shù)，若小于此值進(jìn)程無(wú)法運(yùn)行。

-一般情況下：

■單地址指令且采用直接尋址，則所需最少物理

塊數(shù)為2。

■若單地址指令且允許采用間接尋址，則所需最

少物理塊數(shù)為3。

■某些功能較強(qiáng)的機(jī)器，指令及源地址和目標(biāo)地

址均跨兩個(gè)頁(yè)面，則最少需要6個(gè)物理塊。

、頁(yè)面分配算法

■頁(yè)面分配是指按什么原則給進(jìn)程分配物理塊

數(shù)，通常有以下幾種分配算法：

■平均分配算法：將系統(tǒng)中所有可供分配物理塊平

均分配給每個(gè)進(jìn)程。

-按比例分配算法：根據(jù)進(jìn)程大小按比例分配物理

毓。

■按優(yōu)先級(jí)分配算法：有兩種實(shí)現(xiàn)方案

-將可供分配的物理塊分為兩部分，一部分按比例分配

給每個(gè)進(jìn)程，另一部分根據(jù)進(jìn)程的優(yōu)先級(jí)適當(dāng)增加物

理塊。

■先按比例為進(jìn)程分配物理塊，當(dāng)高優(yōu)先級(jí)進(jìn)程發(fā)生缺

頁(yè)時(shí)，允許它從低優(yōu)先級(jí)進(jìn)程處獲得物理塊。

頁(yè)面分配和置換策略

■頁(yè)面分配常采用固定分配和可變分配兩種

策略。

■頁(yè)面置換也有全局置換和局部置換兩種策

略。

■將分配策略和置換范圍組合可得如下三種

策略：

-固定分配局部置換

■可變分配全局置換

■可變分配局部置換

、固定分配局部置換

-固定分配局部置換：基于某種原則為每個(gè)進(jìn)

程分配固定數(shù)量的物理塊，當(dāng)進(jìn)程運(yùn)行中出

現(xiàn)缺頁(yè)時(shí)，只能從自己的頁(yè)面中選擇一頁(yè)換

出，然后再調(diào)入缺頁(yè)。

■實(shí)現(xiàn)這種策略的困難在于：難以確定應(yīng)為每

個(gè)進(jìn)程分配多少個(gè)物理塊。

、可變分配全局置換

■可變分配全局置換：先為系統(tǒng)中的每個(gè)進(jìn)程分配

一定數(shù)量的物理塊，操作系統(tǒng)本身也保持一個(gè)空

閑物理塊隊(duì)列。當(dāng)某進(jìn)程發(fā)生缺頁(yè)時(shí)，由系統(tǒng)從

空閑物理塊隊(duì)列中取出一個(gè)物理塊分配給該進(jìn)程;

當(dāng)空閑物理塊隊(duì)列中的物理塊用完時(shí)，操作系統(tǒng)

才從內(nèi)存中選擇一頁(yè)調(diào)出，該頁(yè)可以是系統(tǒng)中任

何一個(gè)進(jìn)程的頁(yè)面。

■這是一種容易實(shí)現(xiàn)的頁(yè)面分配和置換策略，目前

已用于若干操作系統(tǒng)中。

、■可變分配局部置換

^rl--------------

■可變分配局部置換：根據(jù)某種原則為每個(gè)進(jìn)

程分配一定數(shù)量的物理塊，當(dāng)進(jìn)程發(fā)生缺頁(yè)

中斷時(shí)，只允許從該進(jìn)程的頁(yè)面中選出一頁(yè)

換出。如果某進(jìn)程的缺頁(yè)率較高，則系統(tǒng)再

為該進(jìn)程分配若干物理塊；反之若某進(jìn)程的

缺頁(yè)率特別低，則系統(tǒng)可適當(dāng)減少分配給該

進(jìn)程的物理塊數(shù)。

■該算法比較復(fù)雜，但性能較好。

r6,2.5頁(yè)面置換算法

-頁(yè)面置換算法又稱為頁(yè)面淘汰算法，是用來(lái)

選擇換出頁(yè)面的算法。

■下面介紹幾種比較常用的頁(yè)面置換算法。

、1.最佳置換算法(OPT)

-最佳算法是從內(nèi)存中選擇將來(lái)最長(zhǎng)時(shí)間

不會(huì)使用的頁(yè)面予以淘汰。

■特點(diǎn)：因頁(yè)面訪問(wèn)的未來(lái)順序很難精確

預(yù)測(cè)，該算法具有理論意義，可以用來(lái)

評(píng)價(jià)其他算法的優(yōu)劣。

、最佳置換算法例

-假定系統(tǒng)為某進(jìn)程分配了3個(gè)物理塊，頁(yè)面訪

問(wèn)序列為：1、2、3、4、1、2、5、1、2、3、

4、5,開(kāi)始時(shí)3個(gè)物理塊均為空閑，采用最佳

置換算法時(shí)的頁(yè)面置換情況如下所示：

、］采用最佳置換算法的頁(yè)面置換情況

走向123412512345

塊11111133

塊2222224

塊334555

缺缺缺缺缺缺缺

■從上表中可以看出，共發(fā)生了7次缺頁(yè)，其缺

頁(yè)率為7/12=58.3%o

、.2,先進(jìn)先出算法(FIFO)

-fl---------------------------------------------------

.先進(jìn)先出算法是選擇調(diào)入主存時(shí)間最長(zhǎng)

的頁(yè)面予以淘汰。

■特點(diǎn)：該算法實(shí)現(xiàn)比較簡(jiǎn)單，對(duì)按線性

順序訪問(wèn)的程序比較合適，但可能產(chǎn)生

異?，F(xiàn)象。

■Belady現(xiàn)象：在某些情況下，分配給進(jìn)

程的頁(yè)面數(shù)增多，缺頁(yè)次數(shù)反而增加。

、先進(jìn)先出置換算法例

?假定系統(tǒng)為某進(jìn)程分配了3個(gè)物理塊，頁(yè)面

訪問(wèn)序列為：1、2、3、4、1、2、5、1、2、

3、4、5,開(kāi)始時(shí)3個(gè)物理塊均為空閑，采用

先進(jìn)先出置換算法時(shí)的頁(yè)面置換情況如下所

示：

、］采用先進(jìn)先出算法的頁(yè)面置換情況

走向123412512345

塊1111444555

塊222211133

塊33332224

缺缺缺缺缺缺缺缺缺

■從上表中可以看出，共發(fā)生了9次缺頁(yè)中斷。

其缺頁(yè)率為9/12=75%o

、為進(jìn)程分配4個(gè)物理塊

走向123412512345

塊11111555544

塊2222211115

塊333332222

塊44444333

缺缺缺缺缺缺缺缺缺缺

■從上表中可以看出，共發(fā)生了10次缺頁(yè)中斷。其缺

頁(yè)率為10/12=83.3%o

、］無(wú)異常現(xiàn)象的頁(yè)面序列

-假定系統(tǒng)為某進(jìn)程分配了3個(gè)物理塊，頁(yè)

面訪問(wèn)序列為：7、0、1、2、0、3、0、

4、2、3、0、3,開(kāi)始時(shí)3個(gè)物理塊均為

空閑，采用先進(jìn)先出置換算法時(shí)的頁(yè)面

置換情況如下所示：

、頁(yè)面置換情況

走向701203042303

/p>

塊2000333222

塊311100033

缺缺缺缺缺缺缺缺缺缺

■從上表中可以看出，共發(fā)生了10次缺頁(yè)

中斷。其缺頁(yè)率為10/12=833%o

、為進(jìn)程分配4個(gè)物理塊

走向701203042303

塊17777333

塊2000044

塊311110

塊42222

缺缺缺缺缺缺缺

■從上表中可以看出，共發(fā)生了7次缺頁(yè)中

斷。其缺頁(yè)率為7/12=58.3%o

I3.最近最久未使用置換算法(LRU)

-最近最久未使用算法選擇最近一段時(shí)間

內(nèi)最長(zhǎng)時(shí)間沒(méi)有被訪問(wèn)過(guò)的頁(yè)面予以淘

汰。

■為此，應(yīng)賦予每個(gè)頁(yè)面一個(gè)訪問(wèn)字段，

用于記錄頁(yè)面自上次訪問(wèn)以來(lái)所經(jīng)歷的

時(shí)間。

?卜LRU算法例

-假定系統(tǒng)為某進(jìn)程分配了3個(gè)物理塊，頁(yè)

面訪問(wèn)序列為：1、2、3、4、1、2、5、

1、2、3、4、5,開(kāi)始時(shí)3個(gè)物理塊均為

空閑，采用LRU置換算法時(shí)的頁(yè)面置換

情況如下所示：

2］采用LRU算法的頁(yè)面置換情況

走向123412512345

塊11114445333

塊2222111144

塊333322225

缺缺缺缺缺缺缺缺缺缺

■從上表中可以看出，共發(fā)生了10次缺頁(yè)，其

缺頁(yè)率為10/12=83.3%o

、為進(jìn)程分配4個(gè)物理塊

走向123412512345

塊111111115

塊22222222

塊3335544

塊444333

缺缺缺缺缺缺缺缺

■從上表中可以看出，共發(fā)生了8次缺頁(yè)中斷。其缺

頁(yè)率為8/12=66.7%。

、LRU算法的實(shí)現(xiàn)

-LRU算法實(shí)現(xiàn)時(shí)需要較多的硬件支持，以

記錄進(jìn)程中各頁(yè)面自上次訪問(wèn)以來(lái)有多

長(zhǎng)時(shí)間未被訪問(wèn)。下面介紹幾種實(shí)現(xiàn)方

法。

-計(jì)數(shù)器法

■鏈表法

.卜計(jì)數(shù)器法

-為每個(gè)頁(yè)面配置一個(gè)計(jì)數(shù)器，其初值為0。

當(dāng)進(jìn)程訪問(wèn)某頁(yè)時(shí)，將計(jì)數(shù)器的最高位置1,

定時(shí)器每隔一定時(shí)間將計(jì)數(shù)器右移1位，則

數(shù)值最小的頁(yè)是最近最久未使用的頁(yè)面。

、?計(jì)數(shù)器法（續(xù)）

-1----------------------

、］鏈表法

-用一個(gè)單鏈表保存當(dāng)前進(jìn)程所訪問(wèn)的各頁(yè)面

號(hào)，剛使用過(guò)的頁(yè)面放表尾，則表頭一定是

最近最久未使用的頁(yè)面。其實(shí)現(xiàn)思想為：

-當(dāng)分配給進(jìn)程的物理塊未用完時(shí)，則將進(jìn)程裝入

內(nèi)存的頁(yè)面按先后順序構(gòu)成一個(gè)鏈表

■當(dāng)進(jìn)程訪問(wèn)的頁(yè)面在內(nèi)存時(shí)，將頁(yè)面從鏈表中移

出放到表尾

■當(dāng)進(jìn)程訪問(wèn)的頁(yè)面不在內(nèi)存時(shí)，則發(fā)生缺頁(yè)中斷,

將表頭頁(yè)面置換

?卜鏈表法例

?例如：設(shè)分配給某進(jìn)程4個(gè)物理塊，頁(yè)面訪問(wèn)序列

、14其他頁(yè)面置換算法-二次機(jī)會(huì)算法

-二次機(jī)會(huì)算法是FIFO算法的改進(jìn)，以避

免將經(jīng)常使用的頁(yè)面淘汰掉。

■算法思想：使用FIFO算法選擇一頁(yè)淘汰

時(shí)，先檢查該頁(yè)的引用位，如果是。就立

即淘汰該頁(yè)，如果是1就給它第二次機(jī)會(huì),

將其引用位清0,并將它放入頁(yè)面鏈的末

尾將其裝入時(shí)間置為當(dāng)前時(shí)間，然后選

擇下一個(gè)頁(yè)面。

、］簡(jiǎn)單時(shí)鐘(clock)算法

-簡(jiǎn)單時(shí)鐘置換算法既是對(duì)二次機(jī)會(huì)算法的改進(jìn)，

也是對(duì)LRU算法的近似。

■實(shí)現(xiàn)思想：將頁(yè)面排成一個(gè)循環(huán)隊(duì)列，類似于時(shí)

鐘表面，并使用一個(gè)置換指針。當(dāng)發(fā)生缺頁(yè)時(shí)，

檢查指針指向的頁(yè)面，若其訪問(wèn)位為0則淘汰該

頁(yè)，然后將指針下移一個(gè)位置；否則將該頁(yè)的訪

問(wèn)位清0,指針前移并重復(fù)上述過(guò)程，知道找到

訪問(wèn)位為0的頁(yè)為止。

■該算法也稱為最近未使用(NotRecentlyUsed,

NRU)算法。

，I簡(jiǎn)單時(shí)鐘置換算法頁(yè)面鏈

、■簡(jiǎn)單時(shí)鐘置換算法流程

入口

NI丫

k指針?biāo)疙?yè)面訪問(wèn)位=0?------1

選擇該頁(yè)面淘汰

置頁(yè)面訪問(wèn)位為0I

I指針前進(jìn)一步

-------指針前進(jìn)一步1

返回

、改進(jìn)的時(shí)鐘算法

■將一個(gè)修改過(guò)的頁(yè)面換出需要寫磁盤，其開(kāi)

銷大于未修改頁(yè)面。為此在改進(jìn)型時(shí)鐘算法

中應(yīng)考慮頁(yè)面修改情況。設(shè)R為訪問(wèn)位，U為

修改位，將頁(yè)面分為以下4種類型：

■1類(R=O,U=O)：未被訪問(wèn)又未被修改

■2類(R=O,U=1)：未被訪問(wèn)但已被修改

■3類(R=1,U=O)：已被訪問(wèn)但未被修改

■4類(R=1,U=1)：已被訪問(wèn)且已被修改

、改進(jìn)型時(shí)鐘算法描述

■從指針當(dāng)前位置開(kāi)始掃描循環(huán)隊(duì)列，尋找R=O,U=O

的頁(yè)面，將滿足條件的第一個(gè)頁(yè)面作為淘汰頁(yè)。

■若第1步失敗，則開(kāi)始第2輪掃描，尋找R=O,U=1的

頁(yè)面，將滿足條件的第一個(gè)頁(yè)面作為淘汰頁(yè)，并將

所有經(jīng)歷過(guò)頁(yè)面的訪問(wèn)位置0。

■若第2步失敗，則將指針?lè)祷氐介_(kāi)始位置，然后重復(fù)

第1步，若仍失敗則必須重復(fù)第2步。此時(shí)一定能找

到淘汰頁(yè)面。

■特點(diǎn)：減少了磁盤I/O次數(shù)，但算法本身開(kāi)銷增加。

、最不常用算法（LFU）

-最不常用算法選擇到當(dāng)前時(shí)間為止訪問(wèn)

次數(shù)最少的頁(yè)淘汰。

■該算法要求為每頁(yè)設(shè)置一個(gè)訪問(wèn)計(jì)數(shù)器,

每當(dāng)頁(yè)被訪問(wèn)時(shí)，該頁(yè)的訪問(wèn)計(jì)數(shù)器加1。

發(fā)生缺頁(yè)中斷時(shí)，淘汰計(jì)數(shù)值最小的頁(yè)

面，并將所有計(jì)數(shù)器清零。

、［頁(yè)面緩沖算法

-頁(yè)面緩沖算法是FIFO算法的發(fā)展。

-頁(yè)面緩沖置換算法采用FIFO選擇被置換頁(yè)面,

選擇出的頁(yè)面不是立即換出，而是放入兩個(gè)

鏈表之一。

、頁(yè)面緩沖算法描述

■算法采用FIFO選擇淘汰頁(yè)，規(guī)定將淘汰頁(yè)放

入兩個(gè)鏈表之一：

-空閑鏈：頁(yè)面未修改則放入空閑鏈末尾

■修改鏈：頁(yè)面已修改則放入修改鏈末尾

-當(dāng)需要訪問(wèn)一個(gè)頁(yè)面時(shí)，若該頁(yè)在上述兩個(gè)

隊(duì)列中，則只要將該頁(yè)面從隊(duì)列中移出，否

則用空閑鏈的第一個(gè)物理塊裝入該頁(yè)。當(dāng)修

改鏈中的頁(yè)面數(shù)達(dá)到一定值時(shí)，再將它們一

次寫回磁盤，然后將它們加入空閑頁(yè)面鏈表

中。

、6.2?6頁(yè)面大小的選擇

■頁(yè)面大小的選擇涉及諸多因素，需要在這些

因素之間權(quán)衡利弊。

■頁(yè)表大＜1、：頁(yè)面越小，頁(yè)表越長(zhǎng)。依此應(yīng)選擇大頁(yè)面。

■頁(yè)內(nèi)碎片問(wèn)題：頁(yè)面越大，碎片越大。依此應(yīng)選擇小頁(yè)面。

■內(nèi)外存?zhèn)鬏敚捍笮№?yè)面?zhèn)鬏敃r(shí)間基本相同，依此應(yīng)選擇大頁(yè)面。

■頁(yè)面大小對(duì)缺頁(yè)率的影響：頁(yè)面較小缺頁(yè)率小，頁(yè)面增大

缺頁(yè)率增大然后又下降。

■頁(yè)面大小與主存關(guān)系：主存大則頁(yè)面大。

■程序結(jié)構(gòu)對(duì)缺頁(yè)率的影響：好的程序結(jié)構(gòu)可以降低缺頁(yè)率。

■頁(yè)面大小與快表命中率的關(guān)系：頁(yè)面小快表命中

率低。

、頁(yè)面大小選擇的分析

-設(shè)系統(tǒng)內(nèi)每個(gè)進(jìn)程的平均長(zhǎng)度為S,頁(yè)面大小

為P，每個(gè)頁(yè)表項(xiàng)需e個(gè)字節(jié)。

■每個(gè)進(jìn)程頁(yè)表長(zhǎng)度：S/P

■頁(yè)表占用空間：se/p

■每進(jìn)程碎片的平均大小：p/2

■每進(jìn)程浪費(fèi)的空間為：se/p+p/2

■對(duì)P求導(dǎo)數(shù)：=l/2-se/p2

■令導(dǎo)數(shù)為0求最小值：l/2s-e/p2=o

■則頁(yè)面大小為：p=V2es時(shí),f最小。

、頁(yè)面大小選擇的分析（續(xù)）

■考慮其他因素，商用計(jì)算機(jī)的頁(yè)面尺寸多在

512B到4KB之間。

、627工作集和抖動(dòng)

-工作集：指在某段時(shí)間間隔A里，進(jìn)程實(shí)

際訪問(wèn)的頁(yè)面集合，具體地說(shuō)便是把某

進(jìn)程在時(shí)間t-A到t之間所訪問(wèn)的頁(yè)面集合

記為w(t,A),把變量A稱為工作集窗口

尺寸。

■為使進(jìn)程能有效運(yùn)行，減少缺頁(yè)率，就

必須使進(jìn)程的工作集全在內(nèi)存中。

.卜抖動(dòng)

-抖動(dòng)：如果運(yùn)行進(jìn)程的大部分時(shí)間都用于頁(yè)

面的換入/換出，而幾乎不能完成任何有效的

工作，則稱此進(jìn)程處于抖動(dòng)狀態(tài)。抖動(dòng)又稱

為顛簸、顫動(dòng)。

■抖動(dòng)分為：

■局部抖動(dòng)

■全局抖動(dòng)

CPU利用率與多道程序度的關(guān)系

-左圖是CPU利用率與程序道數(shù)的關(guān)

系。

■開(kāi)始時(shí)CPU利用率會(huì)隨著程序道數(shù)

的增加而增加，當(dāng)程序道數(shù)增加到

利用率

CPU一定數(shù)量以后，程序道數(shù)的增加會(huì)

使CPU的利用率急劇下降。

.多道程序度

0

、抖動(dòng)產(chǎn)生的原因

-抖動(dòng)產(chǎn)生的原因有：

■進(jìn)程分配的物理塊太少

■置換算法選擇不當(dāng)

■全局置換使抖動(dòng)傳播

■卜抖動(dòng)的發(fā)現(xiàn)

-抖動(dòng)發(fā)生前會(huì)出現(xiàn)一些征兆，可利用這些征

兆發(fā)現(xiàn)抖動(dòng)并加以防范。這些技術(shù)有：

■全局范圍技術(shù)

■L=S準(zhǔn)則

-利用缺頁(yè)率發(fā)現(xiàn)抖動(dòng)

-平均缺頁(yè)頻率

■卜全局范圍技術(shù)

-全局范圍技術(shù)采用時(shí)鐘置換算法，用一個(gè)計(jì)

數(shù)器C記錄搜索指針掃描頁(yè)面緩沖的速度。

■若C的值大于給定的上限值，說(shuō)明缺頁(yè)率太高

（可能抖動(dòng)）或找不到可供置換的頁(yè)面，這時(shí)應(yīng)

減少程序道數(shù)。

.若C小于給定的下限值，表明缺頁(yè)率小或存在較

多可供置換的頁(yè)面，這時(shí)應(yīng)增加程序的道數(shù)。

.卜1_=5準(zhǔn)則

-實(shí)際證明，產(chǎn)生缺頁(yè)的平均時(shí)間L等于系

統(tǒng)處理缺頁(yè)的平均時(shí)間S時(shí)，CPU的利用

率達(dá)到最大。

■當(dāng)LvS時(shí)，表明系統(tǒng)頻繁缺頁(yè)，CPU利用

率低，會(huì)導(dǎo)致系統(tǒng)抖動(dòng)。

、］利用缺頁(yè)率發(fā)現(xiàn)抖動(dòng)

■下圖是缺頁(yè)率與進(jìn)程分得物理塊數(shù)之間的關(guān)系。

當(dāng)缺頁(yè)率超過(guò)上限時(shí)會(huì)引起抖動(dòng)，因此應(yīng)增加

分配給進(jìn)程的物理塊；此時(shí)每增加一個(gè)物理塊,

其缺頁(yè)率明顯降低；當(dāng)進(jìn)程缺頁(yè)率達(dá)到下限值

缺頁(yè)率時(shí)，物理塊的進(jìn)一步增加對(duì)進(jìn)程缺頁(yè)率的影響

不大。

……〈......................上限

……….….…下限

--------------------------------物理塊

.卜缺頁(yè)率算法

-缺頁(yè)率算法是一種直接的控制抖動(dòng)方法。該

方法要求為每頁(yè)設(shè)一個(gè)使用位，當(dāng)該頁(yè)被訪

問(wèn)時(shí)，相應(yīng)位置1。同時(shí)設(shè)計(jì)一個(gè)計(jì)數(shù)器，記

錄自上次進(jìn)程產(chǎn)生缺頁(yè)以來(lái)進(jìn)程執(zhí)行的時(shí)間。

■方法1：設(shè)置一個(gè)閾值F,如最近兩次缺頁(yè)時(shí)

間間隔小于F,則分配一個(gè)物理塊給該進(jìn)程；

否則淘汰使用位為0的頁(yè)，并減少該進(jìn)程的物

理塊數(shù)，同時(shí)將該進(jìn)程的剩余頁(yè)使用位重置

為0。

、［缺頁(yè)率算法（續(xù)）

-方法2：設(shè)置兩個(gè)閾值，當(dāng)缺頁(yè)率達(dá)到上限值

時(shí)為進(jìn)程增加物理塊，當(dāng)缺頁(yè)率達(dá)到下限值

時(shí)減少進(jìn)程的物理塊。

■缺頁(yè)率算法的缺點(diǎn)：當(dāng)進(jìn)程由一個(gè)局部轉(zhuǎn)移

到另一個(gè)局部時(shí)，在原局部中的頁(yè)面未移出

內(nèi)存之前，連續(xù)的缺頁(yè)會(huì)導(dǎo)致該進(jìn)程在內(nèi)存

的頁(yè)面迅速增加，產(chǎn)生對(duì)內(nèi)存請(qǐng)求的高峰。

.卜平均缺頁(yè)頻率

-設(shè)ti為兩次缺頁(yè)之間的間隔時(shí)間，fj為其缺頁(yè)

頻率，則有：fj=1/tj

-設(shè)F為平均缺頁(yè)頻率，則有：

■F=(fi+f2+..?+fn)/n

■當(dāng)F大于系統(tǒng)中規(guī)定的允許缺頁(yè)頻率時(shí)，則說(shuō)

明系統(tǒng)中缺頁(yè)率過(guò)高，有可能引起抖動(dòng)。

、抖動(dòng)的預(yù)防及解除

-采用局部置換策略可以防止抖動(dòng)傳播

■利用工作計(jì)模型防止抖動(dòng)：給進(jìn)程分配工作

集所需的物理塊。

■掛起進(jìn)程來(lái)解決抖動(dòng)。

■選擇掛起進(jìn)程的條件

?優(yōu)先級(jí)最低：符合進(jìn)程調(diào)度原則

■發(fā)生缺頁(yè)中斷的進(jìn)程：內(nèi)存不含工作集，缺頁(yè)時(shí)

應(yīng)阻塞

■最后被激活的進(jìn)程：工作集可能不在內(nèi)存

■最大的進(jìn)程：可釋放較多空間

、［程序結(jié)構(gòu)對(duì)缺頁(yè)率影響例

設(shè)頁(yè)面大小為128字節(jié)，二維數(shù)組為128X128,初

始時(shí)未裝入數(shù)據(jù)，需將數(shù)組初始化為0。若數(shù)組按行

存放，問(wèn)下述兩個(gè)程序段的缺頁(yè)率各為多少？

■程序1程序2

shortinta[128][128]；

for(j=0;j<=127;j++)for(i=0;i<=127;i++)

for(i=0;i<=127;i++)for(j=0;j<=127;j++)

a[i][j]=0;a[i][j]=0;

、［程序1的缺頁(yè)次數(shù)

■因數(shù)組以行為主存放，

■程序

1頁(yè)面大小為128字節(jié)，

shortinta[128][128]；故每行占一個(gè)頁(yè)面。

for(j=0;j<=127;j++)■程序1的內(nèi)層循環(huán)將每

for(i=0;i<=127;i++)行中的指定列置為0,

故產(chǎn)生128次中斷。

a[i][j]=0;

■外層循環(huán)128次，總?cè)?/p>

頁(yè)次數(shù)為128X128。

、.程序2的缺頁(yè)次數(shù)

一■1----------------------

鏟住,■因數(shù)組以行為主存放,

■程序2頁(yè)面大小為128字節(jié)，

shortinta[128][128]；故每行占一個(gè)頁(yè)面。

for(i=0;i<=127;i++)■程序2的內(nèi)層循環(huán)將每

for(j=0;j<=127;j++)行的所有列置為0,故

產(chǎn)生1次中斷。

a[i][j]=0;

■外層循環(huán)128次，總?cè)?/p>

頁(yè)次數(shù)為128。

、［缺頁(yè)率對(duì)有效訪問(wèn)時(shí)間的影響

■有效訪問(wèn)時(shí)間是指訪問(wèn)存儲(chǔ)器所需時(shí)間的平

均值。

■假設(shè)使用了快表，則CPU訪問(wèn)內(nèi)存時(shí)有以下

三種情況：

■頁(yè)面在內(nèi)存且頁(yè)表項(xiàng)在快表中：只需一次訪問(wèn)內(nèi)

存

■頁(yè)面在內(nèi)存但頁(yè)表項(xiàng)不在快表中：需兩次訪問(wèn)內(nèi)

存

■頁(yè)面不在內(nèi)存：缺頁(yè)中斷時(shí)間

■.缺頁(yè)中斷處理時(shí)間______

—rl--------------

■缺頁(yè)中斷處理時(shí)間由三部分組成：

■缺頁(yè)中斷服務(wù)時(shí)間

■頁(yè)面?zhèn)魉蜁r(shí)間：包括讀缺頁(yè)和寫置換頁(yè)的時(shí)

間

.進(jìn)程重新執(zhí)行時(shí)間

■由于缺頁(yè)中斷服務(wù)時(shí)間及進(jìn)程重新執(zhí)行

時(shí)間較短，這里僅考慮頁(yè)面?zhèn)魉蜁r(shí)間。

.b有效訪問(wèn)時(shí)間

-設(shè)內(nèi)存讀寫周期為m,缺頁(yè)中斷服務(wù)時(shí)間為t,

快表命中率為p,缺頁(yè)中斷率為f,則有效訪

問(wèn)時(shí)間為：

■EAT=pXm+(1-p-f)X2m+fxt

■設(shè)p=0,8,m=100ns,t=10ms,貝U：

.EAT=0,8x0.1+(1-0,8-f)x2x0.1+fxlOx1000

■=0.12+9999.8f(|js)

■若f為6001,則EAT為10.1198微秒，是沒(méi)有

缺頁(yè)時(shí)間(0.12)的84倍。

、6.2.8頁(yè)的共享與保護(hù)

■在分頁(yè)存儲(chǔ)管理系統(tǒng)中，信息的共享是

通過(guò)使多個(gè)進(jìn)程頁(yè)表項(xiàng)指向同一個(gè)物理

塊來(lái)實(shí)現(xiàn)的。

-分頁(yè)存儲(chǔ)管理采用兩種方式保護(hù)內(nèi)存：

■地址越界保護(hù)：頁(yè)表長(zhǎng)度與邏輯地址中的頁(yè)

號(hào)比較

■存取控制保護(hù)：在頁(yè)表中增加保護(hù)位

、6.3請(qǐng)求分段存儲(chǔ)管理-

■請(qǐng)求分段存儲(chǔ)管理是另一種實(shí)現(xiàn)虛擬存儲(chǔ)器

的方法。

-分段有如下優(yōu)點(diǎn)：

■有利于動(dòng)態(tài)增長(zhǎng)

■允許按段進(jìn)行編譯

■有利于共享

■有利于保護(hù)

、63.1請(qǐng)求分段的實(shí)現(xiàn)思想

■請(qǐng)求分段存儲(chǔ)管理系統(tǒng)基于分段存儲(chǔ)管理，

是在分段存儲(chǔ)管理系統(tǒng)的基礎(chǔ)上，增加了請(qǐng)

求調(diào)段、分段置換功能所形成的一種虛擬存

儲(chǔ)系統(tǒng)。

■在請(qǐng)求分段存儲(chǔ)管理中，作業(yè)運(yùn)行之前，只

要求將當(dāng)前需要的若干個(gè)分段裝入主存，便

可啟動(dòng)作業(yè)運(yùn)行。在作業(yè)運(yùn)行過(guò)程中，若所

要訪問(wèn)的分段不在主存，則通過(guò)調(diào)段功能將

其調(diào)入，同時(shí)還可以通過(guò)置換功能將暫時(shí)不

用的分段換出到外存上，以便騰出內(nèi)存空間。

、請(qǐng)求分段的支持機(jī)構(gòu)

-請(qǐng)求分段的支持機(jī)構(gòu)有：

■段表

■缺段中斷機(jī)構(gòu)

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

■請(qǐng)求調(diào)段和分段置換軟件

?卜段表結(jié)構(gòu)

-請(qǐng)求分段系統(tǒng)中使用的主要數(shù)據(jù)結(jié)構(gòu)仍然是

段表。

■由于每次只將作業(yè)的一部分調(diào)入內(nèi)存，還有

一部分內(nèi)容存放在磁盤上，故需擴(kuò)充段表表

項(xiàng)，擴(kuò)充后的段表項(xiàng)如下所示：

、段表項(xiàng)中各字段的說(shuō)明

訪

問(wèn)

段基存取修改存在增補(bǔ)外存

段

段號(hào)段長(zhǎng)字

址方式位位位地址

■段號(hào)、段長(zhǎng)和段基址：其定義同分段存儲(chǔ)管理。

■存取方式：標(biāo)識(shí)該分段的存取方式：讀、寫、執(zhí)行。

■訪問(wèn)字段：記錄該段在一段時(shí)間內(nèi)被訪問(wèn)的次數(shù)。

■修改位：表示該段調(diào)入內(nèi)存后是否被修改過(guò)。

■存在位：表示該段是否在主存中。

■增補(bǔ)位：指出該段在運(yùn)行過(guò)程中，是否作過(guò)動(dòng)態(tài)增長(zhǎng)。

-外存地址：指出該段在外存上的地址。

、缺段中斷處理

■在請(qǐng)求分段系統(tǒng)中，每當(dāng)所訪問(wèn)的段不在內(nèi)

存時(shí)，便產(chǎn)生一個(gè)缺段中斷信號(hào)，請(qǐng)求OS

將所缺分段調(diào)入內(nèi)存。

■缺段中斷與缺頁(yè)中斷類似，也是在指令執(zhí)行

期間產(chǎn)生和處理。

、缺段中斷處理流程

缺段中斷處理

I

阻塞請(qǐng)求進(jìn)程淘汰實(shí)段以形成合適的空閑區(qū)

1NA

內(nèi)存中有合適的空閑區(qū)嗎？----?空閑區(qū)容量總和能否滿足

Yl^----lY

從外存讀入缺段拼接以形成合適的空閑區(qū)

II

修改段表及內(nèi)存空閑區(qū)鏈---------------±-------------y

喚醒請(qǐng)求進(jìn)程一?返回

、■缺段中斷涉及的幾個(gè)問(wèn)題

-fl-------------------------------------------------------------------------------------------------------------------

■內(nèi)存管理：請(qǐng)求分段的內(nèi)存管理與與分

區(qū)管理類似，采用連續(xù)內(nèi)存管理方式。

■段的置換：調(diào)入缺段時(shí)，若有足夠的空

閑分區(qū)則直接調(diào)入，否則查看空閑區(qū)之

和能否滿足要求，若能則進(jìn)行拼接，否

則進(jìn)行置換。置換時(shí)可能要淘汰多段。

、動(dòng)態(tài)地址變換

■請(qǐng)求分段系統(tǒng)的地址變換是在分段系統(tǒng)地址

變換的基礎(chǔ)上形成的。

■在地址變換過(guò)程中，若段在內(nèi)存則判斷其存

取權(quán)限是否合法，若合法則從段表中取出該

段在內(nèi)存的起始地址，與段內(nèi)位移相加形成

訪問(wèn)內(nèi)存附物理地址。

■若段不在內(nèi)存，則產(chǎn)生缺段中斷信號(hào)，請(qǐng)求

OS將缺段調(diào)入內(nèi)存，然后修改段表，再利用

段表進(jìn)行地址變換。

、請(qǐng)求分段的地址變換過(guò)程

程序請(qǐng)求訪問(wèn)一段

I

段號(hào)〈段表長(zhǎng)度，段內(nèi)位移V段長(zhǎng)？——?分段越界處理

Yl

N

符合存取方式？-------?分段保護(hù)處理

IY

N

分段在主存中？---------?缺段中斷處理

I丫

修改訪問(wèn)位和修改位

I

形成物理地址

返回

、I引入快表提高訪問(wèn)速度

-與請(qǐng)求分頁(yè)管理一樣，請(qǐng)求分段的地址

變換過(guò)程必須訪問(wèn)內(nèi)存兩次以上。

-為提高訪問(wèn)速度，也可以使用快表。

、6.3,2段的共享與保護(hù)

■在分段存儲(chǔ)管理系統(tǒng)中，信息的共享是通

過(guò)使多個(gè)進(jìn)程的段表項(xiàng)指向同一內(nèi)存區(qū)域

實(shí)現(xiàn)的。

■為了實(shí)現(xiàn)分段共享，可在系統(tǒng)中設(shè)置一張

共享段表，所有共享分段都在其中占有一

表項(xiàng)。共享段表的格式如下：

、］共享段表及表項(xiàng)

■共享進(jìn)程計(jì)數(shù)：記錄有多少進(jìn)程共享該段。

■存取控制字段：對(duì)同一共享段，不同進(jìn)程有不同的操作權(quán)限。

-段號(hào)：共享段在不同進(jìn)程中有不同的段號(hào)。

■卜共享段的分配

-當(dāng)為共享段分配內(nèi)存時(shí)，對(duì)第一個(gè)請(qǐng)求使用

該段的進(jìn)程，系統(tǒng)為該共享段分配一個(gè)內(nèi)存

區(qū)，再將該共享段調(diào)入，同時(shí)將該區(qū)的始址

填入請(qǐng)求進(jìn)程的段表，還需在共享段表中增

加一項(xiàng)，填寫有關(guān)數(shù)據(jù)并將count置1。

■此后，當(dāng)又有其他進(jìn)程申請(qǐng)使用該共享段時(shí),

只需將count加1并填寫有關(guān)數(shù)據(jù)結(jié)構(gòu)。

、■共享段的回收

---------------------------------------------------------------------------------------------------------------

-當(dāng)某進(jìn)程不再需要使用共享段時(shí)，應(yīng)釋放該

段。此時(shí)應(yīng)將該進(jìn)程段表中共享段的對(duì)應(yīng)表

項(xiàng)撤消，并將count減1,若結(jié)果為。則需要系

統(tǒng)回收共享段的物理內(nèi)存及有關(guān)表項(xiàng)，否則

僅取消該進(jìn)程在共享段中的記錄。

、.可重入代碼

-rl-----------------------------

■可重入代碼又稱為純代碼，是允許多個(gè)

進(jìn)程同時(shí)訪問(wèn)的代碼?？芍厝氪a在執(zhí)

行中不能修改。

、［6,3.3虛擬段頁(yè)式存儲(chǔ)管理系統(tǒng)

-虛擬段頁(yè)式存儲(chǔ)管理系統(tǒng)是虛擬頁(yè)式和

虛擬段式存儲(chǔ)管理的結(jié)合。

、［習(xí)題

■P147

■3(1)

■3(2)

■3(3)

■3(4)

.'UNIX存儲(chǔ)管理

■在早期的UNIX系統(tǒng)中，為提高內(nèi)存的利用率,

已提供了內(nèi)存與外存之間的進(jìn)程對(duì)換機(jī)制。

■在UNIXSYSTEMV中，除對(duì)換功能外還支

持請(qǐng)求調(diào)頁(yè)的存儲(chǔ)管理方式。每個(gè)頁(yè)面的大

小隨版本不同而異，一般在512B?4KB之間。

請(qǐng)求調(diào)頁(yè)管理的數(shù)據(jù)結(jié)構(gòu)

■在UNIX系統(tǒng)中，為實(shí)現(xiàn)請(qǐng)求調(diào)頁(yè)，核心

配置了四種數(shù)據(jù)結(jié)構(gòu)：

■頁(yè)表

■磁盤塊描述表

■頁(yè)面數(shù)據(jù)表

■對(duì)換使用表

”頁(yè)表

T1--------------------------------

■每個(gè)頁(yè)表項(xiàng)中需包含以下字段：

■物理塊號(hào)。即頁(yè)在內(nèi)存中的物理塊號(hào)。

-年齡。記錄該頁(yè)在內(nèi)存中有多長(zhǎng)時(shí)間未訪問(wèn)。

-訪問(wèn)位。指示該頁(yè)最近是否被訪問(wèn)過(guò)。

-修改位。指示該頁(yè)內(nèi)容是否被修改過(guò)。

-有效位。指示該頁(yè)內(nèi)容是否有效。

-寫時(shí)拷貝位。指示進(jìn)程修改該頁(yè)時(shí)，是否要為該頁(yè)建立

拷貝。

-保護(hù)位。指示該頁(yè)允許的訪問(wèn)方式，如只讀、讀寫。

磁盤塊描述表

■在UNIX系統(tǒng)中，每個(gè)頁(yè)表項(xiàng)對(duì)應(yīng)一個(gè)磁盤塊

描述項(xiàng)，記錄頁(yè)面的磁盤拷貝所在的磁盤塊

號(hào)。磁盤塊描述項(xiàng)中包含：

■對(duì)換設(shè)備號(hào)：頁(yè)面副本所在設(shè)備號(hào)。

■塊號(hào)：頁(yè)面副本所在塊號(hào)。

■類型：頁(yè)面副本在可執(zhí)行文件中時(shí)類型為File,在

對(duì)換設(shè)備上時(shí)類型為Disk。

、頁(yè)表表項(xiàng)和磁盤塊描述項(xiàng)

貝面物理地址年齡有效位訪問(wèn)位修改位寫時(shí)拷貝位保護(hù)位

磁盤塊描述項(xiàng)

對(duì)換設(shè)備號(hào)塊號(hào)類型（對(duì)換、文件）

.,.?、r_；l!~zT一?*

、［頁(yè)面

-頁(yè)面數(shù)據(jù)表項(xiàng)描述內(nèi)存中的一個(gè)物理塊，包含:

■頁(yè)狀態(tài)。指示頁(yè)面拷貝是在對(duì)換設(shè)備上還是在可

執(zhí)行文件中。

■內(nèi)存引用計(jì)數(shù)。指出引用該頁(yè)面的進(jìn)程數(shù)目。

■邏輯設(shè)備。指出含有該頁(yè)面拷貝的邏輯設(shè)備和塊

號(hào)。

■空閑頁(yè)面鏈指針和散列隊(duì)列指針。

■為分配一個(gè)物理塊，核心從空閑鏈表首部摘下

一個(gè)空閑頁(yè)表項(xiàng)，修改其對(duì)換設(shè)備號(hào)和塊號(hào)后,

將它放到相應(yīng)的散列隊(duì)列中。

?卜對(duì)換使用表

-對(duì)換設(shè)備上的每一塊都占有對(duì)換使用表

中的一個(gè)表項(xiàng)。

■表項(xiàng)中含有一個(gè)引用計(jì)數(shù)，表示有多少

頁(yè)表項(xiàng)指向該塊。

、四種數(shù)據(jù)結(jié)構(gòu)間的關(guān)系

■一個(gè)進(jìn)程的虛地址為1493K,其物理頁(yè)為794,其拷

貝在對(duì)換設(shè)備1的2743號(hào)塊中。

■卜偷頁(yè)進(jìn)程

-UNIX系統(tǒng)中設(shè)置了一個(gè)偷頁(yè)進(jìn)程，其主

要任務(wù)是：

■每隔一定時(shí)間增加內(nèi)存中所有有效頁(yè)的年齡;

■當(dāng)有效頁(yè)的年齡達(dá)到規(guī)定值后便將它換出。

增加有效頁(yè)年齡

■設(shè)用兩位作為年齡域，當(dāng)頁(yè)面的年齡為0、1、

2時(shí)，頁(yè)面處于不可換出狀態(tài)；而當(dāng)其年齡達(dá)

到3時(shí)，便可將它換出內(nèi)存。

■當(dāng)內(nèi)存中的空閑頁(yè)面數(shù)低于某規(guī)定的下限時(shí)，

核心喚醒偷頁(yè)進(jìn)程去檢查內(nèi)存中的每一個(gè)活動(dòng)

區(qū)，對(duì)所有有效頁(yè)的年齡字段加1。

■對(duì)于那些年齡字段已增至3的頁(yè)面便不再加1,

而是將它們換出。每當(dāng)有進(jìn)程訪問(wèn)了某個(gè)頁(yè)面

時(shí)，便將該頁(yè)的年齡設(shè)置為0。

有效頁(yè)年齡的變化

頁(yè)狀態(tài)時(shí)間上次訪問(wèn)以來(lái)

在內(nèi)存0

1

2頁(yè)被訪問(wèn)

0

1

2

3頁(yè)被換出

不在內(nèi)存

、對(duì)換出頁(yè)的幾種處理方式(1)

-若對(duì)換設(shè)備上有換出頁(yè)的拷貝且換出頁(yè)的內(nèi)

容未修改，則只需將頁(yè)表項(xiàng)的有效位清零，

并將頁(yè)面數(shù)據(jù)表項(xiàng)中的引用數(shù)減1,再將該頁(yè)

表項(xiàng)放入空閑頁(yè)面鏈表中。

、對(duì)換出頁(yè)的幾種處理方式(2)

■若對(duì)換設(shè)備上沒(méi)有換出頁(yè)的拷貝，則應(yīng)將該

頁(yè)寫到對(duì)換設(shè)備上。

■通常偷頁(yè)進(jìn)程先將要換出的頁(yè)鏈到一個(gè)鏈表

上，當(dāng)換出頁(yè)面鏈上的頁(yè)數(shù)達(dá)到某一規(guī)定值

時(shí)，核心才真正將這些頁(yè)面換出。

、對(duì)換出頁(yè)的幾種處理方式(3)

■在對(duì)換設(shè)備上已有換出頁(yè)的副本，但該頁(yè)內(nèi)

容已被修改過(guò)。此時(shí)核心將該頁(yè)在對(duì)換設(shè)備

上原來(lái)占有的空間釋放，再重新將該頁(yè)拷貝

到對(duì)換設(shè)備上。

、將換出頁(yè)面寫到對(duì)換設(shè)備上

■當(dāng)換出頁(yè)面鏈上的頁(yè)數(shù)達(dá)到規(guī)定值時(shí)，核心先為這

些頁(yè)分配連續(xù)的對(duì)換空間以便將它們換出；

■當(dāng)核心向?qū)Q設(shè)備上寫一個(gè)頁(yè)面時(shí)，應(yīng)首先清除該

頁(yè)表項(xiàng)的有效位，并將對(duì)應(yīng)頁(yè)面數(shù)據(jù)表項(xiàng)中的引用

數(shù)減1。

■若引用計(jì)數(shù)為0,表明已無(wú)進(jìn)程引用該頁(yè)，核心便

將其頁(yè)面數(shù)據(jù)表項(xiàng)鏈入空閑頁(yè)面鏈表的尾部。

-最后，核心將分配給該頁(yè)的對(duì)換空間地址填入相應(yīng)

的磁盤塊描述項(xiàng)中，并將對(duì)換使用表中的計(jì)數(shù)加1。

、將換出頁(yè)面寫到對(duì)換設(shè)備上例

■例如偷頁(yè)進(jìn)程以A、B、C、D的順序檢查進(jìn)程的頁(yè)

面，并準(zhǔn)備分別將進(jìn)程A、B、C和D的30、40、50

和20個(gè)頁(yè)面換出，每64個(gè)頁(yè)面為一批。下圖給出了

頁(yè)面的換出過(guò)程和對(duì)換空間的分配情況。

.卜請(qǐng)求調(diào)頁(yè)

-當(dāng)一個(gè)進(jìn)程存取一個(gè)有效位為0的頁(yè)面時(shí)將產(chǎn)

生一個(gè)有效性錯(cuò)。此時(shí)由核心調(diào)用有效性錯(cuò)

處理程序加以處理。可能有下列兩種情況：

■若在磁盤塊描述項(xiàng)中找不到所缺的頁(yè)，則表明此

次內(nèi)存訪問(wèn)非法，核心將向該進(jìn)程發(fā)出一個(gè)“段

違例”軟中斷信號(hào)。

■若找到了所缺的頁(yè)，表明此次內(nèi)存訪問(wèn)合法；核

心為該頁(yè)分配一個(gè)內(nèi)存塊，并將所缺的頁(yè)調(diào)入內(nèi)

存。

、缺頁(yè)在可執(zhí)行文件中

-如果頁(yè)面對(duì)應(yīng)的磁盤塊描述項(xiàng)中的類型是

File,表示缺頁(yè)在可執(zhí)行文件中。

■其具體的調(diào)入過(guò)程為：根據(jù)該文件所對(duì)應(yīng)的

系統(tǒng)區(qū)表項(xiàng)中的索引節(jié)點(diǎn)指針，找到該文件

的索引節(jié)點(diǎn)；再?gòu)拇疟P塊描述項(xiàng)中找到該頁(yè)

的邏輯塊號(hào)，以此作為偏移量查找索引節(jié)點(diǎn)

中的磁盤塊號(hào)表，便可找到該頁(yè)所在的磁盤

塊號(hào)，再將該頁(yè)調(diào)入內(nèi)存。

?缺頁(yè)在可執(zhí)行文件中例■地址1K

二」

頁(yè)表項(xiàng)磁盤塊描述項(xiàng)貝面數(shù)據(jù)表

虛地址物理貞狀態(tài)狀態(tài)塊頁(yè)磁盤塊引用數(shù)

0

1K1648InvFile3

2K13063870

1

11

1—

164816181

64K1917InvDisk1206

1

1

65K1

66K1036InvDisk847186112060

虛地址物理災(zāi)狀態(tài)狀態(tài)塊頁(yè)磁盤塊引用數(shù)

66K1776valDisk84717768471

、缺頁(yè)在對(duì)換設(shè)備上

-如果頁(yè)面所對(duì)應(yīng)的磁盤塊描述項(xiàng)中的類型是

Disk,表示該缺頁(yè)在對(duì)換設(shè)備上。

■其調(diào)入過(guò)程為：核心先為缺頁(yè)分配一個(gè)內(nèi)存塊,

修改該頁(yè)表項(xiàng)，并將頁(yè)面數(shù)據(jù)表項(xiàng)放入相應(yīng)的

散列隊(duì)列中，然后把該頁(yè)從對(duì)換設(shè)備上調(diào)入內(nèi)

存。當(dāng)I/O操作完成時(shí)，核心將請(qǐng)求調(diào)入該頁(yè)

的進(jìn)程喚醒。

二f缺頁(yè)在對(duì)換設(shè)備上例?66K

■頁(yè)表項(xiàng)

磁盤塊描述項(xiàng)頁(yè)面數(shù)據(jù)表

虛地比:物理員狀態(tài)狀態(tài)塊頁(yè)磁盤塊引用數(shù)

0

1K1648InvFile3

2K13063870

1

11

1—

164816181

64K1917InvDisk1206

1

1

65K