读写自旋锁的实现细节上节阐述的自动机模型是个抽象的机器，用于帮助我们理解读写自旋锁的工作原理，但是忽略了很多实现的关键细节：
1. 操作的执行者。如果按照上节的描述，为读写自旋锁创建专门的操作执行线程，那么锁的实际性能将会比较低下，因此我们要求申请线程自己执行提交的操作。
2. 操作类别的区分。可以提供多个调用接口来区分不同种类的操作，避免使用额外变量存放类别信息。
3. 确定操作的提交顺序，即线程的到来的先后关系。写者优先和公平读写自旋锁需要这个信息。可以有 3 种方法：
- 假定系统有一个非常精确的实时时钟，线程到来的时刻用于确定顺序。但是寻找直接后继者比较困难，因为事先无法预知线程到来的精确时间。
- 参考银行的做法，即每个到来的线程领取一张号码牌，号码的大小决定先后关系。
- 将线程组织成一个先进先出（FIFO）的队列，具体实现可以使用单向链表，双向链表等。
4. 在状态 q，确定操作（线程）是否被允许执行。这有 2 个条件：首先 q 必须允许该操作；其次对于写者优先和公平读写自旋锁，不存在先提交但尚未执行的写者（读者 / 写者）申请操作。可以有 3 种方法：
- 不停地主动查询这 2 个条件。
- 被动等待前一个执行线程通知。
- 主动 / 被动相结合。
5. 选择执行的线程。在状态 q，如果存在多个被允许执行的线程，那么它们必须达成一致（Consensus），保证只有一个线程执行成功，否则会破坏锁状态的一致性。有 2 种简单方法：
- 互斥执行。原子指令（总线级别的互斥），或使用锁（高级互斥原语）。
- 投机执行。线程不管三七二十一先执行再说，然后检查是否成功。如果不成功，可能需要执行回滚操作。
6. 因为多个读者可以同时持有锁，那么读者释放锁时，有可能需要知道自己是不是最后一个持有者（例如通知后面的写者）。一个简单的方法是用共享计数器保存当前持有锁的读者数目。如果我们对具体数目并不关心，只是想知道计数器是大于 0 还是等于 0，那么用一种称为“非零指示器”（Non-Zero Indicator）的数据结构效果更好。还可以使用双向链表等特殊数据结构。
本系列文章所论述的算法只关注共享内存的系统。相关代码全部用 C 语言编写，主要目的是为了印证读写自旋锁的原理，故而性能并非最优，有兴趣的读者朋友可以尝试用汇编语言改写。代码中出现的 atomic_t 数据结构，cpu_relax()、atomic_*() 等函数引自 Linux 内核 [1]。
读写自旋锁的接口我们将操作种类集合的 6 种操作定义为各种读写自旋锁提供给用户调用的通用接口函数：
- init_lock()，初始化锁。
- destroy_lock()，析构锁。
- reader_lock()，读者申请获取锁。
- reader_unlock()，读者释放锁。
- writer_lock()，写者申请获取锁。
- writer_unlock()，写者释放锁。
一般而言，destroy_lock() 可以简单地将动态分配的锁结构释放掉，或调用 init_lock() 将锁的状态置为初始值；且在系统的存活期内，读写自旋锁不会被析构。所以在后续文章的代码中，我们没有附上 destroy_lock() 的实现。
结束语本系列文章详细论述读写自旋锁的原理和实现，本文是其中的第一部分，以自动机的观点阐述读写自旋锁的原理。 |
