本章内容将介绍自旋锁种的复合锁和层次锁算法，代码结构较为复杂。由于复杂度原因本章没有提供较多的示意图，需要读者反复阅读代码，加上文字说明以帮助理解算法。正如古人云：“学如溺水行舟不进则退。”
复合锁
public class Backoff {final int minDelay , maxDelay;int limit;final Random random;public Backoff(int min , int max) {minDelay = min;maxDelay = max;limit = minDelay;random = new Random();}public void backoff() throw Exception {int delay = random.nextInt(limit);limit = Math.min(maxDelay , 2 * limit);Thread.sleep(delay);}}
enum State {FREE, WAITING, RELEASED, ABORTED};class QNode {AtomicReference<State> state;QNode pred;public QNode() {state = new AtomicReference<State>(State.FREE);}}public class CompositeLock implements Lock{private static final int SIZE = 4;private static final int MIN_BACKOFF = 1024;private static final int MAX_BACKOFF = 256 * MIN_BACKOFF;AtomicStampedReference<QNode> tail;QNode[] waiting;Random random;ThreadLocal<QNode> myNode = new ThreadLocal<QNode>() {protected QNode initialValue() { return null; };};public CompositeLock() {tail = new AtomicStampedReference<QNode>(null, 0);random = new Random();waiting = new QNode[SIZE];for (int i = 0; i < waiting.length; i++) {waiting[i] = new QNode();}}public boolean tryLock(long time, TimeUnit unit) throws InterruptedException {long patience = TimeUnit.MILLISECONDS.convert(time, unit);long startTime = System.currentTimeMillis();Backoff backoff = new Backoff(MIN_BACKOFF, MAX_BACKOFF);try {QNode node = acquireQNode(backoff, startTime, patience);QNode pred = spliceQNode(node, startTime, patience);waitForPredecessor(pred, node, startTime, patience);return true;} catch (TimeoutException e) {return false;}}public void unlock() {QNode acqNode = myNode.get();acqNode.state.set(State.RELEASED);}private boolean timeout(long startTime, long patience) {return System.currentTimeMillis() - startTime > patience;}private QNode acquireQNode(Backoff backoff, long startTime, long patience)throws TimeoutException, InterruptedException {QNode node = waiting[random.nextInt(SIZE)];QNode currTail;int[] currStamp = {0};while (true) {if (node.state.compareAndSet(State.FREE, State.WAITING)) {return node;}currTail = tail.get(currStamp);State state = node.state.get();if (state == State.ABORTED || state == State.RELEASED) {if (node == currTail) {QNode myPred = null;if (state == State.ABORTED) {myPred = node.pred;}if (tail.compareAndSet(currTail, myPred,currStamp[0], currStamp[0]+1)) {node.state.set(State.WAITING);return node;}}}backoff.backoff();if (timeout(patience, startTime)) {throw new TimeoutException();}}}private QNode spliceQNode(QNode node, long startTime, long patience)throws TimeoutException {QNode currTail;int[] currStamp = {0};// splice node into queuedo {currTail = tail.get(currStamp);if (timeout(startTime, patience)) {node.state.set(State.FREE);throw new TimeoutException();}} while (!tail.compareAndSet(currTail, node,currStamp[0], currStamp[0]+1));return currTail;}private void waitForPredecessor(QNode pred, QNode node, long startTime, long patience)throws TimeoutException {// wait for predecessor to release lockint[] stamp = {0};if (pred == null) {myNode.set(node);return;}State predState = pred.state.get();while (predState != State.RELEASED) {if (predState == State.ABORTED) {QNode temp = pred;pred = pred.pred;temp.state.set(State.FREE);}if (timeout(patience, startTime)) {node.pred = pred;node.state.set(State.ABORTED);throw new TimeoutException();}predState = pred.state.get();}pred.state.set(State.FREE);myNode.set(node);return;}
快速路径复合锁
public class CompositeFastPathLock extends CompositeLock {private static final int FASTPATH = 1 << 30;public int fastPathTaken = 0;public boolean tryLock(long time, TimeUnit unit) throws InterruptedException {if (fastPathLock()) {fastPathTaken++;return true;}if (super.tryLock(time, unit)) {fastPathWait();return true;}return false;}public void unlock() {if (!fastPathUnlock()) {super.unlock();};}private boolean fastPathLock() {int oldStamp, newStamp;int stamp[] = {0};QNode qnode;qnode = tail.get(stamp);oldStamp = stamp[0];if (qnode != null) {return false;}if ((oldStamp & FASTPATH) != 0) {return false;}newStamp = (oldStamp + 1) | FASTPATH; // set flagreturn tail.compareAndSet(qnode, null, oldStamp, newStamp);}private boolean fastPathUnlock() {int oldStamp, newStamp;oldStamp = tail.getStamp();if ((oldStamp & FASTPATH) == 0) {return false;}int[] stamp = {0};QNode qnode;do {qnode = tail.get(stamp);oldStamp = stamp[0];newStamp = oldStamp & (~FASTPATH); // unset flag} while (!tail.compareAndSet(qnode, qnode, oldStamp, newStamp));return true;}private void fastPathWait() {while ((tail.getStamp() & FASTPATH ) != 0) {} // spin while flag is set}}
层次锁
层次后退锁
HBOLock
public class HBOLock implements Lock {private static final int LOCAL_MIN_DELAY = 8;private static final int LOCAL_MAX_DELAY = 256;private static final int REMOTE_MIN_DELAY = 256;private static final int REMOTE_MAX_DELAY = 1024;private static final int FREE = -1;AtomicInteger state;public HBOLock() {state = new AtomicInteger(FREE);}public void lock() {int myCluster = ThreadID.getCluster();Backoff localBackoff = new Backoff(LOCAL_MIN_DELAY, LOCAL_MAX_DELAY);Backoff remoteBackoff = new Backoff(REMOTE_MIN_DELAY, REMOTE_MAX_DELAY);while (true) {if (state.compareAndSet(FREE, myCluster)) {return;}int lockState = state.get();try {if (lockState == myCluster) {localBackoff.backoff();} else {remoteBackoff.backoff();}} catch (InterruptedException ex) {}}}public void unlock() {state.set(FREE);}}
层次CLH队列锁
HCLHLock
public class HCLHLock implements Lock {static final int MAX_CLUSTERS = 32;List<AtomicReference<QNode>> localQueues;AtomicReference<QNode> globalQueue;ThreadLocal<QNode> currNode = new ThreadLocal<QNode>() {protected QNode initialValue() { return new QNode(); };};ThreadLocal<QNode> predNode = new ThreadLocal<QNode>() {protected QNode initialValue() { return null; };};public HCLHLock() {localQueues = new ArrayList<AtomicReference<QNode>>(MAX_CLUSTERS);for (int i = 0; i < MAX_CLUSTERS; i++) {localQueues.add(new AtomicReference <QNode>());}QNode head = new QNode();globalQueue = new AtomicReference<QNode>(head);}public void lock() {QNode myNode = currNode.get();AtomicReference<QNode> localQueue = localQueues.get(ThreadID.getCluster());// splice my QNode into local queueQNode myPred = null;do {myPred = localQueue.get();} while (!localQueue.compareAndSet(myPred, myNode));if (myPred != null) {boolean iOwnLock = myPred.waitForGrantOrClusterMaster();if (iOwnLock) {// I have the lock. Save QNode just released by previous leaderpredNode.set(myPred);return;}}// At this point I am the cluster master.// Splice local queue into global queue.QNode localTail = null;do {myPred = globalQueue.get();localTail = localQueue.get();} while(!globalQueue.compareAndSet(myPred, localTail));// inform successor it is the new masterlocalTail.setTailWhenSpliced(true);// wait for predecessor to release lockwhile (myPred.isSuccessorMustWait()) {};// I have the lock. Save QNode just released by previous leaderpredNode.set(myPred);return;}public void unlock() {QNode myNode = currNode.get();myNode.setSuccessorMustWait(false);// promote pred node to currentQNode node = predNode.get();node.unlock();currNode.set(node);}static class QNode {// private boolean tailWhenSpliced;private static final int TWS_MASK = 0x80000000;// private boolean successorMustWait= false;private static final int SMW_MASK = 0x40000000;// private int clusterID;private static final int CLUSTER_MASK = 0x3FFFFFFF;AtomicInteger state;public QNode() {state = new AtomicInteger(0);}boolean waitForGrantOrClusterMaster() {int myCluster = ThreadID.getCluster();while(true) {if (getClusterID() == myCluster &&!isTailWhenSpliced() &&!isSuccessorMustWait()) {return true;} else if (getClusterID() != myCluster || isTailWhenSpliced()) {return false;}}}public void unlock() {int oldState = 0;int newState = ThreadID.getCluster();// successorMustWait = true;newState |= SMW_MASK;// tailWhenSpliced = false;newState &= (~TWS_MASK);do {oldState = state.get();} while (! state.compareAndSet(oldState, newState));}public int getClusterID() {return state.get() & CLUSTER_MASK;}public void setClusterID(int clusterID) {int oldState, newState;do {oldState = state.get();newState = (oldState & ~CLUSTER_MASK) | clusterID;} while (! state.compareAndSet(oldState, newState));}public boolean isSuccessorMustWait() {return (state.get() & SMW_MASK) != 0;}public void setSuccessorMustWait(boolean successorMustWait) {int oldState, newState;do {oldState = state.get();if (successorMustWait) {newState = oldState | SMW_MASK;} else {newState = oldState & ~SMW_MASK;}} while (! state.compareAndSet(oldState, newState));}public boolean isTailWhenSpliced() {return (state.get() & TWS_MASK) != 0;}public void setTailWhenSpliced(boolean tailWhenSpliced) {int oldState, newState;do {oldState = state.get();if (tailWhenSpliced) {newState = oldState | TWS_MASK;} else {newState = oldState & ~TWS_MASK;}} while (! state.compareAndSet(oldState, newState));}}}
到这里今天的内容就讲完了，希望对你有帮助，如果觉得有收获还请点击"再看"支持作者。本人才疏学浅，如果文中有不当之处还请留言指正。
往期精彩回顾
长按识别
原文作者：DevXTalk；如有侵权，请联系管理员删除。
上一篇：
技术之外的图片故事
下一篇：
并发编程的艺术06-自旋锁总结
请登录后发表评论
登录
全部评论
