| MIT6.S081 | 您所在的位置：网站首页 › mit的6s081课程 › MIT6.S081 |
MIT6.S081
|
MIT6.S081笔记——写写OS
深陷脊背的腐烂禁 人生浪费指南三流写手/吃肉肉 2 人赞同了该文章 MIT 6.S081 lab tool 环境要求主要是3个项目:一个是riscv64的toolchain,另一个就是虚拟机qemu,剩下的就是一个源码库,装好这三个就可以开始写代码了 关于环境一些坑首先就是toolchain,这个项目仅仅源代码就有3个多G,按照国内访问git的速度几乎不可能下载完,(这个项目是一个套娃项目,其中里面的子module对应着github上的别的项目,其中qemu的部分还不是在github的服务器上,需要请求另一个美国的服务器,即使翻墙走代理速度也是慢的离谱) 解决方法: 1.翻墙走代理,对git进行配置,该项目是套娃项目所以在clone时要进行–recursive. 2.使用网上的百度云,没会员也是慢的离谱,https://zhayujie.com/mit6828-env.html 中有博主分享的百度云链接,加上会员很丝滑 配置好之后编译大约个把小时 Lab: Xv6 and Unix utilities Boot xv6这部分主要介绍的就是如何编译,如何使用qemu运行程序,通过Makefile文件在UPROGS加上自己的文件进行编译用户程序,使用make grade进行打分 sleep这部分代码倒是不难,可以直接对sleep进行系统调用 pipe这里使用管道对父子进程进行ipc,逻辑上也不难 primes这个模块很有意思,要求实现一个并发的素数筛,网页给了一个csp的论文进行参考 其中素数筛得基本思路也就是多开线程每个线程筛一个质因子,然后把没有被筛掉的数字向子进程write然后通过进程的不断fork达到一个素数筛的目的 一个错误我卡了很久,就是没有检测read函数的返回值,我认为既然read函数是阻塞io既然没读到就会持续地阻塞下去,实际上不是 并发素数筛的核心逻辑 while(1) {//child thread parent_fd[0]=child_fd[0]; close(child_fd[1]); pipe(child_fd); buffer_num=0; if(read(parent_fd[0],&buffer_num,sizeof(buffer_num))==0) { exit(); } //printf("sta=%d %d\n",sta,parent_fd[0]); thread_num=buffer_num; //int pid=getpid(); printf("prime %d\n",thread_num); if(fork())//parent thread { close(child_fd[0]); while(read(parent_fd[0],&buffer_num,sizeof(buffer_num))==4) { if(buffer_num%thread_num) { //pid=getpid(); //printf("write buffer_num=%d thread_num=%d,pid=%d\n",buffer_num,thread_num,pid); write(child_fd[1],&buffer_num,sizeof(buffer_num)); } } exit(); } pipe关于pipe的一段代码 int p[2]; char *argv[2]; argv[0] = "wc"; argv[1] = 0; pipe(p); if(fork() == 0) { close(0); dup(p[0]); close(p[0]); close(p[1]); exec("/bin/wc", argv); } else { write(p[1], "hello world\n", 12); close(p[0]); close(p[1]); }这是一段很有意思的代码 这段代码通过pipe,close和dup成功把wc的标准输入绑定到了另一个程序的管道中 阻塞read直到不可能到达新数据的一个原因是在执行wc之前，让子进程关闭管道的写入端非常重要。因为如果wc的一个文件描述符指向了管道的写入端，wc将永远不会看到文件末尾。 findls 的递归版使用dfs搜索所有的文件夹 其中目录是一种特殊的文件 注意不能递归./ ../否则会无限递归 xargs这个程序可以执行shell命令 并且把这个程序的标准输入当作argv传入执行的shell 可以用来使用管道把别的程序的输出用管道成为另一个程序的参数 注意好处理字符串 使用fork配合exec即可实现 xv6 shell features1.可以调用一些用户态的程序 2.允许cd切换目录 3.对调用的程序传参 4.使用|进行输出输入和管道的绑定 5.使用进行io重定向 6.使用&后台运行 7.使用;分割指令从做到右依次执行 shell只是一个用户程序，而不是内核的一部分，shell没有什么特别之处反倒说明了系统调用接口的力量。完成以上的features就符合了shell的基本需求,正要写一个shell,参考xv6的shell源码,下面从整体上来记录一下xv如何实现shell parser还记之前ccf的第一是实现一个计算器似乎要完成加减乘除,当时好像就过了样例点.现在回想起来实现其实就是语法树这一套 由于|();等调用会产生相当多复杂的命令和处理方式,实质上的处理时的各种递归调用其实就是一个语法树,这个树由5种基本命令构成 #define EXEC 1 #define REDIR 2 #define PIPE 3 #define LIST 4 #define BACK 5 struct cmd { int type; }; struct execcmd { int type; char *argv[MAXARGS]; char *eargv[MAXARGS]; }; struct redircmd { int type; struct cmd *cmd; char *file; char *efile; int mode; int fd; }; struct pipecmd { int type; struct cmd *left; struct cmd *right; }; struct listcmd { int type; struct cmd *left; struct cmd *right; }; struct backcmd { int type; struct cmd *cmd; };以上代码在c语言中完成了继承和多态的性质,配合这两个性质,所有的函数都使用统一的cmd接口,其中cmd可以看作是一个抽象类,这个shell的源码的是学习类模板设计模式极好的范例,整段代码的复用性极高 pipecmd和listcmd有左右两个子节点,通过这种抽象就可以把整个一个命令抽象为一棵语法树 其中解析AST的过程先解析析pipe 在解析list 最后就可以把所有的作为基本命令进行解析 其中从解析器到执行的的传参,使用字符串指针,也就是在parse buffer的时候将所有的参数以指针进行储存,然后把所有的参数结尾替换为\0 执行器 runcmd(parsecmd(buf));在parse之后会返回一个语法树,其中核心的功能就是runcmd通过递归的遍历整棵树进行从左到右的执行 // Execute cmd. Never returns. void runcmd(struct cmd *cmd) { int p[2]; struct backcmd *bcmd; struct execcmd *ecmd; struct listcmd *lcmd; struct pipecmd *pcmd; struct redircmd *rcmd; if(cmd == 0) exit(); switch(cmd->type){ default: panic("runcmd"); case EXEC: ecmd = (struct execcmd*)cmd; if(ecmd->argv[0] == 0) exit(); exec(ecmd->argv[0], ecmd->argv); printf(2, "exec %s failed\n", ecmd->argv[0]); break; case REDIR: rcmd = (struct redircmd*)cmd; close(rcmd->fd); if(open(rcmd->file, rcmd->mode) < 0){ printf(2, "open %s failed\n", rcmd->file); exit(); } runcmd(rcmd->cmd); break; case LIST: lcmd = (struct listcmd*)cmd; if(fork1() == 0) runcmd(lcmd->left); wait(); runcmd(lcmd->right); break; case PIPE: pcmd = (struct pipecmd*)cmd; if(pipe(p) < 0) panic("pipe"); if(fork1() == 0){ close(1); dup(p[1]); close(p[0]); close(p[1]); runcmd(pcmd->left); } if(fork1() == 0){ close(0); dup(p[0]); close(p[0]); close(p[1]); runcmd(pcmd->right); } close(p[0]); close(p[1]); wait(); wait(); break; case BACK: bcmd = (struct backcmd*)cmd; if(fork1() == 0) runcmd(bcmd->cmd); break; } exit(); }其中对于管道的处理就是fork两个儿子程序,向下递归,并且通过dup和pipe函数把输入输出重定向 我的nsh 解析器由于本lab规定不能使用malloc进行动态内存分配,所以数据结构采取了统一的节点 struct cmd { int type; int left; //left node int right; //right node char * arg[MAX_ARG]; char * earg[MAX_ARG]; char *in_s; char *end_in_s; char *out_s; char *end_out_s; }mycmd[20];节点有两种类型第一种是普通execmd 第二种是pipeexe作为一个节点包含着两个子节点 采用分治的方法对pipecmd进行分治,通过递归继续对整体的语法树构造 对单独的节点execmd构造就是把所有的参数全部都放存进字符串指针数组,这样方便对exec传递参数,注意要把>后的字符串和alloc->slip->自由内存->unavilible 题目给出了一个优化内存的方法那就是把alloc缩减为原来的一半,原来记录的是每一段是否被分配,现在记录bi和buddy的状态是否一致. 其实再malloc时我们并不需要检查标志,只有再回收内存时,我们才考虑吧检查标志,看是否需要合并内存块到上一层. 把alloc缩短之后,我们就要配合着把malloc和free中的isset 和 switch函数重写 主要的难点其实在初始化空间时,init时我们要把所有的空闲内存挂在freelist上,这时我们已经没有了alloc标志位,所以我们只能手动判断,每个内存块的地址空间是否在是为未分配的空间 MIT 6S081_lazylib本实验要完成的是内存管理的lazy sbrk模块,程序可以通过调用sbrk向操作系统申请内存,但是在很多情况下申请完并不是马上就可以用到,所以操作系统可以对sbrk进行lazy操作,即先对进程空间进行增加,但是并不实际分配物理页面,然后在真正用到lazy时在去在中断中判断是否是已经申请内存的空间,如果是可以对当前访问的页面进行分配内存页面. 下面谈一下编写的代码 sbrk函数,要在调用sbrk时并不真正的分配内存,而是只增加myproc()->sz的大小,然后在真正进行读写时才进行内存分配vmprint 利用三级页表进行递归的查询usertrap捕捉缺页异常,判断缺页是否时未进行分配的,如果是,分配页,并对它进行映射neltrap所以判断实在copyout和copyin的时候发生的异常,所以可以直接对他们调用的walkaddr进行修改vmcheckguard对栈底页面进行标记 MIT 6S081_cow_lab这个实验其实本质上于上一个没有太大区别,主要任务就是完成copy on write的编写,也是在fork的时候并不真正的分配内存而是,直接把页面进行PTE_W的标志位取消,然后设计一个PTE_cow标志被重新映射的页面,然后在内存中的一块加入引用计数,记录每一块内存块被复用的次数,每次新增加映射时对ref进行增加,每次copy时对页面引用进行减少. 下面谈一下编写的代码 kalloc中的代码要增加一个引用数组记录每个内存块的引用次数,xv6中最多有64个进程,所以引用可以直接开uint8的数组,对所有内存块进行记录,然后编写两个函数kborrow和kdrop来增加和减少引用.vmmemcopy在fork进程时会调用vmmemcopy的代码,因为要copy on write所以memcopy并不真正的分配内存而是直接对物理地址进行mappage一个新的vm,然后调用kborrow,对引用进行增加.在系统触发缺页中断时候进行复制物理页,然后把虚拟内存进行重新映射,调用kdrop时会减少引用次数,在引用为0时free掉内存同样在从内核态向用户态复制内存时也要进行检查是否是共用内存,如果是也要重新分配内存 tips在使用gdb调试能显著提升debug的效率 continue 执行程序 break vm.c:12 增加断点 step 执行一步进入函数 next 执行一步不进入函数 bt 在触发中断时特别有用,查看函数调用栈 git git log –oneline –graph 查看日志 git diff x x 查看更改 git status 查看当前状态 git stash 把当前修改压进缓存区栈 git checkout HEAD vm.c 恢复某一个文件 MIT6S081_Lab: user-level threads and alarm&Lock user-level threads这个lab是实现用户级线程切换和实现时钟中断函数 用户级别的线程切换其实就是简单版的系统级线程切换,不同的是系统级的进程需要加锁防止多核引发冲突,而用户级别的线程切换则完全不需要考虑这个问题 如何实现切换首先看一看uthread的汇编代码,可以发现几乎所有的函数只用了a和s寄存器也就是callee寄存器,所以也就是保存这些进程的上下文只要保存好callee寄存器和栈顶寄存器(sp)还有返回寄存器(ra)就可以保存进程所有的上下文 我们看context的数据结构 struct context { uint64 ra; uint64 sp; // callee-saved uint64 s0; uint64 s1; uint64 s2; uint64 s3; uint64 s4; uint64 s5; uint64 s6; uint64 s7; uint64 s8; uint64 s9; uint64 s10; uint64 s11; }; struct thread { char stack[STACK_SIZE]; /* the thread's stack */ int state; /* FREE, RUNNING, RUNNABLE */ struct context context_pointer; };其中线程的数据结构是一个stack作为该线程的用户栈和一个state作为该线程的运行状态.在进行用户级别的进程切换时只需要切换这个数据结构即可.switch函数进行返回时,会返回到ra中的值作为当前的地址,所以在进行switch切换后所就会切换进入另一个函数.注意的是一开始的时候要提取函数指针,把函数指针放入该线程数据结构的ra寄存器 MIT6S081_Lab_Alarm这个实验主要是要完成一个时钟中断函数的调用,在xv6中时钟的ticks由硬件发出每次会触发一个trap,trap_handle中编写函数对其进行处理,这个任务是让我们实现一个sigalarm(interval, handler)函数,每经过interval个时钟中断就调用handler函数一次,所以我们为需要在进程中多维护几个变量用于储存 void (*handle)(); uint64 interrupt_num; uint64 interrupt_val; uint64 running; struct trapframe snapshot;其中handle作为一个函数指针,执行被调用需要处理的函数,num我们维护的代表当前的中断数,val目标的中断数,一旦num达到了val的值我们就开始调用handle函数,running代表处理函数当前是否在运行,snap当然是保存当前的所有寄存器,在调用sigalarm函数时其实就是把以上的数据结构进行初始化,然后要增加一个sigreturn函数,sigreturn就是恢复栈帧,然后把当前的信号量减一个val Lock这个lab就是要求重新设计内存分配器和读写缓冲区来减少锁的竞争 首先看一看xv6中的两种锁 xv6中的锁其实很简单,只有两种锁,一个是自旋锁还有一个是就是睡眠锁 其中自旋锁的代码如下: void acquire(struct spin *lk) { for(;;) { if(lk->locked==0) { lk->locked=1; break; } } }其中if中的语句需要用原子操作替换,自旋锁顾名思义就是自循环的锁,所以跟睡眠锁相比更加的耗费cpu的资源. 其中原子操作时使用特别的硬件是实现的. 注意要在使用锁时,特别的最好是按照顺序申请,如果都是用固定的申请顺序,这样可以很好的避免造成死锁.但是通常由于代码中大量的函数等嵌套关系,所以锁不一定可以按照固定的顺序进行申请. POSIX线程允许一个程序的几个线程跑在不同的cpu上,但是如果其中一个线程进行了地址空间的更改,那么代价就比较大了 说完了锁,那么我们现在开始看Lab,首先Lab的第一个任务. 内存空间配置器其中在这个test程序中程序大量的进行申请内存,导致锁的竞争很激烈,那我们首先来看一看空间配置器的代码 其实整个空闲空间被配置成为了一个大链表,我们想要申请内存就要在这个链表上区,所以一旦为这个大链表上了锁,其他core就不能在同时申请内存. 所以想要减少竞争其实很简单,为每一个cpu都分配一个链表,当申请内存时,先查看cpuid,然后用该cpu对应的链表进行分配就可以了. 磁盘缓存区首先看一下bio代码,主要部分都是先初始缓存区,然后申请缓存区,读写缓存区,然后是释放缓存区,其中缓存区也是一个链表,在每次我们想找到磁盘对应的缓存区时都要把整个bceche都上锁,所以这么做的代价是很高昂的,通过功能来看也肯定并不能像上一个任务一样通过cpu来分.那我我们的解决办法就是通过hash来分块,由于每个buffer都会磁盘块的块号,所以可以通过块号进行hash,把巨大的竞争分散掉,选取一个质数13,所以我们就把1个链表分散进了13个链表,初始化的时候就先把所有的链表全都悬挂在0链表上,每当其他bucket没有新的区域了,就从别的链表上steal一个块,加进自己的链表. MIT_6S081_mmapLab featuresmmap是unix系统中的一个函数,其作用就是把磁盘上的文件映射进入内存方便读写. mmap是一种内存映射文件的方法，即将一个文件或者其它对象映射到进程的地址空间，实现文件磁盘地址和进程虚拟地址空间中一段虚拟地址的一一对映关系。实现这样的映射关系后，进程就可以采用指针的方式读写操作这一段内存，而系统会自动回写脏页面到对应的文件磁盘上，即完成了对文件的操作而不必再调用read,write等系统调用函数。相反，内核空间对这段区域的修改也直接反映用户空间，从而可以实现不同进程间的文件共享。 ###实现 首先一定是增加mmap函数和unmap函数的系统调用lazy的分配内存页,在mmap并不分配具体的内存地址,在真正访问地址触发一个trap缺页中断,然后对地址进行分配,这样既可以增加mmap的速度,也可以使mmap映射一个比内存空间大的文件分配一个vma数据结构记录地址,长度,文件,许可位等等实现mmap,在调用时维护好一个新增的vma,同时为vma增加一个file ref防止文件被关闭,这时调用mmaptest会会因为触发缺页中断而被迫关闭增加缺页中断处理的函数,分配一个页并且从文件中读取4098字节,并且映射进入用户空间,使用readi读,要传一个offset函数,在读的时候要把inode上锁实现munmap,回收页,并且减少一个文件引用,如果mapshared那马就把内存写入文件中PTE中的dirty bit可以检测页面是否被修改过,如果被修改过那么就往回写修改exit函数,如果调用了mmap就自动把页面回收修改fork函数让子进程也继承那个地址,不要忘记增加引用,子进程的vma也要写时复制通过这个lab收获到了对虚拟内存的理解更为深入,更好的理解进程内存的分配 记录一下大体的实现,这个lab其实包括了lazy sbrk的内容也是在分配数据结构时并不真正分配内存页,而在真正要用到这段内存时触发缺页中断,从而节省内存,在设计方面通过调用sys_xx函数读取栈帧中的传参,然后再调用系统中的接口函数,接口函数完整真正的操作sys_xx只是负责简单的传参和返回,把所有的sys函数写进一个文件,然后再调用不同模块中的函数这种设计可维护性和可读性都更好 设计一个vma储存mmap所需要的数据,然后建立vmatable,这些都是放入内核内存中,然后每个进程维护5个vma指针,需要分配时,访问内核的内存 在进行mmap时要fileup增加文件引用,然后把各个数据赋值,然后为进程增加地址空间但是并不分配物理内存,在写入时,trap判断addr是否在某个vma中的地址 在进行munmap要判断是否是把当前整段vma全部撤销,如果是要fileclose,同时检测是否需要写回磁盘,如果并不是那么还是保存当前的数据结构,但是修改七点或者是终点. MIT6S081_Lab_Networking这个实验是为E1000编写一个网卡驱动,这个网卡是由qemu模拟的但是看起像是LAN中真实的网卡,事实上连LAN也是qemu实现的,在这个实验中xv6ip地址是10.0.2.15,仅有的另一台主机ip为10.0.2.2,当xv6使用E1000向10.0.2.2发送数据包时，它实际上会被发送到运行qemu的(真实的)计算机上的适当应用程序.我们将qemu的用户态网络栈.我们需要更新Makefile文件完成.qemu记录进出的包在packets.pcap中可以使用tcpdump查看16进制文件 tcpdump -XXnr packets.pcap实验提供了分析自定义的工具包为ip,udp,arp.其中mbuf提供和管理包荷载,他将被整个lab使用. 阅读e1000的开发手册,这个手册包含了相关的的网卡控制器,qemu仿真82540EM,快速浏览第二章找找感觉,为了写驱动还要阅读第3和第14章,还有4.1,也需要使用13章的引用 我们的第一个任务是先完成收发模块,发送和接收数据包都由一个描述符队列管理，该描述符队列在内存中由xv6和E1000共享。这些队列提供了指向E1000到DMA(即传输)数据包数据的内存位置的指针。它们被实现为循环数组，这意味着当卡或驱动程序到达数组的末尾时，它将绕回开始。一个常见的缩写是指接收数据结构为RX，传输数据结构为TX。每当收到新的包时，E1000就会生成一个中断。您的接收代码必须扫描RX队列来处理每个到达的数据包，并通过调用net RX()将其mbuf发送到协议层。struct rx desc描述描述符格式。然后，您需要分配一个新的mbuf并将其编程到描述符中，以便当下一次负载最终到达数组中的相同位置时，E1000知道将其放置在何处。 当协议层调用e1000 transmission()时，数据包发送是由协议层请求的。传输代码必须将mbuf加入到TX队列中。这包括提取有效负载在内存中的位置及其长度，并将该信息编码到TX队列中的描述符中。struct tx desc描述描述符格式。您将需要确保mbufs最终被释放，但只有在传输完成之后才释放(NIC可以在描述符中编码一个通知位来表示这一点)。 除了读写描述符的循环数组之外，您还需要通过内存映射的I / O与E1000进行交互，以检测接收路径上何时有新的描述符可用，并通知E1000已经提供了新的描述符。 在传输路径上。 指向设备I / O的指针存储在regs中，并且可以将其作为控制寄存器数组进行访问。 您需要特别使用索引E1000_RDT和E1000_TDT。 先完成第一个任务 首先我们来看一下函数调用栈 调用顺序为(以写为例)e1000_transmit->net_tx_eth->net_tx_ip->net_tx_udp->sockwrite->file_write(从底层开始到顶层) 其中e1000_transmit是直接与网卡的接口,功能是把需要发送的缓冲区放入网卡的描述符结构中,这部分是需要查阅一定的网卡datasheet,没有太多的技术问题 第二个任务是完成操作系统的udp协议接口 其中包括sockclose,sockwrite,sockread,net_rx_udp sockwrite就是将内存中的一段地址,通过copyin复制进内核内存中的缓冲区 然后调用net_tx_udp不断地向下调用 sockread则是从缓冲区读一段代码 net_rx_udp是把网卡不断接受的包进行分配,通过遍历的方法,把所有的包分配到不同的sock结构中去 sockclose无非是从sockets链表中找到要close的sockets,然后关闭 其中阻塞读写的实现是时候sleep一个变量,然后当这个变量被叫醒时,这个进程也会被唤醒 最后附上链接:caowenbo2000/xv6-riscv-fall19 |
【本文地址】