[운영체제] 동기화 문제들(The Dining-Philosophers Problem)

The Dining Philisophers Problem(식사하는 철학자 문제)

출처:  Operating System Concepts tenth Edition,  Abraham Silberschatz,  Peter Baer Galvin,  Greg Gagne

철학자 다섯 명이 원형 테이블에서 식사를 하려고 한다. 테이블 중앙에 음식이 있고, 다섯 개의 젓가락이 철학자 사이에 놓여 있다. 철학자가 배고파서 음식을 먹으려 할때 자신의 왼쪽과 오른쪽 젓가락을 잡으려고 하고, 두 젓가락을 잡아야 식사가 가능하다. 이후 식사가 끝나면 젓가락 두 개를 테이블에 놓고 다시 생각에 빠지는 상황이다.

철학자 문제 알고리즘은 다음과 같다.

while(true) {
    wait(chopstick[i]); // 왼쪽 젓가락 집기
    wait(chopstick[(i+1) % 5]); // 오른쪽 젓가락 집기

    // 젓가락 두 개 모두 집으면 성공
    // 먹는다

    signal(chopstick[i]); // 왼쪽 젓가락 내려놓기
    signal(chopstick[(i+1) % 5]); // 오른쪽 젓가락 내려놓기

    // 생각한다.
}

The Dining Philosophers Problems 문제 해결

위의 코드에서 둘 중 하나라도 실패하면 wait에 걸려서 block되는데, 어떤 프로세스가 밥을 먹고자 하여 wait() 호출하는 사이에 또 다른 프로세스가 wait()을 호출하면 데드락이 발생할 수 있다. 특히 세마포어는 사용시 굉장히 유용하지만 한편으로는 잘못된 설계로 인하여 데드락을 발생시킬 수 있다. 따라서 모니터를 이용해서 그 문제를 상쇄할 수 있다. 모니터는 프로그래머가 정의한 함수에 mutual exclusion을 제공하며 모니터 안에서 항상 하나의 프로세스만 실행 가능하다.

출처:  Operating System Concepts tenth Edition,  Abraham Silberschatz,  Peter Baer Galvin,  Greg Gagne

모니터 안에서 하나의 프로세스가 공유된 데이터와 함수를 지니고 실행하고 있으면, 모니터 진입을 원하는 다른 프로세스들은 모두 entry queue에 머무르게 된다. 하지만 이러한 구조는 문제점을 지니고 있는데, 만일 실행중인 프로세스가 I/O Interrupt에 걸려서 I/O 작업을 하게 된다면 혼자 모니터를 점유하며 시간을 보내게 되고 그 동안 다른 프로세스들은 모니터에 진입하지 못하여 성능 저하가 발생하게 된다.

출처:  Operating System Concepts tenth Edition,  Abraham Silberschatz,  Peter Baer Galvin,  Greg Gagne

그리하여 해결책으로 condition variables를 추가하는데, condition variable은 쓸데없이 시간을 잡아먹는 프로세스를 condition queue에 넣어서 대기시키다가 다시 실행 준비가 되면 깨우기 전까지 보관한다.
예를 들어, A라는 조건변수가 있다면, A.wait(), A.signal()로 호출하게 된다.

• wait() : 이 연산을 호출한 프로세스는 다른 프로세스가 signal() 함수 호출할 때까지 차단되고, 차단된 프로세스는 해당 조건과 관련된 condition queue에서 잠들게 된다.
• signal() : 대기하고 있던 프로세스를 깨운다. 대기중인 프로세스가 아무것도 없으면 아무 작업도 수행하지 않는다.

이 구조에서 모니터 내의 프로세스가 signal 함수를 호출하여 다른 프로세스를 깨우면 모니터 내에 두 개의 프로세스가 동시에 실행하게 되는 문제점이 발생한다. 예를 들어, condition x에서 프로세스 P가 block되어 있을 때, 프로세스 Q가 x.signal()을 호출하여 프로세스를 P를 깨웠을 때, 두 가지의 방법이 생긴다.

• Signal and wait: 살려준 프로세스 Q가 모니터를 떠날 때까지 프로세스 P는 기다린다.
• Signal and continue: 살아난 프로세스 P가 먼저 실행하여 모니터를 떠나기 전까지 살려준 Q가 기다린다.

철학자 문제 해결코드

monitor DiningPhilosophers
{
    enum {THINKING, HUNGRY, EATING} state[5]; //철학자들의 3가지 상태
    condition self[5]; // 철학자가 두 개의 젓가락을 잡을 수 없을 때 대기 상태에 빠진다.

    void pickup(int i) { // 젓가락을 집는 행위
        state[i] = HUNGRY; // 젓가락을 집는 행위는 배고프다는 의미이므로 상태를 HUNGRY로 바꿔준다.
        test(i); // 배가 고픈 i 철학자는 식사해도 되는지 test()를 수행한다.
        if(state[i] != EATING) // i 철학자 상태가 EATING이 아니라면 대기 상태에 들어간다.
            self[i].wait();
    }

    void putdown(int i) { // 젓가락을 놓는 행위
        state[i] = THINKING; // 우선 i 철학자는 상태를 THINKING으로 바꾼다
        test((i + 4) % 5); // i 철학자 왼쪽 사람이 test를 한다.
        test((i + 1) % 5); // i 철학자 오른쪽 사람이 test를 한다.
    }

    void test(int i) {
        if((state[(i + 4) % 5] != EATING) && //i 철학자 왼쪽 사람이 식사하지 않음
            (state[i] == HUNGRY) && // i 철학자가 현재 배고픈 상황
            (state[(i + 1) % 5] != EATING)) { // i 철학자  오른쪽 사람이 식사하지 않음
                state[i] = EATING; // 세 조건 모두 만족하면 철학자 i는 상태를 EATING으로 바꿔준다.
                self[i].signal(); // 자기 자신인 i에게 signal을 보낸다.(처음에는 의미없음)
        }
    }

    initialization_code() { // 초기 상태는 모두 THINKING
        for(int i=0;i<5;i++) {
            state[i] = THINKING;
        }
    }
}

철학자는 DiningPhilosophers 모니터를 공유하며 다음 작업 순서를 사용하여 식사를 한다.

DiningPhilosophers.pickup(i);

//먹는다

DiningPhilosophers.putdown(i);

이로써 모니터를 사용하여 간단하게 동기화 할 수 있다.

 

참고자료

https://blog.naver.com/PostView.nhn?blogId=and_lamyland&logNo=221192481544 

[대딩의 운영체제, OS 14] 동기화 문제(Bounded Buffer, Readers Writers, Dining Philosophers Problem)와 모니터 Moni

 

https://yoongrammer.tistory.com/65

Process synchronization: 모니터(monitor)