转载

Sequence Lock

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

Mutex
Reader Writer Lock
Sequence Lock
Read Copy Update

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

从今天起，我们介绍后面两种同步设施。今天我们先介绍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是否相等，不等的话说明此次读取失败，需要重试。

基本实现

#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;     CPU_MEMORY_BARRIER();     if (!(sc & 1)) {       break; //sc是偶数，说明没有writer，返回     }   }   return sc; }  static bool reader_need_retry(SequenceLock &sl, uint64_t oldseq) {   uint64_t s = 0;   CPU_MEMORY_BARRIER();   s = sl.sequence_count;   return s != oldseq; }  static void write_seqlock(SequenceLock &sl) {   sl.lock.lock();   ++sl.sequence_count;//让count变为奇数，和读者声明自己的存在   CPU_MEMORY_BARRIER(); }  static void write_sequnlock(SequenceLock &sl) {   CPU_MEMORY_BARRIER();   ++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几乎不会发生。

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

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

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

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