实验反馈¶
Lab3 主要是 Linux 上的网络编程，我们希望通过这个实验帮助大家建立对线程和锁的直观了解。
代码编写与调试¶
在 lab3 中我们的代码会涉及到线程间的并发执行，这会带来很多竞态条件相关的 bug（例如两个线程对同一个内存地址的读写），你可能会需要一些趁手的调试工具：
- gdb：gdb 虽然初看起来比较劝退，但对于一些复杂应用程序的 debug 几乎是必不可少的。gdb 也有一些漂亮的调试器前端可以搭配使用。具体使用请参照网上的各类教程文档。
- tsan: 在编译 C/C++ 代码时，可以加上
-fsanitize=thread参数。你可能已经比较熟悉-fsanitize=address参数了：后者可以在程序出现内存错误时提供详细的错误信息，与之类似，前者可以帮你发现一些线程相关的错误，如数据竞争等。除了 asan 和 tsan 之外，还有 msan 和 ubsan 可以帮你进行更多运行时检查。具体使用同理请参照文档。
计算机永远不会出错，若计算机出现不符合自己预期的行为，那原因一定是有迹可循的。锻炼自己的调试能力可以很好的帮助解决各种问题。
本实验的常见问题¶
如果你没有选做缓存部分，你可能不太会遇到复杂的竞态条件。但是一个常见的问题是：
while (1) {
int clnt_sock = accept(serv_sock, (struct sockaddr*)&clnt_addr, &clnt_addr_size);
pthread_t thread;
pthread_create(&thread, NULL, handle_clnt, &clnt_sock);
pthread_detach(thread);//分离线程
}
以上实现每个线程从 &clnt_sock 中获取参数。但线程创建后并不会立即执行，因此可能出现：
clnt_sock = 1 -> 线程1创建 -> clnt_sock = 2 -> 线程2创建 -> 线程1调度 -> 线程2调度
此时线程 1 读取 &clnt_sock 得到的值是 2，与预期不符。
这个问题在开启 -fsanitize=thread 编译选项后是可以被运行时检测到的。
锁¶
不管是操作系统内核还是应用程序，对共享数据的访问都是常见的。对于多核 CPU，一般来说内核是可以同时在多个 CPU 核心上同时运行的（这里需要补充一个对操作系统内核的感性认识，在完成了系统资源的初始化后，操作系统就成为了 interrupt/trap/exception handler，而当多个核心上运行的线程都在调用 syscall，或者同时陷入异常（如除零异常，缺页异常）时，显然应该允许多个核心都进入内核态）。
此时，对于内核中一些数据结构，例如空闲页链表或各种设备寄存器的内存映射地址的访问就出现了数据竞争。此时必须引入锁机制保证数据更新的正确性，以及操作的原子性。锁是针对某个操作而言的，而不是对某个内存地址而言的。例如，多线程同时进行链表的插入，需要对链表加锁，而不是对某个结点上面的 next 指针加锁。
对于操作系统内核中此类竞态条件，最经常被使用的是自旋锁（spinlock）。
自旋锁¶
自旋锁常常通过指令集提供的对内存的原子指令实现。例如 RISC-V 指令集提供了 amoswap 原子交换指令，该指令会将 R1 寄存器的值写入对应内存地址并将地址原先的值保存到 R2 寄存器。通过 amoswap 原子指令，我们可以实现 test-and-set 原子操作。例如，我们可以用某个变量表示锁是否被持有：
struct spinlock {
int locked;
}
对于加锁操作，我们可以循环调用 amoswap 不断向内存中写入 1。如果发现地址原先的值是 1，那么说明锁原先就已经被持有，我们需要继续循环以获取锁；如果发现地址原先的值是 0，那么说明原先锁没有被持有，此时我们就获取到了锁，可以退出循环。
对于解锁操作，我们直接向内存中写入 0 即可。注意这里的写入也需要用原子指令。
为什么不直接 store 0?
store 指令本身并不提供原子性保证，例如 store 指令可能会先加载 cache line, 再向 cache line 中写入数据，注意这里不再只是简单的 RAM 模型。
实际自旋锁的实现还有一些值得注意的细节，例如获取自旋锁前应该先关闭中断，避免中断处理程序中再次申请同一个锁，在释放锁后再打开中断（同一时刻可能会持有多把自旋锁，因此往往这里会设计一个 push 和 pop 中断开关的机制）。以及实际内存还有内存序等更多细节需要考虑，可能会需要屏障指令来保证锁之间操作的原子性。
互斥锁¶
一个用户程序可能需要多个线程并行执行，此时数据的竞争也需要用锁来解决。
但用户程序往往不会直接使用自旋锁，一方面自旋锁需要确保在获取锁和释放锁之间线程不能被调度走，否则另一个线程会 busy-loop 很长时间；另一方面用户态程序可能会对某些复杂操作加锁，这时我们希望暂时获取不到锁的线程可以休眠，操作系统调度其他的线程执行。
为了满足上面的需求，互斥锁就诞生了。互斥锁是操作系统面向用户态程序提供的一种锁，当获取失败时，允许操作系统调度其他线程执行。
当然，切换线程的开销毕竟还是很大的，所以一个高性能的程序会尽量减少锁的使用。一个简单的策略是，对数据哈希分桶，每个桶对应一把锁以替换原来的大锁。
协程¶
（本部分内容仅供拓展了解，参考自 NJU OS 2022 M2 libco，协议 CC BY-NC 4.0 License）
我们注意到多个线程可以提高程序的并行性，但程序本身根据目的也分为计算密集型程序和 I/O 密集型程序两种。对于前者，合适的并行策略可以几乎线性的提高程序的运行效率。但是对于后者，瓶颈主要在操作系统读取文件并拷贝回用户态地址空间，本身程序执行所占的时间并不多，因此事实上可能并不需要多线程并行（同一时间运行多个任务），而只需要能应对并发（同时到达大量任务，但并不需要同时处理）的情景即可。而且，线程切换本身也有大量的开销，会带来页表的切换和缓存的失效。
我们有没有可能在不借助操作系统 API (也不解释执行代码) 的前提下，用一个进程 (状态机) 去模拟多个共享内存的执行流 (状态机)？
答案是可以的。线程作为串行执行调度代码的基本单位，体现这一点的就是每个线程都具有独立的栈帧链和寄存器环境（除此之外，堆，程序代码，全局变量等都是共享的）。因此，如果我们采取某种机制保存并恢复栈帧链和寄存器，就可以在多个执行环境之间切换了。这样，我们就在用户态实现了协作多任务的调度，一般也称为协程。之所以说是协作多任务，是因为这种多任务需要每个任务主动让出自己的执行权，执行调度代码切换到别的任务。
对于保存寄存器环境，C 语言标准库中提供了很方便的 setjmp 和 longjmp 函数。当然实际上在切换执行环境时，我们并不需要保存所有的寄存器，只需要保存被调用者保存寄存器即可（想一想为什么）。
无论你觉得你理解得多么“清楚”，亲手调试过代码后的感觉仍是很不一样的。
我们非常欢迎感兴趣的同学尝试 NJU OS 2022 M2 libco，你可以联系助教获取一份参考实现（出于外校课程实验要求，答案并不直接开源）。
本学期有关操作系统具体实现的实验到此就结束了，由于课程安排的原因，我们并没有选择某个具体的内核实现讲解。如果你对操作系统的具体实现有兴趣（包括页表，中断，线程调度等），我们推荐以下资源以供进一步学习：