MIT 6s081 lab6:Copy-on-Write Fork for xv6

2024-01-16 05:52
文章标签 fork mit write xv6 copy lab6 6s081

本文主要是介绍MIT 6s081 lab6:Copy-on-Write Fork for xv6，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

lab6：Copy-on-write fork

作业地址：Lab: Copy-on-Write Fork for xv6 (mit.edu)

实现 fork 懒复制机制，在进程 fork 后，不立刻复制内存页，而是将虚拟地址指向与父进程相同的物理地址。在父子任意一方尝试对内存页进行修改时，才对内存页进行复制。 物理内存页必须保证在所有引用都消失后才能被释放，这里需要有引用计数机制。

一开始做的时候没有上锁，一直没通过全部测试。后来参考了下面这位大佬的博客后意识到了竞争问题，加入自旋锁后顺利通过测试。

[mit6.s081] 笔记 Lab6: Copy-on-write fork | fork 懒拷贝 | Miigon’s blog

fork时不立刻复制内存

uvmcopy()，在复制父进程的内存到子进程的时候，不立刻复制数据，而是建立指向原物理页的映射，并将父子两端的页表项都设置为不可写。

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");panic("uvmcopy: page not present");pa = PTE2PA(*pte);// 如果原来是可写的，那就要改成不可写，并且加上COW标志if(*pte & PTE_W){*pte &= ~PTE_W; // 去掉写flag*pte |= PTE_C; //标记为写时复制状态}flags = PTE_FLAGS(*pte);if(mappages(new, i, PGSIZE, (uint64)pa, flags) != 0){// kfree(mem);goto err;}// 添加这个物理地址的引用计数acquire(&pgreflock);modify(GET_IDX(pa), 1);release(&pgreflock);    }return 0;err:uvmunmap(new, 0, i / PGSIZE, 1);return -1;
}

在riscv.h中加入对标志位PTE_C的定义：

#define PTE_V (1L << 0) // valid
#define PTE_R (1L << 1)
#define PTE_W (1L << 2)
#define PTE_X (1L << 3)
#define PTE_U (1L << 4) // 1 -> user can access#define PTE_C (1L << 8) // copy on write

这样，fork 时就不会立刻复制内存，只会创建一个映射了。这时候如果尝试修改懒复制的页，会出现 page fault 被 usertrap() 捕获。接下来需要在 usertrap() 中捕捉这个 page fault，并在尝试修改页的时候，执行真正的复制操作。

捕获写操作并执行复制

在 usertrap() 中添加对 page fault 的检测，检测接收的页是否是一个懒复制页（有PTE_C标志，并且虚拟地址合法），如果此时物理页的引用次数大于1，那么需要进行复制，将旧物理页的引用次数减一，分配的新物理页的引用次数加一；若引用次数为1，直接返回该页。

void
usertrap(void)
{int which_dev = 0;if((r_sstatus() & SSTATUS_SPP) != 0)panic("usertrap: not from user mode");// send interrupts and exceptions to kerneltrap(),// since we're now in the kernel.w_stvec((uint64)kernelvec);struct proc *p = myproc();// save user program counter.p->trapframe->epc = r_sepc();if(r_scause() == 8){// system callif(p->killed)exit(-1);// sepc points to the ecall instruction,// but we want to return to the next instruction.p->trapframe->epc += 4;// an interrupt will change sstatus &c registers,// so don't enable until done with those registers.intr_on();syscall();} else if((which_dev = devintr()) != 0){// ok} else {} else if(r_scause() == 15){ // page fault// 12 : instruction page fault// 13 ：load page fault// 15 ：store/AMO page Faultuint64 va = r_stval(); // get the virtual address that caused the page fault.pte_t *pte = walk(p->pagetable, va, 0);uint flags = PTE_FLAGS(*pte);uint64 old_pa = PTE2PA(*pte);if(flags & PTE_C && uvmcheckcowpage(va)) // 是写时复制场景{acquire(&pgreflock);int count = modify(GET_IDX((old_pa)),0);release(&pgreflock);if(count > 1) { // 引用次数超过1char * pa = kalloc(); // alloc physial memory ，分配一页物理内存if(pa == 0){ // 申请失败p->killed = 1; // 杀死进程exit(-1);}else{memset(pa, 0, PGSIZE); // 记录之前指向的内存地址的值，然后拷贝过去memmove(pa, (void * )old_pa, PGSIZE); kfree((void*)old_pa); //对于旧的地址，直接尝试删除//  增加新地址的引用次数，在kalloc中完成uint flags_new = (flags | (PTE_W)) & (~PTE_C); // 把原来的flag，清空掉PTE_C标志，加上PTE_W标志*pte = PA2PTE(pa) | flags_new | PTE_V; //修改pte}}else{uint flags_new = (flags | (PTE_W)) & (~PTE_C); *pte = PA2PTE(old_pa) | flags_new | PTE_V;}}else{p->killed = 1;exit(-1);} }else {printf("r_scause() == %d\n", r_scause());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;}if(p->killed)exit(-1);// give up the CPU if this is a timer interrupt.if(which_dev == 2)yield();usertrapret();
}

同时 copyout() 由于是软件访问页表，不会触发缺页异常，所以需要手动添加同样的监测代码，检测接收的页是否是一个懒复制页（有PTE_C标志，并且虚拟地址合法），如果此时物理页的引用次数大于1，那么需要进行复制，将旧物理页的引用次数减一，分配的新物理页的引用次数加一；若引用次数为1，直接返回该页。

int
copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len)
{uint64 n, va0, pa0;while(len > 0){va0 = PGROUNDDOWN(dstva);pa0 = walkaddr(pagetable, va0);if(pa0 == 0)return -1;// 这里可能会往一个cow page的页进行写操作，这时需要及时复制,和trap类似的操作pte_t *pte = walk(pagetable, va0, 0);if((*pte & PTE_U) == 0) return -1;uint flags = PTE_FLAGS(*pte);if((flags & PTE_C) && (flags & PTE_V) && uvmcheckcowpage(dstva)) // 是写时复制场景{acquire(&pgreflock);int count = modify(GET_IDX((pa0)),0);release(&pgreflock);if(count > 1) { // 引用次数超过1char * pa = kalloc(); // alloc physial memory ，分配一页物理内存if(pa == 0){ // 申请失败return -1;}else{memset(pa, 0, PGSIZE);// 记录之前指向的内存地址的值，然后拷贝过去uint64 old_pa = pa0;memmove(pa, (void * )old_pa, PGSIZE); kfree((void*)old_pa); //对于旧的地址，直接尝试删除uint flags_new = (flags | (PTE_W)) & (~PTE_C); // 把原来的flag，清空掉PTE_C标志，加上PTE_W标志*pte = PA2PTE(pa) | flags_new | PTE_V;pa0 = (uint64)pa; // 更新读写的位置}}else{  //此时引用次数为1uint flags_new = (flags | (PTE_W)) & (~PTE_C); *pte = PA2PTE(pa0) | flags_new | PTE_V;}} n = PGSIZE - (dstva - va0);if(n > len)n = len;memmove((void *)(pa0 + (dstva - va0)), src, n);len -= n;src += n;dstva = va0 + PGSIZE;}return 0;
}

提供工具方法：uvmcheckcowpage

int uvmcheckcowpage(uint64 va) {struct proc *p = myproc();return va < p->sz;
}

到这里，就已经确定了大体的逻辑了：在 fork 的时候不复制数据只建立映射+标记，在进程尝试写入的时候进行实复制并重新映射为可写。

接下来，还需要做页的生命周期管理，确保在所有进程都不使用一个页时才将其释放

在原本的 xv6 实现中，一个物理页的生命周期内，可以支持以下操作：

  • kalloc(): 分配物理页
  • kfree(): 释放回收物理页

而在支持了懒分配后，由于一个物理页可能被多个进程（多个虚拟地址）引用，并且必须在最后一个引用消失后才可以释放回收该物理页，所以一个物理页的生命周期内，现在需要支持以下操作：

  • kalloc，分配物理页时，引用次数加一
  • fork，将旧的物理页的引用次数加一
  • 写时复制场景usertrap\copyout：把旧的物理页的引用次数减一，新分配的物理页次数加一
  • kfree：对物理页的引用次数减一，当计数为0，才真正释放物理页

记录物理页的引用次数

在kalloc.c中添加一个全局数组，用于记录物理页的引用次数，并提供Modify方法，用于修改引用计数数组

int rc_array[(PHYSTOP - KERNBASE) / PGSIZE];
struct spinlock pgreflock; // 用于 rc_array 数组的锁，防止竞态条件引起内存泄漏int modify(int x,int c)
{if(x < 1){return -1;}rc_array[x] += c;if(rc_array[x] < 0) rc_array[x] = 0;return rc_array[x];
}

修改kfree函数：引用次数为0才能删去

void
kfree(void *pa)
{struct run *r;if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP){panic("kfree");}// acquire(&pgreflock);// 添加对引用次数的判断，如果引用次数为1，才能删去acquire(&pgreflock);int count = modify(GET_IDX(pa), -1); // 把自己的引用计数减一，如果引用计数还是大于0，说明不能删除，则返回。release(&pgreflock);if(count <= 0){// Fill with junk to catch dangling refs.// 如果引用计数为-1，说明还未分配空间，那么往下执行，分配空间// 如果引用计数为0，说明空间已经不被使用了，释放空间memset(pa, 1, PGSIZE);r = (struct run*)pa;acquire(&kmem.lock);r->next = kmem.freelist;kmem.freelist = r;release(&kmem.lock);}}

修改Kalloc函数，分配物理页时将引用次数加一

void * // 添加对引用次数+1的功能
kalloc(void)
{struct run *r;acquire(&kmem.lock);r = kmem.freelist;if(r)kmem.freelist = r->next;release(&kmem.lock);if(r)memset((char*)r, 5, PGSIZE); // fill with junk// lab6 add if(r){acquire(&pgreflock);modify(GET_IDX(r), 1);release(&pgreflock);}return (void*)r;
}

在usertrap和copyout函数中，加入判断，当物理页的引用次数为1时，说明此时只有一个进程使用这个物理页，那么就不用进行复制，直接返回这个物理页即可

加锁防止竞争

在rc_array添加了自旋锁pgreflock，在使用modify方法时，都使用acquire("&pgreflock")和release(&pgreflock)来对操作进行保护，防止竞争导致的内存泄露。

如果出现了内存泄露问题，在运行Make grade后，系统会提示usertests调用前后的空闲页数量不同。

FAILED -- lost some free pages 32447 (out of 32448)

在以下四种场景调用Modify操作中加入锁进行保护。

  • kalloc
  • fork
  • 写时复制场景usertrap\copyout
  • kfree

提交

$ make qemu-gdb
(7.1s) 
== Test   simple == simple: OK 
== Test   three == three: OK 
== Test   file == file: OK 
== Test usertests == 
$ make qemu-gdb
(78.3s) 
== Test   usertests: copyin == usertests: copyin: OK 
== Test   usertests: copyout == usertests: copyout: OK 
== Test   usertests: all tests == usertests: all tests: OK 
== Test time == 
time: OK 
Score: 110/110

这篇关于MIT 6s081 lab6:Copy-on-Write Fork for xv6的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/611520。

相关文章

Unstructured cannot write mode RGBA as JPEG 错误解决

Unstructured cannot write mode RGBA as JPEG 错误解决

Unstructured cannot write mode RGBA as JPEG 错误解决 0. 错误详细1. 解决方法 0. 错误详细 Image Extraction Error: Skipping the failed imageTraceback (most recent call last):File "/root/miniconda3/envs/learn-y
阅读更多...
70-java write类应用场景

70-java write类应用场景

在Java中，我们可以使用java.io包中的FileWriter和BufferedWriter类来写入数据到文件。以下是一个简单的例子，展示了如何使用FileWriter和BufferedWriter来写入数据到文件： import java.io.BufferedWriter;import java.io.FileWriter;import java.io.IOException;pub
阅读更多...
SylixOS write 0 字节问题

SylixOS write 0 字节问题

1 问题描述 在移植中间件过程中，在SylixOS调用write函数写入0字节的数据到文件中时，会导致对应的中间件测试用例失败，失败的原因是文件系统中的write函数在Linux系统和SylixOS有区别，两种实现的差别如下。 2 write函数的实现机制 2.1 SylixOS实现机制 在SylixOS下通过write 函数写数据到普通文件中时，第一步会判断写入的数据是否为0，如果是0直
阅读更多...
Java 入门指南：Java 并发编程 —— Copy-On-Write 写时复制技术

Java 入门指南：Java 并发编程 —— Copy-On-Write 写时复制技术

文章目录 Copy-On-Write使用场景特点缺点CopyOnWrite 和 读写锁相同点之处不同之处 CopyOnWriteArrayList适用场景主要特性方法构造方法CopyOnWriteArrayList 使用示例 CopyOnWriteArraySet适用场景主要特性方法构造方法使用注意事项CopyOnWriteArraySet 使用示例 Copy-On-Writ
阅读更多...
Linux进程初识：OS基础、fork函数创建进程、进程排队和进程状态讲解

Linux进程初识：OS基础、fork函数创建进程、进程排队和进程状态讲解

目录 1、冯诺伊曼体系结构 问题一：为什么在体系结构中存在存储器（内存）？ 存储单元总结： 问题二：为什么程序在运行的时候，必须把程序先加载到内存？ 问题三：请解释，从你登录上qq开始和某位朋友聊天开始，数据的流动过程。 2、操作系统 2.1操作系统的概念： 我们首先要明白什么是管理： 2.2为什么要有操作系统？ 2.3操作系统如何保证稳定和安全呢？（利用系统调用函数解决）
阅读更多...
df.write.csv

df.write.csv

# 将 DataFrame 写入 CSV 文件# 拆分 ArrayType 列df_exploded = df.withColumn("interests", explode("interests"))print("\nExploded DataFrame:")df_exploded.show(truncate=False)# 写入 CSV 文件df_exploded.write.csv
阅读更多...
redis被攻击redis READONLY You can‘t write against a read only slave.

redis被攻击redis READONLY You can‘t write against a read only slave.

redis 日志路径 /var/log/redis 拿下来后发现有这种错误 Operation now in progress 可能是网络断开导致， 查找redis whereis redis 修改 vim /etc/redis.conf 大概在300行 下面代码yes改no slave-read-only no 重启redis sudo systemctl restart
阅读更多...
Linux的进程,线程以及调度(fork与僵尸,内存泄漏,task结构体,停止状态与作业控制）

Linux的进程,线程以及调度(fork与僵尸,内存泄漏,task结构体,停止状态与作业控制）

1.Linux进程生命周期(就绪、运行、睡眠、停止、僵死) 2.僵尸是个什么鬼？ 3.停止状态与作业控制，cpulimit 4.内存泄漏的真实含义 5.task_struct以及task_
阅读更多...
代码开源许可证傻傻分不清 Apache MIT GPL的区别

代码开源许可证傻傻分不清 Apache MIT GPL的区别

https://www.ruanyifeng.com/blog/2011/05/how_to_choose_free_software_licenses.html
阅读更多...
2024.9.1 Python，跳跃游戏，贪心算法，回溯算法复原 IP 地址，关于回溯过程中列表的[:]以及copy问题再讨论

2024.9.1 Python，跳跃游戏，贪心算法，回溯算法复原 IP 地址，关于回溯过程中列表的[:]以及copy问题再讨论

先祝各位C友们9月快乐，生活幸福。 1.跳跃游戏，贪心算法 昨天的三个代码我写到最后没时间去盘了，今天来盘一下，昨天我写的第一个代码从逻辑上就有问题，所以不停的报错不停的报错，我在报错的过程中不断地去加可能性，但是加一种可能就只解决一种问题，所以说明问题没有在根本上解决，所以我便在今天去看之前的代码有什么问题，我的代码如下： #错的class Solution:def jump(self,
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2