Eden Mo Blog

Lab1 Stitching substrings into a byte stream Lab1实验手册: https://vixbob.github.io/cs144-web-page/assignments/lab1.pdf(2021 Fall) 部分实验目的和内容摘抄自手册。 在Lab0的Warm up实验，我们完成了一些小实验，它们来自应用层的协议，例如过时的telnet协议，邮箱发送的smtp协议等，通过coding，完成了两个简单设计，包括简单的TCP的socket传输，以及实现一个deque的读写缓冲区； 进入Lab1——Lab4，我们将逐步实现一个TCP协议：Lab1的任务是实现一个流重组器；互联网TCP下层的所有协议，例如IP、以太网协议等均不会提供可靠的传输服务，可靠传输服务依靠TCP服务实现。数据报的传输是一种分组转发，如何将切片数据报重组成一个完整、无误的数据报，是TCP协议要实现的重要依靠。 实验目的 实现一个类，这个类就是实现流重组的类，初始定义如下，为了直观，删除了所有注释并改写中文注释如下： 12345678910111213cla ...

贪心算法篇 1. 划分数组为连续数字的集合 给你一个整数数组 nums 和一个正整数 k，请你判断是否可以把这个数组划分成一些由 k 个连续数字组成的集合。 如果可以，请返回 true；否则，返回 false。 输入：nums = [3,2,1,2,3,4,3,4,5,9,10,11], k = 3 输出：true 解释：数组可以分成 [1,2,3] , [2,3,4] , [3,4,5] 和 [9,10,11]。 哈希表+贪心算法 假设数据可被划分多个连续数组，就从单个连续数组构造开始。哈希表统计各元素个数，nums[i]到nums[i]+k-1尝试构造k个数（因此num[i]应该有序），并且消耗个数，只有哈希表个数全为0，才可能划分成功。 1234567891011121314151617181920212223class Solution {public: bool isPossibleDivide(vector<int>& nums, int k) { sort(nums.begin(),nums.e ...

记录了计算机网络相关基础知识，参考书是谢希仁教授的《计算机网络》（第八版）以及美国Jim Kurose和Keith Ross所著的《计算机网络：自顶向下方法》（陈铭 译），前者是国内大学常用的计算机网络教材，注重历史发展、基础理论、常用的协议细节等描述，后者是网络应用领域的权威教材，横向技术内容比较全面，在国内也很受欢迎，贴两个大佬整理好的读书笔记： 计算机网络-自顶向下方法 GuoYi:《计算机网络-自顶向下方法》笔记 无论是哪本教材，经典的网络协议和理论是绕不开的，因为初次接触计算机网络是自底向上的逻辑，这个影响了笔者的一些逻辑接受方式。本文旨在从网络底层开始记录这些重要的理论，计算机网络发展的近半个世纪，各层的协议已经比较垄断，了解太多古老且边缘协议帮助不大，本文对于计网的入门应该是比较完整的体系。 计算机网络概述 互联网两个基本特点：连接性与共享 发展三个阶段 ARPANET向互连网发展；单个分组交换到互连网络；1983年TCP/IP成为阿帕网标准协议，不同系统可以在该协议上进行通信，形成互联网。 形成三级结构互联网；主干网、地区网、企业网（校园网）； ...

之前偷懒一直没看这部分，现在开始看很多C++风格代码确实离不开C++ 11引入的新特性，尤其智能指针、右值引用等，本来只想写这两个，但是用到的auto、python风格的for循环、lambda表达式等小特性也逐渐影响了设计者的代码风格，我在一段时间十分抗拒使用这种非常巧妙的写法，慢慢又变成会看不会写了，用和不用相当忐忑，因此就有了这个总结，确保忘记了也能很快拾起来；这里只记录用到且必要的，逐渐记录，追求完整版的还是移步官方文档。 RAII机制 资源获取即初始化(Resource Acquisition Is Initialization，RAII)不是C++11的新特性，而是C++之父很早提出的编程思想。RAII就是将资源和对象的生命周期绑定，对象创建自动获取资源，对象生命周期内资源始终有效，对象生命周期结束资源释放，避免了内存泄漏的问题。RAII类模板是申请、释放资源的基本手段，智能指针就是RAII的其中一种典型应用。 C++智能指针 智能指针是C++ 11引入重要新特性，用于解决raw指针需要手动管理问题，例如由malloc、free或者new、delete操作错误 ...

mmap实验 这个实验算是我花时间最长的实验了，定位问题和解决问题的时间大概是4：1，除了信手沾来的大佬，我认为很难按照hints从头写到尾写完解决完所有报错就顺利过关，因为有时候甚至很难确定问题的具体位置。这个实验很有必要听从Robert教授的之前教导，不要想着一次实现所有功能，尝试先实现一点，调试成功再去继续；因此本次实验概述既参考了hints本身固有逻辑，更多是从调试步骤解决，我相信这样的思路会为读者省下很大一部分定位问题的时间。另外，这个实验设计应该是有bug的，这部分疑惑连同debug问题被记录在Q&A； 实验目的 这个实验意在为xv6加入文件映射内存特性，所谓文件映射内存，就是将文件直接map到某个内存，直接对文件进行读写，绕过了read/write文件调用系统调用、将数据读到内核缓冲区再拷贝用户空间的过程，实现高效率的文件修改；文件映射内存涉及的内容还是比较综合的，要求有文件操作、内存映射，此外文件不可能常驻内存，因此必然采用了Page Fault机制来进行懒分配、就需要处理系统陷入，可见它几乎综合了前面的所有实验特性，设计不能不说别出心裁； 此外，本实 ...

卡内基·梅隆大学的这个CSAPP项目，几乎是计算机科学领域受众最广的项目了，在国内这个项目的参与者更是数不胜数，该项目涉及很多方面，例如汇编编译、操作系统、网络、并行等领域，项目使用的编程语言是C，分为八个Lab，深受CS专业、Java/Go以及11408选手们的爱戴。尽管博主是平平无奇的EE学生，四舍五入也算CS的半个同行了，这个项目在我这里优先级并不大，就当作一些阅读和记录随写了，时间会拉很长，可能做完这个项目就差不多过年了。 环境搭建 基本环境： Ubuntu 18.04 VMware 16 Vscode+SSH 虽说博客很多，但是从环境搭建开始介绍的还真没多少，但还是找到了字节大佬的gitee仓库，大佬将安装命令都整理成脚本了，Ubuntu 20.04及以下的都可以直接使用这个脚本安装，因此我记录下的基本都是这个脚本的内容，请参考大佬的origin分支installAll.sh即可； 可以直接运行并安装： 1wget https://gitee.com/lin-xi-269/csapplab/raw/origin/installAll.sh&&a ...

Lab0 Networking Warmup Lab0实验手册: https://vixbob.github.io/cs144-web-page/assignments/lab0.pdf(2021 Fall) 部分实验目的和内容摘抄自手册。 Networking by hand 这一小节只是简单的网络实验，不涉及代码，围绕telnet、netcat的一些操作展开，无兴趣的可以跳过。 Fetch a Web page 打开浏览器，访问http://cs144.keithw.org/hello，你会看到Hello, CS144!； 现在虚拟机可以做同样的事情，Linux下运行： 1telnet cs144.keithw.org http 这个命令建立你和另一台计算机（cs144.keithw.org）的可靠字节流，并且运行万维网使用的http(Hyper-Text Transfer Protocol，超文本传输协议)服务。telnet和ssh类似，都是用于远程登录或管理设备的网络协议，但telnet的数据以明文发送，仅支持基本用户名-命名验证，没有文件传输能力，基本 ...

大三学过计算机网络，后面就没有碰过这门课了。那时候的教材是谢希仁教授的《计算机网络》，为了应付期末考试还将课件和资料整理成了上万字的文档，放到校内网去低价出售，不知道光顾的那几位老哥考得咋样，可能不如多看几道课后题考得高分，多少有点误人子弟（哭），计算机网络是一个庞大的课程，往下它可以和硬件层各种协议交流，网上它需要提供应用层的各种软件接口，作为EE专业的主修课，授课的时候更倾向于信号处理、电路连接等联系，后面选修的《网络体系空间结构》更是承接了这个特点，几乎没有从代码的角度构建过这些通信协议，Stanford CS144利用C++以及容器算法，围绕TCP协议开展实验，技术栈还是比较匹配的，就尝试做做吧。 一个有意思的插曲是斯坦福的老师在2019年开源了这个项目，后续又出了2021、2023等多个版本，但是后面因为考虑到自己的学生可能会直接从开源仓库获取答案，遂关闭了官方仓库，要求其他仓库克隆者也应该将仓库转为private，一位清华大佬希望只去除“CS144”防止被google索引，而且回复道： I think opensourcing is irrelevant to w ...

前置提醒 fs分支的文件系统布局和常规xv6布局是不一样的，常规情况下，文件系统的磁盘布局是：46个元数据块（boot、super、30 log、13 inode 、1 bitmap）、954个数据块；fs分支下：70个元数据块（boot、super、30 log、13 inode 、25 bitmap）、199930个数据块；因为它需要支持二级Inode索引，知晓这点再去看代码（指系统代码，不是实验代码）才会理解。 Large files实验 实验目的 看过Inode层理论或者我的基础理论一文，就知道xv6文件大小的限制是每个Inode只能存放256+12个块大小，因此这里需要我们牺牲一个Direct Number，用于创建二级Indirect Number，这种提升是明显的，因为每个Indirect Number指向256个，二级的Indirect Inode存储的块是11+256+256*256； 具体实现 这个实现比较简单，只要看一下kernel/fs.c哪些代码涉及间接Indirect inode设计即可，即bmap函数和itrunc函数，前者负责将 ...

Memory allocator实验 实验目的 目前的页帧分配共用一个大锁kmem.spinlock和一个共用空闲页帧链表kmem.freelist，也即无论哪个CPU想要通过kalloc获取页帧，都需要首先从这个共享的数据结构获取锁和页帧，理论和实验表明这个设计是导致race condition最严重的事件之一，导致性能瓶颈；本节的实验旨在通过为每个CPU都维护一个独享的锁和页帧空闲分配链表，以降低进程内存分配时的严重竞争条件。此外还需要考虑当当前CPU耗光页帧时，如何从其他的CPU安全地“窃取”空闲页帧。 具体实现 从kernel/param.h获知了系统最大CPU核心数定义，这也是CPU遍历的基本原理； 1#define NCPU 8 // maximum number of CPUs 通过kernel/proc.c函数可以获取当前CPU编号： 123456intcpuid() {int id = r_tp();return id;} 全部代码仅在kernel/kalloc.c修改即可： 将kmem设计 ...