Э. Таненбаум, М. ван Стеен - Распределённые системы (принципы и парадигмы) (1162619), страница 77
Текст из файла (страница 77)
Если были получены только сообщения ГОТОВО, топонятно, что обычный обмен сообщениями отсутствует, а значит, вычислениязавершены. В противном случае процесс Р инициирует создание нового снимкасостояния и продолжает делать это, пока не получит полного комплекта сообщений ГОТОВО.Были разработаны и другие решения задачи определения момента завершения вычислений, рассмотренной в этом пункте. Дополнительные ссылки и при-296Глава 5. Синхронизациямеры можно почерпнуть из [17, 421]. Обзор и сравнение различных решенийможно найти также в [285, 372].5.4. Алгоритмы голосованияМногие распределенные алгоритмы требуют, чтобы один из процессов был координатором, инициатором или выполнял другую специальную роль. Обычно неважно, какой именно процесс выполняет эти специальные действрш, главное, чтобы он вообще существовал.
В этом разделе мы рассмотрим алгоритмы, предназначенные для выбора координатора (это слово мы будем использовать в качестве обобщенного имени специального процесса).Если все процессы абсолютно одинаковы и не имеют отличительных характеристик, способа выбрать один из них не существует. Соответственно, мы должнысчитать, что каждый процесс имеет уникальный номер, например сетевой адрес(для простоты будем считать, что на каждую машину приходится по процессу).В общем, алгоритмы голосования пытаются найти процесс с максимальнымномером и назначить его координатором. Алгоритмы разлршаются способамипоиска.Мы также считаем, что каждый процесс знает номера всех остальных процессов. Чего процессы не знают, так это то, какие из них в настоящее время работают,а какие нет. Алгоритм голосования должен гарантировать, что если голосованиеначалось, то оно, рассмотрев все процессы, решит, кто станет новым координатором. Известны различные алгоритмы, например, [153, 159, 419].5 .
4 . 1 . Алгоритм забиякив качестве первого примера рассмотрим алгоритм забияки {bully algorithm), предложенный в [159]. Когда один из процессов замечает, что координатор больше неотвечает на запросы, он инициирует голосование. Процесс, например Р, проводитголосование следующим образом.1. Р посылает всем процессам с большими, чем у него, номерами сообщениеГОЛОСОВАНИЕ.2. Далее возможно два варианта развития событий:> если никто не отвечает, Р выигрывает голосование и становится координатором;^ если один из процессов с большими номерами отвечает, он становится координатором, а работа Р на этом заканчивается.В любой момент процесс может получить сообщение ГОЛОСОВАНИЕ от одного из своих коллег с меньшим номером.
По получении этого сообщения получатель посылает отправителю сообщение ОК, показывая, что он работает и готовстать координатором. Затем получатель сам организует голосование. В концеконцов, все процессы, кроме одного, отпадут, этот последний и будет новым ко-5.4. Алгоритмы голосования297ординатором.
Он уведомит о своей победе посылкой всем процессам сообщения,гласящего, что он новый координатор и приступает к работе.Если процесс, который находился в нерабочем состоянии, начинает работать,он организует голосование. Если он оказывается процессом с самым большим изработающих процессов номером, он выигрывает голосование и берет на себяфункции координатора. Итак, побеждает всегда самый большой парень в городишке, отсюда и название «алгоритм забияки».На рис. 5.11 приведен пример работы алгоритма забияки. Группа состоит извосьми процессов, пронумерованных от О до 7.
Ранее коордршатором был процесс 7, но он завис. Процесс 4 первым замечает это и посылает сообщениеГОЛОСОВАНИЕ всем процессам с номерами больше, чем у него, то есть процессам 5, 6 и 7, как показано на рис. 5.11, а. Процессы 5 и 6 отвечают ОК, как показано на рис. 5.11, б.
После получения первого из этих ответов процесс 4 понимает, что «ему не светит» и коордршатором будет одна из этих более важныхличностей. Он садится на место и ожидает, кто станет победителем (хотя ужесейчас он может сделать довольно точное предположение).© 0D^*» ©© ^ ©©Предыдущийкоординатор «завис»©© ^ ©©© ^ ©гаРис.
5 . 1 1 . Голосование по алгоритму забиякиНа ppic. 5.11, в показано, как оба оставшихся процесса, 5 и 6, продолжают голосование. Каждый посылает сообщения только тем процессам, номера у которых больше их собственных. На рис. 5.11, г процесс 6 сообгцает процессу 5, что298Глава 5. Синхронизацияголосование будет вести он. В это время 6 понимает, что процесс 7 мертв, а значит, победитель — он сам.
Если информация о состоянии сохраняется на дискеили где-то еще, откуда ее можно достать, когда с прежним координатором чтонибудь случается, процесс 6 должен записать все что нужно на диск. Готовый занять свою должность процесс 6 заявляет об этом путем рассылки сообщенияКООРДИНАТОР всем работающим процессам. Когда 4 получит это сообщение,он продолжит работу с той операции, которую пытался выполнить, когда обнаружил, что процесс 7 мертв, используя теперь в качестве координатора процесс 6.Таким образом, мы обошли сбой в процессе 7, и работа продолжается.Если процесс 7 запустится снова, ему будет достаточно послать всем остальным сообщение КООРДИНАТОР и вынудить их подчиниться.5.4.2. Кольцевой алгоритмДругой алгоритм голосования основан на использовании кольца.
В отличие отнекоторых других кольцевых алгоритмов в этом не требуется маркер. Мы предполагаем, что процессы физически или логически упорядочены, так что каждыйиз процессов знает, кто его преемник. Когда один из процессов обнаруживает, чтокоординатор не функционирует, он строит сообщение ГОЛОСОВАНИЕ, содержащее его номер процесса, и посылает его своему преемнику. Если преемник не работает, отправитель пропускает его и переходит к следующему элементу кольцаили к следующему, пока не найдет работающий процесс. На каждом шаге отправитель добавляет свой номер процесса к списку в сообщении, активно продвигаясебя в качестве кандидата в координаторы.В конце концов, сообщение вернется к процессу, который начал голосование.Процесс распознает это событие по приходу сообщения, содержащего его номерпроцесса.
В этот момент тип сообщения изменяется на КООРДИНАТОР и вновьотправляется по кругу, на этот раз с целью сообщить всем процессам, кто сталкоординатором (элемент списка с максимальным номером) и какие процессы входят в новое кольцо. После того как это сообщение один раз обойдет все кольцо,оно удаляется и процессы кольца возвращаются к обычной работе.Сообщениео голосовании[2]Предыдущийкоординаторвыбыл из строяНе отвечаетРис.
5.12. Кольцевой алгоритм голосования5.5. Взаимное исключение299На рис. 5.12 мы видим, что происходит, когда два процесса, 2 и 5, одновременно обнаруживают, что предыдущий координатор, процесс 7, перестал работать. Каждый из них строит сообщение ГОЛОСОВАНИЕ и запускает это сообщение в путь по кольцу независимо от другого. В конце концов, оба сообщенияпроходят все кольцо, и процессы 2 и 5 превращают их в сообщения КООРДИНАТОР, которые пересылаются тем же элементам кольца и в том же порядке.Когда эти сообщения, в свою очередь, совершают полный круг, они удаляются.Больше не происходит ничего такого, что потребовало бы дополнительного обмена сообщениями.
Даже в наихудшем случае все проделанное столь незначительно загружает сеть, что это нельзя назвать расточительством.5.5. Взаимное исключениеСистемы, состоящие из множества процессов, обычно проще всего программировать, используя критические области. Когда процесс нуждается в том, чтобы считать или обновить совместно используемые структуры данных, он сначала входит в критическую область, чтобы путем взаимного исключения убедиться, чтони один из процессов не использует одновременно с ним общие структуры данных. В однопроцессорных системах критические области защищаются семафорами,мониторами и другими конструкциями подобного рода.
Теперь мы рассмотримнесколько примеров того, как именно критические области и взаимные исключения реализуются в распределенных системах. Описание этих методов и библиографию по ним можно найти в [373, 420].5 . 5 . 1 . Централизованный алгоритмНаиболее простой способ организации взаимных исключений в распределенныхсистемах состоит в том, чтобы использовать методы их реализации, принятые воднопроцессорных системах. Один из процессов выбирается координатором (например, процесс, запущенный на машине с самым большим сетевым адресом).Каждый раз, когда этот процесс собирается войти в критическую область, он посылает координатору сообщение с запросом, в котором уведомляет, в какую критическую область он собирается войти, и запрашивает разрешение на это.
Еслини один из процессов в данный момент не находится в этой критической области,координатор посылает ответ с разрешением на доступ, как показано на рис. 5.13, а.После получения ответа процесс, запросивший доступ, входит в критическую область.Предположим теперь, что другой процесс, 2, запрашивает разрешение на входв ту же самую область (рис. 5.13, б). Координатор знает, что в этой критическойобласти уже находится другой процесс, и не дает разрешения на вход.
Конкретный способ запрещения доступа зависит от особенностей системы. На рис. 5.13, бкоординатор просто не отвечает, блокируя этим процесс 2, который ожидает ответа. Он также может послать ответ, гласящий «доступ запрещен». В любом случаеон ставит запрос от процесса 2 в очередь и ожидает дальнейших сообщений.300Глава 5. Синхронизация©0©Запрос©©©Запрос /^ОтветанетОчередьпуста©Освобождениекритической >1г / О КобластиШКоординаторРис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
