Spinlock and Doubly Linked List

2019.10.14

Spinlock 自旋锁，在获取锁时使用轮询的方式检查锁是否可用。其优点是避免了线程切换，缺点是轮询持续占用 CPU，故一般只在临界区非常短的时候使用。更详细的介绍见维基百科。

一般使用 compare-and-swap (CAS) 来实现自旋锁。CAS 可以理解为以下函数的原子实现：

bool compare_and_swap(int *p, int origin, int target) {
  int old = *p;
  if (old == origin) {
    *p = target;
    return true;
  } else {
    return false;
  }
}

C++ 中一般使用 std::atomic_flag 来完成 bool 型的 CAS 操作。下面实现一个自旋锁：

#include <atomic>

class SpinMutex {
 public:
  void lock() {
    while (flag_.test_and_set()) {}
  }

  void unlock() {
    flag_.clear(std::memory_order_release);
  }

 private:
  std::atomic_flag flag_ = ATOMIC_FLAG_INIT;
};

注意 ATOMIC_FLAG_INIT，按照文档要求只能使用 operator= 来完成 std::atomic_flag 的初始化。由于提供了 lock 和 unlock，可以配合 std::lock_guard 使用。下面使用自旋锁实现双向链表：

#include <atomic>
#include <cassert>
#include <mutex>
#include <vector>

class SpinMutex { ... };

template <class T>
class DoublyLinkedList {
 public:
  struct Node {
    T value;
    Node *prev;
    Node *next;
  };

 public:
  DoublyLinkedList() : head_({.prev = &head_, .next = &head_}) {}
  void PushFront(Node *node) {
    std::lock_guard<SpinMutex> lock(mutex_);
    node->next = head_.next;
    node->prev = &head_;
    head_.next->prev = node;
    head_.next = node;
  }

  void PushBack(Node *node) {
    std::lock_guard<SpinMutex> lock(mutex_);
    node->next = &head_;
    node->prev = head_.prev;
    head_.prev->next = node;
    head_.prev = node;
  }

  Node *PopFront() {
    std::lock_guard<SpinMutex> lock(mutex_);
    Node *node = head_.next;
    node->next->prev = node->prev;
    node->prev->next = node->next;
    return node == &head_ ? nullptr : node;
  }

  Node *PopBack() {
    std::lock_guard<SpinMutex> lock(mutex_);
    Node *node = head_.prev;
    node->next->prev = node->prev;
    node->prev->next = node->next;
    return node == &head_ ? nullptr : node;
  }

 private:
  Node head_;
  SpinMutex mutex_;
};

int main() {
  std::vector<DoublyLinkedList<int>::Node> nodes(4);
  for (int i = 0; i < nodes.size(); ++i) {
    nodes[i].value = i;
  }

  DoublyLinkedList<int> list;
  list.PushFront(&nodes[0]);            // head -> 0 -> head
  list.PushFront(&nodes[1]);            // head -> 1 -> 0 -> head
  list.PushBack(&nodes[2]);             // head -> 1 -> 0 -> 2 -> head
  list.PushBack(&nodes[3]);             // head -> 1 -> 0 -> 2 -> 3 -> head
  assert(list.PopFront()->value == 1);  // head -> 0 -> 2 -> 3 -> head
  assert(list.PopFront()->value == 0);  // head -> 2 -> 3 -> head
  assert(list.PopBack()->value == 3);   // head -> 2 -> head
  assert(list.PopFront()->value == 2);  // head -> head
  assert(list.PopFront() == nullptr);   // head -> head, null
}

双向链表的各项操作的临界区均较短，适合使用自旋锁。在使用上和普通的互斥锁一致。在实际应用场景中，有时会混合使用自旋锁和互斥锁，在自旋等待一定时间仍没有拿到锁时，将线程挂起，等待的时间可以自适应学习。

Spinlock and Doubly Linked List

References