os7主存管理課件

主存管理主存管理主存管理概述主存管理的功能分區(qū)存儲(chǔ)管理頁(yè)式存儲(chǔ)管理段式及段頁(yè)式存儲(chǔ)管理Linux系統(tǒng)的存儲(chǔ)管理1主存管理——主要內(nèi)容2主存管理——主存管理概述1.主存共享方式大小不等的區(qū)域分區(qū)存儲(chǔ)管理段式存儲(chǔ)管理大小相等的區(qū)域頁(yè)式存儲(chǔ)管理二者結(jié)合段頁(yè)式存儲(chǔ)管理3主存管理——主存管理概述2.程序的邏輯組織一維地址結(jié)構(gòu)一個(gè)程序是一個(gè)連續(xù)、線性的地址結(jié)構(gòu)；確定線性地址空間中的指令地址或操作數(shù)地址只需要一個(gè)信息。程序地址空間01n-1

4主存管理——主存管理概述二維地址結(jié)構(gòu)一個(gè)程序由若干個(gè)分段組成，每個(gè)分段是一個(gè)連續(xù)的地址區(qū)；確定任一線性地址空間中的指令地址或操作數(shù)地址需要兩個(gè)信息，一是該信息所在的分段，另一個(gè)是該信息在段內(nèi)的偏移量。code_addr4KB

10代碼分段data_addr3KB

10數(shù)據(jù)分段stack_addr2KB

10棧段11

51.幾個(gè)概念物理地址(絕對(duì)地址、實(shí)地址)

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

物理地址的集合所對(duì)應(yīng)的空間組成了主存空間。邏輯地址(相對(duì)地址、虛地址)

用戶的程序地址(指令地址或操作數(shù)地址)均為邏輯地址。作業(yè)地址空間用戶程序所有的邏輯地址集合對(duì)應(yīng)的空間。主存管理——主存管理功能6作業(yè)地址空間與主存空間主存管理——主存管理功能主存空間01m-1作業(yè)1地址空間01n-1作業(yè)i地址空間01k-1

7主存管理——主存管理功能2.主存管理功能實(shí)現(xiàn)邏輯地址到物理主存地址的映射主存分配存儲(chǔ)保護(hù)主存擴(kuò)充8主存管理——地址映射3.地址映射什么是地址映射

將程序地址空間中使用的邏輯地址變換成主存中的物理地址的過程，稱為地址映射。movr1,[500]1230100500599作業(yè)地址空間movr1,[500]12301000110015001599256k-1存儲(chǔ)空間9主存管理——地址映射在作業(yè)裝入時(shí)確定地址映射關(guān)系在作業(yè)裝入過程中隨即進(jìn)行的地址變換方式稱為靜態(tài)地址映射。movr1,[500]movr1,[500+m]01005005990mm+100256k-1作業(yè)地址空間存儲(chǔ)空間m+500重定位裝入程序123123地址映射的時(shí)機(jī)和類別編程或編譯時(shí)確定地址映射關(guān)系

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

在程序執(zhí)行期間，隨著每條指令和數(shù)據(jù)的訪問自動(dòng)地連續(xù)地進(jìn)行地址映射，這種地址變換方式稱為動(dòng)態(tài)地址映射。重定位寄存器1000500邏輯地址+0

movr1,[500]

1000256k-1存儲(chǔ)空間110015001600123movr1,[500]0100500599作業(yè)地址空間12311主存管理——地址映射靜態(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主存管理——主存管理功能4.主存分配構(gòu)造分配用的數(shù)據(jù)結(jié)構(gòu)

主存資源信息塊：等待隊(duì)列；空閑區(qū)隊(duì)列；主存分配程序制定策略主存分配策略

——在眾多個(gè)請(qǐng)求者中選擇一個(gè)請(qǐng)求者的原則放置策略

——在可用資源中，選擇一個(gè)空閑區(qū)的原則調(diào)入策略

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

——在主存中沒有可用的空閑區(qū)(對(duì)某一作業(yè)而言)時(shí)，決定哪些信息從主存中移走，即確定淘汰已占用的內(nèi)存區(qū)的原則。實(shí)施主存分配與回收13主存管理——主存管理功能5.主存擴(kuò)充可行性實(shí)現(xiàn)方法程序的全部代碼和數(shù)據(jù)存放在輔存中；將程序當(dāng)前執(zhí)行所涉及的那部分程序代碼放入主存中；程序執(zhí)行時(shí)，當(dāng)所需信息不在主存，由操作系統(tǒng)和硬件相配合來完成主存從輔存中調(diào)入信息，程序繼續(xù)執(zhí)行。什么是虛擬存儲(chǔ)器

由操作系統(tǒng)和硬件相配合來完成主存和輔存之間的信息的動(dòng)態(tài)調(diào)度。這樣的計(jì)算機(jī)系統(tǒng)好像為用戶提供了一個(gè)其存儲(chǔ)容量比實(shí)際主存大得多的存儲(chǔ)器，這個(gè)存儲(chǔ)器稱為虛擬存儲(chǔ)器。局部性特征14主存管理——主存管理功能虛擬存儲(chǔ)器的核心邏輯地址與物理地址分開存儲(chǔ)空間與虛地址空間分開提供地址變換機(jī)構(gòu)實(shí)現(xiàn)虛擬存儲(chǔ)器的物質(zhì)基礎(chǔ)有相當(dāng)容量的輔存足以存放應(yīng)用程序的虛地址空間有一定容量的主存存放進(jìn)入主存的多進(jìn)程的信息地址變換機(jī)構(gòu)15主存管理——主存管理功能6.存儲(chǔ)保護(hù)什么是存儲(chǔ)保護(hù)

在多用戶環(huán)境中，主存儲(chǔ)器按區(qū)分配給各用戶程序使用。為了互不影響，必須由硬件(軟件配合)保證各用戶程序只能在給定的存儲(chǔ)區(qū)域內(nèi)活動(dòng)，這種措施叫做存儲(chǔ)保護(hù)。實(shí)現(xiàn)方法界地址保護(hù)存儲(chǔ)鍵保護(hù)16主存管理——主存管理功能界地址保護(hù)上下界防護(hù)例：作業(yè)大小為4KB，主存首址為20KB。movr1,[500]123020KB256KB

1存儲(chǔ)空間24KB下界寄存器

20KB上界寄存器

24KB如何設(shè)置上下界寄存器內(nèi)容？如何判斷是否越界？若20KB≤D＜24KB

允許訪問；否則發(fā)生越界中斷17主存管理——主存管理功能界地址保護(hù)基地址、限長(zhǎng)防護(hù)例：作業(yè)大小為4KB，主存首址為20KB。如何設(shè)置基址、限長(zhǎng)寄存器內(nèi)容？如何判斷是否越界？若邏輯地址＜4KB

允許訪問；否則發(fā)生越界中斷movr1,[500]123020KB256KB

1存儲(chǔ)空間24KB基址寄存器

20KB限長(zhǎng)寄存器

4KB181.動(dòng)態(tài)分區(qū)分配什么是動(dòng)態(tài)分區(qū)分配

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

主存管理——分區(qū)存儲(chǔ)管理19主存管理——分區(qū)存儲(chǔ)管理作業(yè)1申請(qǐng)

32KB0

256KB1主存20KBos20KB0

52KB256KB1主存os作業(yè)1作業(yè)2申請(qǐng)

14KB20KB0

52KB66KB256KB1主存os作業(yè)1作業(yè)2作業(yè)3申請(qǐng)

64KB20KB0

52KB66KB130KB256KB1主存os作業(yè)1作業(yè)2作業(yè)3作業(yè)4申請(qǐng)

100KB20KB0

52KB66KB130KB230KB256KB1主存os作業(yè)1作業(yè)2作業(yè)3作業(yè)4作業(yè)5申請(qǐng)

50KB20主存管理——分區(qū)存儲(chǔ)管理動(dòng)態(tài)分區(qū)的回收過程

作業(yè)2

完成作業(yè)4完成20KB0

52KB66KB130KB230KB256KB1主存作業(yè)1作業(yè)2作業(yè)3作業(yè)4os20KB0

52KB66KB130KB230KB256KB1主存作業(yè)1作業(yè)3作業(yè)4os20KB0

52KB66KB130KB230KB256KB1主存os作業(yè)1作業(yè)3211.動(dòng)態(tài)分區(qū)分配什么是動(dòng)態(tài)分區(qū)分配

在處理作業(yè)的過程中，建立分區(qū)，依用戶請(qǐng)求的大小分配分區(qū)。分區(qū)分配結(jié)構(gòu)主存資源信息塊(M_RIB)分區(qū)描述器(PD)主存管理——分區(qū)存儲(chǔ)管理

等待隊(duì)列頭指針空閑區(qū)隊(duì)列頭指針主存分配程序入口地址M_RIBflag：為0——空閑區(qū)為1——已分配區(qū)size：分區(qū)大小next：空閑區(qū)——自由主存隊(duì)列中的勾鏈字已分配區(qū)——此項(xiàng)為零

分配標(biāo)志flag

大小size

勾鏈字nextPD22空閑區(qū)隊(duì)列結(jié)構(gòu)主存管理——分區(qū)存儲(chǔ)管理20KB0

52KB66KB130KB230KB256KB1主存os作業(yè)1作業(yè)3作業(yè)452KBm-rib

空閑區(qū)隊(duì)列230KB014KB026KB

232.分區(qū)的分配與回收分區(qū)分配思路依申請(qǐng)者所要求的主存區(qū)的大小，分區(qū)分配程序在自由主存隊(duì)列中找一個(gè)滿足用戶需要的空閑塊；若找到了所需的空閑區(qū)，有兩種情況空閑區(qū)與要求的大小相等，將該空閑區(qū)分配并從隊(duì)列中摘除；空閑區(qū)大于所要求的的大小，將空閑區(qū)分為兩部分：一部分成為已分配區(qū)，建立已分配區(qū)的描述器；剩下部分仍為空閑區(qū)。返回所分配區(qū)域的首址；否則，告之不能滿足要求。主存管理——分區(qū)存儲(chǔ)管理24分區(qū)回收思路檢查釋放分區(qū)(即為回收分區(qū))在主存中的鄰接情況；若上、下鄰接空閑區(qū)，則合并，成為一個(gè)連續(xù)的空閑區(qū)；若回收分區(qū)不與任何空閑區(qū)相鄰接，建立一個(gè)新的空閑區(qū)，并加入到空閑區(qū)隊(duì)列中。主存管理——分區(qū)存儲(chǔ)管理253.放置策略什么是放置策略選擇空閑區(qū)的策略，稱為放置策略。常用的放置策略——

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

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

最壞匹配(最壞適應(yīng)算法)主存管理——分區(qū)存儲(chǔ)管理26首次適應(yīng)算法首次適應(yīng)算法是將輸入的作業(yè)放置到主存里第一個(gè)足夠裝入它的地址最低的空閑區(qū)中。主存管理——分區(qū)存儲(chǔ)管理

作業(yè)A

18KB首次適應(yīng)算法的例空閑區(qū)隊(duì)列結(jié)構(gòu)

空閑區(qū)地址由低到高排序首次適應(yīng)算法的特點(diǎn)盡可能地利用存儲(chǔ)器中低地址的空閑區(qū)，而盡量保存高地址的空閑區(qū)。

在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB-1主存os27最佳適應(yīng)算法最佳適應(yīng)算法是將輸入的作業(yè)放置到主存中與它所需大小最接近的空閑區(qū)中。主存管理——分區(qū)存儲(chǔ)管理

作業(yè)A

18KB最佳適應(yīng)算法的例空閑區(qū)隊(duì)列結(jié)構(gòu)

空閑區(qū)大小由小到大排序最佳適應(yīng)算法的特點(diǎn)盡可能地利用存儲(chǔ)器中小的空閑區(qū)，而盡量保存大的空閑區(qū)。

在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB-1主存os28最壞適應(yīng)算法最壞適應(yīng)算法是將輸入的作業(yè)放置到主存中與它所需大小差距最大的空閑區(qū)中。主存管理——分區(qū)存儲(chǔ)管理

作業(yè)A

18KB最壞適應(yīng)算法的例空閑區(qū)隊(duì)列結(jié)構(gòu)

空閑區(qū)大小由大到小排序最壞適應(yīng)算法的特點(diǎn)盡可能地利用存儲(chǔ)器中大的空閑區(qū)。

在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB-1主存os29三種放置策略的討論作業(yè)A要求18KB；作業(yè)B要求25KB；作業(yè)C要求30KB。用首次適應(yīng)算法、最佳適應(yīng)算法、最壞適應(yīng)算法來處理該作業(yè)序列，看哪種算法合適。

主存管理——分區(qū)存儲(chǔ)管理30三種放置策略的討論首次適應(yīng)算法、最佳適應(yīng)算法、最壞適應(yīng)算法的隊(duì)列結(jié)構(gòu)。主存管理——分區(qū)存儲(chǔ)管理

在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB-1主存os(a)首次適應(yīng)算法的空閑區(qū)隊(duì)列20KB030KB100KB020KB160KB05KB210KB046KB

(a)最佳適應(yīng)算法的空閑區(qū)隊(duì)列160KB05KB100KB020KB20KB030KB210KB046KB

(a)最壞適應(yīng)算法的空閑區(qū)隊(duì)列210KB046KB20KB030KB100KB020KB160KB05KB

31三種放置策略的討論首次適應(yīng)算法

主存管理——分區(qū)存儲(chǔ)管理

作業(yè)A要求18KB

作業(yè)B要求25KB

作業(yè)C要求30KB

首次適應(yīng)算法對(duì)該作業(yè)序列是不合適的

在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB-1主存os(a)首次適應(yīng)算法的空閑區(qū)隊(duì)列20KB030KB100KB020KB160KB05KB210KB046KB

32最佳適應(yīng)算法

主存管理——分區(qū)存儲(chǔ)管理

作業(yè)A要求18KB

作業(yè)B要求25KB

作業(yè)C要求30KB

最佳適應(yīng)算法對(duì)該作業(yè)序列是合適的

在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB-1主存os(a)最佳適應(yīng)算法的空閑區(qū)隊(duì)列160KB05KB100KB020KB20KB030KB210KB046KB

33最壞適應(yīng)算法

主存管理——分區(qū)存儲(chǔ)管理

作業(yè)A要求18KB

作業(yè)B要求25KB

作業(yè)C要求30KB

最壞適應(yīng)算法對(duì)該作業(yè)序列是不合適的

os在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB-1主存(a)最壞適應(yīng)算法的空閑區(qū)隊(duì)列210KB046KB20KB030KB100KB020KB160KB05KB

344.碎片問題及拼接技術(shù)什么是碎片問題在已分配區(qū)之間存在著的一些沒有被充分利用的空閑區(qū)

主存管理——分區(qū)存儲(chǔ)管理如何解決碎片問題？什么是拼接技術(shù)

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

54KB58KB135KB254KB256KB1主存138KB作業(yè)20os作業(yè)3作業(yè)１拼接前20KB0

54KB131KB247KB256KB1主存os作業(yè)１作業(yè)2作業(yè)3拼接后351.頁(yè)式系統(tǒng)的基本概念頁(yè)面

程序的地址空間被等分成大小相等的片，稱為頁(yè)面，又稱為虛頁(yè)。主存塊主存被等分成大小相等的片，稱為主存塊，又稱為實(shí)頁(yè)。頁(yè)面與主存塊的關(guān)系主存管理——頁(yè)式存儲(chǔ)管理02KB4KB254KB256KB102KB4KB6KB0頁(yè)1頁(yè)2頁(yè)3頁(yè)主存作業(yè)地址空間36頁(yè)表什么是頁(yè)表為了實(shí)現(xiàn)從地址空間到物理主存的映象，系統(tǒng)建立的記錄頁(yè)與內(nèi)存塊之間對(duì)應(yīng)關(guān)系的地址變換的機(jī)構(gòu)稱為頁(yè)面映像表，簡(jiǎn)稱頁(yè)表。頁(yè)表的組成高速緩沖存儲(chǔ)器——地址變換速度快，但成本較高主存區(qū)域——地址變換速度比硬件慢，成本較低主存管理——頁(yè)式存儲(chǔ)管理37分頁(yè)映像存儲(chǔ)的例主存管理——頁(yè)式存儲(chǔ)管理01KB01KB2KB3KB1主存作業(yè)2地址空間2KB3KB4KB5KB6KB7KB8KB9KB10KB101KB2KB1作業(yè)1地址空間01KB1作業(yè)3地址空間0516頁(yè)號(hào)塊號(hào)02140827作業(yè)1頁(yè)表作業(yè)2頁(yè)表作業(yè)3頁(yè)表osos382.頁(yè)式地址變換頁(yè)表記錄頁(yè)與塊之間對(duì)應(yīng)關(guān)系的地址變換的機(jī)構(gòu)。虛地址結(jié)構(gòu)當(dāng)CPU給出的虛地址長(zhǎng)度為16位，頁(yè)面大小為1KB時(shí)，在分頁(yè)系統(tǒng)中地址結(jié)構(gòu)的格式如下：主存管理——頁(yè)式存儲(chǔ)管理pw151090頁(yè)號(hào)P頁(yè)內(nèi)位移Wmovr1,[2500]12301KB2KB3KB1作業(yè)2地址空間391頁(yè)式地址變換頁(yè)式地址變換的例作業(yè)2地址空間中，設(shè)100號(hào)單元處有如下指令：

movr1,[2500]。當(dāng)這條指令執(zhí)行時(shí)，如何進(jìn)行正確的地址變換。主存管理——頁(yè)式存儲(chǔ)管理2500→2×1024+452p=2w=45200001001110001000000100111000100movr1,[2500]12301KB2KB3KB1作業(yè)2地址空間40頁(yè)式地址變換過程主存管理——頁(yè)式存儲(chǔ)管理頁(yè)表始址寄存器movr1,[2500]12301KB2KB3KB1作業(yè)2地址空間+021427頁(yè)表0000100111000100151090頁(yè)號(hào)P頁(yè)內(nèi)位移W250001KB主存2KB3KB4KB5KB6KB7KB8KB9KB10KB1ososmovr1,[2500]123第1頁(yè)頁(yè)號(hào)P頁(yè)內(nèi)位移W

15109000011101110001007×1024+452=762041頁(yè)式地址變換步驟CPU給出操作數(shù)地址(為2500)；由分頁(yè)機(jī)構(gòu)自動(dòng)地把邏輯地址分為兩部分，得到頁(yè)號(hào)p和頁(yè)內(nèi)相對(duì)位移w(p=2，w=452)；根據(jù)頁(yè)表始址寄存器指示的頁(yè)表始地址，以頁(yè)號(hào)為索引，找到第2頁(yè)所對(duì)應(yīng)的塊號(hào)(為7)；將塊號(hào)b和頁(yè)內(nèi)位移量w拼接在一起，就形成了訪問主存的物理地址

(7*1024+452=7620)主存管理——頁(yè)式存儲(chǔ)管理42采用聯(lián)想存儲(chǔ)器加快查表速度什么是聯(lián)想存儲(chǔ)器高速、小容量半導(dǎo)體存儲(chǔ)部件，又稱緩沖存儲(chǔ)器?？毂碓诰彌_存儲(chǔ)器中存放正在運(yùn)行的進(jìn)程當(dāng)前用到的頁(yè)號(hào)和對(duì)應(yīng)的塊號(hào)，又稱為快表。主存管理——頁(yè)式存儲(chǔ)管理43利用快表進(jìn)行地址映射

主存管理——頁(yè)式存儲(chǔ)管理a

+Pw

僅在聯(lián)想映像不匹配時(shí)進(jìn)行頁(yè)號(hào)bw首先選擇聯(lián)想存儲(chǔ)器所有頁(yè)表在主存中物理地址pb┇┇┇┇┇┇ba+pa443.請(qǐng)調(diào)頁(yè)面的機(jī)制兩種頁(yè)式系統(tǒng)簡(jiǎn)單頁(yè)式系統(tǒng)——裝入一個(gè)作業(yè)的全部頁(yè)面才能投入運(yùn)行。請(qǐng)求頁(yè)式系統(tǒng)——裝入一個(gè)作業(yè)的部分頁(yè)面即可投入運(yùn)行。

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

(2)請(qǐng)求分頁(yè)系統(tǒng)需要解決什么問題?主存管理——頁(yè)式存儲(chǔ)管理請(qǐng)求頁(yè)式系統(tǒng)需解決的問題

擴(kuò)充頁(yè)表功能

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

——

標(biāo)識(shí)該頁(yè)是否在主存若i=1，表示此頁(yè)不在主存；若i=0，表示該頁(yè)在主存輔存地址

——該頁(yè)面在輔存的位置45缺頁(yè)處理

主存管理——頁(yè)式存儲(chǔ)管理作業(yè)2在請(qǐng)求分頁(yè)系統(tǒng)中的存儲(chǔ)映像01KB2KB4KB1作業(yè)2地址空間movr1,[2120]addr1,[3410]0062510068023KB01KB主存2KB3KB4KB5KB6KB7KB8KB9KB10KB102142作業(yè)2頁(yè)表osos作業(yè)2

第1頁(yè)作業(yè)2

第0頁(yè)3頁(yè)號(hào)輔存地址中斷位塊號(hào)

0011地址地址地址地址46主存管理——頁(yè)式存儲(chǔ)管理缺頁(yè)處理的例作業(yè)2的主存塊數(shù)為m2=3，討論程序執(zhí)行“movr1，[2120］”指令時(shí)的情況。CPU產(chǎn)生的虛地址為2120分頁(yè)機(jī)構(gòu)得p=2，w=72查頁(yè)表。該頁(yè)中斷位i=1發(fā)生缺頁(yè)中斷！

如主存中有空白塊，且nm則直接調(diào)入如主存中無空白塊，或n

m，則需淘汰該作業(yè)在主存中的一頁(yè)01KB2KB4KB1作業(yè)2地址空間movr1,[2120]addr1,[3410]0062510068023KB47主存管理——頁(yè)式存儲(chǔ)管理缺頁(yè)處理

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

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

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

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

從外存讀入所需的頁(yè)

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

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

調(diào)整存儲(chǔ)分配表和頁(yè)表要重寫入?該頁(yè)寫入外存YNNY硬件軟件YN484.淘汰機(jī)制與策略什么是淘汰策略用來選擇淘汰哪一頁(yè)的規(guī)則叫做置換策略，或稱淘汰算法。

主存管理——頁(yè)式存儲(chǔ)管理如何決定淘汰哪一頁(yè)？擴(kuò)充頁(yè)表功能

引用位——標(biāo)識(shí)該頁(yè)最近是否被訪問

為“0”——該頁(yè)沒有被訪問；為“1”——該頁(yè)已被訪問改變位——表示該頁(yè)是否被修改

為“0”——該頁(yè)未被修改；為“1”——該頁(yè)已被修改

頁(yè)號(hào)主存塊號(hào)中斷位輔存地址引用位改變位49顛簸顛簸(thrashing)，又稱為“抖動(dòng)”。簡(jiǎn)單地說，導(dǎo)致系統(tǒng)效率急劇下降的主存和輔存之間的頻繁頁(yè)面置換現(xiàn)像稱為“抖動(dòng)”。

主存管理——頁(yè)式存儲(chǔ)管理缺頁(yè)中斷率假定程序p共有n頁(yè)，系統(tǒng)分配m塊，有1≤m≤n；

若程序p在運(yùn)行中：成功的訪問次數(shù)為s，不成功的訪問次數(shù)為f；缺頁(yè)中斷率：f′=f/(s+f)f′=f(r，m，p)；r：置換算法；

p：程序特征；m：系統(tǒng)分配的塊數(shù)50主存管理——頁(yè)式存儲(chǔ)管理最佳算法(OPT算法)當(dāng)要調(diào)入一新頁(yè)而必須先淘汰一舊頁(yè)時(shí)，所淘汰的那一頁(yè)應(yīng)是以后不再要用的，或者是在最長(zhǎng)的時(shí)間以后才會(huì)用到的那頁(yè)。

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

什么是先進(jìn)先出淘汰算法總是選擇在主存中居留時(shí)間最長(zhǎng)(即最早進(jìn)入主存)的一頁(yè)淘汰。先進(jìn)先出淘汰算法的實(shí)現(xiàn)建立一個(gè)頁(yè)面進(jìn)入主存的先后次序表；建立一個(gè)替換指針，指向最早進(jìn)入主存的頁(yè)面；當(dāng)需要置換一頁(yè)時(shí)，選擇替換指向的那一頁(yè)，然后調(diào)整替換指針的內(nèi)容。51主存管理——頁(yè)式存儲(chǔ)管理頁(yè)號(hào)表頁(yè)面進(jìn)入主存的先后次序：

2451

替換指針

指向最老的一頁(yè)頁(yè)號(hào)

24516

當(dāng)要調(diào)入第6頁(yè)時(shí)：置換第2頁(yè)將第2頁(yè)改為6替換指針指向第4頁(yè)

52主存管理——頁(yè)式存儲(chǔ)管理在存儲(chǔ)分塊表中建立次序表頁(yè)面進(jìn)入主存的先后次序：

4512

當(dāng)要調(diào)入第6頁(yè)時(shí)：如何處理?51267102345642516

742替換指針塊號(hào)頁(yè)號(hào)指針710234566251

2746替換指針

塊號(hào)頁(yè)號(hào)指針53主存管理——頁(yè)式存儲(chǔ)管理最久未使用淘汰算法(LRU算法)什么是最久未使用淘汰算法總是選擇最長(zhǎng)時(shí)間未被使用的那一頁(yè)淘汰。最久未使用淘汰算法的實(shí)現(xiàn)用引用位考察頁(yè)面的使用情況；當(dāng)訪問頁(yè)面時(shí)，將引用位置1，并記時(shí)；當(dāng)要淘汰一頁(yè)時(shí)，選擇時(shí)間最長(zhǎng)的一頁(yè)淘汰。

要精確實(shí)現(xiàn)很困難硬件方法：采用計(jì)數(shù)器軟件方法：采用頁(yè)號(hào)棧54主存管理——頁(yè)式存儲(chǔ)管理軟件方法：采用頁(yè)號(hào)棧頁(yè)面訪問軌跡：4512

5

64512訪問第5頁(yè)訪問第6頁(yè)淘汰第4頁(yè)41251256訪問4、5、1、2頁(yè)后棧的內(nèi)容

訪問第5頁(yè)后，調(diào)整棧的內(nèi)容

訪問第6頁(yè)后，棧的內(nèi)容

55主存管理——頁(yè)式存儲(chǔ)管理LRU近似淘汰算法

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

引用位為0?選擇該頁(yè)淘汰，記錄該頁(yè)的頁(yè)號(hào)、塊號(hào)將該頁(yè)所在的塊號(hào)送到替換指針返回置引用位為0YN56主存管理——頁(yè)式存儲(chǔ)管理LRU近似淘汰算法舉例71023456425141724替換指針

塊號(hào)頁(yè)號(hào)引用位指針600171023456425640727替換指針

塊號(hào)頁(yè)號(hào)引用位指針6011當(dāng)要調(diào)入第6頁(yè)時(shí)，如何處理?571.段式地址空間什么是段分段是程序中自然劃分的一組邏輯意義完整的信息集合。分段的例：代碼分段、數(shù)據(jù)分段、棧段頁(yè)。作業(yè)地址空間

由若干個(gè)邏輯分段組成，每個(gè)分段有自己的名字，對(duì)于一個(gè)分段而言，它是一個(gè)連續(xù)的地址區(qū)。主存管理——段頁(yè)式存儲(chǔ)管理code_addr4KB

10代碼分段data_addr3KB

10數(shù)據(jù)分段stack_addr2KB

10棧段58段式地址結(jié)構(gòu)

主存管理——段頁(yè)式存儲(chǔ)管理

段號(hào)s段內(nèi)位移w2.段式地址變換

LBswB+w第S段段號(hào)段內(nèi)位移段號(hào)長(zhǎng)度基址段式地址步驟取出程序地址(s，w)；用s檢索段表；如w＜0或w≥L則主存越界；(B＋w)即為所需主存地址593.頁(yè)式系統(tǒng)與段式系統(tǒng)的區(qū)別用戶地址空間的區(qū)別頁(yè)式系統(tǒng)中用戶地址空間——一維地址空間段式系統(tǒng)中用戶地址空間——二維地址空間

分段和頁(yè)面的區(qū)別

分段頁(yè)面

信息的邏輯劃分

信息的物理劃分

段長(zhǎng)是可變的

頁(yè)的大小是固定的

用戶可見

用戶不可見

w字段的溢出

w字段的溢出自動(dòng)將產(chǎn)生越界中斷加入到頁(yè)號(hào)中

主存管理——段頁(yè)式存儲(chǔ)管理604.段頁(yè)式系統(tǒng)

在段式存儲(chǔ)管理中結(jié)合分頁(yè)存儲(chǔ)管理技術(shù)，在一個(gè)分段內(nèi)劃分頁(yè)面，就形成了段頁(yè)式存儲(chǔ)管理。段頁(yè)式地址結(jié)構(gòu)的用戶地址空間主存管理——段頁(yè)式存儲(chǔ)管理code_addr4KB

10代碼分段data_addr3KB

10數(shù)據(jù)分段stack_addr2KB

10棧段61主存管理——段頁(yè)式存儲(chǔ)管理段頁(yè)式系統(tǒng)中段表、頁(yè)表與主存的關(guān)系01n段號(hào)頁(yè)表長(zhǎng)度頁(yè)表始址23┆頁(yè)號(hào)1塊號(hào)其他0段頁(yè)表主存段表┆

01塊號(hào)其他1段頁(yè)表2頁(yè)號(hào)0621.Linux系統(tǒng)段頁(yè)式地址變換Linux系統(tǒng)的分段Linux系統(tǒng)處在用戶態(tài)時(shí)，使用用戶代碼段和用戶數(shù)據(jù)段來對(duì)指令和數(shù)據(jù)尋址在核態(tài)時(shí)，使用內(nèi)核代碼段和內(nèi)核數(shù)據(jù)段來對(duì)指令和數(shù)據(jù)尋址每個(gè)分段是一個(gè)連續(xù)的線性地址空間，從0開始直到

232?1的尋址長(zhǎng)度。

主存管理——Linux系統(tǒng)存儲(chǔ)管理6380x86分頁(yè)結(jié)構(gòu)

80x86微處理器的分頁(yè)單元處理4KB的頁(yè)。一個(gè)32位的線性地址分為3個(gè)域。主存管理——Linux系統(tǒng)存儲(chǔ)管理

頁(yè)目錄頁(yè)表頁(yè)內(nèi)位移31222112110頁(yè)目錄字段指向頁(yè)目錄項(xiàng)；頁(yè)表字段指向進(jìn)程的一個(gè)頁(yè)表項(xiàng)；頁(yè)內(nèi)位移則是頁(yè)內(nèi)偏移量

64主存管理——Linux系統(tǒng)存儲(chǔ)管理三級(jí)頁(yè)表

第一級(jí)：全局目錄(PGD)PGD中的表項(xiàng)指向頁(yè)目錄中的一個(gè)表項(xiàng)二級(jí)頁(yè)表：頁(yè)目錄(PMD)PMD中的表項(xiàng)指向頁(yè)表PTE中的一個(gè)表項(xiàng)三級(jí)：頁(yè)表該表項(xiàng)指向物理頁(yè)(頁(yè)框)的主存地址65主存管理——Linux系統(tǒng)存儲(chǔ)管理線性地址轉(zhuǎn)換為物理地址地址轉(zhuǎn)換過程

Linux系統(tǒng)通過三級(jí)頁(yè)表完成線性地址到物理地址的轉(zhuǎn)換頁(yè)目錄頁(yè)表頁(yè)內(nèi)位移31222112110cr3+：+：頁(yè)目錄表頁(yè)表物理頁(yè)+++66主存管理——Linux系統(tǒng)存儲(chǔ)管理地址變換步驟由cr3指示的當(dāng)前頁(yè)目錄的物理地址與分頁(yè)結(jié)構(gòu)中的頁(yè)目錄字段的內(nèi)容相加指向頁(yè)目錄表項(xiàng)；由頁(yè)目錄表項(xiàng)內(nèi)容得到當(dāng)前使用的頁(yè)表的始地址，通過分頁(yè)結(jié)構(gòu)中的頁(yè)表字段的內(nèi)容找到該頁(yè)表項(xiàng)；由頁(yè)表項(xiàng)指示的該頁(yè)的物理頁(yè)(頁(yè)框)的主存地址與分頁(yè)結(jié)構(gòu)中的頁(yè)內(nèi)位移相加，得到最終的物理地址。672.Linux系統(tǒng)動(dòng)態(tài)內(nèi)核管理物理頁(yè)的描述Linux系統(tǒng)主存分配的基本單位是物理頁(yè)(又稱為頁(yè)框)

主存管理單元MMU以頁(yè)為單位進(jìn)行分配和處理

32位體系結(jié)構(gòu)支持4KB的頁(yè)，64位體系結(jié)構(gòu)支持8KB的頁(yè)內(nèi)核用structpage結(jié)構(gòu)描述頁(yè)框

structpage{flags;/*頁(yè)的狀態(tài)*/_count;/*該頁(yè)被引用的次數(shù)*/

*virtual;/*頁(yè)的虛擬地址，通常情況下記錄頁(yè)在虛擬主存中的地址*/};

主存管理——Linux系統(tǒng)存儲(chǔ)管理68物理主存分區(qū)內(nèi)核將系統(tǒng)中的所有頁(yè)框劃分為不同的區(qū)，具有相似特征的頁(yè)框歸為同一個(gè)分區(qū)。Linux系統(tǒng)共分為三種分區(qū)ZONE_DMA

這個(gè)分區(qū)包含的頁(yè)只能用來執(zhí)行DMA操作，大小為16MB；ZONE_NORMAL

這個(gè)分區(qū)包含的頁(yè)都是能正常映射的頁(yè)，大小為16MB

896MBZONE_HIGHMEM

這個(gè)分區(qū)包含的是“高端主存”，其中的物理頁(yè)并不能永久地映射到內(nèi)核地址空間，大小為896MB。主存管理——Linux系統(tǒng)存儲(chǔ)管理69分區(qū)頁(yè)框的分配

Linux內(nèi)核通過頁(yè)框和區(qū)對(duì)主存進(jìn)行管理，實(shí)現(xiàn)了請(qǐng)求主存的底層機(jī)制；內(nèi)核提供提供一組訪問接口(函數(shù)或宏)可以直接的方式獲得動(dòng)態(tài)主存，注意這種方式只能由內(nèi)核使用。

主存管理——Linux系統(tǒng)存儲(chǔ)管理70主存管理——Linux系統(tǒng)存儲(chǔ)管理分區(qū)頁(yè)框分配器

分區(qū)頁(yè)框分配器(Zonedpageframeallocator)是一個(gè)內(nèi)核子系統(tǒng)，它負(fù)責(zé)對(duì)連續(xù)頁(yè)框的主存分配。分區(qū)頁(yè)框分配器的組成如下圖

管理區(qū)分配器每CPU頁(yè)框高速緩存每CPU頁(yè)框高速緩存每CPU頁(yè)框高速緩存

伙伴系統(tǒng)

伙伴系統(tǒng)

伙伴系統(tǒng)71主存管理——Linux系統(tǒng)存儲(chǔ)管理伙伴系統(tǒng)算法

主存管理中的外碎片問題當(dāng)頻繁地請(qǐng)求和釋放不同大小的連續(xù)頁(yè)框，就會(huì)導(dǎo)致在已分配頁(yè)框內(nèi)產(chǎn)生許多小的、分散的空閑頁(yè)框；

Linux系統(tǒng)采用伙伴系統(tǒng)算法記錄當(dāng)前空閑的連續(xù)頁(yè)框塊的情況，以盡量避免為滿足小塊的請(qǐng)求而分割大的空閑塊?；锇橄到y(tǒng)算法中頁(yè)框的組織將所有的空閑頁(yè)框分組為11個(gè)塊鏈表；每個(gè)塊鏈表分別包含大小為1、2、4、8、16、32