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

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

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

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

Такая постановка задачи в качестве частного случая включает в себя классическую формулировку проблемы обедающих философов, когда пять философов сидят вокруг круглого стола, и, соответственно, каждый из них имеет по два соседа. В этом случае граф G будет представлять собой кольцо с пятью вершинами. Кроме того, рассмотренная в предыдущих пунктах традиционная задача взаимного исключения для N процессов также может быть описана в терминах обобщенной задачи обедающих философов. А именно, в этом случае в каждый момент времени принимать пищу будет разрешено максимум одному философу. Поэтому, для задачи взаимного исключения граф G будет представлять собой полный граф из N вершин, а состояние приема пищи будет соответствовать выполнению процесса внутри КС.
Для разрешения конфликтов между собой философам необходим механизм определения приоритетов друг относительно друга, очевидно, удовлетворяющий рассмотренным ранее требованиям различимости и справедливости, чтобы не допустить вечного голодания философов. А именно, за конечное время голодный философ либо должен получить возможность поесть, обнаружив всех своих соседей в состоянии размышления, либо в случае возникновения конфликтов с соседями, рано или поздно, должен получить возможность разрешать все конфликты в свою пользу. Этот механизм может быть реализован в виде графа предшествования H, изменение которого осуществляется по следующим правилам.

• 
  Направление ребра в графе H изменяется только тогда, когда философ, находящийся в вершине, инцидентной данному ребру, переходит из голодного состояния в состояние приема пищи. То есть философ понижает приоритет по отношению к своему соседу только с началом употребления пищи.
  
• 
  При переходе философа в состояние приема пищи все ребра, инцидентные его вершине, одновременно изменяют свое направление в сторону этой вершины. Другими словами, кушающий философ понижает свой приоритет по отношению ко всем своим соседям.
  

Перечисленные правила основываются на следующем свойстве ориентированных графов. В результате переориентации всех ребер по
направлению к какой-либо вершине u не может быть создано никаких новых путей из вершины w в вершину v, для любых w и v ≠ u, т.к. через u не может пройти ни один путь (u не будет являться промежуточной вершиной на любом пути). Поэтому такие правила преобразования графа H не позволяют голодному философу, находящемуся в вершине v, опускаться вниз в порядке предшествования. Кроме того, очевидно, что эти правила сохраняют свойство ацикличности графа H, т.к. при переориентации всех ребер по направлению к вершине u не может быть получено ни одного цикла, содержащего u.
Покажем теперь, что при таких правилах изменения H гарантируется, что голодный философ, в конце концов, поест, т.к. поднимется вверх в порядке предшествования и сможет разрешить все конфликты в свою пользу. Пусть философ в вершине v с глубиной k, k > 0, голоден и находится выше всех своих голодных соседей в порядке предшествования. Тогда либо v начнет прием пищи, либо какой-нибудь из его размышляющих соседей, стоящих выше v в порядке предшествования, перейдет в голодное состояние. Голодный философ, являющийся корнем графа H, имеет приоритет над всеми своими соседями, поэтому сможет принимать пищу вне зависимости от того, голодны ли его соседи или нет. Кроме того, согласно правилам изменения H, любой голодный философ, начав прием пищи, опускается в самый низ в порядке предшествования, тем самым продвигая других голодных философов вверх. Таким образом, по индукции, голодный философ с глубиной k, в конце концов, приступит к приему пищи, потому что он стоит выше всех своих голодных соседей с глубиной, большей чем k, а все философы с глубиной, меньшей чем k, если они станут голодными, рано или поздно опустятся в порядке предшествования ниже рассматриваемого философа.

Рис. 4.7. Пример изменения графа предшествования.

На рис. 4.7 показан пример изменения графа предшествования H, представленного ранее на рис. 4.5. На рис. 4.7 бывший корень P₁ начинает принимать пищу, что в терминах задачи заседаний пяти комитетов

соответствует заседанию комитета 1, и понижает свой приоритет по отношению к своим соседям P₂, P₄ и P₅. Вершина P₅ становится корнем.
Приведенные выше правила работы с графом H обеспечивают выполнение требований различимости философов и справедливости разрешения конфликтов. Однако сами по себе они не дают представления о способе реализации графа H в распределенной системе и не определяют, можно ли голодному философу приступить к приему пищи, не нарушая при этом требования задачи, согласно которому соседи не должны питаться одновременно. Действительно, голодный философ может перейти в состояние приема пищи, когда он находится выше всех своих голодных соседей в порядке предшествования, и при этом ни один из его соседей не ест. Если же хотя бы один из его соседей принимает пищу, голодному философу необходимо ожидать до тех пор, пока кушающий сосед не закончит питаться. Как философам определить, питается ли его сосед или нет?
Для ответа на этот вопрос в решение задачи вводятся вспомогательные ресурсы, вилки (англ. fork), таким образом, что с каждым ребром графа G ассоциируется ровно одна вилка. Вилка, ассоциируемая с ребром, соединяющим философов u и v, находится в их совместном доступе, но в каждый момент времени может принадлежать только одному из них. Для того чтобы поесть, потребуем от философа собрать все вилки по всем ребрам графа, инцидентным вершине, в которой он находится. Из этого требования будет следовать, что любые два соседних философа не смогут одновременно находиться в состоянии приема пищи, т.к. они не смогут одновременно владеть вилкой, находящейся в их совместном доступе.
Очевидно, что с введением вспомогательных ресурсов, правило перехода из голодного состояния в состояние приема пищи и правило передачи вилок от одного философа к другому можно сформулировать следующим образом.

1. 
   Голодный философ u может начать принимать пищу только тогда, когда u владеет всеми вилками от всех своих соседей, и для любого его соседа v верно, что u имеет приоритет над v или v находится в состоянии размышления.
   
2. 
   Не принимающий пищу философ u должен отдавать вилку своему голодному соседу v только в случаях, когда v имеет приоритет над u, или когда u находится в состоянии размышления, т.е. не заинтересован в обладании этой вилкой.
   

Для реализации этих правил философам необходимо определять взаимный приоритет друг относительно друга с помощью графа предшествования H. Отметим, что особенность представления графа H в распределенной системе как раз и состоит в том, что философ должен
определять наличие или отсутствие приоритета над своим соседом исходя только из своего локального состояния, и приоритет между парой соседних философов должен согласованно изменяться обоими философами.
Задать граф H в распределенной системе можно путем введения для каждой вилки атрибута "грязная" / "чистая" и определения относительного приоритета таким образом, что философ u имеет приоритет над философом v, т.е. ребро в графе H ориентировано из вершины u в вершину v, тогда и только тогда, когда 1) философ u владеет общей с v вилкой, и она "чистая", или 2) философ v владеет общей с u вилкой, и она "грязная", или
3) вилка находится в процессе передачи от философа v к философу u.
Соответственно представленные выше правила изменения графа H
будут иметь следующее выражение.

• 
  Философ, принимающий пищу, владеет всеми общими с его соседями вилками, и все эти вилки "грязные". Это утверждение соответствует правилу, согласно которому кушающий философ получает более низкий приоритет по отношению ко всем своим соседям.
  
• 
  Философ, владеющий "чистой" вилкой, продолжает ее удерживать до тех пор, пока он не перейдет в состояние приема пищи. Все это время вилка остается "чистой". Это утверждение соответствует правилу, согласно которому приоритет философа по отношению к своему соседу понижается только с началом употребления пищи.
  
• 
  Если вилка использовалась для приема пищи, она становится "грязной" и остается "грязной" до тех пор, пока она не будет передана соседнему философу. Вилка становится "чистой" только при передаче соседнему философу. Важно отметить, что передача "очищенных" вилок не изменяет ориентацию ребер графа H, поэтому это утверждение также соответствует правилу, согласно которому приоритет философа по отношению к своему соседу понижается только с началом употребления пищи.
  
• 
  "Чистыми" вилками владеют только голодные философы.
  

Последнее утверждение следует из следующих соображений. Предположим, что "чистой" вилкой может владеть размышляющий философ. Философ имеет право передать вилку своему соседу только, если вилка "грязная". Поэтому размышляющий философ будет удерживать вилку у себя в течение всего периода размышления. Однако по условиям задачи философ может размышлять бесконечно долго и, как следствие, может удерживать вилку в течение произвольного времени, тем самым приводя своих соседей к бесконечному голоданию.
Таким образом, в случае представления графа H с помощью атрибутов вспомогательных ресурсов, а именно, вилок, правило перехода
из голодного состояния в состояние приема пищи и правило передачи вилок от одного философа к другому принимают вид:

1. 
   Голодный философ u может начать принимать пищу только тогда, когда u владеет всеми вилками от всех своих соседей, и для любого его соседа v верно, что общая с v вилка – "чистая", или v находится в состоянии размышления.
   
2. 
   Не принимающий пищу философ u должен отдавать вилку своему голодному соседу v только в случае, когда общая с v вилка – "грязная".
   

Согласно второму правилу философ u передает "грязную" вилку своему соседу v только, если v голоден. Отсюда, кстати, следует, что закончивший прием пищи философ, не будет возвращать вилки своим соседям, если они находятся в состоянии размышления и, следовательно, не заинтересованы в них. Соответственно, если философ, обладающий всеми вилками, повторно проголодается раньше любого из своих соседей, он сможет поесть без необходимости вновь собирать все вилки. Но как философу определить, голоден его сосед или нет?
Для ответа на этот вопрос потребуем от голодного философа, не обладающего какой-либо вилкой, явным образом запрашивать ее у своего соседа. Для каждой пары соседних философов будем использовать маркер запроса (англ. request-token), соответствующий общей для этих философов вилке. В каждый момент времени маркер запроса может находиться только у одного философа из пары или находиться в состоянии пересылки от одного философа к другому. Обладатель маркера имеет право запрашивать вилку у своего соседа, пересылая ему маркер. Тогда, если у философа u находится одновременно и общая с философом v вилка, и маркер запроса, соответствующий этой вилке, то u может заключить, что v голоден.
Таким образом, решение задачи обедающих философов определяется следующими правилами.

1.