Введение в распределенные

Симметричность.

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

3. Экономия.

Между переходами из состояния в состояние каждый философ отправляет и получает ограниченное число сообщений. А именно, если число соседей у философа равно d, то тогда этот философ отправит не более d и получит не более d сообщений, содержащих маркеры запроса или вилки. Действительно, предположим, что когда философ переходит в голодное состояние, у него содержится e "грязных" вилок. Тогда для получения недостающих вилок он должен отправить (d – e) запросов своим соседям. Кроме того, в худшем случае, до перехода в состояние приема пищи он может потерять все свои "грязные" вилки, и ему потребуется запросить их вновь. Т.к. философ находится в голодном состоянии при пересылке своей "грязной" вилки в этом же сообщении он может переслать и соответствующий ей маркер запроса. Поэтому для перехода из голодного состояния в состояние приема пищи потребуется не более чем 2d сообщений. В состоянии приема пищи и в состоянии размышления каждый философ может лишь получать сообщения с маркером запроса и отправлять вилки своим соседям, поэтому число получаемых и отправляемых сообщений также не превосходит 2d. В лучшем случае, когда все соседи философа постоянно находятся в состоянии размышления, он не будет получать от них запросов на вилки и может чередовать прием пищи и размышления вовсе без взаимодействия с ними.

4. Параллелизм.

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

5. Ограниченность.

Число сообщений, находящихся в каждый момент времени в состоянии пересылки между любыми двумя философами, не превосходит двух: сообщение с маркером запроса и сообщение, содержащее передаваемую вилку.
В заключение еще раз отметим, что для традиционной задачи взаимного исключения граф конфликтов представляет собой полный граф, т.к. по постановке этой задачи при попытке доступа к КС процесс потенциально входит в конфликт с любым другим процессом, который может претендовать на доступ к этой же КС. В наихудшем случае для входа в КС процессу придется собрать (N – 1) вилок: по одной от каждого другого процесса в распределенной системе. Поэтому при использовании алгоритма обедающих философов для входа в КС потребуется обмен максимум 2(N – 1) сообщениями. Если же, начиная с некоторого момента, процесс перестанет запрашивать вход в КС, он рано или поздно отдаст все свои вилки другим процессам и не будет участвовать в обмене сообщениями. Таким образом, число сообщений, требуемых для работы с КС, в среднем будет пропорционально только числу процессов, активно работающих с этой КС.
Пример работы алгоритма обедающих философов для традиционной задачи взаимного исключения приведен на рис. 4.8. Каждый процесс (философ) P_i поддерживает работу с массивами fork_i[1..N], dirty_i[1..N] и reqf_i[1..N] такими, что fork_i[j] = 1, когда P_i владеет общей с P_j вилкой, dirty_i[j] = 1, когда эта вилка "грязная", и reqf_i[j] = 1, когда у P_i находится маркер запроса, соответствующий общей с P_j вилке. В противном случае элементы перечисленных массивов содержат ноль. Направление ребер в графе предшествования Н обозначено стрелками. На рис. 4.8а изображено начальное состояние системы: вилки распределены так, что граф Н не содержит циклов, и все процессы находятся в состоянии выполнения вне КС (в размышлениях), т.е. все вилки "грязные", и ни у одного из процессов одновременно с вилкой не находится соответствующий ей маркер запроса. На рис. 4.8б процессы Р₂ и Р₃ переходят в состояние запроса на вход в КС (голодное состояние) и запрашивают недостающие вилки у своих соседей. Когда процесс P_i запрашивает вилку у процесса P_j, элемент массива reqf_i[j] сбрасывается в ноль. При получении процессом P_j запроса от P_i элемент массива reqf_j[i] устанавливается в единицу. По правилу передачи вилки процесс P₁ вынужден расстаться со своими вилками и передать их процессам P₂ и P₃, т.к. у Р₁ находятся "грязные" вилки вместе с поступившими на них запросами, и, кроме того, Р₁ не выполняется в КС (не принимает пищу). При передаче вилок они "очищаются" – см. рис. 4.8в.

(а)

(б)

(в)

(г)

(д)

(е)

(ж)

(з)

(и)
Рис. 4.8. Пример работы алгоритма обедающих философов.

Обратим внимание, что на рис. 4.8в процесс Р₂ содержит все необходимые ему вилки. При этом общая с Р₁ вилка – "чистая", а общая с Р₃ вилка – "грязная". Однако процесс Р₂ не может войти в КС (начать прием пищи), т.к. вместе с "грязной" вилкой у него содержится запрос на нее от процесса Р₃. Поэтому Р₂ отправляет эту вилку процессу Р₃, не забывая перед этим ее "почистить", как показано на рис. 4.8г. В итоге процесс Р₃ получит "чистые" вилки от Р₁ и Р₂ и сможет войти в КС. С началом работы в КС все вилки процесса Р₃ становятся "грязными": его приоритет по отношению к Р₁ и Р₂ понижается. Т.к. процесс Р₂ находится в состоянии запроса на вход в КС, он отправляет запрос на только что отданную вилку процессу Р₃. В свою очередь процесс Р₃ не возвращает "грязную" вилку процессу Р₂, т.к. в момент получения запроса процесс Р₃ выполняется внутри КС. Эта ситуация проиллюстрирована на рис. 4.8д. На рис. 4.8е процесс Р₁ переходит в состояние запроса на вход в КС и запрашивает вилки у своих соседей. Отметим, что процесс Р₃ не отдает процессу Р₁ "грязную" вилку,

т.к. выполняется в КС, а процесс Р₂ не отдает процессу Р₁ вилку, т.к. она – "чистая". Поэтому процессу Р₁ придется ожидать до тех пор, пока Р₃ не завершит свое выполнение в КС, и пока Р₂ не войдет и не выйдет из КС. После завершения выполнения в КС процесс Р₃ "очищает" все свои вилки и отдает их запрашивающим соседям – см. рис. 4.8ж. Обладая чистыми вилками, процесс Р₂ сможет войти в КС, как показано на рис. 4.8з. С началом работы в КС Р₂ понизит свой приоритет по отношению к Р₁ и Р₃. После завершения выполнения внутри КС, имея маркер запроса от Р₁, процесс Р₂ отдаст Р₁ общую с ним вилку, после чего Р₁ также получит возможность войти в КС, как показано на рис. 4.8и.

4.