Почему у монитора-столового философии нет тупика, а есть голод?

Question

Из концепции операционной системы

5.8.2. Обедание философов с использованием мониторов

Далее мы проиллюстрируем концепции мониторов, представив решение без тупиковых ситуаций для философии столовой. Это решение налагает ограничение на то, что философ может брать свои палочки для еды, только если они оба доступны. Чтобы закодировать это решение, нам нужно различать три состояния, в которых мы можем найти философа. Для этого введем следующую структуру данных:

enum {THINKING, HUNGRY, EATING} state[5];

Философ я могу установить переменную state[i] = EATING только если двое ее соседей не едят (state[(i+4) % 5] != EATING) а также (state[(i+1) % 5] != EATING),

Нам также нужно объявить

condition self[5];

Это позволяет философу задерживать себя, когда она голодна, но не может получить палочки для еды, в которых она нуждается.

monitor DiningPhilosophers
{

    enum {THINKING, HUNGRY, EATING} state[5];
    condition self[5];
    void pickup(int i) {

        state[i] = HUNGRY;
        test(i);
        if (state[i] != EATING)
            self[i].wait();

    }
    void putdown(int i) {

        state[i] = THINKING;
        test((i + 4) % 5);
        test((i + 1) % 5);

    }
    void test(int i) {

        if ((state[(i + 4) % 5] != EATING) &&
        (state[i] == HUNGRY) &&
        (state[(i + 1) % 5] != EATING)) {
            state[i] = EATING;
            self[i].signal();
        }

    }
    initialization code() {

        for (int i = 0; i < 5; i++)
            state[i] = THINKING;
    }

}

Рисунок 5.18. Решение проблемы столовой-философа на мониторе.

Каждый философ, прежде чем начать есть, должен вызвать операцию pickup(), Этот акт может привести к приостановке философского процесса. После успешного завершения операции философ может есть. После этого философ призывает putdown() операция.

DiningPhilosophers.pickup(i);
...
eat
...
DiningPhilosophers.putdown(i);

Легко показать, что это решение гарантирует, что нет двух соседей, которые едят одновременно, и что никаких тупиков не возникнет.

Мы отмечаем, однако, что философ может умереть от голода. Мы не представляем решение этой проблемы, а оставляем его в качестве упражнения для вас.

Почему у монитора нет тупиков?

Почему философ может умереть от голода?

Каково решение этой проблемы?

Благодарю.

Answer 1

Чтобы понять, почему два соседа никогда не могут есть одновременно, взгляните на test(int i) метод. Это единственное место, где философское государство EATING:

if ((state[(i + 4) % 5] != EATING) &&
    (state[i] == HUNGRY) &&
    (state[(i + 1) % 5] != EATING)) {
        state[i] = EATING;
        self[i].signal();
}

Предыдущее условие if гарантирует, что для любого философа i ни один из его соседей (i + 4) % 5 ни (i + 1) % 5 поедание.

Истощение возможно, потому что signal() не является справедливым: он пробуждает любой из ожидающих потоков случайным образом и, таким образом, может не разбудить определенный поток в течение произвольно долгого времени.