리눅스 내부 구조 08 - 동기화와 동시성

동시성이 문제가 되는 이유

현대 시스템에서 CPU는 여러 코어를 갖고 있으며, 커널은 수많은 스레드를 동시에 실행한다. 이러한 환경에서 두 개 이상의 실행 흐름이 같은 데이터를 동시에 읽고 쓰면 예측할 수 없는 결과가 발생한다. 이것이 경쟁 상태(race condition)이다.

경쟁 상태가 위험한 이유는 대부분의 경우 정상적으로 동작하기 때문이다. 문제는 수천 번에 한 번, 혹은 특정 타이밍에서만 발생하며, 재현하기 극도로 어렵다. 단순한 카운터 증가 연산조차 안전하지 않다. count++라는 코드는 고급 언어에서 한 줄이지만, CPU 수준에서는 메모리에서 값을 읽고, 1을 더하고, 다시 메모리에 쓰는 세 단계로 이루어진다. 두 스레드가 동시에 이 세 단계를 실행하면 하나의 증가가 유실될 수 있는 것이다.

스레드 A: 읽기(count=5) → 증가(6) → 쓰기(count=6)
스레드 B:      읽기(count=5) → 증가(6) → 쓰기(count=6)

결과: count=6 (기대값 7)

이 문제를 해결하려면 공유 자원에 접근하는 코드 영역, 즉 임계 영역(critical section)을 보호해야 한다. 한 번에 하나의 실행 흐름만 임계 영역에 들어갈 수 있도록 보장하는 것이 동기화의 핵심이다.

원자적 연산

가장 기본적인 동기화 수단은 원자적 연산(atomic operation)이다. 원자적 연산은 CPU가 하나의 명령으로 수행하기 때문에 중간에 다른 실행 흐름이 끼어들 수 없다.

리눅스 커널은 atomic_t 타입과 관련 함수들을 제공한다. atomic_inc(), atomic_dec(), atomic_add() 같은 함수는 단일 CPU 명령으로 변환되어 실행되므로 별도의 잠금 없이도 안전하다. x86 아키텍처에서는 LOCK 프리픽스가 붙은 명령어가 버스를 잠가서 다른 코어의 접근을 차단하는 방식으로 이를 구현한다.

그러나 원자적 연산만으로는 복잡한 동기화를 해결할 수 없다. 두 개 이상의 변수를 동시에 갱신해야 하거나, 조건을 확인한 후 동작을 수행해야 하는 경우에는 더 정교한 메커니즘이 필요하다.

스핀락

스핀락(spinlock)은 커널에서 가장 많이 사용되는 잠금 메커니즘이다. 스핀락을 획득하지 못한 스레드는 잠금이 풀릴 때까지 반복적으로 확인하면서 대기한다. 말 그대로 제자리에서 회전(spin)하는 것이다.

과연 바쁜 대기(busy waiting)가 효율적인 방법인가? 유저 공간의 관점에서는 CPU 시간을 낭비하는 것처럼 보인다. 하지만 커널에서는 사정이 다르다. 임계 영역이 매우 짧은 경우, 컨텍스트 스위치의 비용이 잠시 대기하는 비용보다 훨씬 크다. 스레드를 재우고 깨우는 데 수천 사이클이 소요되는 반면, 스핀락의 임계 영역은 보통 수십에서 수백 사이클이면 완료되기 때문이다.

스핀락을 사용할 때 반드시 지켜야 하는 규칙이 있다. 스핀락을 보유한 상태에서는 절대로 잠들어서는 안 된다. 스핀락을 잡은 채 스케줄링이 발생하면, 다른 코어에서 같은 스핀락을 기다리는 스레드가 영원히 회전하게 되는 것이다. 또한 인터럽트 핸들러에서도 스핀락이 필요한 경우에는 spin_lock_irqsave()를 사용하여 인터럽트를 비활성화해야 한다. 그렇지 않으면 스핀락을 보유한 상태에서 인터럽트가 발생하고, 인터럽트 핸들러가 같은 스핀락을 요청하여 데드락에 빠질 수 있다.

뮤텍스와 세마포어

스핀락이 짧은 임계 영역에 적합하다면, 뮤텍스(mutex)는 더 긴 임계 영역에 적합하다. 뮤텍스를 획득하지 못한 스레드는 대기 큐에 들어가 잠든다. 잠금이 해제되면 대기 중인 스레드가 깨어나 실행을 재개한다. 이 방식은 CPU 시간을 낭비하지 않지만, 컨텍스트 스위치 비용이 발생한다.

뮤텍스와 세마포어(semaphore)의 차이는 허용하는 동시 접근 수이다. 뮤텍스는 한 번에 하나의 스레드만 임계 영역에 진입할 수 있다. 세마포어는 카운터를 사용하여 동시에 N개의 스레드가 접근할 수 있도록 한다. 카운터가 1인 세마포어(바이너리 세마포어)는 뮤텍스와 유사하게 동작하지만, 뮤텍스에는 소유권이라는 중요한 개념이 있다. 뮤텍스를 잠근 스레드만이 해제할 수 있는 반면, 세마포어는 다른 스레드가 해제할 수 있다. 이 소유권 개념 덕분에 뮤텍스는 우선순위 역전 문제를 해결할 수 있는 것이다.

커널 개발에서는 특별한 이유가 없는 한 세마포어 대신 뮤텍스를 사용하는 것이 권장된다. 뮤텍스가 더 엄격한 사용 규칙을 강제하므로 디버깅이 용이하고, 성능 최적화 여지도 더 크기 때문이다.

읽기-쓰기 잠금

많은 경우 공유 데이터에 대한 접근은 읽기가 쓰기보다 압도적으로 많다. 읽기만 하는 스레드들끼리는 충돌이 발생하지 않으므로 동시에 접근을 허용해도 안전하다. 이러한 관찰에서 읽기-쓰기 잠금(read-write lock)이 탄생했다.

읽기-쓰기 잠금은 읽기 잠금과 쓰기 잠금을 구분한다. 여러 스레드가 동시에 읽기 잠금을 획득할 수 있지만, 쓰기 잠금은 배타적이다. 쓰기 잠금을 획득하려면 모든 읽기 잠금이 해제될 때까지 기다려야 한다. 반대로 쓰기 잠금이 활성화된 동안에는 읽기도 차단된다.

이 방식에는 함정이 있다. 읽기가 매우 빈번한 경우, 쓰기 스레드가 기아 상태에 빠질 수 있다. 새로운 읽기 요청이 끊임없이 들어오면 쓰기 잠금을 획득할 기회가 없어지는 것이다. 리눅스 커널의 rwlock_t는 이 문제를 완전히 해결하지 못하며, 이것이 RCU 같은 더 정교한 메커니즘이 필요한 이유 중 하나이다.

데드락

동기화 메커니즘을 사용할 때 가장 두려운 상황이 데드락(deadlock)이다. 데드락은 두 개 이상의 실행 흐름이 서로 상대방이 보유한 자원을 기다리며 영원히 진행하지 못하는 상태이다.

스레드 A: lock(X) 획득 → lock(Y) 대기...
스레드 B: lock(Y) 획득 → lock(X) 대기...

→ 양쪽 모두 영원히 대기

데드락이 발생하려면 네 가지 조건이 동시에 충족되어야 한다. 상호 배제(자원을 한 번에 하나만 사용), 점유 대기(자원을 보유한 채 다른 자원 대기), 비선점(다른 스레드의 자원을 강제로 빼앗지 못함), 순환 대기(스레드들이 원형으로 자원을 대기)이다. 이 네 조건 중 하나라도 깨뜨리면 데드락을 방지할 수 있다.

가장 실용적인 예방법은 잠금 순서를 고정하는 것이다. 시스템의 모든 잠금에 순서를 부여하고, 항상 낮은 번호의 잠금을 먼저 획득하도록 강제하면 순환 대기가 발생할 수 없다. 리눅스 커널은 lockdep이라는 잠금 의존성 검증 도구를 내장하고 있다. lockdep은 런타임에 잠금 획득 순서를 추적하고, 잠재적 데드락 패턴을 감지하면 경고를 출력한다. 실제 데드락이 발생하기 전에 문제를 발견할 수 있어 커널 개발에서 매우 유용한 도구인 것이다.

Futex: 유저 공간의 빠른 잠금

유저 공간 프로그램도 동기화가 필요하다. pthread_mutex가 대표적인 예이다. 초기의 유저 공간 잠금 구현은 항상 시스템 콜을 호출해야 했기 때문에 성능이 좋지 않았다. 잠금을 획득하든 실패하든 커널 진입이 필요했던 것이다.

Futex(Fast Userspace Mutex)는 이 문제를 해결한다. 핵심 아이디어는 경쟁이 없는 경우(대부분의 경우)에는 시스템 콜 없이 유저 공간에서 원자적 연산만으로 잠금을 처리하고, 경쟁이 발생한 경우에만 커널에 도움을 요청하는 것이다.

Futex는 공유 메모리의 정수 값과 커널의 대기 큐라는 두 가지 구성 요소로 이루어진다. 잠금 획득 시 유저 공간에서 compare-and-swap 원자적 연산을 수행한다. 성공하면 잠금이 획득된 것이고 시스템 콜이 필요 없다. 실패하면 FUTEX_WAIT 시스템 콜을 호출하여 커널의 대기 큐에서 잠든다. 잠금 해제 시에는 대기자가 있는 경우에만 FUTEX_WAKE 시스템 콜을 호출하여 대기 중인 스레드를 깨운다.

이 설계가 효과적인 이유는 실제 시스템에서 잠금 경쟁이 발생하는 비율이 낮기 때문이다. 대부분의 잠금 획득은 경쟁 없이 성공하며, 이때 시스템 콜의 오버헤드를 완전히 피할 수 있는 것이다. glibc의 pthread 뮤텍스 구현은 내부적으로 futex를 사용한다.

RCU: 읽기 최적화의 극단

RCU(Read-Copy-Update)는 리눅스 커널에서 가장 정교한 동기화 메커니즘 중 하나이다. 읽기-쓰기 잠금의 근본적인 한계, 즉 읽기 잠금조차도 캐시 라인 경쟁을 유발한다는 문제를 해결하기 위해 설계되었다.

RCU의 핵심 원리는 읽기 측에서 잠금을 전혀 사용하지 않는 것이다. 읽기 측은 rcu_read_lock()과 rcu_read_unlock() 사이에서 보호된 데이터를 읽기만 하면 된다. 이 함수들은 실질적으로 선점을 비활성화할 뿐 캐시 라인을 건드리지 않으므로 멀티코어 환경에서도 완벽하게 확장된다.

쓰기 측은 어떻게 동작하는가? 쓰기 측은 기존 데이터를 복사하고, 복사본을 수정한 다음, 포인터를 원자적으로 교체한다. 이때 기존 데이터를 즉시 해제하지 않는다. 아직 기존 데이터를 읽고 있는 스레드가 있을 수 있기 때문이다. synchronize_rcu()를 호출하면, 모든 CPU가 한 번 이상 RCU 읽기 임계 영역을 벗어날 때까지 기다린다. 이 시점을 유예 기간(grace period)이라 하며, 유예 기간이 지나면 기존 데이터를 안전하게 해제할 수 있는 것이다.

쓰기 측:
1. old = rcu_dereference(ptr)
2. new = copy(old)
3. modify(new)
4. rcu_assign_pointer(ptr, new)
5. synchronize_rcu()  ← 유예 기간 대기
6. free(old)

읽기 측:
rcu_read_lock()
p = rcu_dereference(ptr)  ← old든 new든 항상 유효한 데이터
read(p)
rcu_read_unlock()

RCU는 라우팅 테이블, 프로세스 목록, 모듈 목록 등 읽기가 압도적으로 많은 커널 데이터 구조에서 광범위하게 사용된다. 읽기 경로에서 캐시 라인 경쟁이 전혀 없기 때문에 코어 수가 증가해도 성능이 저하되지 않는 것이다.

락 프리 자료 구조

잠금을 사용하지 않고도 스레드 안전한 자료 구조를 구현할 수 있다. 락 프리(lock-free) 자료 구조는 원자적 연산, 특히 CAS(Compare-And-Swap)를 기반으로 동작한다.

CAS 연산은 메모리 위치의 현재 값이 기대 값과 같으면 새로운 값으로 교체하고, 다르면 실패하여 재시도하는 방식으로 동작한다. 이를 이용하면 잠금 없이도 스택, 큐, 연결 리스트 같은 자료 구조를 구현할 수 있다.

과연 락 프리가 항상 잠금보다 빠른가? 그렇지 않다. 경쟁이 낮은 환경에서는 잠금 기반 구현이 더 단순하고 효율적일 수 있다. 락 프리의 진정한 장점은 진행 보장(progress guarantee)에 있다. 잠금 기반 구현에서는 잠금을 보유한 스레드가 선점되면 다른 모든 스레드가 대기해야 하지만, 락 프리 구현에서는 항상 적어도 하나의 스레드가 진행할 수 있다. 리눅스 커널은 락 프리 연결 리스트(llist)와 같은 자료 구조를 일부 경로에서 활용하고 있으며, 이는 특히 인터럽트 컨텍스트처럼 잠금을 사용하기 어려운 상황에서 유용한 것이다.

동기화 메커니즘의 선택

리눅스 커널이 이렇게 다양한 동기화 메커니즘을 제공하는 이유는 하나의 도구로 모든 상황을 해결할 수 없기 때문이다. 각 메커니즘은 서로 다른 트레이드오프를 가지며, 상황에 맞는 선택이 성능과 정확성 모두에 결정적인 영향을 미친다.

동시성 문제는 커널 개발에서 가장 어려운 영역 중 하나이며, 올바른 동기화 설계는 시스템의 안정성과 성능을 좌우한다. 커널이 제공하는 이러한 메커니즘들은 수십 년간의 경험과 수많은 버그 수정을 통해 발전해 온 결과인 것이다.

다음 포스트에서는 리눅스의 네트워킹 스택을 살펴본다.