在读多写少(Read Mostly)的场景里，我们可能会使用的同步设施包括：

• Mutex / Spin Lock
• Reader Writer Lock
• Sequence Lock
• Read Copy Update

前面两种一般人都很清楚了，如雷贯耳、妇孺皆知。如果您对Spin Lock的实现细节有兴趣，建议您阅读我的这几篇博客：

Peterson Lock

Ticket Lock

MCS Queue Lock

从今天起，我们介绍后面两种同步设施。今天我们先介绍Sequence Lock。

基本原理

我们知道，传统的Reader Writer Lock是reader preference的，可能会产生writer starvation。和Reader Writer Lock不同，sequence lock是writer preference的，writer随时都可以更新临界资源。

sequence lock的精髓在于一个sequence count。当writer在更新时，count为奇数；不存在writer更新时，该count为偶数。

count初始化为一个偶数，比如说0。当writer操作临界资源前，先将count++，这时候count变成奇数；然后writer操作临界资源，完毕后，再count++，这时候count将又恢复为偶数。

对于reader，每次进入临界区前读取count值，如果为偶数，说明没有writer存在，那么它可以进入临界区；如果为奇数，那么它需要等待，不断重试，读取count直到count为偶数。进入临界区读取临界资源后，你知道，从reader进入临界区到试图离开临界区这段时间里，可能writer进来了，因此reader需要重新读取count，看和它进入临界区时的count是否相等，不等的话说明此次读取失败，需要重试。

基本实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

#include<mutex> //c++11的mutex
using namespace std;

struct SequenceLock
{
  volatile uint64_t sequence_count;
  mutex lock; //这把锁是用于writer们互斥的。保证只有一个writer能更新。和reader无关。
};

static void seqlock_init(SequenceLock &sl)
{
  sl.sequence_count = 0;//初始化为偶数
}

static uint64_t read_seqbegin(SequenceLock &sl)
{
  uint64_t sc = 0;
  while(true) {
    sc = sl.sequence_count;
    if (!(sc & 1)) {
      break; //sc是偶数，说明没有writer，返回
    }
  }
  return sc;
}

static bool reader_need_retry(SequenceLock &sl, uint64_t oldseq)
{
  return sl.sequence_count != oldseq;
}

static void write_seqlock(SequenceLock &sl)
{
  sl.lock.lock();
  ++sl.sequence_count;//让count变为奇数，和读者声明自己的存在
}

static void write_sequnlock(SequenceLock &sl)
{
  ++sl.sequence_count;//让count恢复为偶数
  sl.lock.unlock();
}

深度思考

1，sequence lock和reader writer lock相比，有什么区别？

最主要的区别，如上所述，就是writer随时随地可以进行更新，不会出现writer starvation的情况。正因为如此，如果update heavily，那么可能造成reader starvation。然而，正如我们一早所说的，sequence lock用于read mostly的situation。因此，reader starvation几乎不会发生。

reader端并不需要加锁，只在极少情况下需要重试而已。因此，从某种角度来说，sequence lock是一种乐观锁。

2，sequence_count声明为uint32_t是否可以？

看你的writer更新的频率。假如你的writer每小时才更新一次，那么一天更新24次，一个月更新720次，一年才262800次，一百年才26280000次，是没有溢出危险的。如果每纳秒更新一次呢？算算看。

我知道，C语言uint32_max（奇数）再自增1之后溢出会回滚到0（偶数）不会影响到程序的正确性，但是好的程序个人认为不应该对此有依赖。

3，使用sequence lock可能会有什么坑？

假如我们的临界资源是这样的：

1

something *p;

reader进入临界区后读取p，存放在自己的变量something *q里，然后返回。之后writer对p进行了free操作；如果reader之后使用*q将发生错误。对于这种情况，需要使用值拷贝语义，或者通过引入hazard pointer等其他机制来避免内存释放问题。不仅如此，实际上在临界区里，reader都不可以使用*p，这是因为和reader writer lock不同，sequence lock是不保证writer的不存在的，也就是说在临界区里，是可能随时有writer对p进行释放等操作的，这也是它和读写锁的最大不同。