[Operating System] Chapter 6

이한량·2024년 4월 12일

목록 보기

6/12

1. Dining Pilosophers Problem

5명의 철학자가 한 원형 테이블에 앉아있다고 가정해보자. 접시에 담겨있는 음식을 먹기 위해선 각 철학자의 양옆에 있는 포크 중 하나를 사용해야된다. 이 문제를 해결하는 알고리즘을 살펴보자.

A First Solution

semaphore fork[5] = {1, 1, 1, 1, 1}; // 모든 포크에 대한 세마포어를 1로 초기화하여 사용 가능하게 함
int i;

void philosopher(int i) {
    while (true) { // 무한 루프로 철학자의 생활을 반복
        think(); // 생각하는 단계
        wait(fork[i]); // 왼쪽 포크를 집으려고 시도
        wait(fork[(i+1) % 5]); // 오른쪽 포크를 집으려고 시도
        eat(); // 두 포크를 모두 집었으면 식사
        signal(fork[(i+1) % 5]); // 오른쪽 포크를 내려놓음
        signal(fork[i]); // 왼쪽 포크를 내려놓음
    }
}

void main() {
    parbegin(philosopher(0), philosopher(1), philosopher(2), philosopher(3), philosopher(4));
}

위 코드같은 경우, 모든 철학자가 자신의 왼쪽에 있는 포크를 먼저 집은 상태에서 오른쪽 포크를 집으려고 시도하는 경우, Deadlock에 빠질 수 있다.

A Second Solution

/* program diningphilosophers */
semaphore fork[5] = {1, 1, 1, 1, 1}; // 모든 포크에 대한 세마포어를 1로 초기화
semaphore room = 4; // 식사실에 동시에 있을 수 있는 철학자의 수를 4로 제한

void philosopher(int i) {
    while (true) {
        think(); // 생각하는 단계
        wait(room); // 식사실에 자리가 있는지 확인하고, 자리가 있으면 식사실에 들어감
        wait(fork[i]); // 왼쪽 포크를 집음
        wait(fork[(i+1) % 5]); // 오른쪽 포크를 집음
        eat(); // 식사
        signal(fork[(i+1) % 5]); // 오른쪽 포크를 내려놓음
        signal(fork[i]); // 왼쪽 포크를 내려놓음
        signal(room); // 식사실에서 나옴
    }
}

void main() {
    // 병렬로 5명의 철학자가 동작하도록 시작
    parbegin(philosopher(0), philosopher(1), philosopher(2), philosopher(3), philosopher(4));
}

위 코드는, semaphore 변수 room을 통해 식사실에 동시에 들어갈 수 있는 철학자 (프로세스)를 제한하여 Deadlock을 극복한 것을 보여준다. 즉, 항상 최소 한 명의 철학자가 식사를 할 수 있는 환경이 보장된다.

2. Deadlock

Deadlock은 시스템 자원을 경쟁하거나 서로 통신하는 일련의 프로세스들이 영구적으로 차단되는 상황을 정의한다. 일련의 프로세스가 Deadlock(교착 상태)에 빠졌을 때, 그 집합 내의 각 프로세스는 다른 차단된 프로세스에 의해서만 차단 해제될 수 있다.

Deadlock의 발생 조건 : Deadlock이 발생하기 위한 조건은 4가지가 있는데, 4가지중 한 가지라도 만족하지 않는다면, Deadlock 발생을 예방할 수 있다.

Mutual Exclusion : 한 번에 한 프로세스만이 특정 자원에 접근할 수 있다.
Hold and wait : 프로세스가 최소한 하나의 자원을 보유한 상태로, 다른 프로세스에 의해 점유된 추가 자원을 기다리는 경우이다. 이로 인해 프로세스들은 자원을 보유한 채로 서로를 기다리게 된다.
No preemption : 한 프로세스가 다른 프로세스에게 자원을 강제로 빼앗을 수 없다. 한번 프로세스에 할당된 자원은 그 프로세스가 자발적으로 사용을 마치고 자원이 회수될 때까지 해당 프로세스에 할당되어 있다.
Circular wait : 프로세스의 집합 {P0, P1, ..., Pn}에서 P0가 P1이 보유한 자원을 대기하고, P1은 P2가 보유한 자원을 대기하고, ... , Pn는 P0가 보유한 자원을 대기하는 순환적인 대기 관계가 형성된 것이다.

Deadlock에 무조건 빠지는 경우 : Resource allocation 구조에서 프로세스의 자원 할당 구조가 원을 그리면서, 각 프로세스의 리소스는 1개뿐일 때 항상 Deadlock에 빠지게 된다.

시스템에 프로세스 P1, P2, P3, P4가 있고, 자원 Ra, Rb, Rc, Rd가 하나씩 있다.
프로세스 P1, P2, P3, P4는 각각 자원 Ra, Rb, Rc, Rd를 보유하고 있다.
프로세스 P1, P2, P3, P4는 각각 자원 Rb, Rc, Rd, Ra를 요청하고 있다.
Mutual Exclusion, Hold and wait, No preemption, Circular wait (Ra → P1 → Rb → P2 → Rc → P3 → Rd → P4 → Ra), 4가지 조건을 모두 만족하며, 다음과 같은 방식의 프로세스 구조는 항상 Deadlock에 빠지게 된다.

3. Deadlock Prevention Strategy

데드락이 발생하기 위한 필수 조건 4가지 중 한 가지라도 만족하지 않으면, 데드락을 예방할 수 있다.

이한량

한량 극복 프로젝트

이전 포스트

[Operating System] Chapter 6