Э. Таненбаум, М. ван Стеен - Распределённые системы (принципы и парадигмы) (1162619), страница 78

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 78)

5.13. Процесс 1 запрашивает у координатора разрешение на вход в критическуюобласть, и разрешение дано (а). Процесс 2 запрашивает разрешение на вход в ту жекритическую область, и координатор не отвечает (б). Когда процесс 1 выходитиз критической области, он сообщает об этом координатору,который разрешает доступ процессу 2 (е)Когда процесс 1 покидает критическую область, он посылает координаторусообщение, отказываясь от эксклюзивного доступа на область, как показано нарис.

5.13, в. Координатор выбирает первый элемент из очереди отложенных за­просов и посылает процессу разрешающее сообщение. Если процесс был блоки­рован (то есть для него это первое сообщение от координатора), он разблокиру­ется и входит в критическую область. Если процессу было отослано сообщениес запретом на доступ, он будет опрашивать приходящие сообщения или блоки.В любом случае, увидев разрешение, он войдет в критическую область.Легко заметить, что алгоритм гарантирует взаимное исключение: координа­тор позволяет войти в каждую критическую область только одному процессу зараз. Это, П0МР1М0 всего прочего, честно, поскольку разрешения выдаются в томже порядке, в каком они запрашивались. Никакой процесс никогда не ждет веч­но (зависания отсутствуют).

Схема также проста в реализации и использует дляработы с критической областью всего три сообщения (запросить, разрешить ивысвободить). Подобный алгоритм может использоваться и для другого выделе­ния ресурсов, а не только для работы с критическими областями.5.5.2. Распределенный алгоритмНаличие даже одного неработающего места в централизованных алгоритмах час­то недопустимо, поэтому исследователи обратились к распределенным алгорит­мам взаимного исключения [380].Рассматриваемый алгоритм требуют наличия полной упорядоченности собы­тий в системе. То есть в любой паре событий, например отправки сообщений,должно быть однозначно известно, какое из них произошло первым.

АлгоритмЛампорта, представленный в пункте 5.2.1, является одним из способов введенияподобной упорядоченности и может быть испо.льзован для расстановки отметоквремени распределенных взаимных исключений.Алгоритм работает следующим образом. Когда процесс собирается войти вкритическую область, он создает сообщение, содержащее имя критической облас­ти, свой номер и текущее время. Затем он отсылает это сообщение всем процес-5.5.

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

Можно выделить три варианта.> Если получатель не находится в критической области и не собирается ту­да входить, он отсылает отправителю сообщение ОК,-¥ Если получатель находится в критической области, он не отвечает, а поме­щает запрос в очередь.> Если получатель собирается войти в критическую область, но еще не сде­лал этого, он сравнивает метку времени пришедшего сообщения с меткойвремени сообщения, которое он отослал.

Выигрывает минимальное. Еслипришедшее сообщение имеет меньший номер, получатель отвечает посыл­кой сообщения ОК. Если его собственное сообщение имеет меньшую от­метку времени, получатель ставит приходящие сообщения в очередь, ни­чего не посылая при этом.После посылки сообщения-запроса на доступ в критическую область процессприостанавливается и ожидает, что кто-нибудь даст ему разрешение на доступ.После того как все разрешения получены, он может войти в критическую об­ласть. Когда он покидает критическую область, то отсылает сообщения ОК всемпроцессам в их очереди и удаляет все сообщения подобного рода из своей очереди.Попытаемся теперь понять, как работает алгоритм.

Если конфликты отсутст­вуют, все идет хорошо. Однако представим себе, что два процесса пытаютсяодновременно войти в одну и ту же критическую область, как показано нарис. 5.14, а.Входитв критическуюобластьВходитв критическуюобластьРис. 5.14. Два процесса одновременно хотят получить доступ в одну и ту же критическуюобласть (а). Процесс О имеет меньшую отметку времени и потому выигрывает (б). Когдапроцесс О завершает работу с критической областью, он отправляет сообщение ОК,и теперь процесс 2 может войти в критическую область (в)Процесс О рассылает всем запрос с отметкой времени 8, и одновременнос ним процесс 2 рассылает всем запрос с отметкой времени 12. Процесс 1 не ин-302Глава 5. Синхронизациятересуется входом в критическую область и в ответ посылает сообщение ОК имобоим.

Процессы О и 2 замечают конфликт и сравнивают отметки времени. Про­цесс 2 видит, что проиграл, и разрешает доступ процессу О, посылая ему сообще­ние ОК. Процесс О ставит ответ от процесса 2 в очередь для дальнейшей обработ­ки и входит в критическую секцию, как показано на рис. 5.14, б. Когда процесс Озаканчивает работу в критической области, он удаляет ответ 2 из очереди сооб­щений и отправляет процессу 2 сообщение ОК, разрешая ему войти в критиче­скую область, что и показано на рис. 5.14, в. Алгоритм работает, поскольку в слу­чае конфликтов наименьшая отметка времени выигрывает, а с очередностьюотметок времени способен разобраться любой процесс.Отметим, что показанная на рисунке ситуация могла бы в корне измениться,если бы процесс 2 послал свое сообщение раньше, чем это сделал процесс О, и по­лучил разрешение на доступ до создания своего ответа на сообщение от процесса 0.В этом случае процесс 2, зная о том, что в момент отсылки ответа он находится вкритической области, просто поместил бы запрос от процесса О в очередь, не по­сылая никакого ответа.Как и централизованный алгоритм, который мы обсуждали ранее, распреде­ленное взаимное исключение гарантировано от тупиков и зависаний.

Число со­общений, приходящихся на один процесс, — 2(п-1), где п — общее число процес­сов в системе. Больше нет единой точки, сбой в которой мог бы погубить всюсистему.Однако, к сожалению, одна точка сбоя сменилась на п точек сбоев. Если ка­кой-либо из процессов «рухнет», он не сможет ответить на запрос. Это молчаниебудет воспринято (неправильно) как отказ в доступе и блокирует все последую­щие попытки всех процессов войти в какую-либо из критических областей.

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

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

Взаимное исключение303оказывается неспособным справиться с такой нагрузкой, маловероятно, что во­зымеет успех попытка их всех сделать то же самое параллельно.В этот алгоритм можно внести разнообразные дополнительные усовершенст­вования. Например, получение каждым из процессов разрешения на вход в кри­тическую область — это, по правде говоря, чересчур.

Ведь нам необходимо толь­ко предотвратить одновременный вход двух процессов в критическую область.Алгоритм можно модифицировать так, чтобы разрешить процессу вход в крити­ческую область после того, как он соберет разрешения простого большинства,а не всех остальных процессов. Разумеется, в этом случае, после того как процессдаст разрешение на вход в критическую область одному из процессов, он не смо­жет дать то же самое разрешение другому процессу до тех пор, пока первый непокинет критическую область.

Возможны также и другие улучшения, в частно­сти предложенные в [279], но они легко могут запутать алгоритм.Несмотря на все возможные улучшения, этот алгоритм остается более мед­ленным, более сложным, более затратным и менее устойчивым, чем исходныйцентрализованный алгоритм. Зачем тогда его вообще изучать? Для единствен­ной цели.

Мы показали, что распределенные алгоритмы как минимум возможны.Когда мы начинали рассмотрение, это не было очевидно. Кроме того, только об­ратив внимание на недостатки, мы можем подвигнуть будущих теоретиков наразработку алгоритмов, которые действительно можно будет использовать.

Характеристики

Список файлов книги