操作系統(tǒng)原理 第7章 主存管理

1(一)

主存的共享方式

(二)

主存管理的功能

(三)分區(qū)存儲管理技術(shù)

(四)

頁式存儲管理技術(shù)

(五)

段式及段頁式存儲管理技術(shù)第七章主存管理2

(一)主存的共享方式主存共享方式——空間分片

大小不等的區(qū)域——分區(qū)存儲管理分段存儲管理

大小相等的片——頁式存儲管理

兩者結(jié)合——段頁式存儲管理3

(二)主存管理功能一.幾個概念

1.物理地址(絕對地址、實地址)

物理地址是計算機主存單元的真實地址，又稱為絕對地址或?qū)嵉刂贰?/p>

2.主存空間物理地址的集合所對應(yīng)的空間組成了主存空間。

3.區(qū)域物理地址集合的一個遞增整數(shù)序列子集n，n+1，┄，n＋m所對應(yīng)的主存空間。4

4.邏輯地址(相對地址、虛地址)

用戶的程序地址(指令地址或操作數(shù)地址)均為邏輯地址。

5.作業(yè)地址空間

用戶程序所有的邏輯地址集合對應(yīng)的空間。作業(yè)地址空間01n-15

6.作業(yè)地址空間與主存空間主存空間01m-1作業(yè)1地址空間01n-1作業(yè)i地址空間01k-1

┇

┇6

二.主存管理功能

1.實現(xiàn)邏輯地址到物理主存地址的映射

2.主存分配

3.存儲保護

4.主存擴充7

三.主存映射

1.什么是地址映射

(1)為什么要進行地址映射作業(yè)的相應(yīng)進程在處理機上運行時，所要訪問的指令和數(shù)據(jù)的實際地址和作業(yè)地址空間中的地址是不同的。這種情況可用圖7.1來說明。movr1,[500]123movr1,[500]123010050059901000110015001599256k-1作業(yè)地址空間存儲空間8

(2)什么是地址映射將程序地址空間中使用的邏輯地址變換成主存中的物理地址的過程，稱為地址映射。

2.地址映射的時機與類別

(1)編程或編譯時確定地址映射關(guān)系在程序編寫或程序編譯時確定虛、實地址之間的對應(yīng)關(guān)系，結(jié)果是一個不能浮動的程序模塊。9

(2)在作業(yè)裝入時確定地址映射關(guān)系——靜態(tài)地址映射在作業(yè)裝入過程中隨即進行的地址變換方式稱為靜態(tài)重定位或靜態(tài)地址映射。movr1,[500]1230100500599作業(yè)地址空間重定位裝入程序movr1,[500+m]256k-1存儲空間0mm+100m+50012310

(3)在程序運行時確定地址映射關(guān)系——動態(tài)地址映射在程序執(zhí)行期間，隨著每條指令和數(shù)據(jù)的訪問自動地連續(xù)地進行地址映射。movr1,[500]123

movr1,[500]123存儲空間01000256k-1110015001600作業(yè)地址空間0100500599邏輯地址重定位寄存器1000500+11

3.靜態(tài)地址映射與動態(tài)地址映射的區(qū)別

靜態(tài)地址映射動態(tài)地址映射

在作業(yè)裝入過程中在程序執(zhí)行期間進行地址映射進行地址映射

需軟件需硬件地址變換機構(gòu)重定位裝入程序重定位寄存器

需花費較多CPU時間地址變換快

不靈活靈活12

四.主存分配

1.構(gòu)造分配用的數(shù)據(jù)結(jié)構(gòu)主存資源信息塊：等待隊列頭指針自由主存隊列頭指針主存分配程序地址

2.制定分配策略

(1)主存分配策略在眾多個請求者中選擇一個請求者的原則。

(2)放置策略選擇一個空閑區(qū)或若干空閑區(qū)的原則。13

(3)調(diào)入策略決定信息裝入主存的時機預(yù)調(diào)策略：預(yù)先將信息調(diào)入主存請調(diào)策略：當(dāng)需要信息時，將信息調(diào)入主存

(4)淘汰策略在主存中沒有任何可用的空閑區(qū)時，決定哪些信息從主存中移走，即確定淘汰已占用的內(nèi)存區(qū)的原則。3.實施主存分配與回收14

五.主存擴充主存擴充也就是提供虛擬存儲器

1.問題的提出主存容量始終顯得十分緊張

如何使用戶使用計算機不受主存容量的限制？

2.解決問題的思路

裝入部分程序地址空間，它還能正確地執(zhí)行？15

3.實現(xiàn)方法

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

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

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

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

4.虛擬存儲器的核心

邏輯地址與物理地址分開

主存空間與地址空間分開

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

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

有相當(dāng)容量的輔存足以存放多用戶的作業(yè)的地址空間

有一定容量的主存存放運行進程的當(dāng)前信息

地址變換機構(gòu)17

六.存儲保護

1.什么是存儲保護在多用戶環(huán)境中，主存儲器按區(qū)分配給各用戶程序使用。為了互不影響，必須由硬件(軟件配合)保證每道程序只能在給定的存儲區(qū)域內(nèi)活動，這種措施叫做存儲保護。

2.存儲保護方法通常的存儲保護方法——

界地址保護存儲鍵保護18

3.界地址保護

(1)上、下界防護movr1,[500]123020KB256KB1存儲空間24KB下界寄存器20KB上界寄存器24KB

如何設(shè)置上下界寄存器內(nèi)容

如何判斷是否越界

滿足

20KB≤D＜24KB

允許訪問否則發(fā)生越界中斷19

(2)基地址、限長防護movr1,[500]123020KB256KB1存儲空間24KB基址寄存器20KB限長寄存器4KB

如何設(shè)置基址寄存器和限長寄存器內(nèi)容

如何判斷是否越界

滿足邏輯地址＜4KB

允許訪問否則發(fā)生越界中斷20

7.3分區(qū)存儲管理一.動態(tài)分區(qū)分配

1.什么是動態(tài)分區(qū)分配在處理作業(yè)的過程中，建立分區(qū)，依用戶請求的大小分配分區(qū)。

2.動態(tài)分區(qū)的分配、回收過程

21

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

os

作業(yè)1

作業(yè)2

作業(yè)3

作業(yè)4

52KB66KB130KB230KB256KB1主存20KB0

os

作業(yè)1

作業(yè)2

作業(yè)3

52KB66KB130KB256KB1主存20KB0

os

作業(yè)1

52KB256KB1主存0

os

256KB1主存20KB20KB0

os

作業(yè)1

作業(yè)2

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

32KB作業(yè)2申請

14KB作業(yè)3申請

64KB作業(yè)4申請

100KB作業(yè)5申請

50KB22

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

os

作業(yè)1

作業(yè)2

作業(yè)3

作業(yè)4

20KB0

os

作業(yè)1

作業(yè)2

作業(yè)3

作業(yè)4

52KB66KB130KB230KB256KB1主存20KB0

os

作業(yè)1

作業(yè)2

作業(yè)3

作業(yè)4

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

二.分區(qū)分配機構(gòu)

1.分區(qū)描述器

分配標(biāo)志flag

大小size

勾鏈字nextflag：為0——空閑區(qū)為1——已分配區(qū)size：分區(qū)大小next：空閑區(qū)——自由主存隊列中的勾鏈字已分配區(qū)——此項為零24

2.自由主存隊列(或空閑區(qū)隊列)結(jié)構(gòu)20KB0os

作業(yè)1

作業(yè)3

作業(yè)4

52KB66KB130KB230KB256KB1主存52KBm-rib

014KB230KB

026KB

自由主存隊列25

三.分區(qū)的分配與回收

1.分區(qū)分配

(1)分區(qū)分配思路

?用戶請求分配一個主存塊

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

?若找到，以空閑塊與請求的主存塊大小之間的關(guān)系進行相應(yīng)的處理，并返回所分配區(qū)域的首址；

?否則，告之不能滿足要求。算法見P167MODULE7.126

2.分區(qū)回收(算法見P169MODULE7.2)

回收主存塊的四種情況

r上鄰空閑區(qū)rf1作業(yè)2

r上下鄰空閑區(qū)rf1f2

r上下鄰已分配區(qū)r作業(yè)1作業(yè)2

r下鄰空閑區(qū)r作業(yè)1f227

回收分區(qū)r上鄰空閑區(qū)

rf1作業(yè)2

f1作業(yè)2r與f1合并成為一個大的空閑區(qū)f1

回收分區(qū)r下鄰空閑區(qū)

r作業(yè)1f2

作業(yè)1f2r與f2合并成為一個大的空閑區(qū)f2

28

回收分區(qū)r上、下鄰空閑區(qū)r與f1、

f1

合并成為一個大的空閑區(qū)f1

回收分區(qū)r上、下鄰已分配區(qū)r成為一個新的空閑區(qū)f

rf1f2

f1

r作業(yè)1作業(yè)2

f作業(yè)1作業(yè)229

四.放置策略

1.什么是放置策略選擇空閑區(qū)的策略，稱為放置策略。空閑區(qū)隊列建立方法體現(xiàn)了放置策略常用的放置策略——

首次匹配(首次適應(yīng)算法)

最佳匹配(最佳適應(yīng)算法)

最壞匹配(最壞適應(yīng)算法)

三種放置策略見P171圖7.11，P172圖7.1230

2.首次適應(yīng)算法

(1)什么是首次適應(yīng)算法首次適應(yīng)算法是將輸入的作業(yè)放置到主存里第一個足夠裝入它的可利用的空閑區(qū)中。

(2)特點

自由主存隊列結(jié)構(gòu)——

空閑區(qū)地址由低到高排序盡可能地利用存儲器中低地址的空閑區(qū)，而盡量保存高地址的空閑區(qū)。31

3.最佳適應(yīng)算法

(1)什么是最佳適應(yīng)算法最佳適應(yīng)算法是將輸入的作業(yè)放置到主存中與它所需大小最接近的空閑區(qū)中。

(2)特點自由主存隊列結(jié)構(gòu)——

空閑區(qū)大小由小到大排序盡可能地利用存儲器中小的空閑區(qū)，而盡量保存大的空閑區(qū)。32

4.最壞適應(yīng)算法

(1)什么是最壞適應(yīng)算法最壞適應(yīng)算法是將輸入的作業(yè)放置到主存中主存中最不適合它的空閑區(qū)中。

(3)特點

自由主存隊列結(jié)構(gòu)——

空閑區(qū)大小由大到小排序盡可能地利用存儲器中大的空閑區(qū)。33

五.碎片問題及拼接技術(shù)

1.什么是碎片問題在已分配區(qū)之間存在著的一些沒有被充分利用的空閑區(qū)。如何解決碎片問題？

2.拼接技術(shù)所謂拼接技術(shù)是指移動存儲器中某些已分配區(qū)中的信息，使本來分散的空閑區(qū)連成一個大的空閑區(qū)。

P172圖7.1334

(四)頁式存儲管理一.頁式系統(tǒng)的基本概念

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

2.主存塊主存被等分成大小相等的片，稱為主存塊，又稱為實頁。35

3.頁表

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

(2)頁表的組成

高速緩沖存儲器組成地址變換速度快，但成本較高。

主存區(qū)域地址變換速度比硬件慢，成本較低。36

4.分頁映像存儲的例01KB01KB2KB3KB1主存作業(yè)2地址空間2KB3KB4KB5KB6KB7KB8KB9KB10KB101KB2KB1作業(yè)1地址空間01KB1作業(yè)3地址空間0516頁號塊號02140827作業(yè)1頁表作業(yè)2頁表作業(yè)3頁表osos37

二.頁式地址變換

1.頁表記錄頁與塊之間對應(yīng)關(guān)系的地址變換的機構(gòu)

2.虛地址結(jié)構(gòu)當(dāng)CPU給出的虛地址長度為16位，頁面大小為1KB時，在分頁系統(tǒng)中地址結(jié)構(gòu)的格式如下。pw151090頁號P頁內(nèi)位移Wmovr1,[2500]12301KB2KB3KB1作業(yè)2地址空間38

3.頁式地址變換

(1)頁式地址變換的例作業(yè)2地址空間中，設(shè)100號單元處有如下指令：movr1,[2500]。當(dāng)這條指令執(zhí)行時，如何進行正確的地址變換。movr1,[2500]12301KB1KB3KB1作業(yè)2地址空間2500→2*1024+452p=2w=4520000100111000100000010011100010039

(2)頁式地址變換過程

151090塊號b塊內(nèi)位移W頁表始址寄存器movr1,[2500]12301KB2KB3KB1作業(yè)2地址空間+021427頁表00001001110001001090p=2w=452頁號P頁內(nèi)位移W250001KB主存2KB3KB4KB5KB6KB7KB8KB9KB10KB1ososmovr1,[2500]123第1頁7*1024+452=7620000111011100010040

(3)

頁式地址變換的步驟

CPU給出操作數(shù)地址(為2500)；

由分頁機構(gòu)自動地把邏輯地址分為兩部分，得到頁號p和頁內(nèi)相對位移w(p=2，w=452)；

根據(jù)頁表始址寄存器指示的頁表始地址，以頁號為索引，找到第2頁所對應(yīng)的塊號(為7)；

最后，將塊號b和頁內(nèi)位移量w拼接在一起，就形成了訪問主存的物理地址

(7*1024+452=7620)。41

4.采用聯(lián)想存儲器加快查表速度

(1)什么是聯(lián)想存儲器高速、小容量半導(dǎo)體存儲部件，又稱緩沖存儲器。

(2)快表在緩沖存儲器中存放正在運行的進程當(dāng)前用到的頁號和對應(yīng)的塊號，又稱為快表。42

三.請調(diào)策略

1.兩種頁式系統(tǒng)

(1)簡單頁式系統(tǒng)裝入一個作業(yè)的全部頁面才能投入運行。

(2)請求頁式系統(tǒng)只裝入一個作業(yè)的部分頁面即可投入運行。

(1)簡單頁式系統(tǒng)需要解決什么問題？

(2)請求分頁系統(tǒng)需要解決什么問題?43

2.請求頁式系統(tǒng)需解決的問題

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

(2)當(dāng)發(fā)現(xiàn)所需訪問的頁面不在主存時如何處理?

3.擴充頁表功能

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

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

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

4.缺頁處理

啟動要處理的指令給出虛地址

得到頁號該頁在主存?有空閑塊?

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

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

從外存讀入所需的頁

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

重新啟動被中斷的指令

調(diào)整存儲分配表和頁表要重寫入?該頁寫入外存YNNY硬件軟件YN45

四.淘汰策略

1.什么是淘汰策略用來選擇淘汰哪一頁的規(guī)則就叫做置換策略，或稱淘汰算法。

如何決定淘汰哪一頁？根據(jù)頁面在系統(tǒng)中的表現(xiàn)如：使用的頻繁程度進入系統(tǒng)時間的長短46

2.擴充頁表功能

頁號主存塊號中斷位輔存地址引用位改變位

引用位——標(biāo)識某頁最近是否被訪問為“0”——該頁沒有被訪問為“1”——該頁已被訪問

改變位——表示某頁是否被修改為“0”——該頁未被修改為“1”——該頁已被修改47

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

下面討論常用的頁面淘汰算法48

4.先進先出淘汰算法(FIFO算法)

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

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

建立一個頁面進入主存的先后次序表；

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

當(dāng)需要置換一頁時，選擇替換指向的那一頁，然后調(diào)整替換指針的內(nèi)容。49

5.最久未使用淘汰算法(LRU算法)

(1)什么是最久未使用淘汰算法總是選擇最長時間未被使用的那一頁淘汰。

(2)最久未使用淘汰算法的實現(xiàn)方法

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

當(dāng)訪問頁面時，將引用位置1，并記時；

當(dāng)要淘汰一頁時，選擇時間最長的一頁淘汰。要精確實現(xiàn)很困難硬件方法：采用寄存器軟件方法：采用頁號棧50

(3)LRU近似淘汰算法

入口讀出替換指針指向的塊號移動指針指向下一個存儲塊

引用位為0?選擇該頁淘汰，記錄該頁的頁號、塊號將該頁所在的塊號送到替換指針返回置引用位為0YN51

(五)段頁式存儲管理一.段式地址空間

1.什么是段分段是程序中自然劃分的一組邏輯意義完整的信息集合。分段的例：代碼分段、數(shù)據(jù)分段、棧段。

2.作業(yè)地址空間由若干個邏輯分段組成，每個分段有自己的名字，對于一個分段而言，它是一個連續(xù)的地址區(qū)。52

3.段式地址空間code_addr4KB10代碼分段data_addr3KB10數(shù)據(jù)分段stack_addr2KB10棧段

段號s段內(nèi)位移w53

二.頁式系統(tǒng)與段式系統(tǒng)的區(qū)別

1.用戶地址空間的區(qū)別

頁式系統(tǒng)中用戶地址空間——一維地址空間

段式系統(tǒng)中用戶地址空間——二維地址空間

2.分段與頁面的區(qū)別分段頁面

信息的邏輯劃分信息的物理劃分

段長是可變的