CAS로 스핀 락 만들기

앞 글에서는 CAS로 숫자 하나를 안전하게 바꿨습니다. 같은 CAS로 락도 만들 수 있습니다. 락의 핵심은 '아무도 잠그지 않았으면 내가 잠근다'인데, 이것은 false를 true로 바꾸는 CAS 한 번과 같기 때문입니다. 19장에서는 synchronized와 ReentrantLock을 이미 만들어진 도구로 썼습니다. 이 글에서는 간단한 락을 직접 만들어 보면서 락이 안에서 무엇을 하는지 살펴봅니다.

직접 만든 락은 원리를 배우는 데는 좋지만, 실제 프로그램에서 표준 락 대신 쓸 만한 것은 아닙니다. 글 후반에서 그 이유도 함께 정리합니다. 실행 결과는 앞 글과 같은 코어 2개짜리 컴퓨터에서 JDK 21로 얻었습니다.

volatile 플래그로 만든 락에 두 스레드가 함께 들어온다

가장 먼저 떠오르는 방법은 boolean 플래그 하나로 락을 표현하는 것입니다. 다음 lock()은 locked가 true인 동안 반복하며 기다리다가, false가 되면 반복을 빠져나와 true로 바꿉니다. unlock()은 false로 되돌립니다. 다른 스레드의 쓰기가 보이도록 locked는 volatile로 선언했습니다. 두 스레드가 이 락을 잡은 상태에서 일반 필드 entrants를 10만 번씩 늘리므로, 락이 제대로 동작한다면 20만이 출력되어야 합니다.

public final class CheckThenSetLock {
    private volatile boolean locked;
    private int entrants;

    void lock() {
        while (locked) {
            Thread.onSpinWait();
        }
        locked = true;
    }
    void unlock() { locked = false; }

    public static void main(String[] args) throws InterruptedException {
        CheckThenSetLock lock = new CheckThenSetLock();
        Runnable task = () -> {
            for (int i = 0; i < 100_000; i++) {
                lock.lock();
                lock.entrants++;
                lock.unlock();
            }
        };
        Thread a = Thread.ofPlatform().start(task);
        Thread b = Thread.ofPlatform().start(task);
        a.join(); b.join();
        System.out.println("expected=200000 actual=" + lock.entrants);
    }
}

이 프로그램을 30번씩 두 차례 실행했습니다. 첫 30번 가운데 28번, 다음 30번 가운데 7번이 20만보다 작은 값을 출력했고, 가장 작은 값은 179,781이었습니다. 같은 컴퓨터에서도 실행할 때마다, 또 묶음마다 결과가 크게 달랐습니다. 다음은 그중 한 번의 출력입니다.

expected=200000 actual=197962

entrants++에서 증가가 사라졌다는 것은 두 스레드가 같은 순간에 락 안에 있었다는 뜻입니다. 락이 한 번에 한 스레드만 들여보냈다면 entrants++가 겹칠 일이 없습니다. 두 스레드가 함께 들어오는 순서는 다음과 같습니다.

T2는 2번 순서에서 이미 검사를 통과했으므로, 3번에서 T1이 true를 써도 되돌아가지 않습니다. 결국 두 스레드 모두 lock()에서 반환해 함께 entrants++를 실행할 수 있고, 그러면 21장 첫 글에서 본 갱신 손실이 생깁니다. 그림 속 실행에서는 20만 대신 195,755가 출력되었습니다. 이 표도 매번 일어나는 순서가 아니라 일어날 수 있는 순서의 한 예입니다. 20만이 나온 실행이 있었다고 해서 이 락이 상호 배제를 지킨다는 뜻은 아닙니다.

원인은 volatile int에 value++를 했을 때와 같습니다. locked의 읽기와 쓰기는 각각 다른 스레드에 보이지만, while에서 하는 검사와 그 뒤의 쓰기는 별개의 동작입니다. 상태를 확인하고 그 결과에 따라 행동하는 사이에 다른 스레드가 끼어드는 이런 문제를 검사 후 행동(check-then-act) 경쟁이라고 합니다. 앞 글에서 본 대로, 이런 틈은 검사와 변경을 CAS 하나로 합쳐서 없앱니다.

CAS로 검사와 잠금을 한 번에

locked를 AtomicBoolean으로 바꾸고, lock()의 검사와 쓰기를 compareAndSet(false, true) 하나로 합칩니다. 파일 맨 위에 import java.util.concurrent.atomic.AtomicBoolean;을 추가하고, main과 entrants는 그대로 둡니다.

private final AtomicBoolean locked = new AtomicBoolean();

void lock() {
    while (!locked.compareAndSet(false, true)) {
        Thread.onSpinWait();
    }
}
void unlock() { locked.set(false); }

이렇게 바꾼 프로그램을 30번 실행했더니 30번 모두 expected=200000 actual=200000이 출력되었습니다. 이번에는 우연이 아닙니다. 두 스레드가 동시에 false를 보더라도, false를 true로 바꾸는 CAS는 둘 중 하나만 성공합니다. 진 스레드의 CAS는 이미 true인 값을 보고 실패하므로, 반복하며 다시 시도합니다. 락을 가진 스레드가 unlock()에서 false를 써야 비로소 다음 CAS가 성공할 수 있습니다.

이처럼 락을 얻지 못한 스레드가 잠들지 않고 반복문을 돌며 계속 시도하는 락을 스핀 락(spin lock)이라고 합니다. 제자리에서 빙빙 돈다(spin)는 뜻입니다. 반면 synchronized와 ReentrantLock은 락을 얻지 못한 스레드를 대기 상태로 만들어 CPU를 내놓게 하고, 락이 풀리면 깨웁니다. ReentrantLock이 스레드를 재우고 깨울 때 쓰는 것이 park와 unpark를 다룬 글에서 본 LockSupport.park()와 unpark()입니다.

더 깊이: 일반 필드인 entrants가 다음 스레드에 보이는 이유

entrants는 volatile도 원자 변수도 아닌 일반 필드인데, 락을 고친 프로그램은 언제나 20만을 출력합니다. 한 스레드가 늘린 값이 다음에 락을 잡은 스레드에게 보이기 때문입니다. 이것도 첫 글에서 본 happens-before 연결로 설명할 수 있습니다. T1 안에서 entrants++는 unlock()의 locked.set(false)보다 먼저 일어납니다. set()은 volatile 쓰기와 같은 효과를 내고, compareAndSet()은 volatile 읽기와 쓰기를 함께 한 것과 같은 효과를 냅니다. 그래서 T1의 set(false)는 그 false를 보고 성공한 T2의 CAS보다 먼저 일어나고, 그 CAS는 T2의 entrants++보다 먼저 일어납니다. 연결을 따라가면 T1의 증가는 T2가 entrants를 읽기 전에 일어난 것이 됩니다. 락이 하는 일은 이렇게 두 가지입니다. 한 번에 한 스레드만 들여보내는 상호 배제와, 앞 스레드가 쓴 값을 다음 스레드가 보게 하는 가시성입니다. 고치기 전의 락은 volatile 덕분에 가시성은 있었지만 상호 배제가 없었습니다.

학습용 스핀 락에 소유자 확인 더하기

방금 만든 락은 동작하지만 쉽게 잘못 쓸 수 있습니다. 첫째, unlock()이 호출한 스레드를 확인하지 않습니다. 락을 갖지 않은 스레드가 실수로 unlock()을 호출하면 다른 스레드가 쥐고 있던 락이 풀리고, 세 번째 스레드가 그 틈에 들어올 수 있습니다. 둘째, 락을 가진 스레드가 lock()을 다시 호출하면 자기 자신이 락을 풀어 주기를 기다리며 끝없이 돕니다. 실제로 이렇게 두 번 lock()을 호출하는 스레드를 만들어 보니, 1초 뒤에도 그 스레드는 RUNNABLE 상태로 계속 돌고 있었습니다. 셋째, 락 안에서 예외가 나서 unlock()을 건너뛰면, 기다리던 스레드들은 영원히 돕니다.

다음 OwnedSpinLock은 앞의 두 문제를 직접 막습니다. 세 번째 문제는 락을 쓰는 쪽이 try/finally로 막습니다.

import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.atomic.AtomicReference;

public final class OwnedSpinLock {
    private final AtomicBoolean locked = new AtomicBoolean();
    private final AtomicReference<Thread> owner = new AtomicReference<>();

    void lock() {
        Thread current = Thread.currentThread();
        if (owner.get() == current) throw new IllegalStateException("not reentrant");
        while (!locked.compareAndSet(false, true)) {
            Thread.onSpinWait();
        }
        owner.set(current);
    }

    void unlock() {
        Thread current = Thread.currentThread();
        if (!owner.compareAndSet(current, null)) {
            throw new IllegalMonitorStateException("not owner");
        }
        locked.set(false);
    }

    public static void main(String[] args) throws InterruptedException {
        OwnedSpinLock lock = new OwnedSpinLock();
        int[] counter = {0};
        Runnable task = () -> {
            for (int i = 0; i < 50_000; i++) {
                lock.lock();
                try { counter[0]++; }
                finally { lock.unlock(); }
            }
        };
        Thread a = Thread.ofPlatform().start(task);
        Thread b = Thread.ofPlatform().start(task);
        a.join(); b.join();
        System.out.println("counter=" + counter[0]);
    }
}

owner는 지금 락을 가진 스레드를 기록합니다. lock()은 먼저 owner가 자기 자신인지 확인해, 이미 락을 가진 스레드가 다시 들어오려 하면 끝없이 도는 대신 IllegalStateException을 던집니다. 그다음 CAS로 락을 얻고, 얻은 뒤에 owner에 자기 자신을 적습니다. unlock()은 owner.compareAndSet(current, null)로 '내가 소유자일 때만 소유자를 지운다'를 한 번에 처리합니다. 소유자가 아니면 CAS가 실패하고 IllegalMonitorStateException을 던지므로, 남의 락을 푸는 일이 생기지 않습니다. ReentrantLock의 unlock()도 락을 갖지 않은 스레드가 호출하면 같은 예외를 던집니다.

main은 두 스레드가 5만 번씩 counter[0]을 늘리고, 해제를 finally에 두어 예외가 나도 락이 풀리게 합니다. 20번 실행해 20번 모두 같은 결과가 나왔습니다.

counter=100000

main은 예외가 나는 경우를 실행하지 않으므로, 두 예외를 확인하는 코드를 따로 실행해 보았습니다. main 스레드가 락을 잡은 채 lock()을 한 번 더 호출하고, 다른 스레드가 그 락을 unlock()하려고 시도한 뒤, 마지막으로 main이 직접 풉니다.

public final class OwnedSpinLockErrors {
    public static void main(String[] args) throws Exception {
        OwnedSpinLock lock = new OwnedSpinLock();
        lock.lock();
        try {
            lock.lock();
        } catch (IllegalStateException e) {
            System.out.println("reentry: " + e);
        }
        Thread other = Thread.ofPlatform().start(() -> {
            try {
                lock.unlock();
            } catch (IllegalMonitorStateException e) {
                System.out.println("non-owner: " + e);
            }
        });
        other.join();
        lock.unlock();
        System.out.println("released by owner");
    }
}

이 클래스는 같은 폴더의 OwnedSpinLock을 사용하므로 두 파일을 함께 컴파일해야 합니다. 실행 결과의 앞 두 줄은 각 catch가 잡은 예외를 출력한 것이고, 마지막 줄은 소유자인 main이 락을 정상적으로 푼 뒤에 출력한 것입니다.

reentry: java.lang.IllegalStateException: not reentrant
non-owner: java.lang.IllegalMonitorStateException: not owner
released by owner

그림은 락을 얻고 푸는 동안 두 필드가 어떻게 바뀌는지 순서대로 보여 줍니다. CAS에 성공한 직후에는 locked가 true인데 owner는 아직 null입니다. 이 틈에 다른 스레드가 unlock()을 호출해도 owner가 그 스레드가 아니므로 예외가 납니다. 해제할 때는 owner를 먼저 지우고 locked를 나중에 풉니다. owner를 지운 것만으로는 아직 다른 스레드가 락을 얻을 수 없고, locked.set(false)가 실행되어야 다음 CAS가 성공합니다. 첫 글에서 본 것처럼 원자 변수 두 개는 한 쌍으로 읽히지 않으므로, 다른 스레드가 두 필드를 읽으면 이런 중간 상태를 볼 수 있습니다. 이 락은 그 점을 감안해, 락을 얻을 수 있는지는 locked 하나로만 판단합니다. owner는 소유자 자신이 다시 들어오는지와 소유자가 아닌 스레드가 풀려고 하는지를 확인하는 데만 씁니다.

그래도 이 락은 학습용입니다. 락을 기다리는 동안 시간 제한이 없고, 인터럽트에도 반응하지 않습니다. 먼저 기다린 스레드가 먼저 얻는다는 공정성도 없고, Condition처럼 조건을 기다리는 기능도 없습니다. ReentrantLock은 이 기능을 모두 제공하면서, 오래 기다려야 하는 스레드는 재워서 CPU를 거의 쓰지 않게 합니다.

기다리는 시간에 한도 두기

스핀 락의 lock()은 락을 얻을 때까지 끝없이 돕니다. 락을 가진 스레드가 오래 놓지 않으면 기다리는 스레드는 그동안 CPU를 계속 씁니다. 다음 프로그램은 정해진 시간 동안만 시도하고 포기하는 tryLockUntil()을 만들어, 이미 잠긴 락을 2밀리초 동안 시도하면 어떻게 되는지 봅니다.

import java.time.Duration;
import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.atomic.LongAdder;

public final class SpinBudgetProbe {
    private final AtomicBoolean gate = new AtomicBoolean();
    private final LongAdder failedAttempts = new LongAdder();

    boolean tryLockUntil(Duration budget) {
        long deadline = System.nanoTime() + budget.toNanos();
        do {
            if (gate.compareAndSet(false, true)) return true;
            failedAttempts.increment();
            Thread.onSpinWait();
        } while (deadline - System.nanoTime() > 0);
        return false;
    }

    void unlock() { gate.set(false); }

    public static void main(String[] args) throws InterruptedException {
        SpinBudgetProbe probe = new SpinBudgetProbe();
        probe.gate.set(true);
        Thread contender = Thread.ofPlatform().start(() ->
                System.out.println("acquired=" + probe.tryLockUntil(Duration.ofMillis(2))));
        contender.join();
        probe.unlock();
        System.out.println("failedAttempts=" + probe.failedAttempts.sum());
    }
}

main은 경쟁 스레드를 시작하기 전에 gate를 true로 만들어, 다른 누군가가 락을 쥐고 있는 상황을 흉내 냅니다. 경쟁 스레드는 2밀리초 동안 CAS를 반복하고, 실패할 때마다 failedAttempts를 1 늘립니다. do-while이므로 시간을 확인하기 전에 적어도 한 번은 시도합니다. main은 경쟁 스레드가 끝날 때까지 join()으로 기다린 뒤에야 gate를 풉니다.

반복 조건이 System.nanoTime() < deadline이 아니라 deadline - System.nanoTime() > 0인 데는 이유가 있습니다. System.nanoTime()의 값은 임의의 기준 시각에서 잰 나노초라서, 매우 큰 값이나 음수일 수도 있습니다. 그래서 nanoTime() + 예산을 계산할 때 long 범위를 넘어 값이 음수로 바뀔 수 있고, 그러면 두 시각을 그대로 비교한 결과가 틀어집니다. System.nanoTime() 공식 문서도 이 때문에 두 값을 직접 비교하지 말고 차이를 계산해 비교하라고 안내합니다. 차이는 넘침이 일어나도 올바르게 계산되기 때문입니다.

30번 실행했더니 30번 모두 첫 줄은 acquired=false였고, failedAttempts는 96부터 1,773까지 실행마다 크게 달랐습니다. 다음은 그중 한 번의 출력입니다.

acquired=false
failedAttempts=1024

첫 줄이 언제나 false인 이유는 프로그램의 순서에 있습니다. main은 경쟁 스레드가 결과를 정하고 끝난 뒤에야 gate를 풀므로, 경쟁 스레드가 시도하는 동안 gate는 줄곧 true입니다. 둘째 줄의 실패 횟수는 2밀리초 동안 반복문이 몇 번 돌았는지를 보여 줄 뿐, 시간이나 CPU 사용량을 잰 값이 아닙니다. 반복 한 번에 걸리는 시간은 CPU, JIT 컴파일 여부, 그 순간 스레드가 실제로 실행되고 있었는지에 따라 달라집니다. 첫 시도 직후 스레드가 잠시 실행되지 못하면, 시간을 처음 확인했을 때 이미 2밀리초가 지나 있어 failedAttempts=1로 끝날 수도 있습니다. 같은 이유로 2밀리초는 메서드가 반환하기까지 걸리는 시간의 상한도 아닙니다. 시간 확인을 통과해 반복을 한 번 더 시작한 직후에 스레드가 잠시 실행되지 못하면, 반환은 그만큼 늦어집니다.

그림은 gate를 먼저 잠근 뒤, 경쟁 스레드가 반복해서 실패하다가 false를 반환하고, join()이 끝난 뒤에야 gate가 풀리는 순서를 보여 줍니다. 그림 속 실행에서는 실패 횟수가 1,863번이었습니다.

실제 프로그램에서 시간 제한이 있는 락이 필요하다면 이 탐침 대신 ReentrantLock의 tryLock(시간, 단위)를 씁니다. 기다리는 동안 스레드를 재우므로 CPU를 거의 쓰지 않고, 기다리는 중에 인터럽트되면 InterruptedException을 던져 바로 빠져나옵니다. 사용법은 tryLock을 다룬 글에 있습니다.

스핀 대기는 언제 쓸모 있을까

스핀이 언제나 나쁜 것은 아닙니다. 스레드를 재웠다가 깨우려면 운영체제가 개입해야 하고, 컨텍스트 스위칭과 스레드 수에서 본 비용도 듭니다. 기다릴 시간이 그 비용보다 짧다면, 잠들지 않고 몇 번 더 시도하는 편이 빠를 수 있습니다. 그래서 표준 락도 상황에 따라 잠들기 전에 아주 잠깐 스핀하기도 합니다. JDK 21의 ReentrantLock이 쓰는 AbstractQueuedSynchronizer도, 대기열 맨 앞의 스레드가 깨어난 뒤 다시 기다려야 할 때는 잠깐 스핀하고 그래도 얻지 못하면 잠듭니다.

반대로 기다림이 길어지면 스핀은 손해입니다. 기다리는 내내 코어 하나를 차지하고, 그 코어로 할 수 있었던 다른 일은 진행되지 않습니다. 스레드가 코어보다 많으면 더 나빠집니다. 도는 스레드가 코어를 차지하는 동안 정작 락을 가진 스레드가 실행되지 못해, 락이 풀리는 시점까지 늦어질 수 있기 때문입니다. 락 안에서 네트워크나 파일 입출력을 한다면 기다림이 언제 끝날지 알 수 없으므로 스핀은 맞지 않습니다.

정리하면 스핀 락을 직접 만들어 쓸 일은 거의 없습니다. 값 하나를 바꾸는 일이라면 원자 클래스의 메서드로 충분하고, 여러 동작을 묶어야 한다면 synchronized나 ReentrantLock이 더 안전하고 기능도 많습니다. 직접 CAS를 써야 한다면, CAS가 실패했을 때 무엇을 할지와 얻은 락을 어떤 경우에도 푸는지부터 확인해야 합니다.

정리

• 플래그를 검사하는 일과 바꾸는 일을 따로 하면, 두 스레드가 모두 검사를 통과해 함께 락 안에 들어올 수 있습니다. volatile은 이 틈을 막지 못합니다.
• compareAndSet(false, true)는 검사와 잠금을 한 번에 처리하므로 한 스레드만 성공합니다. 실패한 스레드가 잠들지 않고 계속 시도하는 락을 스핀 락이라고 합니다.
• 락은 상호 배제와 함께 가시성도 줍니다. 앞 스레드가 락 안에서 쓴 일반 필드는 다음에 락을 얻은 스레드에 보입니다.
• 쓸 만한 락은 소유자가 아닌 스레드의 해제를 막고, 같은 스레드가 다시 잠그는 경우를 처리해야 합니다. 락을 쓰는 쪽은 finally에서 해제해야 합니다.
• 스핀은 기다림이 아주 짧을 때만 이득이고, 기다리는 동안 CPU를 계속 씁니다. 시간 제한, 인터럽트, 공정성이 필요하면 ReentrantLock을 씁니다.
• System.nanoTime()으로 시간 제한을 검사할 때는 두 값을 직접 비교하지 말고 차이를 비교합니다.

연습 문제

1. CheckThenSetLock에서 entrants만 AtomicInteger로 바꾸고 incrementAndGet()으로 늘리면, 출력은 언제나 20만이 됩니다. 그렇다면 이 락은 고쳐진 것인가요?

2. OwnedSpinLock.unlock()의 두 동작 순서를 바꿔, locked.set(false)를 먼저 하고 owner.compareAndSet(current, null)을 나중에 하면 어떤 문제가 생길 수 있는지 두 가지를 설명하세요.

3. 여러 스레드가 동시에 초기화를 요청해도 실제 초기화 작업은 한 번만 실행되어야 합니다. 초기화 권한을 얻지 못한 호출자는 기다리지 않고 바로 false를 돌려주게 만드세요.

import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.atomic.AtomicInteger;

public final class InitializeOnceSolution {
    private final AtomicBoolean claimed = new AtomicBoolean();
    private final AtomicInteger runs = new AtomicInteger();

    boolean initialize() {
        if (!claimed.compareAndSet(false, true)) return false;
        runs.incrementAndGet();
        return true;
    }

    public static void main(String[] args) throws InterruptedException {
        InitializeOnceSolution service = new InitializeOnceSolution();
        Thread[] threads = new Thread[20];
        for (int i = 0; i < threads.length; i++) {
            threads[i] = Thread.ofPlatform().start(service::initialize);
        }
        for (Thread thread : threads) {
            thread.join();
        }
        System.out.println("runs=" + service.runs.get());
    }
}

runs=1

다음 글

다음 글에서는 같은 작업을 락과 CAS로 각각 구현해 비교합니다. 충돌이 얼마나 잦은지, 계산이 얼마나 긴지, 함께 바꿔야 하는 상태가 얼마나 큰지에 따라 무엇을 고를지 정리합니다.