자바 병렬 프로 그래 밍 (14): 원자 변수 와 비 차단 동기 화 메커니즘

원자 변수 와 비 차단 동기 화 메커니즘:
자물쇠 의 장점:

스 레 드 가 잠 금 에서 경쟁 할 때 스마트 한 JVM 은 반드시 스 레 드 를 걸 지 않 고 이전 작업 에서 잠 금 보유 시간 에 따라 이 스 레 드 가 걸 리 는 지 자전 하 는 지 판단 합 니 다.

하드웨어 가 병발 에 미 치 는 영향:

독점 자 물 쇠 는 비관 적 인 기술 이다.

현재 프로세서 에 서 는 읽 기 - 쓰기 - 변경 명령 을 기본적으로 지원 합 니 다. 예 를 들 어 비교 및 교환 (CAS) 또는 관련 로드 / 조건 저장 (Load - Link / store - Conditional).운영 체제 와 JVM 은 이러한 명령 을 사용 하여 잠 금 과 동시 데이터 구 조 를 실현 한다.jdk 5 이전에 이 명령 을 직접 사용 할 수 없습니다.

비교 및 교환:

CAS 는 읽 기와 쓰기 가 필요 한 메모리 위치 V, 비교 하 는 값 A 와 쓰기 위 한 새 값 B 를 3 개의 조작 수 를 포함 하고 있다.

시 뮬 레이 션 CAS 작업:

/**
 *   CAS
 */
public class SimulatedCAS {
	private int value;
	
	public synchronized int get(){
		return value;
	}
	
	public synchronized int compareAndSwap(int expectedValue, int newValue){
		int oldValue = value;
		if (oldValue == expectedValue){
			value = newValue;
		}
		return oldValue;
	}
	
	public synchronized boolean compareAndSet(int expectedValue, int newValue){
		return (expectedValue == compareAndSwap(expectedValue, newValue));
	}
}

차단 되 지 않 은 카운터:

/**
 *   CAS         
 */
public class CasCounter {
	private SimulatedCAS value;
	
	public int getValue(){
		return value.get();
	}
	
	public int increment(){
		int v;
		
		do {
			v = value.get();
		} while (v != value.compareAndSwap(v, v+1));
		return v + 1;
	}
}

대부분의 프로세서 에서 경쟁 없 는 잠 금 획득 과 방출 된 '빠 른 코드 경로' 에 대한 비용 은 CAS 비용 의 두 배 에 달 합 니 다.

JVM 의 CAS 지원:

JVM 은 디지털 형식 과 인용 유형 에 효율 적 인 CAS 작업 을 제공 했다. 예 를 들 어 AtomicXxx.

원자 변수 클래스:
원자 변 수 는 '더 좋 은 volatile' 입 니 다.

/**
 *   CAS               
 */
public class CasNumberRange {
	private static class IntPair{
		//      : lower <= upper
		final int lower;
		final int upper;
		
		public IntPair(int lower, int upper) {
			this.lower = lower;
			this.upper = upper;
		}
	}
	
	private AtomicReference<IntPair> values = new AtomicReference<>();
	
	public int getLower(){
		return values.get().lower;
	}
	
	public int getUpper(){
		return values.get().upper;
	}
	
	public void setLower(int i){
		while (true){
			IntPair oldv = values.get();
			if (i > oldv.upper){
				throw new IllegalArgumentException("lower can't > upper");
			}
			IntPair newv = new IntPair(i, oldv.upper);
			if (values.compareAndSet(oldv, newv)){
				return;
			}
		}
	}
}

성능 비교: 자물쇠 와 원자 변수

ReentrantLock 기반 난수 생 성기:

/**
 *   ReentrantLock         
 */
public class ReentrantLockPreudoRandom extends PseudoRandom{
	private final Lock lock = new ReentrantLock(false);
	private int seed;
	
	public ReentrantLockPreudoRandom(int seed){
		this.seed = seed;
	}
	
	public int nextInt(int n){
		lock.lock();
		try{
			int  s = seed;
			seed = calculateNext(s);
			int remainder = s % n;
			return remainder > 0 ? remainder : remainder + n;
		} finally{
			lock.unlock();
		}
	}
       ...
}

AtomicInteger 기반 랜 덤 생 성기

/**
 *   AtomicInteger         
 */
public class AtomicPseudoRandom extends PseudoRandom{
	private AtomicInteger seed;
	
	public AtomicPseudoRandom(int seed){
		this.seed = new AtomicInteger(seed);
	}
	
	public int nextInt(int n){
		while (true){
			int s = seed.get();
			int nextSeed = calculateNext(s);
			if (seed.compareAndSet(s, nextSeed)){
				int remainder = s % n;
				return remainder > 0 ? remainder: remainder + n;
			}
		}
	}
       ...
}

비 차단 알고리즘:

한 스 레 드 가 실패 하거나 걸 리 면 다른 스 레 드 도 실패 하거나 걸 리 지 않 습 니 다. 그러면 이런 알고리즘 은 바로 비 차단 알고리즘 입 니 다.

비 차단 스 택 구현:

/**
 *   Treiber         
 */
public class ConcurrentStack<E> {
	private AtomicReference<Node<E>> top = new AtomicReference<ConcurrentStack.Node<E>>();
	
	public void push(E item){
		Node<E> newHead = new Node<E>(item);
		Node<E> oldHead;
		
		do{
			oldHead = top.get();
			newHead.next = oldHead;
		} while (!top.compareAndSet(oldHead, newHead));
	}
	
	public E pop(){
		Node<E> oldHead;
		Node<E> newHead;
		
		do {
			oldHead = top.get();
			if (oldHead == null)
				return null;
			newHead = oldHead.next;
		} while (!top.compareAndSet(oldHead, newHead));
		return oldHead.item;
	}
	
	private static class Node<E>{
		public final E item;
		public Node<E> next;
		
		public Node(E item){
			this.item = item;
		}
	}
}

비 차단 링크 의 삽입 작업 실현:

/**
 *               ，  Michael-Scott
 */
public class LinkedQueue<E> {
	private static class Node<E>{
		final E item;
		final AtomicReference<Node<E>> next;
		
		public Node(E item, Node<E> next){ 
			this.item = item;
			this.next = new AtomicReference<>(next);
		}
	}
	
	private final Node<E> dummy = new Node<E>(null, null);
	private final AtomicReference<Node<E>> head = 
						new AtomicReference<>(dummy);
	private final AtomicReference<Node<E>> tail = 
						new AtomicReference<>(dummy);
	
	public boolean put(E item){
		Node<E> newNode = new Node<E>(item, null);
		while (true){
			Node<E> curTail = tail.get();
			Node<E> tailNext = curTail.next.get();
			if (curTail == tail.get()){		//      
				if (tailNext != null){
					//         (        ，       )，     
					tail.compareAndSet(curTail, tailNext);
				} else{
					//       ,        
					if (curTail.next.compareAndSet(null, newNode)){
						//      ，     
						tail.compareAndSet(curTail, tailNext);
						return true;
					}
				}
			}
		}
	}
}

원자의 도 메 인 업데이트 기:

private static class Node<E>{
		private final E item;
		private volatile Node<E> next; // volatile  
		
		public Node(E item){
			this.item = item;
		}
	}
	//   CAS    
	private static AtomicReferenceFieldUpdater<Node, Node> nextUpdater
		= AtomicReferenceFieldUpdater.newUpdater(Node.class, Node.class, "next");

ABA 문제:

ABA 문 제 는 일종 의 현상 이다. 만약 에 알고리즘 중의 노드 가 순환 적 으로 사용 된다 면 '비교 및 교환' 을 사용 할 때 이런 문제 가 발생 할 수 있다.일부 알고리즘 에서 V 의 값 은 A 에서 B 로 바 뀌 었 다가 B 에서 A 로 바 뀌 었 지만 여전히 변화 가 생 겼 다 고 여 겨 지고 알고리즘 중의 일부 절 차 를 다시 실행 해 야 한다.

AtomicStampedReference 나 AtomicMarkableReference 변 수 를 통 해 ABA 문 제 를 피 할 수 있 습 니 다.

아 낌 없 이 지적 하 다.