동기화 (Synchronization)

동기화는 멀티 프로세스 또는 멀티 스레드 환경에서 여러 주체가 공유 자원(Shared Resource)에 동시에 접근할 때, 데이터의 일관성(Consistency)과 무결성(Integrity)을 유지하도록 접근 순서를 제어하는 것

즉, 공유 자원에 동시에 접근하여 예상치 못한 결과를 초래하는 경쟁 상태(Race Condition)를 방지하는 것이 주된 목적

경쟁 상태 (Race Condition)

• 여러 프로세스/스레드가 동시에 공유 자원에 접근하여 최종 실행 결과가 접근 순서에 따라 달라지는 상황
• 동기화의 가장 기본적인 문제 상황이며, Critical Section 문제가 발생하는 원인

Critical Section 문제 (임계 구역 문제)

임계 구역(Critical Section)이란 둘 이상의 프로세스/스레드가 공유 데이터(변수, 파일 등)에 접근하고 변경하는 코드 영역

Critical Section 문제는 여러 프로세스가 동시에 임계 구역에 진입하여 공유 데이터를 변경하려 할 때 발생할 수 있는 데이터 불일치 문제를 해결하는 것

이 문제를 해결하기 위해서는 다음 세 가지 조건이 보장되어야 한다.

1. 상호 배제 (Mutual Exclusion): 한 프로세스가 임계 구역에 들어가 있으면, 다른 프로세스는 임계 구역에 들어갈 수 없다.
2. 진행 (Progress): 임계 구역에 아무도 없고 들어가려는 프로세스가 있다면, 이들 중 어떤 프로세스가 진입할 지를 유한한 시간 안에 결정해야 한다 (무한 대기 방지).
3. 한정된 대기 (Bounded Waiting): 한 프로세스가 임계 구역에 진입하려 요청한 후부터 실제로 진입이 허용될 때까지, 다른 프로세스들이 임계 구역에 진입하는 횟수에 제한이 있어야 한다 (기아(Starvation) 방지).

기아 (Starvation)

• 특정 프로세스/스레드가 자원을 할당받지 못하고 영원히 대기하는 상태
• 이는 잘못된 동기화 정책이나 자원 할당 정책(예: 낮은 우선순위)으로 인해 발생할 수 있다. 한정 대기(Bounded Waiting) 조건을 만족시키지 못하면 발생

---

뮤텍스, 세마포어, 모니터

이들은 Critical Section 문제를 해결하기 위한 대표적인 동기화 도구(Synchronization Tools)

뮤텍스(Mutex: Mutual Exclusion)

• 이진 잠금 장치 (lock/unlock 두 상태만 있음)
• 한 번에 하나의 스레드만 자원을 사용할 수 있도록 보장
• 소유 개념이 있어서 lock을 건 스레드만 unlock 가능

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER; // 1. 뮤텍스 객체 선언 및 초기화
...
do {
	pthread_mutex_lock(&mutex); // 2. Lock 획득 시도: 성공 시 임계 구역 진입, 실패 시 Lock 해제될 때까지 대기 상태(Block) 전환
    ...
    //critical section // 3. 임계 구역: Lock을 획득한 하나의 스레드/프로세스만 실행
    ...
    pthread_mutex_unlock(&mutex); // 4. Lock 반납: 임계 구역 작업 후, Lock 해제
}

세마포어(Semaphore)

• 정수 값 기반 동기화 도구
• P(wait)와 V(signal) 연산을 사용
• 종류
  • Binary Semaphore → 뮤텍스와 유사 (0/1 값만 가짐)
  • Counting Semaphore → 특정 개수의 자원 동시 접근 허용

sem_t semaphore;

sem_init(&semaphore, 0, 3); // 1. 공유 가능한 자원을 수 3으로 초기화
...
do {
	sem_wait(&semaphore); // 2. P() 연산: 자원 획득, 카운트 감소
    ...
    //critical section
    ...
    sem_post(&semaphore); // 3. V() 연산: 자원 반납, 카운트 증가
}

모니터(Monitor)

• 고수준 언어 수준에서 제공되는 동기화 추상화 도구
• 공유 자원과 해당 자원을 조작하는 메서드, 그리고 동기화 기법을 하나의 모듈로 묶음
• 프로세스는 모니터를 통해서만 자원 접근 → 자동으로 상호 배제 보장

class ResourceManager {
    private int availableResources = 3; // 공유 자원

    // 메서드 전체에 Lock을 걸어 상호 배제를 보장
    public synchronized void acquireResource(int needed) throws InterruptedException {
        // [자동 Lock 획득] - 메서드 진입 시 자동

        // 2. 조건 대기 (Condition Wait)
        while (availableResources < needed) {
            // 자원이 부족하면 대기 큐로 이동. Lock을 반납함.
            this.wait(); 
        }

        // 조건 충족: 자원 사용
        availableResources -= needed;
        
        // [자동 Lock 해제] - 메서드 종료 시 자동
    }

    public synchronized void releaseResource(int amount) {
        // [자동 Lock 획득] - 메서드 진입 시 자동
        
        // 자원 반납
        availableResources += amount;

        // 대기 중인 스레드 깨우기
        // wait() 상태인 스레드 중 하나를 깨워 경쟁하도록 함 (모니터의 signal() 역할)
        this.notify(); // 또는 this.notifyAll();

        // [자동 Lock 해제] - 메서드 종료 시 자동
    }
}

정리

구분	뮤텍스 (Mutex)	세마포어 (Semaphore)	모니터 (Monitor)
개념	상호 배제(Mutual Exclusion)를 위한 잠금(Lock) 메커니즘.	신호 메커니즘을 사용하는 동기화 도구. 공유 자원에 접근 가능한 프로세스/스레드의 수를 정수 변수로 관리.	공유 자원과 이에 접근하는 프로시저(함수)들을 하나로 묶어 상호 배제를 달성하는 고급 동기화 구조체.
자원 수	동기화 대상이 1개일 때 사용 (Binary Semaphore와 유사).	동기화 대상이 1개 이상일 때 사용 (Counting Semaphore). 1개일 경우 이진 세마포어.	일반적으로 공유 자원을 보호하며 상호 배제를 보장.
소유	Lock을 획득한 (소유한) 스레드/프로세스만이 Lock을 해제(반납)할 수 있음.	Lock을 소유하지 않은 스레드/프로세스도 Signal(V 연산)을 통해 자원 사용 가능 수를 증가시킬 수 있음.	내부적으로 상호 배제를 자동 보장하며, 조건 변수(Condition Variable)를 통해 복잡한 동기화를 처리.
구현	Lock/Unlock (또는 Wait/Signal의 일종) 연산을 사용.	P() (Wait, 감소)와 V() (Signal, 증가) 두 가지 원자적(Atomic) 연산을 사용.	컴파일러가 상호 배제를 처리해주므로, 사용자가 직접 Lock/Unlock 관리를 할 필요가 적어 오류 발생 가능성이 낮음.

Busy Waiting (바쁜 대기)

• 어떤 프로세스/스레드가 임계 구역에 진입하기 위해 Lock이 해제될 때까지 반복문(Loop)을 돌면서 대기하는 방식
• CPU를 계속 사용하면서 대기하므로 자원의 낭비가 심하며, 성능 저하의 원인이 될 수 있다. 세마포어나 모니터는 일반적으로 Busy Waiting을 피하기 위해 대기 중인 프로세스를 Block(정지) 상태로 전환

---

교착 상태 (Deadlock)

교착 상태(Deadlock)란 둘 이상의 프로세스가 서로 상대방이 점유하고 있는 자원을 기다리면서, 무한히 대기하는 상태. 이 상태에 빠진 프로세스는 더 이상 작업을 진행할 수 없다.

Deadlock 발생 조건

교착 상태가 발생하기 위해서는 다음 네 가지 조건이 모두 동시에 충족되어야 한다.

1. 상호 배제 (Mutual Exclusion): 한 번에 프로세스 하나만 자원을 사용할 수 있다. (공유 불가능한 자원)
2. 점유와 대기 (Hold and Wait): 자원을 최소한 하나 보유하고 있는 프로세스가, 다른 프로세스에 할당된 자원을 추가로 얻기 위해 대기
3. 비선점 (No Preemption): 이미 할당된 자원은 해당 프로세스가 사용을 끝내고 자발적으로 반납하기 전까지는 강제로 빼앗을 수 없다.
4. 순환 대기 (Circular Wait): 대기하는 프로세스의 집합이 순환 형태로 자원 대기 (예: P1은 R2를, P2는 R1을 기다림)

---

Deadlock 해결 방법

교착 상태를 해결하는 접근 방식은 크게 네 가지이다.

해결 방법	설명
Deadlock 예방 (Prevention)	교착 상태 발생 조건 4가지 중 하나 이상을 부정하여 교착 상태가 애초에 발생하지 않도록 합니다. (예: 자원을 한 번에 모두 할당, 선점 허용 등)
Deadlock 회피 (Avoidance)	자원 요청 시 시스템을 안전 상태(Safe State)로 유지할 수 있는 경우에만 자원을 할당합니다. 대표적으로 은행원 알고리즘 (Banker's Algorithm)
Deadlock 탐지 및 회복 (Detection & Recovery)	교착 상태 발생을 허용하되, 주기적으로 교착 상태를 탐지하고, 발생하면 강제로 프로세스를 종료하거나 자원을 선점하여 교착 상태에서 벗어남
Deadlock 무시 (Ignorance)	교착 상태가 매우 드물게 발생한다고 가정하고, 운영체제가 아무런 조치도 취하지 않는 방식 (가장 일반적인 접근 방식)

+자료에 따라 교착상태 복구 (recovery)를 4번째 방법으로 정리함

Deadlock 복구 (Recovery) = 교착 상태를 일으킨 프로세스를 종료하거나 할당된 자원을 해제시키는 방법.