某储备粮的“学习笔记”

by 咳嗽di小鱼

这次Assignment除了Physical Memory Management, 其他几个部分都相互关联. 所以在设计完成前几部分的时候, 最好将所有需要解决的问题都搞明白, 然后统一设计Address Space的结构.

TLB Management

和TLB有关的, 需要解决的问题有这么几个:

  1. Context Switch的时候, 如果不是两个不同的thread, 则不需要flush TLB
  2. 当TLB被占满的时候, 要替换最老的TLB entry
  3. TLB内保存read-only信息

然后一个一个说…

  1. 只要检查上一次flush TLB时候的thread, 和现在的是不是同一个thread即可
  2. 这部分这次Assignment已经把code写好大半了…`你需要做的就是把tlb_get_rr_victim return回来的那个entry替换掉
  3. 理解MIPS TLB的每个flag bits的用处, 然后把read-only flag放在对应的位置.
    当程序试图写入一个read-only的memory时候, vm_fault拿到的faulttype是VM_FAULT_READONLY.
    Don't PANIC!!!

TLB基本就这么多= =||`没啥东西…

On-Demand Loading

This is the fun part…哈哈哈
这部分, 需要, 灰常严谨的逻辑和计算…`还要对page loading的步骤非常清晰. 任何一点对内存地址或者file offset的计算错误, 或者理解错误, 都会mess up.

所以, 咱们重新来列一遍从程序开始运行, 到page loading结束的整个过程:

  • runprogram/execv拿到一个progname (ELF file's path), 并call load_elf.
  • load_elf不立刻load到physical memory,
    而是把ELF中的每一个segment所对应的virtual address定义好, 并且保存load这个segment所需要的所有信息.
    (这些信息如何/以什么样的形式保存, 需要在动手之前就先明确!)
  • 当系统碰到一个TLB Miss时, 会有两种情况:
  • 这个page还没有被load到physical memory, 说明这个page是第一次被访问,

    • 找到这个page所对应的segment的信息
    • 计算load这个page所需要的所有相关数据
    • 从physical memory steal一个page的内存
    • 将这个page的数据从file load到physical memory中
      (提示: PADDR_TO_KVADDR is useful)
    • 将这个physical memory保存成这个segment vaddr对应的paddr
    • 将这对vaddr和paddr存入TLB
  • 反之, 直接将已知的一对vaddr和paddr存入TLB即可

本身, 整个过程还是很straight forward的. 可有一些special case需要handle…

  1. 有的segment不是从一个page的顶头开始的
  2. 有的segment跨越多个page
  3. 有的data segment的filesize是0, 但memsize需要填零
  4. …好像还有别的, = =想不起来了, 大家写的时候发现了, 告诉我下, 哈哈 最容易出错的部分还是计算, filesize, memsize, file offset, memory offset, 等各种数据…大家加油

Address Space

多写两句和as有关的

很多人在刚开始写这个assignment的时候, 最先纠结的就是, as的结构要不要改...
这是个好问题, 但答案是: 不一定要改as, 但肯定需要+东西.

在解释为什么之前, 咱们先来看看dumb_vm的as里, 每个东西都是干嘛用的.

struct addrspace { 
    #if OPT_DUMBVM 
        vaddr_t as_vbase1; 
        paddr_t as_pbase1; 
        size_t as_npages1; 
        vaddr_t as_vbase2; 
        paddr_t as_pbase2; 
        size_t as_npages2; 
        paddr_t as_stackpbase; 
    #else 
        /* Put stuff here for your VM system */ 
    #endif 
};

dumb_vm里只保存两个segment/region的内存信息

  • vbase是每个reg在virtual address上开始的位置
  • pbase是每个reg在physical address上开始的位置
  • npages是每一个reg一共占用了多少个virtual page/physical frame
  • stackpbase顾名思义, stack在physical address上的底是哪里

然后咱们再研究下, 可能需要记录哪些信息. (并不一定全部都需要记录, 有些可以相互计算)

为了计算写入TLB的值, 需要

  • 每个reg在virtual & physical address的开始位置
  • 每个reg有多少个page/frame
  • 每个reg的permission flags

为了On-Demand Loading, 需要

  • 当前app对应的ELF file是什么
  • 每个reg里的每个page/frame是否被load过
  • 每个reg里的每个page/frame的vaddr和paddr开始位置
  • 每个reg里的每个page/frame所对应在ELF-FILE中的program header information (例如: file offset)
  • stack已经占用了多少个page

对比一下上下两个列表, 我们缺点什么呢?
原来的as没有记录reg的permissions, 没有记录page/frame是不是被load过了, 没有分别记录每个page/frame的vaddr+paddr(当然, 可以通过seg的数据进行计算), 也没有每个reg对应的ELF信息...stack也是固定大小

所以原本的as是100%缺少东西的, 但这些额外的东西, 具体应该保存到哪里就自由发挥了.

补充1: OS161里假设了一个ELF程序只包括两个segment. 虽然实际可能不止2个, 但现阶段, 只支持2个也没问题.
更新1: 叫seg不太确切, 还是叫region好了. 另补充了一些需要记录的内容.

Physical Memory Management

在dumbvm里, Physical Memory的分配机制非常简单. 在first和last之间, 一页一页的把内存分配出去, first逐次往后移动, 直到first = last, 就没有memory可用了. 也不回收, 不重复使用.

要想改变优化这个机制, 首先需要增加一个能够tracking所有可用Physical Frame使用状态的table. 在进行malloc或者free某个frame的时候, 在table中记录下来这个frame的状态. 这样, 如果存在free过的page, 这些page就可以优先被malloc, 从而重复利用已经free了的内存.

整体流程:

  • 系统启动
  • 进入vm_bootstrap
  • 取得现在可用的Physical Memory的地址范围
  • 通过地址范围计算出有多少个可用的frame
  • 建立保存Physical Frame Status的table
  • 完成其他vm_bootstrap所需要做的工作
  • 再次取得可用的Physical Memory的地址范围, 这就是真正可用的内存范围
  • 停用原本的Physical Memory管理机制, 并接管所有alloc_kpages和free_kpages的操作
  • vm系统启动完成

除此之外, 还需要修改allocation和free时候的操作, 让alloc能够通过某种algorithm来重复使用已经被free的内存位置. (用什么样的Algorithm就看各位了, 实在不行做liner search也是方法之一, 嘿嘿)

个别要点:

  • 建立的table可能比最后实际需要的大, 但并无大碍. (因为table本身占用了一部分内存)
  • alloc_kpages的时候, 有可能需要一次alloc超过一页的frame.
    如果你使用的algorithm不方便在被free的内存中找出多个连续的frame, 那尽管把从未用过的连续frame分配出去吧.
  • 其他的待补充...


Instrumentation实在没什么好写的, 把declaration和initialization放对地方就好了.


19 comments »

  1. 梦文 梦文

    greg好人一生平安

  2. michael.. michael..

    好人一生平安,谢谢分享

  3. 杰森葱 杰森葱

    辛苦了,感谢!!

  4. 吉他 吉他

    G哥威武,永垂不朽

  5. fred fred

    经典 小心350professor= =

  6. 杰森葱 杰森葱

    Physical memory management 部分,请指点迷津

  7. skyey skyey

    final刚考完TLB - -

    1. 那应该很稳啊...哈哈哈

  8. youling youling

    大神,你452会有Note不?

    1. 452不需要Notes, 上课就可以了. 我能总结出来的东西prof上课都讲过. Prof自己的notes在这里, http://www.cgl.uwaterloo.ca/~wmcowan/teaching/cs452/w13/notes/index.html

  9. DT DT

    好人一生平安~~~喵了个咪

  10. Jerry Jerry

    我们老师上课说,你们不要去网上找资料,他说之前他google了一下发现还有用中文写的,他说他完全看不懂是什么意思,哈哈 说的就是你,你中枪了

    1. 哈哈`听说了这个事儿. 其实我也没写什么会剧透的东西, 具体怎么implemente还都要大家自由发挥.

Add new comment »

Enter your comment here...

captcha
请输入验证码