高同時(8)いくつかのスピンロックを実現することについて話します(3)

高同時(7)いくつかのスピンロックを実現することについて話しています(二)本編では2種類のキューロックについて紹介した.1つは境界キューロックであり、1つは境界キューロックである.ここで境界キューロックCLHLockはチェーンテーブル方式を採用してマルチスレッドを組織し、2つのThreadLocalを使用して自身のnodeと前のnodeを指す.その特点は前のnodeのlock状態スピンであり、現在のnodeのロックが解放されると自動的に通知される次のスレッドはロックを取得します.
CLHLockは飢餓がなく、先にサービスする公平性を保証し、少量のキャッシュ整合性流量しかなく、SMPシステム構造の中で、比較的完備したロックである.しかし、cacheのないNUMAシステムアーキテクチャでは、前のノードのlock状態でスピンするため、NUMAアーキテクチャではプロセッサがローカルメモリにアクセスする速度がネットワークを介して他のノードにアクセスするメモリよりも高いため、CLHLockはNUMAアーキテクチャで最適なスピンロックではない.
この論文では,cacheのないNUMAシステムアーキテクチャにおいて比較的完全なキューロックMCSLockに適したものを紹介する.その特徴は次のとおりです.
1.1つのThreadLocalポインタを使用してチェーンテーブルを作成し、QNode自身が次のノードのポインタを維持する
2.スレッドはCLHLockのように前のノードでスピンするのではなく、自身のノードでスピンする
3.ロック解除時に一意ノードかどうかを判断する必要があり、CAS操作を行う必要があります.一意ノードでない場合は、チェーンテーブル関係の確立を少し待つ必要があります.

package com.zc.lock;

import java.util.concurrent.atomic.AtomicReference;

/**
 *      ，           
 *   L  ，n   ，          O(L+n)
 * **/
public class MCSLock implements Lock{
	//         
	private AtomicReference tail;
	//     ，       Node,       Node
	ThreadLocal myNode;
	
	public MCSLock(){
		tail = new AtomicReference(null);
		myNode = new ThreadLocal(){
			protected QNode initialValue(){
				return new QNode();
			}
		};
	}
	
	@Override
	public void lock() {
		QNode node = myNode.get();
		// CAS    ，     
		QNode preNode = tail.getAndSet(node);
		//   preNode   ，          
		if(preNode != null){
			node.lock = true;
			preNode.next = node;
			//       node    ，  cache NUMA      ，                 
			while(node.lock){
				
			}
		}
	}

	@Override
	public void unlock() {
		QNode node = myNode.get();
		if(node.next == null){
			// CAS  ，            
			if(tail.compareAndSet(node, null)){
				//         ,    
				return;
			}
			//        ，       
			while(node.next == null){
				
			}
		}
		//           
		node.next.lock = false;
		//   next    ，          
		node.next = null;
	}
	
	public static class QNode {
		volatile boolean lock;
		volatile QNode next;
	}
	
	public String toString(){
		return "MCSLock";
	}
}

次に、MCSLockの正確性を、前編と同様の試験例を用いて試験する

package com.zc.lock;

public class Main {
	//private static Lock lock = new TimeCost(new ArrayLock(150));
	
	private static Lock lock = new MCSLock();
	
	//private static TimeCost timeCost = new TimeCost(new TTASLock());
	
	private static volatile int value = 0;
	public static void method(){
		lock.lock();
		System.out.println("Value: " + ++value);
		lock.unlock();
	}
	
	public static void main(String[] args) {
		for(int i = 0; i < 50; i ++){
			Thread t = new Thread(new Runnable(){
	
				@Override
				public void run() {
					method();
				}
				
			});
			t.start();
		}
	}

}

テスト結果:volatile変数++の結果を順番に印刷し、同じ時刻にvolatile++操作をしているスレッドが1つしかないことを証明し、ロックに成功したことを証明した.

Value: 1
Value: 2
Value: 3
Value: 4
Value: 5
Value: 6
Value: 7
Value: 8
Value: 9
Value: 10
Value: 11
Value: 12
Value: 13
Value: 14
Value: 15
Value: 16
Value: 17
Value: 18
Value: 19
Value: 20
Value: 21
Value: 22
Value: 23
Value: 24
Value: 25
Value: 26
Value: 27
Value: 28
Value: 29
Value: 30
Value: 31
Value: 32
Value: 33
Value: 34
Value: 35
Value: 36
Value: 37
Value: 38
Value: 39
Value: 40
Value: 41
Value: 42
Value: 43
Value: 44
Value: 45
Value: 46
Value: 47
Value: 48
Value: 49
Value: 50