Yebangyu's Blog

Fond of Concurrency Programming, Distributed System and Performance Optimization.

Sequence Lock

在读多写少(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进行释放等操作的,这也是它和读写锁的最大不同。