[Chapter 7. 교착상태] 교착상태 처리 방법 - 예방, 식사하는 철학자들 문제

* 본 글은 '운영체제(Operating System: Concepts) 9th edition'의 내용과 2021학년도 1학기에 수강한 '운영체제' 과목 강의 내용을 함께 정리하여 작성하였습니다.

 

 

교착상태 문제를 처리하는 데에는 3가지 방법이 존재한다.

 

1. 시스템이 결코 교착상태가 되지 않도록 보장하기 위해 교착상태를 예방하거나 회피하는 프로토콜을 사용하는 방법

2. 시스템이 교착상태가 되도록 허용한 다음에 탐지하여 회복(복구)시키는 방법

3. 문제를 무시, 교착상태가 시스템에서 결코 발생하지 않는 척한다.

 

대부분의 운영체제들은 3번째 방법을 사용하고 있으며, 이에 교착상태를 처리하는 프로그램을 작성하는 것은 프로그래머의 몫이다.

 

1번째와 2번째 방법에 대하여 차근차근 알아보자.

1. 교착상태가 되지 않도록 사전에 조치하는 방법 (예방, 회피)

2. 교착상태 방치 후 탐지하여 복구하는 방법 (탐지, 복구)

 

교착상태 예방(prevent)

---

교착상태는 교착상태 발생의 4가지 필요충분조건 중 하나만 일어나지 않아도 예방이 가능하다.

 

1. "상호 배제" 조건을 부정

일반적으로 상호 배제 조건을 거부하는 것으로 교착 상태를 방지하는 것은 불가능하다.

어떤 자원들은 근본적으로 공유가 불가능하기 때문이다.

 

2. "점유하며 대기" 조건을 부정

첫 번째 방법 - 대기 없음

프로세스가 실행되기 전에 자신의 모든 자원을 요청하고 확보하도록 한다.

 

두 번째 방법 - 점유 없음

프로세스가 자원을 전혀 갖고 있지 않을 때만 자원을 요청할 수 있도록 허용한다.

추가 자원을 요청하려면 자신에게 할당된 모든 자원을 반드시 먼저 방출해야 한다.

 

단점

1. 할당된 후에도 한동안 사용되지 않는 자원이 생겨나, 자원의 활용도가 낮아지고 시스템의 성능이 하락한다.

2. 기아 상태 발생의 가능성이 증가한다.

자주 쓰이는 자원을 여러 개 필요로 하는 프로세스의 경우,

적어도 하나가 다른 프로세스에 할당되어 있는 경우가 빈번하게 발생할 것이기에 무한정 대기해야 할 수도 있다.

 

3. "비선점" 조건을 부정

만약 어떤 자원을 점유하고 있는 프로세스가 즉시 할당받을 수 없는 다른 자원을 요청한다면

현재 점유하고 있는 모든 자원을 강제로 반환하도록 한다.

 

대기 상태에 있는 프로세스가 반환한 자원들에 대해서는 선점이 가능하며,

 

대기 상태로 들어간 프로세스는

자신이 요청하고 있는 새로운 자원과 이미 점유했었던 옛 자원들을 전부 획득할 수 있을 때에만 다시 시작될 수 있다.

 

단점

이 방법은 상태의 보존과 복구가 필요하다.

CPU 레지스터나 메모리처럼 상태가 쉽게 저장되고 복원될 수 있는 자원에는 용이하나,

일반적으로 입출력 장치, Mutex, 세마포어 등에는 적용할 수 없다.

 

4. "순환(환형) 대기" 조건을 부정

각 자원 유형에게 증가하는 순서의 일련번호를 부여한다.

* 자원 유형의 집합 R = {R1, R2, ... , Rm}

* 자원 유형에 일련번호를 부여하는 함수 F : R → N

   해당 번호는 두 자원을 비교해 어느 것이 순서가 빠른지 결정할 수 있게 함

 

각 프로세스가 열거된 순서대로(번호가 증가하는 순서대로)만 자원을 요청하도록 강제한다.

 

즉, F(Rj) > F(Ri)를 만족하는 Rj 유형의 자원만 요청할 수 있으며

만약 F(Ri) >= F(Rj)인 Rj 유형의 자원을 요청할 때에는 F(Ri) >= F(Rj)인 모든 Ri를 반납해야 요청할 수 있다.

 

단점

프로세스에 대하여 공평하지 않은 해결안이다. (비대칭 해결안)

 

 

위의 교착상태 예방 방법들은 식사하는 철학자들 문제에 적용할 수 있다.

 

---

식사하는 철학자들 문제 (The Dining-Philosophers Problem)

이는 고전적인 동기화 문제로,

여러 스레드에게 여러 자원을 교착상태와 기아를 발생시키지 않고 할당해야 할 필요성을 표현한 것이다.

 

 

생각하고 먹으면서 생애를 보내는 5명의 철학자들이 원형 테이블에 앉아 있다.

테이블의 중앙에는 밥이 있고, 5개의 포크가 올려져 있다.

 

 

철학자는 식사를 할 때마다 접시의 왼쪽과 오른쪽에 있는 두 개의 포크를 모두 사용해야 한다.

한 번에 한 개의 포크만 집을 수도 있지만 식사는 불가능하며, 이미 옆 사람의 손에 들어간 포크를 집을 수는 없다.

 

철학자는 식사를 마치고 다시 생각에 잠기기 전에는 두 포크를 제자리에 둔다.

 

 

 

한 가지 해결책은 포크에 번호를 부여하여 번호가 증가하는 순으로만 포크를 집도록 하는 것이다. (4. 환형 대기 조건을 부정)

하지만 이는 모든 철학자들에게 공평하지 않은 해결책이다.

 

먼저 1번 철학자가 1번 포크를 집고, 2번 철학자가 2번 포크, ... , 5번 철학자가 5번 포크를 집는다.

그 후 5번 철학자는 1번 포크를 집으려고 하는데 이미 1번 철학자가 그 포크를 집고 있는 상태이기 때문에 환형 대기가 생기게 된다.

 

이때 5번 철학자가 자신이 갖고 있던 5번 포크를 내려놓아 4번 철학자가 그것을 집어 식사를 하고,

식사를 마친 4번 철학자가 놓은 4번 포크를 3번 철학자가 집어서 식사를 하고, ...

이렇게 쭉 실행하여 1번 철학자가 식사를 마쳐서야 5번 철학자가 5번 포크가 1번 포크를 통해 식사를 할 수 있게 된다.

 

이 방식으로 환형 대기가 풀리게 되어 문제가 해결되긴 하지만,

5번 철학자가 가장 늦게 식사를 하게 되어 공평하지 않은 해결책이라는 것이다.

 

 

 

또 다른 해결책은 세마포어를 이용하는 것이다.

각 포크가 하나의 세마포어이다.

 

철학자는 그 세마포어에 wait() 연산을 실행하는 것으로 포크를 집으려고 시도하고,

signal() 연산을 통해 자신이 집은 포크를 놓는다.

 

philosopher (int i) {
    while(1) {
        think();
        P(fork[i]);
        P(fork[(i+1) mod 5]);
        
        eat();
        V(fork[i]);
        V(fork[(i+1) mod 5]);
    }
}

semaphore fork[5];
fork[0] = fork[1] = fork[2] = fork[3] = fork[4] = 1

// 각각 스레드로 호출
create_thread(philosopher, 0);
create_thread(philosopher, 1);
create_thread(philosopher, 2);
create_thread(philosopher, 3);
create_thread(philosopher, 4);

 

하지만 이렇게 했을 때 각 스레드가 포크 세마포어를 하나씩 소유하면서 다음 포크 세마포어를 대기할 경우 교착상태가 발생한다.

(철학자 예시 - 철학자들이 모두 왼쪽 포크를 하나씩만 소유하고 동시에 오른쪽 포크를 집으려고 하는 상황)

 

 

홀수 철학자와 짝수 철학자의 포크 집는 순서를 다르게 하는 방법도 있겠지만,

하나의 단일 조건에 대한 동기화가 아닌, 여러 조건 집합에 대한 동기화가 필요하다.

 

 

따라서 AND 동기화를 이용해서 해결할 수 있다. (2. 점유하며 대기 조건을 부정)

 

필요한 모든 세마포어를 한꺼번에 모두 차지하거나 / 세마포어를 아예 하나도 갖지 않도록

새로운 P, V 연산이 필요하다. (Simultaneous Semaphore - P_sim, V_sim)

P_sim(semaphore S, int N) {
    if ((S[0] >= 1 && .. && (S[N-1] >= 1)) {  // L1
        for (i = 0; i < N; i++) {
            S[i]--;
        } else {
            Enqueue the calling thread in the queue for the first S[i] where S[i] < 1;
            The calling thread is blocked while it is in the queue;
            Goto L1; // When the thread is removed from the queue
        }
    }
}

V_sim(semaphore S, int N) {
    for (i = 0; i < N; i++) {
        if (S[i]++ <= 0) {
            Dequeue all threads in the queue for S[i];
            All such threads are now ready to run (but may be blocked again int P_sim);
        }
    }
}

philosopher (int i) {
    while(1) {
        think();
        P_sim(fork[i], fork[(i+1) mod 5]); // 양쪽 포크를 모두 획득 가능할 때만 포크를 집을 수 있음
        
        eat();
        V_sim(fork[i], fork[(i+1) mod 5]);
    }
}

semaphore fork[5];
fork[0] = fork[1] = fork[2] = fork[3] = fork[4] = 1

// 각각 스레드로 호출
create_thread(philosopher, 0);
create_thread(philosopher, 1);
create_thread(philosopher, 2);
create_thread(philosopher, 3);
create_thread(philosopher, 4);