工學(xué)存儲(chǔ)管理PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1工學(xué)存儲(chǔ)管理工學(xué)存儲(chǔ)管理6.1 存儲(chǔ)管理功能存儲(chǔ)管理功能n 內(nèi)存/外存的管理;n 內(nèi)/外存管理采用相同 或相似的管理技術(shù)；n 功 能 l 存儲(chǔ)分配存儲(chǔ)分配l 存儲(chǔ)共享存儲(chǔ)共享l 存儲(chǔ)保護(hù)存儲(chǔ)保護(hù)l 存儲(chǔ)擴(kuò)充存儲(chǔ)擴(kuò)充l 地址映射地址映射第1頁(yè)/共62頁(yè)第2頁(yè)/共62頁(yè)第3頁(yè)/共62頁(yè)第4頁(yè)/共62頁(yè)第5頁(yè)/共62頁(yè)6.2.2.1 靜態(tài)等長(zhǎng)分區(qū)的分配靜態(tài)等長(zhǎng)分區(qū)的分配n 字位映象圖字位映象圖(bit map)用一個(gè) bit 代表一頁(yè)狀態(tài)，0: 空閑，1: 占用。1001.10第第0頁(yè)頁(yè)第第1頁(yè)頁(yè)第第2頁(yè)頁(yè)第第k頁(yè)頁(yè)第第n-1頁(yè)頁(yè)第第n頁(yè)頁(yè)分配: 按頁(yè)號(hào)從小到大查字位圖, 找到為0的位改為1

2、，返回頁(yè)號(hào)。去配: 把頁(yè)號(hào)對(duì)應(yīng)的 bit 置為 0 。第6頁(yè)/共62頁(yè)n 空閑頁(yè)面表空閑頁(yè)面表:首頁(yè)面號(hào)首頁(yè)面號(hào)頁(yè)面?zhèn)€數(shù)頁(yè)面?zhèn)€數(shù)1204占用占用120頁(yè)頁(yè)121頁(yè)頁(yè)122頁(yè)頁(yè)123頁(yè)頁(yè)占用占用內(nèi)存內(nèi)存分配/去配: 需修改空閑頁(yè)面表。特點(diǎn): 可以分配連續(xù)頁(yè)面。 DMA 要求6.2.2.1 靜態(tài)等長(zhǎng)分區(qū)的分配靜態(tài)等長(zhǎng)分區(qū)的分配(Cont.)空閑頁(yè)面表結(jié)構(gòu)空閑頁(yè)面表結(jié)構(gòu)第7頁(yè)/共62頁(yè)6.2.2.1 靜態(tài)等長(zhǎng)分區(qū)的分配靜態(tài)等長(zhǎng)分區(qū)的分配(Cont.)n 空閑頁(yè)面鏈空閑頁(yè)面鏈 :占 用占 用占 用head空閑頁(yè)面鏈結(jié)構(gòu)空閑頁(yè)面鏈結(jié)構(gòu)分配/去配: 調(diào)整鏈表。特點(diǎn): 節(jié)省空間。 (不適合外存管理)第8頁(yè)/

3、共62頁(yè)6.2.2.2 動(dòng)態(tài)異長(zhǎng)分區(qū)的分配動(dòng)態(tài)異長(zhǎng)分區(qū)的分配常用于界地址存儲(chǔ)管理和段式存儲(chǔ)管理。常用于界地址存儲(chǔ)管理和段式存儲(chǔ)管理?？臻e區(qū)首址空閑區(qū)首址空閑區(qū)長(zhǎng)度空閑區(qū)長(zhǎng)度.addresssize0空閑區(qū)表空閑區(qū)表n 初始時(shí)一個(gè)連續(xù)空閑區(qū);n 空閑區(qū)首址由小到大;n 長(zhǎng)度 = 0 為表尾。分配: 按分配策略調(diào)整表項(xiàng);去配: 把去配的空間插入表中, 可能需要合并空閑區(qū)。第9頁(yè)/共62頁(yè)6.2.2.2 動(dòng)態(tài)異長(zhǎng)分區(qū)的分配動(dòng)態(tài)異長(zhǎng)分區(qū)的分配(Cont.)最先適應(yīng)算法最先適應(yīng)算法(First Fit) :空閑區(qū)首址空閑區(qū)首址空閑區(qū)長(zhǎng)度空閑區(qū)長(zhǎng)度128642563210242560空閑區(qū)表空閑區(qū)表空閑區(qū)

4、: 首址遞增排列；申請(qǐng): 取第一個(gè)可滿足區(qū)域 ;優(yōu)點(diǎn): 盡量使用低地址空間, 高區(qū)保持大空閑區(qū)域。缺點(diǎn): 可能分割大空閑區(qū)。 如申請(qǐng)32將分割第一個(gè)區(qū)域。第10頁(yè)/共62頁(yè)6.2.2.2 動(dòng)態(tài)異長(zhǎng)分區(qū)的分配動(dòng)態(tài)異長(zhǎng)分區(qū)的分配(Cont.)最佳適應(yīng)算法最佳適應(yīng)算法(Best Fit) :空閑區(qū)首址空閑區(qū)首址空閑區(qū)長(zhǎng)度空閑區(qū)長(zhǎng)度256321286410242560空閑區(qū)表空閑區(qū)表空閑區(qū): 空閑區(qū)長(zhǎng)度遞增排列 ;申請(qǐng): 取最小可滿足區(qū)域 ;優(yōu)點(diǎn): 盡量使用小空閑區(qū), 保持大空閑區(qū)域。缺點(diǎn): 容易形成碎片fragment。 如申請(qǐng)30將留下長(zhǎng)度為2的空閑區(qū)。第11頁(yè)/共62頁(yè)6.2.2.2 動(dòng)態(tài)異長(zhǎng)分

5、區(qū)的分配動(dòng)態(tài)異長(zhǎng)分區(qū)的分配(Cont.)最壞適應(yīng)算法最壞適應(yīng)算法(Worst Fit) :空閑區(qū)首址空閑區(qū)首址空閑區(qū)長(zhǎng)度空閑區(qū)長(zhǎng)度102425612864256320空閑區(qū)表空閑區(qū)表空閑區(qū): 空閑區(qū)長(zhǎng)度遞減排列。申請(qǐng): 取最大可滿足區(qū)域。優(yōu)點(diǎn): 防止形成碎片。缺點(diǎn): 分割大空閑區(qū)。第12頁(yè)/共62頁(yè)最先適應(yīng)算法，空閑區(qū)首址遞增排列define CMAPSIZ 100define SMAPSIZ 100struct map /存儲(chǔ)資源表結(jié)構(gòu) char *m_size; char *m_addr;struct map coremapCMAPSIZ; /內(nèi)存資源表struct map swapmap

6、SMAPSIZ; /外存資源表第13頁(yè)/共62頁(yè)int malloc (mp, size ) /存儲(chǔ)分配函數(shù)struct map *mp; register int a ; register struct map *bp ; for (bp = mp; bp - m_size ; bp +) if ( bp - m_size = size ) a= bp - m_addr ; bp - m_addr += size ; if ( bp - m_size -= size ) = 0) /當(dāng)前塊size do bp +; /do循環(huán)壓縮size=0的存儲(chǔ)表項(xiàng) (bp-1) - m_addr = b

7、p - m_addr ; while(bp-1)-m_size = bp - m_size); return(a); /分配成功，返回分配存儲(chǔ)塊的首地址 return(0); /分配不成功，返回0存儲(chǔ)分配函數(shù): mp=coremap 內(nèi)存分配swapmap 外存分配第14頁(yè)/共62頁(yè)mfree (mp, size, aa)struct map *map; register struct map bp ; register int t , a ; a = aa ; for (bp = mp; bp - m_addrm_size !=0; bp +); if (bp mp & (bp-1)

8、-m_addr+(bp-1)-m_size = a) (bp-1)-m_size =+ size; /與前項(xiàng)存儲(chǔ)塊合并 if (a+size = bp - m_addr) /判斷與后項(xiàng)存儲(chǔ)塊是否相連 (bp-1)-m_size += bp -m_size; /再與后項(xiàng)存儲(chǔ)塊合并 while (bp-m_size) /刪除后項(xiàng)存儲(chǔ)塊表項(xiàng) bp+; (bp-1)- m_addr = bp - m_addr ; (bp-1)-m_size = bp - m_size ; 存儲(chǔ)釋放算法: mp=coremap 釋放內(nèi)存swapmap 釋放外存第15頁(yè)/共62頁(yè) else /是存儲(chǔ)表項(xiàng)的第一項(xiàng)或不與前項(xiàng)

9、存儲(chǔ)塊相連 if (a+size = bp -m_addr & bp -m_size) /與后項(xiàng)存儲(chǔ)塊相連? bp- m_addr -= size; /與后項(xiàng)存儲(chǔ)塊合并。 bp -m_size += size ; else if (size) /與前、后項(xiàng)存儲(chǔ)塊均不相連, 插入(size,a)表項(xiàng) do t = bp - m_addr ; /do循環(huán)逐項(xiàng)后移 bp - m_addr = a; a = t; /a與 bp - m_addr 交換 t = bp - m_size; bp - m_size = size; / size 與bp - m_size 交換 bp+; while (

10、size = t ); 存儲(chǔ)釋放算法(Cont.)第16頁(yè)/共62頁(yè)6.2.3 碎片與緊湊碎片與緊湊緊湊(Compaction): 移動(dòng)占用區(qū)域，使所有空閑區(qū)域 連成一片(開(kāi)銷很大)。0 KB操作系統(tǒng)空間操作系統(tǒng)空間20KB20 KB空閑區(qū)域空閑區(qū)域10KB30 KB進(jìn)程進(jìn)程p1空間空間30KB60 KB空閑區(qū)域空閑區(qū)域10KB70 KB進(jìn)程進(jìn)程p1空間空間20KB90 KB空閑區(qū)域空閑區(qū)域10KB緊湊前0 KB操作系統(tǒng)空間操作系統(tǒng)空間20KB20 KB進(jìn)程進(jìn)程p1空間空間30KB50 KB進(jìn)程進(jìn)程p1空間空間20KB70 KB空閑區(qū)域空閑區(qū)域30KB緊湊后第17頁(yè)/共62頁(yè)址址)n 段頁(yè)式管

11、理方式段頁(yè)式管理方式(二維二維地址地址)第18頁(yè)/共62頁(yè)6.3.1 界地址管理方式界地址管理方式單對(duì)界存儲(chǔ)管理方式單對(duì)界存儲(chǔ)管理方式: (首地址首地址, 長(zhǎng)度長(zhǎng)度)基本原理 內(nèi)存空間劃分: 動(dòng)態(tài)異長(zhǎng)； 進(jìn)程空間劃分: 一個(gè)進(jìn)程一個(gè)區(qū)域, 邏輯地址0L -1 ; 進(jìn)程空間與內(nèi)存空間對(duì)應(yīng)關(guān)系(可以浮動(dòng)) :0 :L-1 :b :b+L-1 :L進(jìn)程空間內(nèi)存空間第19頁(yè)/共62頁(yè)6.3.1 界地址管理方式界地址管理方式(Cont.) 所需表目： 內(nèi)存分配表: 在PCB中 ; 空閑區(qū)域表: array of ( addr , size )。 所需寄存器： 基址寄存器b: 保存運(yùn)行進(jìn)程起始地址; 限長(zhǎng)

12、寄存器l : 保存運(yùn)行進(jìn)程長(zhǎng)度。第20頁(yè)/共62頁(yè)6.3.1 界地址管理方式界地址管理方式(Cont.) 地址映射： : (a) (b+a) 0:L-1:b:b+L-1:L進(jìn)程空間內(nèi)存空間限長(zhǎng)寄存器首址寄存器Lba越界中斷CMP+b+a步驟 : 由程序確定邏輯地址 a ; a與 L 比較判斷是否越界，不滿足: 0aL-1，越界; a與 b 相加得到物理地址。第21頁(yè)/共62頁(yè)6.3.1 界地址管理方式界地址管理方式(Cont.)n 雙對(duì)界l 代碼區(qū)域代碼區(qū)域: 首址寄存器、限長(zhǎng)寄存器首址寄存器、限長(zhǎng)寄存器 ;l 數(shù)據(jù)區(qū)域數(shù)據(jù)區(qū)域: 首址寄存器、限長(zhǎng)寄存器首址寄存器、限長(zhǎng)寄存器 ;l UNIX

13、: 代碼代碼I空間、數(shù)據(jù)空間、數(shù)據(jù)D空間?？臻g。n 交換與重定位l 交換交換: 換入換入(swap-in)/換出換出(swap-out) ; 滾入(roll-in)/滾出(roll-out) ; 交換的基本單位為整個(gè)進(jìn)程。l 可重定位程序可重定位程序: 程序編址與內(nèi)存存放位置無(wú)關(guān)程序編址與內(nèi)存存放位置無(wú)關(guān) ;l 浮動(dòng)程序浮動(dòng)程序: 滿足重定位要求的程序滿足重定位要求的程序,如如0起始編址。起始編址。l 重定位重定位: 換入程序需重定位。換入程序需重定位。第22頁(yè)/共62頁(yè)6.3.1 界地址管理方式界地址管理方式(Cont.)n 覆蓋技術(shù)覆蓋技術(shù): 將較大程序裝入較小進(jìn)程空間的技術(shù)將較大程序裝入

14、較小進(jìn)程空間的技術(shù), 最大限度提高內(nèi)存利用率。最大限度提高內(nèi)存利用率。l 只將全局代碼和數(shù)據(jù)靜態(tài)裝入內(nèi)存只將全局代碼和數(shù)據(jù)靜態(tài)裝入內(nèi)存, 其它部分動(dòng)態(tài)裝入其它部分動(dòng)態(tài)裝入;l 后裝入的成分重復(fù)使用先裝入成分所使用的后裝入的成分重復(fù)使用先裝入成分所使用的 存儲(chǔ)區(qū)存儲(chǔ)區(qū), 即覆蓋先裝入的成分即覆蓋先裝入的成分;l 用戶編寫(xiě)用戶編寫(xiě)覆蓋驅(qū)動(dòng)程序覆蓋驅(qū)動(dòng)程序, 無(wú)需操作系統(tǒng)支持。無(wú)需操作系統(tǒng)支持。第23頁(yè)/共62頁(yè)6.3.1 界地址管理方式界地址管理方式(Cont.)例覆蓋技術(shù)：四遍掃描的編譯程序符符 號(hào)號(hào) 表表公公 共共 例例 程程覆蓋驅(qū)動(dòng)程序覆蓋驅(qū)動(dòng)程序覆覆 蓋蓋 區(qū)區(qū)50 KB內(nèi) 存Pass13

15、0 KBPass250 KBPass425 KBPass340 KB第24頁(yè)/共62頁(yè)6.3.2 分頁(yè)式存儲(chǔ)管理分頁(yè)式存儲(chǔ)管理頁(yè)式存儲(chǔ)管理(paging): 一個(gè)進(jìn)程占多個(gè)等長(zhǎng)、連續(xù)內(nèi)存空間; 無(wú)碎片。6.3.2.1 基本原理 內(nèi)存空間劃分: 頁(yè)架: 靜態(tài)等長(zhǎng), 長(zhǎng)度2 i ; 頁(yè)架號(hào): 所有頁(yè)架由0開(kāi)始依次編號(hào) ; 頁(yè)內(nèi)地址: 頁(yè)架內(nèi)單元由0開(kāi)始依次編址。 例如: 內(nèi)存容量為2 n , 則共有2 n-i個(gè)頁(yè)架。 第 k 個(gè)頁(yè)架的起始地址為 k2 i。第25頁(yè)/共62頁(yè)6.3.2 分頁(yè)式存儲(chǔ)管理分頁(yè)式存儲(chǔ)管理(Cont.)02i第第 0 頁(yè)頁(yè)2i12i第第 1 頁(yè)頁(yè)2ik2i第第 k 頁(yè)頁(yè)2i

16、(2n-i-1)2i第第 2n-i1 頁(yè)頁(yè)2i內(nèi)存空間劃分n 位一維地址碼=頁(yè)架首址+頁(yè)內(nèi)地址=頁(yè)架號(hào)2i+頁(yè)內(nèi)地址=頁(yè)內(nèi)地址頁(yè)內(nèi)地址頁(yè)架號(hào)頁(yè)架號(hào)i 位n-i 位物理地址第26頁(yè)/共62頁(yè)6.3.2 分頁(yè)式存儲(chǔ)管理分頁(yè)式存儲(chǔ)管理(Cont.) 進(jìn)程空間劃分: 靜態(tài)等長(zhǎng)，2 i, 稱為一個(gè)頁(yè)面。02i第第 0 頁(yè)頁(yè)2i12i第第 1 頁(yè)頁(yè)2ik2i第第 k 頁(yè)頁(yè)2i(l-1)2i第第 l1 頁(yè)頁(yè)2i進(jìn)程空間劃分=邏輯頁(yè)首址+頁(yè)內(nèi)地址=邏輯頁(yè)號(hào)2i+頁(yè)內(nèi)地址=頁(yè)內(nèi)地址頁(yè)內(nèi)地址邏輯頁(yè)號(hào)邏輯頁(yè)號(hào)i 位n-i 位邏輯地址第27頁(yè)/共62頁(yè)6.3.2 分頁(yè)式存儲(chǔ)管理分頁(yè)式存儲(chǔ)管理(Cont.) 進(jìn)程空間與

17、內(nèi)存空間對(duì)應(yīng)關(guān)系: 頁(yè)面連續(xù), 頁(yè)架可能不連續(xù)。第第 3 頁(yè)頁(yè)第第 2 頁(yè)頁(yè)第第 1 頁(yè)頁(yè)第第 0 頁(yè)頁(yè)進(jìn)程空間第第 79 頁(yè)頁(yè)第第 78 頁(yè)頁(yè)第第 47 頁(yè)頁(yè)第第 18 頁(yè)頁(yè)內(nèi)存空間第28頁(yè)/共62頁(yè)6.3.2 分頁(yè)式存儲(chǔ)管理分頁(yè)式存儲(chǔ)管理(Cont.) 所需表目n 頁(yè)表: 每個(gè)進(jìn)程一個(gè)。頁(yè)架號(hào)頁(yè)架號(hào)18477978邏輯頁(yè)號(hào)邏輯頁(yè)號(hào)0123n 總頁(yè)表: 系統(tǒng)一個(gè), 記錄頁(yè)架使用情況 兩種結(jié)構(gòu)：表、鏈。 所需寄存器n 頁(yè)表首址寄存器: 系統(tǒng)一個(gè)。bn 頁(yè)表長(zhǎng)度寄存器: 系統(tǒng)一個(gè)。ln 快表: 系統(tǒng)一組。邏輯頁(yè)號(hào)邏輯頁(yè)號(hào)頁(yè)架號(hào)頁(yè)架號(hào)pfl =4第29頁(yè)/共62頁(yè)6.3.2 分頁(yè)式存儲(chǔ)管理分頁(yè)式存

18、儲(chǔ)管理(Cont.) 地址映射 : (p, d) (f, d) 邏輯地址 (p, d) 物理地址 (f, d) : 由程序確定邏輯地址 (p, d) ; 由 p 查快表得頁(yè)架號(hào) f ; 如查不到： p 與 l 比較，判別是否越界: 不滿足: 0 p l 1 , 越界中斷; 由 p 和 b 查頁(yè)表得 f, (p,f) 快表, 如滿淘汰一個(gè); 轉(zhuǎn) ; f 與 d 合并得物理地址 (f, d) 。第30頁(yè)/共62頁(yè)頁(yè)表長(zhǎng)度寄存器 頁(yè)表首址寄存器lb頁(yè)架號(hào)頁(yè)架號(hào)f邏輔邏輔頁(yè)號(hào)頁(yè)號(hào)0pl-1進(jìn)程標(biāo)識(shí)進(jìn)程標(biāo)識(shí)pid頁(yè)表長(zhǎng)度頁(yè)表長(zhǎng)度 l頁(yè)表首址頁(yè)表首址 b頁(yè) 表進(jìn)程控制塊PCB邏輯頁(yè)號(hào)邏輯頁(yè)號(hào)頁(yè)架號(hào)頁(yè)架號(hào)p

19、f 快表TLBdp頁(yè)內(nèi)地址頁(yè)內(nèi)地址頁(yè)號(hào)頁(yè)號(hào) 邏輯地址df頁(yè)內(nèi)地址頁(yè)內(nèi)地址頁(yè)架號(hào)頁(yè)架號(hào)物理地址頁(yè)式存儲(chǔ)管理地址映射快表未查到 p6.3.2 分頁(yè)式存儲(chǔ)管理分頁(yè)式存儲(chǔ)管理(Cont.)第31頁(yè)/共62頁(yè)頁(yè)表長(zhǎng)度寄存器 頁(yè)表首址寄存器lb頁(yè)架號(hào)頁(yè)架號(hào)f0邏輯邏輯頁(yè)號(hào)頁(yè)號(hào)l-1p頁(yè) 表進(jìn)程控制塊PCB邏輯頁(yè)號(hào)邏輯頁(yè)號(hào)頁(yè)架號(hào)頁(yè)架號(hào)pf 快表TLBdp頁(yè)內(nèi)地址頁(yè)內(nèi)地址頁(yè)號(hào)頁(yè)號(hào) 邏輯地址df頁(yè)內(nèi)地址頁(yè)內(nèi)地址頁(yè)架號(hào)頁(yè)架號(hào)物理地址Cmp p:lb+p頁(yè)式存儲(chǔ)管理地址映射fp6.3.2 分頁(yè)式存儲(chǔ)管理分頁(yè)式存儲(chǔ)管理(Cont.)進(jìn)程標(biāo)識(shí)進(jìn)程標(biāo)識(shí)pid頁(yè)表長(zhǎng)度頁(yè)表長(zhǎng)度 l頁(yè)表首址頁(yè)表首址 b第32頁(yè)/共62頁(yè)6.3

20、.2 分頁(yè)式存儲(chǔ)管理分頁(yè)式存儲(chǔ)管理(Cont.)EAT = 快表命中率(快表訪問(wèn)時(shí)間+內(nèi)存訪問(wèn)時(shí)間)+ 快表不中率快表不中率(快表訪問(wèn)時(shí)間快表訪問(wèn)時(shí)間+2內(nèi)存訪問(wèn)時(shí)間內(nèi)存訪問(wèn)時(shí)間) ns 例：快表命中率例：快表命中率98，快表訪問(wèn)時(shí)間，快表訪問(wèn)時(shí)間20ns， 內(nèi)存一次訪問(wèn)時(shí)間內(nèi)存一次訪問(wèn)時(shí)間100ns，則，則 EAT = 98 (20+100)+2 (20+200) = 122 ns第33頁(yè)/共62頁(yè)6.3.2 分頁(yè)式存儲(chǔ)管理分頁(yè)式存儲(chǔ)管理(Cont.)第34頁(yè)/共62頁(yè)6.3.2 分頁(yè)式存儲(chǔ)管理分頁(yè)式存儲(chǔ)管理(Cont.)01102320951023094985120102301023010

21、232095102309498512Outer-pagetablePage tableMemory外頁(yè)表對(duì)應(yīng)hole的表項(xiàng)沒(méi)有對(duì)應(yīng)的內(nèi)頁(yè)表，訪問(wèn)hole表項(xiàng)動(dòng)態(tài)建立內(nèi)頁(yè)表二級(jí)頁(yè)表第35頁(yè)/共62頁(yè)6.3.2 分頁(yè)式存儲(chǔ)管理分頁(yè)式存儲(chǔ)管理(Cont.)二級(jí)頁(yè)表的地址映射: pipjdn Logical address structure :10 bits10 bits12 bitsPage offsetPi : outer page table index ;Pj : page table displacement .Page numbern address translation scheme

22、 :p1p2dLogical address.Outer-pagetablep1.fPage tablep2.Physicaladdressmemoryd第36頁(yè)/共62頁(yè)6.3.2 分頁(yè)式存儲(chǔ)管理分頁(yè)式存儲(chǔ)管理(Cont.) 采用二級(jí)頁(yè)表結(jié)構(gòu)時(shí), 邏輯地址由外層頁(yè)號(hào)pi, 外層頁(yè)內(nèi)地址pj, 頁(yè)內(nèi)地址d三部分構(gòu)成。若給定一個(gè)邏輯地址空間的地址為A, 系統(tǒng)頁(yè)面大小為L(zhǎng), 頁(yè)表項(xiàng)的長(zhǎng)度為N, 則pi, pj和d的計(jì)算公式如下： pi = int int A/L / N pj = int A/L mod N d = A mod L 對(duì)前述二級(jí)頁(yè)表結(jié)構(gòu), L=212, N=210第37頁(yè)/共62頁(yè)6

23、.3.2 分頁(yè)式存儲(chǔ)管理分頁(yè)式存儲(chǔ)管理(Cont.)4級(jí)頁(yè)表有效訪問(wèn)時(shí)間級(jí)頁(yè)表有效訪問(wèn)時(shí)間n EAT=快表命中率快表命中率 (快表訪問(wèn)時(shí)間快表訪問(wèn)時(shí)間+內(nèi)存訪問(wèn)時(shí)間內(nèi)存訪問(wèn)時(shí)間)+ 快表不中率快表不中率 (快表訪問(wèn)時(shí)間快表訪問(wèn)時(shí)間+5 內(nèi)存訪問(wèn)時(shí)間內(nèi)存訪問(wèn)時(shí)間) ns例例4級(jí)頁(yè)表級(jí)頁(yè)表: 快表命中率快表命中率98，快表訪問(wèn)時(shí)間，快表訪問(wèn)時(shí)間20ns， 內(nèi)存訪問(wèn)時(shí)間內(nèi)存訪問(wèn)時(shí)間100ns，則，則 EAT = 98% (20+100)+2% (20+500)ns =128ns第38頁(yè)/共62頁(yè)inverted page table第39頁(yè)/共62頁(yè)6.3.2.3 反置頁(yè)表反置頁(yè)表(Cont.)反置

24、頁(yè)表工作原理反置頁(yè)表工作原理 : pidpd邏輯地址pidp程序0ffd物理地址反置頁(yè)表d f個(gè)頁(yè)架d物理內(nèi)存第40頁(yè)/共62頁(yè)6.3.2.3 反置頁(yè)表反置頁(yè)表(Cont.)第41頁(yè)/共62頁(yè)6.3.3 分段式存儲(chǔ)管理分段式存儲(chǔ)管理 segmentation6.3.2.1 基本原理 內(nèi)存空間劃分: n動(dòng)態(tài)劃分成異長(zhǎng)區(qū)域，每個(gè)區(qū)域稱作一個(gè)動(dòng)態(tài)劃分成異長(zhǎng)區(qū)域，每個(gè)區(qū)域稱作一個(gè)物理段物理段;n物理段物理段: 段首址段首址, 段內(nèi)地址段內(nèi)地址(由由0開(kāi)始編址開(kāi)始編址) ;n物理地址物理地址: 段首址段首址+段內(nèi)地址段內(nèi)地址 (一維地址一維地址);段號(hào)段號(hào)段內(nèi)地址段內(nèi)地址 進(jìn)程空間劃分:n靜態(tài)劃分成異長(zhǎng)

25、區(qū)域，每個(gè)區(qū)域稱作一個(gè)靜態(tài)劃分成異長(zhǎng)區(qū)域，每個(gè)區(qū)域稱作一個(gè)邏輯段邏輯段 ;n邏輯段邏輯段: 程序單位程序單位, 如主程序如主程序, 子程序子程序, 數(shù)據(jù)區(qū)數(shù)據(jù)區(qū), 模塊模塊 ;n段號(hào)段號(hào): 每個(gè)進(jìn)程有多個(gè)邏輯段，從每個(gè)進(jìn)程有多個(gè)邏輯段，從0開(kāi)始依次編號(hào)開(kāi)始依次編號(hào) ;n邏輯段的段內(nèi)地址從邏輯段的段內(nèi)地址從0開(kāi)始編址開(kāi)始編址 ;n邏輯地址邏輯地址: (二維地址二維地址)第42頁(yè)/共62頁(yè)6.3.3 分段式存儲(chǔ)管理分段式存儲(chǔ)管理(Cont.)占用占用空閑空閑占用占用空閑空閑占用占用空閑空閑占用占用140 KB100 KB130 KB60 KB20 KB50 KB 0 KB內(nèi)存空間劃分調(diào)用X段入口E

26、.訪問(wèn)DATA段A單元調(diào)用Y段入口F主程序段: main段號(hào)=0 050KB-1. F: 子程序段: Y段號(hào)=2 030KB-1 E： 子程序段: X段號(hào)=3 040KB-1 A: 子程序段: DATA段號(hào)=1 030KB-1進(jìn)程空間第43頁(yè)/共62頁(yè)6.3.3 分段式存儲(chǔ)管理分段式存儲(chǔ)管理(Cont.) 進(jìn)程空間與內(nèi)存空間對(duì)應(yīng)關(guān)系: 進(jìn)程P段main段號(hào)=0進(jìn)程P段data段號(hào)=1進(jìn)程P段Y段號(hào)=2進(jìn)程P段X段號(hào)=3 050KB-1 0 0 030KB-140KB-130KB-1120 KB390 KB480 KB810 KB50 KB30 KB30 KB40 KB120 KB220 KB6

27、0 KB300 KB第44頁(yè)/共62頁(yè)6.3.3 分段式存儲(chǔ)管理分段式存儲(chǔ)管理(Cont.) 所需表目: 段表: 每個(gè)進(jìn)程一個(gè)。段號(hào)段號(hào)段首址段首址段長(zhǎng)段長(zhǎng)0120 KB50 KB1 390 KB30 KB2 480 KB30 KB3 810 KB40 KB 空閑表: 系統(tǒng)一個(gè) array of (addr,size)首地址首地址長(zhǎng)度長(zhǎng)度 0 KB120 KB 170 KB220 KB 420 KB 60 KB 510 KB300 KB第45頁(yè)/共62頁(yè)6.3.3 分段式存儲(chǔ)管理分段式存儲(chǔ)管理(Cont.) 所需寄存器: 段表首址寄存器一個(gè) : 段表長(zhǎng)度寄存器一個(gè): 快表: 系統(tǒng)一組bl段號(hào)段

28、號(hào)段首址段首址段長(zhǎng)度段長(zhǎng)度sbl第46頁(yè)/共62頁(yè)邏輯地址 (s, d) 物理地址 (b+ d) : 由程序確定邏輯地址 (s, d) ; 由 s 查快表得 b和 l ;如查不到： s 與 l 比較，判別是否越界: 不滿足: 0 s l 1 , 越界中斷; 由 s 和 b 查段表得 b和 l , (s,b,l)快表, 如快表滿淘汰一個(gè)； 轉(zhuǎn) ; d 與 l 比較, 不滿足: 0dl-1 , 越界 ; b+d 得物理地址。6.3.3 分段式存儲(chǔ)管理分段式存儲(chǔ)管理(Cont.) 地址映射: : (s, d) ( b + d ) 第47頁(yè)/共62頁(yè)6.3.3 分段式存儲(chǔ)管理分段式存儲(chǔ)管理(Cont.

29、)段首址段首址段長(zhǎng)段長(zhǎng)bl段號(hào)段號(hào)0sl-1進(jìn)程標(biāo)識(shí)進(jìn)程標(biāo)識(shí)pid段表長(zhǎng)度段表長(zhǎng)度 l段表首址段表首址 b段 表進(jìn)程控制塊PCB段號(hào)段號(hào)段首址段首址段長(zhǎng)段長(zhǎng)sbl 快表TLB段式存儲(chǔ)管理地址映射偏移偏移段號(hào)段號(hào) 邏輯地址dscmp物理地址b+d+段表長(zhǎng)度reg段表首址regbl若快表查不到s第48頁(yè)/共62頁(yè)6.3.3 分段式存儲(chǔ)管理分段式存儲(chǔ)管理(Cont.)段首址段首址段長(zhǎng)段長(zhǎng)bl段號(hào)段號(hào)0sl-1進(jìn)程標(biāo)識(shí)進(jìn)程標(biāo)識(shí)pid段表長(zhǎng)度段表長(zhǎng)度 l段表首址段表首址 b段 表進(jìn)程控制塊PCB段號(hào)段號(hào)段首址段首址段長(zhǎng)段長(zhǎng)sbl 快表TLB段式存儲(chǔ)管理地址映射sbl偏移偏移段號(hào)段號(hào) 邏輯地址dscmp物

30、理地址b+d+段表長(zhǎng)度reg段表首址regbl+cmp第49頁(yè)/共62頁(yè)6.3.3 分段式存儲(chǔ)管理分段式存儲(chǔ)管理(Cont.) 6.3.2.2 段的共享與保護(hù) 段的共享: 不同進(jìn)程的段號(hào)Spi和Spj對(duì)應(yīng)同一個(gè)段的段首址 和段長(zhǎng)即可實(shí)現(xiàn)不同進(jìn)程對(duì)段的共享。段首址段首址段長(zhǎng)度段長(zhǎng)度blP1段表si段號(hào)段首址段首址段長(zhǎng)度段長(zhǎng)度blP2段表sj段號(hào)共享段共享段b:l內(nèi)存空間第50頁(yè)/共62頁(yè)6.3.3 分段式存儲(chǔ)管理分段式存儲(chǔ)管理(Cont.)共享段表: 系統(tǒng)1個(gè), 記錄所有共享段。main1子程序子程序X子程序子程序Ydatamain2data子程序子程序Y子程序子程序X段長(zhǎng)度段長(zhǎng)度 首址首址P1

31、0段號(hào)P21234段長(zhǎng)度段長(zhǎng)度 首址首址0段號(hào)123段 表段名段名共享共享計(jì)數(shù)計(jì)數(shù)段長(zhǎng)度段長(zhǎng)度 段首址段首址其其它它X2Y2data2共享段表main1XDataYmain2主 存第51頁(yè)/共62頁(yè)6.3.3 分段式存儲(chǔ)管理分段式存儲(chǔ)管理(Cont.) 段的保護(hù): 不同進(jìn)程對(duì)共享段的訪問(wèn)權(quán)限不同， 需要在段表中加上訪問(wèn)權(quán)限。段首址段首址段長(zhǎng)度段長(zhǎng)度訪問(wèn)權(quán)限訪問(wèn)權(quán)限RWEbl101段表的改進(jìn)s段號(hào)段號(hào)段號(hào)段首址段首址 段長(zhǎng)度段長(zhǎng)度訪問(wèn)權(quán)限訪問(wèn)權(quán)限RWEsbl101快表的改進(jìn)第52頁(yè)/共62頁(yè)頁(yè)式管理頁(yè)式管理段式管理段式管理一維地址空間一維地址空間二維地址空間二維地址空間頁(yè)是物理單位頁(yè)是物理單位段

32、是邏輯單位段是邏輯單位頁(yè)的大小固定頁(yè)的大小固定段的大小可變段的大小可變對(duì)用戶透明對(duì)用戶透明對(duì)用戶可見(jiàn)對(duì)用戶可見(jiàn)無(wú)碎片無(wú)碎片有碎片有碎片通常不共享通常不共享便于共享、保護(hù)便于共享、保護(hù)頁(yè)式管理和段式管理的比較:6.3.3 分段式存儲(chǔ)管理分段式存儲(chǔ)管理(Cont.)第53頁(yè)/共62頁(yè)6.3.4 段頁(yè)式存儲(chǔ)管理段頁(yè)式存儲(chǔ)管理segmentation with paging第54頁(yè)/共62頁(yè)6.3.4 段頁(yè)式存儲(chǔ)管理段頁(yè)式存儲(chǔ)管理(Cont.)6.3.4.1 基本原理 內(nèi)存空間劃分: (同頁(yè)式) 靜態(tài)等長(zhǎng), 2i, 稱為一頁(yè)架 ; 物理地址 = = (f,d)。頁(yè)內(nèi)地址頁(yè)內(nèi)地址頁(yè)架號(hào)頁(yè)架號(hào)n-i 位i 位 進(jìn)程空間劃分: 一個(gè)進(jìn)程若干個(gè)段; 一個(gè)段若干個(gè)頁(yè); 邏輯地址= =(s,p,d)。段號(hào)段號(hào)頁(yè)內(nèi)地址頁(yè)內(nèi)地址邏輯頁(yè)號(hào)邏輯頁(yè)號(hào)i 位j 位n-i-j 位第55頁(yè)/共62頁(yè) 進(jìn)程空間與內(nèi)存空間對(duì)應(yīng)關(guān)系: 6.3.4 段頁(yè)式存儲(chǔ)管理段頁(yè)式存儲(chǔ)管理(Cont.)第第 0 頁(yè)頁(yè)第第 1 頁(yè)頁(yè)第第 2 頁(yè)頁(yè)第第 0 頁(yè)頁(yè)第第 1 頁(yè)頁(yè)第第 2 頁(yè)頁(yè)第第 0 頁(yè)頁(yè)第第 1 頁(yè)