섹션 11. CAS - 동기화와 원자적 연산 (3)

[seyeop03]

0x03. CAS 락 구현

3.1. CAS 락 구현1

CAS는 단순한 연산 뿐만 아니라, 락을 구현하는데 사용할 수도 있다.
synchronized, Lock(ReentrantLock) 없이 CAS를 활용해서 락을 구현해보자.
먼저 CAS의 필요성을 이해하기 위해 CAS 없이 직접 락을 구현해보자.

우선 코드를 먼저 작성하고 실행해보자.

package thread.cas.spinlock;

import static util.MyLogger.log;
import static util.ThreadUtils.sleep;

public class SpinLockBad {
		private volatile boolean lock = false;
		
		public void lock() {
				log("락 획득 시도");
				
				while(true) {
						if (!lock) { // 1. 락 사용 여부 확인
								sleep(100); // 문제 상황 확인용, 스레드 대기
								lock = true; // 2. 락의 값 변경
								break; // while 탈출
						} else {
								// 락을 획득할 때 까지 스핀 대기(바쁜 대기) 한다.
								log("락 획득 실패 - 스핀 대기");
						}
				}
				log("락 획득 완료");
		}
		
		public void unlock() {
				lock = false;
				log("락 반납 완료");
		}
		
}

구현 원리는 매우 단순하다.

• 스레드가 락을 획득하면 lock의 값이 true가 된다.

• 스레드가 락을 반납하면 lock의 값이 false가 된다.

• 스레드가 락을 획득하면 while문을 탈출한다.

• 스레드가 락을 획득하지 못하면 락을 획득할 때 까지 while문을 계속 반복 실행한다.

package thread.cas.spinlock;

import static util.MyLogger.log;
import static util.ThreadUtils.sleep;

public class SpinLockMain {
		public static void main(String[] args) {
				SpinLockBad spinLock = new SpinLockBad();
				
				Runnable task = new Runnable() {
						@Override
						public void run() {
								spinLock.lock();
								try {
										// critical section
										log("비즈니스 로직 실행");
										//sleep(1); // 오래 걸리는 로직에서 스핀 락 사용X
								} 
								finally {
										spinLock.unlock();
								}
						}
				};
				
				Thread t1 = new Thread(task, "Thread-1");
				Thread t2 = new Thread(task, "Thread-2");
				
				t1.start();
				t2.start();
		}
}

실행 결과

실행 결과를 보면 기대와는 다르게 Thread-1, Thread-2 둘다 동시에 락을 획득하고 비즈니스 로직을 동시에 수행해버린다.
이제는 왜 이런 문제가 발생하는지 이제는 쉽게 이해할 수 있을 것이다.

스레드 둘이 동시에 수행되기 때문에 문제가 발생했다. 실행 결과를 분석해보자.

public void lock() {
    log("락 획득 시도");
    while(true) {
        if (!lock) { // 1. 락 사용 여부 확인
            sleep(100); // 문제 상황 확인용, 스레드 대기
            lock = true; // 2. 락의 값 변경
            break; // while 탈출
        } else {
            // 락을 획득할 때 까지 스핀 대기(바쁜 대기) 한다.
            log("락 획득 실패 - 스핀 대기");
        }
    }
    log("락 획득 완료");
}

실행 결과 분석

lock의 초기값은 false이다.
Thread-1과 Thread-2는 동시에 실행된다.

• Thread-1: lock()을 호출해서 락 획득을 시도한다.

• Thread-2: lock()을 호출해서 락 획득을 시도한다.

• Thread-1: if (!lock)에서 락의 사용 여부를 확인한다. lock의 값이 false이다.

  • if (!lock) → if (!false) → if (true)이므로 if문을 통과한다.

• Thread-2: if (!lock)에서 락의 사용 여부를 확인한다. lock의 값이 false이다.

  • if (!lock) → if (!false) → if (true)이므로 if문을 통과한다.

• Thread-1: lock = true;를 호출해서 락의 값을 변경한다.

  • 이 시점에 lock은 false → true가 된다.

• Thread-2: lock = true;를 호출해서 락의 값을 변경한다.

  • 이 시점에 lock은 true → true가 된다.

• Thread-1, Thread-2 둘 다 break;를 통해 while문을 탈출한다.

• Thread-1, Thread-2 둘 다 락 획득을 완료하고, 비즈니스 로직을 수행한 다음에 락을 반납한다.

여기서 어떤 부분이 문제일까?
바로 다음 두 부분이 원자적이지 않다는 문제가 있다.

1. 락 사용 여부 확인
2. 락의 값 변경

이 둘은 한 번에 하나의 스레드만 실행해야 한다. 따라서 synchronized 또는 Lock을 사용해서 두 코드를 동기화해서 안전한 임계 영역을 만들어야 한다.

여기서 다른 해결 방안도 있다. 바로 두 코드를 하나로 묶어서 원자적으로 처리하는 것이다.
CAS 연산을 사용하면 두 연산을 하나로 묶어서 하나의 원자적인 연산으로 처리할 수 있다.
락의 사용 여부를 확인하고, 그 값이 기대하는 값과 같다면 변경하는 것이다. 이것은 CAS 연산에 딱 들어 맞는다!

참고로 락을 반납하는 다음 연산은 연산이 하나인 원자적인 연산이다. 따라서 이 부분은 여러 스레드가 함께 실행해도 문제가 발생하지 않는다.

public void unlock() {
		lock = false; //원자적인 연산
		log("락 반납 완료");
}

3.2. CAS 락 구현2

이번에는 CAS를 사용해서 락을 구현해보자.

package thread.cas.spinlock;

import java.util.concurrent.atomic.AtomicBoolean;
import static util.MyLogger.log;

public class SpinLock {

		private final AtomicBoolean lock = new AtomicBoolean(false);
		
		public void lock() {
				log("락 획득 시도");
				while (!lock.compareAndSet(false, true)) {
						// 락을 획득할 때 까지 스핀 대기(바쁜 대기) 한다.
		        log("락 획득 실패 - 스핀 대기");
		    }
		    log("락 획득 완료");
    }
    
    public void unlock() {
        lock.set(false);
        log("락 반납 완료");
    }
}

CAS 연산을 지원하는 AtomicBoolean을 사용했다.

구현 원리는 단순하다.

• 스레드가 락을 획득하면 lock의 값이 true가 된다.

• 스레드가 락을 반납하면 lock의 값이 false가 된다.

• 스레드가 락을 획득하면 while문을 탈출한다.

• 스레드가 락을 획득하지 못하면 락을 획득할 때까지 while문을 계속 반복 실행한다.

락을 획득할 때 매우 중요한 부분이 있다. 바로 다음 두 연산을 하나로 만들어야 한다는 점이다.

1. 락 사용 여부 확인
2. 락의 값 변경

락을 획득하기 위해 먼저 락의 사용 여부를 확인했을 때 lock의 현재 값이 반드시 false여야 한다. true는 이미 다른 스레드가 락을 획득했다는 뜻이다. 따라서 이 값이 false일 때만 락의 값을 변경할 수 있다.

락의 값이 false인 것을 확인한 시점부터 lock의 값을 true로 변경할 때까지 lock의 값은 반드시 false를 유지해야 한다.
중간에 다른 스레드가 lock의 값을 true로 변경하면 안 된다. 그러면 여러 스레드가 임계 영역을 통과하는 동시성 문제가 발생한다.

CAS 연산은 이 두 연산을 하나의 원자적인 연산으로 만들어준다.
lock.compareAndSet(false, true)

1. 락 사용 여부 확인: lock의 값이 false이면
2. 락의 값 변경: lock의 값을 true로 변경해라.

SpinLockMain - 코드 변경

package thread.cas.spinlock;

import static util.MyLogger.log;
import static util.ThreadUtils.sleep;

public class SpinLockMain {
		public static void main(String[] args) {
				//SpinLockBad spinLock = new SpinLockBad();
				SpinLock spinLock = new SpinLock();
				...
		}
		
}

• SpinLockBad 대신에 SpinLock을 사용하도록 코드를 변경하자.
• 참고로 예제를 단순화 하려고 인터페이스는 사용하지 않았다.

실행 결과

• 실행 결과는 환경에 따라 달라질 수 있다.

실행 결과를 보면 락이 잘 적용된 것을 확인할 수 있다.

실행 결과 분석

public void lock() {
		log("락 획득 시도");
		while (!lock.compareAndSet(false, true)) {
				// 락을 획득할 때 까지 스핀 대기(바쁜 대기) 한다.
				log("락 획득 실패 - 스핀 대기");
		}
		log("락 획득 완료");
}

Thread-1 로그

Thread-2 로그

lock의 초기값은 false이다.

• Thread-1: lock()을 호출해서 락 획득을 시도한다.
• Thread-2: lock()을 호출해서 락 획득을 시도한다.
• Thread-1: while (!lock.compareAndSet(false, true))를 사용해서 락의 사용 여부를 확인하면서 변경을 시도한다.
  • lock.compareAndSet(false, true)
    • CAS 연산을 사용했다. lock이 false면 lock의 값을 true로 변경한다.
    • lock의 값이 false이므로 true로 변경한다. 변경에 성공했기 때문에 true를 반환한다.
  • while (!true) → while(false)가 되므로 while문을 빠져나온다.
  • 락 획득을 완료한다.
• Thread-2: while (!lock.compareAndSet(false, true))를 사용해서 락의 사용 여부를 확인하면서 변경을 시도한다.
  • lock.compareAndSet(false, true)
    • CAS 연산을 사용했다. lock이 false면 lock의 값을 true로 변경한다.
    • lock의 값이 true이므로 값을 변경할 수 없다. 변경에 실패했기 때문에 false를 반환한다.
  • while (!false) → while(true)가 되므로 while문을 시작한다.
  • 락 획득에 실패하고, 락을 획득할 때까지 while문을 반복한다.
    • 락 획득 실패 - 스핀 대기 로그가 반복해서 남는다.
• Thread-1: 비즈니스 로직을 수행하고 lock.set(false)를 수행해서 락을 반납한다.
• Thread-2: 락을 획득하고 while문을 탈출한다. 비즈니스 로직을 수행한 다음에 락을 반납한다.

기존 코드와 비교

기존 코드는 바로 다음 두 부분이 원자적이지 않다는 문제가 있었다.

1. 락 사용 여부 확인
2. 락의 값 변경

while(
		if (!lock) { //1. 락 사용 여부 확인
				lock = true; //2. 락의 값 변경
		}
)

이 문제를 CAS 연산을 통해서 원자적으로 바꾸었다.

while(lock.compareAndSet(false, true)) {}

CAS 연산 덕분에 원자적이지 않은 두 연산을 다음과 같이 하나의 원자적인 연산으로 바꿀 수 있었다.

1. 락을 사용하지 않는다면 락의 값을 변경

원자적인 연산은 스레드 입장에서 쪼갤 수 없는 하나의 연산이다. 따라서 여러 스레드가 동시에 실행해도 안전하다. 이렇게 CAS를 사용해서 원자적인 연산을 만든 덕분에 무거운 동기화 작업 없이 아주 가벼운 락을 만들 수 있었다. 동기화 락을 사용하는 경우 스레드가 락을 획득하지 못하면 BLOCKED, WAITING 등으로 상태가 변한다. 그리고 또 대기 상태의 스레드를 깨워야 하는 무겁고 복잡한 과정이 추가로 들어간다. 따라서 성능이 상대적으로 느릴 수 있다. 반면에 CAS를 활용한 락 방식은 사실 락이 없다. 단순히 while문을 반복할 뿐이다. 따라서 대기하는 스레드도 RUNNABLE 상태를 유지하면서 가볍고 빠르게 작동할 수 있다.

(1) CAS 단점

하지만 이렇게 반복문과 CAS를 사용해서 락을 대체하는 방식에도 단점이 있다.

SpinLockMain 코드에 있는 sleep(1) 주석을 풀고 실행해보자.

public void run() {
		spinLock.lock();
		try {
				// critical section
				log("비즈니스 로직 실행");
				sleep(1); // 오래 걸리는 로직에서 스핀 락 사용X
		} 
		finally {
				spinLock.unlock();
		}
}

실행 결과

이 방식은 락을 기다리는 스레드가 BLOCKED, WAITING 상태로 빠지지는 않지만, RUNNABLE 상태로 락을 획득할 때까지 while문을 반복하는 문제가 있다. 따라서 락을 기다리는 스레드가 CPU를 계속 사용하면서 대기하는 것이다! BLOCKED, WAITING 상태의 스레드는 CPU를 거의 사용하지 않지만, RUNNABLE 상태로 while문을 반복 실행하는 방식은 CPU 자원을 계속해서 사용하는 것이다.

동기화 락을 사용하면 RUNNABLE 상태의 스레드가 BLOCKED, WAITING 상태에서 다시 RUNNABLE 상태로 이동한다. 이 사이에 CPU 자원을 거의 사용하지 않을 수 있다.
그래서 동기화 락을 사용하는 방식보다 스레드를 RUNNABLE로 살려둔 상태에서 계속 락 획득을 반복 체크하는 것이 더 효율적인 경우에 이런 방식을 사용해야 한다. 이 방식은 스레드의 상태가 변경되지 않기 때문에 매우 빠르게 락을 획득하고, 또 바로 실행할 수 있는 장점이 있다.

그럼 어떤 경우에 이런 방식이 효율적일까?
안전한 임계 영역이 필요하지만, 연산이 길지 않고 매우매우매우! 짧게 끝날 때 사용해야 한다.
예를 들어 숫자 값의 증가, 자료 구조의 데이터 추가와 같이 CPU 사이클이 금방 끝나는 연산에 사용하면 효과적이다.
반면에 데이터베이스의 결과를 대기한다거나, 다른 서버의 요청을 기다린다거나 하는 것 처럼 오래 기다리는 작업에 사용하면 CPU를 계속 사용하며 기다리는 최악의 결과가 나올 수도 있다.

스핀 락

스레드가 락이 해제되기를 기다리면서 반복문을 통해 계속해서 확인하는 모습이 마치 제자리에서 회전(spin)하는 것처럼 보인다. 그래서 이런 방식을 "스핀 락"이라고도 부른다. 그리고 이런 방식에서 스레드가 락을 획득 할 때 까지 대기하는 것을 스핀 대기(spin-wait) 또는 CPU 자원을 계속 사용하면서 바쁘게 대기한다고 해서 바쁜 대기(busy-wait)라 한다.
이런 스핀 락 방식은 아주 짧은 CPU 연산을 수행할 때 사용해야 효율적이다. 잘못 사용하면 오히려 CPU 자원을 더 많이 사용할 수 있다.
정리하면 "스핀 락"이라는 용어는, 락을 획득하기 위해 자원을 소모하면서 반복적으로 확인(스핀)하는 락 메커니즘을 의미한다. 그리고 이런 스핀 락은 CAS를 사용해서 구현할 수 있다.

0x04. 정리

4.1. 락 VS CAS 사용 방식

동기화 락(synchronized, Lock(ReentrantLock))을 사용하는 방식과 CAS를 활용하는 락 프리 방식의 장단
점을 비교해보자.

CAS의 장점

1. 낙관적 동기화: 락을 걸지 않고도 값을 안전하게 업데이트할 수 있다. CAS는 충돌이 자주 발생하지 않을 것이라고 가정한다. 이는 충돌이 적은 환경에서 높은 성능을 발휘한다.
2. 락 프리(Lock-Free): CAS는 락을 사용하지 않기 때문에, 락을 획득하기 위해 대기하는 시간이 없다. 따라서 스레드가 블로킹되지 않으며, 병렬 처리가 더 효율적일 수 있다.

CAS의 단점

1. 충돌이 빈번한 경우: 여러 스레드가 동시에 동일한 변수에 접근하여 업데이트를 시도할 때 충돌이 발생할 수 있다. 충돌이 발생하면 CAS는 루프를 돌며 재시도해야 하며, 이에 따라 CPU 자원을 계속 소모할 수 있다. 반복적인 재시도로 인해 오버헤드가 발생할 수 있다.
2. 스핀락과 유사한 오버헤드: CAS는 충돌 시 반복적인 재시도를 하므로, 이 과정이 계속 반복되면 스핀락과 유사한 성능 저하가 발생할 수 있다. 특히 충돌 빈도가 높을수록 이런 현상이 두드러진다.

동기화 락의 장점

1. 충돌 관리: 락을 사용하면 하나의 스레드만 리소스에 접근할 수 있으므로 충돌이 발생하지 않는다. 여러 스레드가 경쟁할 경우에도 안정적으로 동작한다.
2. 안정성: 복잡한 상황에서도 락은 일관성 있는 동작을 보장한다.
3. 스레드 대기: 락을 대기하는 스레드는 CPU를 거의 사용하지 않는다.

동기화 락의 단점

1. 락 획득 대기 시간: 스레드가 락을 획득하기 위해 대기해야 하므로, 대기 시간이 길어질 수 있다.
2. 컨텍스트 스위칭 오버헤드: 락을 사용하면, 락 획득을 대기하는 시점과 또 락을 획득하는 시점에 스레드의 상태가 변경된다. 이때 컨텍스트 스위칭이 발생할 수 있으며, 이로 인해 오버헤드가 증가할 수 있다.

결론

일반적으로 동기화 락을 사용하고, 아주 특별한 경우에 한정해서 CAS를 사용해서 최적화해야 한다.
CAS를 통한 최적화가 더 나은 경우는 스레드가 RUNNABLE → BLOCKED, WAITING 상태에서 다시 RUNNABLE 상태태로 가는 것 보다는, 스레드를 RUNNABLE로 살려둔 상태에서 계속 락 획득을 반복 체크하는 것이 더 효율적인 경우에 사용해야 한다. 하지만 이 경우 대기하는 스레드가 CPU 자원을 계속 소모하기 때문에 대기 시간이 아주아주아주 짧아야 한다. 따라서 임계 영역이 필요는 하지만, 연산이 길지 않고 매우매우매우! 짧게 끝날 때 사용해야 한다.
예를 들어 숫자 값의 증가, 자료 구조의 데이터 추가, 삭제와 같이 CPU 사이클이 금방 끝나지만 안전한 임계 영역, 또는 원자적인 연산이 필요한 경우에 사용해야 한다.

반면에 데이터베이스를 기다린다거나, 다른 서버의 요청을 기다리는 것 처럼 오래 기다리는 작업에 CAS를 사용하면 CPU를 계속 사용하며 기다리는 최악의 결과가 나올 수도 있다. 이런 경우에는 동기화 락을 사용해야 한다.

또한 CAS는 충돌 가능성이 낮은 환경에서 매우 효율적이지만, 충돌 가능성이 높은 환경에서는 성능 저하가 발생할 수 있다. 이런 경우에는 상황에 맞는 적절한 동기화 전략을 사용하는 것이 중요하다. 때로는 락이 더 나은 성능을 발휘할 수 있으며, CAS가 항상 더 빠르다고 단정할 수는 없다. 따라서, 각 접근 방식의 특성을 이해하고, 애플리케이션의 특정 요구사항과 환경에 맞는 방식을 선택하는 것이 필요하다.

실무 관점

실무 관점에서 보면 대부분의 애플리케이션들은 공유 자원을 사용할 때, 충돌할 가능성 보다 충돌하지 않을 가능성이 훨씬 높다. 예를 들어서 여러 스레드에서 발생하는 주문 수를 실시간으로 증가하면서 카운트 한다고 가정해보자. 그리고 특정 피크시간에 주문이 100만건 들어오는 서비스라고 가정해보자.

• 1,000,000 / 60분 = 1분에 16,666건, 1초에 277건

CPU가 1초에 얼마나 많은 연산을 처리하는지 생각해보면, 백만 건 중에 충돌이 나는 경우는 아주 넉넉하게 해도 몇 십건 이하일 것이다. 따라서 실무에서는 주문 수 증가와 같은 단순한 연산의 경우, 락을 걸고 시작하는 것 보다는, CAS처럼 낙관적인 방식이 더 나은 성능을 보인다.

그런데 여기서 중요한 핵심은 주문 수 증가와 같은 단순한 연산이라는 점이다. 이런 경우에는 AtomicInteger와 같은 CAS 연산을 사용하는 방식이 효과적이다. 이런 연산은 나노 초 단위로 발생하는 연산이다.
반면에 데이터베이스를 기다린다거나, 다른 서버의 요청을 기다리는 것 처럼 수 밀리초 이상의 시간이 걸리는 작업이라면 CAS를 사용하는 것 보다 동기화 락을 사용하거나 스레드가 대기하는 방식이 더 효과적이다.

우리가 사용하는 많은 자바 동시성 라이브러리들, 동기화 컬렉션들은 성능 최적화를 위해 CAS 연산을 적극 활용한다. 덕분에 실무에서 직접 CAS 연산을 사용하는 사용하는 일은 매우 드물다. 대신에 CAS 연산을 사용해서 최적화 되어 있는 라이브러리들을 이해하고 편리하게 사용할 줄 알면 충분하다.

CAS의 개념을 알아두면 앞으로 멀티스레드와 관련된 다양한 라이브러리들을 분석할 때, "아~ 이 부분은 CAS를 사용해서 최적화 했구나"라는 점을 이해할 수 있을 것이다.

참고: CAS 연산은 심화 내용이다. 이해가 어렵다면 가볍게 듣고 넘어가도 괜찮다. 왜냐하면 우리가 직접 CAS 연산을 사용하는 경우는 거의 없기 때문이다. 대부분 복잡한 동시성 라이브러리들이 CAS 연산을 사용한다. 우리는 AtomicInteger와 같은 CAS 연산을 사용하는 라이브러리들을 잘 사용하는 정도면 충분하다.