1(一)

主存的共享方式

(二)

主存管理的功能

(三)分區存儲管理技術

(四)

頁式存儲管理技術

(五)

段式及段頁式存儲管理技術第七章主存管理2

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

大小不等的區域——分區存儲管理分段存儲管理

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

兩者結合——段頁式存儲管理3

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

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

物理地址是計算機主存單元的真實地址，又稱為絕對地址或實地址。

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

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

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

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

5.作業地址空間

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

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

┇

┇6

二.主存管理功能

1.實現邏輯地址到物理主存地址的映射

2.主存分配

3.存儲保護

4.主存擴充7

三.主存映射

1.什么是地址映射

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

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

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

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

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

(3)在程序運行時確定地址映射關系——動態地址映射在程序執行期間，隨著每條指令和數據的訪問自動地連續地進行地址映射。movr1,[500]123

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

3.靜態地址映射與動態地址映射的區別

靜態地址映射動態地址映射

在作業裝入過程中在程序執行期間進行地址映射進行地址映射

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

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

不靈活靈活12

四.主存分配

1.構造分配用的數據結構主存資源信息塊：等待隊列頭指針自由主存隊列頭指針主存分配程序地址

2.制定分配策略

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

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

(3)調入策略決定信息裝入主存的時機預調策略：預先將信息調入主存請調策略：當需要信息時，將信息調入主存

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

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

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

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

2.解決問題的思路

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

3.實現方法

程序的全部代碼和數據存放在輔存中；

將程序當前執行所涉及的那部分程序代碼放入主存中；

程序執行時，當所需信息不在主存，由操作系統和硬件相配合來完成主存從輔存中調入信息，程序繼續執行。

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

4.虛擬存儲器的核心

邏輯地址與物理地址分開

主存空間與地址空間分開

提供地址變換機構

5.實現虛擬存儲器的物質基礎

有相當容量的輔存足以存放多用戶的作業的地址空間

有一定容量的主存存放運行進程的當前信息

地址變換機構17

六.存儲保護

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

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

界地址保護存儲鍵保護18

3.界地址保護

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

如何設置上下界寄存器內容

如何判斷是否越界

滿足

20KB≤D＜24KB

允許訪問否則發生越界中斷19

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

如何設置基址寄存器和限長寄存器內容

如何判斷是否越界

滿足邏輯地址＜4KB

允許訪問否則發生越界中斷20

7.3分區存儲管理一.動態分區分配

1.什么是動態分區分配在處理作業的過程中，建立分區，依用戶請求的大小分配分區。

2.動態分區的分配、回收過程

21

(1)動態分區的分配過程20KB0

os

作業1

作業2

作業3

作業4

52KB66KB130KB230KB256KB1主存20KB0

os

作業1

作業2

作業3

52KB66KB130KB256KB1主存20KB0

os

作業1

52KB256KB1主存0

os

256KB1主存20KB20KB0

os

作業1

作業2

52KB66KB256KB1主存作業1申請

32KB作業2申請

14KB作業3申請

64KB作業4申請

100KB作業5申請

50KB22

(2)動態分區的回收過程20KB052KB66KB130KB230KB256KB1主存

os

作業1

作業2

作業3

作業4

20KB0

os

作業1

作業2

作業3

作業4

52KB66KB130KB230KB256KB1主存20KB0

os

作業1

作業2

作業3

作業4

52KB66KB130KB230KB256KB1主存作業2完成作業4完成23

二.分區分配機構

1.分區描述器

分配標志flag

大小size

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

2.自由主存隊列(或空閑區隊列)結構20KB0os

作業1

作業3

作業4

52KB66KB130KB230KB256KB1主存52KBm-rib

014KB230KB

026KB

自由主存隊列25

三.分區的分配與回收

1.分區分配

(1)分區分配思路

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

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

?若找到，以空閑塊與請求的主存塊大小之間的關系進行相應的處理，并返回所分配區域的首址；

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

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

回收主存塊的四種情況

r上鄰空閑區rf1作業2

r上下鄰空閑區rf1f2

r上下鄰已分配區r作業1作業2

r下鄰空閑區r作業1f227

回收分區r上鄰空閑區

rf1作業2

f1作業2r與f1合并成為一個大的空閑區f1

回收分區r下鄰空閑區

r作業1f2

作業1f2r與f2合并成為一個大的空閑區f2

28

回收分區r上、下鄰空閑區r與f1、

f1

合并成為一個大的空閑區f1

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

rf1f2

f1

r作業1作業2

f作業1作業229

四.放置策略

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

首次匹配(首次適應算法)

最佳匹配(最佳適應算法)

最壞匹配(最壞適應算法)

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

2.首次適應算法

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

(2)特點

自由主存隊列結構——

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

3.最佳適應算法

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

(2)特點自由主存隊列結構——

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

4.最壞適應算法

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

(3)特點

自由主存隊列結構——

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

五.碎片問題及拼接技術

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

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

P172圖7.1334

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

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

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

3.頁表

(1)什么是頁表為了實現從地址空間到物理主存的映象，系統建立的記錄頁與內存塊之間對應關系的地址變換的機構稱為頁面映像表，簡稱頁表。

(2)頁表的組成

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

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

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

二.頁式地址變換

1.頁表記錄頁與塊之間對應關系的地址變換的機構

2.虛地址結構當CPU給出的虛地址長度為16位，頁面大小為1KB時，在分頁系統中地址結構的格式如下。pw151090頁號P頁內位移Wmovr1,[2500]12301KB2KB3KB1作業2地址空間38

3.頁式地址變換

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

(2)頁式地址變換過程

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

(3)

頁式地址變換的步驟

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

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

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

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

(7*1024+452=7620)。41

4.采用聯想存儲器加快查表速度

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

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

三.請調策略

1.兩種頁式系統

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

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

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

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

2.請求頁式系統需解決的問題

(1)怎樣發現所訪問的頁面在不在主存？

(2)當發現所需訪問的頁面不在主存時如何處理?

3.擴充頁表功能

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

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

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

4.缺頁處理

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

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

缺頁中斷執行完該指令

準備執行下條指令選一頁淘汰

從外存讀入所需的頁

調整存儲分配表和頁表

重新啟動被中斷的指令

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

四.淘汰策略

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

如何決定淘汰哪一頁？根據頁面在系統中的表現如：使用的頻繁程度進入系統時間的長短46

2.擴充頁表功能

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

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

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

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

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

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

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

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

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

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

當需要置換一頁時，選擇替換指向的那一頁，然后調整替換指針的內容。49

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

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

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

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

當訪問頁面時，將引用位置1，并記時；

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

(3)LRU近似淘汰算法

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

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

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

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

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

3.段式地址空間code_addr4KB10代碼分段data_addr3KB10數據分段stack_addr2KB10棧段

段號s段內位移w53

二.頁式系統與段式系統的區別

1.用戶地址空間的區別

頁式系統中用戶地址空間——一維地址空間

段式系統中用戶地址空間——二維地址空間

2.分段與頁面的區別分段頁面

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

段長是可變的