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} \]

1
2
3
4
5
6
7
8
9
10
11
#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

testtt
https://chohee15.github.io/2024/07/a46a136eb054.html
作者
ChoHee
发布于
2024年7月13日
许可协议