操作系統(tǒng)第六章存儲(chǔ)管理

1、第六章第六章 存儲(chǔ)管理存儲(chǔ)管理n存儲(chǔ)管理功能存儲(chǔ)管理功能n內(nèi)存資源管理內(nèi)存資源管理n存儲(chǔ)管理方式存儲(chǔ)管理方式n外存空間管理外存空間管理n虛擬存儲(chǔ)系統(tǒng)虛擬存儲(chǔ)系統(tǒng) 6.1 存儲(chǔ)管理功能存儲(chǔ)管理功能n存儲(chǔ)分配和去配存儲(chǔ)分配和去配n分配去配對(duì)象分配去配對(duì)象n內(nèi)存、外存內(nèi)存、外存(相同方法相同方法)n分配去配時(shí)刻分配去配時(shí)刻n進(jìn)程創(chuàng)建、撤銷、交換、長(zhǎng)度變化進(jìn)程創(chuàng)建、撤銷、交換、長(zhǎng)度變化(棧溢出棧溢出, execl)n存儲(chǔ)共享存儲(chǔ)共享n目的：節(jié)省內(nèi)存、相互通訊目的：節(jié)省內(nèi)存、相互通訊n內(nèi)容：代碼、數(shù)據(jù)內(nèi)容：代碼、數(shù)據(jù)n存儲(chǔ)保護(hù)存儲(chǔ)保護(hù)n防止地址越界防止地址越界n防止操作越權(quán)防止操作越權(quán)6.1 存儲(chǔ)管理功

2、能存儲(chǔ)管理功能(cont.)n存儲(chǔ)擴(kuò)充存儲(chǔ)擴(kuò)充n內(nèi)存、外存結(jié)合，虛擬存儲(chǔ)體系內(nèi)存、外存結(jié)合，虛擬存儲(chǔ)體系n速度接近內(nèi)存，容量相當(dāng)外存速度接近內(nèi)存，容量相當(dāng)外存n地址映射地址映射n邏輯地址邏輯地址=物理地址物理地址n硬件支持硬件支持n基址寄存器基址寄存器(base)、限長(zhǎng)寄存器、限長(zhǎng)寄存器(limit)、快表；、快表；n使用上述寄存器完成地址映射過程；使用上述寄存器完成地址映射過程；n不能正常完成地址映射時(shí)產(chǎn)生中斷。不能正常完成地址映射時(shí)產(chǎn)生中斷。6.2 內(nèi)存資源管理內(nèi)存資源管理n6.2.1 內(nèi)存分區(qū)內(nèi)存分區(qū)n分區(qū)時(shí)刻分區(qū)時(shí)刻n靜態(tài)分區(qū)：系統(tǒng)初始化時(shí)分；靜態(tài)分區(qū)：系統(tǒng)初始化時(shí)分；n動(dòng)態(tài)分區(qū)：申請(qǐng)

3、時(shí)分。動(dòng)態(tài)分區(qū)：申請(qǐng)時(shí)分。n分區(qū)大小分區(qū)大小n等長(zhǎng)分區(qū)：等長(zhǎng)分區(qū)：2in異長(zhǎng)分區(qū)：依程序、程序單位、對(duì)象大小。異長(zhǎng)分區(qū)：依程序、程序單位、對(duì)象大小。n通常作法通常作法n靜態(tài)靜態(tài)+等長(zhǎng)（頁式、段頁式）等長(zhǎng)（頁式、段頁式）n動(dòng)態(tài)動(dòng)態(tài)+異長(zhǎng)（段式、界地址）異長(zhǎng)（段式、界地址）6.2.2 內(nèi)存分配內(nèi)存分配n 靜態(tài)等長(zhǎng)分區(qū)的分配靜態(tài)等長(zhǎng)分區(qū)的分配n 字位映象圖字位映象圖n 空閑頁面表空閑頁面表n 空閑頁面鏈空閑頁面鏈n動(dòng)態(tài)異長(zhǎng)分區(qū)的分配動(dòng)態(tài)異長(zhǎng)分區(qū)的分配n最先適應(yīng)最先適應(yīng) (first fit)n最佳適應(yīng)最佳適應(yīng) (best fit)n最壞適應(yīng)最壞適應(yīng) (worst fit)位示圖（位示圖（bit ma

4、p）1 0 0 1 . 1 0第第0 頁頁第第2 頁頁第第1 頁頁第第 k 頁頁第第 n 頁頁.分配：自頭尋找第一個(gè)為分配：自頭尋找第一個(gè)為0的位，改為的位，改為1，返回頁號(hào)；，返回頁號(hào)；去配：頁號(hào)對(duì)應(yīng)的位去配：頁號(hào)對(duì)應(yīng)的位(bit)置為置為0。用一個(gè)用一個(gè)bit代表一頁狀態(tài)，代表一頁狀態(tài)，0表空閑，表空閑，1表占用。（表占用。（ 多單元）多單元）空閑頁面表空閑頁面表首頁號(hào)首頁號(hào)空頁數(shù)空頁數(shù).1204特點(diǎn)：可以分配連續(xù)頁面。特點(diǎn)：可以分配連續(xù)頁面。 dma 要求要求占用占用占用占用120頁頁121頁頁122頁頁123頁頁 . .空閑頁面鏈空閑頁面鏈占用占用占用占用占用占用head:優(yōu)點(diǎn)：節(jié)省空

5、間。優(yōu)點(diǎn)：節(jié)省空間。 （不適合管理外存）（不適合管理外存）動(dòng)態(tài)異長(zhǎng)分區(qū)的分配動(dòng)態(tài)異長(zhǎng)分區(qū)的分配空閑區(qū)首址空閑區(qū)首址空閑區(qū)長(zhǎng)度空閑區(qū)長(zhǎng)度.25001500數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)：criteria: 盡量使空閑區(qū)域連續(xù)。盡量使空閑區(qū)域連續(xù)。初始時(shí)一個(gè)連續(xù)空閑區(qū)。初始時(shí)一個(gè)連續(xù)空閑區(qū)。長(zhǎng)度長(zhǎng)度=0為表尾。為表尾。最先適應(yīng)算法（最先適應(yīng)算法（first fit）空閑區(qū)首址空閑區(qū)首址空閑區(qū)長(zhǎng)度空閑區(qū)長(zhǎng)度128641024256322560.空閑區(qū)：首址遞增排列；空閑區(qū)：首址遞增排列；申請(qǐng)：取第一個(gè)可滿足區(qū)域；申請(qǐng)：取第一個(gè)可滿足區(qū)域；優(yōu)點(diǎn)：盡量使用低地址空間，優(yōu)點(diǎn)：盡量使用低地址空間， 高區(qū)保持大空閑區(qū)域。

6、高區(qū)保持大空閑區(qū)域。缺點(diǎn)：可能分割大空閑區(qū)。缺點(diǎn)：可能分割大空閑區(qū)。 eg. 申請(qǐng)申請(qǐng)32將分割第將分割第 一個(gè)區(qū)域。一個(gè)區(qū)域。最佳適應(yīng)算法（最佳適應(yīng)算法（best fit）空閑區(qū)：首址遞增排列；空閑區(qū)：首址遞增排列；申請(qǐng)：取最小可滿足區(qū)域；申請(qǐng)：取最小可滿足區(qū)域；優(yōu)點(diǎn)：盡量使用小空閑區(qū)，優(yōu)點(diǎn)：盡量使用小空閑區(qū)， 保持大空閑區(qū)。保持大空閑區(qū)。缺點(diǎn)：可能形成碎片缺點(diǎn)：可能形成碎片 (fragment)。 eg. 申請(qǐng)申請(qǐng)30將留下長(zhǎng)將留下長(zhǎng) 度為度為2的空閑區(qū)。的空閑區(qū)。 空閑區(qū)首址空閑區(qū)首址空閑區(qū)長(zhǎng)度空閑區(qū)長(zhǎng)度128641024256322560.最壞適應(yīng)算法（最壞適應(yīng)算法（worst fit

7、）空閑區(qū)：首址遞增排列；空閑區(qū)：首址遞增排列；申請(qǐng)：取最大可滿足區(qū)域；申請(qǐng)：取最大可滿足區(qū)域；優(yōu)點(diǎn)：防止形成碎片。優(yōu)點(diǎn)：防止形成碎片。缺點(diǎn)：分割大空閑區(qū)域。缺點(diǎn)：分割大空閑區(qū)域?？臻e區(qū)首址空閑區(qū)首址空閑區(qū)長(zhǎng)度空閑區(qū)長(zhǎng)度128641024256322560.unix存儲(chǔ)分配存儲(chǔ)分配-ffstruct map char *m_size; char *m_addr;struct map coremapcmapsiz;struct map swapmapsmapsiz;define cmapsiz 100define smapsiz 100malloc(mp,size)struct map, *mp;

8、 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;

9、register int t,a; a = aa; for(bp=mp; bp-m_addrm_size !=0; bp+); if(bpmp & (bp-1)-m_addr+(bp-1)-m_size = a) /與前合并與前合并 (bp-1)-m_size =+ size; if (a+size = bp-m_addr) /前后合并前后合并 (bp-1)-m_size =+ bp-m_size; while (bp-m_size) bp+; (bp-1)-m_addr = bp-m_addr; (bp-1)-m_size = bp-m_size; else if (a+size =

10、 bp-m_addr & bp-m_size) /與后合與后合并并 bp-m_addr =- size; bp-m_size =+ size; else if (size) do /無合并無合并 t = bp-m_addr; bp-m_addr = a; a = t; /a與與bp-m_addr交換交換 t = bp-m_size; bp-m_size = size; bp+; /size與與bp-m_size交換交換 while (size = t); 6.2.3 碎片處理碎片處理緊湊：移動(dòng)占用區(qū)域，使所有空閑區(qū)域連成一片（開銷很大）。緊湊：移動(dòng)占用區(qū)域，使所有空閑區(qū)域連成一片（開銷

11、很大）。 os p1(248k) p2(250k) 8k 6k 4k256k:512k:768k:264k:518k: p1 os p2256k:504k:754k:18k6.3 存儲(chǔ)管理方式存儲(chǔ)管理方式n界地址管理方式（一維地址）界地址管理方式（一維地址）n頁式管理方式（一維地址）頁式管理方式（一維地址）n段式管理方式（二維地址）段式管理方式（二維地址）n段頁式管理方式（二維地址）段頁式管理方式（二維地址）6.3.1 界地址管理方式界地址管理方式4.3.1.1 基本原理基本原理 1. 內(nèi)存空間劃分：動(dòng)態(tài)異長(zhǎng)；內(nèi)存空間劃分：動(dòng)態(tài)異長(zhǎng)； 2. 進(jìn)程空間劃分：一個(gè)進(jìn)程一個(gè)區(qū)域，邏輯地址進(jìn)程空間劃分

12、：一個(gè)進(jìn)程一個(gè)區(qū)域，邏輯地址0 l-1 3. 進(jìn)程空間與內(nèi)存空間對(duì)應(yīng)關(guān)系（可以浮動(dòng)）：進(jìn)程空間與內(nèi)存空間對(duì)應(yīng)關(guān)系（可以浮動(dòng)）：0:l-1:.b:lb+l-1:進(jìn)程空間進(jìn)程空間內(nèi)存空間內(nèi)存空間6.3.1 界地址管理方式界地址管理方式 4. 所需表目：所需表目： (1)內(nèi)存分配表內(nèi)存分配表-在在pcb中；中； (2)空閑區(qū)域表：空閑區(qū)域表：array of (addr,size)。 5. 所需寄存器：所需寄存器： (1)基址寄存器基址寄存器b: 保存運(yùn)行進(jìn)程起始地址；保存運(yùn)行進(jìn)程起始地址； (2)限長(zhǎng)寄存器限長(zhǎng)寄存器l: 保存運(yùn)行進(jìn)程長(zhǎng)度保存運(yùn)行進(jìn)程長(zhǎng)度。 6. 地址映射：地址映射：6.3.1 界

13、地址管理方式界地址管理方式0:l-1:.b:lb+l-1:lb邏輯地址邏輯地址cp+ab+a步驟：步驟：(1) 由程序確定邏輯地址由程序確定邏輯地址a； (2) a與與l比較判斷是否越界，比較判斷是否越界， 不滿足：不滿足：0 a l-1，越界；，越界； (3) a與與b相加得到物理地址。相加得到物理地址。進(jìn)程空間進(jìn)程空間內(nèi)存空間內(nèi)存空間6.3.1 界地址管理方式界地址管理方式6.3.1.2 雙對(duì)界雙對(duì)界 代碼代碼(i空間空間)：一對(duì)界：一對(duì)界 數(shù)據(jù)數(shù)據(jù)(d空間空間)：一對(duì)界：一對(duì)界6.3.1.3 交換技術(shù)交換技術(shù)(swapping) 例：例：unix 交換進(jìn)程交換進(jìn)程sched (#0) 交

14、換原則：外存交換原則：外存 srun 狀態(tài)進(jìn)程狀態(tài)進(jìn)程內(nèi)存內(nèi)存 (1)內(nèi)存有空間，直接移入；內(nèi)存有空間，直接移入； (2)內(nèi)存空間不夠，移出內(nèi)存空間不夠，移出swait, sstop狀態(tài)進(jìn)程；狀態(tài)進(jìn)程； (3)如果還不夠，移出如果還不夠，移出ssleep, srun狀態(tài)進(jìn)程，狀態(tài)進(jìn)程， 條件：在外時(shí)間條件：在外時(shí)間 3秒；在內(nèi)時(shí)間秒；在內(nèi)時(shí)間 2秒。秒。 b1l1b2l26.3.1 界地址管理方式界地址管理方式n覆蓋技術(shù)覆蓋技術(shù): 將較大程序裝入較小進(jìn)程空間將較大程序裝入較小進(jìn)程空間的技術(shù)的技術(shù).n只將全局代碼和數(shù)據(jù)靜態(tài)裝入內(nèi)存只將全局代碼和數(shù)據(jù)靜態(tài)裝入內(nèi)存, 其它部其它部分動(dòng)態(tài)裝入分動(dòng)態(tài)裝入

15、.n后裝入的成分重復(fù)使用先裝入成分所使用的后裝入的成分重復(fù)使用先裝入成分所使用的存儲(chǔ)區(qū)存儲(chǔ)區(qū), 即覆蓋先裝入的成分即覆蓋先裝入的成分.覆蓋技術(shù)覆蓋技術(shù)符號(hào)表符號(hào)表公共例程公共例程覆蓋驅(qū)動(dòng)程序覆蓋驅(qū)動(dòng)程序覆蓋區(qū)覆蓋區(qū)50kbpass130kbpass250kbpass340kbpass425kb6.3.2 分頁式存儲(chǔ)管理分頁式存儲(chǔ)管理(paging)6.3.2.1 基本原理基本原理 1. 內(nèi)存空間劃分：靜態(tài)等長(zhǎng)，內(nèi)存空間劃分：靜態(tài)等長(zhǎng)，2i, 稱為一個(gè)頁框（稱為一個(gè)頁框（frame)。 .第第0頁頁第第1頁頁第第k頁頁第第2n-i-1頁頁2i0 2i:1 2i:k 2i:(2n-i-1) 2i:

16、物理地址物理地址=頁架首址頁架首址+頁內(nèi)地址頁內(nèi)地址 =頁架號(hào)頁架號(hào) 2i +頁內(nèi)地址頁內(nèi)地址 = 頁架號(hào)頁架號(hào) 頁內(nèi)地址頁內(nèi)地址i位位n-i位位6.3.2 分頁式存儲(chǔ)管理分頁式存儲(chǔ)管理2. 進(jìn)程空間劃分：靜態(tài)等長(zhǎng)，進(jìn)程空間劃分：靜態(tài)等長(zhǎng)，2i, 稱為一個(gè)頁面。稱為一個(gè)頁面。.第第0頁頁第第1頁頁第第k頁頁 第第l-1頁頁2i0 2i:1 2i:k 2i: (l-1) 2i:邏輯地址邏輯地址=邏輯頁首址邏輯頁首址+頁內(nèi)地址頁內(nèi)地址 =邏輯頁號(hào)邏輯頁號(hào) 2i +頁內(nèi)地址頁內(nèi)地址 =邏輯頁號(hào)邏輯頁號(hào) 頁內(nèi)地址頁內(nèi)地址i位位3. 進(jìn)程空間與內(nèi)存空間對(duì)應(yīng)關(guān)系進(jìn)程空間與內(nèi)存空間對(duì)應(yīng)關(guān)系.第第0頁頁第第1

17、頁頁第第2頁頁第第3頁頁第第16頁頁第第22頁頁第第32頁頁第第15頁頁.進(jìn)程空間進(jìn)程空間內(nèi)存空間內(nèi)存空間4. 所需表目：所需表目：(1)頁表，每個(gè)進(jìn)程一個(gè)頁表，每個(gè)進(jìn)程一個(gè)物理頁號(hào)物理頁號(hào)邏輯頁號(hào)邏輯頁號(hào):1522163201235. 所需寄存器所需寄存器(2)總頁表：系統(tǒng)一個(gè)總頁表：系統(tǒng)一個(gè)(1) 頁表首址寄存器：頁表首址寄存器：bl(2) 頁表長(zhǎng)度寄存器：頁表長(zhǎng)度寄存器：系統(tǒng)一個(gè)系統(tǒng)一個(gè)系統(tǒng)一個(gè)系統(tǒng)一個(gè)(3) 快表快表(tlb)：系統(tǒng)一組：系統(tǒng)一組：邏輯頁號(hào)邏輯頁號(hào)頁架號(hào)頁架號(hào).fp邏輯地址邏輯地址(p,d)物理地址物理地址(f,d)(1) 由程序確定邏輯地址由程序確定邏輯地址(p,d)

18、；(2) 由由p查快表得頁架號(hào)查快表得頁架號(hào)f； 如查不到：如查不到： (3) 由由p與與l比較，判別是否越界：比較，判別是否越界： 不滿足：不滿足：0 p l-1，越界；，越界； (4) 由由p和和b查頁表得查頁表得f; (5) parbegin (p,f)快表，如滿淘汰一個(gè)快表，如滿淘汰一個(gè); f與與d合并得物理地址合并得物理地址 parend(3) f與與d合并得物理地址合并得物理地址6. 地址映射地址映射 : (p,d)(f,d) .邏輯頁號(hào)邏輯頁號(hào)頁架號(hào)頁架號(hào).fplbbl.pcb頁架號(hào)頁架號(hào)邏輯頁號(hào)邏輯頁號(hào).f.p.f dp d物理地址物理地址邏輯地址邏輯地址b:.如查不到.邏輯頁

19、號(hào)邏輯頁號(hào)頁架號(hào)頁架號(hào).fplbbl.pcb頁架號(hào)頁架號(hào)邏輯頁號(hào)邏輯頁號(hào).f.p.f dp d+cp p f 物理地址物理地址邏輯地址邏輯地址b:.有效訪問時(shí)間有效訪問時(shí)間n(effective access time)neat=快表命中率快表命中率 (快表訪問時(shí)間快表訪問時(shí)間+內(nèi)存訪內(nèi)存訪問時(shí)間問時(shí)間)+快表不中率快表不中率 (快表訪問時(shí)間快表訪問時(shí)間+2 內(nèi)存訪問時(shí)間內(nèi)存訪問時(shí)間) nsn 98% (20+100)+2% (20+200)ns =122ns6.3.2.2 多級(jí)頁表多級(jí)頁表n提出背景提出背景n內(nèi)存空間成倍增長(zhǎng)內(nèi)存空間成倍增長(zhǎng), 進(jìn)程虛擬空間成倍增加進(jìn)程虛擬空間成倍增加n單級(jí)頁

20、表需要很大連續(xù)內(nèi)存空間單級(jí)頁表需要很大連續(xù)內(nèi)存空間n例如例如n32位進(jìn)程地址空間，頁長(zhǎng)占位進(jìn)程地址空間，頁長(zhǎng)占12位（位（4k），頁號(hào)），頁號(hào)20位，頁位，頁表最多可達(dá)表最多可達(dá)220個(gè)入口！個(gè)入口！n多線程設(shè)計(jì)導(dǎo)致進(jìn)程虛擬空間不連續(xù)多線程設(shè)計(jì)導(dǎo)致進(jìn)程虛擬空間不連續(xù)(空洞空洞hole)n棧的預(yù)留空間棧的預(yù)留空間(沒有頁架相對(duì)應(yīng)沒有頁架相對(duì)應(yīng))n頁表所占內(nèi)存空間浪費(fèi)頁表所占內(nèi)存空間浪費(fèi)n解決策略解決策略n二級(jí)或多級(jí)頁表二級(jí)或多級(jí)頁表two-level page-table scheme外頁表對(duì)應(yīng)外頁表對(duì)應(yīng)hole的表項(xiàng)沒有對(duì)應(yīng)的表項(xiàng)沒有對(duì)應(yīng)的內(nèi)頁表的內(nèi)頁表訪問訪問hole表項(xiàng)動(dòng)表項(xiàng)動(dòng)態(tài)建立內(nèi)頁表

21、態(tài)建立內(nèi)頁表two-level paging examplea 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 logi

22、cal address is as follows:where pi is an index into the outer page table, and pj is the displacement within the page table.page number page offsetpipjd101012address-translation scheme address-translation scheme for a two-level 32-bit paging architecture even though time needed for one memory access

23、is quintupled, caching permits performance to remain reasonable4級(jí)頁表有效訪問時(shí)間級(jí)頁表有效訪問時(shí)間neat=快表命中率快表命中率 (快表訪問時(shí)間快表訪問時(shí)間+內(nèi)存訪內(nèi)存訪問時(shí)間問時(shí)間)+快表不中率快表不中率 (快表訪問時(shí)間快表訪問時(shí)間+5 內(nèi)存訪問時(shí)間內(nèi)存訪問時(shí)間) nsn 98% (20+100)+2% (20+500)nsn=128ns6.3.2.3 反置頁表反置頁表(inverted page table)n傳統(tǒng)頁表面向進(jìn)程空間傳統(tǒng)頁表面向進(jìn)程空間n每個(gè)進(jìn)程邏輯頁面有一表項(xiàng)每個(gè)進(jìn)程邏輯頁面有一表項(xiàng)n當(dāng)進(jìn)程空間很大時(shí)，頁表很

24、大當(dāng)進(jìn)程空間很大時(shí)，頁表很大n反置頁表面向內(nèi)存空間反置頁表面向內(nèi)存空間n每個(gè)內(nèi)存頁架一個(gè)表項(xiàng)每個(gè)內(nèi)存頁架一個(gè)表項(xiàng)n大小固定大小固定反置頁表反置頁表-工作原理工作原理程序程序物理物理內(nèi)存內(nèi)存pidpf dpid p df邏輯地址邏輯地址物理地址物理地址反置頁表反置頁表6.3.2 頁式存儲(chǔ)管理頁式存儲(chǔ)管理(cont.)采用散列技術(shù)的反置頁表地址映射采用散列技術(shù)的反置頁表地址映射邏輯地址邏輯地址pidpd進(jìn)程進(jìn)程邏輯邏輯頁號(hào)頁號(hào)沖突沖突計(jì)數(shù)計(jì)數(shù)空閑空閑.pidp21進(jìn)進(jìn)程程散列散列函數(shù)函數(shù)ffd物理地址物理地址采用散列技術(shù)的反置頁表采用散列技術(shù)的反置頁表物理內(nèi)存物理內(nèi)存速度問題速度問題n反置頁表查找

25、反置頁表查找n由表頭起始，平均為表長(zhǎng)度的一半由表頭起始，平均為表長(zhǎng)度的一半n速度慢速度慢n解決方案解決方案n在反置頁表前增加一級(jí)雜湊表在反置頁表前增加一級(jí)雜湊表n查找雜湊表與反置頁表至少需要兩次訪問內(nèi)查找雜湊表與反置頁表至少需要兩次訪問內(nèi)存存n為進(jìn)一步提高速度，快表緩沖為進(jìn)一步提高速度，快表緩沖1. 內(nèi)存空間劃分：動(dòng)態(tài)異長(zhǎng)，每區(qū)一段。內(nèi)存空間劃分：動(dòng)態(tài)異長(zhǎng)，每區(qū)一段。段首址段首址+段內(nèi)地址段內(nèi)地址物理地址物理地址=b：lb+d6.3.3 分段式存儲(chǔ)管理分段式存儲(chǔ)管理(segmentation)2. 進(jìn)程空間劃分：若干段，每段一個(gè)程序單位。進(jìn)程空間劃分：若干段，每段一個(gè)程序單位。調(diào)用調(diào)用x段段e

26、f: 訪問訪問d段段ae: 調(diào)用調(diào)用y段段fmain(段號(hào)段號(hào)0)x(段號(hào)段號(hào)1)y(段號(hào)段號(hào)2)d(段號(hào)段號(hào)3)a:080k-10.40k-1020k-1060k-1邏輯地址邏輯地址= 段號(hào)段號(hào) 段內(nèi)地址段內(nèi)地址(二維地址二維地址)mainxyd3. 對(duì)應(yīng)關(guān)系對(duì)應(yīng)關(guān)系40k60k80k20k.進(jìn)程空間進(jìn)程空間內(nèi)存空間內(nèi)存空間100k:200k:300k:320k:4. 所需表目所需表目(1) 段表：每進(jìn)程一個(gè)段表：每進(jìn)程一個(gè)段首址段首址段長(zhǎng)度段長(zhǎng)度100k40k80k60k段號(hào)段號(hào) 0: 1: 2: 3:20k200k320k300k(2) 空閑表：系統(tǒng)一個(gè)空閑表：系統(tǒng)一個(gè) array of

27、 (addr,size)5. 所需寄存器所需寄存器(1) 段表首址寄存器：段表首址寄存器：bl(2) 段表長(zhǎng)度寄存器：段表長(zhǎng)度寄存器：系統(tǒng)一個(gè)系統(tǒng)一個(gè)系統(tǒng)一個(gè)系統(tǒng)一個(gè)(3) 快表快表(tlb)：系統(tǒng)一組：系統(tǒng)一組： 段號(hào)段號(hào) 段首址段首址 段長(zhǎng)度段長(zhǎng)度.ls.b.6. 地址映射地址映射 : (s,d)(b+d) 邏輯地址邏輯地址(s,d)物理地址物理地址(b+d) (1)由程序確定邏輯地址由程序確定邏輯地址(s,d); (2) 由由s查快表得查快表得b和和l 如查不到：如查不到： (3) 由由s與與l比較判斷是否越界比較判斷是否越界 不滿足：不滿足：0 s l-1，越界；，越界； (4) 由由

28、s和和b查段表，得查段表，得b和和l (5) 由由d與與l比較，判斷是否越界比較，判斷是否越界 不滿足：不滿足：0 d l-1，越界，越界; (6) parbegin (s,b,l)快表快表, 如快表滿淘汰一個(gè)；如快表滿淘汰一個(gè)； 由由b d得物理地址得物理地址 parend (3) 由由d與與l比較，判斷是否越界比較，判斷是否越界 不滿足：不滿足：0 d l-1，越界；，越界； (4) 由由b d得物理地址。得物理地址。段號(hào)段號(hào)段長(zhǎng)段長(zhǎng) 段首址段首址. . . l b slbbl.pcb段首址段首址 段長(zhǎng)段長(zhǎng) 段號(hào)段號(hào) b l.s.b+d物理地址物理地址s d邏輯地址邏輯地址 cp+b:若查

29、不到若查不到段號(hào)段號(hào)段長(zhǎng)段長(zhǎng) 段首址段首址. . . l b slbbl.pcb段首址段首址 段長(zhǎng)段長(zhǎng) 段號(hào)段號(hào) . b l.s.b+d物理地址物理地址s d邏輯地址邏輯地址 . s l b b:+cpcp+6.3.3.2 段的共享段的共享段長(zhǎng)段長(zhǎng) 段首址段首址 . l b . .段號(hào)段號(hào) si .p1段表：段表：段長(zhǎng)段長(zhǎng) 段首址段首址 . l b . .段號(hào)段號(hào) sj .p2段表：段表：共享段共享段.b:l內(nèi)存空間內(nèi)存空間 如何實(shí)現(xiàn)？如何實(shí)現(xiàn)？ 共享段表共享段表段名段名 共享記數(shù)共享記數(shù) 段長(zhǎng)段長(zhǎng) 段首址段首址 其它其它 . vi 3 35k 125k ? 共享段表：共享段表：進(jìn)程段表進(jìn)程段

30、表(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 *

31、p_textp; /*pointer to text structure;struct user int u_tsize; 6.3.3.2 段的保護(hù)段的保護(hù) (1) 段表的改進(jìn)：段表的改進(jìn)：段長(zhǎng)段長(zhǎng) 段首址段首址 . . . l b e 1 0 1段號(hào)段號(hào) s .訪問權(quán)限訪問權(quán)限r(nóng) w e . . . 段號(hào)段號(hào) 段長(zhǎng)段長(zhǎng) 段首址段首址 . . . s l b 1 0 1訪問權(quán)限訪問權(quán)限r(nóng) w e(2) 快表的改進(jìn)：快表的改進(jìn)： . . .共享段共享段 表入口表入口6.3.4 段頁式存儲(chǔ)管理段頁式存儲(chǔ)管理(segmentation with paging)n段式優(yōu)于頁式段式優(yōu)于頁式n便于共享和保護(hù)便于共享和保護(hù)n頁式優(yōu)于段式頁式優(yōu)于段式n消除消除“碎片碎片”問題問題n段頁式：結(jié)合二者優(yōu)點(diǎn)段頁式：結(jié)合二者優(yōu)點(diǎn)n每個(gè)進(jìn)程包含若干段每個(gè)進(jìn)程包含若干段n每個(gè)段包含若干頁每個(gè)段包含若干頁6.3.4.1 基本原理基本原理 1. 內(nèi)存空間劃分：內(nèi)存空間劃分：(同頁式同頁式) 靜態(tài)等長(zhǎng)，靜態(tài)等長(zhǎng)，2i, 稱為一頁架。稱為一頁架。 物理地址物理地址=(頁架號(hào)頁架號(hào),頁內(nèi)地址頁內(nèi)地址)=(f,d) 2. 進(jìn)程空間劃分：進(jìn)程空間劃分： 一個(gè)進(jìn)程一個(gè)進(jìn)程若干個(gè)段若干個(gè)段 一個(gè)段一