存儲管理存儲管理功能內(nèi)存資源管理存儲管理方式外存空間管理虛擬存儲系統(tǒng).ppt

第六章 存儲管理,存儲管理功能 內(nèi)存資源管理 存儲管理方式 外存空間管理 虛擬存儲系統(tǒng),6.1 存儲管理功能,存儲分配和去配 分配去配對象 內(nèi)存、外存(相同方法) 分配去配時刻 進(jìn)程創(chuàng)建、撤銷、交換、長度變化(棧溢出, execl) 存儲共享 目的：節(jié)省內(nèi)存、相互通訊 內(nèi)容：代碼、數(shù)據(jù) 存儲保護(hù) 防止地址越界 防止操作越權(quán),6.1 存儲管理功能(Cont.),存儲擴(kuò)充 內(nèi)存、外存結(jié)合，虛擬存儲體系 速度接近內(nèi)存，容量相當(dāng)外存 地址映射 邏輯地址=物理地址 硬件支持 基址寄存器(base)、限長寄存器(limit)、快表； 使用上述寄存器完成地址映射過程； 不能正常完成地址映射時產(chǎn)生中斷。,6.2 內(nèi)存資源管理,6.2.1 內(nèi)存分區(qū) 分區(qū)時刻 靜態(tài)分區(qū)：系統(tǒng)初始化時分； 動態(tài)分區(qū)：申請時分。 分區(qū)大小 等長分區(qū)：2i 異長分區(qū)：依程序、程序單位、對象大小。 通常作法 靜態(tài)+等長（頁式、段頁式） 動態(tài)+異長（段式、界地址）,6.2.2 內(nèi)存分配,靜態(tài)等長分區(qū)的分配 字位映象圖 空閑頁面表 空閑頁面鏈 動態(tài)異長分區(qū)的分配 最先適應(yīng) (First Fit) 最佳適應(yīng) (Best Fit) 最壞適應(yīng) (Worst Fit),位示圖（bit map）,第0 頁,第2 頁,第1 頁,第 k 頁,第 n 頁,.,.,分配：自頭尋找第一個為0的位，改為1，返回頁號； 去配：頁號對應(yīng)的位(bit)置為0。,用一個bit代表一頁狀態(tài)，0表空閑，1表占用。（ 多單元）,空閑頁面表,特點：可以分配連續(xù)頁面。 DMA 要求,占用,占用,120頁,121頁,122頁,123頁,.,.,空閑頁面鏈,占用,占用,占用,Head:,優(yōu)點：節(jié)省空間。 （不適合管理外存）,動態(tài)異長分區(qū)的分配,數(shù)據(jù)結(jié)構(gòu)：,Criteria: 盡量使空閑區(qū)域連續(xù)。,初始時一個連續(xù)空閑區(qū)。 長度=0為表尾。,最先適應(yīng)算法（First Fit）,空閑區(qū)：首址遞增排列； 申請：取第一個可滿足區(qū)域； 優(yōu)點：盡量使用低地址空間， 高區(qū)保持大空閑區(qū)域。 缺點：可能分割大空閑區(qū)。 Eg. 申請32將分割第 一個區(qū)域。,最佳適應(yīng)算法（Best Fit）,空閑區(qū)：首址遞增排列； 申請：取最小可滿足區(qū)域； 優(yōu)點：盡量使用小空閑區(qū)， 保持大空閑區(qū)。 缺點：可能形成碎片 (fragment)。 Eg. 申請30將留下長 度為2的空閑區(qū)。,最壞適應(yīng)算法（Worst Fit）,空閑區(qū)：首址遞增排列； 申請：取最大可滿足區(qū)域； 優(yōu)點：防止形成碎片。 缺點：分割大空閑區(qū)域。,UNIX存儲分配-FF,struct map char *m_size; char *m_addr; ; struct map coremapCMAPSIZ; struct map swapmapSMAPSIZ; define CMAPSIZ 100 define SMAPSIZ 100,malloc(mp,size) 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) do bp+; (bp-1)-m_addr = bp-m_addr; while(bp-1)-m_size = bp-m_size); return(a); return(0); ,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(bpmp ,else if (a+size = bp-m_addr ,6.2.3 碎片處理,緊湊：移動占用區(qū)域，使所有空閑區(qū)域連成一片（開銷很大）。,OS,P1(248k),P2(250k),8k,6k,4k,256k:,512k:,768k:,264k:,518k:,256k:,504k:,754k:,18k,6.3 存儲管理方式,界地址管理方式（一維地址） 頁式管理方式（一維地址） 段式管理方式（二維地址） 段頁式管理方式（二維地址）,6.3.1 界地址管理方式,4.3.1.1 基本原理 1. 內(nèi)存空間劃分：動態(tài)異長； 2. 進(jìn)程空間劃分：一個進(jìn)程一個區(qū)域，邏輯地址0l-1 3. 進(jìn)程空間與內(nèi)存空間對應(yīng)關(guān)系（可以浮動）：,0:,l-1:,.,.,b:,l,b+l-1:,進(jìn)程空間,內(nèi)存空間,6.3.1 界地址管理方式,4. 所需表目： (1)內(nèi)存分配表-在PCB中； (2)空閑區(qū)域表：array of (addr,size)。 5. 所需寄存器： (1)基址寄存器b: 保存運行進(jìn)程起始地址； (2)限長寄存器l: 保存運行進(jìn)程長度。 6. 地址映射：,6.3.1 界地址管理方式,0:,l-1:,.,.,b:,l,b+l-1:,l,b,邏輯地址,CP,+,a,b+a,步驟：(1) 由程序確定邏輯地址a； (2) a與l比較判斷是否越界， 不滿足：0al-1，越界； (3) a與b相加得到物理地址。,進(jìn)程空間,內(nèi)存空間,6.3.1 界地址管理方式,6.3.1.2 雙對界 代碼(I空間)：一對界 數(shù)據(jù)(D空間)：一對界 6.3.1.3 交換技術(shù)(swapping) 例：UNIX 交換進(jìn)程sched (#0) 交換原則：外存 SRUN 狀態(tài)進(jìn)程內(nèi)存 (1)內(nèi)存有空間，直接移入； (2)內(nèi)存空間不夠，移出SWAIT, SSTOP狀態(tài)進(jìn)程； (3)如果還不夠，移出SSLEEP, SRUN狀態(tài)進(jìn)程， 條件：在外時間3秒；在內(nèi)時間2秒。,6.3.1 界地址管理方式,覆蓋技術(shù): 將較大程序裝入較小進(jìn)程空間的技術(shù). 只將全局代碼和數(shù)據(jù)靜態(tài)裝入內(nèi)存, 其它部分動態(tài)裝入. 后裝入的成分重復(fù)使用先裝入成分所使用的存儲區(qū), 即覆蓋先裝入的成分.,覆蓋技術(shù),符號表 公共例程 覆蓋驅(qū)動程序 覆蓋區(qū)50kb,Pass1 30kb,Pass2 50kb,Pass3 40kb,Pass4 25kb,6.3.2 分頁式存儲管理(paging),6.3.2.1 基本原理 1. 內(nèi)存空間劃分：靜態(tài)等長，2i, 稱為一個頁框（frame)。,.,.,第0頁,第1頁,第k頁,第2n-i-1頁,2i,02i:,12i:,k2i:,(2n-i-1)2i:,物理地址=頁架首址+頁內(nèi)地址 =頁架號 2i +頁內(nèi)地址 =,i位,n-i位,6.3.2 分頁式存儲管理,2. 進(jìn)程空間劃分：靜態(tài)等長，2i, 稱為一個頁面。,.,.,第0頁,第1頁,第k頁,第l-1頁,2i,02i:,12i:,k2i:,(l-1)2i:,邏輯地址=邏輯頁首址+頁內(nèi)地址 =邏輯頁號 2i +頁內(nèi)地址 =,i位,3. 進(jìn)程空間與內(nèi)存空間對應(yīng)關(guān)系,.,第0頁,第1頁,第2頁,第3頁,第16頁,第22頁,第32頁,第15頁,.,.,.,進(jìn)程空間,內(nèi)存空間,4. 所需表目：,(1)頁表，每個進(jìn)程一個,物理頁號,邏輯頁號:,15,22,16,32,0,1,2,3,5. 所需寄存器,(2)總頁表：系統(tǒng)一個,(1) 頁表首址寄存器：,b,l,(2) 頁表長度寄存器：,系統(tǒng)一個,系統(tǒng)一個,(3) 快表(TLB)：系統(tǒng)一組：,邏輯頁號,頁架號,.,.,.,.,f,p,邏輯地址(p,d)物理地址(f,d) (1) 由程序確定邏輯地址(p,d)； (2) 由p查快表得頁架號f； 如查不到： (3) 由p與l比較，判別是否越界： 不滿足：0pl-1，越界； (4) 由p和b查頁表得f; (5) parbegin (p,f)快表，如滿淘汰一個; f與d合并得物理地址 parend (3) f與d合并得物理地址,6. 地址映射 : (p,d)(f,d),.,邏輯頁號,頁架號,.,.,.,.,f,p,l,b,b,l,.,.,PCB,頁架號,邏輯頁號,.,f,.,p,.,f d,物理地址,邏輯地址,b:,.,如查不到,.,邏輯頁號,頁架號,.,.,.,.,f,p,l,b,b,l,.,.,PCB,頁架號,邏輯頁號,.,f,.,p,.,f d,+,cp,p f,物理地址,邏輯地址,b:,.,有效訪問時間,(Effective Access Time) EAT=快表命中率(快表訪問時間+內(nèi)存訪問時間)+快表不中率(快表訪問時間+2 內(nèi)存訪問時間) ns 98%(20+100)+2% (20+200)ns =122ns,6.3.2.2 多級頁表,提出背景 內(nèi)存空間成倍增長, 進(jìn)程虛擬空間成倍增加 單級頁表需要很大連續(xù)內(nèi)存空間 例如 32位進(jìn)程地址空間，頁長占12位（4k），頁號20位，頁表最多可達(dá)220個入口！ 多線程設(shè)計導(dǎo)致進(jìn)程虛擬空間不連續(xù)(空洞hole) 棧的預(yù)留空間(沒有頁架相對應(yīng)) 頁表所占內(nèi)存空間浪費 解決策略 二級或多級頁表,Two-Level Page-Table Scheme,外頁表對應(yīng)hole的表項沒有對應(yīng)的內(nèi)頁表 訪問hole表項動態(tài)建立內(nèi)頁表,Two-Level Paging Example,A logical address (on 32-bit machine with 4K page size) is divided into: a page number consisting of 20 bits. a page offset consisting of 12 bits. Since the page table is paged, the page number is further divided into: a 10-bit page number. a 10-bit page offset. Thus, a logical address is as follows: where pi is an index into the outer page table, and pj is the displacement within the page table.,Address-Translation Scheme,Address-translation scheme for a two-level 32-bit paging architecture,Even though time needed for one memory access is quintupled, caching permits performance to remain reasonable,4級頁表有效訪問時間,EAT=快表命中率(快表訪問時間+內(nèi)存訪問時間)+快表不中率(快表訪問時間+5 內(nèi)存訪問時間) ns 98%(20+100)+2% (20+500)ns =128ns,6.3.2.3 反置頁表(inverted page table),傳統(tǒng)頁表面向進(jìn)程空間 每個進(jìn)程邏輯頁面有一表項 當(dāng)進(jìn)程空間很大時，頁表很大 反置頁表面向內(nèi)存空間 每個內(nèi)存頁架一個表項 大小固定,反置頁表-工作原理,程序,物理 內(nèi)存,f d,pid p d,f,邏輯地址,物理地址,反置頁表,速度問題,反置頁表查找 由表頭起始，平均為表長度的一半 速度慢 解決方案 在反置頁表前增加一級雜湊表 查找雜湊表與反置頁表至少需要兩次訪問內(nèi)存 為進(jìn)一步提高速度，快表緩沖,1. 內(nèi)存空間劃分：動態(tài)異長，每區(qū)一段。,段首址+段內(nèi)地址,物理地址=,6.3.3 分段式存儲管理(segmentation),2. 進(jìn)程空間劃分：若干段，每段一個程序單位。,調(diào)用x段e,f: 訪問d段a,e: 調(diào)用y段f,main(段號0),X(段號1),Y(段號2),D(段號3),a:,0 80k-1,0 . 40k-1,0 20k-1,0 60k-1,邏輯地址=,段號 段內(nèi)地址,(二維地址),main,x,y,d,3. 對應(yīng)關(guān)系,40k,60k,80k,20k,.,.,.,.,進(jìn)程空間,內(nèi)存空間,100k:,200k:,300k:,320k:,4. 所需表目,(1) 段表：每進(jìn)程一個,段首址,段長度,100k,40k,80k,60k,段號,0: 1: 2: 3:,20k,200k,320k,300k,(2) 空閑表：系統(tǒng)一個 array of (addr,size),5. 所需寄存器,(1) 段表首址寄存器：,b,l,(2) 段表長度寄存器：,系統(tǒng)一個,系統(tǒng)一個,(3) 快表(TLB)：系統(tǒng)一組：,6. 地址映射 : (s,d)(b+d) 邏輯地址(s,d)物理地址(b+d) (1)由程序確定邏輯地址(s,d); (2) 由s查快表得b和l 如查不到： (3) 由s與l比較判斷是否越界 不滿足：0sl-1，越界； (4) 由s和b查段表，得b和l (5) 由d與l比較，判斷是否越界 不滿足：0dl-1，越界; (6) parbegin (s,b,l)快表, 如快表滿淘汰一個； 由bd得物理地址 parend (3) 由d與l比較，判斷是否越界 不滿足：0dl-1，越界； (4) 由bd得物理地址。,段號,段長 段首址,., ., .,.,l b,s,l,b,b,l,.,.,PCB,段首址 段長,段號, ,b l,.,s,., ,+,b:,若查不到,段號,段長 段首址,., ., .,.,l b,s,l,b,b,l,.,.,PCB,段首址 段長,段號, .,b l,.,s,., .,s l b,b:,+,cp,+,6.3.3.2 段的共享,段長 段首址, .,l b,. .,段號 si .,P1段表：,段長 段首址, .,l b,. .,段號 sj .,P2段表：,共享段,.,.,b:,l,內(nèi)存空間,如何實現(xiàn)？ 共享段表,段名 共享記數(shù) 段長 段首址 其它, .,vi 3 35k 125k ?, ,共享段表：,進(jìn)程段表(n)共享段表(1)共享段(1),例子：UNIX正文段(text段) struct text int x_daddr; /*disk address int x_caddr; /*core address, if loaded int x_size; /*size(64) int *x_iptr; /*inode pointer char x_count; /*reference count char x_ccount; /*number of loaded reference; textNTEXT; define NTEXT 40,struct proc int *p_textp; /*pointer to text structure; struct user int u_tsize; ,6.3.3.2 段的保護(hù) (1) 段表的改進(jìn)：,段長 段首址, ,l b e 1 0 1,段號 s .,訪問權(quán)限 R W E, ,段號 段長 段首址, ,s l b 1 0 1,訪問權(quán)限 R W E,(2) 快表的改進(jìn)：, ,共享段 表入口,6.3.4 段頁式存儲管理(segmentation with paging),段式優(yōu)于頁式 便于共享和保護(hù) 頁式優(yōu)于段式 消除“碎片”問題 段頁式：結(jié)合二者優(yōu)點 每個進(jìn)程包含若干段 每個段包含若干頁,6.3.4.1 基本原理 1. 內(nèi)存空間劃分：(同頁式) 靜態(tài)等長，2i, 稱為一頁架。 物理地址=(頁架號,頁內(nèi)地址)=(f,d)