KAIST-CS431: Lock Implementations

Naive Spin Lock#

Naive Spin Lock的缺陷#

• 无法保证公平性，可能有的倒霉蛋空转了一辈子也无法cas成功，无法做到按竞争线程先来后到的次序占有锁。
• 扩展性差，大量对同一内存区域的自旋引发性能问题。

对Naive Spin Lock的优化#

关键思路：

• 通过release/acquire同步机制保证互斥量的排他性
  • 从一个临界区的结束（release）到另一个临界区的开始（acquire）
  • 在ticket lock里面是curr成员，CLH/MCS lock是每个waiter的一个新内存区域
• 通过排队和等待不同的区域释放保证公平性
  • 通过公平的指令来排队（如swap, fetch-and-add）
  • Ticket lock：通过next来排队，curr来等待锁
  • CLH/MCS lock：通过tail来排队，等待每个锁调用者申请的不同区域中值的变化来获取锁

Ticket Lock#

ticket lock在锁的结构体里面新增了一个原子变量next，每次需要竞争锁时，需要先从next中拿到一个ticket，然后再去监听curr，只有curr被更新成当前的ticket值后，才能去占领锁。

优点#

• 利用公平指令排队解决了公平性问题

缺点#

• API相对较复杂（调用者感知ticket）（为什么不直接用curr+1？）
• 没有解决spinlock中所有线程监听同一个原子变量的问题

CLH Lock#

为了减少缓存一致性带来的开销，CLH lock被发明了。CLH是三个人首字母的缩写：Craig, Landin, and Hagersten。

CLH lock给所有等待线程分配了一个Node，每个Node初始为true，在锁内维护一个链表，所有竞争锁的线程都会获取到前一个线程的Node，并将tail指针指向自己的Node。

不同于spin lock和Ticket lock，CLH lock的临界区是前一个Node中的原子变量。在锁释放时，当前线程会将自己的Node值置为false，而排队的下一个线程监听到这个变化，则可以安全地占有锁了。

优点#

• 线程监听的不同临界区，减少缓存一致性的开销
• 链表排队，也能保证公平性

缺点#

• O(n)的空间复杂度开销，n是临界区数目
• 每个线程都是在前驱节点的Node上自旋，如果跨NUMA会有性能问题

MCS Lock#

MCS lock也是以三个人名命名的：John M. Mellor-Crummey and Michael L. Scott。MCS lock和LCH lock最大的不同是：CLH lock是在前驱节点上自旋，MCS则是在自己节点上自旋。

在CLH的Node结构里面，MCS又添加了一个next字段，新的线程竞争锁时，会将自己的Node添加到前驱节点的next字段中。

线程持续在自己Node的lock字段上自旋，当为false时，表示可以安全地获取锁。

在释放锁时，将next Node中的lock置为false，从而通知后驱节点可以获取锁了。

MCS lock将CLH lock多次对远端内存的监听 + 一次对本地内存的更新，简化成了多次对本地内存的监听 + 一次对远端内存的更新。

优点#

• 能够保证公平性
• 解决CLH锁跨NUMA的性能问题

缺点#

• unlock可能会存在一次额外的cas开销

MCS Parking Lock#

MCS Parking Lock即即将MCS Lock中的自旋改成了parking。牺牲了低竞争环境下的性能，改善大量锁自旋引发的开销。