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

Варианты оптимизации алгоритма Реймонда. Одним из вариантов оптимизации алгоритма Реймонда может быть допустимое в некоторых случаях совмещение запроса REQUEST вместе с сообщением TOKEN. А именно, при выходе из КС процессу может потребоваться передать маркер своему соседу с помощью функции AssignPrivilege, а также отправить ему запрос на возврат маркера с помощью функции MakeRequest. Если передачу маркера отложить до определения необходимости передачи запроса, в таких ситуациях отправку TOKEN и REQUEST можно совместить в одном сообщении, тем самым уменьшая общее количество передаваемых сообщений. При получении такого совмещенного сообщения оно обрабатывается как два независимых сообщения. Стоит отметить, что совмещенные сообщения могут быть отправлены только процессами, не являющимися листьями дерева, т.к. листья не могут требовать возврата маркера сразу же после выхода из КС. Данный подход становится эффективным при высокой интенсивности поступления запросов на вход в КС. При низкой загрузке вероятность того, что в очереди Q процесса, передающего маркер, содержатся идентификаторы других процессов, нуждающихся в маркере, невелика.
Другим вариантом оптимизации является так называемая "жадная" версия алгоритма Реймонда. Суть этого алгоритма заключается в том, что если процесс P_i запрашивает доступ к КС, он может помещать значение self не в конец своей очереди Q, как в стандартном алгоритме Реймонда, а в ее начало вперед идентификаторов других процессов, уже находящихся в очереди. В этом случае при получении маркера процесс P_i сможет сразу войти в КС, не передавая маркер соседним с ним процессам и не дожидаясь, пока они закончат свою работу с маркером. Как и для предыдущего случая, этот подход не влияет на работу системы при низкой загрузке, т.к. self, скорее всего, окажется единственным элементом в очереди Q. При высокой интенсивности поступления запросов "жадный" алгоритм позволит уменьшить среднюю задержку на получение маркера и,
как следствие, увеличить число входов в КС за определенный интервал времени. Однако это преимущество будет достигнуто за счет процессов, являющихся листьями дерева. Действительно, в стандартном алгоритме Реймонда задержка на получение маркера приблизительно одинакова для всех процессов в системе вне зависимости от того, являются ли они листьями дерева или нет. В случае "жадной" версии алгоритма Реймонда листья могут ожидать прихода маркера значительно дольше процессов, находящихся в вершинах ветвления, и, соответственно, получать его в пользование гораздо реже. Например, если процессы распределенной системы на рис. 4.10 постоянно запрашивают вход в КС, то процессы Р₁ и Р₄, находящиеся в вершинах ветвления, будут получать возможность войти в КС в три раза чаще, чем остальные процессы, и соответственно, задержка на получение маркера для них будет в три раза меньше.
Таким образом, в отличие от стандартного алгоритма "жадный" алгоритм Реймонда не является справедливым в том смысле, что он предоставляет процессам неравные шансы войти в КС. На самом деле, эффективность "жадной" версии обеспечивается напрямую за счет справедливости предоставления доступа к КС, но этот алгоритм по- прежнему гарантирует отсутствие голодания процессов. Действительно, очередь Q каждого процесса обслуживается в порядке FIFO и перед идентификатором процесса, стоящим в начале очереди Q, может быть поставлено только значение self и только один раз, т.к. при выходе из КС процесс должен будет передать маркер процессу с этим идентификатором. Поэтому, в конце концов, идентификатор каждого процесса в очереди Q доберется до ее начала, и, следовательно, процесс, нуждающийся в маркере, получит его.