상호 배제 (Mutual Exclusion)

여러 프로세스나 스레드가 공유 자원에 동시에 접근하는 것을 방지하는 동기화 메커니즘.
한 번에 하나의 프로세스나 스레드만 임계 영역(critical section)에 진입할 수 있도록 보장하는 기법이다.

필요한 이유:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

# 상호 배제가 없는 경우의 문제점
class BankAccount:
    def __init__(self):
        self.balance = 1000
    
    def withdraw(self, amount):
        # 다음 세 줄의 작업이 원자적이지 않음
        current_balance = self.balance  # 잔액 읽기
        current_balance = current_balance - amount  # 계산
        self.balance = current_balance  # 결과 저장
        
# 두 스레드가 동시에 실행되면 문제가 발생할 수 있음
account = BankAccount()
# 스레드 1: withdraw(500)
# 스레드 2: withdraw(500)
# 예상 잔액: 0, 실제 잔액: 500 (잘못된 결과)

목적

  • 데이터 무결성 유지: 여러 프로세스가 동시에 공유 데이터를 수정하는 것을 방지한다.
  • 경쟁 조건(Race Condition) 예방: 프로세스 실행 순서에 따른 결과 불일치를 막는다.
  • 교착 상태(Deadlock)와 기아 상태(Starvation) 방지: 자원 할당의 효율성을 높인다.

구현 방법

  1. 잠금(Lock)
    가장 기본적인 동기화 메커니즘으로, 한 번에 하나의 스레드만 임계 영역에 접근할 수 있게 한다.

  2. 세마포어(Semaphores)
    여러 스레드가 동시에 접근할 수 있는 자원의 수를 제한한다.

  3. 모니터(Monitor)
    모니터는 객체 지향적인 동기화 메커니즘으로, 데이터와 해당 데이터에 접근하는 메서드들을 하나의 단위로 캡슐화한다.

  4. 조건 변수(Condition Variable)
    스레드가 특정 조건이 만족될 때까지 대기하게 해주는 동기화 메커니즘.
    생산자-소비자 패턴에서 자주 사용된다.

  5. 원자적 연산 (Atomic Operations)
    하드웨어 수준에서 지원하는 원자적 연산을 사용하여 상호 배제를 구현할 수 있다.

  6. 메시지 패싱 (Message Passing)
    프로세스나 스레드 간에 메시지를 주고받아 상호 배제를 구현할 수 있다.

  7. 비동기 프로그래밍 (Asynchronous Programming)
    비동기 프로그래밍을 통해 상호 배제를 구현할 수 있다.

  8. 피터슨 알고리즘 (Peterson’s Algorithm)
    두 프로세스 간의 상호 배제를 소프트웨어적으로 구현하는 방법.
    플래그와 턴 변수를 사용하여 임계 영역 진입을 제어한다.

  9. 데커 알고리즘 (Dekker’s Algorithm)
    피터슨 알고리즘과 비슷하지만 더 복잡한 구조를 가진 상호 배제 알고리즘.

  10. 램포트의 빵집 알고리즘 (Lamport’s Bakery Algorithm)
    여러 프로세스 간의 상호 배제를 구현할 수 있는 알고리즘.
    빵집에서 번호표를 뽑는 것과 같은 방식으로 작동한다.

동기화 메커니즘은 서로 다른 상황에서 유용하다:

  • Lock은 간단한 상호 배제가 필요할 때 사용
  • Semaphore는 리소스 풀 관리에 적합
  • Monitor는 데이터와 연산을 함께 캡슐화할 때 유용
  • Condition Variables는 스레드 간 시그널링이 필요할 때 사용

조건

  • 상호 배제: 한 번에 하나의 프로세스만 임계 영역에 진입할 수 있어야 한다.
  • 진행: 임계 영역 외부의 프로세스가 다른 프로세스의 진입을 방해해서는 안 된다.
  • 유한 대기: 프로세스는 임계 영역 진입을 무한정 기다리지 않아야 한다.

참고 및 출처