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

Алгоритм обедающих философов

В алгоритме Рикарта-Агравала для работы с КС требовался обмен 2(N – 1) сообщениями. Ниже мы опишем алгоритм, требующий 2(N – 1) сообщений только в наихудшем случае. Для этого предположим, что распределенная система состоит из большого числа процессов, однако число процессов, активно работающих с КС, невелико. Представленный в данном пункте алгоритм позволяет процессам, незаинтересованным в работе с КС, в конце концов, не участвовать в обмене сообщениями.
В отличие от алгоритма Рикарта-Агравала, в котором процесс запрашивает разрешение у всех других процессов каждый раз перед входом в КС, в рассматриваемом алгоритме такие разрешения представлены в виде специальных сущностей (вспомогательных ресурсов), которые процесс собирает для получения доступа к КС. При этом если
другие процессы не забирают эти разрешения обратно между последовательными обращениями процесса к КС, процесс сохраняет полученные разрешения у себя и может не запрашивать их при повторном входе в КС.
Важно также отметить, что в отличие от алгоритмов взаимного исключения, представленных выше, рассматриваемый алгоритм решает более общую задачу – задачу обедающих философов. Постановка этой задачи допускает одновременное выполнение нескольких процессов в своих КС при условии, что между этими процессами не может возникнуть конфликта доступа из-за обращений к любому из разделяемых ресурсов. В задаче обедающих философов такая ситуация моделируется разрешением нескольким философам питаться одновременно, если они не являются соседями.
Общие концепции разрешения конфликтов. Как уже отмечалось, проблема взаимного исключения возникает в тех случаях, когда несколько процессов претендуют на некоторый общий ресурс, который в каждый момент времени может быть использован только одним процессом. Если несколько процессов одновременно обращаются к такому разделяемому ресурсу, то имеет место конфликт доступа, который должен быть разрешен в пользу одного из этих процессов и, соответственно, в ущерб остальным процессам. Когда все конфликтующие процессы неразличимы между собой, т.е. в случае, когда какое-либо свойство одного из этих процессов присутствует также у всех остальных процессов, то разрешить конфликт становится невозможным без обращения к случайному выбору. Дело в том, что любой детерминированный метод, отдающий предпочтение одному процессу из группы для разрешения конфликта в его пользу, должен осуществлять такой выбор на основании какого-либо свойства, присущего именного этому процессу и отсутствующего у других. Таким образом, если не пользоваться методами случайного выбора, для разрешения конфликтов необходимо обеспечить выполнение следующих требований.

1.