OS161 Memory Management

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

TLB Management

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

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

然后一个一个说…

只要检查上一次flush TLB时候的thread, 和现在的是不是同一个thread即可
这部分这次Assignment已经把code写好大半了…`你需要做的就是把tlb_get_rr_victim return回来的那个entry替换掉
理解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…

有的segment不是从一个page的顶头开始的
有的segment跨越多个page
有的data segment的filesize是0, 但memsize需要填零
…好像还有别的, = =想不起来了, 大家写的时候发现了, 告诉我下, 哈哈最容易出错的部分还是计算, 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放对地方就好了.