Lock-Free 알고리즘, 데이터 구조 및 기술

Lock-Free 프로그래밍

• 단일 하드웨어 명령어로 실행될 수 있게 보증하는 것을 말한다.
• 단일 하드웨어 명령어는 의미상 원자적이라 Thread-safe하다.
• 락을 이용했을 때 생기는 복잡성과 블로킹 상태에서 생기는 context switch 오버헤드를 없앨 수 있다.

AtomicPackage 

• AtomicInteger, AtomicBoolean, AtomicReference, 등등 있다.
• 각 클래스는 다양하면서 유용한 원자적 연산을 제공하여 아주 강력한 lock free 알고리즘과 데이터 구조를 디자인할 수 있다.
• 싱글 스레드에서는 오히려 성능이 더 떨어진다.

public static void main(String[] args) {
        int initialValue = 0 ;
        AtomicInteger atomicInteger = new AtomicInteger(initialValue);
        System.out.println(atomicInteger.getAndIncrement()); // 이전 값을 리턴하고 값 증가
        System.out.println(atomicInteger.incrementAndGet()); // 값을 증가하고 증가한 값을 리턴
        System.out.println(atomicInteger.getAndAdd(3)); // 이전 값 리턴하고 3 더하기
        System.out.println(atomicInteger.addAndGet(3)); // 3 더하고 이 값 리턴
}
//출력 : 0 2 2 8

 

CompareAndSet() : AtomicPackage로 생성한 변수에 들어있는 현재 값이 1번째 인자로 준 기대값과 같으면 2번째 인자로 준 새로운 값을 할당해준다. 아닐 시에는 아무 일도 없다.

public static void main(String[] args) {
    String oldName = "old name";
    String newName = "new name";
    AtomicReference<String> atomicReference = new AtomicReference<>(oldName);
    //atomicReference.set("hello"); 주석을 제거하면 change 출력된다.
    if(atomicReference.compareAndSet(oldName, newName)){
        System.out.println("change");
    }else{
        System.out.println("not change");
    }
}

 

Lock-Free Stack 예제

public static class LockFreeStack<T> {

    private final AtomicReference<StackNode<T>> head = new AtomicReference<>();
    private final AtomicInteger counter = new AtomicInteger(0)

    public void push(T value){
        StackNode<T> newHeadNode = new StackNode<>(value);
        //다른 스레드에서 이미 헤드를 변경하는 과정이 생길 수 있으므로 반복 작업 해야함
        while(true){
            StackNode<T> currentHeadNode = head.get();
            newHeadNode.next=currentHeadNode;
            if(head.compareAndSet(currentHeadNode,newHeadNode))
                break;
            else
                LockSupport.parkNanos(1);
        }
        counter.incrementAndGet();
    }

    public T pop(){
        StackNode<T> currentHeadNode = head.get();
        StackNode<T> newHeadNode;

        while(currentHeadNode!=null){
            newHeadNode = currentHeadNode.next;
            if(head.compareAndSet(currentHeadNode, newHeadNode)){
                break;
            }else {
                LockSupport.parkNanos(1);
                currentHeadNode = head.get();
            }
        }
        counter.decrementAndGet();
        return currentHeadNode != null ? currentHeadNode.value : null;
    }

    public int getCounter() {
        return counter.get();
    }
}

private static class StackNode<T> {
    public T value;
    public StackNode<T> next;

    public StackNode(T value){
        this.value=value;
    }
}