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