[OS] Lock 구현의 기본 원리

Lock은 어떻게 만들어지는가? 

지난 포스팅에서 다뤘듯이 멀티스레드 프로그램을 작성할 때 가장 먼저 부딪히는 문제가 바로 동시성(Concurrency)이다. 여러 스레드가 공유 데이터를 동시에 수정하면 예상치 못한 결과가 발생한다. OS는 이런 문제를 해결하기 위해 다양한 동기화(synchronization) 기법을 제공하는데, 그 핵심이 바로 Lock이다.

 

이 글에서는

• 왜 Lock이 필요한지
• 하드웨어 관점에서 Lock은 어떻게 구현되는지
• Spin lock의 한계
• OS가 개입하는 고급 Lock들까지 정리한다.

 

 

---

 

왜 Lock이 필요한가?

동시에 실행되는 스레드는 순서를 보장할 수 없다.

예를 들어 

int x = 0;

// Thread1
void foo() {
	x++;
}

// Thread2
void bar() {
	x--;
}

x는 0에서 시작하지만 최종 값은 0, 1, -1 무엇이든 가능하다.

 

한 줄짜리 연산처럼 보여도 CPU 내부에서는 load → add → store의 여러 단계로 나뉘기 때문에 원자성이 보장되지 않는다.
따라서 공유 자원에 접근하는 critical section을 보호하기 위한 Lock이 필요하다.

 

Lock의 기본 개념

Lock은 다음 두 가지 상태를 가진다.

• available(unlock): 아무 스레드가 락을 잡지 않는 상태이다.
• acquired(lock): 단 하나의 스레드가 락을 잡은 상태이다. 

스레드는 critical section에 들어가기 전에 lock()을 호출해 락을 획득하고, 끝나면 unlock()으로 반납한다.

lock(&mutex);
balance = balance + 1;
unlock(&mutex);

 

POSIX에서는 이를 mutex(뮤텍스)라고 부르며, 프로그래머가 쉽게 사용할 수 있도록 라이브러리로 제공된다.

 

 

락을 평가하는 기준

락을 단순히 잠금/해제만 잘한다고 좋은 락이라고 말할 수 없다.

좋은 락은 최소한 다음 세 가지 조건을 만족해야 한다.

1) 상호 배제(Mutual Exclusion)

여러 스레드가 동시에 critical section에 진입하는 일이 없어야 한다.
이것이 락의 존재 이유이자 가장 기본 조건이다.

2) 공정성(Fairness)

여러 스레드가 락을 기다릴 때 특정 스레드가 계속 밀려나는 일이 없어야 한다.
Starvation(기아) 문제를 방지하는 것이 중요하다.

3) 성능(Performance)

락을 사용하면 대기 시간이 늘어나고 오버헤드가 발생하기 때문에, 락 자체의 비용이 가능한 한 낮아야 한다.
특히 멀티코어 환경에서는 효율적인 락 구현이 성능에 큰 영향을 준다.

 

 

---

 

Controlling Interrupts (초기 Lock 구현 방식)

Interrupt Disable (인터럽트 비활성화 기반 Lock)

void lock() {
    DisableInterrupts();
}
void unlock() {
    EnableInterrupts();
}

장점

• 간단함
• critical section이 인터럽트되지 않으므로 원자성 보장

단점

• 사용자 프로그램이 인터럽트를 마음대로 끄면 전체 시스템 안정성 망가짐
• 인터럽트를 오래 끄면 인터럽트 손실 발생
• 멀티코어 환경에서는 아예 작동하지 않음
  → 한 CPU만 인터럽트를 끄는 것이므로 다른 CPU는 계속 동작함

 

---

 

 

가장 단순한 Lock 구현 

가장 단순하게 flag를 사용하는 방법이 있다.

하지만 2가지 문제가 발생한다.

 

1) 원자성이 없음

1) 원자성이 없어서 mutual exclusion을 보장하지 못한다.

 

두 스레드가 동시에 flag를 읽고, 둘 다 비어 있음으로 판단해 flag=1을 써버릴 수 있다. critical section 보호 실패 → 상호배제 깨지게 된다. 

 

 

2) 스핀으로 CPU 낭비

계속 도는 동안 아무 일도 하지 않으면서 CPU를 소모한다.

따라서 올바른 락을 위해서는 읽기-비교-쓰기 작업을 하나의 원자적 연산으로 묶어주는 하드웨어 명령어가 반드시 필요하다.

 

 

→ 따라서 하드웨어의 지원을 받은 atomic intruction이 필요하다.

 

---

 

 

하드웨어가 제공하는 Atomic 연산

CPU는 락 구현을 위해 다음과 같은 atomic instruction을 제공한다.

 

Test-and-Set

값을 읽고(테스트) 동시에 새 값을 저장(설정)하는 연산이다.

int TestAndSet(int *ptr, int new) {
    int old = *ptr;
    *ptr = new;
    return old;
}

값을 읽고, 동시에 새로운 값을 업데이트 하기 때문에 원자성이 보장된다. 

 

Compare-and-Swap (CAS)

메모리 값이 특정 값과 같을 때만 새로운 값으로 교체한다.
대부분의 언어에서 atomic 연산 기반으로 사용.

Fetch-and-Add

값을 원자적으로 1 증가시키고 이전 값을 반환한다. 티켓 락(ticket lock)을 구현할 때 사용된다.

이 명령어들은 어떤 스레드도 중간에 끼어들 수 없도록 만들어 lock의 원자성을 보장해주는 핵심 도구들이다.

 

 

---

 

Spin Lock: 가장 단순한 실제 락

하드웨어 atomic 명령어(보통 Test-Amd-Set)를 이용하면 스핀락을 만들 수 있다.
스레드는 락을 얻을 때까지 계속 검사하며 기다린다.

 

 

 

장점

• 구현 간단
• Lock 시간이 매우 짧으면 효율적

단점

• CPU를 계속 소모(busy-wait)
• 공정성(Fairness)이 없음
• 단일 CPU 환경에서는 전체 스케줄링이 막힐 수 있음

특히 경쟁이 많은 환경에서는 Spin Lock의 성능이 크게 떨어진다.

 

---

 

CAS 기반 락

CAS는 현대 CPU가 가장 폭넓게 제공하는 원자 연산이다.
"값이 expected일 때만 new로 바꾸기"라는 성질 때문에 스핀락을 더 효율적으로 만들 수 있다.

 

expected는 메모리에 들어있기를 기대하는 값이며, 실제 값이 expected와 같을 때만 new로 교체된다.

 

하지만 여전히 스핀 기반이므로 CPU 낭비 문제는 존재한다.

 

 

---

Fairness를 보장하는 Ticket Lock

 

Fetch-and-Add

Fetch-and-Add 명령어는 원자적으로 값을 증가시키는 방법이다.

 

 

Fetch-and-Add기반의 티켓 락은 supermarket의 번호표 시스템과 비슷하다.

• 스레드가 락을 요청하면 번호표(ticket)를 가져감
• 자신의 번호가 호출될 때까지 기다림
• FIFO 순서 보장 → starvation 없음

티켓 락도 스핀 자체는 존재하지만, 순번 기반(FIFO)이라 모든 스레드가 반드시 기회를 얻게 되어 공정성이 보장된다.

 

 

---

 

Spinning 문제를 해결하기 위한 OS 수준의 락

여러 스레드가 스핀으로 기다리는 것은 매우 비효율적이다. 그래서 OS는 다음과 같은 방식을 도입한다.

1) yield 기반

스레드가 락을 얻지 못하면 CPU를 양보(running -> ready state)한다.

그러나 context-switch 비용이 크고 여전히 fairness 문제가 존재한다.

 

2) sleep/wakeup기반 Queue-based Lock

• 락을 기다리는 스레드를 큐에 저장
• 스레드는 sleep 상태로 전환 (park)
• 락을 해제할 때 특정 스레드를 정확히 깨움(unpark)

→ CPU 낭비 없음
→ 공정성도 관리 가능

하지만 여기서 또 다른 문제가 발생한다.

 

 

Lost Wakeup 문제와 해결

sleep(park)과 wakeup(unpark) 사이 타이밍이 어긋나면 스레드를 깨울 기회를 놓쳐 스레드가 영원히 잠들어 버릴 수 있다.

 

T1이 먼저 unpark()를 호출하고 난 뒤 T2가 뒤늦게 park()를 호출하면, 깨움 신호가 이미 전달된 상황이라 T2는 다시는 깨어나지 못하고 영구적으로 sleep 상태에 빠질 수 있다.

 

운영체제는 이를 해결하기 위해 park 하기 직전에 깨움 신호가 왔는지를 기록하는 메커니즘(setpark)을 도입해 문제를 해결한다. setpark()는 곧 park()한다는 의미로 그 사이에 나오는 unpark()는 무시해달라고 지시한다.

 

 

---

 

Two-Phase Lock (현대 OS)

리눅스는 두 가지 접근을 결합한다.

Phase 1: 짧게 스핀

Lock이 금방 풀릴 가능성이 있으면 잠깐 스핀한다.

Phase 2: 그래도 안 되면 sleep

OS에 의해 스레드가 대기열로 넘어가고 block 상태로 쉼.

이 방식은 불필요한 CPU 소모를 줄이고, 불필요한 문맥 전환을 피하며, 락 경쟁이 많은 환경에서도 좋은 성능을 낸다.

 

 

 

 

 

출처: 경북대학교 한명균 교수님, "운영체제" 강의 자료