os7主存管理課件

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

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

10代碼分段data_addr3KB

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

10棧段11

51.幾個概念物理地址(絕對地址、實地址)

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

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

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

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

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

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

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

movr1,[500]

1000256k-1存儲空間110015001600123movr1,[500]0100500599作業(yè)地址空間12311主存管理——地址映射靜態(tài)地址映射與動態(tài)地址映射的區(qū)別

靜態(tài)地址映射

動態(tài)地址映射

在作業(yè)裝入過程中

在程序執(zhí)行期間

進行地址映射

進行地址映射

需軟件

需硬件地址變換機構(gòu)

重定位裝入程序

重定位寄存器

需花費較多CPU時間

地址變換快

不靈活

靈活

12主存管理——主存管理功能4.主存分配構(gòu)造分配用的數(shù)據(jù)結(jié)構(gòu)

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

——在眾多個請求者中選擇一個請求者的原則放置策略

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

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

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

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

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

1存儲空間24KB下界寄存器

20KB上界寄存器

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

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

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

1存儲空間24KB基址寄存器

20KB限長寄存器

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

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

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

32KB0

256KB1主存20KBos20KB0

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

14KB20KB0

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

64KB20KB0

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

100KB20KB0

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

50KB20主存管理——分區(qū)存儲管理動態(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.動態(tài)分區(qū)分配什么是動態(tài)分區(qū)分配

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

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

分配標志flag

大小size

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

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

空閑區(qū)隊列230KB014KB026KB

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

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

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

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

作業(yè)A

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

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

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

作業(yè)A

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

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

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

作業(yè)A

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

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

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

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

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

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

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

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

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

作業(yè)A要求18KB

作業(yè)B要求25KB

作業(yè)C要求30KB

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

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

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

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

作業(yè)A要求18KB

作業(yè)B要求25KB

作業(yè)C要求30KB

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

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

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

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

作業(yè)A要求18KB

作業(yè)B要求25KB

作業(yè)C要求30KB

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

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

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

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

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

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

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

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

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

15109000011101110001007×1024+452=762041頁式地址變換步驟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)主存管理——頁式存儲管理42采用聯(lián)想存儲器加快查表速度什么是聯(lián)想存儲器高速、小容量半導(dǎo)體存儲部件，又稱緩沖存儲器?？毂碓诰彌_存儲器中存放正在運行的進程當(dāng)前用到的頁號和對應(yīng)的塊號，又稱為快表。主存管理——頁式存儲管理43利用快表進行地址映射

主存管理——頁式存儲管理a

+Pw

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

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

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

擴充頁表功能

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

——

標識該頁是否在主存若i=1，表示此頁不在主存；若i=0，表示該頁在主存輔存地址

——該頁面在輔存的位置45缺頁處理

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

第1頁作業(yè)2

第0頁3頁號輔存地址中斷位塊號

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

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

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

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

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

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

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

從外存讀入所需的頁

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

重新啟動被中斷的指令

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

主存管理——頁式存儲管理如何決定淘汰哪一頁？擴充頁表功能

引用位——標識該頁最近是否被訪問

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

為“0”——該頁未被修改；為“1”——該頁已被修改

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

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

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

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

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

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

2451

替換指針

指向最老的一頁頁號

24516

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

52主存管理——頁式存儲管理在存儲分塊表中建立次序表頁面進入主存的先后次序：

4512

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

742替換指針塊號頁號指針710234566251

2746替換指針

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

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

5

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

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

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

55主存管理——頁式存儲管理LRU近似淘汰算法

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

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

塊號頁號引用位指針600171023456425640727替換指針

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

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

10代碼分段data_addr3KB

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

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

主存管理——段頁式存儲管理

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

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

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

分段頁面

信息的邏輯劃分

信息的物理劃分

段長是可變的

頁的大小是固定的

用戶可見

用戶不可見

w字段的溢出

w字段的溢出自動將產(chǎn)生越界中斷加入到頁號中

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

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

10代碼分段data_addr3KB

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

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

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

232?1的尋址長度。

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

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

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

64主存管理——Linux系統(tǒng)存儲管理三級頁表

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

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

主存管理單元MMU以頁為單位進行分配和處理

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

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

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

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

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

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

896MBZONE_HIGHMEM

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

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

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

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

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

伙伴系統(tǒng)

伙伴系統(tǒng)

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

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

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