Обедающие философы, использующие бинарные семафоры

Question

Может ли этот псевдокод решить проблему столовой философии с максимальным параллелизмом? Вот mutex является двоичным семафором, инициализированным в 1. Предполагается, что вилки пронумерованы от 0 до (N-1). Всего N философов пронумерованы от 0 до (N-1).

void philosopher(int i)    // ith philosopher
{   
   while (true)
   {
        think();
        down(&mutex);          // acquire lock
        take_fork(i);            // take left fork
        take_fork((i+1)%N);        // take right fork
        up(&mutex);          // release the lock
        eat();
        down(&mutex);       // acquire lock
        put_fork(i);
        put_fork((i+1)%N);
        up(&mutex);        // release the lock
   }    
}

Это должно решить проблему столового философа с максимальным параллелизмом, потому что замок снимается после того, как один философ приобрел обе вилки. Но так ли это? И будет ли какая-то проблема с живостью? Я сбит с толку.

Answer 1

Чтобы ответить на ваш вопрос, я хотел бы представить след событий, который, кажется, приводит ваших философов в нежелательное состояние.

Рассмотрим систему с N>2 философами Ph(0),...,Ph(N-1) и следующей последовательностью действий:

Ph(1).think();
Ph(0).think();
Ph(1).down(&mutex);
Ph(1).take_fork(1);
Ph(1).take_fork(2);
Ph(1).up(&mutex);
Ph(0).down(&mutex);
Ph(0).take_fork(0);
Ph(0).take_fork(1);

Напомним, что fork(1) уже приобретен Ph(1), Теперь в зависимости от семантики take_fork() может произойти другое поведение.

Если take_fork() немедленно выходит из строя, если вилка не может быть получена, то fork(0) никогда не будет выпущен

Если take_fork() зависает до тех пор, пока ресурс не будет выпущен, тогда мьютекс никогда не будет освобожден, и никто из других философов не сможет добиться прогресса, поэтому только один философ будет есть одновременно.