Sequantial Lock in Java

    1 Overview

   Linux内核中常见的同步机制有Atomic Operation，Spin Locks，Semaphore，Mutex等。其中Spin Locks和Semaphore都支持读/写锁。此外，Linux内核还支持一种更轻量级的读/写锁定机制：Sequential Lock。跟其它读/写锁定机制相比，Sequential Lock有以下特点：

在获取锁时偏向写锁。只要他人不持有写锁，那么获得写锁的操作总是能够成功。
读操作时不需要获得锁（即读操作永远不会被阻塞），然而在有些情况下读操作需要重试。
Sequential Lock更轻量级，可伸缩性相对更好。


2 Linux Kernel's Implementation

   以下是2.6版本的内核中，Sequential Lock的实现：
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:
seqlock_t mr_seq_lock = DEFINE_SEQLOCK(mr_seq_lock);
   The write path:
write_seqlock(&mr_seq_lock);
/* write lock is obtained... */
write_sequnlock(&mr_seq_lock);
   The read path:
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已经提供了一比较好的实现，在其基础之上稍加改动之后的实现如下：
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