《内存管理数据结构》PPT课件.ppt

内存管理数据结构,2015.3.31星期二（单周）2015.4.7星期二（双周）,掌握内存管理的数据结构,程序的页表MMU的APRU区的u.u_uisa16,u.u_uisd16内存的空白区域structmap,一、程序的内存组织方法,Staticchar*class=host;/标题页上的类名Staticcharformat=f;/打印文件用的格式字符Staticcharhdr=1;/是否打印标题,已经初始化的数据,Staticchar*dfname;/数据文件Staticchar*fonts4;/troff字体名Staticchariflag;/需要的缩进,未初始化的数据bss,程序,Staticchar*lmktemp(char*id,intnum,intlen)char*s;if(s=malloc(len)=NULL)fatal2(“outofmemory”);(void)snfrintf(s,len,”%s%A%03d%S”,SD,id,num,host);,程序参数栈区域,局部变量栈区域,堆,代码,Linux虚拟存储器管理,与进程相关的数据结构（页表，task,mm结构，内核栈）,物理存储器,内核代码和数据,每个进程不同,每个进程相同,用户栈,共享库的存储器映射区域,运行时堆（malloc分配）,未初始化数据.bss,已初始化数据.data,程序文件(.text),0 x08048000(32)0 x0040000(64),brk,%esp,内核虚拟存储器,进程虚拟存储器,二、UNIXV6内存管理,(1)页表内存的分页管理(paging)：把每个程序的地址空间分成大小相等的片，称之为页面或者页(page)；内存的存储空间分成与页大小相同的片，称为页框(pageframe),为进程分配存储空间时，以页为单位。MMU为进程的每一个页面分配一个寄存器，这些寄存器组成一个表，称为页表页表的硬件实现有多种方法，用一组专用寄存器存放页表。PDP-11/40使用APR，高速逻辑电路构造，有效进行分页地址的转换。由于对内存的每次访问都要经过页表，因此效率很重要。,Unixv6的页表用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地址和总线物理地址,总线18位，所以内存物理地址218=4*64k=256k。P5所以内存最多可存放4个完整的进程地址空间。P23实际上，一般情况是，执行进程的整个地址空间在内存中，而不在CPU上执行的进程，将它的数据段调出到交换区（交换文件），只有一部分进程映像在内存，可提高内存的利用率。,UNIXV6进程页表的硬件实现,PDP-11/40的APR页表是页面与块两级结构。页面长度8k,这是CPU字长决定的。每个页面分成128块，块的长度64B.块是存储分配的基本单位PDP-11/46的页表包括8个页面，maxmem表示页表中最多块数。APR(activepageregister)寄存器一共有8组，每组APR由1个PAR(pageaddressregister)和1个PDR(pagedescriptionregister)寄存器构成，PAR07,PDR07。,UNIXV6进程页表的硬件实现,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,13,12,6,5,0,页号APR,块号,块内偏移量,15,12,11,0,PARi块号起始地址,+,块号,块内偏移量,P25,执行进程uP26,执行进程U区，全局变量u(0140000)在内核PAR6的起始地址Proc.p_addr=PAR6,内核APR,0,1,2,3,4,5,6u,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,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示例qaqrfrqwertP,当进程的代码段，数据区域，栈区域的长度约为192*64字节时，用户APR的状态,0128,16(USIZE)144,00,208273,01,代码,23,45,67,数据,栈,起始块号,127RO只读64RO,127RW64RW,00,64RWED127RW,01,23,45,67,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块，则数据段的数据区域最后一块的块号是16+192-1=207。(3)栈区域在数据段中，在数据区域之后连续分配，因此在数据段的第208块开始分配，总块数192，栈区域的ED要求在APR7开始分配。若栈区域最后一块的块号400，则PAR7=400，PAR6=400-128+1=273.因此实际上最后一块的块号是399。,（4）UNIXV6的段页式管理,段表,代码段,数据段栈区域）,Text.x_caddr(proc.p_textp),proc.p_addr,Sep=0,代码段和数据段在在同一个页表中管理。现代OS，每一个段有自己的一个页表。,在物理内存中的地址,二、地址转换,地址变换：程序的逻辑地址变换为主存的物理地址,0128,16(USIZE)144,00,208273,01,代码,23,45,67,数据,栈,执行进程的APR页表,1.从ARP页表中可知，程序的代码段、数据段从0块号开始。2.进程的数据段有PPDA（系统数据区），因此可执行文件实际从数据段的块号16开始分配主存的地址空间。数据段的块号0,15保存PPDA。3.栈区域从进程地址空间的最高地址开始分配。栈区域的脚地址=数据区域脚地址+栈区域长度ns。,1.程序的执行exec(),程序在执行时，需将程序的可执行文件从块设备读取至内存(1)代码段的读入程序的代码段所在地址text.x_caddr在exec()原语实现exec()83行xalloc()。P91xalloc():p_textp=xp。17行,39行xp是text数组的元素text.x_caddr:代码段读入内存物理空间起始地址text.x_daddr:代码段在外存交换区的地址,数据段在内存的起始块号,(2)数据段的读入proc.p_addr是数据段在内存中的起始地址在exec()中实现数据段的读入94行，readi(ip)。P246readi()readi()函数必须先在estabur()中设置APReatabur()在APR页表中设置数据段的相对地址：PAR,PDR数据段的内存分配在fork()中实现(a)子进程和EP进程共享代码段，则APR页表相同(b)子进程exec新的程序，则读入新的程序而且更新APR页表proc.p_addr=a2=malloc(coremap,n);数据段的实际地址,P63例题,text.x_caddr=50proc.p_addr=300则进程的主存地址空间,0128,16(USIZE)144,00,208273,01,代码,23,45,67,数据,栈,执行进程的APR页表,50,241,代码段,300,第一次地址转换:(1)逻辑地址：0110001000001000011:页号。第三页APR30001000:块号。第八块，相对块号。001000：块内偏移量(2)相对物理地址：PAR3=144,物理块号144+8-1=151,主存物理空间（fork()）,PPDA,316,数据区域,栈区域,508,699,8相对块号：相对所在APR起始地址的块号。,151相对块号：相对所在段起始地址的块号。,第二次地址转换：151+300=451在物理内存中的实际块号。字节地址：451*64+块内偏移量,问题：为什么是*64而不是*32？,sureg():将相对物理地址转换成内存物理地址,50178,316(USIZE)444,00,508573,01,代码,23,45,67,数据,栈,UISA,UISA:内存映射技术将寄存器映射到内存中的一个事先定义的地址。PSW：PS，0177776APR的PAR：UISA，0177640PDR：UDSA，0177660,P63例题,进程调出，APR页表的内容保存在u.u_uisa,u.u_uisd,0128,16(USIZE)144,00,208273,01,代码,23,45,67,数据,栈,u.u_uisa,并不保存UISA和UDSA的内容。原因是什么？,P63例题,0128,16(USIZE)144,00,208273,01,代码,23,45,67,数据,栈,执行进程的APR页表,50,241,代码段,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例题的主存物理空间,50178,416(USIZE)544,00,608673,01,代码,23,45,67,数据,栈,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。物理内存的一个时刻包括：进程，空白区。进程是已经分配的物理内存区域。空白区是多个空白块组成的区域。进程内存空间的管理用APR页表空白区的管理用coremap数组,空白区的管理coremap,coremap的每一个元素map，包括：空白区起始块号，长度（块数）。数组中的元素总是按相对地址从低到高排列。,coremap,起始块号X长度Y,起始块号X长度Y,起始块号X长度Y,起始块号X长度Y,coremap数组有4个元素，coremap0,coremap1,coremap2,coremap3,物理内存,