Недетерминированные автоматы в проектировании систем параллельной обработки. Вашкевич Н.П. - 188 стр.

      Задача «обедающие философы» является примером классической
задачи, иллюстрирующей работу параллельных процессов, совместно
использующих пересекающие группы ресурсов. Эта задача рассматривается
во многих источниках, например, в [75, 76], где условие задачи
формулируется следующим образом.
       Пять философов, решая свои философские проблемы, время от времени,
почувствовав голод, заходят в общую столовую, чтобы подкрепиться. В столовой за
круглым столом расставлены пять стульев, каждый из которых занимает определенный
философ. В центре стола находится большое блюдо спагетти, а между двумя соседними
стульями на столе лежит по одной вилке. Для того чтобы покушать спагетти, философ
должен обязательно взять две вилки, расположенные непосредственно слева и справа от
него и наполнить с их помощью свою тарелку спагетти из общего блюда. После этого
философ может приступить к трапезе, используя те же обе вилки. Окончив трапезу, он
кладет вилки на свои места и выходит из столовой.
     Тупиковая ситуация может возникнуть в том случае, если все пять
философов для утоления голода сядут на свои стулья одновременно и
каждый из них возьмет одновременно по одной, например, правой вилке. В
этом случае никто из философов не сможет приступить к трапезе, т.к.
любому из них для этого необходимы две вилки. Такую конфликтную
ситуацию принято называть взаимоблокировкой процессов.
     Одно из возможных решений рассматриваемой задачи, которое может
позволить избежать взаимоблокировки процессов, основывается на том,
чтобы не допускать пребывания в столовой всех пяти философов. В
частности, исходя из условий задачи, когда количество ресурсов (вилок)
ограничено, трапезой в столовой могут одновременно заниматься лишь два
философа (или один). Однако такое обслуживание не позволит избежать
другой конфликтной ситуации, называемой взаимоотталкиванием процессов,
если не предусмотреть специальных мер, позволяющих избежать такой
ситуации. Для рассматриваемой задачи «обедающие философы»
взаимоотталкивание процессов может возникнуть в том случае, если два
философа по договоренности между собой поочередно занимают вилки слева
и справа от третьего философа так, что он никогда не сможет
воспользоваться обеими вилками. Это и есть ситуация взаимоотталкивания.
Для иллюстрации действующих в задаче «обедающие философы» процессов
и возможных связях между ними и ресурсами (вилками) воспользуемся
диаграммой, представленной на рис.6.11.




                                                                                188