【文章內(nèi)容簡介】 ress space USTC。 21000201OPERATING SYSTEMS。 FALL 2022。 INSTRUCTOR: LINGBO WEI 37 Page size=4KB=212 232 220 pages 4byte page table entry 222 210 pages 212 1 page 三級頁表結(jié)構(gòu)及其地址映射過程 USTC21000201OPERATING SYSTEMS。 FALL 2022。 INSTRUCTOR: LINGBO WEI 38 倒排頁表的引入 ? 64位地址，兩級頁表不行了。因?yàn)椋? ? 設(shè)頁大小為 4KB（ 12位），則塊號占 52位（用 8字節(jié)存儲(chǔ)），每塊可存儲(chǔ) 512個(gè)塊號（故頁表索引號占 9位），則外層頁號占 43位（有 243個(gè)頁表）， 243個(gè)表項(xiàng)，因每個(gè)表項(xiàng) 8（即 23）個(gè)字節(jié)，所以存放外層頁表需要 246個(gè)字節(jié)（ 64TB），大得嚇人 ——兩級頁表已經(jīng)不行了。 USTC21000201OPERATING SYSTEMS。 FALL 2022。 INSTRUCTOR: LINGBO WEI 39 即使 用 3級頁表也不行。 34位 9位 9位 12位 外層頁表有 234個(gè)表項(xiàng)，占 237字節(jié)， 128GB。 倒排頁表 ? 傳統(tǒng)頁表面向進(jìn)程空間 (邏輯地址空間 ) ? 每個(gè)進(jìn)程邏輯頁面有一表項(xiàng) ? 當(dāng)進(jìn)程空間很大時(shí)，頁表很大 ? 倒排頁表面向內(nèi)存空間 (物理地址空間 ) 問題：倒排頁表的搜索很慢！ ? 每個(gè)內(nèi)存頁框一個(gè)表項(xiàng)，大小固定 ? 整個(gè)系統(tǒng)共用一個(gè)頁表 USTC21000201OPERATING SYSTEMS。 FALL 2022 40 程序 物理 內(nèi)存 … … pid p … … f d pid p d f 邏輯地址 物理地址 倒排 頁表：使用頁框號來索引頁表項(xiàng) 搜索 p: 邏輯頁號 f: 物理框號 d: 頁內(nèi)偏移 pid: 進(jìn)程 ID 倒排頁表 ? 傳統(tǒng)頁表面向進(jìn)程空間 (邏輯地址空間 ) ? 每個(gè)進(jìn)程邏輯頁面有一表項(xiàng) ? 當(dāng)進(jìn)程空間很大時(shí)，頁表很大 ? 倒排頁表面向內(nèi)存空間 (物理地址空間 ) ? 每個(gè)內(nèi)存頁框一個(gè)表項(xiàng)，大小固定 ? 整個(gè)系統(tǒng)共用一個(gè)頁表 USTC21000201OPERATING SYSTEMS。 FALL 2022 41 程序 物理 內(nèi)存 … … pid p … … f d pid p d f 邏輯地址 物理地址 缺點(diǎn)：關(guān)聯(lián)寄存器大小受限！ 空間大小成為問題 使用關(guān)聯(lián)寄存器組并行查找 優(yōu)點(diǎn)：速度不是問題 p: 邏輯頁號 f: 物理框號 d: 頁內(nèi)偏移 pid: 進(jìn)程 ID 過渡：哈希頁表 42 ? Common in address spaces 32 bits ? The virtual page number is hashed into a page table. This page table contains a chain of elements hashing to the same location. ? Virtual page numbers are pared in this chain searching for a match. If a match is found, the corresponding physical frame is extracted. p, q: 邏輯頁號 s, r: 物理框號 d: 頁內(nèi)偏移 采用哈希函數(shù)的倒排頁表 USTC21000201OPERATING SYSTEMS。 FALL 2022。 INSTRUCTOR: LINGBO WEI 43 邏輯地址 pid p d 進(jìn)程 邏輯頁號 沖突計(jì)數(shù) 鏈表 ... … … … pid p 2 … … … … … 進(jìn) 程 哈希函數(shù) f f d 物理地址 采用 哈希函數(shù) 的倒排頁表 物理內(nèi)存 溢 出 鏈 ? 將哈希頁表與倒排頁表結(jié)合，解決倒排表搜索速度慢的問題 ? 哈希表中的槽數(shù)與機(jī)器中物理頁框數(shù)一樣多，則哈希表中的溢出鏈（沖突）平均長度會(huì)是 1，這將大大提高映射的速度。 p: 邏輯頁號 f: 物理框號 d: 頁內(nèi)偏移 pid: 進(jìn)程 ID 用硬件 實(shí)現(xiàn) 分頁的共享與保護(hù) USTC21000201OPERATING SYSTEMS。 FALL 2022。 INSTRUCTOR: LINGBO WEI 44 存儲(chǔ)保護(hù) ? 越界保護(hù)：設(shè)置頁表長度寄存器，查頁表前，先檢查頁號是否越界。 ? 操作訪問保護(hù)：在 每個(gè)頁表項(xiàng) 中增設(shè)一存儲(chǔ)保護(hù)域，用于說明對該頁的訪問權(quán)限，每一個(gè)對該頁存儲(chǔ)的訪問都首先要比照是否滿足該頁訪問權(quán)限的說明，滿足則訪問，否則報(bào)錯(cuò)。 例 ：設(shè)為每一頁表項(xiàng)增加三位， R位表示讀權(quán)限， W位表示寫權(quán)限， E位表示執(zhí)行權(quán)限。 R W E 0 0 0 不可進(jìn)行任何操作 0 0 1 可以執(zhí)行 ,不可以讀寫 1 0 0 只 可以讀 分頁的共享與保護(hù) ? 分頁的共享 ?理論上分頁管理可以實(shí)現(xiàn)共享，某一時(shí)刻，不同作業(yè)的不同頁面對應(yīng)于同一個(gè)內(nèi)存幀號，該內(nèi)存塊就被共享了。但由于頁面的劃分并沒有考慮作業(yè)地址空間的邏輯意義，所對應(yīng)的內(nèi)存塊中的數(shù)據(jù)無法劃分出那些可以共享，如果使用頁表來硬性共享內(nèi)存中某一幀，則可能會(huì)導(dǎo)致對該塊數(shù)據(jù)的破壞，因此實(shí)際上無法實(shí)現(xiàn)真正意義上的共享。 USTC21000201OPERATING SYSTEMS。 FALL 2022。 INSTRUCTOR: LINGBO WEI 45 USTC21000201OPERATING SYSTEMS。 FALL 2022。 INSTRUCTOR: LINGBO WEI 46 Part 2: 內(nèi)存管理 ? 硬件背景 ? 基本內(nèi)存管理 ? 虛擬內(nèi)存管理 ?非連續(xù)的內(nèi)存分配和內(nèi)存地址空間 ?分頁 ?分段 ?虛擬內(nèi)存管理算法 分段的引入 ? 主要是為了滿足用戶和程序員的下述需要： USTC21000201OPERATING SYSTEMS。 FALL 2022。 INSTRUCTOR: LINGBO WEI 47 方便編程 通常用戶把自己的程序按邏輯關(guān)系分為若干個(gè)段 ， 每段都從 0開始編址 ， 并有自己的名字和長度 。 因此 ， 希望要訪問的邏輯地址是由段名 (段號 )和段內(nèi)偏移量 (段內(nèi)地址 )決定的 。 信息共享 在實(shí)現(xiàn)對程序和數(shù)據(jù)的共享時(shí) ， 是以信息的邏輯單位為基礎(chǔ)的 ， 比如 ， 共享某個(gè)例程和函數(shù) 。 分頁系統(tǒng)中的 “ 頁 ” 只是存放信息的物理單位 （ 塊 ） ， 并無完整的意義 ， 不便于實(shí)現(xiàn)共享；而段卻是信息的邏輯單位 。 信息保護(hù) 信息保護(hù)同樣是對信息的邏輯單位進(jìn)行保護(hù) ， 因此 ， 分段管理能更有效地實(shí)現(xiàn)信息保護(hù)功能 。 動(dòng)態(tài)增長 在實(shí)際應(yīng)用中，往往有些段，特別是數(shù)據(jù)段，在使用過程中會(huì)不斷增長，而事先又無法確切地知道數(shù)據(jù)段會(huì)增長到多大。前述的其它幾種存儲(chǔ)管理方式，都難以應(yīng)付這種動(dòng)態(tài)增長的情況，而分段存儲(chǔ)管理方式卻能較好地解決這一問題 動(dòng)態(tài)連接 動(dòng)態(tài)鏈接是指在作業(yè)運(yùn)行之前 ， 并不把幾個(gè)目標(biāo)程序鏈接起來 。 要運(yùn)行時(shí) ， 先將主程序所對應(yīng)的目標(biāo)程序裝入內(nèi)存并啟動(dòng)運(yùn)行 ， 當(dāng)運(yùn)行過程中需要調(diào)用某段時(shí) ， 才將該段 （ 目標(biāo)程序 ） 調(diào)入內(nèi)存并進(jìn)行鏈接 。 可見 ， 動(dòng)態(tài)鏈接也要求以段作為管理的單位 。 分段中的基本概念 ? 分段 ? 將進(jìn)程的地址空間劃分為若干個(gè)邏輯段，段的長度由邏輯信息本身的長度決定。每一段占一個(gè)連續(xù)內(nèi)存分區(qū) ? 每個(gè)段都有名字。為實(shí)現(xiàn)簡單，常用段號代替段名 (段號從 0開始 ) ? 分段在編譯時(shí)由編譯程序完成。 USTC21000201OPERATING SYSTEMS。 FALL 2022。 INSTRUCTOR: LINGBO WEI 48 … CALL[X]|Y … LOAD1,[A]|6 STORE1,[B]|C … 分段 MAIN … Y … … … C … 分段 X （子程序） 分段 A （ 數(shù)據(jù)） 分段 B （工作區(qū)） 分段中的基本概念 ? 每個(gè)段內(nèi)都從 0開始編址，并采用一段連續(xù)的地址空間。由于分多個(gè)段，所以地址是二維的，亦即邏輯地址由段號S和段內(nèi)地址 d組成。具體結(jié)構(gòu)舉例如下： USTC21000201OPERATING SYSTEMS。 FALL 2022。 INSTRUCTOR: LINGBO WEI 49 段號 S 段內(nèi)地址 d 31 20 19 0 該地址結(jié)構(gòu)中允許作業(yè)最多有 4K(212)個(gè)段，每段最大長度為 1MB(220)。 段表 ? 在分段存儲(chǔ)管理系統(tǒng)中，為每個(gè)分段分配一個(gè)連續(xù)的分區(qū)，而進(jìn)程中的各個(gè)段可以離散地移入內(nèi)存中的不同的分區(qū)中 ? 系統(tǒng)為每個(gè)進(jìn)程建立一張段映射表，簡稱為 ―段表 ‖ ? 每個(gè)段在段表中占一個(gè)表項(xiàng)，其中記錄了該段在內(nèi)存中的起始地址 (又稱為 ―基址 ‖)和段的長度 ? 實(shí)現(xiàn)從邏輯段到物理內(nèi)存區(qū)的映射。 USTC。 21000201OPERATING SYSTEMS。 FALL 2022。 INSTRUCTOR: CHI ZHANG 50 (MAIN)=0 (X)=1 (D)=2 (S)=3 基址 段長 段號 3 2 1 0 150K 10KB 120K 15KB 80K 20KB 40K 30KB 進(jìn)程 空間 段表 (MIAN)=0 30KB (X)=1 20KB (D