工學(xué)06第六章-存儲管理

第六章存儲管理6.1存儲管理功能6.2內(nèi)存資源管理6.3存儲管理方式6.4外存空間管理6.5虛擬存儲系統(tǒng)6.1存儲管理功能

內(nèi)存/外存的管理;

內(nèi)/外存管理采用相同或相似的管理技術(shù)；功能存儲分配存儲共享存儲保護(hù)存儲擴(kuò)充地址映射6.1存儲管理功能(Cont.)

存儲分配/去配記錄內(nèi)/外存資源的使用情況:分配表、空閑表;分配/去配對象內(nèi)存、外存(相同方法);分配/去配時刻進(jìn)程創(chuàng)建、撤銷、交換、長度變化(棧溢出,execl)

存儲共享多個進(jìn)程共用內(nèi)存的相同區(qū)域;(物理空間有相交的部分)

目的：節(jié)省內(nèi)存、相互通訊;

內(nèi)容：代碼、數(shù)據(jù)。存儲保護(hù)防止地址越界;

防止操作越權(quán)。存儲擴(kuò)充內(nèi)存、外存結(jié)合，虛擬存儲體系;

速度接近內(nèi)存，容量相當(dāng)外存。地址映射邏輯地址=>物理地址硬件支持基址寄存器(base)、限長寄存器(limit)、快表；使用上述寄存器完成地址映射過程；不能正常完成地址映射時產(chǎn)生中斷。6.1存儲管理功能(Cont.)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ū)的分配分配策略:分配幾個等長區(qū)域;

分區(qū)表示:

字位映象圖;

空閑頁面表;

空閑頁面鏈。

動態(tài)異長分區(qū)的分配最先適應(yīng)(FirstFit);

最佳適應(yīng)(BestFit);

最壞適應(yīng)(WorstFit)。6.2.2.1靜態(tài)等長分區(qū)的分配

字位映象圖(bitmap)用一個bit代表一頁狀態(tài)，0:空閑，1:占用。100………1……..10第0頁第1頁第2頁………第k頁第n-1頁第n頁分配:按頁號從小到大查字位圖,找到為0的位改為1，返回頁號。去配:把頁號對應(yīng)的bit置為0。

空閑頁面表:首頁面號頁面?zhèn)€數(shù)…………1204………………占用120頁121頁122頁123頁占用……內(nèi)存分配/去配:需修改空閑頁面表。特點:可以分配連續(xù)頁面。

DMA要求6.2.2.1靜態(tài)等長分區(qū)的分配(Cont.)空閑頁面表結(jié)構(gòu)6.2.2.1靜態(tài)等長分區(qū)的分配(Cont.)

空閑頁面鏈:占用占用占用head空閑頁面鏈結(jié)構(gòu)分配/去配:調(diào)整鏈表。特點:節(jié)省空間。

(不適合外存管理)6.2.2.2動態(tài)異長分區(qū)的分配常用于界地址存儲管理和段式存儲管理?？臻e區(qū)首址空閑區(qū)長度……addresssize………………0空閑區(qū)表

初始時一個連續(xù)空閑區(qū);

空閑區(qū)首址由小到大;

長度=0為表尾。分配:

按分配策略調(diào)整表項;去配:把去配的空間插入表中,

可能需要合并空閑區(qū)。6.2.2.2動態(tài)異長分區(qū)的分配(Cont.)最先適應(yīng)算法(FirstFit):空閑區(qū)首址空閑區(qū)長度128642563210242560…………空閑區(qū)表空閑區(qū):首址遞增排列；申請:取第一個可滿足區(qū)域;優(yōu)點:盡量使用低地址空間,高區(qū)保持大空閑區(qū)域。缺點:可能分割大空閑區(qū)。

如申請32將分割第一個區(qū)域。6.2.2.2動態(tài)異長分區(qū)的分配(Cont.)最佳適應(yīng)算法(BestFit):空閑區(qū)首址空閑區(qū)長度256321286410242560…………空閑區(qū)表空閑區(qū):空閑區(qū)長度遞增排列;申請:取最小可滿足區(qū)域;優(yōu)點:盡量使用小空閑區(qū),保持大空閑區(qū)域。缺點:容易形成碎片fragment。

如申請30將留下長度為2的空閑區(qū)。6.2.2.2動態(tài)異長分區(qū)的分配(Cont.)最壞適應(yīng)算法(WorstFit):空閑區(qū)首址空閑區(qū)長度102425612864256320…………空閑區(qū)表空閑區(qū):空閑區(qū)長度遞減排列。申請:取最大可滿足區(qū)域。優(yōu)點:防止形成碎片。缺點:分割大空閑區(qū)。例:UNIX存儲分配－FirstFit

(見12章p286-12.4.2)最先適應(yīng)算法，空閑區(qū)首址遞增排列defineCMAPSIZ100defineSMAPSIZ100structmap//存儲資源表結(jié)構(gòu){char*m_size;char*m_addr;};structmapcoremap[CMAPSIZ];//內(nèi)存資源表structmapswapmap[SMAPSIZ];//外存資源表intmalloc(mp,size)

//存儲分配函數(shù)structmap*mp;{registerinta;registerstructmap*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)前塊＝sizedo{bp++;//do循環(huán)壓縮size=0的存儲表項

(bp-1)->m_addr=bp->m_addr;}while((bp-1)->m_size=bp->m_size);return(a);//分配成功，返回分配存儲塊的首地址

}return(0);//分配不成功，返回0}存儲分配函數(shù):mp=coremap內(nèi)存分配swapmap外存分配mfree(mp,size,aa)structmap*map;{registerstructmapbp;registerintt,a;a=aa;for(bp=mp;bp->m_addr<=a&&bp->m_size!=0;bp++);if(bp>mp&&(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;}}存儲釋放算法:mp=coremap釋放內(nèi)存swapmap釋放外存

}else//是存儲表項的第一項或不與前項存儲塊相連

{if(a+size==bp->m_addr&&bp->m_size)//與后項存儲塊相連?{bp->m_addr-=size;//與后項存儲塊合并。

bp->m_size+=size;}elseif(size)//與前、后項存儲塊均不相連,插入(size,a)表項

do{t=bp->m_addr;//do循環(huán)逐項后移

bp->m_addr=a;a=t;//a與bp->m_addr交換

t=bp->m_size;bp->m_size=size;//size與bp->m_size交換

bp++;}while(size=t);}}存儲釋放算法(Cont.)6.2.3碎片與緊湊緊湊(Compaction):

移動占用區(qū)域，使所有空閑區(qū)域連成一片(開銷很大)。0KB操作系統(tǒng)空間20KB20KB空閑區(qū)域10KB30KB進(jìn)程p1空間30KB60KB空閑區(qū)域10KB70KB進(jìn)程p1空間20KB90KB空閑區(qū)域10KB緊湊前0KB操作系統(tǒng)空間20KB20KB進(jìn)程p1空間30KB50KB進(jìn)程p1空間20KB70KB空閑區(qū)域30KB緊湊后6.3存儲管理方式無虛擬功能的存儲管理方式：界地址管理方式(一維地址)

頁式管理方式(一維地址)

段式管理方式(二維地址)

段頁式管理方式(二維地址)6.3.1界地址管理方式單對界存儲管理方式:(首地址,長度)基本原理⒈內(nèi)存空間劃分:動態(tài)異長；⒉進(jìn)程空間劃分:一個進(jìn)程一個區(qū)域,邏輯地址0～L-1;⒊進(jìn)程空間與內(nèi)存空間對應(yīng)關(guān)系(可以浮動):0:L-1:b:b+L-1:L…………進(jìn)程空間內(nèi)存空間6.3.1界地址管理方式(Cont.)⒋所需表目：

⑴內(nèi)存分配表:在PCB中;

⑵空閑區(qū)域表:arrayof(addr,size)。⒌所需寄存器：

⑴基址寄存器b:保存運行進(jìn)程起始地址;

⑵限長寄存器l:保存運行進(jìn)程長度。6.3.1界地址管理方式(Cont.)⒍地址映射：σ:(a)→(b+a)∪{Ω}0:L-1:b:b+L-1:L…………進(jìn)程空間內(nèi)存空間限長寄存器首址寄存器Lb…………<邏輯地址>……………………<物理地址>…………a越界中斷CMP+b+a步驟:

⑴由程序確定邏輯地址a;

⑵a與L比較判斷是否越界，不滿足:0≤a≤L-1，越界;

⑶a與b相加得到物理地址。6.3.1界地址管理方式(Cont.)

雙對界代碼區(qū)域:首址寄存器、限長寄存器;

數(shù)據(jù)區(qū)域:首址寄存器、限長寄存器;UNIX:代碼I空間、數(shù)據(jù)D空間。交換與重定位

交換:換入(swap-in)/換出(swap-out);

滾入(roll-in)/滾出(roll-out);

交換的基本單位為整個進(jìn)程。

可重定位程序:程序編址與內(nèi)存存放位置無關(guān);

浮動程序:滿足重定位要求的程序,如0起始編址。

重定位:換入程序需重定位。6.3.1界地址管理方式(Cont.)

覆蓋技術(shù):

將較大程序裝入較小進(jìn)程空間的技術(shù),

最大限度提高內(nèi)存利用率。只將全局代碼和數(shù)據(jù)靜態(tài)裝入內(nèi)存,

其它部分動態(tài)裝入;

后裝入的成分重復(fù)使用先裝入成分所使用的存儲區(qū),即覆蓋先裝入的成分;

用戶編寫覆蓋驅(qū)動程序,無需操作系統(tǒng)支持。6.3.1界地址管理方式(Cont.)例[覆蓋技術(shù)]：四遍掃描的編譯程序符號表公共例程覆蓋驅(qū)動程序覆蓋區(qū)50KB…………內(nèi)存Pass130KBPass250KBPass425KBPass340KB6.3.2分頁式存儲管理頁式存儲管理(paging):一個進(jìn)程占多個等長、連續(xù)內(nèi)存空間;無碎片。6.3.2.1基本原理⒈內(nèi)存空間劃分:頁架:靜態(tài)等長,長度2i;

頁架號:所有頁架由0開始依次編號;

頁內(nèi)地址:頁架內(nèi)單元由0開始依次編址。例如:內(nèi)存容量為2n,則共有2n-i個頁架。第k個頁架的起始地址為k×2i。6.3.2分頁式存儲管理(Cont.)0×2i第0頁2i1×2i第1頁2i…………k×2i第k頁2i…………(2n-i-1)×2i第2n-i－1頁2i內(nèi)存空間劃分n位一維地址碼=頁架首址+頁內(nèi)地址=頁架號×2i+頁內(nèi)地址=頁內(nèi)地址頁架號i位n-i位物理地址6.3.2分頁式存儲管理(Cont.)⒉進(jìn)程空間劃分:靜態(tài)等長，2

i,稱為一個頁面。0×2i第0頁2i1×2i第1頁2i…………k×2i第k頁2i…………(l-1)×2i第l－1頁2i進(jìn)程空間劃分=邏輯頁首址+頁內(nèi)地址=邏輯頁號×2i+頁內(nèi)地址=頁內(nèi)地址邏輯頁號i位n-i位邏輯地址6.3.2分頁式存儲管理(Cont.)⒊進(jìn)程空間與內(nèi)存空間對應(yīng)關(guān)系:頁面連續(xù),頁架可能不連續(xù)。第3頁第2頁第1頁第0頁進(jìn)程空間……第79頁第78頁……第47頁……第18頁……內(nèi)存空間6.3.2分頁式存儲管理(Cont.)⒋所需表目

頁表:

每個進(jìn)程一個。頁架號18477978邏輯頁號0123

總頁表:

系統(tǒng)一個,

記錄頁架使用情況

兩種結(jié)構(gòu)：表、鏈。⒌所需寄存器

頁表首址寄存器:

系統(tǒng)一個。b

頁表長度寄存器:

系統(tǒng)一個。l

快表:

系統(tǒng)一組。邏輯頁號頁架號…………pf…………l=46.3.2分頁式存儲管理(Cont.)⒍地址映射

:(p,d)(f,d)∪{}邏輯地址(p,d)

物理地址(f,d):⑴由程序確定邏輯地址(p,d);⑵由p查快表得頁架號f;如查不到：

①p與l比較，判別是否越界:

不滿足:0≤p≤l–1,越界中斷;②由p和b查頁表得f,(p,f)快表,如滿淘汰一個;

③轉(zhuǎn)⑵;⑶f與d合并得物理地址

(f,d)

。頁表長度寄存器頁表首址寄存器lb頁架號……f……邏輔頁號0…p…l-1進(jìn)程標(biāo)識pid……頁表長度l頁表首址b……頁表進(jìn)程控制塊PCB邏輯頁號頁架號…………pf…………快表TLBdp頁內(nèi)地址頁號

邏輯地址df頁內(nèi)地址頁架號物理地址頁式存儲管理地址映射快表未查到p6.3.2分頁式存儲管理(Cont.)頁表長度寄存器頁表首址寄存器lb頁架號……f……0邏輯頁號l-1…p…頁表進(jìn)程控制塊PCB邏輯頁號頁架號…………pf…………快表TLBdp頁內(nèi)地址頁號

邏輯地址df頁內(nèi)地址頁架號物理地址Cmpp:lb+p頁式存儲管理地址映射fp6.3.2分頁式存儲管理(Cont.)進(jìn)程標(biāo)識pid……頁表長度l頁表首址b……有效訪問時間

EffectiveAccessTime:EAT6.3.2分頁式存儲管理(Cont.)EAT=快表命中率×(快表訪問時間+內(nèi)存訪問時間)+快表不中率×(快表訪問時間+2×內(nèi)存訪問時間)ns例：快表命中率98％，快表訪問時間20ns，內(nèi)存一次訪問時間100ns，則EAT=98％(20+100)+2％(20+200)=122ns6.3.2.2多級頁表提出背景內(nèi)存空間成倍增長,進(jìn)程虛擬空間成倍增加。單級頁表需要很大連續(xù)內(nèi)存空間

例如:

232位進(jìn)程地址空間(4G),頁長占212位(4K),

進(jìn)程擁有的頁面最多可達(dá)220,即頁表最多可達(dá)220個表項。多線程設(shè)計導(dǎo)致進(jìn)程虛擬空間不連續(xù)(空洞hole)

頁表所占內(nèi)存空間浪費。解決策略:

減少頁表所占內(nèi)存空間。二級或多級頁表:外頁表,內(nèi)頁表棧的預(yù)留空間(沒有頁架相對應(yīng))6.3.2分頁式存儲管理(Cont.)6.3.2分頁式存儲管理(Cont.)……01102320……95102……309498……512010230102301023…………20……95……102……309……498……512……OutertablePagetableMemory外頁表對應(yīng)hole的表項沒有對應(yīng)的內(nèi)頁表，訪問hole表項動態(tài)建立內(nèi)頁表二級頁表6.3.2分頁式存儲管理(Cont.)二級頁表的地址映射:pipjd

Logicaladdressstructure:10bits10bits12bitsPageoffsetPi:outerpagetableindex;Pj:pagetabledisplacement.Pagenumber

addresstranslationscheme:p1p2dLogicaladdress……Outertablep1f……Pagetablep2Physicaladdress……memoryd6.3.2分頁式存儲管理(Cont.)

采用二級頁表結(jié)構(gòu)時,邏輯地址由外層頁號pi,外層頁內(nèi)地址pj,頁內(nèi)地址d三部分構(gòu)成。若給定一個邏輯地址空間的地址為A,系統(tǒng)頁面大小為L,頁表項的長度為N,則pi,pj和d的計算公式如下：pi=int[int[A/L]/N]

pj=int[A/L]modN

d=AmodL

對前述二級頁表結(jié)構(gòu),L=212,N=2106.3.2分頁式存儲管理(Cont.)4級頁表有效訪問時間EAT=快表命中率

(快表訪問時間+內(nèi)存訪問時間)+

快表不中率(快表訪問時間+5內(nèi)存訪問時間)ns例[4級頁表]:

快表命中率98％，快表訪問時間20ns，內(nèi)存訪問時間100ns，則

EAT=98%(20+100)+2%(20+500)ns=128ns6.3.2.3反置頁表

傳統(tǒng)頁表面向進(jìn)程空間每個進(jìn)程邏輯頁面有一表項;

當(dāng)進(jìn)程空間很大時,頁表很大。

反置頁表面向內(nèi)存空間系統(tǒng)只設(shè)置一個反置頁表,為所有進(jìn)程所用。反置頁表大小固定;

每個內(nèi)存頁架一個表項,表項序號即為頁架號;invertedpagetable6.3.2.3反置頁表(Cont.)反置頁表工作原理:

……<內(nèi)存訪問>……pidpd邏輯地址pidp程序0f…fd物理地址反置頁表……………………d

f個頁架d物理內(nèi)存速度問題

反置頁表查找由表頭起始,平均為表長度的一半;

速度慢。解決方案在反置頁表前增加一級雜湊表;

邏輯頁號為關(guān)鍵字，通過Hash函數(shù)確定進(jìn)程反置頁表首項位置。

查找雜湊表與反置頁表至少需要兩次訪問內(nèi)存;

為進(jìn)一步提高速度，快表緩沖。6.3.2.3反置頁表(Cont.)6.3.3分段式存儲管理

segmentation6.3.2.1基本原理⒈內(nèi)存空間劃分:動態(tài)劃分成異長區(qū)域，每個區(qū)域稱作一個物理段;物理段:段首址,段內(nèi)地址(由0開始編址);物理地址:段首址+段內(nèi)地址(一維地址);段號段內(nèi)地址⒉進(jìn)程空間劃分:靜態(tài)劃分成異長區(qū)域，每個區(qū)域稱作一個邏輯段;邏輯段:程序單位,如主程序,子程序,數(shù)據(jù)區(qū),模塊;段號:每個進(jìn)程有多個邏輯段，從0開始依次編號;邏輯段的段內(nèi)地址從0開始編址;邏輯地址:(二維地址)6.3.3分段式存儲管理(Cont.)占用空閑占用空閑占用空閑占用140KB100KB130KB60KB20KB50KB

0KB內(nèi)存空間劃分……調(diào)用[X]段入口E訪問[DATA]段A單元……調(diào)用[Y]段入口F……主程序段:[main]段號=0

050KB-1......

……F:…………子程序段:[Y]段號=2

030KB-1…

……E：…………子程序段:[X]段號=3

040KB-1…

……A:…………子程序段:[DATA]段號=1

030KB-1…進(jìn)程空間6.3.3分段式存儲管理(Cont.)⒊進(jìn)程空間與內(nèi)存空間對應(yīng)關(guān)系:進(jìn)程P段[main]段號=0進(jìn)程P段[data]段號=1進(jìn)程P段[Y]段號=2進(jìn)程P段[X]段號=3

050KB-1

0

0

030KB-140KB-130KB-1……………………………………………………120KB390KB480KB810KB50KB30KB30KB40KB120KB220KB60KB300KB6.3.3分段式存儲管理(Cont.)⒋所需表目:⑴段表:每個進(jìn)程一個。段號段首址段長0120KB50KB1

390KB30KB2

480KB30KB3

810KB40KB⑵空閑表:系統(tǒng)一個arrayof(addr,size)首地址長度

0KB120KB

170KB220KB

420KB

60KB

510KB300KB6.3.3分段式存儲管理(Cont.)⒌所需寄存器:⑴段表首址寄存器一個:⑵段表長度寄存器一個:⑶快表:系統(tǒng)一組bl段號段首址段長度………………sb’l’………………邏輯地址(s,d)

物理地址(b’+d):⑴由程序確定邏輯地址(s,d);⑵由s查快表得b’和l’;如查不到：

①s與l比較，判別是否越界:

不滿足:0≤s≤l–1,越界中斷;②由s和b查段表得b’和l’,(s,b’,l’)快表,如快表滿淘汰一個；③轉(zhuǎn)⑵;⑶d與l’比較,不滿足:0≤d≤l’-1,越界;⑷b’+d得物理地址。6.3.3分段式存儲管理(Cont.)⒍地址映射::(s,d)(b’+d)∪{}6.3.3分段式存儲管理(Cont.)段首址段長…………b’l’…………段號0…s…l-1進(jìn)程標(biāo)識pid……段表長度l段表首址b……段表進(jìn)程控制塊PCB段號段首址段長…………sb’l’…………

快表TLB段式存儲管理地址映射偏移段號

邏輯地址dscmp物理地址b’+d+段表長度reg段表首址regbl若快表查不到s6.3.3分段式存儲管理(Cont.)段首址段長…………b’l’…………段號0…s…l-1進(jìn)程標(biāo)識pid……段表長度l段表首址b……段表進(jìn)程控制塊PCB段號段首址段長…………sb’l’…………

快表TLB段式存儲管理地址映射sb’l’偏移段號

邏輯地址dscmp物理地址b’+d+段表長度reg段表首址regbl+cmp6.3.3分段式存儲管理(Cont.)

6.3.2.2段的共享與保護(hù)⒈段的共享:不同進(jìn)程的段號Spi和Spj對應(yīng)同一個段的段首址和段長即可實現(xiàn)不同進(jìn)程對段的共享。段首址段長度…………b’l’…………P1段表……si段號段首址段長度…………b’l’…………P2段表……sj段號……共享段……b’:l’內(nèi)存空間6.3.3分段式存儲管理(Cont.)共享段表:系統(tǒng)1個,記錄所有共享段。main1子程序X子程序Y……datamain2data子程序Y子程序X段長度首址P10段號P21234段長度首址0段號123段表段名共享計數(shù)段長度段首址其它X2Y2data2共享段表●●●main1XDataYmain2●●●主存6.3.3分段式存儲管理(Cont.)⒉段的保護(hù):不同進(jìn)程對共享段的訪問權(quán)限不同，需要在段表中加上訪問權(quán)限。段首址段長度訪問權(quán)限RWE…………………………b’l’101…………………………段表的改進(jìn)……s段號段號段首址段長度訪問權(quán)限RWE…………………………sb’l’101…………………………快表的改進(jìn)頁式管理段式管理一維地址空間二維地址空間頁是物理單位段是邏輯單位頁的大小固定段的大小可變對用戶透明對用戶可見無碎片有碎片通常不共享便于共享、保護(hù)頁式管理和段式管理的比較:6.3.3分段式存儲管理(Cont.)

段式優(yōu)于頁式便于共享和保護(hù)

頁式優(yōu)于段式消除“碎片”問題段頁式：結(jié)合二者優(yōu)點每個進(jìn)程包含若干段；每個段包含若干頁。6.3.4段頁式存儲管理segmentationwithpaging6.3.4段頁式存儲管理(Cont.)6.3.4.1基本原理

⒈內(nèi)存空間劃分:(同頁式)靜態(tài)等長,2i,稱為一頁架;

物理地址

==(f,d)。頁內(nèi)地址頁架號n-i位i位⒉進(jìn)程空間劃分:

一個進(jìn)程若干個段;

一個段若干個頁;

邏輯地址==(s,p,d)。段號頁內(nèi)地址邏輯頁號i位j位n-i-j位⒊