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

Отсутствие голодания.

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

2.