[운영체제] 동기화 예제 3) 식사하는 철학자 문제

 

1. 식사하는 철학자 문제  Dining Philosopher Problem

1)  식사하는 철학자 문제 

• 5명의 철학자와 5개의 젓가락이 있다.
• 철학자는 생각 → 식사 → 생각 → 식사 과정을 반복한다.
• 철학자는 자신의 왼쪽 젓가락을 집고, 오른쪽 젓가락을 집어야만 식사가 가능하다. (2개 집어야 식사 가능)
• 배가 부르면 젓가락을 내려놓는다.

 

2) 예제 코드

• 젓가락 -> 세마포 (# of permit = 1. 1 명만 젓가락 들 수 있음)
• 젓가락과 세마포에 일련번호: 0 ~ 4
• 순서 : 왼쪽 젓가락 → 오른쪽 젓가락 

/* Dining Philosopher Problem */

import java.util.concurrent.Semaphore;

class Philosopher extends Thread {
    int id; // philosopher id
    Semaphore lstick, rstick; // left, right chopsticks
    Philosopher(int id, Semaphore lstick, Semaphore rstick) {
        this.id = id;
        this.lstick = lstick;
        this.rstick = rstick;
    }
    public void run() {
        try {
            while (true) {
                lstick.acquire();
                rstick.acquire();
                eating();
                lstick.release();
                rstick.release();
                thinking();
            }
        } catch (InterruptedException e) {}
    }

    void eating() {
        System.out.println("[" + id + "] eating");
    }
    void thinking() {
        System.out.println("[" + id + "] thinking");
    }
}

class Main {
    static final int num = 5; // number of philosphers & chopsticks
    public static void main(String[] args) {
        int i;
        /* chopsticks */
        Semaphore[] stick = new Semaphore[num];
        for (i = 0; i < num; i++)
            stick[i] = new Semaphore(1);
        /* philosophers */
        Philosopher[] phil = new Philosopher[num];
        for (i = 0; i < num; i++)
            phil[i] = new Philosopher(i, stick[i], stick[(i + 1) % num]);
        /* let philosophers eat and think */
        for (i = 0; i < num; i++)
            phil[i].start();
    }
}

/*
Output
[1] eating
[0] eating
[3] eating
[0] thinking
[0] eating
[0] thinking
[1] thinking
[3] thinking
[4] eating
[4] thinking
[4] eating
[4] thinking
[4] eating
[4] thinking
[4] eating
[4] thinking
[4] eating
[4] thinking
[4] eating
[4] thinking
[4] eating
[4] thinking
[4] eating
[4] thinking
[4] eating
[4] thinking
[4] eating
[4] thinking
[4] eating
[4] thinking
[4] eating
[4] thinking
[4] eating
[4] thinking
[4] eating
[4] thinking
[4] eating
[4] thinking
[4] eating
[4] thinking
[4] eating
[4] thinking
[4] eating
[4] thinking
[4] eating
[4] thinking
[4] eating
[4] thinking
[2] eating

*/

문제점

무한 루프 돌도록 실행했는데 돌다가 중지된다.

starvation (모든 철학자가 식사를 하지 못해 굶어 죽는 상황)

원인 : 교착상태 (deadlock)

public void run() {
        try {
            while (true) {
            	/* 수정한 부분 */
                if (id%2 == 0) {
                    lstick.acquire();
                    rstick.acquire();                    
                }
                else {
                    rstick.acquire();
                    lstick.acquire();  
                }

                eating();
                lstick.release();
                rstick.release();
                thinking();
            }
        } catch (InterruptedException e) {}
    }

환형 대기를 깨기 위해

짝수번 프로세스는 왼, 오른쪽 들기, 홀수번 프로세스는 오, 왼쪽 들기

이렇게 수정하면 데드락이 발생하지 않는다