内存管理数据结构.ppt

1、内存管理数据结构,2015.3.31星期二（单周） 2015.4.7星期二（双周,掌握内存管理的数据结构,程序的页表 MMU的APR U区的u.u_uisa16,u.u_uisd16 内存的空白区域 struct map,一、程序的内存组织方法,Static char *class=host;/标题页上的类名 Static char format=f; /打印文件用的格式字符 Static char hdr=1; /是否打印标题,已经初始化的数据,Static char *dfname; /数据文件 Static char *fonts4; /troff字体名 Static char ifla

2、g; /需要的缩进,未初始化的数据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);,程序参数栈区域,局部变量栈区域,堆,代码,Linux虚拟存储器管理,与进程相关的数据结构（页表，task,mm结构，内核栈,物理存储器,内核代码和数据,每个进程不同,每个进程相同,用户栈,共享库的存储器映射区域,运行时堆（malloc分配,未

3、初始化数据.bss,已初始化数据.data,程序文件(.text,0 x08048000(32) 0 x0040000(64,brk,esp,内核虚拟存储器,进程虚拟存储器,二、UNIX V6内存管理,1)页表 内存的分页管理(paging)：把每个程序的地址空间分成大小相等的片，称之为页面或者页(page)；内存的存储空间分成与页大小相同的片，称为页框(page frame),为进程分配存储空间时，以页为单位。 MMU为进程的每一个页面分配一个寄存器，这些寄存器组成一个表，称为页表 页表的硬件实现 有多种方法，用一组专用寄存器存放页表。PDP-11/40使用APR，高速逻辑电路构造，有效进行

4、分页地址的转换。由于对内存的每次访问都要经过页表，因此效率很重要,Unix v6的页表用APR实现。程序装入问题,CPU调度程序swtch()在装入保存在U区的R0R7数据时，也装入APR的数据。 APR数据保存在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个条目。 现代OS的页表(一百万个条目)放在内存，将页表基地址存放在PTBR寄存器。使用快表，提高效率,PDP-11/40的CPU地址和

5、总线物理地址,总线18位，所以内存物理地址218=4*64k=256k。P5 所以内存最多可存放4个完整的进程地址空间。 P23 实际上，一般情况是，执行进程的整个地址空间在内存中，而不在CPU上执行的进程，将它的数据段调出到交换区（交换文件），只有一部分进程映像在内存，可提高内存的利用率,UNIX V6进程页表的硬件实现,PDP-11/40的APR页表是页面与块两级结构。 页面长度8k,这是CPU字长决定的。 每个页面分成128块，块的长度64B. 块是存储分配的基本单位 PDP-11/46的页表包括8个页面，maxmem表示页表中最多块数。 APR(active page register

6、)寄存器一共有8组，每组APR由1个PAR(page address register)和1个PDR(page description register)寄存器构成，PAR07,PDR07,UNIX V6进程页表的硬件实现,PAR保存各页面在块的起始地址，PDR保存各页当前的块数。每页最多128块，每块64字节。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,地址转换,逻辑地址,15

7、,13,12,6,5,0,页号APR,块号,块内偏移量,15,12,11,0,PARi块号起始地址,块号,块内偏移量,P25,执行进程u P26,执行进程U区，全局变量u(0140000)在内核PAR6的起始地址 Proc.p_addr=PAR6,内核APR,0,1,2,3,4,5,6 u,7,1-100-000-000-000-000,6：110,U区,内核栈,Proc.p_addr,执行进程的数据段,物理地址,八进制数，16位CPU字长。最高位1位，后面15位，所以有5个数字,APR6,3)用户APR在进程调度时，savu()保存在U区,进程切换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的内容传递到APR页表中,例题1. eatabur()设定的用户APR示例 qaqrfrqwert P,当进程的代码段，数据区域，栈区域的长度约为192*64字节时，用户APR的状态,0 128,16(USIZE) 144,0 0,208 273,0 1,代码,2 3,4 5,6 7,数据,

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没有分配的块，在连续页面APR1分配，PAR1=128. 与代码段不应在同一个页面，到代码段page之后连续的页面分配。这个例子中，数据段在PAR2开始分配，从第0块开始。 (2)数据段有PPDA，长度USIZE*64B。因此数据段的进程地址空间从第16块开始分配，PAR2=16。数据段192

10、块，则数据段的数据区域最后一块的块号是16+192-1=207。 (3)栈区域在数据段中，在数据区域之后连续分配，因此在数据段的第208块开始分配，总块数192，栈区域的ED要求在APR7开始分配。 若栈区域最后一块的块号400，则PAR7=400，PAR6=400-128+1=273.因此实际上最后一块的块号是399,4）UNIX V6的段页式管理,段表,代码段,数据段 栈区域,Text.x_caddr(proc.p_textp,proc.p_addr,Sep=0,代码段和数据段在在同一个页表中管理。 现代OS，每一个段有自己的一个页表,在物理内存中的地址,二、地址转换,地址变换：程序的逻辑

11、地址变换为主存的物理地址,0 128,16(USIZE) 144,0 0,208 273,0 1,代码,2 3,4 5,6 7,数据,栈,执行进程的APR页表,1.从ARP页表中可知，程序的代码段、数据段从0块号开始。 2.进程的数据段有PPDA（系统数据区），因此可执行文件实际从数据段的块号16开始分配主存的地址空间。数据段的块号0,15保存PPDA。 3.栈区域从进程地址空间的最高地址开始分配。栈区域的脚地址=数据区域脚地址+栈区域长度ns,1.程序的执行exec(,程序在执行时，需将程序的可执行文件从块设备读取至内存 (1)代码段的读入 程序的代码段所在地址text.x_caddr 在e

12、xec()原语实现 exec()83行xalloc()。 P91 xalloc() :p_textp=xp。 17行,39行 xp是text数组的元素 text.x_caddr:代码段读入内存物理空间起始地址 text.x_daddr:代码段在外存交换区的地址,数据段在内存的起始块号,2)数据段的读入 proc.p_addr 是数据段在内存中的起始地址 在exec()中实现数据段的读入 94行， readi(ip) 。 P246 readi() readi()函数必须先在estabur()中设置APR eatabur()在APR页表中设置数据段的相对地址：PAR,PDR 数据段的内存分配在fo

13、rk()中实现 (a)子进程和EP进程共享代码段，则APR页表相同 (b)子进程exec新的程序，则读入新的程序而且更新APR页表 proc.p_addr=a2=malloc(coremap,n); 数据段的实际地址,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,数据,栈,执行进程的APR页表,50,241,代码段,300,第一次地址转换: (1)逻辑地址：0110001000001000 011: 页号。第三页APR3 0001000:块号

14、。第八块，相对块号。 001000：块内偏移量 (2)相对物理地址： PAR3=144,物理块号144+8-1=151,主存物理空间（fork(),PPDA,316,数据区域,栈区域,508,699,8相对块号：相对所在APR起始地址的块号,151相对块号：相对所在段起始地址的块号,第二次地址转换： 151+300=451 在物理内存中的实际块号。 字节地址： 451*64+块内偏移量,问题：为什么是*64而不是*32,sureg():将相对物理地址转换成内存物理地址,50 178,316(USIZE) 444,0 0,508 573,0 1,代码,2 3,4 5,6 7,数据,栈,UISA,

15、UISA: 内存映射技术 将寄存器映射到内存中的一个事先定义的地址。 PSW：PS，0177776 APR的PAR：UISA，0177640 PDR：UDSA，0177660,P63 例题,进程调出，APR页表的内容保存在u.u_uisa,u.u_uisd,0 128,16(USIZE) 144,0 0,208 273,0 1,代码,2 3,4 5,6 7,数据,栈,u.u_uisa,并不保存UISA和UDSA的内容。 原因是什么,P63 例题,0 128,16(USIZE) 144,0 0,208 273,0 1,代码,2 3,4 5,6 7,数据,栈,执行进程的APR页表,50,241,代

16、码段,400,主存物理空间（fork(),PPDA,416,数据区域,栈区域,608,799,8相对块号：相对所在APR起始地址的块号,151相对块号：相对所在段起始地址的块号,问题：为什么保留u.u_uisa,u.u_uisd中的相对地址，而不是UISA，UDSA中的实际物理内存地址,进程调入：代码段，有共享进程则text.x_xaddr不变，仍为50. 则数据段调入到a=400的起始地址,text.x_xaddr,proc.p_addr,重新调入内存后，P63例题的主存物理空间,50 178,416(USIZE) 544,0 0,608 673,0 1,代码,2 3,4 5,6 7,数据,栈,UISA,P63 例题,问题：为什么保留u.u_uisa,u.u_uisd中的相对地址，而不是UISA，UDSA中的实际物理内存地址？ 这个问题可以回答了。 每一次进程调出调入的物理内存起始地址不同。 所以每次保存相对地址,若进程的代码段在内存中不存在,则malloc(coremap,text.x_size+proc.p_size) 代码段和数据段相邻分配物理内存,相对块号与实际字节物理地址,实际物理地址：实际块号*64B+块内偏移量 map的长度64B，所以不是*32,2.内存的物理地址空间,以块为单位分配物理内存。 内存块长度64B，磁盘交换区块长度512B。 物