[JAVA] CAS 알고리즘이란?!

nick·2024년 4월 19일
0

JAVA

목록 보기
13/13

CAS가 뭐야?

  • Compare-And-Swap의 약어로, 멀티 쓰레드 환경에서 발생하는 동기화 문제를 해결하기 위한 알고리즘

- 현재 쓰레드에 저장된 값메인 메모리에 저장된 값을 비교해서 일치하는 경우, 새로운 값으로 교체하고, 일치하지 않으면 재시도 진행

  • 위 과정이 하드웨어적으로 atomic하게 구현되어야 함

CAS 목적

  • 결국 해당 변수에 대해서 동시에 딱 하나의 쓰레드만 값을 수정할 수 있게 함으로써 synchronized 또는 lock 을 사용하지 않고 동기화 문제(race condition)을 해결할 수 있다.

CAS 동작 방식

CAS 알고리즘을 위한 3가지 변수

  1. 바꾸려는 변수

  2. 바꾸려는 변수의 기댓값

  3. 업데이트 할 값

CAS 동작 방식

package java.util.concurrent.atomic;

public class AtomicInteger extends Number implements java.io.Serializable {

		private static final long VALUE = U.objectFieldOffset(AtomicInteger.class, "value");

    	private volatile int value;
    
    ...
    
		public final boolean compareAndSet(int expectedValue, int newValue) {
		    return U.compareAndSetInt(this, VALUE, expectedValue, newValue);
		}
}
package jdk.internal.misc;

public final class Unsafe {
		
		...
		
		@IntrinsicCandidate
		public final native boolean compareAndSetInt(Object o, long offset,
		                                             int expected,
		                                             int x);
                                           
}
  • AtomicInteger를 보면 valuevolatile로 선언된 것을 볼 수 있다.

    • 이로 인해, value의 값을 가져올 때는 바로 메인 메모리에서 읽어오고, 수정하게 되어도 메인 메모리에 바로 수정한다
    • 모든 thread가 해당 변수의 변경 사항을 즉각 확인할 수 있다 = 가시성이 보장된다
    • 동시성은 보장되지 않지만, CAS 연산 자체가 하드웨어적으로 atomic하게 진행되기에 동시성도 보장된다
  • Object o(AtomicInteger)의 값이 expected와 같다면 그 값을 x로 업데이트 해준다

    • compareAndSetInt의 과정을 atomic하게 처리해준다

❓ 뭘 어떻게 atomic하게 처리한다는거야?

  • public final native boolean compareAndSetInt(Object o, long offset, int expected, int x);

  • 이 메서드는 native 메서드이기에 JVM 내부 구현에 의해 직접 기계어 수준에서 실행된다는 의미다.

  • 그래서 이 메서드를 사용하면 하드웨어적으로 해당 메서드의 원자성을 보장해준다.

CAS 예시 코드

import java.util.concurrent.atomic.AtomicInteger;

public class CASExample {

    private static AtomicInteger counter = new AtomicInteger(0);

    public static void incrementCounter() {
        // 현재 값 가져오기
        int currentValue;
        int newValue;

        do {
            currentValue = counter.get(); // 현재 카운터 값 읽기
            newValue = currentValue + 1; // 새 값 계산
            
        } while (!counter.compareAndSet(currentValue, newValue));
        
    }

    public static void main(String[] args) throws InterruptedException {
        Thread t1 = new Thread(() -> {
            for (int i = 0; i < 1000; i++) {
                incrementCounter();
            }
        });

        Thread t2 = new Thread(() -> {
            for (int i = 0; i < 1000; i++) {
                incrementCounter();
            }
        });

        t1.start();
        t2.start();

        // 메인 스레드가 두 작업 스레드의 종료를 기다립니다.
        t1.join();
        t2.join();

        // 최종 카운터 값 출력
        System.out.println("Final counter value: " + counter.get());
    }
}

new AtomicInteger(0);

  • 인자로 넘어가는 값 0은 내부적으로 volatile 변수에 할당된다

  • 이후에 .get()을 통해 값을 가져올 때, CPU Cache가 아닌 메인 메모리에서 값을 읽어온다

  • 모든 스레드가 해당 값의 변경사항을 즉각적으로 볼 수 있음

do-while 문

  • 매 반복마다 메인 메모리에서 현재 값을 가져와서 (currentValue = counter.get();)

  • 업데이트 할 값 설정하고 (newValue = currentValue + 1;)

  • 가져온 값(currentValue)과 메인 메모리에 저장되어 있는 값(counter 객체 안에 저장되어 있는 값)을 비교해 같으면 newValue로 메모리에 저장되어 있는 값을 수정하고 while문을 빠져 나간다

  • 만약 두 값이 다르다면 counter.compareAndSet(currentValue, newValue)의 결과는 false과 되어 결국 while문을 빠져나가지 못하고 다시 반복된다.

  • 결국, 이 루프는 currentValuecounter의 값이 같아서 compareAndSet을 실행할 때까지 계속 반복된다

t1과 t2

  • t1 스레드와 t2 스레드가 do-while문을 통해 계속 compareAndSet 메서드를 성공시키려고 도전한다

  • 결국, 둘 중 누군가 하나는 더 빨리 compareAndSet 메서드를 먼저 수행해서 counter의 값과 currentValue 값을 맞춘다면 counter의 값은 newValue로 업데이트 된다

  • 직후에 들어온 스레드 입장에서는 counter의 값은 이미 1 증가되었고 내 currentValue 값과 다르기에 실패하고 다시 do-while문을 실행한다

CAS 장점

1. lock을 사용하지 않고 thread 간의 동기화를 가능

  • hardware적으로 compareAndSet(정확히 말하면 compareAndSetInt)을 원자적으로 실행되는 것을 보장해주기에 lock이 필요 없음

2. synchronized와 다르게 blocking이 아닌 nonblocking하면서 동기화 문제를 해결

  • non blocking이기에 CAS에서 while의 조건문에서 false를 받아도 thread가 waiting pool에 들어가지 않고, 계속 resource 얻기 위해 시도할 수 있다(무한 loop)

    • 또는 false 받았을 때, 다른 방법을 취할지 결정할 수 있다
  • 즉, 해당 resource 얻는 것을 실패했더라도 대기 상태로 들어가지 않는다

CAS 단점

busy waiting이라 무한 루프 돌면서 resource 얻을 때까지 계속 수행한다

  • 대기 시간이 짧으면 상관없는데 길어질 수록 많은 thread들이 CPU 자원을 낭비할 수 있다
  • 또한, 너무 많은 thread들이 동일한 데이터에 CAS 연산 시도하면, 성공 확률이 낮아져 성능이 저하된다

busy waiting과 blocking의 차이

  • blocking은 특정 조건이 충족될 때까지 “대기 상태”로 전환되어 스케쥴링되지 않는다

    • 즉, 이 thread는 아무것도 안하고 가만히 있음, 대신 cpu 리소스 소비하진 않음
  • busy waitingnonblocking 동작인데, 특정 조건이 충족될 때까지 계속 loop를 돌면서 조건을 체크한다

    • 이때 실행을 멈추는게 아니라 cpu에게 스케쥴링 되면서 계속 시도함
    • 얘도 사실상 다른 task 못하고 cpu 리소스까지 소비한다 (물론 다른 task 할수도 있음)
    • 하지만 blocking 처럼 context switching이 일어나지 않는다 (당연히 계속 실행중이니까)
    • 그래서 매우 짧은 대기 시간이 예상되거나 엄청 붐비지 않을 것으로 예상된다면 오버헤드를 줄일 수 있다
  • 결론 : 특정 조건을 충족될 때까지 멈추고 있냐(blocking), 멈추지 않고 계속 동작하냐(busy waiting)의 차이다

    • 둘 다 다른 task를 하지 못하는 점은 유사하다 (대신 busy waiting은 다른 task 하려고 빠져 나올 수 있는 자유?가 있다)
profile
티스토리로 이전 : https://andantej99.tistory.com/

0개의 댓글