1. 소개
이 사용방법(예제)에서는 비차단 데이터 구조가 무엇이고 잠금 기반 동시 데이터 구조의 중요한 대안인 이유를 배웁니다.
먼저 방해 없는 , 잠금 없는 , 대기 없는 과 같은 용어를 살펴보겠습니다 .
둘째, CAS (비교 및 교환)와 같은 비차단 알고리즘의 기본 빌딩 블록을 살펴보겠습니다 .
세 번째로 Java에서 잠금이 없는 큐의 구현을 살펴보고 마지막으로 wait-freedom 을 달성하는 방법에 대한 개요를 설명합니다 .
2. 기아 대 잠금
먼저 차단된 스레드와 굶주린 스레드의 차이점을 살펴보겠습니다 .
위 그림에서 스레드 2는 데이터 구조에 대한 잠금을 획득합니다. 스레드 1도 잠금을 얻으려고 시도할 때 스레드 2가 잠금을 해제할 때까지 기다려야 합니다. 잠금을 얻기 전에 진행되지 않습니다. 잠금을 유지하는 동안 스레드 2를 일시 중단하면 스레드 1은 영원히 기다려야 합니다.
다음 그림은 스레드 기아 상태를 보여줍니다.
여기서 스레드 2는 데이터 구조에 액세스하지만 잠금을 획득하지 않습니다. 스레드 1은 동시에 데이터 구조에 액세스를 시도하고 동시 액세스를 감지하고 즉시 반환하여 작업을 완료할 수 없음(빨간색)을 스레드에 알립니다. 그런 다음 스레드 1은 작업을 완료하는 데 성공할 때까지 다시 시도합니다(녹색).
이 접근 방식의 장점은 잠금 장치가 필요하지 않다는 것입니다. 그러나 스레드 2(또는 다른 스레드)가 높은 빈도로 데이터 구조에 액세스하면 스레드 1이 마침내 성공할 때까지 많은 시도가 필요할 수 있습니다. 우리는 이것을 기아라고 부릅니다.
나중에 우리는 비교 및 교환 작업이 어떻게 비차단 액세스를 달성 하는지 볼 것 입니다.
3. 논블로킹 자료구조의 종류
우리는 세 가지 수준의 비차단 데이터 구조를 구별할 수 있습니다.
3.1. 방해물 없음
방해가 없는 것은 비차단 데이터 구조의 가장 약한 형태입니다. 여기에서는 다른 모든 스레드가 일시 중단된 경우에만 스레드가 계속 진행되도록 보장해야 합니다 .
보다 정확하게는 다른 모든 스레드가 일시 중단된 경우 스레드가 계속해서 기아 상태가 되지 않습니다. 이것은 스레드가 잠금을 기다리고 있고 잠금을 보유하고 있는 스레드가 일시 중단된 경우 대기 중인 스레드가 영원히 대기한다는 점에서 잠금을 사용하는 것과 다릅니다.
3.2. 잠금 해제
데이터 구조는 언제든지 적어도 하나의 스레드가 진행할 수 있는 경우 잠금 해제를 제공합니다 . 다른 모든 스레드가 부족할 수 있습니다. 방해가 없는 것과의 차이점은 중단된 스레드가 없더라도 적어도 하나의 비고유 스레드가 있다는 것입니다.
3.3. 대기 없음
데이터 구조는 잠금이 없고 모든 스레드가 유한한 수의 단계 후에 진행되도록 보장되는 경우 대기가 없는 것입니다.
3.4. 요약
그래픽 표현으로 이러한 정의를 요약해 보겠습니다.
이미지의 첫 번째 부분은 다른 스레드(하단에서 노란색)를 일시 중단하는 즉시 스레드 1(상단 스레드)이 진행할 수 있으므로(녹색 화살표) 장애물이 없는 것을 보여줍니다.
중간 부분은 잠금 해제를 보여줍니다. 다른 스레드가 굶어 죽을 수 있는 동안 적어도 스레드 1은 진행할 수 있습니다(빨간색 화살표).
마지막 부분은 대기 자유를 보여줍니다. 여기서 우리는 스레드 1이 특정 기간(빨간색 화살표)의 기아 상태(빨간색 화살표) 후에 계속될 수 있음을 보장합니다(녹색 화살표).
4. 논블로킹 프리미티브
이 섹션에서는 데이터 구조에 대한 잠금 없는 작업을 빌드하는 데 도움이 되는 세 가지 기본 작업을 살펴보겠습니다.
4.1. 비교 및 교환
잠금을 방지하는 데 사용되는 기본 작업 중 하나는 CAS( 비교 및 교환 ) 작업 입니다.
비교 및 교환의 개념은 변수가 주 메모리에서 변수 값을 가져왔을 때와 여전히 동일한 값을 갖는 경우에만 변수가 업데이트된다는 것입니다. CAS는 원자적 작업이므로 가져오기와 업데이트가 함께 하나의 단일 작업입니다 .
여기에서 두 스레드 모두 주 메모리에서 값 3을 가져옵니다. 스레드 2는 성공하고(녹색) 변수를 8로 업데이트합니다. 스레드 1의 첫 번째 CAS는 값이 여전히 3일 것으로 예상하므로 CAS는 실패합니다(빨간색). 따라서 스레드 1은 값을 다시 가져오고 두 번째 CAS는 성공합니다.
여기서 중요한 것은 CAS가 데이터 구조에 대한 잠금을 획득하지 않고 업데이트가 성공하면 true를 반환 하고 그렇지 않으면 false를 반환한다는 것 입니다.
다음 코드 스니펫은 CAS 작동 방식을 간략하게 보여줍니다.
volatile int value;
boolean cas(int expectedValue, int newValue) {
if(value == expectedValue) {
value = newValue;
return true;
}
return false;
}예상 값이 여전히 있는 경우에만 값을 새 값으로 업데이트하고, 그렇지 않으면 false 를 반환합니다 . 다음 코드 스니펫은 CAS를 호출하는 방법을 보여줍니다.
void testCas() {
int v = value;
int x = v + 1;
while(!cas(v, x)) {
v = value;
x = v + 1;
}
}CAS 작업이 성공할 때까지, 즉 true 를 반환할 때까지 값을 업데이트하려고 합니다 .
그러나 스레드가 기아 상태에 빠질 수 있습니다. 이는 다른 스레드가 동일한 변수에 대해 동시에 CAS를 수행하는 경우 발생할 수 있으므로 특정 스레드에 대해서는 작업이 성공하지 못합니다(또는 성공하는 데 무리한 시간이 소요됨). 그래도 비교 및 교환 이 실패하면 다른 스레드가 성공했다는 것을 알고 있으므로 잠금 해제에 필요한 글로벌 진행도 보장합니다.
잠금을 사용하지 않고 진정한 원자적 작업 이 되도록 하드웨어가 비교 및 교환을 지원해야 한다는 점에 유의하는 것이 중요합니다 .
Java는 sun.misc.Unsafe 클래스 에서 비교 및 교환 의 구현을 제공합니다 . 그러나 대부분의 경우 이 클래스를 직접 사용하지 않고 대신 Atomic 변수 를 사용해야 합니다.
또한 비교 및 교환 이 ABA 문제를 방지하지 못합니다. 다음 섹션에서 살펴보겠습니다.
4.2. 로드 링크/저장 조건부
비교 및 교환 의 대안 은 load-link/store-conditional 입니다. 먼저 compare-and-swap 을 다시 살펴보겠습니다 . 이전에 보았듯이 CAS는 주 메모리의 값이 여전히 우리가 기대하는 값인 경우에만 값을 업데이트합니다.
그러나 CAS는 값이 변경된 경우에도 성공하며 그 동안 이전 값으로 다시 변경되었습니다.
아래 이미지는 이러한 상황을 보여줍니다.
스레드 1과 스레드 2 모두 변수 값 3을 읽습니다. 그런 다음 스레드 2가 CAS를 수행하여 변수를 8로 설정하는 데 성공합니다. 그런 다음 다시 스레드 2가 CAS를 수행하여 변수를 다시 3으로 설정합니다. 그것도 성공합니다. 마지막으로, 쓰레드 1은 값 3을 기대하면서 CAS를 수행하고, 우리 변수의 값이 그 사이에 두 번 수정되었음에도 불구하고 역시 성공합니다.
이것을 ABA 문제라고 합니다. 물론 이 동작은 사용 사례에 따라 문제가 되지 않을 수도 있습니다. 그러나 다른 사람들에게는 원하지 않을 수 있습니다. Java는 AtomicStampedReference 클래스를 사용 하여 로드 링크/저장 조건 의 구현을 제공합니다 .
4.3. 가져오기 및 추가
또 다른 대안은 fetch-and-add 입니다. 이 연산은 주 메모리의 변수를 주어진 값만큼 증가시킵니다. 다시 말하지만 중요한 점은 작업이 원자적으로 발생한다는 것 입니다. 이는 다른 스레드가 간섭할 수 없음을 의미 합니다.
Java는 원자성 클래스에서 fetch-and-add 구현을 제공합니다 . 값을 증가시키고 새 값을 반환하는 AtomicInteger.incrementAndGet() 이 그 예입니다 . 및 AtomicInteger.getAndIncrement () 후 이전 값을 반환하고, 값을 증가시킨다.
5. 여러 스레드에서 연결된 대기열에 액세스
큐에 동시에 액세스하는 두 개(또는 그 이상) 스레드의 문제를 더 잘 이해하기 위해 연결된 큐와 요소를 동시에 추가하려는 두 개의 스레드를 살펴보겠습니다.
우리가 살펴볼 대기열은 이중으로 연결된 FIFO 대기열입니다. 여기서 마지막 요소(L) 뒤에 새 요소를 추가하고 마지막 요소에 대한 변수 꼬리 지점을 추가합니다.
새 요소를 추가하려면 스레드가 세 단계를 수행해야 합니다. 1) 다음 요소에 대한 포인터를 null로 설정하여 새 요소(N 및 M)를 생성합니다 . 2) 이전 요소에 대한 참조는 L을 가리키고 L의 다음 요소에 대한 참조는 N(각각 M)을 가리킵니다. 3) N(각각 M )에 대한 꼬리 지점을 가집니다.
두 스레드가 이 단계를 동시에 수행하면 무엇이 잘못될 수 있습니까? 위 그림의 단계가 ABCD 또는 ACBD 순서로 실행되면 tail 뿐만 아니라 L도 M을 가리킵니다. N은 대기열에서 연결이 끊긴 상태로 유지됩니다.
단계가 ACDB 순서로 실행되면 tail 은 N을 가리키고 L은 M을 가리키므로 대기열에서 불일치가 발생합니다.
물론 이 문제를 해결하는 한 가지 방법은 하나의 스레드가 큐에 대한 잠금을 획득하도록 하는 것입니다. 다음 장에서 살펴볼 솔루션은 앞에서 본 CAS 연산을 사용하여 잠금 해제 연산을 통해 문제를 해결할 것입니다.
6. 자바의 논블로킹 큐
Java의 기본 잠금 없는 큐를 살펴보겠습니다. 먼저 클래스 멤버와 생성자를 살펴보겠습니다.
public class NonBlockingQueue<T> {
private final AtomicReference<Node<T>> head, tail;
private final AtomicInteger size;
public NonBlockingQueue() {
head = new AtomicReference<>(null);
tail = new AtomicReference<>(null);
size = new AtomicInteger();
size.set(0);
}
}중요한 부분은 헤드 및 테일 참조를 AtomicReference 로 선언 하여 이러한 참조에 대한 모든 업데이트가 원자적 작업임을 보장하는 것 입니다. Java의 이 데이터 유형은 필요한 비교 및 교환 작업을 구현합니다 .
다음으로 Node 클래스의 구현을 살펴보겠습니다.
private class Node<T> {
private volatile T value;
private volatile Node<T> next;
private volatile Node<T> previous;
public Node(T value) {
this.value = value;
this.next = null;
}
// getters and setters
}여기서 중요한 부분은 이전 및 다음 노드에 대한 참조를 volatile 로 선언하는 것 입니다. 이렇게 하면 이러한 참조를 항상 주 메모리에서 업데이트할 수 있습니다(따라서 모든 스레드에서 직접 볼 수 있음). 실제 노드 값에 대해서도 동일합니다.
6.1. 잠금 해제 추가
잠금이 없는 추가 작업은 꼬리 부분에 새 요소를 추가하고 여러 스레드가 새 요소를 동시에 추가하려는 경우에도 대기열에서 연결이 끊기지 않도록 합니다.
public void add(T element) {
if (element == null) {
throw new NullPointerException();
}
Node<T> node = new Node<>(element);
Node<T> currentTail;
do {
currentTail = tail.get();
node.setPrevious(currentTail);
} while(!tail.compareAndSet(currentTail, node));
if(node.previous != null) {
node.previous.next = node;
}
head.compareAndSet(null, node); // for inserting the first element
size.incrementAndGet();
}주목해야 할 필수 부분은 강조 표시된 라인입니다. CAS 작업이 꼬리를 업데이트하는 데 성공할 때까지 대기열에 새 노드를 추가하려고 시도합니다. 꼬리는 여전히 새 노드를 추가한 꼬리와 동일해야 합니다.
6.2. 잠금 해제 가져오기
추가 작업과 유사하게 잠금 없는 get 작업은 마지막 요소를 반환하고 꼬리를 현재 위치로 이동하도록 합니다.
public T get() {
if(head.get() == null) {
throw new NoSuchElementException();
}
Node<T> currentHead;
Node<T> nextNode;
do {
currentHead = head.get();
nextNode = currentHead.getNext();
} while(!head.compareAndSet(currentHead, nextNode));
size.decrementAndGet();
return currentHead.getValue();
}다시 말하지만, 주목해야 할 핵심 부분은 강조 표시된 라인입니다. CAS 작업은 그 동안 다른 노드가 제거되지 않은 경우에만 현재 헤드를 이동하도록 합니다.
Java는 이미 비차단 큐의 구현인 ConcurrentLinkedQueue 를 제공 합니다. 이것은 이 백서에 설명된 M. Michael과 L. Scott의 잠금 없는 대기열 구현입니다 . 여기서 흥미로운 참고 사항은 Java 설명서에 대기 없는 대기열 이라고 명시되어 있으며 실제로는 잠금이 없는 상태라는 것 입니다. Java 8 문서는 구현 lock-free를 올바르게 호출합니다 .
7. 대기줄
우리가 보았듯이 위의 구현은 lock-free 이지만 wait-free가 아닙니다 . 대기열에 액세스하는 스레드가 많은 경우 add 및 get 메서드 의 while 루프 는 잠재적으로 오랜 시간 동안(또는 가능성은 없지만 영원히) 루프할 수 있습니다.
우리는 어떻게 기다림의 자유를 얻을 수 있습니까? 대기 없는 알고리즘의 구현은 일반적으로 상당히 까다롭습니다. 관심 있는 독자 는 대기 없는 대기열을 자세히 설명하는 이 문서 를 참조하십시오 . 이 기사에서는 queue 의 대기 없는 구현에 접근하는 방법에 대한 기본 아이디어를 살펴보겠습니다 .
대기 없는 대기열은 모든 스레드가 (유한한 수의 단계 후에) 진행을 보장해야 합니다. 즉, add 및 get 메소드 의 while 루프는 특정 단계 후에 성공해야 합니다.
이를 달성하기 위해 모든 스레드에 도우미 스레드를 할당합니다. 해당 도우미 스레드가 큐에 요소를 추가하는 데 성공하면 다른 스레드가 다른 요소를 삽입하기 전에 해당 요소를 삽입하는 데 도움이 됩니다.
도우미 스레드에는 도우미가 있고 전체 스레드 List 아래에는 모든 스레드에 도우미가 있으므로 모든 스레드가 한 번 삽입을 수행한 후 스레드가 가장 늦게 삽입에 성공하도록 보장할 수 있습니다. 다음 그림은 아이디어를 보여줍니다.
물론 스레드를 동적으로 추가하거나 제거할 수 있으면 상황이 더 복잡해집니다.
8. 결론
이 기사에서 우리는 비차단 데이터 구조의 기초를 보았습니다. 우리는 다른 수준과 비교 및 교환과 같은 기본 작업에 대해 설명했습니다 .
그런 다음 Java에서 잠금 없는 큐 의 기본 구현을 살펴보았습니다 . 마지막으로 wait-freedom 을 달성하는 방법에 대한 아이디어를 설명했습니다 .
