Почему пять столовых философов?

18

Мне было интересно, почему проблема обедающих философов основана на случае пяти философов. Почему не четыре?

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

falconepl
источник
1
Первоначальная проблема была описана Дейкстрой в 1965 году и называлась «Столовая пятерка» (см. Примечания вверху страницы 3).
Кажется, я помню, как учился у четырех столовых философов ...
Майкл Боргвардт
16
Это 5 философов, потому что он пытался увидеть, заметит ли кто-нибудь очевидное; Пять философов будут вместе говорить, пока ресторан не выгонит их, они даже никогда не возьмут свое серебро. Я мог бы прервать разговор достаточно долго, чтобы они начали есть. С 5, как только любые два перестают говорить на мгновение, в очереди уже есть один, ожидающий прерывания для обеспечения непрерывности.
Джимми Хоффа
1
@ Джимми Хоффа - + 1. И почему это не ответ?
Щепурин

Ответы:

17

Согласно тому, что написано в EWD310 «Иерархическое упорядочение последовательных процессов» , похоже, что номер 5 был выбран для образовательных целей, чтобы облегчить студентам понимание алгоритма, предназначенного для демонстрации решения проблемы.

В этой самой статье далее поддерживается идея о том, что 5 на самом деле не имеет отношения к общей проблеме, во-первых, явно заявив, что «проблема могла быть поставлена ​​для 9 или 25 философов ...», а затем, представив ее в виде двух одновременно работающих объекты "класс A и класс B, совместно использующие один и тот же ресурс ..."

Решение, используемое Дейкстрой, вводит три «состояния философа»: мышление, еда, голод. Код, представленный для решения проблемы, оперирует этими тремя состояниями вместе с не связанным с ним числом философов.

Если бы автор выбрал число философов 2, 3 или 4, это может вызвать замешательство у студентов, читающих код, независимо от того, связано ли выбранное число с количеством состояний или чем-то еще. Это можно легко проверить, попробовав указанные цифры в описании процитированных из EWD310 ниже ноты, например , как это изменило бы [0:4]к [0:3], [0:2], [0:1]и заявление с участием mod.

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


Упомянутый алгоритм представлен в EWD310 следующим образом:

... мы связываем с каждым философом переменную состояния, "C" скажем, где

C[i] = 0значит: философ iдумает

C[i] = 2значит: философ iест.

...

введем для последнего перехода промежуточное состояние

C[i] = 1значит: философ iголоден

Теперь каждый философ будет циклически проходить через состояния 0, 1, 2, 0 ...... Следующий вопрос, который нужно задать, состоит в следующем: когда (опасный) переход от 1 к 2 должен произойти для философа K?

...

Во вселенной мы предполагаем

1) semaphore mutexизначально = 1

2) то integer array C[0:4], что изначально весь элемент = 0

3) semaphore array prisem[0:4]изначально все элементы = 0

4) procedure test (integer value K);

if C[(K-1) mod 5] ≠ 2 and C[K]= 1
    and C[(K+1) mod 5] ≠ 2 do
      begin C[K]:= 2; V(prisem[K]) end;

(Эта процедура, которая устраняет нестабильность в Kслучае ее наличия, будет вызываться только из критической секции).

В этой вселенной жизнь философа wтеперь может быть закодирована

cycle begin think;
            P (mutex);
               C[w]:= 1; test (w);
            V(mutex);
            P(prisem[w]); eat
            P(mutex);
               C[w]:= 0; test [(w+l) mod 5];
               test [(w-1) mod 5];
            V(mutex)
      end

И это завершает решение, к которому я стремился ...

комар
источник
2
Тогда я не был бы философом, потому что в то же время я могу думать, когда ем или голоден. И еще: никто из них не пьет и даже не разговаривает.
ot--
5

Только Дейкстра может ответить наверняка, но я был бы достаточно уверен, что это произвольно.

«Первоначально он был сформулирован в 1965 году Эдсгером Дейкстра как упражнение для студенческого экзамена, представленное с точки зрения компьютеров, конкурирующих за доступ к периферийным устройствам на магнитной ленте. Вскоре после этого Тони Хоар дал этой проблеме ее нынешнюю формулировку».

http://en.wikipedia.org/wiki/Dining_philosophers_problem

Эойн Кэрролл
источник
2
Рассмотрим проблему четырех посетителей по сравнению с пятью. Как меняется проблема? Это проще или сложнее? Это был экзаменационный вопрос - сложнее, вероятно, тот, который желательно задать.
2

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

Это мнение; У меня нет исторических знаний о том, что приходило в голову автору.

Эмилио М Бумачар
источник
Этот момент имеет решающее значение. С четырьмя философами две пары могли по очереди есть.
Аарон Брик