[OS 기초] 06. 병행성: 교착상태와 기아

[ 교착상태 원리 ]
• 교착상태 정의
- 2개 이상의 프로세스가 서로가 가진 자원을 기다리며, 아무도 작업을 진행하지 못하는 무한 대기 상태
- 2개 이상의 프로세스들이 공유 자원에 대한 경쟁이나 통신 중에 발생 (다른 블록 된 프로세스의 자원을 기다리면서 자신도 블록)
 

t교착상태 예시

공유 자원 : 교차로 구간 / 프로세스 및 쓰레드(경쟁 task) : 자동차

• 결합 진행 다이어그램
두 자원을 동시에 얻어야 진행이 되는 상황이라 가정
교착 상태 발생 여부를 확인하기 위해 쓰임 (가능성 판단)

교착상태 발생

 

교착상태 발생 다이어그램

 
Q. 자원, 할당 반납 순서가 바뀌면 어떻게 될까?
자원 할당, 반납 순서만 바뀌어도 교착상태 발생의 유무가 달라진다.
 
* 자원 확보 순서가 중요
얻은 후 자원을 바로 푸는 방식

교착상태가 발생하지 않는 다이어그램

 
 
• 교착상태 다른 예들
– 메모리 할당 (가용 메모리 크기 = 200 Kbytes)

메모리 할당

단독으로 수행 시 문제없이 수행 가능
 
동시 진행 시 P1 80 Kbytes → P2 70 Kbytes 여기까지만 수행되고 두 프로세스 모두 필요한 메모리를 얻을 수 없는 상태가 발생
 
 
– 통신 (Receive와 Send순으로 송수신)
두 프로세스를 동시에 진행 시 둘 다 수신을 대기하는 상태 → 모두 진행이 불가한 상황 발생

통신

 
• 자원 종류
< 재사용 가능 자원 (reusable) / 소모성 자원 (consumable) >
 
1. 재사용 가능 자원 (Reusable Resource)
한 번 사용하고 나면 사라지는 것이 아니라, 반납 후 다시 사용할 수 있는 자원

• 특징 (Definition)
  • 한 번에 하나의 프로세스만 안전하게 사용 가능 (상호 배제)
  • 사용된다고 해서 고갈되거나 사라지지 않는다. (is not depleted)
• 대표적인 예
  • 하드웨어: 프로세서(CPU), I/O 채널, 메인/보조 메모리, 각종 장치(Devices)
  • 소프트웨어/데이터: 파일(Files), 데이터베이스(Databases), 세마포어(Semaphores) 등
• 교착상태 발생 원인
  • 각 프로세스가 하나의 자원을 점유(Hold)하고 있는 상태에서, 상대방이 가진 다른 자원을 요청(Request)할 때 발생
  • 사례: 메모리 할당 경쟁, 디스크와 테이프 장치 경쟁 등

2. 소모성 자원 (Consumable Resource)
생성되고 사용되면 사라지는 일회성 자원

• 특징 (Definition)
  • 생성(Produced)될 수 있고, 사용되면 파괴(Destroyed/Consumed)되는 자원
  • 누군가에 의해 생산되고 소비되면서 사라지는 유형 (일회성 처리)
• 대표적인 예시 (Examples)
  • 통신/신호: 인터럽트(Interrupts), 시그널(Signals), 메시지(Messages)
  • 데이터: I/O 버퍼 내의 정보
• 교착상태 발생 원인
  • 주로 블로킹(Blocking) 연산 때문에 발생한다. 메시지를 받아야 다음으로 넘어가는 Receive 상태에서, 필요한 메시지가 영원히 생성되지 않는 경우
  • 사례: 통신사 사례 (두 프로세스가 서로에게 메시지를 보내지 않고 받으려고만 기다리는 상황)
    → 인터럽트 · 시그널 발생 시 처리를 하면서 해당 인터럽트 · 시그널은 소모됨
         메시지 또한 메시지 큐에서 메시지를 큐에서 꺼내서 처리 후 소모

교착상태의 양상은 일회성인지, 가용한 자원의 개수에 따라서도 달라짐
 
• 자원 할당 그래프 (Resource Allocation graph)
 

교착상태 발생 가능성 판단

(a) 각 프로세스가 점유한 자원이 있는 상태에서 나머지 자원 또한 획득하려고 하면 환형 대기가 발생
(b) chain이 만들어진다고 무조건 교착 상태가 발생하는 건 아님! → 가용한 자원의 수에 따라 다름
 

자원 할당 그래프의 유용성

P1이 Ra를 점유, P1이 Rb를 요청 / P2가 Rb를 점유, Rc를 요청 / P3가 Rc를 점유, Rd를 요청 / P4가 Rd를 점유, Ra를 요청
다수의 프로세스와 다수의 자원이 존재하는 상황에서도 환형 대기가 발생할 수 있다. 
 
• 교착상태 발생의 4가지 필요조건
교착상태 가능 vs 교착상태 발생

– 상호배제 (mutual exclusion) :  공유 자원이 존재하는 임계 영역을 보호하기 위해, 한 시점에 하나의 프로세스만 자원을 사용하도록 허용하는 조건. 즉, 누군가 자원을 사용 중이라면 다른 프로세스는 절대 접근할 수 없는 배타적인 상태를 의미
– 점유대기 (hold and wait) : 이미 자원을 보유(Hold)하고 있으면서, 작업을 마치는 것이 아니라 추가 자원을 요청하며 대기(Wait)하고 있는 상태
– 비선점 (no preemption) : 다른 프로세스가 점유한 자원은 그 프로세스가 사용을 마치고 스스로 반납하기 전까지는 강제로 회수(선점)할 수 없는 상황 (선점 불가)
– 환형대기 (circular wait) : 자원 할당 그래프를 그렸을 때, 프로세스들이 서로가 가진 자원을 요청하며 꼬리에 꼬리를 무는 원형 사슬(Cycle) 형태
→  해결하기 위해 이 네 가지 상황이 발생하지 않도록 차단하는 것이 필요! / 차단시킬 수 없는 게 문제임 (애초에 배제가 불가)
      공유 자원을 두고 동시 접근 시 비결정성 문제가 발생되므로 상호배제 필수인데 이를 배제하는 게 불가
 
• 교착상태 해결을 위한 3가지 접근 방법
< 교착상태 예방, 회피, 발견 >
 
[ 교착상태 예방 (deadlock prevention) ]
(미리 대응방법을 마련) 교착상태가 애초에 발생하지 못하도록 차단하는 방식
: 앞서 살펴본 교착상태 발생 4가지 필요조건 (상호 배제, 점유 대기, 비선점, 환형 대기) 중 하나 이상을 설계 단계에서 배제하는 기법 → 현실적으로 어려움
교착상태는 확실히 막을 수 있지만, 자원 낭비가 심하거나 시스템 효율성이 떨어질 수 있다.
 
① 간접적 예방 (Indirect Prevention)
교착상태가 발생하기 위한 구조적 조건 (3가지 필요조건 : 상호 배제, 점유 대기, 비선점) 중 하나를 불가능하게 만든다.
 

• 상호 배제 부정: 자원을 공유 가능하게 만든다. (현실적으로 불가능, 운영체제에서 반드시 보장해 주어야 함)
• 점유 대기 부정: 프로세스 시작 시 모든 자원을 한꺼번에 요청하거나, 자원이 없을 때만 요청하게 한다. (자원 낭비 심함)
• 비선점 부정: 자원을 점유한 프로세스가 다른 자원을 기다려야 하면 (필요한 자원 모두 확보하지 못하면), 가진 자원을 포기한다. (작업 내용을 잃을 수 있음)
  • 협력형 멀티 태스킹, 선점형 멀티 태스킹으로 구분
  • 협력형 : 시간 할당을 받고 수행되는 과정에서 스스로 CPU사용 포기하거나, I/O요청에 의해 block이 아닌 이상 다른 프로세스가 중단시킬 수 없음
  • 선점형 : 시간 할당이 남아서 작업을 수행하는 프로세스가 있음에도 불구하고 더 우선순위가 높은 프로세스가 존재할 때 이전에 수행 중인 프로세스의 실행을 중단시키는 걸 허용

 
예방에 관련 방법을 적용했을 때 부하가 큼. 가능은 하지만 현실적으로 효율성이 매우 떨어짐
 
② 직접적 예방 (Direct Prevention)
교착상태의 결과적인 형태인 환형 대기가 만들어지지 않도록 예방
 

• 효율성 저하: 안 쓸 자원도 미리 잡아두거나(점유 대기 부정), 불필요하게 자원을 반납해야 하므로(비선점 부정) 시스템 성능이 떨어진다.
• 자원 낭비: 자원 이용률(Utilization)과 처리량(Throughput)이 현저히 감소

 
: 교착상태가 발생하는 3가지 필요조건을 충족한다고 해서 무조건 발생 x
  환형대기는 무조건 교착상태를 발생시킴! 환형 대기(Cycle)가 만들어지는 고리를 끊어버리면, 교착상태는 절대 발생하지 않는다.
 

교착상태 예방 조건

 
[ 교착상태 회피 (deadlock avoidance) ]
예방보다는 조금 더 유연한 방법으로 교착상태가 발생할 '가능성'을 피해 가는 방식
예방 기법처럼 1, 2, 3번 조건(상호배제, 점유대기, 비선점)을 엄격하게 막지 않으며, 4번(환형대기)처럼 할당 순서를 미리 정하지도 않는다.
 

• 동적인 결정 (Dynamic Choices): 자원 할당 요청이 들어올 때마다 현재 시스템의 상태(Current State)를 확인하여, 교착상태가 발생할 위험이 없을 때만 자원을 할당
• 필수 전제 조건: 운영체제는 프로세스들이 앞으로 자원을 얼마나, 어떤 순서로 요청할지에 대한 미래의 자원 요청 정보를 미리 알고 있어야 한다.

 
앞서 봤던 다이어그램에서 3, 4번의 흐름을 제외한 다른 경로로 진행하면 교착상태가 발생하지 않는다.

교착상태 회피 예시

 
결합진행 다이어그램과 같이 어떤 순서대로 진행됐는지, 어떤 순서로 자원 할당, 회수되었을 때 교착상태가 발생 가능한지 진행 상황을 따져볼 수 있어야 한다.
 
• 시스템 상태 구분
– 안전한 상태(safe state) : 교착상태가 발생하지 않도록 프로세스에게 자원을 할당할 수 있는 진행 경로가 존재
– 안전하지 않은 상태(unsafe state) : 교착상태를 피할 경로가 없음
 
•  회피 전략
① 자원 할당 거부 (Resource Allocation Denial)
 

• 동적 판단 (Dynamic Decision):
  • 프로세스가 자원을 요청하면, 교착상태가 발생할 가능성이 있는지 여부를 판단하기 위해 일단 '가상으로' 할당해 본다.
  • 그 후 시스템 상태가 여전히 안전한 상태(Safe)인지 확인한다.
• 할당 규칙:교착상태의 가능성이 없을 때 자원 할당 (안전한 상태를 계속 유지할 수 있으면 자원 할당)
  • 안전하다면: 자원을 실제로 할당한다.
  • 안전하지 않다면: 할당을 거부하고, 프로세스를 대기시킨다. (나중에 다른 프로세스가 자원을 반납하여 안전해지면 그때 할당)
• 필수 전제 조건 (제약 사항):
  • 각 프로세스들은 자신이 실행되는 동안 필요한 최대 자원 정보를 미리 운영체제에 알려주어야 한다.
  • 단점: 현실적으로 프로세스가 필요 자원을 완벽하게 미리 아는 것은 어렵다는 한계가 존재

 
② 프로세스 시작 거부 (Process Initialization Denial)
교착상태가 발생할 가능성이 있으면 프로세스 시작 거부 (자원 할당 단계가 아니라, 아예 프로세스를 시작하는 단계에서 제어한다.)

• 프로세스가 실행되려 할 때, 해당 프로세스의 요구 자원과 현재 시스템의 가용 자원을 비교한다.
• 할당 규칙: 현재 시스템의 부하가 크거나, 이 프로세스를 실행시켰을 때 교착상태가 발생할 가능성이 있다면 프로세스 시작 자체를 거부한다.
  • 발생할 가능성에 대해 구체적으로 설명하자면,  프로세스가 작업을 마칠 때까지 필요한 자원을 확실하게 공급해 줄 수 있는 (안전한) 상황이 아니라면, 애초에 일부 자원만 주고 시작하는 것을 허용하지 않는다. 

안전한 상태를 계속 유지하기 위해서는 일부 자원이 할당되고, 일부 자원이 할당되지 못하는 상황이 만들어지지 않도록 하는 게 중요! 필요자원을 동시에 할당할 수 있으면 : 일부자원의 할당을 거부한다. 필요한 자원을 모두 얻지 못하는 상태일 때 거부, 자원을 필요로 하는 프로세스들의 수행을 원천적으로 차단. 
 
• 사용하는 벡터와 행렬

 
• 안전한 상태 예 (banker’s algorithm)

안전한 상태 예(banker&amp;amp;rsquo;s algorithm)

P2를 먼저 수행 → 이후 나머지는 어떤 순서로 수행해도 안전한 상태
 
• 안전하지 않은 상태 예

안전하지 않은 상태 예

P2를 먼저 수행하면 나머지 프로세스들도 자원 할당을 받고 수행할 수 있는데 (b)와 같이 수행한다면 모든 프로세스가 필요로 하는 나머지 자원을 확보할 수 없는 상태가 된다. 모든 프로세스가 수행 불가한(안전하지 않은) 상태가 된다.
 
안전한 상태 예와 동일한 자원 현황이더라도 어떤 프로세스가 일부만 자원을 할당받으면 모든 프로세스의 수행이 불가능한 상황을 초래하지만 이런 상황이 발생되지 않도록 하려면 회피 전략인 ① 자원 할당 거부 (Banker’s algorithm) ②  프로세스 시작 거부 기법 활용!
 

banker’s algorithm Code

(a) 전역 자료 구조 (Global Data Structures)
시스템의 자원 상태를 저장하는 구조체

struct state {
    int resource[m];    /* 자원 벡터 (전체 자원 수) */
    int available[m];   /* 가용 벡터 (현재 사용 가능한 자원 수) */
    int claim[n][m];    /* 요구 행렬 (Max: 각 프로세스의 최대 자원 요구량) */
    int alloc[n][m];    /* 할당 행렬 (Allocation: 현재 할당된 자원 수) */
}

 
(b) 자원 할당 알고리즘 (Resource Allocation Logic)
프로세스가 자원을 요청했을 때, 이를 승인할지 거절할지 결정하는 메인 로직

/* 프로세스 i가 자원(request)을 요청했을 때 */

/* 1. 유효성 검사 */
if (alloc[i,*] + request[*] > claim[i,*]) {
    <error>; /* 전체 요청이 요구한 것(Max)보다 큼 -> 오류 처리 */
}
else if (request[*] > available[*]) {
    <suspend>; /* 당장 줄 자원이 부족함 -> 프로세스 일시 중지(대기) */
}
else {
    /* 2. 가상 할당 (Simulation) */
    /* 자원을 줬다고 가정하고 상태를 변경해봄 (새로운 상태 newstate로 전이) */
    alloc[i,*] = alloc[i,*] + request[*];
    available[*] = available[*] - request[*];
}

/* 3. 안전성 점검 (Safety Check) */
if (safe(newstate)) {
    <execute>; /* 안전하다면, 실제 자원 할당 수행 */
}
else {
    <restore>; /* 불안전하다면, 원래 상태로 복구 (Rollback) */
    <suspend>; /* 프로세스 일시 중지 (대기) */
}

 

(c) 안전한 상태 확인 알고리즘 (Safety Check Algorithm)
위의 safe(newstate) 함수 내부 로직. 실제로 모든 프로세스가 종료될 수 있는지 시뮬레이션

boolean safe (state S) {
    int currentavail[m];                 // 시뮬레이션용 가용 자원
    process rest[<number of processes>]; // 아직 종료되지 않은 프로세스 집합

    currentavail = available;            // 현재 가용 자원 복사
    rest = {all processes};              // 모든 프로세스를 대기 목록에 넣음
    possible = true;

    while (possible) {
        /* [조건을 만족하는 프로세스 Pk 찾기]
         * 남은 프로세스(rest) 중에서, 
         * (최대 요구량 - 현재 할당량) <= (현재 가용 자원) 인 프로세스 찾기
         * 즉, 추가로 필요한 자원(Need)을 현재 남은 자원으로 충당 가능한지 확인 */
        <find a process Pk in rest such that
         claim[k,*] - alloc[k,*] <= currentavail>;

        if (found) {        
            /* Pk의 수행을 시뮬레이션 */
            /* Pk가 작업을 마치고 자원을 반납한다고 가정 */
            currentavail = currentavail + alloc[k,*]; 
            rest = rest - {Pk};  // Pk를 남은 프로세스 집합에서 제거
        }
        else {
            possible = false;    // 더 이상 수행 가능한 프로세스가 없음
        }
    }

    return (rest == null); // 모든 프로세스가 처리되었다면(rest가 비었으면) True 반환
}

코드는 알아서 보세요
 
• 교착상태 회피 장점
– 교착상태 예방에 비해: 자원을 더 효율적으로 사용할 수 있고 덜 제한적이다.
– 교착상태 발견에 비해: 프로세스를 강제로 종료(선점)이나 롤백의 필요가 없다.
 
• 교착상태 회피 단점
회피 기법(은행원 알고리즘)이 이론적으로는 훌륭하지만, 현대 운영체제(Windows, Linux 등)에서 잘 사용되지 않는 이유는 아래의 비현실적인 가정(Assumption)들이 필요하기 때문이다.
 
1. 최대 자원 요구량의 사전 파악

• 각 프로세스는 자신이 실행되는 동안 필요한 자원의 최대량을 운영체제에 미리 숫자로 선언해야 한다.
• 한계: 현실적으로 프로그램이 실행 중에 얼마나 많은 자원을 쓸지 완벽하게 예측하는 것은 불가능에 가깝다.

2. 프로세스 간의 독립성

• 고려 대상인 프로세스들은 서로 독립적이어야 하며, 동기화(Synchronization) 요구사항이 없어야 한다.
• 한계: 실제 시스템의 프로세스들은 서로 통신하거나 순서를 맞추는 경우가 많아 이 가정을 지키기 어렵다.

3. 고정된 자원의 수

• 할당할 수 있는 총자원의 수가 고정되어 있어야 한다.
• 한계: 시스템 운영 중에 장치가 고장 나거나 새로운 장치가 추가되는 등 자원의 수는 변동될 수 있다.

4. 자원 점유 중 종료 불가

• 프로세스는 자원을 보유하고 있는 상태에서 종료되면 안 된다.
• 한계: 오류나 예외 상황으로 인해 프로세스가 자원을 반납하지 못하고 비정상 종료되는 경우가 발생할 수 있다.

 
[ 교착상태 발견 (deadlock detection) ]

• 교착상태 예방은 제한을 많이 두는 보수적(Conservative)인 방식
• 교착상태 발견은 이와 정반대의 접근 방법을 사용
• 프로세스가 자원을 요청하면, 특별한 제한 없이 가능한 한 모두 할당해 준다. (일단 교착상태가 일어나는 것을 허용함)

시스템은 주기적으로 혹은 문제가 감지될 때 검사 알고리즘을 실행하여 교착상태 발생 여부를 확인한다.
 
 
(검사시점 : 발견 주기가 중요) 얼마나 자주 검사할 것인가? 
시스템은 주기적으로 알고리즘을 돌려 교착상태(Cycle)가 있는지 확인해야 하는데, 이 주기에 따라 장단점이 갈림
① 검사 주기가 짧을 때 (자주 검사함)

• 장점 : 교착상태가 발생하자마자 빠르게 발견하여 대처할 수 있다.
• 단점 :
  • 검사루틴을 반복하므로 부하(Overhead)가 크다.
  • 검사 알고리즘 자체가 CPU를 사용하므로, 정작 프로세스가 일할 시간을 뺏긴다.
  • 예를 들어 1초마다 검사하는데 검사 시간이 0.9초라면? 실제 작업은 0.1초밖에 못 하므로 프로세스 수행 시간이 비약적으로 늘어난다(Delay).

② 검사 주기가 길 때 (가끔 검사함)

• 장점: 검사를 자주 안 하므로 시스템 부하(Overhead)는 적다.
• 단점:
  • 교착상태가 발생해도 한참 뒤에나 알게 된다. (발견 지연)
  • 그사이에 교착상태에 연루된 프로세스들이 더 많아져서(꼬리에 꼬리를 물어서), 나중에 발견했을 때 해결(복구)하기가 훨씬 복잡하고 어려워진다.

복구 (Recovery)
검사 결과 교착상태가 발견되면, 운영체제는 프로세스를 종료하거나 자원을 회수하는 등 해결(Recover) 조치를 취한다.
 
교착상태 발생 시점에서 얼마나 진행이 되었는지가 중요한 문제!!
→ 교착상태가 발견된 시점에서 진행이 많이 안 되면 롤백하여 빨리 복구 가능 / 이미 진행이 많이 되었으면 회복하기 위한 과정이 복잡
 
• 교착상태 발견 알고리즘 (요청 행렬 Q, 할당 행렬 A, 자원 벡터 R, 가용 벡터 V, 임시 벡터 W 구성)

교착상태 발견 알고리즘

1. 사용되는 변수(행렬) 설명
알고리즘을 이해하기 위해 먼저 표(행렬)가 무엇을 의미하는지 알아야 한다.

• 할당 행렬 A (Allocation): 현재 각 프로세스가 가지고 있는 자원의 수
• 요청 행렬 Q (Request): 각 프로세스가 작업을 마치기 위해 추가로 필요한 자원의 수
• 가용 벡터 V (Available): 현재 시스템에 남아있는 자원의 수
• 임시 벡터 W (Work): 시뮬레이션 중 자원이 반납되면서 변하는 현재 가용 자원의 양
• 자원 벡터 R (Resource) : 전체 자원에 대한 현황 

2. 알고리즘 수행 단계 (Step-by-Step)
Step 1. 자원이 없는 프로세스 표시

• 할당 행렬 A에서 행의 값이 모두 0인 프로세스를 우선 표시 : 자원을 하나도 가지고 있지 않은(모두 0인) 프로세스
• 자원을 하나도 가지고 있지 않은(모두 0인) 프로세스는 교착상태의 원인이 될 수 없다. (가진 게 없으니 남의 길을 막을 일도 없음)
• 이 프로세스들은 이미 끝났거나 안전하다고 보고 마킹(표시)하는 작업

Step 2. 시뮬레이션 준비 (V = W)

• 현재 실제로 남아있는 자원(V)을 임시 변수 W(Work)에 복사한다. (벡터 W의 초기값은 가용 벡터 V와 동일)
• 이제부터 W를 늘려가며 계산한다.

Step 3. 작업 가능한 프로세스 찾기

• 아직 마킹되지 않은(표시 안 된) 프로세스 중에서, 자신의 요청량(Q)을 현재 가용 자원(W)으로 감당할 수 있는 프로세스를 찾는다.
• 조건: Q <= W(요청 자원보다 현재 남은 자원이 더 많을 때)
• 만약 이런 프로세스가 없다면, 알고리즘을 종료한다. (더 이상 진행 불가 → 교착상태)
• 회피와 차이점 : 이 단계에서 교착상태가 발생했다면 교착상태 발생하지 않는 흐름으로 보내는 게 아니라 교착상태 발견 여부를 확인 → 회복 절차로 이동!!

Step 4. 자원 회수 및 반복

• 작업 가능한 프로세스를 찾았다면, 그 프로세스는 "작업을 완료하고 자원을 반납했다"고 가정한다.
• 그 프로세스가 가지고 있던 자원(A)을 W에 더한다. (W = W + A)
• 해당 프로세스를 '마킹(표시)'하고, 다시 Step 3으로 돌아가서 다음 타자를 찾다.

이 예제에서는 P3에 R5자원을 하나 할당해 주면 P3의 수행이 완료되고, 자원이 반납되면서 가용 벡터 자원이 늘어난다. 이걸 가지고 남은 프로세스들이 수행 가능한지 따져서 수행
 
• 회복 (recovery)
– 교착상태와 연관된 모든 프로세스 종료
– 교착상태에 연관된 프로세스들을 체크포인트 시점으로 롤백한 후 다시 수행 시킴 (교착상태가 다시 발생할 가능성 존재)
   교착상태 발생 바로 이전 체크포인트 지점으로 롤백

체크포인트 시점

– 교착상태가 없어질 때까지 교착상태에 포함되어 있는 프로세스들을 하나씩 종료 (프로세스 종료)
– 교착상태가 없어질 때까지 교착상태에 포함되어 있는 자원을 하나씩 선점 (자원 선점)
 
 
종료 (또는 선점될) 프로세스 선택 기준 (효율성을 따져서 종료)
• 지금까지 사용한 처리기 시간이 적은(연산이 많지 않은) 프로세스부터
• 지금까지 생산한 출력량이 적은 프로세스부터 (작업 시간이 짧다고 볼 수 있다.)
• 이후 남은 수행시간이 가장 긴 프로세스부터 (가장 오랫동안 작업이 진행되어야 하는 프로세스를 종료)
• 할당받은 자원이 가장 적은 프로세스부터 (데드락 발생 가능성이 낮은 것부터 종료)
• 우선순위가 낮은 프로세스부터
 
통합 교착상태 전략

접근 방법	자원할당 정책	구체적인 기법	장점	단점
예방	보수적, (자원 할당이 가능하더라도 조건에 따라 할당하지 않을 수 있다.)	모든 자원을 한꺼번에 요구	• 순간적으로 많은 일을 하는 프로세스에게 적합 • 선점이 불필요	• 효율이 나쁨 • 프로세스 시작을 지연시킬 가능성 있음 • 프로세스는 사용할 모든 자원을 미리 알고 있어야 함
		선점 가능	• 자원 상태의 저장과 복구가 간단한 자원에는 적용하기 쉬움	• 선점이 필요보다 자주 일어남
		자원 할당 순서	• 컴파일 시점에 강제할 수 있음 • 시스템의 설계 시점에 문제를 해결했기 때문에 동적 부하 없음	• 점진적인 자원 할당이 안 됨
회피	예방과 발견의 중간 정도	교착상태가 발생하지 않는 안전한 경로를 최소한 하나는 유지	• 선점이 불필요	• 운영체제는 자원에 대한 미래 요구량을 미리 알고 있어야 함 • 오랜기간 지연 발생의 가능성 있음
발견	적극적 (자원 할당이 가능하면 즉시 할당한다.)	주기적으로 교착상태 발생 여부 파악	• 프로세스 시작을 지연시키지 않음 • 온라인 처리 가능	• 선점에 의한 손실 발생

 

 
식사하는 철학자 문제

식사하는 철학자 문제

 
문제 정의

– 두 철학자가 동시에 같은 포크를 사용할 수 없다. (상호 배제)
– 어떤 철학자도 굶어 죽어서는 안 된다 (교착 상태와 굶주림을 말 그대로 피해야 한다!)
철학자의 행동은 '생각하기(Thinking)'와 '식사하기(Eating)' 두 가지뿐

 
 
데드락이 발생할 수 있는 상황은 언제일까?

• 나의 오른쪽 포크를 이미 내 오른쪽 철학자가 (자신의 왼쪽 포크로서) 쥐고 있을 때

보호가 필요한 공유자원은 뭘까?

• 포크 : 포크가 철학자 사이마다 있으므로 (철학자 1 왼손, 철학자 2 오른손으로 들면 안 됨)
• 양쪽의 포크를 동시에 획득해야 함. 일괄적으로 오른쪽이나 왼쪽 손으로 집어야 한다. → 환형대기 발생할 수 있다.)

 
포크에 대한 상호배제를 처리하기 위해 어떤 유형의 세마포어가 몇 개 필요할까?
프로세스 : 각각의 철학자 / 공유 자원 : 양쪽에 있는 포크(동시 획득)
동시에 오른쪽이나 왼쪽의 포크를 일괄적으로 집어 들었을 때 데드락 발생 가능
 
• 세마포어를 이용한 해결 방법 → 이런 식으로 난 밥 못 먹어

// 식사하는 철학자 문제
semaphore fork[5] = {1}; // 포크 5개, 초기값 1 (사용 가능)

void philosopher(int i) {
    while (true) {
        think();               // 1. 생각하기

        /* 포크 집기 (P연산: 세마포어 감소) */
        wait(fork[i]);         // 2. 왼쪽 포크 집기 (선점)
        wait(fork[(i+1) % 5]); // 3. 오른쪽 포크 집기 (선점)

        eat();                 // 4. 식사하기 (임계 영역)

        /* 포크 내려놓기 (V연산: 세마포어 증가) */
        signal(fork[(i+1) % 5]); // 5. 오른쪽 포크 내려놓기
        signal(fork[i]);         // 6. 왼쪽 포크 내려놓기
    }
}

• 상황: 만약 5명의 철학자가 동시에 배가 고파져서, 각자 자신의 왼쪽 포크(fork [i])를 집어 들었다고 가정

 

[코드 로직 및 상세 동작]

1. 초기화 (Initialization)

• fork라는 5개의 세마포어 배열을 모두 1(Unlock/사용 가능)로 초기화하여 시작

2. 무한 반복 (Life Cycle)

• 각 철학자는 while(true) 루프를 돌며 끊임없이 '생각하기(Thinking)'와 '식사하기(Eating)' 상태를 반복한다.

3. 자원 획득 (Wait / Locking)

• 배가 고파지면 wait() 연산을 수행하여 포크 획득을 시도한다. (세마포어 값이 1이면 0으로 만들고 진입, 0이면 대기)
• 이때 교착상태의 원인이 되는 순차적 접근이 일어난다.
  • 먼저 자신의 왼쪽 포크(i)를 확보한다.
  • 그 후, 오른쪽 포크를 확보한다. 이때 (i+1) % 5 모듈러 연산을 사용하여, 마지막 4번 철학자의 오른쪽 포크가 다시 0번이 되는 원형 식탁 구조를 처리한다. (인덱스 순환)

4. 자원 반납 (Signal / Unlocking)

• 식사(임계 영역 수행)가 끝나면 signal() 연산을 호출한다.
• 잡고 있던 두 포크의 세마포어 값을 다시 1로 복구시켜, 대기 중인 다른 철학자가 사용할 수 있도록 반납한다.

• 결과:
  1. 모든 포크가 사용 중(0)이 된다.
  2. 모든 철학자가 오른쪽 포크(fork[(i+1)%5])를 집으려고 시도한다.
  3. 하지만 오른쪽 포크는 이미 오른쪽 사람이 '왼쪽 포크'로 가지고 있다.
  4. 아무도 포크를 내려놓지 않고, 하염없이 오른쪽 포크가 비기만을 기다리는 무한 대기 상태(순환 대기)에 빠진다.

 
• 세마포어를 이용한 다른 해결 방법

// 식사하는 철학자 문제 : 동시 입장 인원 제한 해결책

/* * program diningphilosophers 
 * semaphore fork[5] = {1};  // 포크 5개 (1: 사용 가능, 0: 사용 중)
 * semaphore room = {4};     // 핵심: 식탁에 앉을 수 있는 인원을 4명으로 제한
 */

void philosopher(int i) {
    while (true) {
        think();                 // 1. 생각하기

        /* [입장 시도] */
        wait(room);              // 방에 빈자리가 있는지 확인 (최대 4명)
                                 // 꽉 찼으면 여기서 대기(Block)하여 교착상태 방지

        /* [포크 집기] */
        wait(fork[i]);           // 2. 왼쪽 포크 집기
        wait(fork[(i+1) % 5]);   // 3. 오른쪽 포크 집기 (원형 테이블 인덱스 처리)

        eat();                   // 4. 식사하기 (임계 영역 수행)

        /* [포크 내려놓기] */
        signal(fork[(i+1) % 5]); // 5. 오른쪽 포크 반납
        signal(fork[i]);         // 6. 왼쪽 포크 반납

        /* [퇴장] */
        signal(room);            // 7. 방에서 나감 (빈자리 +1)
    }
}

void main() {
    /* 5명의 철학자 프로세스를 병렬로 실행 */
    parbegin(philosopher(0), philosopher(1),
             philosopher(2), philosopher(3),
             philosopher(4));
}

room 세마포어의 역할은?

• 식탁에 앉을 수 있는 철학자의 수를 제한하는 계수 세마포어 (Counting Semaphore)
• 값이 0이 되면:
  • 이미 4명이 방에 들어와 있어 꽉 찬 상태.
  • 마지막 5번째 철학자는 wait(room)에서 블록 되어 입장 대기 상태가 됨.

0이 되면 4명이 식사하는 상황 (식사인원을 제한하겠다. → 프로세스 시작 거부와 같음)
 

[코드 로직 및 상세 동작]

1. 초기화 (Initialization)

• fork는 기존과 동일하게 모두 1로 초기화한다.
• 핵심 변경점: room이라는 새로운 세마포어를 추가하고 초기값을 4로 설정한다. (총 5명의 철학자 중 최대 4명만 동시에 식탁에 앉을 수 있음)

2. 무한 반복 (Life Cycle)

• while(true)를 통해 '생각'과 '식사'를 반복하는 구조는 동일하다.

3. 입장 및 자원 획득 (Enter Room & Wait)

• 포크를 집기 전에 wait(room)을 먼저 수행한다.
• 식탁(Room)에 자리가 남았는지 확인하고, 4명이 이미 차 있다면 대기한다. (인원 제한)
• 입장에 성공했다면, 기존처럼 왼쪽 포크(i)와 오른쪽 포크((i+1)%5)를 순서대로 확보한다.

4. 해결 원리 (Why Deadlock Free?)

• 포크는 5개인데 앉아 있는 사람은 최대 4명
• 최악의 경우(모두가 왼쪽 포크를 쥔 경우)라도 반드시 1개의 포크가 남게 된다.
• 따라서 누군가 한 명은 반드시 남은 포크를 집어 식사를 할 수 있으므로, 순환 대기(Circular Wait)가 발생하지 않는다.

5. 자원 반납 및 퇴장 (Leave Room & Signal)

• 식사가 끝나면 포크 두 개를 signal()로 내려놓는다.
• 마지막으로 signal(room)을 호출하여 식탁에서 일어나, 밖에서 대기 중이던 다른 철학자가 들어올 수 있도록 자리를 비워준다.

 
• 모니터를 이용한 해결 방법

// 식사하는 철학자 문제 해결책: 모니터(Monitor) 활용

// 모니터 선언: 공유 자원(포크)과 접근 메서드를 캡슐화
monitor dining_controller;

// 조건 변수 선언: 포크를 기다리는 철학자들의 대기열 역할
cond ForkReady[5]; /* 동기화를 위한 조건 변수 */

// 포크 상태 변수: true면 사용 가능, false면 누군가 사용 중
boolean fork[5] = {true}; /* 각 포크의 사용 가능 여부 */

// [메서드 1] 포크 2개를 집는 함수 (진입 시 모니터 락 획득)
void get_forks(int pid) { /* pid는 철학자 id를 의미 */
    int left = pid;
    int right = (++pid) % 5; // 오른쪽 포크 인덱스 계산 (원형 테이블)

    /* 왼쪽에 놓인 포크 접근 */
    if (!fork[left]) {
        // 왼쪽 포크가 사용 중이면, 해당 조건 변수 큐에서 대기(sleep)
        cwait(ForkReady[left]); /* 조건 변수에서 대기 */
    }
    fork[left] = false; // 획득 성공: 사용 중 상태로 변경

    /* 오른쪽에 놓인 포크 접근 */
    if (!fork[right]) {
        // 오른쪽 포크가 사용 중이면, 해당 조건 변수 큐에서 대기(sleep)
        cwait(ForkReady[right]); /* 조건 변수에서 대기 */
    }
    fork[right] = false; // 획득 성공: 사용 중 상태로 변경
} // 함수 종료 시 모니터 락 반납

// [메서드 2] 포크 2개를 내려놓는 함수 (진입 시 모니터 락 획득)
void release_forks(int pid) {
    int left = pid;
    int right = (++pid) % 5;

    /* 왼쪽에 놓인 포크 반납 */
    if (empty(ForkReady[left])) { // 기다리는 철학자가 없으면
        fork[left] = true;        /* 대기하는 프로세스가 없음 -> 그냥 사용 가능 상태로 변경 */
    } else {                      // 기다리는 철학자가 있으면
        // 대기 중인 철학자 하나를 깨워줌 (포크를 넘겨주는 효과)
        csignal(ForkReady[left]); /* 대기하던 프로세스를 깨움 */
    }

    /* 오른쪽에 놓인 포크 반납 (로직 동일) */
    if (empty(ForkReady[right])) {
        fork[right] = true;       /* 대기하는 프로세스가 없음 */
    } else {
        csignal(ForkReady[right]); /* 대기하던 프로세스를 깨움 */
    }
} // 함수 종료 시 모니터 락 반납

// [프로세스] 각 철학자의 행동 정의
void philosopher[k=0 to 4] { /* 5명의 철학자 존재 */
    while (true) {
        <think>;             // 생각하기
        
        // 모니터의 메서드를 호출하여 포크 요청 (내부적으로 동기화 처리됨)
        get_forks(k);        /* 철학자가 모니터를 통해 2개의 포크 요청 */
        
        <eat spaghetti>;     // 식사하기 (임계 영역)
        
        // 모니터의 메서드를 호출하여 포크 반납
        release_forks(k);    /* 철학자가 모니터를 통해 2개의 포크 반납 */
    }
}

기본 개념

• 모니터(Monitor): 공유 데이터와 그 데이터에 접근하는 함수들을 묶어놓은 추상 데이터 타입(ADT)이다.
• 특징: 모니터 내부에는 한 번에 하나의 프로세스만 진입할 수 있다. (상호 배제가 자동 보장됨)

[코드 로직 및 상세 동작]

1. 초기화 (Initialization)

• 상태 변수 (boolean fork [5]): 세마포어의 정수값 대신, true(사용 가능) / false(사용 중)라는 직관적인 논리값을 사용하여 포크의 상태를 관리한다.
• 조건 변수 (cond ForkReady [5]): 포크가 없을 때 철학자들이 줄을 서서 기다리는 대기열(Queue)을 생성한다.

2. 무한 반복 (Life Cycle)

• 철학자 프로세스(void philosopher)는 직접 락을 걸지 않는다.
• 대신 모니터가 제공하는 함수인 get_forks()와 release_forks()를 호출하며, '생각'과 '식사'를 무한 반복한다.

3. 자원 획득 (get_forks & cwait)

• 상태 확인: 함수에 진입하면 if문을 통해 원하는 포크가 현재 사용 가능한지 확인한다.
• 대기 (Blocking): 만약 누군가 사용 중(false)이라면, cwait()를 호출하여 해당 포크의 대기열(Condition Variable)로 들어가 잠든다.
• 획득: 사용 가능하다면, 상태를 false(사용 중)로 바꾸고 포크를 차지한다.

4. 자원 반납 (release_forks & csignal)

• 대기자 확인: 포크를 내려놓을 때, empty() 함수로 이 포크를 기다리는 사람 (ForkReady) 이 있는지 확인한다.
• 기다리는 사람이 없으면(empty): 포크 상태를 true(사용 가능)로 바꾼다.
• 기다리는 사람이 있으면(else): csignal을 보내 대기 중인 철학자를 깨우고 자원을 넘겨준다. (상태를 true로 바꿀 필요 없이 바로 넘겨줌 포크를 바로 넘겨주는 개념)

5. 해결 원리 (Monitor's Advantage)

• 추상화: 복잡한 동기화 과정(Locking/Unlocking)을 개발자가 직접 짜지 않고, 모니터 내부 함수에 숨겨두었다.
• 자동 상호 배제: 모니터 안에는 한 번에 하나의 프로세스만 진입할 수 있다는 특성이 있어, 데이터 꼬임(Race Condition)을 원천적으로 방지한다.

 
[ 유닉스 병행성 기법 ]

유닉스 병행성 기법

 
프로세스 간 통신 (IPC: InterProcess Communication)

• 실행 중인 프로세스 간에 데이터를 주고받거나, 동기화(Synchronization)를 맞추기 위한 메커니즘.
• 주요 기법: 파이프(Pipe), 시그널(Signal), 소켓(Socket) 등 다양한 방법이 존재함.

통신을 나타내는 용어지만, 데이터 교환을 의미하는 게 아니다.
 
System V IPC 
유닉스 System V 릴리즈에서 표준화된 대표적인 3가지 기법을 말한다,

1. 세마포어 (Semaphore): 데이터 교환보다는 상호배제(Mutual Exclusion)와 동기화를 위한 도구.
2. 공유 메모리 (Shared Memory): 데이터 공유를 위한 기법 (가장 빠름).
3. 메시지 큐 (Message Queue): 메시지 교환을 위한 기법.

 
[ 리눅스 커널 병행성 기법 ]
All UNIX mechanisms + additional features
현대 운영체제는 복잡한 동기화 문제를 해결하기 위해 기본적인 IPC 외에도 다양한 변종 기법을 사용한다.

• 원자적 연산 (Atomic Operation)
• 스핀락 (Spinlock)
• 메모리 배리어 (Memory Barrier)

 
[참고 문헌]

• 본 포스팅은 'Operating Systems: Internals and Design Principles (William Stallings)' 교재와 강의 자료를 바탕으로 학습하여 재구성한 내용입니다.
• 학습 목적으로 정리하였으며, 내용에 대한 저작권은 원저작자에게 있습니다.