1(一)

主存的共享方式

(二)

主存管理的功能

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

(四)

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

(五)

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

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

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

大小相等的片——頁式存儲(chǔ)管理

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

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

1.物理地址(絕對(duì)地址、實(shí)地址)

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

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

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

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

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

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

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

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

┇

┇6

二.主存管理功能

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

2.主存分配

3.存儲(chǔ)保護(hù)

4.主存擴(kuò)充7

三.主存映射

1.什么是地址映射

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

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

2.地址映射的時(shí)機(jī)與類別

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

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

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

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

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

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

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

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

需花費(fèi)較多CPU時(shí)間地址變換快

不靈活靈活12

四.主存分配

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

2.制定分配策略

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

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

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

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

五.主存擴(kuò)充主存擴(kuò)充也就是提供虛擬存儲(chǔ)器

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

如何使用戶使用計(jì)算機(jī)不受主存容量的限制？

2.解決問題的思路

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

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ǔ)器，這個(gè)存儲(chǔ)器稱為虛擬存儲(chǔ)器。16

4.虛擬存儲(chǔ)器的核心

邏輯地址與物理地址分開

主存空間與地址空間分開

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

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

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

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

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

六.存儲(chǔ)保護(hù)

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

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

界地址保護(hù)存儲(chǔ)鍵保護(hù)18

3.界地址保護(hù)

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

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

如何判斷是否越界

滿足

20KB≤D＜24KB

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

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

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

如何判斷是否越界

滿足邏輯地址＜4KB

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

7.3分區(qū)存儲(chǔ)管理一.動(dòng)態(tài)分區(qū)分配

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

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

21

(1)動(dòng)態(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申請(qǐng)

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

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

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

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

50KB22

(2)動(dòng)態(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ū)分配機(jī)構(gòu)

1.分區(qū)描述器

分配標(biāo)志flag

大小size

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

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

作業(yè)1

作業(yè)3

作業(yè)4

52KB66KB130KB230KB256KB1主存52KBm-rib

014KB230KB

026KB

自由主存隊(duì)列25

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

1.分區(qū)分配

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

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

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

?若找到，以空閑塊與請(qǐng)求的主存塊大小之間的關(guān)系進(jì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合并成為一個(gè)大的空閑區(qū)f1

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

r作業(yè)1f2

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

28

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

f1

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

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

rf1f2

f1

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

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

四.放置策略

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

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

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

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

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

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

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

(2)特點(diǎn)

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

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

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

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

(2)特點(diǎn)自由主存隊(duì)列結(jié)構(gòu)——

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

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

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

(3)特點(diǎn)

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

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

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

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

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

P172圖7.1334

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

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

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

3.頁表

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

(2)頁表的組成

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

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

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

二.頁式地址變換

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

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

3.頁式地址變換

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

(2)頁式地址變換過程

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

(3)

頁式地址變換的步驟

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

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

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

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

(7*1024+452=7620)。41

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

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

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

三.請(qǐng)調(diào)策略

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

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

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

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

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

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

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

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

3.擴(kuò)充頁表功能

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

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

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

4.缺頁處理

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

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

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

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

從外存讀入所需的頁

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

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

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

四.淘汰策略

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

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

2.擴(kuò)充頁表功能

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(3)LRU近似淘汰算法

入口讀出替換指針指向的塊號(hào)移動(dòng)指針指向下一個(gè)存儲(chǔ)塊

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

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

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

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

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

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

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

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

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

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

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

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

段長(zhǎng)是可變的