計算機操作系統(tǒng)課件第4章 存儲器管理

內袞提要

.

存儲器管理的相關概念

他連續(xù)分配方式

分頁式存儲管理方式

分段式存儲管理方式

虛擬存儲器

請求分頁為存儲管理方式

頁面置換算法

請求分段式存儲管理方式

,存儲器管理

r⑥存儲器管理的對象包括內存和外存，主

要討論的是內存

@計算機內存被劃分成兩部分：條統(tǒng)區(qū)和

■用戶區(qū)。存儲器的管理主要是針對用戶

■區(qū)的分配和管理

存儲器管理的巨的：一是方便用戶使用,

二是提高存儲器的利用率

存儲器管理的功能

⑥內存的分配與回收

r@地址轉換或重定住

?@存儲器的獷充

存儲器共享和保護

源程序從創(chuàng)建到執(zhí)行的步驟

年接八

源程序從創(chuàng)建到執(zhí)行的步驟

第一步第二步第三步

存儲器管理的相關概念

@物理存儲器中全部物理存儲單元的集

合所限定的空間稱為儲空間

gI每個存儲單元都有它自己的編號地址,

該地址被稱為絕對地址，式物理地址，

或賣地址

q儲空間的大小由系統(tǒng)的硬件配置決

存儲器管理的相關概念

@用戶源程序經編譯鏈接后形成的代碼

所F艮定的地址叫做該程序的

地址無間中每個單元的地址稱為

1地址，或透輯地址，或虛地址

存儲器管理的相關概念

@存儲分配要解決的問題是多道程序之

間如何共享主存的存儲空問

亶I斛決存儲分配問題的三種方式：直接

存儲分配方式、靜態(tài)存儲分配方式、

動態(tài)存儲分配方式

存儲器管理的相關概念

?把程序地址無間的近屬地址轉換為存儲

，空間的物理地址的工作叫做也抓,

■又叫或地址變換

國地址重定住分靜忐重定住和動忠重走住

地址重走住的原因

@地址空間的邏輯地址往往與分配到的存

儲無間的物理地址不一玫，而且不能用

■近屬地址在內存中讀取信息

同處理機執(zhí)行用戶程序時，所要訪問的程

■序和數(shù)據(jù)地址必須是實際的物理地址

靜態(tài)地址重定住

@靜點地址重走?。旱刂忿D換工作是在程

序裝入主存時，由靜出重定位裝入程序

■集中~次完成

］無硬件變換機構

皆為每個程序分配一個連續(xù)的存儲區(qū)

同在程序執(zhí)行期間不能移動，主存利用率

］低

尚不能做到程序和數(shù)據(jù)的共享

靜態(tài)地址重定住過程

存儲空間

J動態(tài)地址重走住

電裝八程序把程序和數(shù)據(jù)原樣裝入到已分

配的存儲區(qū)中，然后把這個五儲區(qū)的超

始地址送入重走住寄存器中。在程序執(zhí)

行時，再將相對地址轉換成絕對地址

主存利用率高

程序不必占有連續(xù)的存儲空間

便于多用戶共享同一程序

動態(tài)地址重定住過程

重定位

OS

■■■

movr1,[1500]

■■■

1234

作業(yè)地址空間

■■■

存儲空間

連續(xù)分配方式

連續(xù)分配是指為~個用戶程序分配

一個連續(xù)的內存空間，這種方式曾被廣

泛地應用于早期的操作系統(tǒng)中。

連續(xù)分配的兩種方式

一連續(xù)分配方式

分區(qū)式分配方式

連續(xù)分配方式的類型

（單一連續(xù)分配存儲管理

連續(xù)分配〈

固定分區(qū)存儲管理

b分區(qū)管理，

動忐分區(qū)存儲管理

單一連續(xù)分配方式

只能用于單用戶、單任務的操作系統(tǒng)中

在這種管理方式下，內存區(qū)分為

和］戶區(qū)兩部分，宗統(tǒng)區(qū)僅供操作系統(tǒng)

使用，用戶區(qū)提供給用戶使用

不支持虛擬存儲方式

優(yōu)點是管理簡單，易于實現(xiàn)存儲保護

單一連續(xù)分配方式的缺點

@索統(tǒng)的存儲空間浪費較大

當正在執(zhí)行的程序因等待某個事件，

如等待外部設備輸入數(shù)據(jù)，處理機就

處于“生悶校忐

F艮制了用戶程序和系統(tǒng)程序的可重人

性，因而主存中的程序和數(shù)據(jù)不能被

共享

$系統(tǒng)的外圍設備也只有一個程序使用,

I因此外圍設備的利用率低

地址映射和地址保護

界限寄重定住

存器寄存器

分區(qū)存儲管理思想

基本思想：將主存的用戶可用區(qū)劃分成

若干個大小不等的區(qū)域，每個選程占據(jù)

一個區(qū)域或多個區(qū)域，從而實現(xiàn)多道程

序設計環(huán)境下各并發(fā)進程共享主存空間

固定分區(qū)管理

@~種最簡單的可運行多道程序的存儲管

理方式

?將內存用戶空間劃分為若干個固定大小

的區(qū)域，每個分區(qū)只裝入~道作業(yè)，這

樣允許有幾道作業(yè)并發(fā)運行

當有全網分區(qū)時，便可從外存的后備作

工隊列中選擇一個迨當大小的作業(yè)裝入

該分區(qū)

,分區(qū)的方法

@分區(qū)大小相等：所有的內存分區(qū)大小相

等，缺點是缺乏靈活性

分區(qū)大小不等：把內存區(qū)劃分成含有多

個較小的分區(qū)、適量的中等分區(qū)及少量

的大分區(qū)。這樣，可根據(jù)程序的大小為

之分配適當?shù)姆謪^(qū)

內存分配

為了便于內存分配，通常將這些

分區(qū)根據(jù)它們的大小排隊，并為之建

立一張分區(qū)使用表。表項中包含每個

分區(qū)的起始地址、大小及技忐（是否

已分配）O

】定分區(qū)使用表

操作系統(tǒng)

分區(qū)號大小(KB)地址(K)狀忠作業(yè)A

11530已分配作業(yè)B

23045已分配作業(yè)C

35075已分配

125K

4100125已分配

J連續(xù)分配方式的優(yōu)缺點

@優(yōu)點：簡單

9缺點：內存利用不充分。因為作業(yè)的大

小不可能剛好等于某個分區(qū)的大小，絕

大多數(shù)已分配的分區(qū)中，都有一部分存

儲空間被浪費掉了，這個被浪費的空間

叫做內存碎片JH

J動態(tài)分邑分配

◎系統(tǒng)初始化時,除了操作系統(tǒng)中常駐

主存部分以外,只存在~個空間分區(qū)

@分配程序根據(jù)進程的大小動忠的劃分

分區(qū)

特點是：各分區(qū)的大小是不定的；內

存中分區(qū)的數(shù)目也是不定的。

動杰分區(qū)分配中的數(shù)據(jù)結構

空間分區(qū)表，用來記錄內存中每個空

網分區(qū)的情況：包括分區(qū)序號，分區(qū)

始址，分區(qū)大小等數(shù)據(jù)項

空間分區(qū)鏈，將所有的全間分區(qū)鏈結

成一個雙向鏈表

分分配異法

首次適應算法FF

首次適應算法

要求全陽分區(qū)按地址遹增的次序排

列。當選行內存分配時，從全間區(qū)鏈鏈

首開始順序查找，直到找到第一個能滿

足其大小要求的全間區(qū)為止。分一塊給

請求者，余下部分仍多在空間鏈中。

首次適應算法的特點

R優(yōu)先利用低地址部分的全陽分區(qū),保

M留了高地址部分的大會間區(qū)

@低地址端可能留下許多很小的全網分

區(qū),而每次查找是從低地址部分開始,

會增加查找開銷

循環(huán)首次適應算法

由首次適應舁法演化而來。在為進

程分配內存空間時，不再每次都從鏈首

開始查找，而是從上次找到的空間分區(qū)

的下一個,空間分區(qū)開始查找，直到找到

一個能滿足要求的空間分區(qū)，從中劃分

出一塊與請求大小相等的內存無間分配

給作業(yè)。

循環(huán)首次適應算法的特點

@使內存中的無間分區(qū)分布得更均勻,

從而減少了查找空間分區(qū)時的開銷

@缺乏大的空間分區(qū)

最佳逶應算法

要掃描所有的空間分區(qū)，以獲得能

滿足進程需求的且為最小的空間區(qū)。如

果該會閑分區(qū)大于作業(yè)的大小，則將剩

余全間區(qū)仍留在全間區(qū)鏈表中。可從小

到大對全間區(qū)排序，方便查找。

最佳適應算法的特點

處因為分配分區(qū)要查找整個鏈表，所以

比首次適應算法效率低

@因為它可能把主存劃分得更小，成為

■無用的碎片，所以它比首次迨應要浪

費更多的存儲如可

分配內存操作

利用某種算法，從全間分區(qū)中找到所

需大小的分區(qū)

值大于事先規(guī)定的不再切割的剩余分

區(qū)的大小,則將全閑分區(qū)一分為二,

一部分分配給進程,另~部分仍作為

全網區(qū)留在表中

將分配區(qū)的首址返回給調用者

回收內存時遇到的情況

分區(qū)管理的優(yōu)點

@實現(xiàn)了多道程序共享主存

@實現(xiàn)分區(qū)管理的條統(tǒng)設計相對簡單,

不需要更多的系統(tǒng)軟硬件開銷

實現(xiàn)存儲保護的手段也比較簡單

Jr

分區(qū)管理的缺點

1⑥主存利用不夠充分。系統(tǒng)中總有一部

分存貯空間得不到利用，這部分被浪

費的空間叫內存碎片

沒有實現(xiàn)主存的獷充問題。當作業(yè)的

地址空間大于存儲空間時,作業(yè)無法

運行。也即作業(yè)的地址空間受實際存

儲無間限制

可重走住分區(qū)分配原理

如果作業(yè)請求的存儲空間大于系統(tǒng)

中任何~個分區(qū)，但小于這些分區(qū)參量

的總和時，利用動忐重定住方法，移動

內存中的所有作業(yè)，使它們在內存相鄰

接。這樣，我們不需要對作業(yè)做任何修

衣，只要用該作業(yè)在內存的新起始地址,

去置換原來的起始地址即可。

緊家

這種通過移動內存中作業(yè)的位置，

把原來多個分散的小的全網分區(qū)拼接成

~個大無網分區(qū)的方法，稱為“拼接”

或“緊?！?。

緊家的示意圖

操作系統(tǒng)操作系統(tǒng)

用戶程序1用戶程序1

用戶程序2

用戶程序2用戶程序3

用戶程序4

用戶程序480K

劫忠重定住的實現(xiàn)

相對地址重定位寄存器

處理機一側

，療充內存的方法

色覆蓋

叵］對換

覆蓋技術

回覆蓋是指一個作業(yè)中的若干程序段或教

據(jù)段共享主存的某個區(qū)域

?覆蓋技術斛決在小的存儲無間運行大作

業(yè)的問題

口覆蓋技術可以讓鄴些不會同時執(zhí)行的程

■序段共用同一個主存區(qū)

同程序執(zhí)行時，把不要求同時裝入主存的

■程序段組成一組，即，并分配同

［一個主存區(qū)（覆蓋區(qū)）O覆蓋段與覆蓋

?區(qū)----對應。

內存分配的覆蓋結構

主程序(30K)

P1

P2覆蓋區(qū)0(10K)

P11覆蓋區(qū)1(25K)

P21

P22

覆蓋技術

當執(zhí)行程序引用當前尚未裝入覆蓋區(qū)的

覆蓋中的例程時，則調用覆蓋管理控制

程序，請求將所需的覆蓋段裝入覆蓋區(qū)

中，宗統(tǒng)響應請求，并自動將所需覆蓋

裝入主存覆蓋區(qū)中

覆蓋技術的關鍵是提供正確的覆蓋結構。

通常覆蓋技術主要用于索統(tǒng)程序的主存

管理上

特點：打破了必須將~個作業(yè)的全部信

息裝入主存后才能運行的限制

交換技術

?交換技術是指索統(tǒng)根據(jù)需要把主存中暫

時不運行的某個（或某些）作業(yè)部分或全

部移到外存，而把外存+的某個（或某

■些）作業(yè)移到相應的主存，并使其投入

?運行

口用輔存作為交換區(qū)，讓多用戶程序在較

■小的4儲空間中通過不斷地換人/換出

■而得到運行。

交換的時機

交換技術的關鍵

設法減少每次交換的信息量。為此，常

將作業(yè)的副本保留在外存，每次換出時,

僅換出那些修改過的信息即可

交換主要是在作業(yè)或進程之間選行，而

覆蓋則可以在同一個或不同作業(yè)間進行

交換打破了一個程序一旦選人主存便一

直運行列結束的喔制

禽散分配方式的分類

⑥分頁存儲管理

色分段存儲管理

■^1段頁式存儲管理

分頁存儲管理方式

在分區(qū)存儲管理中，要求作業(yè)放在一個

連續(xù)的存儲區(qū)域，因而會產生碎片

要斛決碎片問題，條統(tǒng)就要花費很高的

代價去拼接它們

頁式存儲管理的引入，是為了

問題

實現(xiàn)原理

將~個選程的建輯地址,空間分成

若干個大小相等的靈，同時把內存全

間以與頁相等的大小劃分為大小相等

的內存塊r物理塊）,這些內存塊為

系統(tǒng)中的任何進程所共享。在為進程

分配內存時，以塊為單傳將進程中的

若干個頁分別裝入到多個可以不相鄰

接的物理塊中。由于進程的最后一頁

經常裝不滿一塊而形成了不可利用的

碎片，稱之為“頁內碎片”。

頁面和物理塊

@頁面：選程的近屬地址空間分成若干個

大小相等的片，稱為頁面或頁，并為各

頁加以編號，從。開始

啕物理塊：內存空間被分成與頁面相同大

■小的若干個存儲塊，稱為物理塊或內存

塊，也同樣為它們加以編號，如0#塊、

?l#塊等等

頁面大小

在分頁系統(tǒng)中的頁面其大小應適中。頁

面若太小，一方面雖然可使內存碎片或小，

從而臧少了內存碎片的總空間，有利于提嵩

內存利用率，但另一方面也會使每個選程占

用較多的頁面，從而導致進程的頁表過長，

占用大量內存；此外，還會降低頁面換進換

出的效率。然而，如果選擇的頁面較大，雖

然可以減少頁表的長度，提高頁面換更換出

的速度，但卻又會使頁內碎片增大。因此，

頁面的大小應選擇得適中，且頁面大小應是2

的第，通常為512B~8KB。

頁面地址結構

分頁地址結構如T:

3112110

頁號P住移量W

對某特定機器，其地址結構是一定的O

若給定一個近握地址空間中的地址為A,頁

面的大小為L,則頁號P和頁內地址d可按下

式求得：.

JP=IMT——

L

d=乙

地址變換機構

越界中新

頁表寄存器之聘地址L

頁表始址I頁表長度頁號頁內地址

頁號塊號

01

1

2

3Ab

物理地

頁表

地址變換舉例

頁表寄存器

快表和寐想寄存器

為了提高存取速度,可在地址變換機構

中增設一個具有并行查找能力的高速緩

沖寄存器組，又叫，用來存

放頁表的一部分r)o

般想存貯器的存取速度比主存高，但造

價也高，只能少量采用。整個系統(tǒng)通常

只要用8?16個寄存器就可使程序執(zhí)行

速度大大提高。

快表的結構

頁號塊號訪問伉狀態(tài)住

訪問佳：指示該頁最近是否被訪問過。0表

示沒有被訪問，1表示訪問過；

校志佳：指示該寄存器是否被占用。。表示

空閑，1表示占用。

分段存儲管理方式的引入

@方便編程

@分段共享

分段保護

動志鏈接

動態(tài)增長

分段的原理

@每個作業(yè)的地址空間按照程序自身的逐

科關系劃分成若干段，每個段都有自己

的段名

⑥每個段的地址空間都是從“0”開始編址

■的一維地址空間

同作業(yè)的地址無間是二維地址空間

同每一個建輯地址均由兩部分組成：段號

■和段內地址

段號段內地址

段表

作業(yè)空間

內存空間

(MAIN)=O0

40K

(MAIN)=0

030K

80K

20K

120K

(D)=2

15K

150K

(S)=3

10K

分段系統(tǒng)的地址轉換過程

控制寄存器段號S位移量W

越界

段表始址段表長度

段號段長基址

o1K6K

16004K

—:

i5008K

32009200

分頁和分段的王要出別

口頁是信息的物理單位，段則是信息的

邏輯單優(yōu)；

@頁的大小固定且由宗統(tǒng)硬件決定，段

的長度則不固定，大小取決于用戶所

編寫的程序；

分頁的作業(yè)地址，空間是一維的，而分

段的作業(yè)地址空間是二維的。

分段系統(tǒng)的共享示意圖

在分段系統(tǒng)中，為實現(xiàn)共享,只需為文本編聘程

序設置一個段表項，如下圖:

進程1

段長基址80

editoreditor

"so"240

Data1Data1

"40"240

進程2280

editor380

Data2

可重入代碼

可重入代碼，又稱純代碼，是一

種允許多個進程同時訪問的代碼。為

使各個進程執(zhí)行的代碼完全相同，絕

不允許可重人代碼在執(zhí)行中有任何改

變。

段頁式存儲管理原理

段頁式余統(tǒng)的基本原理是分段和

分頁原理的組合，即先將用戶程序分

為若干個段，把每個段分成若干個頁，

并為每個段膩子一個段名。

作業(yè)地址空詞和地址結構

主程序段子程序段數(shù)據(jù)段

00

4K4K

8K8K

12K10K------------------

15K12K?---------------」

16K

段號段內頁號頁內地址

利用段表和頁表實現(xiàn)地址映射

段表

頁表

地址變換機構

存儲管理遇到的兩種情況

作業(yè)很大，要求的內存空間超過了內存

總量，致使作業(yè)無法運行

口大量作業(yè)要運行，內存余量不足以余納

■f所有作業(yè)，這時只能將少數(shù)作業(yè)裝入內

■存，其他大量作業(yè)留在外存上

局部性原理

在?段時間，選程集中在一組子

程序或循環(huán)中執(zhí)行，導致所有的存儲

器訪問局F艮于進程地址空間的一個固

定子集r進程的工作集）-

虛擬存儲器的定義

虛擬存儲器是指具有請求調入

功能和置換功能，能從邏輯上對內

存余量加以獷充的~種存儲器條統(tǒng)。

虛擬存儲器的邏輯袞量由內存和外

存之和來確定，其運行速度接近于

內存速度，而每位的成本接近于外

存。

引入虛擬存儲器的好處

@運行大程序

@大的用戶空間

并發(fā)

易于開發(fā)

虛擬存儲器的特征

@離散性

@多次性

加對換性

置虛擬性

虛擬存儲器的實現(xiàn)方式

也分頁請求系統(tǒng)

旦I請求分段系統(tǒng)

④缺頁（段）中斷機構

虛擬存儲器的定義

請求分頁存儲管理方式是建立

在純分頁基礎上的，是目前常用的

~種實現(xiàn)虛擬存儲器的方式。由于

它換進換出的:本單核是固定長度

的頁面，所以請求分頁管理方式實

現(xiàn)起來相對今易。

頁表機制

在請求分頁系統(tǒng)中需要的主要數(shù)據(jù)結構仍然

是頁表。其基本作用是將用戶地址空間的近斡地

址轉換為內存無間的物理地址。

實現(xiàn)請求分頁［段】的硬件支持

在請求分頁系統(tǒng)中，每當要訪問的

頁面不在內存時，要產生一個缺頁中新。

它是一種特殊的中斷，主要表現(xiàn)在：

在指令執(zhí)行期間產生和處理中斷信號

一條指令在執(zhí)行期間，可產生多次缺頁

中斷

請求分頁余統(tǒng)地址變換機構

A（越界中斷）

頁面分配的三個問題

保證進程正常運行所需的最少物理塊教

的確定

分配的物理塊數(shù)是固定的還是可變的

分配的物理塊數(shù)是象取平均分配算法還

是根據(jù)進程大小按比例予以分配

頁面分配和置換策略

口固定分配局部置換

⑥可變分配全局置換

可變分配局部置換

頁面分配算法

@平均分配算法

@按比例分配算法

&I考慮優(yōu)先權的分配算法

按比例分配算法

若余統(tǒng)中有n個選程，每個選程的頁面數(shù)為Sy則

條統(tǒng)中的頁面數(shù)總和為：

s=￡st

i=l

又設條統(tǒng)中可用的物理塊總數(shù)為m,則每個進程

能分到的物理塊數(shù)為4，則有：

s

bi=—t?m

s

按比例分配算法

在實際應用中，為了照顧重要的、緊迫的作

業(yè)能盡快地完成，應為它分配較多的內存空間。

通常采用的方法就是把內存可供分配的物理塊分

為兩部分：~部分按比例分配給各進程；另一部

分則根據(jù)各進程的優(yōu)先權，分配給各進程。

何時調入頁面

為了確定索統(tǒng)將選程運行時所缺的

頁面調入內存的時機，可及取兩種策略:

■預調頁策略

■請求調頁策略

何處調入頁面

在請求分頁系統(tǒng)中，把外存分為

兩部分：一部分是文件區(qū)，用于存放

文件；另一部分是對換區(qū)，用于常放

對換頁面。

頁面置換算法

通常，把選擇換出的頁面的算法稱為頁面置

換算法(Page-ReplacementAlgorithms)。置換

算法的好壞將直接影響豕統(tǒng)的性能，不適當?shù)乃?/p>

法可能導致進程發(fā)生“”。

一個好的頁面置換算法，應具有較低的頁面

更換頻率。從理論上講，應將那些以后不再會訪

問的頁面換出，或把那些在較長時間內不會再被

訪問的頁面調出。

最佳置換算法

最佳置換算法是由Belady于1966

年提出的一種理論上的算法。其選擇

的頁面，將是永不使用的，或者是在

最長時間內不再被訪問的頁面。

對于固定分配頁面方式，采用最

佳置換算法可保證獲得最低的缺頁率。

最佳頁面置換算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

70120304230321201701

最佳頁面置換算法舉例

假定宗統(tǒng)為某進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

0120304230321201701

最佳頁面置換算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

7120304230321201701

7

0

最佳頁面置換算法舉例

假定宗統(tǒng)為某進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

7020304230321201701

索佳頁面置換算法舉例

假定京統(tǒng)為某選程分配了三個物理塊，并考

慮有以下的頁面號引用串：

7010304230321201701

最佳頁面置換算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

7012304230321201701

2

0

1

最佳頁面置換算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

70120304230321201701

2

0

3

最佳頁面置換算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

7012034230321201701

2

0

3

最佳頁面置換算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

7012030230321201701

2

_0_

3

最佳頁面置換算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

7012030430321201701

最佳頁面置換算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

7012030420321201701

最佳頁面置換算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

7012030423321201701

S

索佳頁面置換算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

最佳頁面置換算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

70120304230321201701

2

0

3

索佳頁面置換算法舉例

假定京統(tǒng)為某選程分配了三個物理塊，并考

慮有以下的頁面號引用串：

7012030423032201701

策佳頁面置換算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

7012030423032101701

索佳頁面置換算法舉例

假定京統(tǒng)為某選程分配了三個物理塊，并考

慮有以下的頁面號引用串：

7012030423032121701

索佳頁面置換算法舉例

假定京統(tǒng)為某選程分配了三個物理塊，并考

慮有以下的頁面號引用串：

7012030423032120701

索佳頁面置換算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

70120304230321201

Z

0

1

策佳頁面置換算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

7012030423032120171

最佳頁面置換算法舉例

假定京統(tǒng)為某選程分配了三個物理塊，并考

慮有以下的頁面號引用串：

7012030423032120170

7

0

1

先進先出頁面置換算法

該算法總是淘次最先進入內存的

頁面，即選擇在內存中駐留時間最久

的頁面予以淘汰。

該算法實現(xiàn)簡單，將選入內存的

進程按照先后次序鏈接成一個隊列，

設置一個替換指針，使它總是指向最

老的頁面。

先進先出頁面置換算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

70120304230321201701

先進先出頁面置換算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

0120304230321201701

7

先進先出頁面置換算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

7120304230321201701

7

0

先進先出頁面置換算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

7020304230321201701

7

0

1

先進先出頁面置換算法舉例

假定京統(tǒng)為某選程分配了三個物理塊，并考

慮有以下的頁面號引用串：

7010304230321201701

先進先出頁面置換算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

7012304230321201701

2

0

1

先進先出頁面置換算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

70120304230321201701

2

0

1

先進先出頁面置換算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

7012034230321201701

2

3

°

先進先出頁面置換算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

7012030230321201701

a

3

0

先進先出頁面置換算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

7012030430321201701

先進先出頁面置換算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

7012030420321201701

先進先出頁面置換算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

7012030423321201701

a

先進先出頁面置換算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

7012030423021201701

S

先進先出頁面置換算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

70120304230321201701

0

2

3

先進先出頁面置換算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

701203042303201701

0

3

先進先出頁面置換算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

先進先出頁面置換算法舉例

假定宗統(tǒng)為某選程分配了三個物理塊，并考

慮有以下的頁面號引用串：

7012030423032121701

S

臼幅

先進先出頁面置換算法舉例

假定京統(tǒng)為某選程分配了三個物理塊，并考

慮有以下的頁面號引用串：

7012030423032120701

S

HH

先進先出頁面置換算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

70120304230321201

0

[

2

先進先出頁面置換算法舉例

假定京統(tǒng)為某選程分配了三個物理塊，并考

慮有以下的頁面號引用串：

701203042303212017

7

0

2

先進先出頁面置換算法舉例

假定京統(tǒng)為某選程分配了三個物理塊，并考

慮有以下的頁面號引用串：

7012030423032120170

7

0

2

最近最久未使用LRU頁面置換算法

LRU算法是選擇最近最久未使用

的頁面予以淘汰。該算法賦j予每個頁

面一個訪問字段，用來記錄頁面上次

被訪問以來所經歷的時間t。當須淘汰

~個頁面時，選擇現(xiàn)有頁面中t值最大

的，即最近最久未使用的頁面予以淘

LRU算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

70120304230321201701

LRU算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

0120304230321201701

7

LRU算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

7120304230321201701

7

0

LRU算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

7020304230321201701

7

0

1

LRU算法舉例

假定京統(tǒng)為某選程分配了三個物理塊，并考

慮有以下的頁面號引用串：

7010304230321201701

LRU算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

7012304230321201701

2

0

1

LRU算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

70120304230321201701

2

0

3

LRU算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

7012034230321201701

2

0

3

LRU算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

7012030230321201701

a

0

3

LRU算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

7012030430321201701

0

3

LRU算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

7012030420321201701

LRU算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

7012030423321201701

S

LRU算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

701203042s3021201701

LRU算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

70120304230321201701

0

3

2

LRU算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

LRU算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

LRU算法舉例

假定京統(tǒng)為某選程分配了三個物理塊，并考

慮有以下的頁面號引用串：

7012030423032121701

LRU算法舉例

假定宗統(tǒng)為禁進程分配了三個物理塊，并考

慮有以下的頁面號引用串：

70120304230321201

1

0

2

LRU算法舉例

假定京統(tǒng)為某選程分配了三個物理塊，并考

慮有以下的頁面號引用串：

70120304230321201