Обедающие философы, использующие бинарные семафоры
Может ли этот псевдокод решить проблему столовой философии с максимальным параллелизмом? Вот 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
}
}
Это должно решить проблему столового философа с максимальным параллелизмом, потому что замок снимается после того, как один философ приобрел обе вилки. Но так ли это? И будет ли какая-то проблема с живостью? Я сбит с толку.
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()
зависает до тех пор, пока ресурс не будет выпущен, тогда мьютекс никогда не будет освобожден, и никто из других философов не сможет добиться прогресса, поэтому только один философ будет есть одновременно.