[운영체제 공룡책] 6장 Synchronization Tools(동기화 도구)

6.1 Background

 

1. 동시성 및 병렬성
   • 프로세스는 동시성(concurrent) 또는 병렬성(parallel)을 통해 실행될 수 있다.
   • CPU 스케줄러는 프로세스 간 빠르게 전환하며 동시 실행을 가능하게 한다.
   • 병렬성은 여러 프로세스가 별도의 처리 코어에서 동시에 실행되는 것을 의미한다.
2. 공유 데이터와 무결성 문제
   • 여러 프로세스가 공유 데이터를 동시에 수정할 때 데이터 무결성 문제가 발생할 수 있다.
   • 예로 생산자-소비자 문제가 있으며, 공유 메모리에서 데이터의 생산과 소비를 조율한다.
3. 레이스 조건(Race Condition)
   • 여러 프로세스가 동일한 데이터에 접근해 조작할 때 실행 순서에 따라 결과가 달라지는 상황을 의미한다.
4. 동기화 필요성
   • 레이스 조건을 방지하려면 공유 데이터에 대해 하나의 프로세스만 접근 가능하도록 프로세스 동기화(process synchronization)가 필요하다.

---

6.2 The Critical-Section Problem

임계 구역(Critical Section) 문제

• 정의: 여러 프로세스가 동시에 공유 데이터를 접근하고 수정하는 경우, 데이터 무결성을 보장하기 위해 동기화 프로토콜을 설계해야 하는 문제.
• 각 프로세스는 임계 구역에 진입하기 전에 진입 코드(entry section)를 실행하고, 임계 구역 실행 후 종료 코드(exit section)를 실행함.

while (true) {
    entry section
        critical section
    exit section
        remainder section
}

 

---

해결 조건

1. 상호 배제(Mutual Exclusion)
   • 한 프로세스가 임계 구역에서 실행 중일 때, 다른 프로세스는 임계 구역에 진입할 수 없어야 함.
2. 진행성(Progress)
   • 어떤 프로세스도 임계 구역에 없고, 특정 프로세스가 임계 구역에 진입하고자 한다면, 해당 프로세스들이 적절한 시간 내에 진입할 수 있도록 보장해야 함.
3. 유한 대기(Bounded Waiting)
   • 한 프로세스가 임계 구역에 진입 요청 후, 다른 프로세스들이 임계 구역에 진입할 수 있는 횟수에 상한이 있어야 함.

---

임계 구역 처리 방식

1. 선점형 커널(Preemptive Kernel)
   • 커널 모드에서 실행 중인 프로세스를 중단(preemption) 가능.
   • 장점:
     • 높은 응답성 (실시간 프로그래밍에 적합).
     • 대기 중인 프로세스가 프로세서를 사용할 수 있는 가능성 증가.
   • 단점:
     • 레이스 조건 발생 가능성 증가 → 설계의 복잡성 증가.
     • 특히 다중 프로세서(SMP) 환경에서 문제 심화.
2. 비선점형 커널(Nonpreemptive Kernel)
   • 커널 모드에서 실행 중인 프로세스는 종료, 블록, 자발적 CPU 반환 전까지 중단되지 않음.
   • 장점:
     • 레이스 조건에 안전.
     • 커널 데이터 구조 보호 용이.
   • 단점:
     • 응답성이 낮아질 가능성.
     • 특정 프로세스가 장시간 CPU를 독점할 위험.

---

6.6 Semaphores

• 정의: 세마포어는 정수 변수로, 두 가지 원자적 연산 wait()와 signal()로만 접근 가능.
  • wait(S): 세마포어 값을 감소시키고, 0 이하일 경우 대기.
  • signal(S): 세마포어 값을 증가시키고, 대기 중인 프로세스를 깨움.

---

6.6.1 Semaphore Usage

1. 유형:
   • 카운팅(counting) 세마포어: 값이 제한 없이 증가/감소 가능, 여러 자원 관리에 사용.
   • 이진 세마포어(binary): 값이 0과 1 사이, 뮤텍스(Mutex)와 유사하게 작동.
2. 자원 접근 제어:
   • 세마포어 값은 자원 개수를 나타냄.
   • wait()으로 자원 사용 시 값을 감소, signal()로 자원 해제 시 값을 증가.
   • 세마포어 값이 0이면 모든 자원이 사용 중이며, 대기 발생.
3. 프로세스 동기화:
   • 한 프로세스의 작업(S1)이 완료된 후 다른 프로세스(S2)가 실행되도록 보장 가능.
   • 예: 세마포어를 0으로 초기화하고 signal()과 wait()를 적절히 사용.

 

---

6.6.2 Semaphore Implementation

 

세마포어 구조:

typedef struct {
    int value;
    struct process *list;
} semaphore;

 

• value: 세마포어 값.
• list: 대기 중인 프로세스 리스트.

 

 

세마포어 연산:

wait(semaphore *S) {
    S->value--;
    if (S->value < 0) {
        add this process to S->list;
        sleep();
    }
}

 

• wait(): 세마포어 값을 감소. 0 이하이면 프로세스를 대기 리스트에 추가하고 대기.

 

signal(semaphore *S) {
    S->value++;
    if (S->value <= 0) {
        remove a process P from S->list;
        wakeup(P);
    }
}

• signal(): 세마포어 값을 증가. 대기 리스트에서 프로세스를 제거하고 실행 재개.

---

 

세마포어 문제점과 해결책

1. 바쁜 대기(Busy Waiting):
   • 기존의 wait()와 signal()는 바쁜 대기를 포함.
   • 개선된 구현에서는 대기 상태로 전환하여 CPU 자원을 낭비하지 않음.
2. 원자성 보장 필요:
   • wait()와 signal() 연산은 원자적으로 실행되어야 함.
   • 단일 프로세서 환경: 인터럽트를 비활성화하여 구현.
   • 다중 코어(SMP) 환경: compare_and_swap() 또는 스핀락(Spinlock) 사용.
3. 완전한 바쁜 대기 제거의 어려움:
   • 임계 구역에서의 바쁜 대기는 여전히 존재 가능하지만, 짧은 코드로 제한하여 비효율성을 최소화.

---

6.7 Monitors

---

6.7.1 Monitor Usage 

• 모니터(Monitor)는 데이터와 이를 다루는 함수들이 포함된 추상 데이터 타입(ADT)이다.
• 모니터 내에서는 상호 배제(mutual exclusion)가 자동으로 보장된다. 즉, 동시에 하나의 프로세스만 모니터에 접근할 수 있다.
• 조건 변수(Condition Variables)는 모니터 내에서 프로세스 간 동기화를 위한 추가 메커니즘이다. 조건 변수는 wait()와 signal() 연산을 제공하며, 이를 통해 특정 조건을 기다리거나 신호를 보낼 수 있다.
  • wait(): 조건이 만족될 때까지 현재 프로세스를 대기 상태로 만든다.
  • signal(): 대기 중인 프로세스 중 하나를 깨운다.
• 모니터의 특징:
  • 프로세스는 모니터를 직접적으로 사용하지 않으며, 모니터 내의 함수만 호출 가능하다. 따라서 동기화 문제를 프로그래머가 명시적으로 처리할 필요 없이 모니터가 이를 자동으로 처리한다.

Monitor with condition variables

---

6.7.2 Implementing a Monitor Using Semaphores

• 모니터의 세마포어 구현 방법:
  • mutex 세마포어: 모니터에 대한 상호 배제를 보장.
  • next 세마포어: 프로세스가 signal() 후 대기하도록 만든다.
  • x.count: 대기 중인 프로세스 수를 추적.

구현 단계:

• wait()과 signal()이 mutex와 next 세마포어를 통해 동기화된다.
• 조건 변수를 처리하기 위해, 각 조건에 대해 세마포어와 카운터를 사용한다.
• wait()와 signal()에서 대기와 깨우기 작업을 세마포어를 통해 처리하여, 여러 프로세스가 동시에 모니터에 들어가지 않도록 한다.

x.wait() {
    x.count++;
    if (next.count > 0) signal(next);
    else signal(mutex);
    wait(x.sem);
    x.count--;
}

x.signal() {
    if (x.count > 0) {
        next.count++;
        signal(x.sem);
        wait(next);
        next.count--;
    }
}

 

---

6.7.3 Resuming Processes within a Monitor

• 프로세스 재개 순서:
  • 여러 프로세스가 대기 중일 때, FCFS(First-Come-First-Served) 방식으로 처리하는 것이 일반적이다.
  • 우선순위 기반 재개 방법을 사용할 수도 있는데, 이 경우 x.wait(c)에서 c는 프로세스의 우선순위를 나타내며, 우선순위가 낮은 프로세스부터 재개된다.
• 재개 방식:
  • signal()을 호출한 프로세스는 대기 중인 프로세스 중 하나를 깨우고, 그 프로세스가 실행을 마친 후 신호를 보낸 프로세스가 계속 실행된다.
  • Signal and wait 또는 Signal and continue 방법으로 두 가지 주요 선택지가 있다.
    • Signal and wait: 신호를 보낸 프로세스는 대기하고, 신호를 받은 프로세스만 실행된다.
    • Signal and continue: 신호를 보낸 프로세스가 계속 실행된다.
• 문제 해결:
  • 모니터는 상호 배제를 보장하지만, 조건 변수를 통해 프로세스 재개 순서를 FCFS 또는 우선순위 기반으로 조정할 수 있다.
  • 프로세스 재개 순서를 명확히 지정하여 동기화 오류를 최소화하는 방법을 선택한다.

---

6.8 Liveness

• 시스템이 실행되는 동안 프로세스들이 계속해서 진행될 수 있도록 보장하는 특성이다.
• 프로세스가 무한히 대기하는 것은 "liveness failure(생명성 실패)"로 간주되며, 이는 시스템의 성능과 반응성을 저하시킨다.
• 무한 루프나 busy wait(계속해서 대기만 하는 상태)는 생명성 실패의 예시로, 동기화 도구인 mutex locks와 semaphores를 사용할 때 발생할 수 있다.

---

6.8.1 Deadlock

• Deadlock(교착 상태)는 두 개 이상의 프로세스가 서로가 실행해야 할 signal() 연산을 기다리고 있는 상태로, 이 상태에 빠지면 프로세스들이 무한히 기다리게 된다.

---

6.8.2 Priority Inversion

 

• Priority Inversion(우선순위 역전)은 낮은 우선순위 프로세스가 자원을 점유하고 있을 때, 높은 우선순위 프로세스가 그 자원을 기다려야 하는 상황에서 발생한다. 이때, 낮은 우선순위 프로세스가 선점되어 높은 우선순위 프로세스의 대기 시간이 늘어날 수 있다.

예시:

• 프로세스 L(낮은 우선순위), M(중간 우선순위), H(높은 우선순위)가 있을 때, 프로세스 H가 세마포어 S를 필요로 하지만, L이 이를 점유하고 있을 때, M이 L을 선점하게 되어 H가 기다려야 하는 시간이 늘어난다.

Priority Inversion 문제 해결 방법:

• 우선순위 상속( Priority Inheritance) 프로토콜을 사용한다. 이 프로토콜은 낮은 우선순위 프로세스가 높은 우선순위 프로세스가 필요한 자원을 점유할 경우, 낮은 우선순위 프로세스가 임시로 높은 우선순위를 물려받아 높은 우선순위 프로세스의 대기를 방지한다.
• L이 H의 우선순위를 임시로 물려받고, M이 L을 선점하는 상황을 방지할 수 있다.