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

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

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

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

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

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

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

7、）空閑區(qū)：首址遞增排列；空閑區(qū)：首址遞增排列；申請：取最大可滿足區(qū)域；申請：取最大可滿足區(qū)域；優(yōu)點：防止形成碎片。優(yōu)點：防止形成碎片。缺點：分割大空閑區(qū)域。缺點：分割大空閑區(qū)域?？臻e區(qū)首址空閑區(qū)首址空閑區(qū)長度空閑區(qū)長度128641024256322560.unix存儲分配存儲分配-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 = bp-

10、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 碎片處理碎片處理緊湊：移動占用區(qū)域，使所有空閑區(qū)域連成一片（開銷很大）緊湊：移動占用區(qū)域，使所有空閑區(qū)域連成一片（開銷很大）。 os p

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

12、，邏輯地址0 l-1 3. 進程空間與內存空間對應關系（可以浮動）：進程空間與內存空間對應關系（可以浮動）：0:l-1:.b:lb+l-1:進程空間進程空間內存空間內存空間6.3.1 界地址管理方式界地址管理方式 4. 所需表目：所需表目： (1)內存分配表內存分配表-在在pcb中；中； (2)空閑區(qū)域表：空閑區(qū)域表：array of (addr,size)。 5. 所需寄存器：所需寄存器： (1)基址寄存器基址寄存器b: 保存運行進程起始地址；保存運行進程起始地址； (2)限長寄存器限長寄存器l: 保存運行進程長度保存運行進程長度。 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相加得到物理地址。相加得到物理地址。進程空間進程空間內存空間內存空間6.3.1 界地址管理方式界地址管理方式6.3.1.2 雙對界雙對界 代碼代碼(i空間空間)：一對界：一對界 數(shù)據(jù)數(shù)據(jù)(d空間空間)：一對界：一對界6.3.1.3 交換技術交換技術(swapping) 例：例：unix 交換進程交換進程sched (#0) 交換原則：外存交換原

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

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

16、頁架首址頁架首址+頁內地址頁內地址 =頁架號頁架號 2i +頁內地址頁內地址 = 頁架號頁架號 頁內地址頁內地址i位位n-i位位6.3.2 分頁式存儲管理分頁式存儲管理2. 進程空間劃分：靜態(tài)等長，進程空間劃分：靜態(tài)等長，2i, 稱為一個頁面。稱為一個頁面。.第第0頁頁第第1頁頁第第k頁頁 第第l-1頁頁2i0 2i:1 2i:k 2i: (l-1) 2i:邏輯地址邏輯地址=邏輯頁首址邏輯頁首址+頁內地址頁內地址 =邏輯頁號邏輯頁號 2i +頁內地址頁內地址 =邏輯頁號邏輯頁號 頁內地址頁內地址i位位3. 進程空間與內存空間對應關系進程空間與內存空間對應關系.第第0頁頁第第1頁頁第第2頁頁第第

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

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

19、架號.fplbbl.pcb頁架號頁架號邏輯頁號邏輯頁號.f.p.f dp d+cp p f 物理地址物理地址邏輯地址邏輯地址b:.有效訪問時間有效訪問時間n(effective access time)neat=快表命中率快表命中率 (快表訪問時間快表訪問時間+內存訪內存訪問時間問時間)+快表不中率快表不中率 (快表訪問時間快表訪問時間+2 內存訪問時間內存訪問時間) nsn 98% (20+100)+2% (20+200)ns =122ns6.3.2.2 多級頁表多級頁表n提出背景提出背景n內存空間成倍增長內存空間成倍增長, 進程虛擬空間成倍增加進程虛擬空間成倍增加n單級頁表需要很大連續(xù)內存

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

21、-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 logical addre

22、ss 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 is quintu

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

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

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

26、e: 調用調用y段段fmain(段號段號0)x(段號段號1)y(段號段號2)d(段號段號3)a:080k-10.40k-1020k-1060k-1邏輯地址邏輯地址= 段號段號 段內地址段內地址(二維地址二維地址)mainxyd3. 對應關系對應關系40k60k80k20k.進程空間進程空間內存空間內存空間100k:200k:300k:320k:4. 所需表目所需表目(1) 段表：每進程一個段表：每進程一個段首址段首址段長度段長度100k40k80k60k段號段號 0: 1: 2: 3:20k200k320k300k(2) 空閑表：系統(tǒng)一個空閑表：系統(tǒng)一個 array of (addr,size

27、)5. 所需寄存器所需寄存器(1) 段表首址寄存器：段表首址寄存器：bl(2) 段表長度寄存器：段表長度寄存器：系統(tǒng)一個系統(tǒng)一個系統(tǒng)一個系統(tǒng)一個(3) 快表快表(tlb)：系統(tǒng)一組：系統(tǒ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) 由由s和和b查段表，得查段表

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

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

30、)共享段共享段(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; /*poi

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