1 Overview
Linux內核中常見的同步機制有Atomic Operation，Spin Locks，Semaphore，Mutex等。其中Spin Locks和Semaphore都支持讀/寫鎖。此外，Linux內核還支持一種更輕量級的讀/寫鎖定機制：Sequential Lock。跟其它讀/寫鎖定機制相比，Sequential Lock有以下特點：
在獲取鎖時偏向寫鎖。隻要他人不持有寫鎖，那麼獲得寫鎖的操作總是能夠成功。
讀操作時不需要獲得鎖（即讀操作永遠不會被阻塞），然而在有些情況下讀操作需要重試。
Sequential Lock更輕量級，可伸縮性相對更好。
2 Linux Kernels Implementation
以下是2.6版本的內核中，Sequential Lock的實現：
C代碼
typedef struct {
unsigned sequence;
spinlock_t lock;
} seqlock_t;
static inline void write_seqlock(seqlock_t *sl)
{
spin_lock(&sl->lock);
++sl->sequence;
smp_wmb();
}
static inline void write_sequnlock(seqlock_t *sl)
{
smp_wmb();
sl->sequence++;
spin_unlock(&sl->lock);
}
static __always_inline unsigned read_seqbegin(const seqlock_t *sl)
{
unsigned ret = sl->sequence;
smp_rmb();
return ret;
}
static __always_inline int read_seqretry(const seqlock_t *sl, unsigned iv)
{
smp_rmb();
return (iv & 1) | (sl->sequence ^ iv);
}
以上代碼中，通過使用spin lock保證瞭write操作的原子性。需要註意的是，Linux spin lock是非可重入鎖，這也是read_seqretry方法中可以通過(iv & 1)判斷一個寫操作是否正在進行中的原因。此外，Linux spin lock隻能保證原子性，為瞭避免由於編譯器或者處理器對指令的重排序（例如x86平臺不會對寫操作重排序，但是可能會對讀操作進行重排序）所導致的潛在問題，seqlock使用memory barrier（smp_wmb和smp_rmb）保證瞭內存可見性。
seqlock的用法如下：
To define a seqlock:
C代碼
seqlock_t mr_seq_lock = DEFINE_SEQLOCK(mr_seq_lock);
The write path:
C代碼
write_seqlock(&mr_seq_lock);
/* write lock is obtained… */
write_sequnlock(&mr_seq_lock);
The read path:
C代碼
unsigned long seq;
do {
seq = read_seqbegin(&mr_seq_lock);
/* read data here … */
} while (read_seqretry(&mr_seq_lock, seq));
seqlock的典型使用場景如下：
跟讀操作的數量相比，寫操作的數量很少。
在鎖獲取時，希望寫操作優先。
使用seqlock的註意事項：
讀操作耗時應比較短，否則容易導致過多次的讀重試。
由於在讀的過程中寫操作可能正在修改數據，因此讀操作可能會讀取到某種不一致的狀態。所以進行讀取時，需要保護性的驗證，以避免因讀取不一致的錯誤數據導致錯讀。
3 Sequential Lock in Java
本想自己實現一個Java版本的Sequential lock，但是在Google瞭之後發現Makoto YUI已經提供瞭一比較好的實現，在其基礎之上稍加改動之後的實現如下：
Java代碼
public final class SequentialLock {
//
private volatile int counter;
/**
*
*/
public int readBegin() {
return this.counter;
}
public boolean readRetry(int v) {
return (v & 1) == 1 || this.counter != v;
}
public synchronized void writeLock() {
//
if((this.counter & 1) != 0) {
throw new IllegalStateException(“sequential lock is NOT reentrantable”);
}
//
++this.counter;
}
public synchronized void writeUnlock() {
++this.counter;
}
}
首先，SequentialLock不是可重入的。其次由於讀操作沒有獲得鎖，因此讀寫之間需要額外的機制以保證內存可見性：對其volitle counter成員變量的讀寫保證瞭Sequential Lock保護的數據之間的happens bofore語義。
4 Reference
Linux Kernel Development 3rd Edition, Robert Love
