首页 > 其他分享 >Mit6.S081笔记Lab5: Lazy Page Allocation 惰性分配

Mit6.S081笔记Lab5: Lazy Page Allocation 惰性分配

时间：2024-11-04 18:43:22浏览次数：4  
标签：uint64 va Lazy pagetable sz Mit6 pte Allocation 分配

课程地址：https://pdos.csail.mit.edu/6.S081/2020/schedule.html
Lab 地址：https://pdos.csail.mit.edu/6.S081/2020/labs/lazy.html
我的代码地址：https://github.com/Amroning/MIT6.S081/tree/lazy
xv6手册：https://pdos.csail.mit.edu/6.S081/2020/xv6/book-riscv-rev1.pdf
相关翻译：http://xv6.dgs.zone/labs/requirements/lab5.html
参考博客：https://www.cnblogs.com/weijunji/p/14338483.html

Lab5: xv6 lazy page allocation

上一章的笔记中稍微提到一点的惰性分配，这次实验就来研究一下利⽤缺⻚故障实现内存分配的惰性分配策略，以及惰性分配有哪些优缺点。

​ 用户态程序通过sbrk系统调用来在堆上分配内存，而sbrk则会通过kalloc函数来申请内存页面，之后将页面映射到页表当中。当申请小的空间时，这个过程是没有问题的。但是如果当进程一次申请很大的空间，如数GB的空间，再使用上述策略来一页页地申请映射的话就会非常的慢（1GB/4KB=262,144）。这时候就引入了lazy allocation技术，当调用sbrk时不进行页面的申请映射，而是仅仅增大堆的大小，当实际访问页面时，就会触发缺页异常，此时再申请一个页面并映射到页表中，再次执行触发缺页异常的代码就可以正常读写内存了。

​ 通过lazy allocation技术，就可以将申请页面的开销平摊到读写内存当中去，在sbrk中进行大量内存页面申请的开销是不可以接受的，但是将代价平摊到读写操作当中去就可以接受了。

​

Lab

仅复制部分题目，完整要求请去该帖子顶部链接查看

Eliminate allocation from sbrk() (easy)

你的首项任务是删除sbrk(n)系统调用中的页面分配代码（位于sysproc.c中的函数sys_sbrk()）。sbrk(n)系统调用将进程的内存大小增加n个字节，然后返回新分配区域的开始部分（即旧的大小）。新的sbrk(n)应该只将进程的大小（myproc()->sz）增加n，然后返回旧的大小。它不应该分配内存——因此您应该删除对growproc()的调用（但是您仍然需要增加进程的大小！）。

实现lazy page allocation的第一步，只记录分配了多少内存，但是不做实际的分配。

改动系统调用sys_sbrk，不再调用分配内存的growproc，仅让进程的sz加上新增的内存

// kernel/sysproc.c
uint64
sys_sbrk(void)
{
  int addr;
  int n;

  if(argint(0, &n) < 0)
    return -1;
  addr = myproc()->sz;

  /*if(growproc(n) < 0)     // 惰性分配
    return -1;*/

  struct proc* p = myproc();

  if (n > 0)                                  //惰性分配，这里仅改变sz字段
      p->sz += n;                       
  else if (p->sz + n > 0)              //如果是减少内存，还是要马上执行,要检查减去内存后是否大于0
      p->sz = uvmdealloc(p->pagetable, p->sz, p->sz + n);
  else
      return -1;

  return addr;
}

这个时候可以启动xv6执行一个简单的命令，可以发现会报错panic: uvmunmap: not mapped，系统未给进程分配内存：

$ echo hi
usertrap(): unexpected scause 0x000000000000000f pid=3
            sepc=0x00000000000012ac stval=0x0000000000004008
panic: uvmunmap: not mapped

Lazytests and Usertests (moderate)

修改trap.c中的代码以响应来自用户空间的页面错误，方法是新分配一个物理页面并映射到发生错误的地址，然后返回到用户空间，让进程继续执行。您应该在生成“usertrap(): …”消息的printf调用之前添加代码。你可以修改任何其他xv6内核代码，以使echo hi正常工作。

​ 接下来修改usertrap函数，处理缺页异常。r_scause可以获取异常原因，其中13表示page load fault，15表示page write fault，stval表示引发缺页异常的虚拟地址，缺页异常就可以由(r_scause() == 13 || r_scause() == 15)表示。

​ 先判断发生错误的虚拟地址是否位于栈空间之上，进程大小之下（虚拟地址从0开始，进程大小可以表示进程的最高虚拟地址），然后为其分配物理内存并添加映射：

// kernel/trap.c
void
usertrap(void)
{
  ......
  } else if((which_dev = devintr()) != 0){
    // ok
  }
  else if (r_scause() == 13 || r_scause() == 15) {      // 惰性分配导致的缺页异常
      uint64 fault_va = r_stval();      // 获取引发缺页异常的虚拟地址
      char* pa = 0;                     // 分配的物理地址
      // 判断fault_va是否在进程栈空间之中
      if (PGROUNDUP(p->trapframe->sp) - 1 < fault_va && fault_va < p->sz && (pa = kalloc()) != 0) {
          memset(pa, 0, PGSIZE);
          // 物理内存映射
          if (mappages(p->pagetable, PGROUNDDOWN(fault_va), PGSIZE, (uint64)pa, PTE_R | PTE_W | PTE_X | PTE_U) != 0) {      
              printf("lazy alloc: failed to map page\n");
              kfree(pa);
              p->killed = 1;
          }
      }
  }else {
    printf("usertrap(): unexpected scause %p pid=%d\n", r_scause(), p->pid);
    printf("            sepc=%p stval=%p\n", r_sepc(), r_stval());
    p->killed = 1;
  }

  ......
}

惰性分配刚开始并未实际分配内存，遇到解除映射关系时直接跳过这部分内存，不然会导致系统崩溃：

// kernel/vm.c
void
uvmunmap(pagetable_t pagetable, uint64 va, uint64 npages, int do_free)
{
  ......

  for(a = va; a < va + npages*PGSIZE; a += PGSIZE){
      if ((pte = walk(pagetable, a, 0)) == 0)
          //   panic("uvmunmap: walk");     惰性分配，遇到不存在的页表项就跳过
          continue;
      if ((*pte & PTE_V) == 0)
          //   panic("uvmunmap: not mapped");   同上
          continue;
      if (PTE_FLAGS(*pte) == PTE_V)
          panic("uvmunmap: not a leaf");
      if(do_free){
          uint64 pa = PTE2PA(*pte);
          kfree((void*)pa);
  }
    *pte = 0;
  }
}

这个时候再启动xv6，执行echo hi，就可以正常运行了

Lazytests and Usertests (moderate)

我们为您提供了lazytests，这是一个xv6用户程序，它测试一些可能会给您的惰性内存分配器带来压力的特定情况。修改内核代码，使所有lazytests和usertests都通过。

  • 处理sbrk()参数为负的情况。
  • 如果某个进程在高于sbrk()分配的任何虚拟内存地址上出现页错误，则终止该进程。
  • 在fork()中正确处理父到子内存拷贝。
  • 处理这种情形：进程从sbrk()向系统调用（如read或write）传递有效地址，但尚未分配该地址的内存。
  • 正确处理内存不足：如果在页面错误处理程序中执行kalloc()失败，则终止当前进程。
  • 处理用户栈下面的无效页面上发生的错误。

sbrk()参数为负的情况上面已处理

使用分配的虚拟内存时注意检查是否在进程空间中（PGROUNDUP(p->trapframe->sp) - 1 < va && va < p->sz）

fork会调用uvmcopy进行内存拷贝，惰性分配会导致读取到未分配的pte，所以要进行处理：

// kernel/vm.c
int
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
  ......

  for(i = 0; i < sz; i += PGSIZE){
      if ((pte = walk(old, i, 0)) == 0)
          // panic("uvmcopy: pte should exist");    惰性分配导致某些pte未分配，遇到不存在的pte就跳过
          continue;
      if ((*pte & PTE_V) == 0)
          // panic("uvmcopy: page not present");    同上
          continue;
      pa = PTE2PA(*pte);
      ......
}

这里设计两个函数，（1）uvmshouldallocate：检测一个虚拟地址是不是因为惰性分配还没分配和映射的地址。（2）uvmlazyallocate：给虚拟地址分配和映射物理内存

其中，uvmshouldallocate要检测的有：

  • 处于 [0, p->sz)地址范围之中（进程申请的内存范围）
  • 不是栈的 guard page（见 xv6手册，栈页的低一页故意留成不映射，作为哨兵用于捕捉 stack overflow 错误。惰性分配不应该给这个地址分配物理页和建立映射，而应该直接抛出异常）
    （解决 usertests 中的 stacktest 失败的问题）
  • 页表项不存在

uvmshouldallocate：

//判断页面是否是之前惰性分配的地址，是的话返回1
int uvmshouldallocate(uint64 va) {
    pte_t* pte;
    struct proc* p = myproc();

    return va < p->sz                   //确保地址在进程的内存大小范围内
        && PGROUNDDOWN(va) != r_sp()    //确保地址不在 guard page 中
        && (((pte = walk(p->pagetable, va, 0)) == 0) || ((*pte & PTE_V) == 0));     //确保页表项确实不存在
}

uvmlazyallocate：

//给惰性分配的页面分配并映射物理地址
void uvmlazyallocate(uint64 va) {
    struct proc* p = myproc();
    char* pa = kalloc();    //分配物理地址
    if (pa == 0) {
        printf("lazy alloc: out of memory\n");
        p->killed = 1;
    }
    else {
        memset(pa, 0, PGSIZE);
        if (mappages(p->pagetable, PGROUNDDOWN(va), PGSIZE, (uint64)pa, PTE_W | PTE_X | PTE_R | PTE_U) != 0) {      //映射物理地址
            printf("lazy alloc: failed to map page\n");
            kfree(pa);
            p->killed = 1;
        }
    }
}

由于惰性分配的页，在刚分配的时候是没有对应的映射的，所以要把一些原本在遇到无映射地址时会 panic 的函数的行为改为直接忽略这样的地址。

vm.c中的uvmunmap：

void
uvmunmap(pagetable_t pagetable, uint64 va, uint64 npages, int do_free)
{
  ......

  for(a = va; a < va + npages*PGSIZE; a += PGSIZE){
      if ((pte = walk(pagetable, a, 0)) == 0)
          //   panic("uvmunmap: walk");     惰性分配，遇到不存在的页表项就跳过
          continue;
      if ((*pte & PTE_V) == 0)
          //   panic("uvmunmap: not mapped");   同上
          continue;
      ......
  }
}

vm.c中的uvmcopy：

int
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
  ......

  for(i = 0; i < sz; i += PGSIZE){
      if ((pte = walk(old, i, 0)) == 0)
          // panic("uvmcopy: pte should exist");    惰性分配导致某些pte未分配，遇到不存在的pte就跳过
          continue;
      if ((*pte & PTE_V) == 0)
          // panic("uvmcopy: page not present");    同上
          continue;
      ......
}

vm.c中的copyin 和 copyout，如果遇到没分配的虚拟地址就马上分配：

int
copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len)
{
  uint64 n, va0, pa0;

  if (uvmshouldallocate(dstva))
      uvmlazyallocate(dstva);

  ......
}

int
copyin(pagetable_t pagetable, char *dst, uint64 srcva, uint64 len)
{
  uint64 n, va0, pa0;

  ......
}

现在可以执行./grade-lab-lazy lazytests和./grade-lab-lazy usertests验证实验是否正确了

标签：uint64,va,Lazy,pagetable,sz,Mit6,pte,Allocation,分配
From： https://www.cnblogs.com/Amroning/p/18525985

相关文章

  • Mit6.S081笔记Lab3: page tables 页表
    课程地址：https://pdos.csail.mit.edu/6.S081/2020/schedule.htmlLab地址：https://pdos.csail.mit.edu/6.S081/2020/labs/pgtbl.html我的代码地址：https://github.com/Amroning/MIT6.S081/tree/pgtbl相关翻译：http://xv6.dgs.zone/labs/requirements/lab3.html参考博客：https://ww......
  • Mit6.S081笔记Lab2: system calls 系统调用
    课程地址：https://pdos.csail.mit.edu/6.S081/2020/schedule.htmlLab地址：https://pdos.csail.mit.edu/6.S081/2020/labs/syscall.html我的代码地址：https://github.com/Amroning/MIT6.S081/tree/syscall相关翻译：http://xv6.dgs.zone/labs/requirements/lab2.html参考博客：https:......
  • 线段树？Lazytag?
    本文导读：本博客主要介绍了线段树的原理和构造的过程，以及一些例题，如果有不足的点，欢迎指出qwq.线段树\((1)_{36}\):什么是线段树？作为一个蒟蒻qwq，看到"线段树"三个字时，你想到了什么？蒟蒻：我知道！不就是"线段+树"吗！......作者：哎呀，你到底在说什么，还是我来解释吧...1.线段树......
  • 循序渐进丨MogDB 数据库查询重写规则lazyagg详解
    问题概述在MogDB和openGauss中，参数rewrite_rule用于控制查询重写，本文介绍查询重写规则lazyagg。在未设置rewrite_rule=lazyagg的情况下，子查询中有GROUPBY会先进行GROUPBY；lazyagg表示延迟聚合运算，目的是消除子查询中的聚合运算，先关联再GROUPBY；当子查询中有GROUPBY，子......
  • lazy_loader attach_stub一种变体玩法
    此方法在scikit-image包中可以明显看到使用玩法流程__init__.py直接基于attach_stub进行定义懒加载，以后的使用就同时标准玩法了添加__init__.pyi进行显示的引入定义，方便实现类型检查以及ide的自动提示一个参考玩法__init__.py定义importlazy_loaderasla......
  • lazy_loader python 子包以及函数懒加载框架
    lazy_loaderpython子包以及函数懒加载框架,内部处理上是基于了importlib.import_module进行动态加载包含的特性可以确保子模块对于用户的可见行，不引起而外的开销允许外部库在使用的时候被加载，提升导入时间说明此包在kedro的datasets模块中使用比较多，基本上每个datase......
  • 17_document的全量替换、强制创建以及图解lazy delete机制
    1、document的全量替换2、document的强制创建3、document的删除1、document的全量替换（1）语法与创建文档是一样的，如果documentid不存在，那么就是创建；如果documentid已经存在，那么就是全量替换操作，替换document的json串内容（2）document是不可变的，如果要修改document的内容，第一种......
  • COMP 412 Local Register Allocation Table of Contents
    COMP412,Fall2024Lab2:LocalRegisterAllocationTableofContentsCriticalDatesfortheProjectIntroductionCodeDueDate10/23/2024OverviewoftheProblemCodeCheck#1Due10/04/2024CodeSpecification3IntroductionInthisprogrammingass......
  • MIT6.824 课程-Aurora
    Aurora原文：https://xie.infoq.cn/article/09849d56c3b18064af6c7f857搬运用于参考学习ABSTRACTAmazonAurora是一个关系型数据库服务，其作为AmazonWebServices(AWS)的一部分为OLTP业务提供服务。本文描述了Aurora的体系结构以及设计该结构时的一些思考。我们认为高吞......
  • CF2005C Lazy Narek
    记录dp的设计。一开始设计的是f[i][j]表示最后一个选i，匹配到j的最大值，然而这样转移是\(n^2\)的，题目要求\(n*m\).设计成0，1背包，考虑第i个选择或者不选择即可。#include<bits/stdc++.h>usingnamespacestd;constintN=1e3+11;intf[N][6];intlef[N][6],val[N][6],to[N......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99