Talk to the God——Notes for jyy OS

References

jyy ‘The Green Advisor’ OS, NJU 2024 Spring
License same as the original course.

Waiting List

• 第一节 ⛔
• 第二节 ⛔
• M1 ✅ 🛐🛐🛐
• 第三节 ⛔
• 第四节 ⛔
• L0 ⛔
• 第五节 ✅
• 第六节 ✅
• 第七节 ✅
  • 阅读XV6源码
  • 群除我佬的问题
  • *benchmark crimes的阅读
  • *RCU细节（缺少链接）
• 第八节 ✅
  • 学习一下GDB in Python
  • 阅读GDB文档，quick guide, cheat sheet
• 第九节 ✅ 🛐
• 第十节 ⛔
• 第十一节 ✅
• 第十二节 ✅
• 第十三节 ⛔
• 第十四节 ✅ 🛐
• 第十五节 ⛔
• 第十六节 ✅ 🛐 *🛐init.gdb
• 第十七节 ✅ 🛐🛐🛐🛐🛐🛐🛐
• 第十八节 ✅
• 第十九节 ✅ *🛐链接 🛐
• 第二十节 ⛔
• 第二十一节 ✅
• 第二十二节 ✅ *🛐XV6重要！
• 第二十三节 ✅
• 第二十四节 ✅ 🛐
• 第二十五节 ✅
• 第二十六节 ✅
• 第二十七节 ✅ 🛐🛐
• 第二十八节 ⛔
• 第二十九节 ⛔
• 第三十节 ⛔

绪论

在做了充足的心理准备之后，终于决定报了jyy老师的OS。

世界上有两种人：没见过神的人和见过jyy的人。

神自我革命，神制造困境，神传达启示，神引发灵感。
本篇作为与神的对话，忠实记录了 jyyOS 24Spring 的课程笔记，实验实录，教材读书笔记和心得感受。

特别说明

为了更适应英文环境，其实绝大多数的笔记都使用英语来记了，但由于绿导师的内容比较深，大面积的使用英语会使得“再提取”非常困难(鸡尾酒会效应)，而且个别思考内容我第一次用英语乱找一个说法写上，下次自己都看不懂什么意思，因此就用中文记了，我可am not那种Chinese英语mix着说的’fashion speaker’(doge)

Lecture 1

OSTEP Chapter 1,2

3 Easy Pieces: virtualization, concurrency, persistence

• virtualization: physical—virtualization–>virtual form
  
  *standard library (APIs)
  *resource manager
  ctrl-c used to terminate the foreground program in UNIX-based OSs
  ALSR: Address Space Layout Randomization: randomized the address where executables are put each time when the process is created to avoid buffer overflow attacks

• concurrency: differenet processes ‘simultaneous’
  *due to the OS execute the instruction groups not atomically, ill-designed multithreading programs may have unexpected results

• persistence: store data persistently, namely, I/O
  journaling:keep track of changes made to data
  JBD: Journaling Block Device
  and WAL in database
  copy-on-write:delay the copying of data until the moment it’s actually modified.
  duplicate on use

Design aims:

• abstractions
• performance
• protection(isolation)
• reliability(not fail)
• …

OS history…

Lecture 2

务必搭配jyywiki食用
可以认为是对状态机模型的深入阐述：
yzh版本：https://jackcuii.github.io/2023/07/04/ysyx0004/

“最小的应用程序” 说明了什么？ 程序是状态机，状态机不能退出自己，只能从外部退出，操作系统也是程序，也是状态机，也不能退出自己。
用户程序—用syscall—借助—>操作系统—用I/O message—借助—>硬件 来退出自己。

硬件呢？它也是状态机，但从主板总控的视角上看，供电控制系统是伺服运行的，它从未 退出 过

深入理解状态机模型：理解调用和递归
case:C语言解释器解决函数调用

2.1 和 2.2 还没

递归向非递归的转换：
其实就是手动来实现了栈，也就是函数调用的过程，跳出“出去回来”的思维模式，一切其实都是在“顺序” “前进”

某种程度上说，都是递归，或者说非递归就是递归，递归可以认为是一种固有的形式逻辑？

Spicy

更深入地理解状态机：理解编译和优化
编译就是状态机之间映射。
什么是优化？就是行为不变提高效率/减少资源消耗。什么是行为不变？就是系统调用不变。（其余的操作都是黑箱，只有调用才和外界产生联系）
不仅如此？系统调用也可以改变，保证系统调用的行为一致（行为的行为），可以把程序本身somehow做成调用，也就是系统的一部分。（前沿了）
额…那这和没有操作系统的区别在于？

还有很多🛐🛐🛐🛐

---

M1:pstree

M1 Log

• 确实觉得祖传代码应该好好打击了!
  • hy老师上周宣布算法的OJ由于系里禁止查重而取消，这两件事对比起来看让人唏嘘啊。。。
• 学习jyy在命令行里接入了GPT，感觉方便了许多！
• 没看后面的就想（问GPT）到了在哪找到state，切实感觉到了方法论的变化（GPT on the shell 之后，问GPT不用点鼠标了，频率飙升）
• 🛐 欠债：POSIX参数约定
• 编写可移植的代码？？？
• 关于Hard Test的事例，略感恐惧
  • 这个虽然给出了,但以后的实验呢，想都不敢想。。。
  • 这个或许可以通过strace来发现，但“行为相同”到这个程度……
  • 另外就是发现OJ平台好像可以看到错误返回值

Spicy🌶️

• Windows Kernel -> offer API
• UNIX (Philosophy) -> Everything is a file -> files
• 在某一个时刻，高级语言也会变成汇编语言，毕竟Programming终究也就是一个Wheel，好像跟蒸汽机没什么区别…

• man 5 proc

• 还是要认真读manual，实验了半天得到的参数解析规则其实在文档里已经写了，不过好像手册没有明确写熔断？（比如说读到-V之后就不再解析了，后面错误参数也不管了）

• 🛐欠债：如何写出string robust的代码？

• 🛐欠债：如何写出内存安全的代码？

• kthreadd pid=2 ppid=0 内核线程守护进程，运行在内核上的进程,并不会显示在pstree里, 而且发现查询后得知线程在对应进程文件夹下的task文件夹里，不过在/proc中cd相应的序号，也可以进去，虽然实际上不在那里也ls不到，不知道是怎么实现的。

  群除我佬之后发现原生pstree中是可以指定根的，只要指定根为0就可以发现了

🔱3.15 V1.0 感想：
前前后后写了10几个小时，终于得到了第一个稳定的版本，确实感觉很菜（
coding 能力确实低下（虽然有熟悉环境的时间）
不过也确实感谢去年ICS的自行加练，一定程度上没有让差距拉的更大
现在效率确实远没有群众大佬高，但是感觉能力确实在一点点积累，也希望后面能跟上大家的进度。。。
在有些地方踌躇过多，但因为其实没有实际的经验，所以写出来的还是缺乏健壮性。。。
而且这么简单的功能写了如此之多行，属实是屎山
但新的风暴确实已经产生了！ 🌪️🌪️🌪️

• 32/64 robustness
  第一次提交挂了，应该是32/64的问题，问了GPT值得注意的问题

32/64 Robustness Checklist:
🔻 指针整数转换的时候使用：uintptr_t/intptr_t
🔻 使用定长的uint32_t系列整型，尽量保证整形长度不变
🔻 检查数据对齐

• 使用#pragma pack或__attribute__((aligned))等指令来控制结构体的对齐方式。
• 在动态分配内存时，考虑使用aligned_alloc、posix_memalign等函数来获取对齐的内存块。

🔻 注意size_t的使用
🔻 确保使用的第三方库和函数的支持
🔻 使用预定义宏如__LP64__、_WIN64等实现条件编译
🔻 使用静态代码分析工具如Lint、Cppcheck等来检查。

L0-Pic Display

对Abstract Machine的理解：
某种意义上讲就是将硬件实现的最基本操作进行了封装和抽象，获得一个C库，这个库的flexibility 恰好可以让我们实现现代操作系统最基本的功能（虽然无法进行更精细的控制）。
使得底层具体的体系结构对操作系统透明。
YCM太讨厌了，一定程度上修好了，但还有一个一直报错。。。
需要仅有图像的二进制数据，可以用Linux工具（叫。。。）转化成ppm格式，去掉简短的文件头，再xxd转化成数组即可
一个非常经典的愚蠢错误，就是宏展开时的优先级错误，Debug了三个小时！！！！！！！！！！！

Lecture 3

务必搭配jyywiki食用

物理世界也是状态机，计算机系统的状态机通过Intr和外界连接起来。
如何控制一台裸机？把程序放到RESET状态里！
固件Firmware：系统配置，开机检查，加载操作系统
Legacy BIOS -> UEFI：丰富的I/O设备, PIC IPIC…
CIH病毒：破坏BIOS
EFI 分区，我们可以用mount挂载它。
还有一个Boot管理工具 rEFInd

• 手册并不是写给学生的，但要痛苦的读
• AbstractMachine可以让你绕开手册
• 模拟器需要做的其实就是状态转移

Extension: Learn from the God

GPT on the shell!

看到3.3节 浮现课上代码

Lecture 4

务必搭配jyywiki食用

• Coq 语言 -> 经过形式化验证
• 这门课的逻辑思路：建模->用Python实现这个模型的Toy（能实现的原因：操作系统就是一个状态机！）->对比Toy和真实操作系统的区别->认识真实操作系统的性质
• 如何设置？把所有性质都显式的assertion出来。
• 操作系统的理解：管理状态机的状态机, 最早的并发程序
• 那我们如何来实现一个“状态机的状态机”玩具呢？如果有简单的工具就好了！——Generator
• 数学视角下，状态机就是一个图，因此系统的状态就是图，因此就可以使用图论方法，比方说，用广度优先搜索验证程序/系统的正确性。

待完成，跑一下 30lineOS 复习Python Gene，余者完成

GDB TUI?

Lecture 5 (C) Intro of Multiprocessor

务必搭配jyywiki食用

• 多线程程序：多个状态机共享内存，有私有的（C：栈区/Assemble：寄存器）

核心方法论：Questioning and Proofing
对给出的结论持怀疑态度，并且试着去构造案例去验证。（Hands dirty…）

• 如何证明共享内存？简单！
• 如何证明不共享栈区？
  找到栈区？指向栈区的“指针”！->局部变量取地址
  如何大致画出栈区范围？ stack overflow! —> default 8MB

阅读代码：最小线程库 简化了线程API

mosaic的使用：直接连起来即可，管道喂给collect.py这样就可以收集结果。

Extention: LLM

LLaMA.cpp: Support run LLM on CPU (OpenSource)
https://zhuanlan.zhihu.com/p/622450960

• 需要reading: Quickguide GDB调试并发程序

• 开放你的思想：“放弃编程原子性的假设”，进行中的状态机会被改变！

  • 在一个处理器的多线程意义下，语句的原子性已经不存在了
  • 在多处理器的意义下，连一条汇编指令的原子性都不存在了

• 1+1都写不对了？确实，而且几乎没人能写对 Dekker’s Algorithm 是第一个
  Question 1+1: N个threads, sum最小是？ 2！任意多个线程都是！

  Thread 1 | Thread 2
  load 0   | load 0
  store 1  |
  load 1   |
  store 2  |
           | store 1
  load 1   | 
           | load 1
           | store 2
           | load 2
           | store 3
  store 2  |

• 线程安排是以一个NP-Complete问题，LLM级别的直觉 也不能解决！

---

• 更大的麻烦：编译器也是这么认为的！
  回顾编译优化，现在每一条指令之间都可能是系统调用！
  共享内存的背景下，几乎任何程序，都是“不可优化的”！
  ‘Heisenbug’: Copilot：“一个bug，你试图修复它，它就消失了！”
  • 更可怕的是当编译器执行了优化，可能会把并发错误隐藏起来！
    -O1 稳定 10000000：把和优化到寄存器里了，只最后写内存了一次
    -O2 稳定 20000000: 直接编译成一个加了，遇到的概率很小
  • waiting for flag bug:
    while(!flag);
    “等另一个线程举起旗子”
    也不行！编译器视角：要么直接过，要么死循环。
    • 解决（也是很多并发的解决办法）：插入不可优化代码，见jyyppt/volatile
    • 而本课程建议：加锁！

Spicy

• 更更更大的麻烦：处理器也是这么认为的！（处理器也是编译器）
  如果单线程乱序等效，处理器就可以乱序执行。
  处理器取出多条指令，然后判断是否冲突。欸？这不就是编译器吗，同样会导致并发错误！
  • “相对论效应”：复杂的相对时序
    多处理器的背景下，共享内存并不是简单共享“同一块”，会发现程序执行的绝对顺序完全不存在了，对于不同的CPU，观测到的时序可能是不一样的（因为多级缓存复杂的写入逻辑（copy-on-write 之类的））。
  • model checker 都失效了
    因为model checker是基于“一块共享内存”建模的
    困难的 memory model (比如x86的 write buffer)
    • 如果model不同，就很难相互模拟，比如ARM和x86之间

OSTEP Chapter 25,26,27

• PCB(Process Control Block) v.s. TCB(Thread Control Block)
• objdump参数：-g
• 工具使用valgrind, purify, helgrind
• pthread库基础
  • pthread_create 创建线程
  • pthread_join 等待线程返回（并不是所有的场景都需要）
• pthread lock
  • pthread_mutex_init
  • pthread_mutex_lock
  • pthread_mutex_unlock
  • pthread_mutex_destroy
  • pthread_mutex_trylock(一般不要用)
  • pthread_mutex_timedlock(一般不要用)
• pthread cond var 暂时略过

Multithreading Checklist:
🔻

Lecture 6 (C) Mutex & lock

务必搭配jyywiki食用

‘sequential creature’的反击：
互斥！不允许并发！给它们上锁，让状态机上的一部分缩成一个点！
如果都不让并发了？那还并发干什么？
运算是可以并行的。局部性原理（经典物理：“物体对相邻的物体产生影响需要时间！”），局部的计算都可以独立的进行，只需要谨慎的处理分块的边界。可以认为不能并发的任务部分远远少于可以并发的。

对于一个处理器，关中断就可以了！
但当某一个程序卡死了，OS就卡死了。
怎么办？外部监控，利用NMI来外部监控OS是否执行正常。（如重置定时器等）
因此操作系统统治了中断，禁止用户程序控制中断。

• 悲观的Amdahl’s Law: 如果你有的代码是不能并行的，那么
• 乐观的Gustafson’s Law (的更细致版本): 并行计算总是能实现的

普通程序不能关中断，多处理器也不能关中断，怎么实现互斥？
尝试用软件（算法）实现互斥：

• Dekker’s Algorithm
• Peterson’s Algorithm （改进后的Dekker）
  • 假设读写过程是原子的，任何时刻都可以执行load/store
  • 过程
    • 希望进厕所：举旗子，把对方的名字贴在门上
    • 之后看：对面没举旗 || 门上是自己的名字 👉才可以进
    • 出来的时候把自己的🚩拿掉
  • 保证了任意打断的正确性。你怎么知道的？Mosaic！

核心方法论：Let model checker tell you!
与其无意识的瞎猜，不如让Mosaic来告诉你答案！
如何知道这个状态机的性质，别忘了图论！
我们学习和研究的方法论改变了

我们只要发散和质疑，提出猜想！让好的工具告诉你对错！


再去想为什么。用机器来替代一些人类的思维活动。
同时可以用一些简单的必要条件来初步验证猜想的正确。
而且简单的验证代码如今还可以让LLM来帮你写。

但是在多处理器系统上简单的写个Peterson并不对（由于上一节课的内容），如果要正确的实现还需要增加大量的内存屏障。而且，如果有多个人上厕所，就不好用了。（所以在现代实践中，这个算法就没什么用）

为什么像人类一样简单的“等在厕所门口”不行？
不能同时“看”和“写”（正因为不能同时，所以中间可能会被插入）
要么闭着眼睛写，要么背着手看！
读&写不具有原子性

所以最简单的解决就是实现RW的原子性
用硬件来解决就可以了！
给我一点stop-the-world的机会，一个load/store.
（x86的xchg，MIPS甚至支持更多）
如果在add/inc前面加上lock，会被编译为原子指令
如果想要更多：TSX Memory🛐
原子交换xchg:世界上只有一个✔，但是每个人有个❌，操作就是交换，换到✔就可以进去了。别人就在❌和❌不停交换，也就是

还有cmpxchg 🛐

相比于上面的自旋锁，实际的自旋锁更为复杂
用户态的自旋锁会导致资源浪费！一核获取，N核围观

🔱System人不喜欢复杂的单点实现，简单能用就可以了，因为System本身就已经足够复杂了

OSTEP Chapter 28

• mutual exclusion
  • disable interruption(simple but bad, as above)
  • atomic instr:
    differs in different Arch
• fairness
• performance

M2:libco

pigeon 既能运行又能被动态加载的共享库。
许多库函数都会提供一个 init 函数，例如 co_init()，在希望使用时调用。但协程库实验中没有。如果你希望在程序运行前完成一系列的初始化工作 (例如分配一些内存)，可以定义 attribute((constructor)) 属性的函数，它们会在 main 执行前被运行。

再看到实验文档前，最初实现协程返回的思路是，在非主协程的协程栈底部增加一个co-yield的栈帧，这样的当协程返回时，就会自动的进入一个co_yield执行，从而实现结束后的切换。那么如何回收资源呢，就是在co_yield切换协程时，检查此时的指针是否在协程初始指针之前，如果是，说明协程已经推出了，就可以对对应的资源进行回收。
不过这个解决方案确实极其麻烦，而且某种意义上讲，好象就是自己实现了wrapper?虽然从

set long jmp差不多
最初的想法是在wrapper中实现资源的回收，看了文档发现这是不可行的，一方面会导致文档中所说的wait一个新协程的情况，另一方面是再多线程的情况下，这种设计会导致在栈被free后再次被分配给其他线程，此时在原来的位置创建yield的栈帧就会导致并发错误。

这个Wrapper实际上不能直接使用，因为wrapper变成了双参函数，使用的话需要修改switch_stack的函数实现，就在准备开始动工的时候，和室友交流意识到可以直接传入协程结构的指针，这样就轻松的解决了这个问题。。

有一个ASsert写错了。。。 yield的时候active co 也可以是刚waiting完。。。

刚开始wrapper的关系都搞错了，离大普。。。

对齐的大问题。。。还没搞懂

还有一些小错误
然后发现还有资源泄漏。。。
刚开始想fair不fair无所谓，后来发现完全不行
不是会死锁，而是会停住！i

逻辑严重错误!!!!

随机性问题；只有绝对随机才不会死锁？

最后的问题是不能yield到自己。。。。。。。。。。。。。。

Lecture 7 (C) Mutex & lock

我们目前是如果一个获取了🔒，整个处理器就被stop-the-world了。
这样的损失太大了，怎么办保证其他人的运行？把每个不同的资源准备一个锁，实现多把锁。
还要保证当一个解锁时，它所做的写必须都是对其他线程可见的，从别人的角度看，它对临界区的修改必须已经发生了（怎么实现先不用管，框架里帮你实现了）
虽然锁很好用，但并不容易正确处理锁。
容易出现忘记加锁了，从而造成数据竞争(Data race)
Warning：一定会遇到并发错误

---

但对于操作系统来说，问题并不止如此，还有中断！

注意：为什么用户态不需要在意这一问题，这是因为在用户态中的锁，在被中断时不会有人尝试去进入临界区，因此不需要在意中断问题（可以认为中断对用户态是透明的“一觉醒来”））

当你进入临界区，触发中断，再试图进入临界区，此时已经上锁了，无法退出！因此仅有自旋是不对的。

尽量不要用直觉去写代码，写错再删….

• 直观的想法：cli -> lock() -> … -> unlock() -> sti

• 一个锁过程中可能会调用中断再次运行这段代码，那么就无法获得这个锁：陷入死锁！

• 多个锁可以嵌套和穿插，但cli和sti只有一个，怎么保证回到从前？（注意：正确不是先关后开，而结束后的状态=开始前的状态）
  保证中断状态不变这件事不容易：必须要保存中断状态。保存在哪？
  每次关中断都+1，开中断-1，类似每次嵌套都把中断状态存到一个栈里，每个CPU都维护
  推荐阅读：XV6

  很好的spinlock代码
  一个启示：多写检查！！
  另外jyy写的main里面也有很多值得学习的东西。

群除我佬：
关于spinlock的main在本地运行结果不正确的问题：
还有就是TCG是什么东西？🛐

跳出fast-pass的投机思维：即假设自己的代码是对的。
以后就没有人告诉你对不对了！而且你的未测代码越来越可能不对！

Spicy🌶️：(半)无锁互斥

benchmark crimes
自旋锁的scalability极差！（类似于反比例）操作系统只在及其短促的操作上使用自旋锁。Linux Kernel的分析见ppt链接
但Linux有大概180K个需要内存保护的函数，怎么办？
一个特性：绝大多数数据结构都是Read-mostly
可不可以读不加锁？RCU(Read-Copy-Update)策略！
牺牲读写的一致性，选择write-on-copy，写入的时候复制建一份新的（对于常见数据结构，不是傻傻的复制，又高效的部分复制），这样总能读到一个。
用户程序应该能容忍 少量的读到错的。（比方说路由表，读到错的大不了重发一次）
这样就解决了性能问题。
什么时候扔掉旧版本？阅读材料（并没有啊。。。）

XV6 Spinlock拿来在实验里用就行了

---

性能问题：大量的自旋锁会浪费大量的资源。
持有锁的线程被中断？？，换一个自旋的，这样可能会100%地占用资源。
怎么办：在自旋的时候调度到其他线程（由操作系统来做！）
pthread_mutex_lock
🌶️一个更聪明的实现：Futex: 如果无人争抢就不会陷入操作系统内核，如果有人争抢就会交给操作系统调度。 fast-slow path
有很多并不显然的困难问题 🛐

至少目前，mutex就是黑箱就可以了

Lecture 8 (Snack)

务必搭配jyywiki食用
好用的工具 Compiler Explorer

记住两件事：
未测代码都是错的！
我写的都是错的！

编译器 + 编译选项 + 特定的硬件 + luck = BUG

Requirements ---> Design ---> Code[Fault] ---> Execution[Error] ---> [Failure]
              ↑           ↑        ↑                                     ↑
mistake here--+-----------+   Where you make                        Where you find

调试就是观察状态机的侧面，以便于找到“第一个错误的状态”
printf就是状态的摘要，使人能够通过知识进行判断：快速的对执行进行分块，定位错误在哪一个块上
但在很多情况下，有很多的错误状态只是一个值，长得和别的值没有什么区别！

---

调试一切（状态机）！
如何解决一个新问题？
UNIX哲学中，整个使用计算机都是编程，你都可以去观察侧面，怎么观察？

• make program verbose -v
• Profiler perf and Trace strace

经过查询，工具中的verbose好像真的是通过多级的if则printf组织的。。。(GPT)

核心方法论：strace/verbose 的不理解？GPT可以告诉你！
GPT非常擅长解释充满了陌生名词但没有复杂逻辑的东西

报错信息有的时候不可靠的，但是它一定“在什么地方打印出来”。
初学者（别人遇到过这个问题）—> 资深程序员（发现原因并解决问题）（“找对象一定给要找程序员：因为出了问题都是自己的原因”）

重新发现GDB： GDB文档 QuickGuide
一些梦寐以求的功能其实GDB已经实现了： 比方说逆向执行！（还有和并发相关的）

Extention

GDB Cheat Sheet.
I have been on it for sometime, though pigeoning!
Commandline-quick-sheet

Spicy: Really Spicy!

时间压力下，我们会被迫用肌肉记忆解决问题
—> 停止自己的技术演进
—> 最后技术与社区脱节，成为油腻的中年“键盘侠”
怎么办？

应用调试理论：什么是好的代码？
Self-Explanatory Code: 代码应该是自解释的，不需要额外的注释
Self-evident Code: 代码应该是自证明的，可以通过阅读确认和需求的一致性。

核心方法论：因为AI还“不够聪明”：AI is a benchmark! 如果你的代码AI能够理解，那么说明是好代码。

---

写出BUG了怎么办？

• 多测试
• 缩短Error和Failure：断言

编译选项：-fsanitize=address 自动添加断言检查存储错。

Lecture 9 (C) Sync: Producer-Consumer

补充互斥：宏观理解锁
应用程序也会被中断，为什么不需要上锁？因为中断对用户程序是不可见的，中断程序(内核态)不回去试图获取用户态的🔒。

同步：使得两个变化量在时间上具有相对关系。
“在某个瞬间互相已知”
状态机视角的同步，简单的状态变复杂，再让世界收束到简单的状态（像一个洋葱🧅）
”相互已知的简单状态“
“电子乐后驱jyy” （电子乐这个地方为什么一定要加锁？）

消费者生产者问题，可以解决99%的同步问题！
概念模型：往有限缓冲区放东西/取东西

第一个错误的生产者-消费者实现
因为没有满足检查和生产/消费的原子性。

第一个正确的生产者-消费者实现
虽然它总是在“自旋”在浪费cpu资源！
获取🔒，条件满足则持有不释放🔒，条件失败则释放重试（自旋）。

这是一个万能的方法，上面的depth判断可以抽象成CAN_PRODUCE/CAN_CONSUME
这样就是一个万能的模板了！

核心方法论：为什么“打印括号”？获得一个容易写程序进一步检查，直观的指标！把问题具象化！

有一个通用的模型，一定有对应的接口实现。
我们发明了条件变量，但还不要这么傻（不自旋retry，休眠，等待唤醒）：当然有现成的库！

使用了条件变量的接口！很可惜，还是错的 书上解释了🛐

真正全局正确的实现，正确打开方式

一个条件变量实现真正正确的P-C

1. 唤醒后再检查 （从wait陷入睡眠后会implicit释放掉🔒，被唤醒时会implicit重新获得，因此应该直接开始检查）
2. 唤醒所有潜在被唤醒的人

我们最好这样写↑

用signal需要两个条件变量来实现🛐

为什么可以解决 99% 的问题？
计算任务都是有向无环图，计算图切分（有序思考方式）

1. 一个生产者，每个核心是消费者，生产者（调度器）拓扑排序计算图，把无依赖的任务扔进buffer，消费者取出任务计算即可。（线程池的工作原理）
2. 还可以每个结点都设置一个条件变量。同步条件就是依赖的都完成了

1%
如果遇到了写不出的条件的怎么办？
小鱼🐟问题：可以借助状态机进行状态转换。
写出了状态机，还是可以用条件变量解决。
条件就是在状态机当前位置是否有可以走的出边.

🔱”我们现在有一个<还有一个>,还有_,那我们可以实现什么呢?可以实现一个小鱼🐟!😍”
Lovely!

Lecture 10 (C)

我们可以用互斥锁来控制同步
happen exactly after/before 就是一种同步
而🔒的获取和释放其实就是一种exactly after/before

pthread要求必须是同一个线程require和release,因此这类DIY的操作是不允许的!
我们用锁来实现计算图的计算: 只需要每一个边一把🔒,每个节点先都尝试获取出度边的锁,之后开始运行,所有人尝试获取入度边的锁,一旦获取就算自己的,算完自己就释放所有出度边的🔒.这样就实现了”并行的拓扑排序”
没问题,也是现实可用,只是在pthread的要求下不行!

所以你就发明了信号量
互斥锁就像是一个更♂衣♂室手环,但缺点是,互斥锁只是一个手环,同时只有一个人在更衣室,除非你开一大堆锁(但这显然也不行,因为每个人不是VIP,并没有一个绑定的手环,手环是共用的)
因此信号量就实现了这样的,共用的公共计数资源机制
P-prolaag取出一个手环
V-verhoog往盒子里面放一个手环
信号量可以认为是一个特殊的条件变量,只不过它隐含了手牌数量大于0
当盒子里只能放一个手环的时候,就是互斥锁:信号量是互斥锁的拓展

“当可以使用一个整数来表达同步条件的时候,我们就可以用一个信号量来表达它”

信号量来实现生产者消费者问题？
有一个Empty和Fill袋子,生产者从Empty里拿一个球,生产,再放到Fill里,消费者从Fill里拿一个球,消费,再放到Empty里

信号量不太好实现选择的问题(比方说小鱼🐟问题中的状态机的分叉)，二选一的情况下必须要你(此时放球的人)来决定球扔给谁，但也因此更高效（不会唤醒所有后继节点）

---

信号量的困难:
哲♂学♂家吃饭问题

• 用信号量很难实现：所有人都会拿起左边的筷子，然后等待右边的筷子，最后死锁(没有保证拿筷子的原子性)
• 用条件变量：无脑实现，因为互斥锁保证了一下拿两个筷子。

怎么用信号量解决？有一些方案

1. 从桌子上赶走一个人，总有一个人能拿到。
2. 给叉子编号，总拿大的、小的(按需编号互斥锁)

但这是一种trick，并不scalable。
————因为当问题稍稍变复杂时，你都要去重新考虑这个信号量设计，而且还不一定能解决。相比之下，条件变量更加简单, 更普适。
对于现实世界，更多的并发问题都是线程数规模远小于单线程任务量，条件变量较大的开销就显得不值一提。

更困难的例子:
用信号量实现生产者消费者.
很难实现,如果我们用一个值nwait去维持等待的线程数
因此在wait中,需要三个操作

1. nwait++
2. 释放保护nwait的锁
3. P操作

这三个操作不能交换,还必须保证原子性

NotLect 10.5

反思一下,什么是条件变量?
条件变量其实不是一个变量,也跟条件没关系,而是一个”铁索连环!”
他是操作系统的提供的一种服务.
这种服务支持:(1,2不寻求OS帮助是无法实现的(不确定,应该是吧))

1. 原子性放锁休眠
2. 原子性获取锁唤醒
3. 叫醒服务(任一个或者所有)

那么什么条件呢,条件就是一个🔒保护起来的数据结构
这是你自定义的.
提供的环境变量就是一个铁链子
你写程序的时候就是将铁链子和🔒绑定在一起.

什么是信号量呢?也是一种服务.
不过这个服务维持了一个整数量,
提供原子的放和拿的操作,且成功就返回,不成功则休眠
且可以满足多个线程的操作的需求s

Lecture 11 (Snack)

Web历史，详见ppt
Web带来的并发问题：请求和更新不同的资源，我们希望他们并发。
Solution: 禁止并发，Event-based concurrency，允许异步操作+回调函数，实际上没有任何并发。
动态计算图：Promise：直接描述动态计算图。

关于高性能计算的部分确实是需要关注的，毕竟和本行Arch密切相关

这节课其实很难给出一个明确的总结，但一个take-away message可以说是黄胖子的话。

Lecture 12 (C)

死锁

• AA-Deadlock: wait for self.
• ABBA-Deadlock: wait for each other.

L1会遇到！

关于Deadlock的论文 🛐
死锁产生的必要条件
可以每次等待的时候的输出一下等待关系从而发现死锁。

避免死锁

• Lock Ordering: 给所有锁编号，严格按照编号顺序加锁,”持有最大的编号的锁的线程总能继续运行！”

Data Race
Read-Write/Write-Write

• 对于Green Hand，严格避免数据竞争！

L2：更加隐形的数据竞争

无非就是上错了🔒和忘了上🔒
两条原则：用🔒保护数据，严格避免数据竞争

本质困难：“反人性(sequential)” 和 “后果自负(No compile error!)”

Atomicity Violation（ABA）
Order Violation（BA）：use-after-free… 最后那里？

Lecture 13 (C)

太奇怪了，明明记得记了这一节的笔记，但是却完全找不到了。。。

Lecture 14 (V)

务必搭配jyywiki食用

控制系统的加载

阅读minimal加载的makefile🛐

• fork 复制一份状态机（为什么只能复制？
  区分：返回值不同
  fork bomb！
  USE mosaic
  fork_demo为什么是48种？？？

  • 诡异的“8个hello”
    你没有正确理解printf!
    buf也被复制了！
    unbuffer, line buffer, fully buffer…
    （谨慎的使用任何隐含假设！）
  • fork 时候默认继承了环境变量

• execve
  抛弃现有的所有状态，准备好参数，设置为另一个状态机的初始状态
  进程总是从这个开始

  • PATH 环境变量：execve的查找顺序

• _exit
  atexit (normal process exit 时调用回调函数, 注意，这是C的机制)

  • return 非0
  • exit(x) 都是Normal exit

  上面都是调用libc–C语言库的退出，都是对C可见的，所以都是Normal exit

  • _exit(0) 利用系统调用直接退出执行的是exit_group
  • __exit(0) 是执行exit

  上面都是非正常退出
  调查这些问题，别忘了Strace…

“操作系统是状态机的管理者，它把所有状态机都剪碎存在数据结构里，当想要执行的时候再拼接起来，加载到CPU上。”

Lecture 15 (V)

状态 = 内存 + 寄存器
“内存” 是什么？
工具

• /proc/maps
• pmap (pmap 1好像比较奇怪)
• gdb

procfs的文档 man 5 proc 🛐
地址空间是有读写权限的地址段
部分与一些文件对应offset, dev, inode, pathname
来看看pmap的结果

🌶️Spicy:vvar,vdso

vvar,vdso
不需要陷入操作系统内核的系统调用：只读
vvar(READ)
vdso(READ|EXEC)
把操作系统维护的一个变量只读地放进用户进程的地址空间。
eg. 系统时间
🔱因此我们需要的并不一定是syscall(陷入内核执行)，而是有一种进程和操作系统通信和交换数据的机制就可以了。
因此也可以往地址空间一个指定位置放一个请求来让操作系统执行，操作系统自旋检查并处理请求——真的有人在做相关的研究！

入侵进程的地址空间！：gdb
外挂！

• 最早期的游戏外挂，一个物理的查找表！Game Genie
• 劫持红警的地址空间：Filter
• gdb就是一个巨大的外挂！
  • 访问proc/mem procfs提供给我们的一个文件，直接指向整个地址空间，可以用文件操作来修改地址空间
  • 或者说外挂是一种游戏的调试器！

ydotool

按键精灵

Lecture 16 (V)

操作系统对象：
第一种理解：文件（有名字的对象） Everything(what thing? 操作系统对象) is a file.
第二种理解：字节流（终端，外设）和字节序列（普通文件）
访问对象需要找对象指针：程序中的指针指向对象，但永远不可能指向“操作系统对象”。
如何指向“操作系统对象”，系统调用！（Matrix中的人不会看到外面的罐子！系统调用就是蓝药丸！）
文件描述符（会考）：指向操作系统对象的指针

Win’s File Descriptor：handle 句柄（历史问题）

---

另一种对象 IPC Endpoints
管道（一种特殊的流）：pipe就是buffer 读口和写口共享
两端一般是用两个文件描述符指向（但文件只有一个！）
并不是严格的buffer，
如果没数据，读不会返回
如果没人拿，写不会返回

实现了InterProcCommunication
是一种进程间同步机制，可以实现成异步的
命名管道：
用mkfifo()创建，有对应的文件名

We also have UNIX domain sockets for local inter-process communication–they also have a name in the file system like “/var/run/docker.sock”. This is similar to a named pipe.

匿名管道：
用pipe()创建
自己同时持有两个口，有用吗
在fork时，duplicate一份管道不会被复制，因为管道不在地址空间里，只是一个指针，所以是浅拷贝。
之后，关掉一个口，就建立了一个父子进程之间的管道

操作系统：对象+API
Shell “Kernel的壳”：Kernel-Shell-I/O-Human
Shell是把用户指令翻译成系统调用的语言
易用性是核心特征，高效，简洁，目标是工作流搭建
>,<,2>,|,&,&&,||,$(),;,<()…
和GUI做到的一样（其实是GUI和CLI一样）：^Z,jobs,fg,&,bg,wait

🛐man sh

为什么人工智能时代我们还要读手册（可惜学期中真没时间读（太摆了））
因为人工智能只会告诉你最常用的解法
Extend: GPT Archive 也引入这种补充功能

必先利其器：init.gdb gdb的预运行脚本，可以实现比方说跳过一些函数等等。🛐
还可以利用Python编写脚本作为hook等等。

_start 定义程序入口，链接器会把程序入口指向这里。
两个编译选项 -ffreestanding -nostdlib

💲不要假设任何特定的库函数，例如main函数，会存在。这对于编写操作系统内核或嵌入式系统的代码非常有用，因为这些代码通常不会链接到标准库。
💲不要假设任何特定的硬件地址布局。这意味着编译器不会假设任何特定的内存布局或寄存器布局。
💲这个选项通常用于编写操作系统内核、引导加载器、嵌入式系统代码或其他不依赖于标准库的代码。
——GPT

Freestanding shell
Python script

dup系统调用
亿些细节：Shell语句的优先级；空格会导致灾难；bash/zsh（更强的shell）不兼容（Shebang指定bash）…
case: 文件描述符的定向设置先进行，然后才是命令的执行，所以sudo echo hello > /etc/a.txt无法正确执行，因为没有权限改描述符！

💫CLI和GUI的未来：AI时代，历史记录和环境可以成为Silent Prompt
将会出现AI-OS（已经有许多相关的工作了）GPT-CLI
Karpathy好像就在做这个？

Lecture 17 (V)

务必搭配jyywiki食用

             applications: steam.exe
任何程序 -→ -------------|--------------  
          sys utilities: shell,gcc,ls...       
----------------|-----------------
          libc等C语言库
----------------|-----------------
      OS: 对象+API(syscall)

pipe的补充(见ppt，阅读手册🛐)

核心方法论：深入阅读手册的方式：尝试复现手册中提到的行为！

“C语言是最通用的高级语言，C语言是一种高级的汇编语言”
“最薄的抽象”
看一看 C23！🛐

libc 可以用多半C语言本身和一些底层支持实现。
已经被标准化 ISO IEC
POSIX libc的子集： 最大的体系结构可移植性！

glibc提供了_start!

核心方法论：学习glibc，使用简化版的glibc，比如musl libc 🛐
我怎么知道？可以去问问GPT的教学意见（绷，上面的后半行甚至是copilot补充出来的）

控制gcc链接哪些东西，不链接那些东西，比方说链接自己的glibc：可以参考musl-gcc的机制！（GPT可以写这种东西）

execve 之后做了什么：我们来调试！
细致的去看程序的一生：加载，argc,argv,envp哪里来，libc怎么控制进入你的程序，乃至libc如何退出你的程序…

循序渐进：minimal.img -> freestanding shell -> musl libc -> glibc…

---

体系结构无关的抽象：ppt上的一页链接 🛐 （GPT帮你阅读！）

核心方法论：闲来无事读手册！（真的很需要热情。。。）
参考一些手册和有趣的实现，可以获得大量的编程经验，系统知识，和奇技淫巧！
一个常见的practice会在各种各样的实现中被反复，从中学习！
ppt上给出了很多很多RTFM entries!🛐

offsetof宏：一个奇技淫巧！

printf带来的启示：一个软件工程上的原则：避免“code clone”
tls 🛐

核心方法论：从各种各样的奇怪机制的调试中获得和加深对系统的认识！此时再打开手册，就不显得困难了！🛐

🔱计算机世界中没有任何的魔法！（只要你不写错）

L1-pmm

一些相关笔记

2024 Lect17

本身是Lect 17的内容，整合过来。
优化必须要基于Workload！
🔱Knuth: Premature optimization is the root of all evil.

核心方法论：Workload哪里来？读论文去！
其实还有profiler, tracer…

System 人的智慧：该省省该花花，先浪费，再在现实问题情景中找补回来

2022 Lect14

面向Workload进行优化
越大的内存块生存周期越长，越少见
越小的说频繁，因此必须优化小内存的分配！（让他们并行）
Fast & Slow Path Philosophy
两套实现，快的实现用于频繁的，无法成功的时候去诉诸Slow Path
Thinking fast and slow
This is a ‘System Way’ of problem solving!

Thread -> CPU ?
Segregated List
16B-4KB(<=4KB – FastPath)
4KB-1MB(>4KB – SlowPath)
CSAPP 9.9.14

心路历程

第一版：异想天开的开端

第一想法就是用树来维护，结果看到底下发现不行！
其实往后想一想也是不行的。。。
随后有了第一版的构想：
就是4KB以上的分配采用一个树形结构来维护(一把大锁)，4KB以下的分配直接采用一个线性的分配，关于小面积的分配交给哪个4KB物理页，为了防止碎片破坏连续性，考虑允许和CPU核数相等的并发申请（4KB以下），每个页面设置四个状态EMPTY，FRAGMENT，FULL，DEAD，尽量往FRAGMENT的区间里分配小内存申请。
这个方案内部有很多问题，
一个是表存在哪
还有一个想法是用一个32bit的位来缩略表示页内的情况。

竟然在没看之前想到了大小内存分开处理和bitmap，可能是从Manual上的Workload获得了一些启发。

上面我的是初步构想，之后去看了jyy的往年视频的讲法

第二版：前辈经验的启示

知道了segregated list和buddy system的概念，设计出第二版。
大内存分配采用树，小内存分配采用segregated list。

重构了代码，写的过程中发现了无穷无尽的诡异的技术细节（后来发现是一个误会导致的）。。。以及过分高估了OJ要求的强度。。。

1. slab空闲链表怎么实现分配？
   好像并不是轻松的O1
   在有free的状态下，我怎么找到第一个可用的？？
   如果存储一个链表的结构，那很难找到free后的可用的，或者说永远往后，加一个计数判断满没满，然后到底了没满就从前面开始？这个均摊代价好像还可以接受。
   另外就是一个比较O1的方法，就是用bitmap存储，然后直接lowbit可以找到第一个
   这个上锁好像会有一些问题。。。
   只读不写是不是不会遇到并发错误，看错了在找一个就可以？（好象不是，小心！）
2. 我们如何在堆区里面存储这些控制数据结构，我们制造一个不能回收的伪分配？（就当静态区用）在堆区里面专门划分出来一快用来做这件事？
3. 而且我们应该中央存储还是分布在每一个链表项里呢？
   都不是很好办
4. 为什么Slab必须要上锁，既然必须要上锁，那么为什么不直接用一个大锁呢(在这个实验里不会影响性能把)，另外就是如果我不能获取一把锁，那我是不是可以直接放弃尝试然后去尝试获取下一把，这样不就不用自旋了吗？

写的时候的一些想法，哈希log表，优化一点点log

第三版：崩坏的复杂

第三版进一步否定了这个大内存树（主要是发现状态过于复杂），采用空闲链表管理大内存，但是处于某种奇怪的信念，总是想要优化新slab分配的过程，因此又引入了大页（近乎于两层的Buddy system）。后来发现动态的链表是无法实现的（必须依赖静态的结构）。因为无动态分配下的链表实现的复杂性，单独抽象出了链表实现。此时的代码复杂度达到了空前绝后的状态（干代码1000行+）。可以想象，这个代码几乎无法维护。
下面是当时记录一些想法（大量内心os预警）：

又回到 buddy system，有一些其他想法。

1. classical buddy system , 当在一块slab里到头的时候，就直接分配下一块slab，如果剩余减到0就直接释放。
   这可能会遇到一个问题，就是如果上来就开一个int，就会导致一直占着一块slab不放。
2. 想到一个改进，就是设置一个阈值a，如果a大于某个值，就开一块新的，如果小于某一个值，就在该块里lowbit查找，（a类似于一个超参数）lowbit时候bit map int的指针还是只往前走。这样就可以避免。相应的可以有两种策略:
   1. 每一次分配的时候，都是以bit map int的单位分配，这样每个32位组里面的分配时间是均匀分布的，出现32个都没被释放的概率比较低（本身也很低了，尤其是a设置的比较小的时候）
   2. 当第一次沿slab分配的时候，按照一个addr向前走分配，之后的分配lowbit搜索。

不过这种还是会有问题:

1. 就是如果有一堆不放的话，可能会导致某个分配非常慢，当然可能a设置合适不会出现这种状况，也可以设置一个probe最大的容忍度，太慢了就开一个新的。
2. 就是使用率不会超过a，但说实话，classic的使用率应该也比较低。
3. 最大的问题是，这个方案需要每一次计算一次除法，这还是可能会致性能问题（其实还会有额外的判断和乘加，但这个应该不是问题(lui)）。尼玛，根本不用阿，比较指令不就行了么，除个p！！！！！
   (有空尝试一下比较一下性能，这个直接的想法应该早就有人想到了(没去Literature Review)不过抛开Workload谈优化都是耍流氓，但jyy的Workload大家也看不到啊(悲))

可以发现当时在错误的路线上越走越远…

第四版：向命运低头

在和Green Advisor聊了聊之后发现之前一个重要的误解，就是，当一个Slab被分配完之后，其实不需要继续作为一个Slab，因此不需要维护一个当前的Slab的链表。当Slab分配完之后，被当作普通的大内存即可。

最后采用的是空闲和占用交替的“数组上链表”+buddy的朴实无华的策略。

印象深刻的BUG

经历了12天的印象深刻的Debug。熟悉了Kernel代码的组织形式。

对齐问题

刚开始的logceil函数写的有问题，但由于用于检验的程序和原程序都使用了这个，本地测试一直没发现。。。

多描述不一致问题

（只记得有一个关于这个的错误）
当存在多个描述描述同一个语义时，必须注意这些状态是否一致，而且两种描述的同一状态的覆盖期会有细微的时间差，需要注意这个gap的原子性。

一个压力测试的漏洞而隐藏的bug

当时不停地报Out of heap allocation，显得莫名其妙。
后来发现是一个很离谱的问题，就是一个错误的假设，就是假设Slab的分配一定成功。当一个NULL被返回的时候被不全面的assert检查特殊豁免了，当第二次分配一个从0地址开始的slab才被发现。
这个问题最终还是被我意外的发现了。我的压力测试虽然各种大小的分配混合且数量多。但因为是随机的分配释放，所以虽然组数多，但在概率上讲，不会同时存在很多分配，只分配的测试时候还严重低估了课分配的地址数量（认为几百万就可以了）。最后这个问题还是在多线程意外发现了（但并不是并发错误，而是单纯的四个线程就是4倍的地址数量达到了触发bug的阈值。。。）

感想

感觉写实验的时候要避免两个问题。
一个是草率：
这个实验从开始思考到写出第一个版本的代码经历了很长时间（一个多月）关键的原因是重构了四次代码。主要都是一些事情没想清楚，写到一半才发现根本无法实现。
另一个是假设：
就是要避免上面Out of heap allocation的问题，要尽量避免假设，一些好的方法是把情况列一个形式化的载体，比方说表格，或者用状态机视角去分析。

M3:GPT2 并行化

先想到一个简单的方案，发现MM是最占时间的，可以直接不看其他的源代码，对MM实现分块并行化，而且四块就可以。(事实就是这样。。。)
而且直接劫持原函数的接口，这样不用做任何其他的修改

Lecture 18 (V) Genesis of OS (and Geniuses)

务必搭配jyywiki食用

尽在不言中。

---

🪐Linux历史：我们操作系统界也有自己的原神！

---

操作系统=对象+API
Linux最初的对象是？
initramfs: 最开始运行的时候操作系统里面什么都没有，只有几个文件…
之后

调试initramfs

在之后systemd会根据etc/fstab来挂载其他的文件系统，配置驱动…
之后就可以构建我们的应用程序世界辣！
演示中使用的是busybox httpd工具，构建了一个http服务器，并且端口映射到qemu外面了！
这就是一个完整的操作系统世界了！

整个操作系统立于一个“很小的东西”上面，因此也可以替换它
Windows Subsystem for Linux: WSL
Linux Subsystem for Windows: Wine
模拟系统调用就可以了

🔱你就可以在里面做“一切事情”，都是构建在一个很小的东西上。
但是他们都是改变世界的想法！

Lecture 19 (V) Executable, Static Link

什么是可执行文件？
操作系统的对象，存储状态机(静态的)初始状态的数据结构。
execve = 初始化Process(?) + 加载ELF（规定了程序执行进入entry时地址空间里的东西）

Binutils 🛐

ELF并不人类友好，并不满足”信息局部性”。(ABI手册规范的)
那我们重新设计一个友好的！

现在的Core Dump是ELF文件❓
很久以前的“a.out”是非常简单的。（但支持的非常少，比如说用于调试的符号都存在哪里？）

“FLE”：代码、符号、数据,重定位！
静态链接是什么·？就是合并同类项(把相同的节合并)，再重定位，就是计算出待定的指针值(因为已经合并了,所以所有待定的符号位置都确定了)。
书签们也要改好（符号）
复习ICS: 高级语言代码(.c, text) –预编译(宏展开…)–> (.i, text) –编译–> 汇编指令序列(.s, txt) –汇编器as–> ELF(.o, bin)
复习一下ICS链接部分🛐

重要的FLE实现

Shebang #! 指定默认的解释器,还可以加参数
利用了所有脚本语言的#都是注释的性质,Shell根据#!找解释器,真正解释执行时又由于#是注释而被忽略

为什么要这么反人类的ELF
ELF是高效的，内存节省的，industrial 的选择
分段,别名,字符串表…
来处理数G大小的可执行文件(甚至已经捉襟见肘了)
threadlocal(.tdata,.tbss)

更多的仔细了解elf🛐

ELF加载器,和FLE没什么大区别!
ELF和FLE都是数据结构,只是ELF是二进制的,而且复杂的多
数据结构是什么? elf.h
可执行文件是描述状态机初始内存状态的数据结构

execve中的行为，我们也可以自己实现！
没有execve的execve

回头看启动加载器,会发现它做的是相同的事情,但因为是加载操作系统的,所以也没有系统调用,加载的位置是物理地址空间,而不是虚拟地址空间(存疑)(此时虚拟化还没被激活)
因而不是用mmap,而是用硬指令来完成搬运.
是一个”没有mmap的没有execve的execve”

Lecture 20 (V) Dynamic Link

A software engineering view
实现运行库和应用代码分离

• 应用之间的库共享(占用存储太大了)
• 大型项目的分解
• 依赖也是克隆，可以同时更新无数的程序（否则需要重新链接无数的程序）（用于打补丁）

Semantic Version 版本号的规约

Dependency Hell
今天的人们对软件系统中的漏洞可能是“恐怖的和平”！

• libc.o（静态链接）
  没节省内存（还是要在内存里有很多份），而且还解析了一大堆用不到的符号
• libc.so(动态链接)
  在a.out中额外定义一张跳转表，把对动态链接库的库函数的调用，变成查表
  编译器生成地址无关代码，加载后把位置填进表里即可
  这一段代码实际上是被共享的，是由OS的虚拟化支持的（只读页面的共享）

我们发明了GOT!(Global Offset Table)
ELF中的.rela.dyn节
这个表项中的offset是这一待重定位的地址的GOT表项的位置（相对加载的初始地址的偏移） （关于什么的？RIP）
GOT中记载了一些待动态解析的符号，里面是指针，当共享库被加载时，这些指针会被填充（符号解析）（GOT里面存的是什么东西，绝对的还是相对的）

关于extern，函数不需要写extern，因为默认就是外部链接的，但是变量需要写extern，（关于强弱符号）

是只有#include<>时候知道？还是前面写一下的时候知道？（不能检查出来吗，那既然知道要构建PLT，为什么不能直接跳呢？

但是：编译器编译时候并不知道一个符号是要静态链接还是动态链接。这种问题存在于什么条件下，什么编译选项下？

• 如果都查表：太慢了！
• 如果都直接跳转，指令中的偏移量只有32位（64位的偏移量太不友好了），在64位的地址空间中，不够跳转到共享库的位置！

解决办法：PLT
在编译时，假设所有的函数都是直接跳转，来留出重定位。（那么liba-2.o里面printf应该是一个直接跳转）当进行动态链接时,（进行链接时），动态链接器会判断是不是对共享库函数的调用（这里肯定有一个优先级或者配置的问题，存在细节），如果是的话将直接跳转的指令目标地址设置出一个构造出的代码段，这个代码段会调用动态链接器，动态链接器会查表，然后填充GOT表项，再用其他的指令跳转到真正的函数地址。

（这是“什么时候”？还是在加载时？如果是在加载时，如何判断某个符号是动态链接的？所有没被填充的就是？（静态链接发生在加载前？））如果是根据GOT判断的，我怎么知道给谁创建空的GOT表项？

对于数据呢?
(当且仅当-fPIC时？)编译器不知道它将会被静态链接还是动态链接，因此它会做出保守的选择（否则编译成静态链接，偏移位数就不够了，就无法补救了），假设都是来自外部的，生成一个GOT表项…
除非显式地告诉编译器这是静态链接的attribute((visibility("hidden")))

out-of-memory killer
听一下

ldd
ld.so 🛐

核心方法论 SEE ALSO in Manual

LD_PRELOAD

M4(&5?)

man mkstemp
man exec
man wait

这个实验表明，编译和解释并没有明确的边界——在 OpenJDK 的实现中，即便是 “解释器” 也是编译的 (只是没有经过优化)。动态 (just-in-time) 技术在程序运行时 (而非程序执行前) 进行编译，并将编译得到的二进制代码 (指令/数据) 动态加载。其中最成功的案例之一是 Sun (现在是 Oracle) 的 Java 虚拟机 HotSpot (现在是OpenJDK的一部分)，它使 Java 彻底摆脱了 “性能低下” 的诟病，也是引领 Web 热潮的核心后端技术。另一个最成功的案例是 JavaScript 的 V8 引擎。借助 Webkit/v8，Chrome 成功地把微软公司的 Internet Explorer 拖下神坛，并且奠定了 Google 在互联网技术领域的霸主地位。

man dlopen
strcat 缓存区溢出， md GPT3.5背锅
man unistd
man dlfcn
WEXITSTATUS
wrapper技巧
int res = execlp(“gcc”, “gcc”, arch, “-x”, “c”, “-shared”, “-fPIC”, “-Wno-implicit-function-declaration”, “-o”, output_name, src_name, NULL);

(gdb) set follow-fork-mode child
info interior

M6

不计其数的问题
这个更象是一个现实的工程问题，一个不同与之前的考虑，就是尽可能的避免崩溃，而不是尽早崩溃
设计模型（启发式搜索
还有就是
自动机编程范式，结合用户态虚拟化的编程语言，可能会适应某些场景

学习一下高级的宏使用

printf wrapper

Lecture 21 (K) Syscall, intr

系统调用：向操作系统的 “函数调用”

还是不要被调用误导
状态机的世界根本不存在进入和返回的概念
只有在适当的时刻进行状态的改变

syscall指令 = ‘jal’ 跳转并提权

• 存寄存器
• 改变权限，切换栈
• 跳转：跳转到哪里？ x86: IA32-LSTAR 寄存器的值

一个细节：跳转之后，’VR眼镜’(CR3)并没变，但是还要能访问到内核代码，因此要有一个固定的映射。

• 以前只有分段: 存在一个固定的物理内存段里
• 有页表之后：内核被固定映射到0xc0000000
• 今天的Linux，用户空间最大到0x7fffffffffff，内核从0xffff800000000000开始

我们来调试syscall
随便调试一个具有系统调用的程序是没用的，因为此时gdb运行在用户态，看不到系统调用的内部——用qemu！
qemu -s -S

中断
x86：极其复杂的中断机制
理解：强行加入的syscall
以RV为例理解中断：
跳转进内核之后做什么？

• 先保存现场（封存状态机）：要小心的使用寄存器！RISC-V有一个scratch寄存器，用来帮助保存现场。（硬件只会给你保存有限的几个）
• 执行操作系统代码
• 选择一个状态机进行恢复，返回(原来的，或者schedule到另一个）

https://github.com/Jackcuii/jyy-codes-test-and-read/blob/master/thread-os.c

Lecture 22 (K) from Thread to Process

务必搭配jyywiki食用

Process = Thread + VR glasses(addr translation)
用一个数据结构来维护地址的Map（一个映射函数）
RBT？不够快！

• 用Radix Tree来实现 riscv, x86, arm
  • A blog
  • (1024叉树 for 32-bit machine)
    • i386的二级页表
  • 64-bit不那么好玩了，4KB页面中只有512个指针了，不整。
    • x86_64: PML4, PML5
    • riscv: 只要三级，只能索引到512GB的内存
  • 因为页表在内存里，不够快，所以还是要用TLB
  • CR3指向一级页表的基址
• 不实现 MIPS （“文艺实现”）
  硬件只管TLB缓存和物理内存，页表什么，随你喜欢！
  缺页发生时，产生一个异常，交由操作系统处理。
  提供指令 tlbwi tlbwr 给操作系统写入TLB

  硬件在变得越来越可编程，一种是本身就可编程(FPGA…)，一种是提供软件的接口自由实现（就像这个）

• Hash table实现 invert page table(“疯狂实现”)
  把进程号也作为虚拟地址的一部分，直接进行Hash
  会有安全问题

疯狂填写（无能狂怒）nop 的libbloat.so：

• 不会榨干内存！因为OS会把它们指向同一份代码(映射函数不一定是单射)
• 即使是100G，也不会被只读内存榨干！
  Kernel Samepage Merging, 不只两个进程指向的“逻辑位置相同”的代码会被合并，“内容相同”的页也会被合并！
  （即使是Malloc的，也不会！）
• 即使是随机代码，也不会被榨干！Demand paging
  磁盘可以被映射到地址空间，此时使用指针访问它
  缺页，操作系统通过数据结构发现它被映射到设备，把该页读入内存再加入映射
  地址空间装不下这么大，该怎么索引？不是正常指针，用文件描述符这种独立的指针🐒尚需确认

进而涉及 Swap page机制（页面交换/虚拟内存）
操作系统会把闲置的页塞回磁盘里去。

高性能的实现fork：Copy-on-write fork()

• 岁月史书：vfork()
• 只读时浅拷贝，不得不copy（发生写事件在共享读的页上，发生一个Exception）再deepcopy
• 可以为服务器作进程快照：可以当父进程挂了的时候，用快照顶上。

所谓局部性就是，你手和眼睛的接触的范围有限，你用VR眼镜的视线之外的部分，操作系统可以随意乱搞。（牺牲一些性能，但保证不会被榨干crash掉）

一些场景下使用2M的大页

🔱The most important characteristics of the system are its simplicity, elegance, and ease of use.

🪐UNIX的岁月史书（ppt）
gets(buf)

“在人工智能的辅助下什么”34min左右…好像被剪掉了。。。

Extention:XV6🛐

https://pdos.csail.mit.edu/6.828/2023/xv6.html
https://jyywiki.cn/OS/manuals/book-riscv-rev3.pdf

Lecture 23 (K) Schedule

务必搭配jyywiki食用

调度的机制：上下文切换
进程无法直接看到内核代码，怎么跳过去？
x86存在机制，可以将内核代码映射到进程的地址空间，但是被页表保护。
xv6和Linux不同之处：在进程地址空间完全不存在内核代码。
怎么进入内核？
Tramploine(RX)(跳板代码): 一个小的代码片段，用来跳转到内核代码，位于地址空间的最高位置，还有Trapframe(RW)，用来保存进入内核前的状态。
跳板的其他用途：动态链接标准库，JIT编译器，软件热更新…

gdb-multiarch

xv6的initcode.S，xv6系统的第一个用户态进程，就是一个ecall，
ecall之后，跳转到Traploine，保存上下文，切换VR眼镜，就进入了内核世界，读取系统调用号，调用内核函数。
调用的是exec，把进程空间布置好，状态机重置为init程序（jyy那个init哪里来的？），然后系统调用返回。
“操作系统是一个C程序，当加载第一个进程后，就变成一个中断处理程序。”
uservec, usertrap, usertrapret, userret

一个软件工程的经验：错误处理的较好写法（C）
任何错误都跳到 goto bad 然后在bad里面统一检查处理回收。

调度的策略：
建模→预测→决策

UNIX Niceness
[-20, 20) 越小的越坏，“坏”就是不愿意让给别人
Nice相差10大概是资源差十倍
When Nices equals
不能Round-and-Robin，低占用的即时前台程序不能和高占用的后台R&R。

最初的天才想法：MLFQ（动态优先级）
如果用完了时间片，说明就是计算密集的，就降低优先级
如果让出CPU，说明是I/O密集的，是交互式的，就提高优先级

现代的想法（Linux）:CFS (Completely Fair Scheduling)
让每个进程尽可能公平共享“一个理想处理器”
记录所有进程的执行时间，永远给目前真正运行时间最少的那个。
Nice的实现：记账的时候按一定的比例，好人钟快，坏人钟慢。
Linux 用红黑树来维护这个进程池

🌶️Spicy: 现实中的处理器调度（bug）

优先级反转,假如有三个进程,中低高优先级,LP/MP/HP
LP获得了一个共享资源(持有一把🔒)
这时候HP来了,要等待LP,但由于有MP在中间,HP就被阻塞了
HP在等待LP,而LP在等待MP,这样实际来看,就是MP一直在有效的推进(HP反而在自旋等待),就变成MP阻塞了LP
“First BUG on Mars”🪐
安卓手机越用越卡，一些垃圾应用获得高优先级的🔒，导致了系统的卡顿

怎么解决?

• Linux：解决不了，拜拜
• 优先级继承,当高优先级等🔒时,持有🔒的低优先级进程就会获得它的优先级.
  不是万能的,比如说条件变量时,你不知道下一个是谁
• lockdep进行预警.

多处理器:
对称多处理器 SMP: 使用的时候,认为每一个处理器是一样的.
不能随机分配，线程退出之后处理器会”围观别人干活”
也不能谁空分给谁，会损失缓存的信息：同处理器跨核L1就没了，跨处理器L2/L3也没了（具体架构相关）
调度可能浪费时间?不调度有可能会等待过久!

事实上SMP还是不理想的建模：现在的处理器(异构处理器,大小核)不对称了(NUMA)
离得远/近的核心调度时间相差悬殊,有的小核不能胜任一些密集的任务.
lstopo

多用户系统的公平:namespaces,cgroups

程序执行也没有那么简单：
有时更多的资源(在更多处理器上调用)反而会变慢。
共享内存的Cache slot在不同处理器之间疯狂横跳。
而这个现象确实会被复现(示例代码),这反映了操作系统对调度问题的建模和优化只能是有限的.

Hot-plug: 有的主板支持CPU的Kernel控制的下线,或者是物理热插拔.

当问题走向不可控……交给用户来处理吧!

OSTEP Chapter 13

Some OS isolate its different parts from others to achieve even better reliabilty. MicroKernel

Lecture 24 (K? K of what…(the world)) from OS to MetaPhysics

务必搭配jyywiki食用

Turing Complete
Turing machine 1D
life game… 2D
We… 3D
程序判断自己是否在虚拟机中，正如我们观察自己是否在Matrix里

• 🔱What if we add Neural Network to the life game?
  Do we create a new life form?

• How do we know the future? (seriously)
  We pray.(we syscall)
  How do we(proc) know travel in time?
  We(proc) syscall.

• 🔱Programming is nothing but syscall!

• We could set some 0-1 array in a special-defined area in the gamelife, and then the area will set the next state of the game.
  We could set the number and syscall, so our programs interact with the ‘outside world’.
  We set some bytes to I/O registers with OS, and the screen make people addicted to Genshin Impact life game. Some keys are hit, and OS is killed.
  🔱We could put some infos into the singlarity, then ….
  🔱We could put some fish and pigs in the sacrifial ceremony, and the god give us something? (People with poor imagination, we do the same thing up till now with the support of neurons!)

• 🔱Whether causality exists if we can travel in time?
  Whether the mathematical system is consistent if we can query the oracle in the special area of the life game? (Maybe P=NP?)

• 🔱jyy：人类优越感是用来维持人类生存的机制。我们带着残缺来到这个世界，我们用机器来带来完美的救赎。
  宣扬机器主宰论会不会被当成邪教被👮‍抓走，所以我刚才都停留在数学的讨论上。

• Debugger：
  Time travel in state machine. record and replay. (GDB, QEMU)

• Profiler实现：
  最简单的实现，不停的每隔一会中断，看在状态机在执行什么，这样就可以得出统计意义的perf。
  jyy在此时语言了下一节课的设备翻车，神秘的2.4GHz频段阻塞事件(狗头)
  硬件支持：Performance Monitoring Unit

• Verifier：
  如何应付更广阔的取值空间？（state machine 分叉太多？）用更加巧妙地表示，状态不是取值，而是方程组！

很多个终端
tty,stty这个问题在之前修正Tmux的时候涉及到了
ttyd

man setpgid/getpgid 🛐

信号（进程可能会从各种来源收到信号，比方说在被中断时被设置）
信号的处理和中断的处理类似，不过信号不会直接触发中断，而是等到该进程被中断的时候处理到来的信号。
操作系统给程序发信号
Core Dump什么的也是信号
但信号可以被屏蔽，可以自定义handler，SIGKILL不能被屏蔽
kill是发送信号，而不是纱！🪐岁月史书

我们不能掌握复杂系统。我们建造一些简单的系统。我们尝试理解复杂系统的时候，不由自主地去用我们能理解的东西去理解它们。然后想一想现在系统和这个toy有什么区别。

🔱A Fairy Tale:
How to maintain an aircraft carrier, such a complicated system?
Genius design it. We just lookup the manual and wrench it, then it works.

Lecture 25 (P) 1-Bit Storage

务必搭配jyywiki食用

States in Physical World

不错的文章，这个网站也很有用

存储器就是一个bit/byte(或者更大) Array
可以按block读写数据
稳定、可靠、可辨别地改变物理状态
把字刻在石头上！

磁存储🪐：电磁效应，物理世界和数字世界的Edge

• 小朋友的磁写板就是最简单的二位磁存储！
• 顺序读写的时代悲歌，旧核时代的机械浪漫：磁带（）📼
  成本很低，但只能顺序读写
• 我们意念合一！：磁鼓()🥁
  n个并联的一圈磁带和读写头，比较快的随机读写
• 杂交的内卷（磁带磁鼓）：磁盘()💽
  随机存储的速度还是相对很慢
  改进：
  Advanced Host Controller Interface (AHCI)
  Native Command Queuing (NCQ)
  半离线地处理读写指令，由磁盘控制器对指令进行排序和合并
  …等等技术
  如今的磁盘控制器和缓存已经是一个小的CPU！操作系统无脑发数据就可以了。
  存在着一整套协议，一定程度可以控制磁盘的service（比如确保写入持久存储）
• 保存图标上的活化石：软盘💾
  移动的存储介质
  可移动的代价：不清洁的环境，读写非常慢

坑（光）存储🪐：

• 把字刻在石头塑料上！：光盘💿
  可以刻得很密集，还可以像刻版印刷一样压出来！
  便于复制分发，一瞬间就可以写入
  非常持久！
• 书写新世纪的挽歌：🗿Project Silica
  今日份罗塞塔石碑
  刻在玻璃内部的永久存储

电存储：短时高速高密度的最终解决方案

• SSD闪存🔌
  几乎具有所有优点：容量越大，读写越快，超大规模并行
  已经超过了接口协议的能力
  磁盘控制器：电路并行+算法+一个微型的计算机系统：使得优化后的读写极快
  （软件定义硬件！）
  致命的缺点：Wear out，放不干净电，万次读写
  FTL：如何克服Wear out？又一个虚拟内存系统，VR眼jing

  • security issue:
    整个是一个copy-on-write系统，修改就复制，尽量不做抹除操作
    这样并不能抹除
  • 越加密，越复杂，越安全，可靠性就会越低（无法恢复）

  SSD可靠性由软件决定，但是软件是一些公司写的，竞争的环境 -> 必然会存在偷工减料（狗头）

Lecture 26(P) I/O

计算机系统对外部世界的边缘：I/O
Mem-mapped I/O: CPU并不关心自己接的是什么，它只能看到一个地址空间
把一部分地址空间分给“外面”就可以了
I/O就是“线”
把寄存器赋予一个地址
通过控制寄存器，状态寄存器，数据寄存器，来和外设交互

• 串口(UART)🔌
• 键盘控制器接口(IBM PC/AT 8042 PS/2)⌨
• 磁盘控制器💽
  • ATA 40pin
  • IDE,SATA…
• 打印机🖨
  • 早期的画的是“矢量图”，“移动的画笔”
    画面就是绘制指令序列
    PostScript 是描述页面的DSL (Page DL),类似于一种汇编
    PDF 就是 PostScript Ultra
    打印机的CPU就是一个Page DL的解释器，
    打印机是将汇编指令翻译成机械运动的机器
• Something not exist yet: 💫
  获取良好的可拓展性：为未来的外设留下接口
  需要一个特殊的接口，把I/O虚拟化👇
• PCI总线：
  总线有自己的虚拟的地址空间，CPU通过总线和外设交互
  总线会识别I/O设备，给他们分配总线地址，并负责把数据分发到各个I/O设备上
  CPU只能看到一个I/O也就是总线。
  • 总线还会桥接到其他总线上，比如USB总线
  • 即插即用不是一个Easy story

这么多的外设都是中断来源，但CPU只有一个可屏蔽中断引脚
所以需要一个中断控制器,管理（排序）来自不同外设的中断
查看 lspci -tv
Intel 8259 PIC, APIC…

• IPI: CPU 也可以给 CPU 发中断
  总是先Reset一个CPU，执行启动程序，然后再给其他CPU发IPI，启动他们
  CPU 也是 CPU 的外设！

释放CPU的算力：如何处理非常慢的外设交互（eg.大数据存盘）
CPU是General Purpose的，当它长期做某“一件事”的时候，就是一种浪费。
交给其他的CPU去做，不过这个CPU不需要很强：只会memcpy就可以了！

• DMA 协处理器：只会load/store的协处理器，在memory和register(device的)之间的搬运工（甚至可以memory-memory）

计算机系统里充满了CPU
CPU的核心，DMA，打印机，网卡…
以及…GPU！

• GPU
  • 马里奥的奇迹🪐
    在性能很低的处理器上实现60fps
    GPU的祖宗NES PPU
  • 走向3D
    虚假的真实感：Screen Space Ambient Occlusion
    从伪-3D到空间多面体建模
  • 真实的真实感：Ray Tracing
    从眼睛射出光线，由于光路的可逆性，追溯到光源/非光源，从而获得真实的光照效果

走向异构计算：有限的、固定的、重复的指令，把这个功能分离出来，就可以做得时钟周期更快，并行度更高

TLB Flash摸鱼了🐟 (没找到这里，，，)

L2-kmt

这个实验其实反而没有特别的多的设计层面

对于单核状态下，就朴实无华的创建和销毁，采用了自旋锁+睡眠信号量，调度采用轮询+引入一定的随机性(50% 跳过一个)。
对于多核的共享栈问题和V操作插入问题
共享栈利用额外的schedulability标记，在陷入之处标记为不可调度，记录上一个线程，在新线程再次陷入内核时释放上一个线程。(是不是也可以用锁锁栈来解决？)
对于V操作插入问题，设置完状态释放锁之前标记wait_but_not_yield标记，在yield时候归零即可，填补上这个gap。（这其实是一个L1提及的“多描述一致性”类的问题）

印象深刻的BUG！！！！！！非常印象深刻！！！！！！

可以说是终生难忘的25天。

前面调的BUG是“上游投毒”(doge)

过于信任绿导师的代码了（狗头），应该先关中断，再取cpu信息。
不过在调试这个的过程中，逐渐把qemu连接 + gdb script + python的调试方法熟练了起来，也算是很有收获。

最大的一个BUG

应该是有史以来给我印象最深的bug，可以和千年虫并列(bushi
当时已经有些破防了，还多次骚扰助教学长和绿导师求助。
主要就是本地测试没问题，主要测试了这几个

1. Producer-Consumer4线程
2. 打印ABC
3. 在中断处理程序中V，用户程序中P
4. 混合corner case在用户程序中P之后创建新线程

正确同步且负载比较均衡，但OJ永远都是Rej

• 改变多个调度策略的实现 依然不可以
• 改变信号量实现（自旋/睡眠） 依然不可以
• 测试队列 压力测试正确
• 多创建大量线程 没问题
• 瞪眼瞅检查（假设1不用信号量
• 语义一致性检查
• 清栈问题（当时没解决这个，因为单核不存在该问题）
• 百万打印量级别的压力测试 也没问题
• 去掉assert 报错原因还是不变
• ……

最后另一位群里同学发现了（震惊于这位哥们的想象力），是因为在pmm->init阶段打印log导致的，改了之后就通过了。。。（嘿啊喂手册上明明说可以的，建议改一下捏（半恼））
还遇到了不常见的Heisenbug，打印log就消失，不打印就出现

想记录一下关于清栈问题的理解（想到的一个便于理解的视角）

可以不考虑是CPU拿来状态机跑。
而是认为CPU是固定地址空间上“跳动的指针”。

记录一个室友提供的逆向思维

在负载均衡时，不要想着测试的视角让线程找不同的CPU，而是反过来避免CPU”占一个”

一些感想

感觉这个实验做到后面，整个人都有一点被异化了，耽误了同时进行的许多事情（其实也没有占用很多时间，因为多数时候都觉得没什么课修改和测试的了，主要是心态炸了有点开摆）。觉得以后无论做什么还是要心如死灰 心平气和（和水群以及做好错误信息反馈(逃），这样能最大程度“负载均衡”和发挥生产力。

Lecture 27(P) vfs, Driver

文件描述符是一个指向操作系统对象的指针！
文件是“虚拟磁盘”（把磁盘的一部分映射到地址龙剑）
Syscalls: mmap,lseek,ftruncate

GPT的一个趋势：self-validation

还是那个方法论：用AI来写一个小的验证代码

无尽的细节：偏移量管理
父子进程共用一个offset，文件描述符是浅拷贝。（存在大量的并发追加操作，如写入终端、写入日志）
open:获得一个独立的offset
dup: 两个共享offset
execve: 文件描述符不变
O_APPEND: 保证写入的时候是追加，打开时永远指向文件末尾

有大量的细节都是与fork交叉带来的，因为进程的状态机并不只是内存和寄存器，还有操作系统内核中维护的文件描述符表、页表、信号处理表等等。
操作系统：平方级别（）的复杂度膨胀

如何实现Everything is a file？
真实的文件好说，虚拟的文件呢？
在每一个文件相关的系统调用中，都会有一个switch case，根据文件的类型，调用不同的处理程序。
如果这个文件是设备的话，那么就会调用设备驱动程序。
如果这个文件是虚拟文件的话，那么就会调用虚拟文件(e.g. /proc/{pid}/maps)的处理程序。
这些东西假装自己是文件，如何假装👇
文件 = （部分）实现了文件操作的 “Anything”（能“像文件一样”被操作的东西都是文件）
设备驱动: 把系统调用 “翻译” 成与设备能听懂的数据的内核代码
vfs的虚拟文件们：

• devfs
• procfs

都是有一个驱动程序，在file syscall，往用户传进来的buf里写，假装自己是个文件。

.ko文件是一个内核模块，可以被动态加载到内核中？🛐

对于设备来说，以上是和设备的数据交互（核弹），还有和设备的配置交互
控制可以是数据的一部分 ANSI ESCAPE CODE
提供新的接口（也是寄存器）：
ioctl 函数原型参数后面是…👉完全由设备决定
是操作系统最大的💩🏔️来源（User-define是原罪啊！）
复杂性：不计其数的hidden speciefication
procfs巨大的负担（procfs的秘密）
同时也非常脆弱（无数的应用程序parse procfs的内容，一旦损坏会导致系统的完全崩溃）

KVM设备：硬件虚拟化，一个完整的可以加载到物理机上的虚拟机🛐

Lecture 28(P) fs

务必搭配jyywiki食用

回顾:文件是虚拟的磁盘镜像
信息的局部性：树状层次结构。
数据/非数据的文件管理：

• Unix-like: 都在/中
• 数据Windows: C: D: E:…（A. B.是软盘）每个驱动器一个根
  非数据Windows特有的机制：注册表（一个巨大的配置文件）
  但注册表不在文件系统里
  Win里面有一类为设备的对象，但也有类似Everything is a file的机制

mount 🐟
mount就是目录树的嫁接。（改掉了原来的目录，但是文件还在）
mount就可以把某一个设备(其实就是一个支持某些操作的字节序列)挂载到某一个目录上
procfs是一个不需要设备的文件系统，只需要一个驱动程序
/proc 其实只是一个普通的目录，只是procfs被mount挂载在了上面（甚至可以被挂载在不同地方很多份）
提供了灵活性，不同的目录可以分配给不同的设备

把磁盘挂载到目录上,不会形成一个自指么???

文件可以是是虚拟的设备
那么把某个虚拟磁盘(比如某个.img文件系统镜像)挂载到某个目录上呢？
loopback device（不能被写在？🐟）
制造一个虚拟的设备loop，把文件关联到这个虚假的存储设备上，然后把这个设备挂载到某个目录上

FHS 有一套文件系统的标准 🛐

目录管理 mkdir,rmdir,getdents
User-friendly: globbing

文件系统允许一个文件被多次引用

• 硬链接,一个指针,指向相同的东西,只有名字可能是不同的
  可以想一下,实际上你看到的是若干个文件名和一个实际的文件的对应关系
  所以删文件的系统调用是unlink,意思就是把这个实际文件的引用计数减少一个
  (是文件系统实现的一部分?所以不能链接不存在东西)
• 符号链接/软链接(Symbolic Link)
  更加宽松,可以指向任何地方,甚至可以指向不存在的东西
  jyy’s Galgame
  每个目录都是一个状态机,软链接可以作为状态机的迁移

文件系统实现:
现实我们面对的是块设备而不是随机存储设备：小的读写都会被严重放大
目录如何实现? 也是一个虚拟的文件

• 古早现实：单目录文件非常少不超过几十个，单文件比较小，文件系统要尽可能小
  纯真的链表最为合适
  目录：就是一个文件
  两种设计🐟
  File Allocation Table (FAT)
  解决可靠性问题：存很多份

  FAT32.读代码🐟

fat32.h实验可以使用

UNIX文件系统:
不同于FAT,引入inode的概念,可以是文件或者是目录,包括元数据甚至是文件头,具有一定的局部性(比如同一目录文件的inode会被放在一个块里)
常用的部分会直接索引,不常用的部分会多级索引

Lecture 29(P) Reliablity

务必搭配jyywiki食用

没有任何可靠的存储设备：哪怕由于三体人进攻地球！
临时失效、部分失效、永久失效。

RAID 存储设备虚拟化 D.Patterson的杰作！
既要可靠性，也要性能！
另一种虚拟化：之前的虚拟化是将但设备虚拟化成多设备，而RAID是将多设备虚拟化成一个设备。（这种虚拟化在计算中心里面也是常见的）

• RAID-0:
  无备份，
  交错排列可以获得读写并行，无法容错，尤其交错时
• RAID-1：
  保持份镜像，，只能读并行，容错率高

如果假设不会有两块盘同时失效（Fail stop）？
求和检查：环和（或者叫异或、奇偶…）
但是每次修改校验和都会修改
把校验分散在多个盘上，可以提高性能

• RAID-5
  …🐟

发现Fail-stop：RAID板卡上的软件会检测🐟

🌶️Spicy:

如果硬盘不连接到一块板卡上呢？构造一个巨大的分布式RAID，可以容纳整个互联网世界：Google File System
map reduce🐟
数据中心存储：EBS：Elastic Block Storage
🐟

发现问题非常困难：Fail Slow 或者 一部分数据损坏，同时多层虚拟化增加了系统复杂度

崩溃一致性：Crash Consistency
需求：无论何时Crash(Kernel panic, 断电)，不能修改一半！
这其实是某种意义上的并发问题，Crash类似于一种中断
磁盘的按块写接口，是无法实现原子性的（甚至都不能保证顺序）
bread,bwrite
最基础的磁盘提供了:bflush等待所有缓冲的写操作落盘
且磁盘的校验机制保证了单次bwrite的原子性
但还是不行,因为写入一个文件是很多个bwrite的集合
糟了，那个L1可能也会有类似的问题
需要写 inode(文件的元数据和块索引),bitmap(标记空闲块),文件数据(可能还有多次bwrite),三部分
(inode和bitmap是集中存储的)
崩溃可能会导致

• 资源泄漏：目录系统是没更新，bitmap更新了
• 文件不一致：文件的前后部分版本不一致
• 最严重的问题：bitmap没更新，目录系统更新了，这一块可能会泄露，同时还可能会被别人修改

(部分)解决上面的不一致:FSCK：一个困难的问题
由于Crash的时候你不能确定之前进行了哪些操作进行了一半，所以只能修正成一个最可能的。
比如当你移动一个目录时，需要修改大量的指针.
但是FSCK的过程也可能Crash，就更chaos了

FSCK只是一个兜底的办法,我们希望有更好的处理:
在非原子的设备中实现原子性的”All or Nothing”操作
重新理解数据结构：

• 数据结构，既是有组织的数据（结果视角）。
• 也是一串有组织的操作的结果（过程视角）。

1. 我们想要修改数据结构
2. 将一个TXbegin+需要修改所需的所有操作全部写入到一个Append-only的日志中
3. 日志完整写入磁盘,flush,写一个TXend标记
4. 开始修改数据结构
5. 数据结构落盘了,就可以把日志删除了

如果发现了Crash，如果有配对的TXbegin和TXend，那么就可以Replay日志，如果没有，那么就可以把日志删除

考一考
如果获取锁的时候crash了呢

Lecture 30 Summary

• Everything is a state machine
• Emulate state machines with executable models
• Enumeration demystifies operating systems

后记

《 Email to Green Advisor 》
这篇其实从学期一初就开始写了，希望的是等到OS这门课出分之后发给绿导师，希望当时我是以一个幸存者的心态，完成了这门课全部的任务，取得了一个不错的分数（不得不这样）比较轻松的发送这篇邮件。

这门课给我的体验的是很好的，我想对比的是同是这学期的算法设计与分析课。黄宇老师的算法课有着非常的清晰的讲解，我也不得不承认确实是一门好课，我用了一个月左右才想清楚了为什么这门课会让我感到痛苦。就是：对于对OI有一定接触的我来说，这些经典“算法”早已没有了初见的新鲜感，更重要的是每节课都在向我传达一个概念“你又不能做什么，你又没法会什么”，因为这些都需要“灵感”，（课上的方法论甚至都不足以解决那占比80%的考试题😭（当然任何形式的考试都承担着检验以外的筛选作用））。相比之下我觉得OS给我的感觉是每一节课后，“我又能做成什么，我又能解决更多问题（乃至所有问题）”。不同于上算法课之前上刑场一般的心理负担，每节操作系统课虽然带着成吨的没读完的OSTEP，没理解完的讲义，没整理完的笔记，没学完的工具，没写完的实验，但都是无比期待的。我觉得这可能是一种“极客主义”。

我想提出一点异见的就是您说只发表“not trivial”的工作。我接触到了一个概念就是do not judge novelty，我觉得，对于一般的研究者而言，他们可能终其一生都无法做出creative的工作，但他们的工作也是有价值的，也需要一个获得认同的平台。（在知乎看到过一个人说一个化学教授说，我们做实验，失败了，也是有价值的，至少别人看到了，知道这样做不行，不用再好费时间了。类似地，CS里面有一些仅仅是方法的融合怪，至少也可以证明这些方法的交叉不会产生奇妙的“化学反应”。）可能只有聪明人做科研才是有价值的，但是在大量聪明人去经商/捞钱的今天，让一些不聪明的人去回收一些low fruit也是应该的。（虽然说 do not judge novelty今天已经变味，更多成为了一种灌水的辩护，这个界限也很难分辨…）

还有就是对这门课程的建议，我觉得这门课的地位已经不言而喻，作为第一个入选CSDIY的国内课程，我觉得这是无上的光荣（比什么CCF发的什么奖项含金量高太多，毕竟这是华语区热爱CS的人投出来的票，好过某随意增减名额把OIer的未来当儿戏的组织太多）。相比于上海交大的一些透露着买办阶级的所谓的好课（质量固然是有的，毕竟是从海外ctrl+C/V来的），这门课更像是一座灯塔。但我发现了一个问题就是，由于您各种意义上一个“聪明人”，所以您上课的节奏虽然适中，但有一些结构上的问题加以忽略。对于拔尖班之类的大佬，他们的可以很快地处理和解决问题点，并且在节奏稍缓的时候迅速的将结构组织起来。但对于我这样反应比较慢的人来说，我全程都在高强度的处理一些思考点（有些甚至还当堂处理不完）最后的感受就是只体会到了一些零散的点。之后虽然有回放可以反复观看，但是由于短时记忆遗忘的问题，就会有一种夹生感，最后需要数倍的时间去组织起来。因此我觉得如果在讲义和授课中更加强调一点结构，这门课就会向普通的同学，乃至开源之后的更广泛的受众群体更加友好。

系统知识，明白自己干什么，提高理想注意，水完这个
建议增加分级制度和每年新内容的Update Log

课程主页爬到了第三,第二是AI，第一是默认页

不要做减法，做加法，大家确实要hard以下
把状态机的视角灌输到下一届一个班的同学了

最后一节课显著增加

评价体系不变，课程改革根本无法实现

环境虽然差，但目前很优越，不够内卷有空间了

之前说的西工大不是大学
残酷并不意味着残酷

人类的本质preaching machine

如何发现问题
回答应不应该

杜绝沙文主义

不要再没有意义上的事情上沾沾自喜
做一些只有你自己相信的事情

回归了humble