Y Combinator
TL;DR
combinator 函数必须不含自由变量,combinator 之间可以组合
Y combinator 解决了匿名函数不能递归调用自身的问题 (在不能给函数命名的 lambda caculus 中也可以递归了)
What is Combinator?
A combinator is just a lambda expressions with no free variables.
123456(lambda (x) x) ✅(lambda (x) y) ❌(lambda (x) (lambda (y) x)) ✅(lambda (x) (lambda (y) (x y))) ✅(x (lambda (y) y)) ❌((lambda (x) x) y) ❌
所以一般的递归函数都不是 combinator
12345(define factorial (lambda (n) (if(= n 0) 1 (* n (factorial (- n 1)))))
factorial 是自由变量,那么如何解决这个问题?只要再套一层 l ...
实现一个 crepl
https://jyywiki.cn/OS/2024/labs/M4.md
今年在追番蒋炎岩老师的 NJU OS 2024spring。因为之前已经做过不少 os lab,所以这次不打算做 os lab,但是发现 jyy 的非 OS lab 设计得都非常有意思,所以决定做一下。
以前我从来没有思考过 crepl 要怎么实现,没想到利用 gcc 就可以如此容易的实现一个 crepl,以前没怎么接触过的 so 库的用法和其本质也逐渐熟悉起来了。
虽说出于学术诚信上的考量 jyy 并不希望我们公开 lab 代码,但是这个 lab 确实没什么难的地方,相信不会有南大学子上网搜代码抄的。并且我因为偷懒直接使用了 system ,直接抄我的也得老老实实改成 fork & execve 实现:D
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798 ...
Linux 并发原语实现
起因之前听到群里有人在问条件变量的实现,发现自己对这方面一无所知。
先复习一下 xv6内核中用到了两种锁,自旋锁和睡眠锁。
自旋锁先看看实现
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354// Acquire the lock.// Loops (spins) until the lock is acquired.voidacquire(struct spinlock *lk){ push_off(); // disable interrupts to avoid deadlock. if(holding(lk)) panic("acquire"); // On RISC-V, sync_lock_test_and_set turns into an atomic swap: // a5 = 1 // s1 = &lk->locked // amoswap.w.a ...
博客写作部署分离实践
使用了 Elog 一键同步飞书文档上编写的博客文章到 hexo 仓库,以后博文迁移到飞书文档上编写。
发现这玩意好像也不是很好用,感觉可以自己写一个。不过感觉有点浪费时间,算了。
该博文同步自飞书文档
2023年度总结
CS 公开课
北大编译实践
算是编译器方面的一个启蒙,不过感觉连入门都算不上
CMU 15-213 CSAPP
其实课刷得有点马虎,不过把 lab 过完了
这课早晚得再过一遍
MIT 6.S081
对系统内核理解 0 的突破,也学着读了一些英文论文
参加了清华组织的 rcore 开源操作系统训练营,混了个结营证书
因为是实习期间做的,所以其实有点水,不过实验都做完了,也学了一些工程项目中内核的调试方法,也不算毫无收获
复习了一下 Rust
CS106X (正在学习)
本意是想过一遍 cpp,后来发现其实基础的算法和数据结构讲得更多。
不过听着感觉也不错,巩固下基础,对以后做力扣题也很有帮助。
参加了达坦科技的 MIT 体系结构公开课开源学习社区,现在在看 MIT 6.004
会学 Bluespec,lab 是做 MIT 6.175 的,内容是用 bluespec 搓颗 RISC-V CPU
真搓出来了想在上面跑 rcore(_我的天,还有比在自己写的 CPU 上跑自己写的系统内核更酷的事情吗_)
猛然发现 2023 是我的 CS 启 ...
周报
2023.12.18~12.24因为游戏账号被封了一个月所以开始写周报 push 自己学习的第一周(
看到学弟在学 6.824,说实话有点慌,真得 push 一下自己了
学习 & 工作
完成 CS106B 的 assignment 1,2
目前为止都是一些很简单的内容,还没有涉及到我比较想学的部分
参加了
Datenlord 的 mit 体系结构公开课学习社区
学习的课程是 6.004 6.175 6.375 ,这三门课的知识点重复度很高,大概只需要看 6.004 的课,做 6.175 的 lab,穿插学习 6.375 即可
不过大概率不会坚持到最后,只是一个学习计组的契机
学习体系结构的过程中也会并发进行另一门公开课的学习,目前是 CS106X,之后会做 445 和 824
生活
久违的下了个音游(邦邦)来玩,发现了一首很不错的曲子
下周计划下周其实离考试周就很近了,所以不一定能做完
过完 6.004 讲 bluespec 之前的内容
过完一半 CS106X 的课,至少再完成 CS106B 的两个 lab
解决 bear 在 MacOS 中生成空 compile_commands.json
在做到 xv6 的最后一个 lab 时,我终于忍受不了满屏的爆红,着手开始配置代码高亮。参考 https://zhuanlan.zhihu.com/p/501901665 配置 Intellisense,然后我遇到了一个问题:
make clean && bear — make qemu 生成空 compile_commands.json
我 google 查了一下,目前没有中文博客提到这个问题。我在 Bear 的 issue 下发现这个问题已经老生常谈了,因为 linux 和 macos 下 bear 的工作原理不同:
For your problem, here is a little background information… Bear works differently on Linux and Mac. On Linux it intercept the process executions with a preloaded shared object. This trick does not work on Mac. Instead it use ...
virtual-memory-for-user-applications
MIT 6.s081 lecture 17 个人总结笔记
参考:
https://mit-public-courses-cn-translatio.gitbook.io/mit6-s081/lec17-virtual-memory-for-applications-frans
https://pdos.csail.mit.edu/6.828/2020/readings/appel-li.pdf
之前我们知道,virtual memory 的 page fault 已经被内核玩出了花。进程 fork 的 COW 机制,虚拟内存页表的驱除机制等等,都是利用了 page fault 这个机制实现的。page fault 很好用,那么我们能不能让用户程序也利用上 page fault 呢?
为了让用户程序有效的利用上 page fault 机制,操作系统内核需要向用户程序提供一系列原语(primitives):
Prot1 降低单个 page 的 accessibility (mprotect)
ProtN 降低 N 个 page 的 accessibility,之所以单独提 ...
xv6-fs
下文中没有具体说明的场景均描述 xv6 文件系统的实现
好吧 我们就来详细捋一捋 fs
组成// todo
事务 Transaction
事务在用数据库的时候就已经经常用到了,但是没想到文件系统也有事务。从文件系统的事务实现中我们也可以管中窥豹数据库的事务是怎么实现的,数据库的 crash recovery 是如何保证的。
xv6事务的作用是保证一组磁盘写操作的原子性 (即要么全部完成,要么全部失败),从而支持 crash recovery。事务是我们对一组整体具有原子性的磁盘写操作的抽象,而我们是如何实现事务这个特性的呢?
当然是凭借日志系统。在xv6中,我们在执行一组磁盘写操作时,会先将这组写操作发到 block cache。block cache 就是磁盘 block 在内存中的 copy。
在write系统调用的最后(也就是事务结束时),这些更新都被从 block cache 拷贝到了 log 中,之后会更新 header block 的计数来表明当前的 transaction 已经结束了。
更新 header block 的计数这个操作是一个原子操作 ...
2023七月到九月总结
2023.7~9月总结从北京回来了,实习基本算告一段落了。至少线下实习告一段落了,能不能继续线上还得等结论。借此机会把 2023.7 ~ 9 月做的事情总结一下:
7月原本计划暑假里好好的把 xv6 给刷了,但是学长突然给了我快手实习的内推,于是暂时搁置了 cs 的学习,全心全意准备面试。一面自我感觉还算可以,但快手那边似乎是因为 hc 的问题迟迟不肯安排二面,鸽了我很长一段时间。这段时间最开始我是在准备面试的,然而等了好几天还没收到二面消息就重启了 xv6 的学习,记得是一口气做到了 traps lab,然后收到了快手的拒信。
收到拒信之后本着一不做二不休的原则又在 boss 直聘上海投,然而只收到了两家公司的面试邀约:禾多科技,字节跳动(抖音开放平台)。
禾多科技一面只问了20分钟,都是非常基础非常简单的问题,二面直接不问了,直接跟我介绍公司业务(做自动驾驶),但是因为只是随便投来练手的小厂,给的实习工资也不够我在北京生活,就拒了。
抖音开放平台面试问得比较有水平,可惜我算法苦手,而面试官又比较看重算法这一块,好死不死一面二面的算法题一道都没有做出来,当然是挂了。问了他们的业务,似 ...