1. 同步原语

三大同步原语：mutex，semaphore，condition variable。

1.1. mutex

mutex有以下细节需要注意：

• 排他性：一次只允许一个线程持有，被占有后，其他尝试获取的线程会进入blocked状态；

• 递归：Linux中的mutex分为递归（重入）的和非递归（不可重入）的，即是否允许同一个线程多次获取和释放。

  多次获取递归mutex，会嵌套持有，增加锁的计数器，必须使用等量的释放动作才可完全释放锁。

  多次获取非递归的mutex，会导致死锁。

• 睡眠与唤醒：无法获取到mutex时，线程会被放到阻塞队列中，直到mutex被其他线程释放，然后会进入就绪队列，等待重新调度。
• 优先级继承：高优先级的线程等待低优先级持有的mutex，会形成优先级翻转，可能导致线程饿死，Linux中的mutex实现了优先级继承，该情况下会暂时提高低优先级线程的优先级。
• 公平性：Linux中的mutex倾向于公平分配，按照请求顺序让线程获取锁，还有其他类型的策略。
• 内存语义：大部分mutex都提供了内存屏障，确保锁保护下的数据的操作不会因为编译器优化、乱序执行导致不可预期的结果。

1.2. semaphore

semaphore的细节：

• 限制并发：可以限制同时访问某资源的线程数量，而mutex同时仅允许一个线程访问资源。

  场景1：（单方向限制）电影院有100张票，设置初始值为100的semaphore，每次被购买就是用release，直到值为0时不可购买。

  场景2：（双向限制上限和下限）使用信号量和有限长队列解决生产者消费者问题，用两个semaphore，一个表示队列剩余元素个数，一个表示队列剩余容量，可以双向控制队列元素数量处于0~max之间。

• 用途：限制同时访问某资源的线程数（见上）。除此之外，还可用于进程间通信，配合内存映射文件使用，使不同进程使用同一个semaphore，在 POSIX API中，semaphore创建时需要提供一个路径名，这样多个不同的进程使用同一个路径，即可使用同一个semaphore。

1.2.1. Q\&As

• 如果把semaphore的最大值设置为1，它和mutex有什么区别吗？

condition variable

锁

同步机制有哪些？（以使用难度降序，临界区大小升序）

• 原子指令
• 无锁算法
• RCU
• 读写锁
• mutex/spinlock

RCU

1.3.1. 一句话介绍RCU是什么？

• read copy update，读者无锁操作，写者创建一个数据的拷贝，然后进行修改，修改完将新数据设置为有效版本，将旧数据标记为过期，旧数据没有读者使用时，删除旧数据。

1.3.2. 使用场景是什么？

• 读多写少的场景，在只有一个写者的时候实现较简单，常用于的数据结构：单链表。

1.3.3. 其他类似的锁有什么问题？

• 读写锁：读与写仍然是互斥的，写者需要等待读者读结束才能操作，读者仍然需要持锁等待写者写结束；
• seqlock：写者不需要等待，但读者需要等待写者写完才能读（为了保证读者读到的总是最新的值，哪怕数据正在被修改）。

1.3.4. RCU的优点有哪些？

• 读者几乎没有额外操作；
• 写者几乎不会被阻塞；
• 在多核场景下性能非常好；

1.3.5. RCU的实现（以链表为例）

1.3.5.1. 节点插入

• 写者创建新节点，将新节点指向后续节点；
• 原子替换前一个节点指向的指针；
• 这个过程没有任何阻塞（有多个写者时需要互斥）；

1.3.5.2. 节点删除

• 写者原子更新上一个节点指向的地址为下一个节点；
• 由于此时可能有读者在读被删除的节点，因此不立即释放被删除节点；
• 所有读者读完的时候，节点可以被删除；此时需要所有读者声明一个临界区，在未开启内核抢占的场景中实际无操作；

  在不可抢占内核里，使用一个特殊的RCU线程（syncer），当他被调度到时，即说明所有的读者读完了。

  grace period：被删除的元素仍然可读的时期；

1.3.5.3. 非原子节点更新

• 写者创建一个待更新节点的拷贝，对节点拷贝做非原子修改；
• 原子替换前一个节点指向的指针；
• 对于多个写者更新的场景，需要使用写锁防止修改被覆盖；

1.3.5.4. 对外接口

• RCU专用接口：rcu_read_lock() rcu_read_unlock() rcu_dereference() synchronize_rcu()；

1.3.6. RCU中的mem barrier

1.3.6.1. RCU通常会在哪里加mem barrier？

• 写者操作结束时；
• 除此之外，编译器可能会加barrier；

1.3.7. RCU的问题

• 不支持batch updates（transaction）；

  新的概念：RLU (read log update)

• 支持内核抢占的系统中，开销稍高一些；
• 实时kernel中需要特殊支持；
• 通常都不支持多个写者；
• 理解、使用、维护的难度较高；

1.3.8. RCU有哪些不同的实现？

• Linux内核中，借助内核调度器和CPU timer等来实现；
• 用户态实现，liburcu，性能可能略低。

1.3.9. Linux中的RCU

to be continued

---