操作系统-lazy allocation

只有真正需要使用这些页的时候才进行物理内存页的实际分配sbrk()在xv6操作系统中,进程的用户内存布局由代码段(text)、数据段(data)、堆区(heap)和栈区(stack)组成。sbrk()主要修改的是堆区的大小,堆在xv6中由低地址向高地址拓展。当程序调用sbrk(n)时,操作系统内核会完成下面的这些过程:1. 首先通过 p-sz 获取当前堆区的起始位置;2. 通过传入的参数 n 计算新的大小 new _sz szn3. 这里传入的参数n 分为2种情况,如果a.n0内核需要为这n个字节的区域分配新的物理内存页,然后更新进程的页表,同时将这些新物理页映射到从 p-sz到 p-szn之间的虚拟地址空间p-szb.n0:此时就代表着释放 new_sz和sz 之间的物理内存页,然后从页表中移除对应的映射关系4. 完成前面的步骤后,需要更新进程控制块(PCB)中记录的进程大小,即p-sz的值应该是new_sz5.最后返回原来的进程大小 sz,因为这个地址是新分配的内存区域的起始地地址sys_sbrk()首先获取到用户输入的n字节后,也使用addr 来存储原始的进程大小(这个也是新分配内存的起始地址),然后会调用growproc来执行具体的内存拓展操作,注意最后返回的是addruint64 sys_sbrk(void) { int addr; // 获取用户输入的字节数 int n; if(argint(0, n) 0) return -1; addr myproc()-sz; if(growproc(n)0) //这里是调用内部函数 growproc来执行实际的内存增长或者收缩的功能 return -1; return addr; }growproc()growproc(n)的定义在 proc.c中 , 它的主要作用是在以n个字节大小为基础修改进程的用户内存空间,这里就会涉及到 n 的大小分为 n0/n0a.n 0此时计算出新旧大小,采用 uvmalloc(p-pagetable, oldsz, newsz),从旧的边界sz 开始,到新的边界szn 结束,然后为这段新的虚拟地址范围调用 kalloc分配物理内存页,同时分配到的物理页会清零,然后更新进程的页表(p-pagetable)建立新的虚拟地址和新的物理地址之间的映射,同时去设置对应的权限(也就是之前提过的PTE_W|PTE_R|PTE_U)。b.n0如果n0 表示需要释放尾部的内存空间,这里使用的核心是调用 uvmdealloc(p-pagetable,oldsz,newsz),负责扫描从新的边界sz n 开始,到旧的边界 sz结束的虚拟地址范围,然后在进程页表(p-pagetable)中解除虚拟地址与物理地址的映射,然后将对应的物理地址使用kfree 释放并回收。int growproc(int n) { uint sz; struct proc *p myproc(); sZ p-sz; if(n 0){ if((sz uvmalloc(p-pagetable, sz, sz n)) 0) { return -1; } } else if(n 0){ sZ uvmdealloc(p-pagetable, sz, sz n); } p-sz sz; return 0; }虚拟地址空间预留(Virtual Address Space Reservation)当用户程序请求内存时(比如调用 sbrk(n)扩展堆),操作系统立即更新进程的页表,为这n 字节的内存创建虚拟地址到物理地址的映射,但这些映射的页表项(PTE)被标记为“无效”或“不可访问”。这里操作系统只是在页表中为这n个字节预留了一个映射的位置,页表的数据结构中有了虚拟地址对应的条目,但是并不会指向任何有效的物理页帧,没有分配实际的物理内存。只有当发生了缺页中断时,操作系统才会在内核中执行 kalloc 分配一个物理页帧。然后再去更新对应的页表项PTE,并将 PTE 对应的有效位设置为1。缺页中断(Page Fault)触发程序执行时,第一次尝试访问预留的虚拟地址空间中的某个地址时(比如,刚刚新分配了一个堆内存,现在进行读写),这个地址对应的PTE 是无效或者不可访问的,CPU会立即触发一个缺页中断(Page Fault)。此时CPU会从用户模式切换到内核模式,并跳转到操作系统的缺页中断处理函数中。按需分配物理内存在用户触发缺页中断之后,CPU进行中断的处理,操作系统会检查导致这个缺页中断的虚拟地址,确认这个虚拟地址是否属于预留的合法地址(未分配实际的物理内存),然后分配一个实际的空闲物理页帧,接着更新进程的页表,将缺页的虚拟地址映射到刚刚分配的物理页帧上,并且将PTE标记为有效设置正确的读写权限。如果是匿名页,则新分配的物理页会被清零。完成这些操作之后,缺页中断处理函数会返回,然后CPU可以重新开始执行用户指令。此时页表已经更新了,访问可以成功。Lazy allocation在申请小空间时,程序通过 sbrk 调用在堆上分配内存,并且通过kalloc 函数申请内存页面,之后将页面映射到页表当中。但是当申请很大的空间时,按照这个方式就会很慢,这里采用lazy allocation 的方式,当调用sbrk 时不进行页面的申请映射,而是仅仅增大了堆的大小,当实际访问页面时,触发了缺页异常,此时再申请一个页面并映射到页表中,然后再次执行缺页异常的代码就可以正常读写内存了,通过这种方式将申请内存页面的开销分摊到读写内存中是我们可以接受的。Eliminate allocation from sbrk原理sbrk(n)的原始功能是增加n 个字节的进程内存,返回新分配区域的起始地址,原来的堆大小 old_size。要求我们修改之后的 sys_sbrk()需要只增加进程的内存大小(myproc()-sz)n 个字节,即更新进程的虚拟地址空间边界,然后返回旧的内存大小(old_size),不应该分配任何物理内存。直接进行修改即可跳过growproc的过程uint64 sys_sbrk(void) { int n; uint64 sz; struct proc *p myproc(); if(argint(0, n) 0) return -1; sz p-sz; // 如果是正数打白条只加数字不分配内存 if (n 0) { p-sz n; } // 如果是负数缩小内存老老实实调用原函数释放内存 else if (n 0) { if(growproc(n) 0) return -1; } return sz; // 返回旧的 size }当n 0时申请扩张可以骗程序向内核要内存。内核只要把虚拟边界p-sz往上提就算是完成了任务。 在这个阶段没有任何真实的物理资源被浪费。物理内存还乖乖地躺在操作系统的仓库里。直到程序真的去写这个地址内核才会抠抠搜搜地掏出一页物理内存给它当n 0时如果这个时候内核也“偷懒”仅仅是把虚拟边界p-sz往下划p-sz n会发生极其恐怖的事情物理内存被永远弄丢了Memory Leak 在那块被缩小的区域里可能已经存在之前因为缺页中断而分配好的真实的物理内存页。如果你只改数字不去把那些物理页kfree掉这些物理内存就成了“孤儿”。两头不认账 * 程序那边因为p-sz变小了以后再访问这些地址会报越界错误所以程序用不了这块内存了。操作系统那边因为你没调用释放函数系统以为这些内存还在被该进程占用也不会把它分给别人。结果 这块极其宝贵的物理内存就永远地消失在宇宙中了随着程序不断扩大又缩小操作系统的物理内存很快就会被彻底榨干最终死机。Lazytests and Usertests现在需要xv6能够相应用户空间的 page fault并且在page fault 发生时惰性分配一个新的物理页并建立映射,然后返回程序继续执行。第一步在usertrap函数中处理page fault情况r_scause() 13 / 15(读缺页写缺页)找到这个虚拟地址判断是否在p-sz的范围内并申请物理内存与其进行映射第二步大体修改完成现在完成“细枝末节”不容易想到并且会出bug的地方假设我们在lazy allocation中分配了一些物理页但还是有一些“白条”我们没有分配当我们调用uvmunmap函数时就会报错这个函数是用来解除虚拟内存与物理内存之间的映射的。我们之前本来就没有映射所以在uvmunmap函数中跳过那些没有设置有效位PTE_V的页表项第三步当调用fork时子进程会完全复制父进程但我们不需要完全复制全部的页表项只复制已经分配的物理地址就行没有分配的物理地址就忽略。所以修改uvmcopy()第四步当系统调用read、write时在内核态运行可能去访问这个不存在的物理地址不会触发中断所以我们要对walkaddr进行修改在访问到不存在的物理地址时要把物理内存垫上第五步当调用exit退出进程时会调用freewalk来递归释放存储页表本身的页内存在迟延时分配的环境下freewalk会出现两种情况由于我们的延迟分配机制和uvmunmap的清理是针对整个p-sz区域进行的,告诉内核这是一个有效的叶子节点,但是假设在前面已经被处理过了,这里不需要处理也就是不需要 panic了只要保证它被清零然后释放页表结构本身就行。