內(nèi)存管理數(shù)據(jù)結(jié)構(gòu).ppt

1、內(nèi)存管理數(shù)據(jù)結(jié)構(gòu),2015.3.31星期二（單周） 2015.4.7星期二（雙周,掌握內(nèi)存管理的數(shù)據(jù)結(jié)構(gòu),程序的頁表 MMU的APR U區(qū)的u.u_uisa16,u.u_uisd16 內(nèi)存的空白區(qū)域 struct map,一、程序的內(nèi)存組織方法,Static char *class=host;/標題頁上的類名 Static char format=f; /打印文件用的格式字符 Static char hdr=1; /是否打印標題,已經(jīng)初始化的數(shù)據(jù),Static char *dfname; /數(shù)據(jù)文件 Static char *fonts4; /troff字體名 Static char ifla

2、g; /需要的縮進,未初始化的數(shù)據(jù)bss,程序,Static char* lmktemp(char *id,int num,int len) char *s; if(s=malloc(len)=NULL) fatal2(“out of memory”); (void)snfrintf(s,len,”%s%A%03d%S”,SD,id,num,host);,程序參數(shù)棧區(qū)域,局部變量棧區(qū)域,堆,代碼,Linux虛擬存儲器管理,與進程相關的數(shù)據(jù)結(jié)構(gòu)（頁表，task,mm結(jié)構(gòu)，內(nèi)核棧,物理存儲器,內(nèi)核代碼和數(shù)據(jù),每個進程不同,每個進程相同,用戶棧,共享庫的存儲器映射區(qū)域,運行時堆（malloc分配,未

3、初始化數(shù)據(jù).bss,已初始化數(shù)據(jù).data,程序文件(.text,0 x08048000(32) 0 x0040000(64,brk,esp,內(nèi)核虛擬存儲器,進程虛擬存儲器,二、UNIX V6內(nèi)存管理,1)頁表 內(nèi)存的分頁管理(paging)：把每個程序的地址空間分成大小相等的片，稱之為頁面或者頁(page)；內(nèi)存的存儲空間分成與頁大小相同的片，稱為頁框(page frame),為進程分配存儲空間時，以頁為單位。 MMU為進程的每一個頁面分配一個寄存器，這些寄存器組成一個表，稱為頁表 頁表的硬件實現(xiàn) 有多種方法，用一組專用寄存器存放頁表。PDP-11/40使用APR，高速邏輯電路構(gòu)造，有效進行

4、分頁地址的轉(zhuǎn)換。由于對內(nèi)存的每次訪問都要經(jīng)過頁表，因此效率很重要,Unix v6的頁表用APR實現(xiàn)。程序裝入問題,CPU調(diào)度程序swtch()在裝入保存在U區(qū)的R0R7數(shù)據(jù)時，也裝入APR的數(shù)據(jù)。 APR數(shù)據(jù)保存在u.u_uisa16和u.u_uisd16中,APR頁表,PDP-11/40的CPU字長是16位，地址是16位，頁面大小8kB，因此APR頁表有8個條目，每個程序最多有8個page。 APR有8個快速reg組。 216=64k 頁面8k，所以頁表有8個條目。 現(xiàn)代OS的頁表(一百萬個條目)放在內(nèi)存，將頁表基地址存放在PTBR寄存器。使用快表，提高效率,PDP-11/40的CPU地址和

5、總線物理地址,總線18位，所以內(nèi)存物理地址218=4*64k=256k。P5 所以內(nèi)存最多可存放4個完整的進程地址空間。 P23 實際上，一般情況是，執(zhí)行進程的整個地址空間在內(nèi)存中，而不在CPU上執(zhí)行的進程，將它的數(shù)據(jù)段調(diào)出到交換區(qū)（交換文件），只有一部分進程映像在內(nèi)存，可提高內(nèi)存的利用率,UNIX V6進程頁表的硬件實現(xiàn),PDP-11/40的APR頁表是頁面與塊兩級結(jié)構(gòu)。 頁面長度8k,這是CPU字長決定的。 每個頁面分成128塊，塊的長度64B. 塊是存儲分配的基本單位 PDP-11/46的頁表包括8個頁面，maxmem表示頁表中最多塊數(shù)。 APR(active page register

6、)寄存器一共有8組，每組APR由1個PAR(page address register)和1個PDR(page description register)寄存器構(gòu)成，PAR07,PDR07,UNIX V6進程頁表的硬件實現(xiàn),PAR保存各頁面在塊的起始地址，PDR保存各頁當前的塊數(shù)。每頁最多128塊，每塊64字節(jié)。128*64B=8k,APR0,APR1,APR2,APR3,APR4,APR5,APR6,APR7,PAR0,PAR1,PAR2,PAR3,PAR4,PAR5,PAR6,PAR7,PDR0,PDR1,PDR2,PDR3,PDR4,PDR5,PDR6,PDR7,地址轉(zhuǎn)換,邏輯地址,15

7、,13,12,6,5,0,頁號APR,塊號,塊內(nèi)偏移量,15,12,11,0,PARi塊號起始地址,塊號,塊內(nèi)偏移量,P25,執(zhí)行進程u P26,執(zhí)行進程U區(qū)，全局變量u(0140000)在內(nèi)核PAR6的起始地址 Proc.p_addr=PAR6,內(nèi)核APR,0,1,2,3,4,5,6 u,7,1-100-000-000-000-000,6：110,U區(qū),內(nèi)核棧,Proc.p_addr,執(zhí)行進程的數(shù)據(jù)段,物理地址,八進制數(shù)，16位CPU字長。最高位1位，后面15位，所以有5個數(shù)字,APR6,3)用戶APR在進程調(diào)度時，savu()保存在U區(qū),進程切換swtch(,PAR,0,1,2,3,4,5

8、,6,7,0,1,2,3,4,5,6,7,u.u_uisa,savu()保存PAR在user.u_uisa中,PDR,0,1,2,3,4,5,7,0,1,2,3,4,5,6,u.u_uisd,savu()保存PDR在user.u_uisd中,6,sureg()將user.u_uisa,user.u_uisd的內(nèi)容傳遞到APR頁表中,例題1. eatabur()設定的用戶APR示例 qaqrfrqwert P,當進程的代碼段，數(shù)據(jù)區(qū)域，棧區(qū)域的長度約為192*64字節(jié)時，用戶APR的狀態(tài),0 128,16(USIZE) 144,0 0,208 273,0 1,代碼,2 3,4 5,6 7,數(shù)據(jù),

9、棧,起始塊號,127 RO 只讀 64 RO,127 RW 64 RW,0 0,64 RW ED 127 RW,0 1,2 3,4 5,6 7,User.u_uisa,User.u_uisd,腳地址207,起始塊號的計算方法,1)代碼段從APR0開始分配，PAR0=0,PDR0=128. 代碼段在APR0沒有分配的塊，在連續(xù)頁面APR1分配，PAR1=128. 與代碼段不應在同一個頁面，到代碼段page之后連續(xù)的頁面分配。這個例子中，數(shù)據(jù)段在PAR2開始分配，從第0塊開始。 (2)數(shù)據(jù)段有PPDA，長度USIZE*64B。因此數(shù)據(jù)段的進程地址空間從第16塊開始分配，PAR2=16。數(shù)據(jù)段192

10、塊，則數(shù)據(jù)段的數(shù)據(jù)區(qū)域最后一塊的塊號是16+192-1=207。 (3)棧區(qū)域在數(shù)據(jù)段中，在數(shù)據(jù)區(qū)域之后連續(xù)分配，因此在數(shù)據(jù)段的第208塊開始分配，總塊數(shù)192，棧區(qū)域的ED要求在APR7開始分配。 若棧區(qū)域最后一塊的塊號400，則PAR7=400，PAR6=400-128+1=273.因此實際上最后一塊的塊號是399,4）UNIX V6的段頁式管理,段表,代碼段,數(shù)據(jù)段 棧區(qū)域,Text.x_caddr(proc.p_textp,proc.p_addr,Sep=0,代碼段和數(shù)據(jù)段在在同一個頁表中管理。 現(xiàn)代OS，每一個段有自己的一個頁表,在物理內(nèi)存中的地址,二、地址轉(zhuǎn)換,地址變換：程序的邏輯

11、地址變換為主存的物理地址,0 128,16(USIZE) 144,0 0,208 273,0 1,代碼,2 3,4 5,6 7,數(shù)據(jù),棧,執(zhí)行進程的APR頁表,1.從ARP頁表中可知，程序的代碼段、數(shù)據(jù)段從0塊號開始。 2.進程的數(shù)據(jù)段有PPDA（系統(tǒng)數(shù)據(jù)區(qū)），因此可執(zhí)行文件實際從數(shù)據(jù)段的塊號16開始分配主存的地址空間。數(shù)據(jù)段的塊號0,15保存PPDA。 3.棧區(qū)域從進程地址空間的最高地址開始分配。棧區(qū)域的腳地址=數(shù)據(jù)區(qū)域腳地址+棧區(qū)域長度ns,1.程序的執(zhí)行exec(,程序在執(zhí)行時，需將程序的可執(zhí)行文件從塊設備讀取至內(nèi)存 (1)代碼段的讀入 程序的代碼段所在地址text.x_caddr 在e

12、xec()原語實現(xiàn) exec()83行xalloc()。 P91 xalloc() :p_textp=xp。 17行,39行 xp是text數(shù)組的元素 text.x_caddr:代碼段讀入內(nèi)存物理空間起始地址 text.x_daddr:代碼段在外存交換區(qū)的地址,數(shù)據(jù)段在內(nèi)存的起始塊號,2)數(shù)據(jù)段的讀入 proc.p_addr 是數(shù)據(jù)段在內(nèi)存中的起始地址 在exec()中實現(xiàn)數(shù)據(jù)段的讀入 94行， readi(ip) 。 P246 readi() readi()函數(shù)必須先在estabur()中設置APR eatabur()在APR頁表中設置數(shù)據(jù)段的相對地址：PAR,PDR 數(shù)據(jù)段的內(nèi)存分配在fo

13、rk()中實現(xiàn) (a)子進程和EP進程共享代碼段，則APR頁表相同 (b)子進程exec新的程序，則讀入新的程序而且更新APR頁表 proc.p_addr=a2=malloc(coremap,n); 數(shù)據(jù)段的實際地址,P63例題,text.x_caddr=50 proc.p_addr=300 則進程的主存地址空間,0 128,16(USIZE) 144,0 0,208 273,0 1,代碼,2 3,4 5,6 7,數(shù)據(jù),棧,執(zhí)行進程的APR頁表,50,241,代碼段,300,第一次地址轉(zhuǎn)換: (1)邏輯地址：0110001000001000 011: 頁號。第三頁APR3 0001000:塊號

14、。第八塊，相對塊號。 001000：塊內(nèi)偏移量 (2)相對物理地址： PAR3=144,物理塊號144+8-1=151,主存物理空間（fork(),PPDA,316,數(shù)據(jù)區(qū)域,棧區(qū)域,508,699,8相對塊號：相對所在APR起始地址的塊號,151相對塊號：相對所在段起始地址的塊號,第二次地址轉(zhuǎn)換： 151+300=451 在物理內(nèi)存中的實際塊號。 字節(jié)地址： 451*64+塊內(nèi)偏移量,問題：為什么是*64而不是*32,sureg():將相對物理地址轉(zhuǎn)換成內(nèi)存物理地址,50 178,316(USIZE) 444,0 0,508 573,0 1,代碼,2 3,4 5,6 7,數(shù)據(jù),棧,UISA,

15、UISA: 內(nèi)存映射技術 將寄存器映射到內(nèi)存中的一個事先定義的地址。 PSW：PS，0177776 APR的PAR：UISA，0177640 PDR：UDSA，0177660,P63 例題,進程調(diào)出，APR頁表的內(nèi)容保存在u.u_uisa,u.u_uisd,0 128,16(USIZE) 144,0 0,208 273,0 1,代碼,2 3,4 5,6 7,數(shù)據(jù),棧,u.u_uisa,并不保存UISA和UDSA的內(nèi)容。 原因是什么,P63 例題,0 128,16(USIZE) 144,0 0,208 273,0 1,代碼,2 3,4 5,6 7,數(shù)據(jù),棧,執(zhí)行進程的APR頁表,50,241,代

16、碼段,400,主存物理空間（fork(),PPDA,416,數(shù)據(jù)區(qū)域,棧區(qū)域,608,799,8相對塊號：相對所在APR起始地址的塊號,151相對塊號：相對所在段起始地址的塊號,問題：為什么保留u.u_uisa,u.u_uisd中的相對地址，而不是UISA，UDSA中的實際物理內(nèi)存地址,進程調(diào)入：代碼段，有共享進程則text.x_xaddr不變，仍為50. 則數(shù)據(jù)段調(diào)入到a=400的起始地址,text.x_xaddr,proc.p_addr,重新調(diào)入內(nèi)存后，P63例題的主存物理空間,50 178,416(USIZE) 544,0 0,608 673,0 1,代碼,2 3,4 5,6 7,數(shù)據(jù),棧,UISA,P63 例題,問題：為什么保留u.u_uisa,u.u_uisd中的相對地址，而不是UISA，UDSA中的實際物理內(nèi)存地址？ 這個問題可以回答了。 每一次進程調(diào)出調(diào)入的物理內(nèi)存起始地址不同。 所以每次保存相對地址,若進程的代碼段在內(nèi)存中不存在,則malloc(coremap,text.x_size+proc.p_size) 代碼段和數(shù)據(jù)段相鄰分配物理內(nèi)存,相對塊號與實際字節(jié)物理地址,實際物理地址：實際塊號*64B+塊內(nèi)偏移量 map的長度64B，所以不是*32,2.內(nèi)存的物理地址空間,以塊為單位分配物理內(nèi)存。 內(nèi)存塊長度64B，磁盤交換區(qū)塊長度512B。 物