testtt

TEST

可以证明，当大小为 \(2^k\) 的某块，其地址也与 \(2^k\) 对齐时，由它分割出来的两个 \(2^{k-1}\) 大小的伙伴块，地址都对齐到 \(2^{k-1}\)。

设某大小为 \(2^k(k>0)\) 的块，其地址为 \(addr_{fa}\) ，有 \(addr_{fa} \bmod 2^k = 0\)。由它分割出来的两个 \(2^{k-1}\) 大小的伙伴块，设地址分别为 \(addr_{ch1}\) 和 \(addr_{ch2}\)，其中 \(addr_{ch1} = addr_{fa}\)，\(addr_{ch2} = addr_{fa} + 2^{k-1}\)。 则有 \[ \begin{align} addr_{ch1} &\bmod 2^{k-1} = addr_{fa} \bmod 2^{k-1} \\ addr_{ch2} &\bmod 2^{k-1} = (addr_{fa} + 2^{k-1}) \bmod 2^{k-1} = addr_{fa} \bmod 2^{k-1}\\ \\ &\because addr_{fa} \bmod 2^k = 0 \\ &\therefore addr_{fa} \bmod 2^{k-1} = 0 \\ &\therefore addr_{ch1} \bmod 2^{k-1} = addr_{ch2} \bmod 2^{k-1} = 0\\ \end{align} \]

#include <stdio.h>

#defind M 100;

int main(){
    printf("%d\n", M); //what aha wha
    return ;
}

//comment

Pasted image 20240228151426|50

Pasted image 20240228151426|100

box

8. 并发bug和应对

防御性编程：正确的assert也是面试加分项

面对死锁：死锁的特征相对明显，即程序莫名其妙不动了。要破坏四个必要条件没书上写的那么简单，一个简单的办法是使用顺序上锁，来破坏循环等待条件。

jyy提到，一个真正好的教科书应当告诉读者死锁的四个必要条件，然后告诉读者在现实中破坏这些条件没那么简单，然后给出一个工程上面对死锁的“最佳实践”，如顺序上锁。而不是说“我们在设计系统、规划资源时，要考虑到这四个条件，从而破坏它们以避免死锁”这种正确之废话。

整个os中通常只有十几？几十？个锁，通常能将其管理好。

数据竞争：对于同一个地址，存在一读一写的线程。因此对于共享数据，应当全部用锁保护起来，而最最简单的一种实现是——全局使用一把锁。在L1中，应当使用这种最简单实现先让它跑起来。

然而，即使用了锁，程序员依然可能因为手滑，在代码中上错了锁或者忘了上锁，导致bug。 忘记上锁（原子性违反av） 忘记同步（顺序违反ov） 有统计表明有97%的非死锁并发bug是av或ov

“TOCTTOU”bug

那么，应对并发bug只能通过程序员不断仔细仔细再仔细的测试和debug吗？只要使用了order locking就万事大吉了吗？显然这不能，人总是会产生遗漏，甚至就算开发手册中明明白白写了使用顺序上锁，也有人会漏看。这意味着我们总是需要一些工具来帮助人们面对并发bug。

例如Lockdep可以实现运行时的死锁检查。其基本思想是在上锁时记录是哪行代码执行了上锁（一种粗糙的实现是，在锁的结构体中加入一个字符串，然后在上锁的函数中，利用__LINE__等将调用位置信息添加到锁的字符串中）。而后便能打印锁的历史，通过这些历史可以分析出T1，T2线程关于锁的调用关系，当调用关系中出现环，可以判定程序出现死锁。Linux和鸿蒙使用了这种方法。

jyy：不要太看不起华子的程序员

同时，调用历史还可以检查顺序调用的情况。例如，若约定X锁需要在Y锁前获得，那么历史中X就必须在Y前出现，否则说明没有满足顺序调用规则。

同样的，ThreadSanitizer可以检查运行时的数据竞争。为所有事件建立happens-before关系，然后求传递闭包（问题求解课，不懂儿）。

动态分析工具：Sanitizer们

Linux做出来确实很不容易，但是它的质量其实并不至于被神话。Sanitizer工具找出过Linux中的许多bug，而驱动更是bug的重灾区。

问：rust有哪些sanitizer？

这些工具确实很强大，但是要你自己做一个时，人们通常就润了。毕竟如果能通过15分钟调一调死锁的话，没人会想先去调几小时的sanitizer，人都是有“惰性”的。这些炫酷工具也是人们遇到人工无法处理的海量错误后，才被开发出来的；Linux在1.x时代也没人想折腾这些东西，而当Linux要支持多处理器，将锁渐渐拆开时，才认识到这些工具的意义。

但是我们仍然有一些基本的，可以手写的方法来进行一些简单的检查。例如使用金丝雀（canary）来进行缓冲区溢出检查。其基本原理是，在分配栈空间时，在前后预留一些空间来存放特定的值，然后定时检查这些值有没有被破坏。msvc在debug模式会将未初始化栈、堆和free后的内存等空间赋予特殊值，这些值在gb2313会被解码成烫烫烫、屯屯屯等字符。

还有可以用于实验的低配版的Lockdep：死锁的一个特征是线程不断尝试上锁。那么我们可以统计上锁次数，当它超过某个较大的值后，我们可以认为死锁了，可以打印信息panic之类的，再配合gdb和backtrace可以迅速调试。至少这在课程实验这种环境中，不失为一种办法。

不必自己完整实现一个sanitizer，而可以将这些思想融入进自己的防御性编程中，这可能带来很大的受益。

使用低配版sanitizer帮助完成L1的多线程alloc：在malloc和free时将内存设置为某个特殊值（刷成一种颜色），然后每次分配和回收时检查相应区域的颜色，来排查double-alloc/free。csapp的malloc lab似乎使用了类似的操作来进行测试。

总结： 常见的并发bug：死锁、数据竞争、原子性/顺序违反 处理方法：不要盲目相信自己，检查再检查；使用防御性编程和动态分析工具

9. 操作系统的状态机模型

在资料如此丰富的当下，写操作系统没有想象中那么的nb，它只是一个c程序而已。小学生也能写os，业余爱好者也可以。然而作为专业人士，你和他们的区别在于，当面对一些难以理解的bug，你该如何定位它？用什么工具，什么方法？

鸡和蛋

之前已经讲过“最小的HelloWorld”，即直接在汇编准备好write的参数然后syscall，这个程序不依赖任何库，完全“自包含”。

Pasted image 20240228151426

在操作系统环境下，加载器会负责把它的初始状态设置好，然后开始运行。那在裸机环境下，程序是被谁运行起来的？这与软/硬件的约定有关。

硬件也是个状态机，当你按下电源，cpu收到reset信号后，它会保证自己会处于某个特定的状态，例如，它保证自己的pc处于某个特定位置。而cpu就是个无情的取指令执行指令的机器，因此联系软/硬件的桥梁就是：硬件厂商保证开机后cpu的pc会先到某个位置，而只要把软件的第一条直接放在那个位置，cpu就会自己去执行了。

这个pc位置通常指向一段memory-mapped ROM，ROM存储了厂商提供的firmware（固件），比如BIOS和UEFI。

Pasted image 20240228152320

Firmware作为运行的第一个软件，它的职责是扫描硬件，找到一个有操作系统的硬件，然后把操作系统加载。Legacy BIOS和操作系统的约定是：BIOS一块块扫描每个磁盘，查看每个磁盘第一个512B的最后2个Byte是否为55aa，来判断这个磁盘是否为启动磁盘；若是的话把启动磁盘的第一个512B作为主引导扇区（MBR），Firmware会把这块内容搬到特定的内存位置，如7c00。这块512B的内容（boot loader）可以引导更多内容进入内存，逐渐完成操作系统的加载。

Pasted image 20240228162156

这一过程你甚至可以亲眼看到：利用watchpoint机制。 在0x7c00处添加watchpoint，就可以逮到是什么指令把磁盘的内容搬到内存中。

Pasted image 20240228155440

Pasted image 20240228155819