Kernel Synchronization Primitives

1. Overview

커널 동기화 원시(Kernel Synchronization Primitives)는 멀티코어 프로세서에서 두 개 이상의 CPU가 동시에 커널 전역 데이터 구조체에 접근할 때 발생할 수 있는 레이스 컨디션(Race Condition)과 데이터 손상을 막기 위한 운영체제의 동기화 도구 체계입니다.

학습자는 락이 풀릴 때까지 CPU를 점유하며 짧게 대기하는 **스핀락(Spinlock)**의 하드웨어 원자성(Atomic)을 이해합니다. 이어 대기 시간이 길 때 실행권을 반납하는 **뮤텍스(Mutex)와 세마포어(Semaphore)**의 차이를 비교하고, 읽기 경로의 락 경합을 줄이기 위해 복사본을 활용하는 RCU(Read-Copy-Update) 알고리즘을 살핍니다.

2. Scope & Boundaries

In-Scope

• 원자적 하드웨어 락 (Atomic Hardware): Test-and-Set(TAS), Compare-and-Swap(CAS), 캐시 간섭 배리어(Memory Barrier).
• 바쁜 대기 스핀락 (Spinlocks): 기본 스핀락, 읽기-쓰기 스핀락(RW-Spinlock), 인터럽트 마스킹 결합 스핀락(spin_lock_irqsave).
• 블로킹 락 (Blocking Primitives): 뮤텍스(Mutex), 세마포어(Semaphore), 대기 큐(Wait Queue)와 컨텍스트 스위치 수면(Sleep).
• 락-프리 최적화 (Lock-Free): RCU(Read-Copy-Update), 그레이스 피리어드(Grace Period) 수거 흐름, 순차락(Seqlock).

Out-of-Scope

• 유저 공간 비동기 프로그래밍: 파이썬 asyncio나 Node.js의 싱글 스레드 이벤트 루프 락(Lock) $\rightarrow$ 01-04-02. Asynchronous Execution 영역.
• 분산 시스템 데이터베이스 락: Redis 분산 락, 트랜잭션 격리 수준(Isolation Level) $\rightarrow$ 04-03-02. Distributed Transactions 영역.

Boundaries

• Kernel Sync vs. RTOS Sync (02-06-02): RTOS 동기화(02-06-02)가 싱글 코어에서 인터럽트와 태스크가 얽힐 때 우선순위 상속(Inheritance)으로 우선순위 역전을 줄이는 데 초점이 있다면, 리눅스 커널 동기화는 멀티코어 서버에서 코어 A와 코어 B가 동시에 task_struct 같은 공유 메모리에 접근할 때 캐시 일관성(MESI)과 락 병목을 어떻게 제어하는지에 초점이 있습니다.

3. Counterexample

• 인터럽트 안에서의 뮤텍스 수면 (Sleeping in ISR): 인터럽트 핸들러(ISR)에서 공유 버퍼를 보호하려고 mutex_lock()을 사용하면 문제가 생길 수 있습니다. 뮤텍스는 락이 풀리지 않았을 때 현재 실행 흐름을 대기 큐에 넣고 Sleep 상태로 전환할 수 있지만, 인터럽트 핸들러는 일반 프로세스 문맥이 아니므로 잠들 수 없습니다. 이 상황은 "Scheduling while atomic" 같은 커널 오류로 이어질 수 있으므로, ISR에서는 짧은 임계 구역에 적합한 스핀락(Spinlock)을 사용해야 합니다.
• 스핀락으로 잠근 채 긴 작업 수행 (Long Work under Spinlock): 스핀락을 잡은 상태(spin_lock)에서 디스크에서 1GB 파일을 읽는 I/O Blocking 작업을 수행하면 다른 코어가 락이 풀리기를 기다리며 CPU를 계속 소모합니다. 스핀락은 매우 짧은 임계 구역에 적합하므로, 긴 작업이나 대기 가능한 작업은 스핀락 밖에서 처리해야 합니다.

4. Prerequisites

• 멀티코어와 레이스 컨디션 (Basic): 두 CPU가 같은 메모리 값을 동시에 +1 할 때 값이 2가 아니라 1이 될 수 있는 데이터 손상 시나리오를 알아야 합니다. (02-06-03 Task Synchronization)
• 문맥 교환과 스케줄링 (Recommended): 프로세스가 자러 간다(Sleep)는 행위가 커널 스택(TCB) 레벨에서 어떻게 일어나는지 구조적 이해가 필요합니다. (03-02-01 Process Lifecycle)

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: 하드웨어가 보장하는 원자적 연산 (Atomic & CAS)

• Why to Learn: 커널 프로그래머가 C 언어로 flag = 1;이나 count++를 작성해도, 멀티코어 CPU 내부에서는 읽기/수정/쓰기 단계가 나뉘어 실행될 수 있습니다. 이 경쟁 구간을 하드웨어 원자 연산으로 제어하는 방법을 이해하기 위해서입니다.
• What to Learn:
  • Concepts: 원자성(Atomicity), 레이스 컨디션(Race Condition), Test-and-Set (TAS), Compare-and-Swap (CAS).
  • Skills: 어셈블리 LOCK 프리픽스, atomic_inc() 매크로.
  • Tools: GCC Built-in Atomic Functions.
  • Trade-offs: 일반 변수 count++는 빠르지만 코어 A와 B가 동시에 갱신하면 값이 깨질 수 있습니다. atomic_inc(&count)는 하드웨어 원자성을 통해 갱신을 보호하지만, 메모리 버스와 캐시 일관성 비용 때문에 코어 수가 많아질수록 병목이 커질 수 있습니다.
• How to Learn:
  • 1단계: "변수가 0이면 1로 바꿔라(Lock 획득)"를 C 코드로 쓰면 if (x==0) x=1;처럼 두 단계가 됩니다. 코어 A가 if를 통과한 직후 코어 B도 같은 조건을 통과하면 두 실행 흐름이 동시에 락을 얻었다고 판단할 수 있습니다.
  • 2단계: 최신 CPU의 cmpxchg(CAS)는 메모리 값이 기대값과 같을 때만 새 값으로 바꾸는 동작을 원자적으로 수행합니다. 이 명령이 경쟁 구간을 어떻게 닫는지 확인합니다.
• Implement: 파이썬 multiprocessing의 Value('i', 0) 공유 변수에 대해 2개의 스레드가 counter += 1을 반복할 때 기대값과 다른 결과가 나오는 레이스 컨디션을 재현합니다. 이어 Lock() 블록(CAS 모사)을 적용했을 때 값은 정확해지지만 소요 시간(Time)이 늘어나는 점을 비교합니다.

Recommended

Core Topic 02: Sleep 없이 기다리는 스핀락 (The Spinlock)

• Why to Learn: 인터럽트 핸들러처럼 Sleep할 수 없는 커널 문맥에서 공유 데이터를 보호하려면, 짧은 시간 동안 CPU를 점유하며 기다리는 스핀락이 왜 필요한지 이해해야 합니다.
• What to Learn:
  • Concepts: 스핀락(Spinlock), 바쁜 대기(Busy Waiting), spin_lock_irqsave (인터럽트 마스킹 융합).
  • Skills: 코어 로컬 인터럽트 비활성화, 데드락(Deadlock) 타파.
  • Tools: 커널 Lockdep(데드락 탐지기).
  • Trade-offs: 락을 얻을 때까지 스케줄러로 빠지지 않고 while(flag==1) 루프를 돌면 문맥 교환(Context Switch) 비용은 피할 수 있습니다. 하지만 락 보유 시간이 길어지면 CPU를 계속 소모하는 비용이 큽니다.
• How to Learn:
  • 1단계: 코어 0이 락을 잡고 리스트를 아주 짧게 수정 중일 때, 코어 1이 Sleep으로 전환하지 않고 짧은 루프를 돌며 락 해제를 기다리는 구조를 분석합니다.
  • 2단계: 코어 0이 스핀락을 잡은 상태에서 같은 코어에 네트워크 인터럽트가 들어오면 데드락 위험이 생길 수 있습니다. 이를 줄이기 위해 spin_lock_irqsave가 해당 코어의 인터럽트 마스킹을 함께 수행하는 이유를 확인합니다.
• Implement: 커스텀 Spinlock 파이썬 객체를 만듭니다. 스레드 B가 lock.acquire()를 호출하면 while self.locked: pass(Busy Wait) 상태에 머물고, 0.1초 뒤 스레드 A가 release() 하면 즉시 통과하는 바쁜 대기 시뮬레이션을 작성합니다.

Practical

Core Topic 03: 실행권을 반납하는 뮤텍스와 세마포어 (Mutex & Semaphore Sleep)

• Why to Learn: 디스크에서 1GB 파일을 읽는 긴 I/O Blocking 작업에 스핀락을 사용하면 다른 코어가 CPU를 계속 소모하며 기다립니다. 긴 대기에는 실행권을 반납하는 뮤텍스와 세마포어가 더 적합한 이유를 이해하기 위해서입니다.
• What to Learn:
  • Concepts: 뮤텍스(Mutex), 세마포어(Semaphore), 대기 큐(Wait Queue), 컨텍스트 스위치(Context Switch).
  • Skills: 뮤텍스 소유권(Ownership) 해제 조건 제한, 수면(Sleep) 및 기상(Wake-up) 핑퐁.
  • Tools: 리눅스 /proc/locks.
  • Trade-offs: 대기 큐에서 Sleep 상태로 들어가면 CPU를 다른 실행 흐름에 양보할 수 있습니다. 대신 Sleep 진입과 Wake-up 과정에서 레지스터 저장·복원과 컨텍스트 스위칭 비용이 발생합니다.
• How to Learn:
  • 1단계: 락 보유 시간이 길 것으로 예상되면 커널은 현재 프로세스의 TCB(Task Control Block)를 뮤텍스 내부의 대기 큐(Wait Queue)에 넣고, 스케줄러를 통해 Sleep 상태로 전환합니다.
  • 2단계: 락 소유자가 Unlock하면 대기 큐에 있던 TCB를 깨워(Wake_up) 스케줄러의 Ready 큐로 되돌리는 과정을 살핍니다.
• Implement: Wait_Queue = [] 리스트를 내장한 파이썬 모의 Kernel_Mutex를 작성합니다. 스레드 B가 acquire()를 시도할 때 이미 잠겨 있으면 Wait_Queue.append(Thread_B)에 넣고 event.wait()(Sleep 모사)로 대기합니다. 스레드 A가 release()할 때 Wait_Queue.pop().set()(Wake_up)으로 B를 깨우는 로그를 출력합니다.

Advanced

Core Topic 04: 읽기 경로를 줄이는 락 프리와 RCU (Lock-Free & RCU)

• Why to Learn: 많은 코어를 가진 서버에서 읽기(Read) 요청이 대부분인 자료구조에 매번 락(Lock)을 걸면 캐시 일관성 비용과 락 경합이 커질 수 있습니다. RCU가 읽기 경로의 병목을 줄이는 방식을 이해하기 위해서입니다.
• What to Learn:
  • Concepts: RCU(Read-Copy-Update), 락 프리(Lock-Free), 그레이스 피리어드(Grace Period), 캐시 일관성 패널티(Cache Coherence).
  • Skills: 포인터 덮어치기(Pointer Publish), 지연된 메모리 해제(Deferred Free).
  • Tools: 리눅스 커널 네트워킹 라우팅 테이블(RCU 대표 사례).
  • Trade-offs: 읽기(Reader) 경로에서 락을 줄이면 리눅스 네트워크 스택처럼 읽기가 많은 경로의 확장성이 좋아질 수 있습니다. 대신 쓰기(Writer) 작업에서는 원본을 복사하고 포인터를 교체한 뒤, 기존 데이터를 읽던 실행 흐름이 모두 빠져나갈 때까지 Grace Period를 기다려야 하므로 쓰기 비용과 메모리 사용량이 늘어납니다.
• How to Learn:
  • 1단계: Read-Copy-Update: 노드 A를 B로 바꾸고 싶을 때 A에 락을 걸지 않고, B를 새로 복사(Copy)해 수정한 뒤 연결 포인터를 원자적으로 A에서 B로 교체(Update)하는 흐름을 살핍니다.
  • 2단계: Grace Period: 포인터가 B로 바뀌었더라도 아직 A 주소를 읽고 있는 Reader가 있을 수 있으므로, 커널은 A를 바로 삭제(Free)하지 않고 모든 CPU가 안전 지점을 지날 때까지 Grace Period를 기다립니다.
• Implement: 리스트 요소 변경 시 Mutex로 전체 루프를 잠그면 Reader 100개가 대기하는 상황을 만들고, RCU 방식을 모사해 new_node = copy(old); new_node.val = 9; global_ptr = new_node;처럼 포인터만 교체했을 때 Reader가 락 없이 과거/현재 데이터를 관측하는 스크립트를 작성합니다.

7. Terminology

8. References

Primary

• [P2] SWEBOK v4.0 - Software Construction / Runtime Efficiency — Concurrency contexts.
• [P1] CS2023 - OS/Operating System Principles (Concurrency) — Core requirements.

Secondary

• [Linux Kernel Development] Robert Love — Practical kernel synchronization.
• [The Art of Multiprocessor Programming] Herlihy — Theoretical foundations.

Industry

• [Kernel.org: Spinlocks and Locking in Linux] — The definitive locking guide.
• [Microsoft: Synchronization Primitives in the Windows Kernel] — NT kernel specifics.

9. Final Checklist

Primary

• '원자적 연산(Atomic Operation)'이 왜 소프트웨어 관례만으로는 충분하지 않고 하드웨어 명령어의 도움을 받아야 하는지 설명 가능한가? (P1)
• '교착 상태(Deadlock)'의 4가지 발생 조건 중 하나를 제거함으로써 시스템을 어떻게 복구할 수 있는지 설명할 수 있는가? (P1)

Secondary

• '스핀락'과 '뮤텍스' 중 어떤 것을 선택할지 결정할 때, 임계 영역의 소요 시간과 문맥 교환 비용을 비교하여 제시할 수 있는가?
• 인터럽트가 활성화된 채로 공유 자원을 수정할 때, 왜 상호 배제가 깨질 수 있는지 시나리오를 설명할 수 있는가?

Industry

• 리눅스 커널의 'RCU(Read-Copy-Update)' 기법이 왜 전통적인 락 방식보다 초당 수백만 건의 읽기 요청 처리(Scalability)에 유리한지 설계 관점에서 제안할 수 있는가? (SFIA)
• 멀티코어 임베디드 시스템에서 스핀락을 과도하게 사용할 때 발생하는 '캐시 바운싱(Cache Bouncing)' 현상이 전체 하드웨어 대역폭에 미치는 영향을 기술할 수 있는가?