計(jì)算機(jī)操作系統(tǒng)第7章

1、主存管理,主存管理,主存管理概述 主存管理的功能 分區(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ù)、線(xiàn)性的 地址結(jié)構(gòu)； 確定線(xiàn)性地址空間中的指令地 址或操作數(shù)地址只需要一個(gè)信息。,4,主存管理主存管理概述,二維地址結(jié)構(gòu) 一個(gè)程序由若干個(gè)分段組成，每個(gè)分段是一個(gè)連續(xù)的地址區(qū)； 確定任一線(xiàn)性地址空間中的指令地址或操作數(shù)地址需要

2、兩個(gè)信息，一是該信息所在的分段，另一個(gè)是該信息在段內(nèi)的偏移量。,5,1. 幾個(gè)概念 物理地址 (絕對(duì)地址、實(shí)地址) 物理地址是計(jì)算機(jī)主存單元的真實(shí)地址，又稱(chēng)為絕對(duì)地址或?qū)嵉刂贰?主存空間 物理地址的集合所對(duì)應(yīng)的空間組成了主存空間。 邏輯地址 (相對(duì)地址、虛地址) 用戶(hù)的程序地址(指令地址或操作數(shù)地址)均為邏輯地址。 作業(yè)地址空間 用戶(hù)程序所有的邏輯地址集合對(duì)應(yīng)的空間。,主存管理主存管理功能,6,作業(yè)地址空間與主存空間,主存管理主存管理功能,7,主存管理主存管理功能,2. 主存管理功能 實(shí)現(xiàn)邏輯地址到物理主存地址的映射 主存分配 存儲(chǔ)保護(hù) 主存擴(kuò)充,8,主存管理地址映射,3. 地址映射 什么是地

3、址映射 將程序地址空間中使用的邏輯地址變換成主存中的物理地址的過(guò)程，稱(chēng)為地址映射。,9,主存管理地址映射,在作業(yè)裝入時(shí)確定地址映射關(guān)系 在作業(yè)裝入過(guò)程中隨即進(jìn)行的地址變換方式稱(chēng)為靜態(tài)地址映射。,地址映射的時(shí)機(jī)和類(lèi)別 編程或編譯時(shí)確定地址映射關(guān)系 在程序編寫(xiě)或程序編譯時(shí)確定虛、實(shí)地址之間的對(duì)應(yīng)關(guān)系，結(jié)果 是一個(gè)不能浮動(dòng)的程序模塊。,10,主存管理地址映射,在程序運(yùn)行時(shí)確定地址映射關(guān)系 在程序執(zhí)行期間，隨著每條指令和數(shù)據(jù)的訪(fǎng)問(wèn)自動(dòng)地 連續(xù)地進(jìn)行地址映射，這種地址變換方式稱(chēng)為動(dòng)態(tài)地 址映射。,11,主存管理地址映射,靜態(tài)地址映射與動(dòng)態(tài)地址映射的區(qū)別 靜態(tài)地址映射 動(dòng)態(tài)地址映射 在作業(yè)裝入過(guò)程中 在程

4、序執(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)入主存 淘汰策略 在主存中沒(méi)有可用的空閑區(qū)(對(duì)某一作業(yè)而言)時(shí)，決定哪些信息從主存中移走，即確定淘汰已占用的內(nèi)存區(qū)的原則。 實(shí)施主存

5、分配與回收,13,主存管理主存管理功能,5. 主存擴(kuò)充 可行性 實(shí)現(xiàn)方法 程序的全部代碼和數(shù)據(jù)存放在輔存中； 將程序當(dāng)前執(zhí)行所涉及的那部分程序代碼放入主存中； 程序執(zhí)行時(shí)，當(dāng)所需信息不在主存，由操作系統(tǒng)和硬件相配合來(lái)完成主存從輔存中調(diào)入信息，程序繼續(xù)執(zhí)行。 什么是虛擬存儲(chǔ)器 由操作系統(tǒng)和硬件相配合來(lái)完成主存和輔存之間的信息的動(dòng)態(tài)調(diào)度。這樣的計(jì)算機(jī)系統(tǒng)好像為用戶(hù)提供了一個(gè)其存儲(chǔ)容量比實(shí)際主存大得多的存儲(chǔ)器，這個(gè)存儲(chǔ)器稱(chēng)為虛擬存儲(chǔ)器。,局部性特征,14,主存管理主存管理功能,虛擬存儲(chǔ)器的核心 邏輯地址與物理地址分開(kāi) 存儲(chǔ)空間與虛地址空間分開(kāi) 提供地址變換機(jī)構(gòu) 實(shí)現(xiàn)虛擬存儲(chǔ)器的物質(zhì)基礎(chǔ) 有相當(dāng)容量的

6、輔存 足以存放應(yīng)用程序的虛地址空間 有一定容量的主存 存放進(jìn)入主存的多進(jìn)程的信息 地址變換機(jī)構(gòu),15,主存管理主存管理功能,6. 存儲(chǔ)保護(hù) 什么是存儲(chǔ)保護(hù) 在多用戶(hù)環(huán)境中，主存儲(chǔ)器按區(qū)分配給各用戶(hù)程序使用。 為了互不影響，必須由硬件(軟件配合)保證各用戶(hù)程序只 能在給定的存儲(chǔ)區(qū)域內(nèi)活動(dòng)，這種措施叫做存儲(chǔ)保護(hù)。 實(shí)現(xiàn)方法 界地址保護(hù) 存儲(chǔ)鍵保護(hù),16,主存管理主存管理功能,界地址保護(hù) 上下界防護(hù) 例：作業(yè)大小為4KB，主存首址為20KB。,20KB,24KB,如何設(shè)置上下界寄存器內(nèi)容 ？ 如何判斷是否越界 ？ 若 20KBD24KB 允許訪(fǎng)問(wèn)； 否則發(fā)生越界中斷,17,主存管理主存管理功能,界地

7、址保護(hù) 基地址、限長(zhǎng)防護(hù) 例：作業(yè)大小為4KB，主存首址為20KB。,如何設(shè)置基址、限長(zhǎng)寄存器內(nèi)容 ？ 如何判斷是否越界 ？ 若 邏輯地址 4KB 允許訪(fǎng)問(wèn)； 否則發(fā)生越界中斷,20KB,4KB,18,1. 動(dòng)態(tài)分區(qū)分配 什么是動(dòng)態(tài)分區(qū)分配 在處理作業(yè)的過(guò)程中，建立分區(qū)，依用戶(hù)請(qǐng)求的大小分配分區(qū)。 動(dòng)態(tài)分區(qū)的分配、回收過(guò)程 動(dòng)態(tài)分區(qū)的分配過(guò)程,主存管理分區(qū)存儲(chǔ)管理,19,主存管理分區(qū)存儲(chǔ)管理,作業(yè)1申請(qǐng) 32KB,作業(yè)2申請(qǐng) 14KB,作業(yè)3申請(qǐng) 64KB,作業(yè)4申請(qǐng) 100KB,作業(yè)5申請(qǐng) 50KB,20,主存管理分區(qū)存儲(chǔ)管理,動(dòng)態(tài)分區(qū)的回收過(guò)程,21,1. 動(dòng)態(tài)分區(qū)分配 什么是動(dòng)態(tài)分區(qū)分配

8、 在處理作業(yè)的過(guò)程中，建立分區(qū)，依用戶(hù)請(qǐng)求的大小分配分區(qū)。 分區(qū)分配結(jié)構(gòu) 主存資源信息塊 (M_RIB) 分區(qū)描述器 (PD),主存管理分區(qū)存儲(chǔ)管理,flag： 為 0 空閑區(qū) 為 1 已分配區(qū) size： 分區(qū)大小 next：空閑區(qū)自由主存隊(duì)列中的勾鏈字 已分配區(qū)此項(xiàng)為零,22,空閑區(qū)隊(duì)列結(jié)構(gòu),主存管理分區(qū)存儲(chǔ)管理,23,2. 分區(qū)的分配與回收 分區(qū)分配思路 依申請(qǐng)者所要求的主存區(qū)的大小，分區(qū)分配程序在自 由主存隊(duì)列中找一個(gè)滿(mǎn)足用戶(hù)需要的空閑塊； 若找到了所需的空閑區(qū)，有兩種情況 空閑區(qū)與要求的大小相等，將該空閑區(qū)分配并從隊(duì)列中摘除； 空閑區(qū)大于所要求的的大小，將空閑區(qū)分為兩部分：一部分成

9、為已分配區(qū)，建立已分配區(qū)的描述器；剩下部分仍為空閑區(qū)。 返回所分配區(qū)域的首址； 否則，告之不能滿(mǎn)足要求。,主存管理分區(qū)存儲(chǔ)管理,24,分區(qū)回收思路 檢查釋放分區(qū)(即為回收分區(qū))在主存中的鄰接情況 ； 若上、下鄰接空閑區(qū)，則合并，成為一個(gè)連續(xù)的空 閑區(qū)； 若回收分區(qū)不與任何空閑區(qū)相鄰接，建立一個(gè)新的空 閑區(qū)，并加入到空閑區(qū)隊(duì)列中。,主存管理分區(qū)存儲(chǔ)管理,25,3. 放置策略 什么是放置策略 選擇空閑區(qū)的策略，稱(chēng)為放置策略。 常用的放置策略 首次匹配(首次適應(yīng)算法) 最佳匹配(最佳適應(yīng)算法) 最壞匹配(最壞適應(yīng)算法),主存管理分區(qū)存儲(chǔ)管理,26,首次適應(yīng)算法 首次適應(yīng)算法是將輸入的作業(yè)放置到主存里

10、第一個(gè)足 夠裝入它的地址最低的空閑區(qū)中。,主存管理分區(qū)存儲(chǔ)管理,作業(yè)A 18KB,首次適應(yīng)算法的例 空閑區(qū)隊(duì)列結(jié)構(gòu) 空閑區(qū)地址由低到高排序 首次適應(yīng)算法的特點(diǎn) 盡可能地利用存儲(chǔ)器中低 地址的空閑區(qū)，而盡量保 存高地址的空閑區(qū)。,27,最佳適應(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ū)。,28,最壞適應(yīng)算法 最壞適應(yīng)算法是將輸入的作業(yè)放置到主存中與它所需 大小差距最大的空閑區(qū)中。,主存管理

11、分區(qū)存儲(chǔ)管理,作業(yè)A 18KB,最壞適應(yīng)算法的例 空閑區(qū)隊(duì)列結(jié)構(gòu) 空閑區(qū)大小由大到小排序 最壞適應(yīng)算法的特點(diǎn) 盡可能地利用存儲(chǔ)器中大的 空閑區(qū)。,29,三種放置策略的討論 作業(yè)A要求18KB；作業(yè)B要求25KB；作業(yè)C要求30KB。 用首次適應(yīng)算法、最佳適應(yīng)算法、最壞適應(yīng)算法來(lái)處理 該作業(yè)序列，看哪種算法合適。,主存管理分區(qū)存儲(chǔ)管理,30,三種放置策略的討論 首次適應(yīng)算法、最佳適應(yīng)算法、最壞適應(yīng)算法的隊(duì)列結(jié)構(gòu)。,主存管理分區(qū)存儲(chǔ)管理,31,三種放置策略的討論 首次適應(yīng)算法,主存管理分區(qū)存儲(chǔ)管理,作業(yè)A要求18KB 作業(yè)B要求25KB 作業(yè)C要求30KB 首次適應(yīng)算法對(duì)該作業(yè)序列是不合適的,32

12、,最佳適應(yīng)算法,主存管理分區(qū)存儲(chǔ)管理,作業(yè)A要求18KB 作業(yè)B要求25KB 作業(yè)C要求30KB 最佳適應(yīng)算法對(duì)該作業(yè)序列是合適的,33,最壞適應(yīng)算法,主存管理分區(qū)存儲(chǔ)管理,作業(yè)A要求18KB 作業(yè)B要求25KB 作業(yè)C要求30KB 最壞適應(yīng)算法對(duì)該作業(yè)序列是不合適的,34,4. 碎片問(wèn)題及拼接技術(shù) 什么是碎片問(wèn)題 在已分配區(qū)之間存在著的一些沒(méi)有被充分利用的空閑區(qū),主存管理分區(qū)存儲(chǔ)管理,如何解決碎片問(wèn)題？,什么是拼接技術(shù) 所謂拼接技術(shù)是指移動(dòng)存儲(chǔ)器中某些已分配區(qū)中的信息，使本來(lái)分散的空閑區(qū)連成一個(gè)大的空閑區(qū)。,35,1. 頁(yè)式系統(tǒng)的基本概念 頁(yè)面 程序的地址空間被等分成 大小相等的片，稱(chēng)為頁(yè)面

13、， 又稱(chēng)為虛頁(yè)。 主存塊 主存被等分成大小相等的 片，稱(chēng)為主存塊，又稱(chēng)為 實(shí)頁(yè)。 頁(yè)面與主存塊的關(guān)系,主存管理頁(yè)式存儲(chǔ)管理,36,頁(yè)表 什么是頁(yè)表 為了實(shí)現(xiàn)從地址空間到物理主存的映象，系統(tǒng)建立的 記錄頁(yè)與內(nèi)存塊之間對(duì)應(yīng)關(guān)系的地址變換的機(jī)構(gòu)稱(chēng)為 頁(yè)面映像表，簡(jiǎn)稱(chēng)頁(yè)表。 頁(yè)表的組成 高速緩沖存儲(chǔ)器 地址變換速度快，但成本較高 主存區(qū)域 地址變換速度比硬件慢，成本較低,主存管理頁(yè)式存儲(chǔ)管理,37,分頁(yè)映像存儲(chǔ)的例,主存管理頁(yè)式存儲(chǔ)管理,38,2. 頁(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)的格式

14、如下：,主存管理頁(yè)式存儲(chǔ)管理,391,頁(yè)式地址變換 頁(yè)式地址變換的例 作業(yè)2地址空間中，設(shè)100號(hào)單元處有如下指令： mov r1,2500。當(dāng)這條指令執(zhí)行時(shí)，如何進(jìn)行正確的 地址變換。,主存管理頁(yè)式存儲(chǔ)管理,2500 21024 + 452 p=2 w=452 0000100111000100 000010 0111000100,40,頁(yè)式地址變換過(guò)程,主存管理頁(yè)式存儲(chǔ)管理,0 0 0 1 1 1,0 1 1 1 0 0 0 1 0 0,41,頁(yè)式地址變換步驟 CPU給出操作數(shù)地址(為2500) ； 由分頁(yè)機(jī)構(gòu)自動(dòng)地把邏輯地址分為兩部分，得到頁(yè) 號(hào)p和頁(yè)內(nèi)相對(duì)位移w (p =2， w =45

15、2)； 根據(jù)頁(yè)表始址寄存器指示的頁(yè)表始地址，以頁(yè)號(hào)為 索引，找到第2頁(yè)所對(duì)應(yīng)的塊號(hào)(為7) ； 將塊號(hào)b和頁(yè)內(nèi)位移量w拼接在一起，就形成了訪(fǎng)問(wèn) 主存的物理地址 (7*1024+452=7620),主存管理頁(yè)式存儲(chǔ)管理,42,采用聯(lián)想存儲(chǔ)器加快查表速度 什么是聯(lián)想存儲(chǔ)器 高速、小容量半導(dǎo)體存儲(chǔ)部件，又稱(chēng)緩沖存儲(chǔ)器。 快表 在緩沖存儲(chǔ)器中存放正在運(yùn)行的進(jìn)程當(dāng)前用到的頁(yè)號(hào) 和對(duì)應(yīng)的塊號(hào)，又稱(chēng)為快表。,主存管理頁(yè)式存儲(chǔ)管理,43,利用快表進(jìn)行地址映射,主存管理頁(yè)式存儲(chǔ)管理,44,3. 請(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è)面

16、即可投入運(yùn)行。 (1) 簡(jiǎn)單頁(yè)式系統(tǒng)需要解決什么問(wèn)題？ (2) 請(qǐng)求分頁(yè)系統(tǒng)需要解決什么問(wèn)題?,主存管理頁(yè)式存儲(chǔ)管理,請(qǐng)求頁(yè)式系統(tǒng)需解決的問(wèn)題,擴(kuò)充頁(yè)表功能,中斷位I 標(biāo)識(shí)該頁(yè)是否在主存 若i=1，表示此頁(yè)不在主存；若i=0，表示該頁(yè)在主存 輔存地址 該頁(yè)面在輔存的位置,45,缺頁(yè)處理,主存管理頁(yè)式存儲(chǔ)管理,作業(yè)2在請(qǐng)求分頁(yè)系統(tǒng)中的存儲(chǔ)映像,46,主存管理頁(yè)式存儲(chǔ)管理,缺頁(yè)處理的例 作業(yè)2的主存塊數(shù)為 m2=3，討論程序執(zhí)行 “mov r1，2120”指令時(shí)的情況。,CPU產(chǎn)生的虛地址為2120 分頁(yè)機(jī)構(gòu)得 p=2，w=72 查頁(yè)表。該頁(yè)中斷位i=1 發(fā)生缺頁(yè)中斷 ！,如主存中有空白塊，且nm

17、 則直接調(diào)入 如主存中無(wú)空白塊，或n m ，則需淘汰該作業(yè)在主存中的一頁(yè),47,主存管理頁(yè)式存儲(chǔ)管理,缺頁(yè)處理,48,4. 淘汰機(jī)制與策略 什么是淘汰策略 用來(lái)選擇淘汰哪一頁(yè)的規(guī)則叫做置換策略，或稱(chēng)淘汰算法。,主存管理頁(yè)式存儲(chǔ)管理,如何決定淘汰哪一頁(yè)？,擴(kuò)充頁(yè)表功能,引用位 標(biāo)識(shí)該頁(yè)最近是否被訪(fǎng)問(wèn) 為“0” 該頁(yè)沒(méi)有被訪(fǎng)問(wèn)；為“1” 該頁(yè)已被訪(fǎng)問(wèn) 改變位 表示該頁(yè)是否被修改 為“0” 該頁(yè)未被修改；為“1” 該頁(yè)已被修改,49,顛簸 顛簸(thrashing)，又稱(chēng)為“抖動(dòng)”。 簡(jiǎn)單地說(shuō)，導(dǎo)致系統(tǒng)效率急劇下降的主存和輔存之間的 頻繁頁(yè)面置換現(xiàn)像稱(chēng)為“抖動(dòng)”。,主存管理頁(yè)式存儲(chǔ)管理,缺頁(yè)中斷率

18、假定程序p共有n頁(yè)，系統(tǒng)分配m塊，有 1mn； 若程序p在運(yùn)行中：成功的訪(fǎng)問(wèn)次數(shù)為s，不成功的訪(fǎng) 問(wèn)次數(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)

19、入主存的頁(yè)面； 當(dāng)需要置換一頁(yè)時(shí)，選擇替換指向的那一頁(yè)，然后調(diào)整替換指 針的內(nèi)容。,51,主存管理頁(yè)式存儲(chǔ)管理,頁(yè)號(hào)表 頁(yè)面進(jìn)入主存的先后次序： 2451,當(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í)： 如何處理 ? 512 6,53,主存管理頁(yè)式存儲(chǔ)管理,最久未使用淘汰算法(LRU算法),什么是最久未使用淘汰算法 總是選擇最長(zhǎng)時(shí)間未被使用的那一頁(yè)淘汰。 最久未使用淘汰算法的實(shí)現(xiàn) 用引用位考察頁(yè)面的使用情況； 當(dāng)訪(fǎng)問(wèn)頁(yè)面時(shí)，將引用位置1，并記時(shí)； 當(dāng)要淘汰一頁(yè)時(shí)，選

20、擇時(shí)間最長(zhǎng)的一頁(yè)淘汰。 要精確實(shí)現(xiàn)很困難 硬件方法：采用計(jì)數(shù)器 軟件方法：采用頁(yè)號(hào)棧,54,主存管理頁(yè)式存儲(chǔ)管理,軟件方法：采用頁(yè)號(hào)棧 頁(yè)面訪(fǎng)問(wèn)軌跡：451 2 5 6,訪(fǎng)問(wèn)4、5、1、2頁(yè)后棧的內(nèi)容,訪(fǎng)問(wèn)第5頁(yè)后，調(diào)整棧的內(nèi)容,訪(fǎng)問(wèn)第6頁(yè)后，棧的內(nèi)容,55,主存管理頁(yè)式存儲(chǔ)管理,LRU近似淘汰算法,56,主存管理頁(yè)式存儲(chǔ)管理,LRU近似淘汰算法舉例,當(dāng)要調(diào)入第6頁(yè)時(shí)，如何處理 ?,57,1. 段式地址空間 什么是段 分段是程序中自然劃分的一組邏輯意義完整的信息集合。 分段的例：代碼分段、數(shù)據(jù)分段、棧段頁(yè)。 作業(yè)地址空間 由若干個(gè)邏輯分段組成，每個(gè)分段有自己的名字，對(duì)于一個(gè)分段而 言，它是一個(gè)

21、連續(xù)的地址區(qū)。,主存管理段頁(yè)式存儲(chǔ)管理,58,段式地址結(jié)構(gòu),主存管理段頁(yè)式存儲(chǔ)管理,2. 段式地址變換,段式地址步驟 取出程序地址(s，w)； 用s檢索段表； 如w0或wL則主存越界； (Bw)即為所需主存地址,59,3. 頁(yè)式系統(tǒng)與段式系統(tǒng)的區(qū)別 用戶(hù)地址空間的區(qū)別 頁(yè)式系統(tǒng)中用戶(hù)地址空間一維地址空間 段式系統(tǒng)中用戶(hù)地址空間二維地址空間 分段和頁(yè)面的區(qū)別 分段 頁(yè)面 信息的邏輯劃分 信息的物理劃分 段長(zhǎng)是可變的 頁(yè)的大小是固定的 用戶(hù)可見(jiàn) 用戶(hù)不可見(jiàn) w字段的溢出 w字段的溢出自動(dòng) 將產(chǎn)生越界中斷 加入到頁(yè)號(hào)中,主存管理段頁(yè)式存儲(chǔ)管理,60,4. 段頁(yè)式系統(tǒng) 在段式存儲(chǔ)管理中結(jié)合分頁(yè)存儲(chǔ)管理

22、技術(shù)，在一個(gè)分段內(nèi) 劃分頁(yè)面，就形成了段頁(yè)式存儲(chǔ)管理。 段頁(yè)式地址結(jié)構(gòu)的用戶(hù)地址空間,主存管理段頁(yè)式存儲(chǔ)管理,61,主存管理段頁(yè)式存儲(chǔ)管理,段頁(yè)式系統(tǒng)中段表、頁(yè)表與主存的關(guān)系,62,1. Linux系統(tǒng)段頁(yè)式地址變換 Linux系統(tǒng)的分段 Linux系統(tǒng)處在用戶(hù)態(tài)時(shí)，使用用戶(hù)代碼段和用戶(hù)數(shù)據(jù) 段來(lái)對(duì)指令和數(shù)據(jù)尋址 在核態(tài)時(shí)，使用內(nèi)核代碼段和內(nèi)核數(shù)據(jù)段來(lái)對(duì)指令和 數(shù)據(jù)尋址 每個(gè)分段是一個(gè)連續(xù)的線(xiàn)性地址空間，從0開(kāi)始直到 2321的尋址長(zhǎng)度。,主存管理Linux系統(tǒng)存儲(chǔ)管理,63,80 x86分頁(yè)結(jié)構(gòu) 80 x86微處理器的分頁(yè)單元處理4KB的頁(yè)。一個(gè)32位的 線(xiàn)性地址分為3個(gè)域。,主存管理Lin

23、ux系統(tǒng)存儲(chǔ)管理,頁(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ǔ)管理,線(xiàn)性地址轉(zhuǎn)換為物理地址 地址轉(zhuǎn)換過(guò)程 Linux系統(tǒng)通過(guò)三級(jí)頁(yè)表完成線(xiàn)性地址到物理地址的轉(zhuǎn)換,66,主存管理Linux系統(tǒng)存儲(chǔ)管理,地址變換步驟 由cr3指示的當(dāng)前頁(yè)目錄的物理地址與分頁(yè)結(jié)構(gòu)中的 頁(yè)目錄字段的內(nèi)容相加指向頁(yè)

24、目錄表項(xiàng)； 由頁(yè)目錄表項(xiàng)內(nèi)容得到當(dāng)前使用的頁(yè)表的始地址， 通過(guò)分頁(yè)結(jié)構(gòu)中的頁(yè)表字段的內(nèi)容找到該頁(yè)表項(xiàng)； 由頁(yè)表項(xiàng)指示的該頁(yè)的物理頁(yè)(頁(yè)框)的主存地址與 分頁(yè)結(jié)構(gòu)中的頁(yè)內(nèi)位移相加，得到最終的物理地址。,67,2. Linux系統(tǒng)動(dòng)態(tài)內(nèi)核管理 物理頁(yè)的描述 Linux系統(tǒng)主存分配的基本單位是物理頁(yè)(又稱(chēng)為頁(yè)框) 主存管理單元MMU以頁(yè)為單位進(jìn)行分配和處理 32位體系結(jié)構(gòu)支持4KB的頁(yè)，64位體系結(jié)構(gòu)支持8KB的頁(yè) 內(nèi)核用struct page結(jié)構(gòu)描述頁(yè)框 struct page flags; /* 頁(yè)的狀態(tài) */ _count; /* 該頁(yè)被引用的次數(shù) */ *virtual; /* 頁(yè)的虛擬地址

25、，通常情況下記錄頁(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è)只能用來(lái)執(zhí)行DMA操作，大小為16MB； ZONE_NORMAL 這個(gè)分區(qū)包含的頁(yè)都是能正常映射的頁(yè)，大小為16MB 896MB ZONE_HIGHMEM 這個(gè)分區(qū)包含的是“高端主存”，其中的物理頁(yè)并不能永久地映射到內(nèi)核地址空間，大小為896MB。,主存管理Linux系統(tǒng)存儲(chǔ)管理,69,分區(qū)頁(yè)框的分配 Linux內(nèi)核通過(guò)頁(yè)框和區(qū)對(duì)主存進(jìn)行管理，實(shí)現(xiàn)了請(qǐng)求 主

26、存的底層機(jī)制； 內(nèi)核提供提供一組訪(fǎng)問(wèn)接口 (函數(shù)或宏) 可以直接的方 式獲得動(dòng)態(tài)主存，注意這種方式只能由內(nèi)核使用。,主存管理Linux系統(tǒng)存儲(chǔ)管理,70,主存管理Linux系統(tǒng)存儲(chǔ)管理,分區(qū)頁(yè)框分配器 分區(qū)頁(yè)框分配器( Zoned page frame allocator)是一個(gè)內(nèi)核 子系統(tǒng)，它負(fù)責(zé)對(duì)連續(xù)頁(yè)框的主存分配。 分區(qū)頁(yè)框分配器的組成如下圖,71,主存管理Linux系統(tǒng)存儲(chǔ)管理,伙伴系統(tǒng)算法 主存管理中的外碎片問(wèn)題 當(dāng)頻繁地請(qǐng)求和釋放不同大小的連續(xù)頁(yè)框，就會(huì)導(dǎo)致在已分配 頁(yè)框內(nèi)產(chǎn)生許多小的、分散的空閑頁(yè)框； Linux系統(tǒng)采用伙伴系統(tǒng)算法記錄當(dāng)前空閑的連續(xù)頁(yè)框塊的情 況，以盡量避免為滿(mǎn)

27、足小塊的請(qǐng)求而分割大的空閑塊。,伙伴系統(tǒng)算法中頁(yè)框的組織 將所有的空閑頁(yè)框分組為11個(gè)塊鏈表； 每個(gè)塊鏈表分別包含大小為1、2、4、8、16、32、64、128、 256、512、1024個(gè)連續(xù)頁(yè)框； 每個(gè)塊的第一個(gè)頁(yè)框的物理地址是該塊大小的整數(shù)倍。,72,主存管理Linux系統(tǒng)存儲(chǔ)管理,頁(yè)框的分配過(guò)程 以分配256個(gè)頁(yè)框的塊為例說(shuō)明伙伴系統(tǒng)算法的頁(yè)框的 分配過(guò)程 首先在256個(gè)頁(yè)框的鏈表中檢查是否有一個(gè)空閑塊滿(mǎn)足需要； 若沒(méi)有，則在512個(gè)頁(yè)框的鏈表中找滿(mǎn)足需要的空閑塊 若存在這樣的塊，算法將這512的頁(yè)框分為2半； 一半用來(lái)滿(mǎn)足請(qǐng)求，另一半插入到256個(gè)頁(yè)框的鏈表中； 若還沒(méi)有，則在102

28、4個(gè)頁(yè)框的鏈表中找滿(mǎn)足需要的空閑塊； 若存在，則將256塊用來(lái)滿(mǎn)足要求，其余部分分為256塊和 512塊分別插入到相應(yīng)的鏈表中； 若不存在；算法放棄并給出不能滿(mǎn)足分配的信息。,73,主存管理Linux系統(tǒng)存儲(chǔ)管理,頁(yè)框的釋放過(guò)程 分配過(guò)程的逆過(guò)程就是頁(yè)框的釋放過(guò)程 內(nèi)核試圖將大小為b 的一對(duì)空閑伙伴塊合并為一個(gè)大小為2b的 單獨(dú)塊。滿(mǎn)足以下條件的兩個(gè)塊稱(chēng)為伙伴： 兩個(gè)塊的大小相同，記為b； 它們的物理地址是連續(xù)的； 第一塊的第一個(gè)頁(yè)框的物理地址是2b212的倍數(shù) 算法是迭代的，如果它成功合并所釋放的塊，它會(huì)試圖合并2b 的塊，以再次試圖形成跟更大的塊。,74,3. Linux系統(tǒng)的進(jìn)程地址空間 Linux內(nèi)核提供用于頁(yè)框分配和釋放的函數(shù)(或宏)。這些函數(shù)只能由 內(nèi)核直接使用，用戶(hù)進(jìn)程請(qǐng)求