MIT 6.S081 2020 Lab6 Copy-on-Write Fork for xv6 个人全流程

文章目录

    • 零、写在前面
    • 一、Implement copy-on write
      • 1.1 说明
      • 1.2 实现
        • 1.2.1 延迟复制与释放
        • 1.2.2 写时复制

零、写在前面

可以阅读下 《xv6 book》 的第五章中断和设备驱动。

问题

在 xv6 中，fork() 系统调用会将父进程的整个用户空间内存复制到子进程中。**如果父进程占用的内存较大，复制过程会非常耗时。更糟糕的是，这种复制往往是浪费的。**例如，在子进程中调用 fork() 后紧接着执行 exec()，会导致子进程丢弃复制来的内存，很可能其中大部分根本没有被使用。另一方面，如果父子进程都使用了某个页面，并且有一个或两个要写这个页面，那就确实需要进行复制。

解决方案

**写时复制（COW）**的 fork() 目标是推迟为子进程分配和复制物理内存页面，直到它们真的被需要（如果有的话）。

COW 的 fork() 仅为子进程创建一个页表，其中用户内存的页表项（PTE）指向父进程的物理页面。COW 的 fork() 会将父子进程中所有用户页面的页表项标记为不可写（即清除可写标志）。当任一进程尝试写这些 COW 页面时，CPU 会触发一个缺页异常（page fault）。内核的缺页异常处理程序会识别出这是 COW 的情况，为发生异常的进程分配一个新的物理页面，复制原页面的内容，然后修改该进程的页表项指向新页面，并将其标记为可写。异常处理程序返回后，用户进程就可以写这个新复制的页面了。

COW 的 fork() 也让用户内存的物理页面释放变得更复杂。因为一个物理页面可能会被多个进程的页表引用，只有当最后一个引用消失时，该页面才能被释放。

我们发现 COW 和 Lazy alloc 的思想其实是类似的。

记得切换到 cow 分支

一、Implement copy-on write

1.1 说明

你的任务是：在 xv6 内核中实现写时复制的 fork()。当你的内核能够成功执行 cowtest 和 usertests 这两个程序时，说明你完成了任务。

官网推荐的实现步骤：

  1. 修改 uvmcopy()，不要为子进程分配新页面，而是将父进程的物理页面映射到子进程中。清除父子两者对应页表项中的 PTE_W（可写标志）。

  2. 修改 usertrap() 以识别缺页异常。如果在 COW 页面上发生缺页异常，则使用 kalloc() 分配一个新页面，将原页面内容复制过去，并在当前进程的页表中安装新页面，并设置 PTE_W。

  3. 确保物理页面只在最后一个引用消失时才释放。你可以为每个物理页面维护一个“引用计数”，记录有多少个用户页表引用了该页面。

    • 当 kalloc() 分配页面时，将引用计数设为 1。
    • 当 fork() 让子进程共享页面时，将引用计数加 1。
    • 每当进程从页表中移除页面时，引用计数减 1。
    • 只有当引用计数为 0 时，kfree() 才能将页面放回空闲列表。
    • 可以用一个定长的整数数组来存储这些引用计数。你需要设计如何为页面选择索引以及数组大小。例如，你可以用页面物理地址除以 4096 作为索引，数组元素个数可以设为 kalloc.c 中 kinit() 放入空闲列表的最高物理地址除以 4096。

  4. 修改 copyout()，当遇到 COW 页面时，采用和处理缺页异常一样的方案进行处理。

官网的一些提示：

  • 懒惰分配实验应该让你对实现 COW 所需的 xv6 代码已有一定了解。但请不要在本实验中基于你之前懒惰分配实验的实现，而是从一个全新的 xv6 拷贝开始。
  • 你可以使用 RISC-V 页表项中的 RSW（软件保留位）来记录每个 PTE 是否为 COW 映射。
  • usertests 测试了一些 cowtest 没有覆盖的情况，所以一定要确保两个测试都能通过。
  • 有用的页表标志宏和定义可以在 kernel/riscv.h 文件末尾找到。
  • 如果在处理 COW 缺页异常时没有可用内存，应该终止对应进程。

1.2 实现

官网给出的步骤其实已经让我们有一个较为清晰的思路了，下面直接实现就行了。

实现逻辑分为两部分：

  • 延迟复制与释放
  • 写时复制
1.2.1 延迟复制与释放
  • 首先在 kalloc.c 中添加一个结构体保存每个页面的引用计数
  • 为了保证并发安全，我们额外添加一个自旋锁
  • 为了方便，提供一个 宏 用于计算引用计数数组索引，这也是官网给出的 页面物理地址除以 4096 作为索引 的方法
// get cnt Array index
#define PA2IDX(p) (((uint64)(p)) / PGSIZE)struct {struct spinlock lock; // spinlock to ensure concurrency safetyint refCnt[PHYSTOP / PGSIZE]; // page ref cnt array
} pageRef;

在 kinit 中新增一行 pageRef 自旋锁的初始化

void
kinit()
{initlock(&kmem.lock, "kmem");initlock(&pageRef.lock, "pageRef"); // initialize the lock for pageReffreerange(end, (void*)PHYSTOP);
}

在 kalloc 中 对新增页面的引用计数初始化为1

void *
kalloc(void)
{// ...if(r) {memset((char*)r, 5, PGSIZE); // fill with junkpageRef.refCnt[PA2IDX(r)] = 1;}return (void*)r;
}

然后修改 kfree 的逻辑为只有当引用计数减为0 时才释放

// Free the page of physical memory pointed at by v,
// 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");acquire(&pageRef.lock); // acquire the lock for pageRef// not referred nowif(--pageRef.refCnt[PA2IDX(pa)] <= 0) {memset(pa, 1, PGSIZE);    // fill with junkr = (struct run*)pa;acquire(&kmem.lock);r->next = kmem.freelist;kmem.freelist = r;release(&kmem.lock);    }release(&pageRef.lock);
}
  • 我们还要添加新增引用计数的逻辑
  • 以及物理页面复制的逻辑，以便后面调用
  • 记得在defs.h添加声明WWWWW
    • 外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传
// if clone is needed
void *kTry_pgclone(void *pa) {acquire(&pageRef.lock);// if it only belongs to meif(pageRef.refCnt[PA2IDX(pa)] <= 1) {release(&pageRef.lock);return pa;}// apply for a new pageuint64 newpa = (uint64)kalloc();if(newpa == 0) {release(&pageRef.lock);return 0;}// copy old data to new onememmove((void*)newpa, (void*)pa, PGSIZE);// refCnt of old page decpageRef.refCnt[PA2IDX(pa)]--;release(&pageRef.lock);return (void*)newpa;
}// inc the refCnt
void kparef_inc(void *pa) {acquire(&pageRef.lock);pageRef.refCnt[PA2IDX(pa)]++;release(&pageRef.lock);
}
  • 然后就可以修改 vm.c 中的uvmcopy的复制操作 改为该物理页面的引用次数+1
  • 以及为子进程新建页表
int
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{pte_t *pte;uint64 pa, i;uint flags;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);if (*pte & PTE_W) {*pte = (*pte & ~PTE_W) | PTE_COW;}flags = PTE_FLAGS(*pte);// create pte for son processif(mappages(new, i, PGSIZE, (uint64)pa, flags) != 0){goto err;}kparef_inc((void*)pa);}return 0;err:uvmunmap(new, 0, i / PGSIZE, 1);return -1;
}
1.2.2 写时复制

即然要延迟写操作，那么在缺页异常的时候我们就需要知道这些页面是否是 写时复制的共享页面，官网也是提醒我们，可以用 PTE 的保留位来标记。

  • 我们为COW 的缺页错误编写一个辅助函数
  • 复制一个新页面
  • 设置为可写，取消 COW标记
  • 取消旧页面映射，添加新映射
  • 记得在 defs.h 中添加声明
    • 外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传
int cow_Helper(pagetable_t pagetable, uint64 va)
{pte_t *pte;// get pte for vaif((pte = walk(pagetable, va, 0)) == 0)panic("uvmcowcopy: walk");uint64 pa = PTE2PA(*pte);uint64 newpa;// clone pageif((newpa = (uint64)kTry_pgclone((void*)pa)) != 0){// set PTE_W and unset PTE_COWuint64 flags = (PTE_FLAGS(*pte) | PTE_W) & ~PTE_COW;// unmap but do not free uvmunmap(pagetable, PGROUNDDOWN(va), 1, 0);// map to new pgif(mappages(pagetable, va, 1, newpa, flags) == -1) {panic("uvmcowcopy: mappages");}return 0;}return -1;
}
  • 然后修改copyout 的逻辑
  • 如果发现是 cow 页面，就调用 cow_Helper() 来处理。
int
copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len)
{uint64 n, va0, pa0;pte_t *pte;struct proc *p = myproc();while(len > 0){va0 = PGROUNDDOWN(dstva);// cowif(va0 < p->sz && (pte = walk(pagetable, va0, 0))!=0 && *pte & PTE_V&& *pte & PTE_COW)cow_Helper(pagetable,va0);// ...
}
  • 以及usertrap 逻辑的修改
  • 针对 我们写时复制的页面错误单独处理
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 if (r_scause() == 13 || r_scause() == 15){pte_t *pte;uint64 va = r_stval();// is va valid?if (va >= p->sz)exit(-1);pte = walk(p->pagetable, va, 0);// valid and cow ?if (pte == 0 || (*pte & PTE_V) == 0 || (*pte & PTE_COW) == 0)exit(-1);// copy on write for cow pgif (cow_Helper(p->pagetable, va) == -1) {exit(-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;}if(p->killed)exit(-1);// give up the CPU if this is a timer interrupt.if(which_dev == 2)yield();usertrapret();
}

测试一下：

cowtest:

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

usertest:

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

官网还是写的太详细了（bushi

p->killed = 1;
}

if(p->killed)
exit(-1);

// give up the CPU if this is a timer interrupt.
if(which_dev == 2)
yield();

usertrapret();
}

**测试一下：****cowtest:**[外链图片转存中...(img-TxytPoKI-1748706565978)]**usertest:**[外链图片转存中...(img-kelfELYU-1748706565978)]官网还是写的太详细了（bushi

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.pswp.cn/web/81999.shtml

如若内容造成侵权/违法违规/事实不符，请联系多彩编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

xhr、fetch和axios

xhr、fetch和axios

XMLHttpRequest (XHR) XMLHttpRequest 是最早用于在浏览器中进行异步网络请求的 API。它允许网页在不刷新整个页面的情况下与服务器交换数据。 // 创建 XHR 对象 const xhr new XMLHttpRequest();// 初始化请求 xhr.open(GET, https://api.example.com/data, true);// 设置请…
阅读更多...
电脑驱动程序更新工具， 3DP Chip 中文绿色版，一键更新驱动！

电脑驱动程序更新工具， 3DP Chip 中文绿色版，一键更新驱动！

介绍 3DP Chip 是一款免费的驱动程序更新工具&#xff0c;可以帮助用户快速、方便地识别和更新计算机硬件驱动程序。 驱动程序更新工具下载 https://pan.quark.cn/s/98895d47f57c 软件截图 软件特点 简单易用&#xff1a;用户界面简洁明了&#xff0c;操作方便&#xff0c;…
阅读更多...
机器学习与深度学习06-决策树02

机器学习与深度学习06-决策树02

目录 前文回顾5.决策树中的熵和信息增益6.什么是基尼不纯度7.决策树与回归问题8.随机森林是什么 前文回顾 上一篇文章地址&#xff1a;链接 5.决策树中的熵和信息增益 熵和信息增益是在决策树中用于特征选择的重要概念&#xff0c;它们帮助选择最佳特征进行划分。 熵&#…
阅读更多...
【Kotlin】数字字符串数组集合

【Kotlin】数字字符串数组集合

【Kotlin】简介&变量&类&接口 【Kotlin】数字&字符串&数组&集合 文章目录 Kotlin_数字&字符串&数组&集合数字字面常量显式转换数值类型转换背后发生了什么 运算字符串字符串模板字符串判等修饰符数组集合通过序列提高效率惰性求值序列的操…
阅读更多...
oscp练习PG Monster靶机复现

oscp练习PG Monster靶机复现

端口扫描 nmap -A -p- -T4 -Pn 192.168.134.180 PORT STATE SERVICE VERSION 80/tcp open http Apache httpd 2.4.41 ((Win64) OpenSSL/1.1.1c PHP/7.3.10) |_http-server-header: Apache/2.4.41 (Win64) OpenSSL/1.1.1c PHP/7.3.10 | http-methods:…
阅读更多...
近期知识库开发过程中遇到的一些问题

近期知识库开发过程中遇到的一些问题

我们正在使用Rust开发一个知识库系统&#xff0c;遇到了一些问题&#xff0c;在此记录备忘。 错误&#xff1a;Unable to make method calls because underlying connection is closed 场景&#xff1a;在docker中调用headless_chrome时出错 原因&#xff1a;为减小镜像大小&am…
阅读更多...
Ubuntu 22.04 系统下 Docker 安装与配置全指南

Ubuntu 22.04 系统下 Docker 安装与配置全指南

Ubuntu 22.04 系统下 Docker 安装与配置全指南 一、前言 Docker 作为现代开发中不可或缺的容器化工具&#xff0c;能极大提升应用部署和环境管理的效率。本文将详细介绍在 Ubuntu 22.04 系统上安装与配置 Docker 的完整流程&#xff0c;包括环境准备、安装步骤、权限配置及镜…
阅读更多...
C#获取磁盘容量：代码实现与应用场景解析

C#获取磁盘容量：代码实现与应用场景解析

C#获取磁盘容量&#xff1a;代码实现与应用场景解析 在软件开发过程中&#xff0c;尤其是涉及文件存储、数据备份等功能时&#xff0c;获取磁盘容量信息是常见的需求。通过获取磁盘的可用空间和总大小&#xff0c;程序可以更好地进行资源管理、预警提示等操作。在 C# 语言中&a…
阅读更多...
2025年- H56-Lc164--200.岛屿数量(图论,深搜）--Java版

2025年- H56-Lc164--200.岛屿数量(图论,深搜）--Java版

1.题目描述 2.思路 &#xff08;1&#xff09;主函数&#xff0c;存储图结构 &#xff08;2&#xff09;主函数&#xff0c;visit数组表示已访问过的元素 &#xff08;3&#xff09;辅助函数&#xff0c;用递归&#xff08;深搜&#xff09;&#xff0c;遍历以已访问过的元素&…
阅读更多...
详细到用手撕transformer下半部分

详细到用手撕transformer下半部分

之前我们讨论了如何实现 Transformer 的核心多头注意力机制&#xff0c;那么这期我们来完整地实现整个 Transformer 的编码器和解码器。 Transformer 架构最初由 Vaswani 等人在 2017 年的论文《Attention Is All You Need》中提出&#xff0c;专为序列到序列&#xff08;seq2s…
阅读更多...
WPF事件处理器+x名称空间

WPF事件处理器+x名称空间

目录 ​编辑 一、事件处理器知识点 1. XAML中的事件绑定 2. C#中的事件处理方法 3. 方法签名解释 4. 命名规范 工作流程 二、导入引用名称空间 三、x名称空间及其常用元素 &#xff08;1&#xff09;x名称空间的由来和作用 &#xff08;2&#xff09;x名称空间里都有…
阅读更多...
Axure设计案例——科技感渐变线性图

Axure设计案例——科技感渐变线性图

想让数据变化趋势展示告别枯燥乏味&#xff0c;成为吸引观众目光的亮点吗&#xff1f;快来看看这个Axure设计的科技感渐变线性图案例&#xff01;科技感设计风格凭借炫酷的渐变色彩打破传统线性图的单调&#xff0c;营造出一种令人过目难忘的视觉体验。每一条线条都仿佛是流动的…
阅读更多...
Git全流程操作指南

Git全流程操作指南

Git全流程操作指南 一、Git 环境配置 1. 安装 Git Windows&#xff1a;下载 Git for Windows macOS&#xff1a;brew install git Linux&#xff1a; sudo apt-get update && sudo apt-get install git # Debian/Ubuntu sudo yum install git …
阅读更多...
AI与软件工程结合的未来三年发展路径分析

AI与软件工程结合的未来三年发展路径分析

基于对数字化、制造业、工业、零售业等行业的系统调研&#xff0c;以及微软、谷歌、阿里、华为等大厂的实践案例&#xff0c;我们可以预见未来三年AI与软件工程结合将呈现以下发展路径和趋势。 一、技术应用维度 1. AI辅助编程工具全面普及 未来三年&#xff0c;AI辅助编程工…
阅读更多...
tiktoken学习

tiktoken学习

1.tiktoken是OpenAI编写的进行高效分词操作的库文件。 2.操作过程&#xff1a; enc tiktoken.get_encoding("gpt2") train_ids enc.encode_ordinary(train_data) val_ids enc.encode_ordinary(val_data) 以这段代码为例&#xff0c;get_encoding是创建了一个En…
阅读更多...
DeepSeek 赋能文化遗产数字化修复：AI 重构千年文明密码

DeepSeek 赋能文化遗产数字化修复：AI 重构千年文明密码

目录 一、引言二、文化遗产数字化修复概述2.1 文化遗产数字化修复的意义2.2 传统数字化修复方法与局限 三、DeepSeek 技术剖析3.1 DeepSeek 技术原理与核心优势3.2 相比其他技术的独特之处 四、DeepSeek 在文化遗产数字化修复中的应用4.1 破损文物的智能修复4.2 文化遗产的虚拟…
阅读更多...
leetcode题解513：找树左下角的值（递归中的回溯处理）！

leetcode题解513：找树左下角的值（递归中的回溯处理）！

一、题目内容&#xff1a; 题目要求找到一个二叉树的最底层最左边节点的值。具体来说&#xff0c;我们需要从根节点开始遍历二叉 树&#xff0c;找到最深的那层中的最左边的节点&#xff0c;并返回该节点的值。因为要先找到最底层左侧的值&#xff0c;所以我们选择遍历顺序一定…
阅读更多...
C#面试问题41-60

C#面试问题41-60

41. What is the Singleton design pattern? Singleton is a class that only allows creating a single instance of itselt. 单例设计模式是一个类&#xff0c;它只允许创建自己的单个实例。 构造函数防止他在单例类以外的地方被调用。 使用情景&#xff1a;need a sing…
阅读更多...
笔记思考法

笔记思考法

掌握麦肯锡流笔记术&#xff0c;对大家来说有以下几种好处: 1) 可以将自己的思考可视化&#xff0c;使之变得更加清晰 2) 避免无用功 3) 经常能够提出有创意的想法 4) 遇到问题时能够及时找到解决办法 5) 不管面对什么情况都能够找出真正有效的解决办法 为什么仅仅通过改变使用…
阅读更多...
Rust 学习笔记：关于闭包的练习题

Rust 学习笔记：关于闭包的练习题

Rust 学习笔记&#xff1a;关于闭包的练习题 Rust 学习笔记&#xff1a;关于闭包的练习题问题 1问题 2以下程序能否通过编译&#xff1f;若能&#xff0c;输出是&#xff1f;以下程序能否通过编译&#xff1f;若能&#xff0c;输出是&#xff1f;考虑该 API&#xff0c;空白处填…
阅读更多...
最新文章

Copyright @ 2022~2023