绍兴手机网站建设,网站开发的论文,成都成立公司,岳麓区网站建设【MTI 6.S081 Lab】Copy-on-write The problemThe solutionImplement copy-on-write fork (hard)实验任务Hints解决方案问题解决思考uvmcopykfreekallockpagerefcow_handlertrap 虚拟内存提供了一定程度的间接性#xff1a;内核可以通过将PTE标记为无效或只读来拦截内存引用内核可以通过将PTE标记为无效或只读来拦截内存引用从而导致页面错误并可以通过修改PTE来更改地址的含义。在计算机系统中有一种说法任何系统问题都可以通过一定程度的间接性来解决。这个实验室探索了一个例子copy-on-write fork
The problem
xv6中的fork系统调用将父进程的所有用户空间内存复制到子进程中。如果父对象很大则复制可能需要很长时间。更糟糕的是这项工作经常被大量浪费fork通常在子进程中后跟exec这会丢弃复制的内存通常不会使用大部分内存。另一方面如果父进程和子进程都使用复制的页面并且其中一个或两个都写入则确实需要复制。‘
The solution
实现写时复制COWfork的目标是推迟分配和复制物理内存页直到实际需要副本如果有的话。突然安排
COW fork只为子进程创建一个页表用户内存的PTE指向父进程的物理页面。COW fork将父进程和子进程中的所有用户PTE标记为只读。当任一进程尝试写入其中一个COW页面时CPU将强制执行页面故障。内核页面错误处理程序检测到这种情况为出错进程分配一页物理内存将原始页面复制到新页面中并修改出错进程中的相关PTE以引用新页面这一次PTE标记为可写。当页面错误处理程序返回时用户进程将能够写入页面的副本。
COW fork使得释放实现用户内存的物理页面变得有点棘手。一个给定的物理页面可能被多个进程的页面表引用并且只有当最后一个引用消失时才应该释放。在像xv6这样的简单内核中这种记账相当简单但在生产内核中这可能很难做到正确例如请参阅Patching until the COWs come home.
Implement copy-on-write fork (hard)
实验任务
你的任务是在xv6内核中实现copy-on-write fork。如果修改后的内核成功地执行了cowtest和“usertests-q”程序那么就完成了。
为了帮助你测试你的实现我们已经提供了一个xv6程序叫做cowtest。cowtest运行不同的测试但是在未修改xv6的情况下第一个测试都会失败。
$ cowtest
simple: fork() failed”simple“测试分配超过一半可用的物理内存然后fork。fork失败的原因是没有足够的物理内存分配给子进程去完整的copy父进程的所有内存。
但你完成这个实验后你的内核应该能通过所有的cowtest和usertests -q的测试。
$ cowtest
simple: ok
simple: ok
three: zombie!
ok
three: zombie!
ok
three: zombie!
ok
file: ok
ALL COW TESTS PASSED
$ usertests -q
...
ALL TESTS PASSED这是一个合理的攻击计划。
修改uvmcopy将父进程的物理页面映射到子进程而不是分配新页面。清除已设置PTE_W的页的子进程和父进程PTE中的PTE_W。修改usertrap以识别页面错误。当最初可写入的COW页面出现写入页面错误时使用kalloc分配一个新页面将旧页面复制到新页面然后在PTE_W设置的PTE中安装新页面。最初只读的页面未映射PTE_W如文本段中的页面应保持只读并在父进程和子进程之间共享试图写入这样一个页面的进程应该被终止。确保每个物理页在最后一个PTE引用消失时都被释放而不是之前。实现这一点的一个好方法是为每个物理页面保留引用该页面的用户页面表数量的“引用计数”。当kalloc分配页面时将页面的引用计数设置为1。当fork导致子级共享页面时增加页面的引用数每当任何进程将页面从其页面表中删除时减少页面的计数。只有当引用计数为零时kfree才应将页面放回空闲列表。将这些计数保存在一个固定大小的整数数组中是可以的。您必须制定出一个方案说明如何索引数组以及如何选择其大小。例如您可以用页面的物理地址除以4096对数组进行索引并通过kalloc.c中的kinit为数组指定一个元素数该元素数等于自由列表中任何页面的最高物理地址。您可以随意修改kalloc.c例如kalloc和kfree以保持引用计数。当遇到COW页面时修改copyout以使用与页面错误相同的方案。
Hints
对于每个PTE有一种方法来记录它是否是COW映射可能是有用的。为此您可以使用RISC-V PTE中的RSW保留用于软件位。usertests -q探索了cowtest没有测试的场景所以不要忘记检查所有测试都通过了。一些有用的宏和页表标志的定义在kernel/rescv.h的末尾。如果发生COW页面故障并且没有可用内存则应终止进程。
解决方案
问题解决思考 用一位代表是否是COW页面。因为只读页面不存在COW的问题所以只要对可写页面进行COW映射即可。 第九位代表是否是COW页面也即 #define PTE_C (1L 8)页表需要创建。也即至少需要三个页表页 蹦床页面每次fork都在allocproc中分配了所以我们不用管蹦床页面 usertrap中确定页面错误的类型 在SCAUSE注Supervisor cause寄存器保存了trap机制中进入到supervisor mode的原因寄存器的介绍中有多个与page fault相关的原因。比如 13表示是因为load引起的page fault15表示是因为store引起的page fault12表示是因为指令执行引起的page fault。 XV6内核会打印出错的虚拟地址并且这个地址会被保存在STVAL寄存器中所以要更新SVAL所指虚拟地址中物理页面。
uvmcopy
// Given a parent processs page table, copy
// its memory into a childs page table.
// Copies both the page table and the
// physical memory.
// returns 0 on success, -1 on failure.
// frees any allocated pages on failure.
int
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{pte_t *pte;uint64 pa, i;uint flags;// char *mem;for(i 0; i sz; i PGSIZE){if((pte walk(old, i, 0)) 0)panic(uvmcopy: pte should exist);if((*pte PTE_V) 0)panic(uvmcopy: page not present);pa PTE2PA(*pte);flags PTE_FLAGS(*pte);// if((mem kalloc()) 0)// goto err;// memmove(mem, (char*)pa, PGSIZE);// if(mappages(new, i, PGSIZE, (uint64)mem, flags) ! 0){// kfree(mem);// goto err;// }if ((flags PTE_C) || (flags PTE_W)) {flags (flags (~PTE_W)) | PTE_C;*pte (*pte (~PTE_W)) | PTE_C;}if(mappages(new, i, PGSIZE, (uint64)pa, flags) ! 0){goto err;}kpageref(pa, 1);}return 0;err:uvmunmap(new, 0, i / PGSIZE, 1);return -1;
}kfree
// Free the page of physical memory pointed at by pa,
// which normally should have been returned by a
// call to kalloc(). (The exception is when
// initializing the allocator; see kinit above.)
void
kfree(void *pa)
{struct run *r;if(((uint64)pa % PGSIZE) ! 0 || (char*)pa end || (uint64)pa PHYSTOP)panic(kfree);int idx (uint64)pa / PGSIZE;acquire(pageref.lock);int count pageref.count[idx];if (count 1) { // 还有大于一个在引用直接返回即可pageref.count[idx]--;release(pageref.lock);return;}pageref.count[idx] 0;release(pageref.lock);// Fill with junk to catch dangling refs.memset(pa, 1, PGSIZE);r (struct run*)pa;acquire(kmem.lock);r-next kmem.freelist;kmem.freelist r;release(kmem.lock);
}kalloc
// Allocate one 4096-byte page of physical memory.
// Returns a pointer that the kernel can use.
// Returns 0 if the memory cannot be allocated.
void *
kalloc(void)
{struct run *r;acquire(kmem.lock);r kmem.freelist;if(r) {kmem.freelist r-next;int idx (uint64)r / PGSIZE;acquire(pageref.lock);pageref.count[idx] 1;release(pageref.lock);}release(kmem.lock);if(r)memset((char*)r, 5, PGSIZE); // fill with junkreturn (void*)r;
}kpageref
void
kpageref(uint64 pa, int inc) {int idx pa / PGSIZE;acquire(pageref.lock);pageref.count[idx] inc;release(pageref.lock);
}cow_handler
int
cow_handler(pagetable_t pagetable, uint64 va) {pte_t *pte;uint64 pa;uint flags;char *mem;if (va MAXVA) {return -1;}va PGROUNDDOWN(va);if ((pte walk(pagetable, va, 0)) 0) {return 0;}pa PTE2PA(*pte);flags PTE_FLAGS(*pte);if (!(flags PTE_C)) {return -1; // 不是cow}if((mem kalloc()) 0)return -1;memmove(mem, (char*)pa, PGSIZE);// 更新flagflags | PTE_W;flags (~PTE_C);*pte PA2PTE(mem) | flags;kfree((void *)pa); // 减少pa的引用计数return 0;
}trap
//
// handle an interrupt, exception, or system call from user space.
// called from trampoline.S
//
void
usertrap(void)
{uint64 scause r_scause(); if(scause 8){// system call} else if (scause 15) {if (cow_handler(p-pagetable, r_stval()) 0) {setkilled(p);}} else if((which_dev devintr()) ! 0){
}要特别注意死锁在死锁上花了三四个小时。
