중복배제
중복배제(重複排除, Mutual Exclusion)는 여러 프로세스·스레드가 공유 자원을 동시에 접근하는 상황에서, 하나의 실행 흐름만이 해당 자원을 이용하도록 보장하는 동기화 메커니즘을 의미한다. 주로 병행·병렬 컴퓨팅, 실시간 시스템, 데이터베이스 트랜잭션 등에서 경쟁 조건(race condition)과 데이터 일관성 오류를 방지하기 위해 사용된다.
정의
- 중복배제는 동시성 제어의 한 형태로, 임계 구역(critical section)이라 불리는 코드 블록에 동시에 하나 이상의 실행 단위가 진입하지 못하도록 제한한다.
- 이를 통해 데이터 무결성, 프로세스 간 충돌 방지, 시스템 안정성을 확보한다.
원리
-
잠금(Lock) 메커니즘
스핀락, 뮤텍스(mutex), 세마포어(semaphore) 등은 중복배제를 구현하기 위한 대표적인 도구이다.- 뮤텍스는 오직 하나의 스레드만 잠금을 획득할 수 있도록 하며, 해제 시 다른 대기 중인 스레드에게 잠금이 양도된다.
- 스핀락은 잠금을 대기하는 동안 CPU를 계속 사용해 바쁜 대기(busy‑wait)를 수행한다.
-
다중 버전 동시성 제어(MVCC)
데이터베이스에서는 잠금을 최소화하기 위해 버전 관리를 이용한다. 이 경우 중복배제는 레코드 수준에서 선택적 적용된다. -
원자성(Atomicity) 보장
하드웨어 수준에서는 테스트‑그리고‑세트(Test‑and‑Set), 교환(Compare‑And‑Swap, CAS) 같은 원자 연산을 이용해 잠금 상태를 변경한다.
구현 방법
| 방법 | 특징 | 장점 | 단점 |
|---|---|---|---|
| 뮤텍스 | 커널 혹은 사용자 수준 라이브러리 구현 | 비교적 간단, 교착 상태 방지 기능 포함 | 시스템 콜 오버헤드 |
| 스핀락 | 바쁜 대기 방식 | 짧은 임계 구역에 효율 | CPU 자원 낭비 |
| 세마포어 | 카운터 기반, 다중 접근 허용 | 제한된 동시성 제어 가능 | 복잡한 해제 관리 |
| 리드/라이트 락 | 읽기 전용 접근은 동시 허용 | 읽기 비중 높은 경우 성능 개선 | 쓰기 시 전체 차단 |
| 잠금 프리 알고리즘 | 락 없이 원자 연산 활용 | 교착 상태 없음, 높은 병렬성 | 구현 난이도 높음 |
관련 용어
- 경쟁 조건(Race Condition): 두 개 이상의 실행 흐름이 예상치 못한 순서로 자원에 접근해 오류가 발생하는 상황.
- 교착 상태(Deadlock): 상호 배제와 자원 점유가 얽혀 시스템이 정지하는 현상.
- 동시성(Concurrency) vs 병렬성(Parallelism): 전자는 논리적 동시에 진행되는 작업, 후자는 물리적으로 동시에 실행되는 작업을 의미한다.
- 임계 구역(Critical Section): 중복배제가 적용되는 코드 블록.
적용 사례
- 운영체제 커널
- 프로세스 스케줄러가 프로세스 제어 블록(PCB) 자료구조를 수정할 때 뮤텍스를 사용한다.
- 데이터베이스 트랜잭션
- 두 트랜잭션이 동일한 레코드를 동시에 업데이트하려 할 때 레코드 잠금을 통해 중복배제를 수행한다.
- 멀티스레드 애플리케이션
- 공유 버퍼에 데이터를 삽입·삭제하는 생산자·소비자 패턴에서 조건 변수와 뮤텍스를 결합한다.
역사
- 1960년대 초반, Edsger W. Dijkstra가 세마포어 개념을 제시하면서 중복배제 개념이 정식화되었다.
- 이어 1970년대에 Tony Hoare가 모니터(monitor) 구조를 도입, 프로그래밍 언어 수준에서 중복배제를 지원하도록 발전시켰다.
- 현대에는 멀티코어 프로세서와 분산 시스템의 확산으로, 락‑프리(Lock‑free)·무잠금(No‑Lock) 알고리즘이 활발히 연구되고 있다.
참고 문헌
- Dijkstra, E. W. (1965). Cooperating Sequential Processes. Programming Languages.
- Hoare, C. A. R. (1974). Monitors: An Operating System Structuring Concept. Communications of the ACM.
- Anderson, J., & Dahlin, M. (2014). Operating Systems: Principles and Practice (2nd ed.). Wiley.
- Herlihy, M., & Shavit, N. (2012). The Art of Multiprocessor Programming (Revised 2nd ed.). Morgan Kaufmann.
이 문서는 2026년 현재까지 확인된 중복배제 관련 학술·산업 정보를 종합하여 작성하였다.