[OSTEP] 28. 락(Locks): 병행성 제어의 기초

3.1 인터럽트 제어 (Controlling Interrupts)#

초기 단일 프로세서 시스템에서는 임계 영역 진입 전에 인터럽트를 끄는 방식이 사용되기도 했습니다.

1
void lock() {
2
    DisableInterrupts();
3
}
4

5
void unlock() {
6
    EnableInterrupts();
7
}

• 장점: 단순하고 확실하게 상호 배제를 보장합니다.
• 단점:
  • 멀티프로세서에서는 동작하지 않습니다. 한 CPU에서 인터럽트를 꺼도 다른 CPU는 계속 실행됩니다.
  • 사용자 프로그램에 인터럽트 제어 권한을 주는 것은 매우 위험합니다. 무한 루프에 빠지면 시스템이 복구 불가능해질 수 있습니다.
  • 중요한 인터럽트(예: 디스크 I/O 완료)를 지연시키거나 놓치면 시스템 전체 지연이 커집니다.

정리하면, 인터럽트 제어는 특정 상황에서만 제한적으로 의미가 있고 일반적인 사용자 레벨 락의 해법으로는 부적절합니다.

3.2 소프트웨어만 사용하기 (A Failed Attempt)#

단순한 플래그 변수(flag)로 락을 구현하려는 시도는 실패합니다.

1
while (flag == 1) {
2
    ; // spin
3
}
4
flag = 1;

문제는 flag를 확인하고 값을 설정하는 과정이 원자적이지 않다는 점입니다. 두 스레드가 동시에 flag를 0으로 읽고 동시에 flag = 1을 수행하면, 결국 둘 다 임계 영역에 진입할 수 있습니다. 즉, 상호 배제를 보장하지 못합니다.

4.1 Test-And-Set (Atomic Exchange)#

Test-And-Set은 메모리의 이전 값을 반환하면서 동시에 새로운 값을 씁니다. 이 과정 전체가 원자적으로 수행됩니다.

이를 이용해 가장 단순한 스핀 락(Spin Lock) 을 만들 수 있습니다.

1
void lock(lock_t *lock) {
2
    while (TestAndSet(&lock->flag, 1) == 1) {
3
        ; // spin-wait
4
    }
5
}

이 락은 상호 배제를 보장하지만, 다음 한계가 있습니다.

• 공정성 부족: 운이 나쁜 스레드는 계속 밀려 기아 상태가 생길 수 있습니다.
• CPU 낭비: 락을 기다리는 동안 계속 루프를 돌며 CPU 시간을 소모합니다.
• 단일 CPU에서 특히 비효율적: 스핀이 타임 슬라이스를 태우면, 정작 락 보유자가 실행될 기회가 줄어 더 느려질 수 있습니다.

4.2 Compare-And-Swap (CAS)#

Compare-And-Swap은 기대값(expected)과 메모리 값이 일치할 때만 새로운 값으로 갱신합니다. 비교와 갱신이 원자적으로 수행됩니다.

• Test-And-Set과 마찬가지로 락 구현에 사용할 수 있고
• 더 일반적으로는 락 프리(lock-free) 자료구조 등에도 활용됩니다

4.3 Load-Linked / Store-Conditional (LL/SC)#

MIPS, ARM 등에서 사용하는 방식입니다.

• Load-Linked로 값을 읽고
• Store-Conditional로 값을 쓰되
• 그 사이 해당 주소에 다른 쓰기(write)가 없었을 때만 저장이 성공합니다

결국 목적은 동일합니다. 경쟁 구간을 원자적으로 다루기 위한 하드웨어 지원입니다.

4.4 Fetch-And-Add (Ticket Lock)#

Fetch-And-Add는 값을 원자적으로 1 증가시키고 이전 값을 반환합니다. 이를 이용하면 티켓 락(Ticket Lock) 을 만들 수 있습니다.

1
int myturn = FetchAndAdd(&lock->ticket);
2
while (lock->turn != myturn) {
3
    ; // spin
4
}

티켓 락은 먼저 온 스레드가 먼저 락을 얻는 선입선출(FIFO)을 보장하여 공정성 문제를 크게 완화합니다.

다만 여전히 스핀 방식이므로 경쟁이 심하면 CPU 낭비와 메모리 트래픽 문제가 남습니다. 특히 많은 스레드가 turn 값을 반복해서 읽으면서 캐시 라인이 흔들릴 수 있습니다.

5.1 양보 (Yield)#

yield() 같은 시스템 콜로 CPU를 다른 스레드에게 양보할 수 있습니다.

• 스핀 대신 양보하면 CPU 낭비는 줄어듭니다.
• 하지만 스레드 수가 많으면 문맥 교환(Context Switch) 비용이 커지고, 실행 큐가 혼잡해집니다.
• 또한 특정 스레드가 계속 밀리는 기아 상태를 완전히 없애기 어렵습니다.

5.2 큐 사용: 잠들기 (Sleeping)#

더 근본적인 접근은 대기 스레드를 재우는 것입니다. OSTEP에서는 Solaris의 park()와 unpark() 같은 인터페이스를 예로 들며, 대기 스레드를 큐로 관리하는 방식으로 확장합니다.

개념적으로는 다음과 같습니다.

• 락이 비어 있으면 즉시 획득
• 이미 누군가 보유 중이면 대기 큐에 등록하고 잠듦
• 락이 풀릴 때 큐에서 하나를 깨움

1
if (m->flag == 0) {
2
    m->flag = 1; // 락 획득
3
} else {
4
    queue_add(m->q, gettid());
5
    park(); // 잠들기
6
}

이 방식은 스핀을 최소화하고 큐를 통해 공정성도 개선할 수 있습니다. 다만 여기에는 중요한 레이스가 숨어 있습니다.

• 스레드가 park() 직전에 락이 해제되고 unpark()가 먼저 발생하면
• 이후 해당 스레드는 깨울 이벤트를 놓친 채 영원히 잠들 수 있습니다

이를 막기 위해 setpark() 같은 추가 프로토콜이 필요합니다. 즉, sleep 기반 락은 성능을 얻는 대신 잠듦과 깨움의 순서를 안전하게 설계해야 합니다.