# StampedLock

## 简介

StampedLock的状态由版本和模式组成。

（1）write

（3）乐观读

### 核心思想

StampedLock实现了不仅多个读不互相阻塞，同时在读操作时不会阻塞写操作

• 为什么StampedLock这么神奇？

## 使用案例

public class Point {

private double x, y;

private final StampedLock stampedLock = new StampedLock();

//写锁的使用
void move(double deltaX, double deltaY){
long stamp = stampedLock.writeLock(); //获取写锁
try {
x += deltaX;
y += deltaY;
} finally {
stampedLock.unlockWrite(stamp); //释放写锁
}
}

//乐观读锁的使用
double distanceFromOrigin() {

double currentX = x;
double currentY = y;
if (!stampedLock.validate(stamp)) { //检查乐观读锁后是否有其他写锁发生，有则返回false

try {
currentX = x;
} finally {
}
}
return Math.sqrt(currentX*currentX + currentY*currentY);
}

//悲观读锁以及读锁升级写锁的使用
void moveIfAtOrigin(double newX,double newY) {

try {
while (x == 0.0 && y == 0.0) {
long ws = stampedLock.tryConvertToWriteLock(stamp); //读锁转换为写锁
if (ws != 0L) { //转换成功

stamp = ws; //票据更新
x = newX;
y = newY;
break;
} else {
stamp = stampedLock.writeLock(); //强制获取写锁
}
}
} finally {
stampedLock.unlock(stamp); //释放所有锁
}
}
}


# 源码分析

## 类定义

/*
* @since 1.8
* @author Doug Lea
*/
public class StampedLock implements java.io.Serializable {}


## 算法笔记

ps: 这里可以看出，这个设计实际上是取自序列锁的设计思想，linux 内核中也有使用。

https://www.hpl.hp.com/techreports/2012/HPL-2012-68.pdf 论文地址

Effective Synchronization on Linux/NUMA Systems

ps: 这两本书我本人也翻译了一遍，但是内容过于枯燥（水平有限，翻译的枯燥），且内容较多，这里就不做展开了。

## 一些常量定义

/** Number of processors, for spin control

*/
private static final int NCPU = Runtime.getRuntime().availableProcessors();

/** Maximum number of retries before enqueuing on acquisition
入队前最大重试次数
*/
private static final int SPINS = (NCPU > 1) ? 1 << 6 : 0;

/** Maximum number of retries before blocking at head on acquisition

*/
private static final int HEAD_SPINS = (NCPU > 1) ? 1 << 10 : 0;

/** Maximum number of retries before re-blocking

*/
private static final int MAX_HEAD_SPINS = (NCPU > 1) ? 1 << 16 : 0;

/** The period for yielding when waiting for overflow spinlock

*/
private static final int OVERFLOW_YIELD_RATE = 7; // must be power 2 - 1
/** The number of bits to use for reader count before overflowing

*/
private static final int LG_READERS = 7;


## 读写锁共享的状态量

// 用于操作state后获取stamp的值
private static final int LG_READERS = 7;
private static final long RUNIT = 1L;               //0000 0000 0001
private static final long WBIT  = 1L << LG_READERS; //0000 1000 0000
private static final long RBITS = WBIT - 1L;        //0000 0111 1111
private static final long RFULL = RBITS - 1L;       //0000 0111 1110
private static final long ABITS = RBITS | WBIT;     //0000 1111 1111
private static final long SBITS = ~RBITS;           //1111 1000 0000

//初始化时state的值
private static final long ORIGIN = WBIT << 1;       //0001 0000 0000

//锁共享变量state
private transient volatile long state;
//读锁溢出时用来存储多出的毒素哦


## 其他常量

// Initial value for lock state; avoid failure value zero
// 锁定状态的初始值； 避免故障值为零
private static final long ORIGIN = WBIT << 1;

// Special value from cancelled acquire methods so caller can throw IE
// 取消get方法中的特殊值，以便调用方可以抛出中断异常
private static final long INTERRUPTED = 1L;

// Values for node status; order matters
// 节点状态的值； 顺序很重要
private static final int WAITING   = -1;
private static final int CANCELLED =  1;

// Modes for nodes (int not boolean to allow arithmetic)
// 节点的模式（不为布尔值以允许算术计算）
private static final int RMODE = 0;
private static final int WMODE = 1;


## 等待节点定义

mode 使用 final 修饰，一旦创建就是不可变的，所以是线程安全的。

/** Wait nodes */
static final class WNode {
volatile WNode prev;
volatile WNode next;
volatile int status;      // 0, WAITING, or CANCELLED
final int mode;           // RMODE or WMODE
WNode(int m, WNode p) { mode = m; prev = p; }
}

/** Head of CLH queue */
/** Tail (last) of CLH queue */
private transient volatile WNode wtail;


# 视图

// views
transient WriteLockView writeLockView;


final class ReadLockView implements Lock {
public void lock() { readLock(); }
public void lockInterruptibly() throws InterruptedException {
}
public boolean tryLock() { return tryReadLock() != 0L; }
public boolean tryLock(long time, TimeUnit unit)
throws InterruptedException {
}
public void unlock() { unstampedUnlockRead(); }
public Condition newCondition() {
throw new UnsupportedOperationException();
}
}


## 写锁视图

final class WriteLockView implements Lock {
public void lock() { writeLock(); }
public void lockInterruptibly() throws InterruptedException {
writeLockInterruptibly();
}
public boolean tryLock() { return tryWriteLock() != 0L; }
public boolean tryLock(long time, TimeUnit unit)
throws InterruptedException {
return tryWriteLock(time, unit) != 0L;
}
public void unlock() { unstampedUnlockWrite(); }
public Condition newCondition() {
throw new UnsupportedOperationException();
}
}


## 读写锁视图

final class ReadWriteLockView implements ReadWriteLock {
public Lock writeLock() { return asWriteLock(); }
}


### 读锁实现

public Lock asReadLock() {
return ((v = readLockView) != null ? v :
}


### 写锁实现

public Lock asWriteLock() {
WriteLockView v;
return ((v = writeLockView) != null ? v :
(writeLockView = new WriteLockView()));
}


# 三种锁的获取和释放

Java并发（8）- 读写锁中的性能之王：StampedLock

## 写锁的释放和获取

### 源码

public StampedLock() {
state = ORIGIN; //初始化state为 0001 0000 0000
}

public long writeLock() {
long s, next;
return ((((s = state) & ABITS) == 0L && //没有读写锁
U.compareAndSwapLong(this, STATE, s, next = s + WBIT)) ? //cas操作尝试获取写锁
next : acquireWrite(false, 0L));    //获取成功后返回next，失败则进行后续处理，排队也在后续处理中
}

public void unlockWrite(long stamp) {
WNode h;
if (state != stamp || (stamp & WBIT) == 0L) //stamp值被修改，或者写锁已经被释放，抛出错误
throw new IllegalMonitorStateException();
state = (stamp += WBIT) == 0L ? ORIGIN : stamp; //加0000 1000 0000来记录写锁的变化，同时改变写锁状态
if ((h = whead) != null && h.status != 0)
release(h);
}


### 写锁获取的情况

（1）没有读锁和写锁时，state为0001 0000 0000

0001 0000 0000 & 0000 1111 1111 = 0000 0000 0000 // 等于0L，可以尝试获取写锁


（2）有一个读锁时，state为0001 0000 0001

0001 0000 0001 & 0000 1111 1111 = 0000 0000 0001 // 不等于0L


（3）有一个写锁，state为0001 1000 0000

0001 1000 0000 & 0000 1111 1111 = 0000 1000 0000 // 不等于0L


0001 0000 0000 + 0000 1000 0000 = 0001 1000 0000


### 写锁释放

0010 0000 0000 = 0001 1000 0000 + 0000 1000 0000


0001 0000 0000 + 0000 1000 0000 = 0001 1000 0000


0001 1000 0000 + 0000 1000 0000 = 0010 0000 0000


0010 0000 0000 + 0000 1000 0000 = 0010 1000 0000


0010 1000 0000 + 0000 1000 0000 = 0011 0000 0000


1110 0000 0000 + 0000 1000 0000 = 1110 1000 0000


1110 1000 0000 + 0000 1000 0000 = 1111 0000 0000


## 悲观读锁的释放和获取

### 源码

public long readLock() {
long s = state, next;
return ((whead == wtail && (s & ABITS) < RFULL && //队列为空，无写锁，同时读锁未溢出，尝试获取读锁
U.compareAndSwapLong(this, STATE, s, next = s + RUNIT)) ?   //cas尝试获取读锁+1
next : acquireRead(false, 0L));     //获取读锁成功，返回s + RUNIT，失败进入后续处理，类似acquireWrite
}

long s, m; WNode h;
for (;;) {
if (((s = state) & SBITS) != (stamp & SBITS) ||
(stamp & ABITS) == 0L || (m = s & ABITS) == 0L || m == WBIT)
throw new IllegalMonitorStateException();
if (m < RFULL) {    //小于最大记录值（最大记录值127超过后放在readerOverflow变量中）
if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {  //cas尝试释放读锁-1
if (m == RUNIT && (h = whead) != null && h.status != 0)
release(h);
break;
}
}
break;
}
}


### 锁获取

// 小于 0000 0111 1110，可以尝试获取读锁
0001 0000 0000 & 0000 1111 1111 = 0000 0000 0000


// 小于 0000 0111 1110，可以尝试获取读锁
0001 0000 0001 & 0000 1111 1111 = 0000 0000 0001


// 大于 0000 0111 1110，不可以获取读锁
0001 1000 0000 & 0000 1111 1111 = 0000 1000 0000


// 等于 0000 0111 1110，不可以获取读锁
0001 0111 1110 & 0000 1111 1111 = 0000 0111 1110


## 乐观读锁的获取和验证

### 源码

//尝试获取乐观锁
long s;
return (((s = state) & WBIT) == 0L) ? (s & SBITS) : 0L;
}

//验证乐观锁获取之后是否有过写操作
public boolean validate(long stamp) {
return (stamp & SBITS) == (state & SBITS);  //比较是否有过写操作
}


### 锁获取

（1）没有读锁和写锁时，state为0001 0000 0000

//((s = state) & WBIT) == 0L) true
0001 0000 0000 & 0000 1000 0000 = 0000 0000 0000
//(s & SBITS)
0001 0000 0000 & 1111 1000 0000 = 0001 0000 0000


（2）有一个读锁时，state为0001 0000 0001

//((s = state) & WBIT) == 0L) true
0001 0000 0001 & 0000 1000 0000 = 0000 0000 0000
//(s & SBITS)
0001 0000 0001 & 1111 1000 0000 = 0001 0000 0000


（3）有一个写锁，state为0001 1000 0000

//((s = state) & WBIT) == 0L) false
0001 1000 0000 & 0000 1000 0000 = 0000 1000 0000
//0L
0000 0000 0000


### 验证是否有写操作

（1）写过一次

0001 0000 0000 & 1111 1000 0000 = 0001 0000 0000
0010 0000 0000 & 1111 1000 0000 = 0010 0000 0000   //false


（2）未写过，但读过

0001 0000 0000 & 1111 1000 0000 = 0001 0000 0000
0001 0000 1111 & 1111 1000 0000 = 0001 0000 0000   //true


（3）正在写

0001 0000 0000 & 1111 1000 0000 = 0001 0000 0000
0001 1000 0000 & 1111 1000 0000 = 0001 1000 0000   //false


（4）之前正在写，无论是否写完都不会为0L

0000 0000 0000 & 1111 1000 0000 = 0000 0000 0000   //false


# 小结

（1）synchronized 最常用的悲观锁，使用方便，但是为非公平锁。

（2）ReentrantLock 可重入锁，提供了公平锁等丰富特性。