xv6 学习笔记: Lab Lock
学习
- xv6 book 第 3 章 3.5 节和第 7 章
- kernel/spinlock.c, kernel/sleeplock.c
- __atomic Builtins (Using the GNU Compiler Collection (GCC))
要点
自旋锁通过 atomic_exchange_n 原子指令不断比较锁是否被持有。在等待锁期间，CPU 被内核或进程占有（除了中断的时间）。
睡眠锁可以使得内核或进程尝试获取锁的时候，能让出 CPU 给其他进程。
自旋锁最适合于短的关键部分，因为等待它们会浪费CPU时间；睡眠锁对长的操作很有效，它们在等待期间会让出 CPU。
练习
Memory allocator
给每个 CPU 一把锁用来访问空闲物理页的 freelist。每次 kalloc 或 kfree 依然要请求锁，不过争用的情况少了很多。当前 CPU 的页面数量不够时，需要请求其他 CPU 的锁，“偷”一页出来。
使用 cpuid() 时必须先用 push_off() 关闭中断，使用完再用 pop_off() 打开中断。因为中断可能会导致当前函数切换到其他 cpu 运行，导致 id 和实际 CPU 不一致。
Read-write lock
读写锁最多只有一个写者，可并发多个读者。
读写锁的写锁优先于读锁。具体来说，当有写请求时，后来的读请求会被阻塞，直到写释放。
正确地加锁只能保护数据，不代表临界区内的指令不会中断。读写锁的要求之一就是任意一个读请求被暂停处理后，其他读请求也不会被阻塞（wait-free）。所以读请求不能独占某个锁或资源。
| 当前有读 | 当前有写 | 请求类型 | 处理方式 |
|---|---|---|---|
| ❌ | ❌ | R | 直接请求 |
| ❌ | ❌ | W | 直接请求 |
| ❌ | ✅ | R | 阻塞，直到当前写结束 |
| ❌ | ✅ | W | 阻塞，直到当前写结束 |
| ✅ | ❌ | R | 直接请求 |
| ✅ | ❌ | W | 阻塞新读，当前读结束后，请求写 |
| ✅ | ✅ | R | 违反定义 |
| ✅ | ✅ | W | 违反定义 |
多参考 GCC 的原子指令。
我的代码
per-CPU freelist 用了比较直观和简单的写法。当前 CPU 页面不足时，只从其他 CPU 偷一页。
读写锁思考了较长时间。首先，允许多个读和最多只有一个写，可以考虑使用两个变量 rlock 和 wlock 存储相关的值，rlock 要存储读者数量，wlock 就像互斥锁的 locked 那样只有 0 或 1 两个值保证最多只有一个写者。每次请求读的时候 rlock 原子加一，释放读的时候 rlock 原子减一，保证了 wait-free。请求写像互斥锁那样用 __atomic_exchange_n 竞争，释放写时设置 wlock 为 0，保证最多只有一个写者。但是这样远远不够，没有保证读写互斥和写者优先。一种做法是，请求写的时候，竞争到 wlock 的那个写者，把 rlock 的最高位（简称 P 位）置为一，表示当前存在写请求。任何读请求都应该观察 P 位是否被设置，如果没有，则请求成功，否则应该把 rlock 原子减一，抵消上一次加法并循环（否则，rlock 的低位就不能表示读者数量，并且循环会使得 rlock 越来越大，最后溢出）。如果请求写时已经存在多个读者，由于 P 位已经被设置，所以不会有新的读者，这时候需要等待所有读者都释放，即可成功申请写。释放写时也要把 P 位置为零。