26.StampedLock

1.简介

ReentrantReadWriteLock采用的是“悲观读”的策略，当第一个读线程拿到锁之后，第二个、第三个读线程还可以拿到锁，使得写线程一直拿不到锁，可能导致写线程“饿死”。虽然在其公平或非公平的实现中，都尽量避免这种情形（写锁偏向性，优先级高），但还有可能发生。

StampedLock引入了“乐观读”策略，读的时候不加读锁，读出来发现数据被修改了，再升级为“悲观读”，相当于降低了“读”的地位，把抢锁的天平往“写”的一方倾斜了一下，避免写线程被饿死。

2.使用场景

class Point { 
    private double x, y; 
    private final StampedLock sl = new StampedLock(); 
    // 多个线程调用该方法，修改x和y的值 
    void move(double deltaX, double deltaY) { 
        long stamp = sl.writeLock(); 
        try {
            x += deltaX; y += deltaY; 
        } finally { 
            sl.unlockWrite(stamp); 
        } }
    // 多个线程调用该方法，求距离 
    double distenceFromOrigin() {
        // 使用“乐观读” 
        long stamp = sl.tryOptimisticRead(); 
        // 将共享变量拷贝到线程栈 
        double currentX = x, currentY = y; 
        // 读期间有其他线程修改数据
        if (!sl.validate(stamp)) { 
            // 读到的是脏数据，丢弃。 
            // 重新使用“悲观读” 
            stamp = sl.readLock(); 
            try {
                currentX = x; currentY = y; 
            } finally { sl.unlockRead(stamp); 
        } }
        return Math.sqrt(currentX * currentX + currentY * currentY); 
    } }

有一个Point类，多个线程调用move()方法，修改坐标；还有多个线程调用distanceFromOrigin()方法，求距离。
首先，执行move操作的时候，要加写锁。这个用法和ReadWriteLock的用法没有区别，写操作和写操作也是互斥的。
关键在于读的时候，用了一个“乐观读”sl.tryOptimisticRead()，相当于在读之前给数据的状态做了一个“快照”。然后，把数据拷贝到内存里面，在用之前，再比对一次版本号。如果版本号变了，则说明在读的期间有其他线程修改了数据。读出来的数据废弃，重新获取读锁。

要说明的是，这三行关键代码对顺序非常敏感，不能有重排序。因为 state 变量已经是volatile，所以可以禁止重排序，但stamp并不是volatile的。为此，在validate(stamp)方法里面插入内存屏障。

public boolean validate(long stamp) { 
    VarHandle.acquireFence();   //内存屏障
    return (stamp & SBITS) == (state & SBITS); 
}

3. “乐观读”的实现原理

首先，StampedLock是一个读写锁，因此也会像读写锁那样，把一个state变量分成两半，分别表示读锁和写锁的状态。同时，它还需要一个数据的version。但是，一次CAS没有办法操作两个变量，所以这个state变量本身同时也表示了数据的version。

用最低的8位表示读和写的状态，其中第8位表示写锁的状态，最低的7位表示读锁的状态。因为写锁只有一个bit位，所以写锁是不可重入的。

4 悲观读/写：“阻塞”与“自旋”策略实现差异

StampedLock也要进行悲观的读锁和写锁操作。不过，它不是基于AQS实现的，而是内部重新实现了一个阻塞队列。

• 刚开始的时候，whead=wtail=NULL，然后初始化，建一个空节点，whead和wtail都指向这个空节点，之后往里面加入一个个读线程或写线程节点。
• 基于这个阻塞队列实现的锁的调度策略和AQS很不一样，也就是“自旋”。
• 不同点：在AQS里面，当一个线程CAS state失败之后，会立即加入阻塞队列，并且进入阻塞状态。
• 但在StampedLock中，CAS state失败之后，会不断自旋，自旋足够多的次数之后，如果还拿不到锁，才进入阻塞状态。
  根据CPU的核数，定义了自旋次数的常量值

StampedLock还提供了更复杂的将悲观读锁升级为写锁的功能，它主要使用在if-then-update的场景：即先读，如果读的数据满足条件，就返回，如果读的数据不满足条件，再尝试写。