Э. Таненбаум, М. ван Стеен - Распределённые системы (принципы и парадигмы) (1162619), страница 79
Текст из файла (страница 79)
И наконец, подобно питанию шпинатом и изучению латыни в средней школе, некоторые вещи выглядят очень хорошо, но только до тех пор, пока остаются теорией.5.5.3. Алгоритм маркерного кольцаАбсолютно иной подход к реализации взаимных исключений в распределенныхсистемах предлагает алгоритм маркерного кольца {Token Ring). Пусть мы имееммагистральную сеть (например, Ethernet), но без внутреннего упорядочения процессов (рис. 15.5, а). Программно создается логическое кольцо, в котором каждому процессу назначается положение в кольце, как показано на рис. 5.15, б.
Положение в кольце может быть назначено по порядку следования сетевых адресовили как-то иначе. Неважно, как именно задана упорядоченность. Главное — какдать процессу знать, кто в кольце является следующим после него.Рис. 5.15. Беспорядочная группа процессов в сети (а).Логическое кольцо, созданное программно (б)304Глава 5. СинхронизацияПри инициализации кольца процесс О получает маркер, или токен {token).Маркер циркулирует по кольцу. Он передается от процесса k процессу k+ \ (этомодуль размера кольца) сквозными сообщениями.
Когда процесс получает маркер от своего соседа, он проверяет, не нужно ли ему войти в критическую область. Если это так, он входит в критическую область, выполняет там всю необходимую работу и покидает область. После выхода он передает маркер дальше.Входить в другую критическую область, используя тот же самый маркер, запрещено.Если процесс, получив от соседа маркер, не заинтересован во входе в критическую область, он просто передает этот маркер дальше.
Соответственно, если ниодин из процессов не находится в критических областях, маркер просто циркулирует по кольцу с максимально возможной скоростью.Легко видеть, что этот алгоритм корректен. Только один процесс в любоймомент времени обладает маркером, а значит, только один процесс может находиться в критической области. Поскольку маркер перемещается от процессак процессу в общеизвестном порядке, зависания не происходит. Когда процессрешает войти в критическую область, в худшем случае ему придется ждать, покавсе остальные процессы последовательно не войдут в критическую область и невыйдут из нее.Обычно этот алгоритм также имеет проблемы.
Если маркер однажды потеряется, он должен быть восстановлен. На самом деле, понять, что он пропал, довольно сложно, поскольку срок между последовательными появлениями маркера в сети не ограничен. Тот факт, что маркера не было видно в течение часа,вовсе не означает, что он потерян, кто-нибудь просто может его использовать.Алгоритм также сталкивается с проблемами при сбоях процессов, однакосправиться с этим проще, чем в других случаях. Если мы потребуем от процесса,получающего маркер, подтверждать получение, неработающий процесс будет обнаружен при первой же попытке соседа передать ему маркер.
В этот момент неработающий процесс можно удалить из группы, и хранитель маркера сможетперебросить маркер через его «голову» следующему члену кольца или, при необходимости следующему за ним. Разумеется, это требует поддержания текущейконфигурации кольца.5.5.4. Сравнение трех алгоритмовМы сделаем краткое сравнение трех алгоритмов взаимных исключений, поскольку оно поучительно. В табл. 5.1 мы перечислили алгоритмы и три их ключевыхсвойства: число сообщений, необходимое процессу для того, чтобы войти в критическую область или выйти из нее, возможная задержка перед входом (предполагается, что сообщения передаются по сети последовательно) и некоторые проблемы, связанные с описываемым алгоритмом.Централизованный алгоритм наиболее прост и наиболее эффективен.
На то,чтобы войти в критическую область, ему достаточно всего трех сообщений — запрос, разрешение на вход и сообщение о выходе. Распределенному алгоритму(мы предполагаем, что используются только сквозные коммуникации) требуется5.6. Распределенные транзакции305для запроса п- 1 сообщений, по одному на каждый процесс, и дополнительно п- iсообщений на разрешение, всего 2(п -1).
В алгоритме маркерного кольца числосообщений различно. Если каждый из процессов будет постоянно требовать входа в критическую область, каждая передача маркера станет результатом выходаиз критической области одного из процессов и в среднем на вход в критическуюобласть понадобится одно сообщение.
В другом крайнем случае маркер можетциркулировать по кольцу часами и им никто и не заинтересуется. В этом случаечисло сообщений на вход в критическую область одного процесса не ограничено.Таблица 5 . 1 . Сравнение трех алгоритмов взаимных исключенийАлгоритмЧисло сообщенийна вход-выходЗадержка передвходом в числесообщенийЦентрализованный32Крах координатораРаспределенный2(п-1)2(п~1)Сбой в одномиз процессовМаркерного кольцаО т 1 д о сюОтОдоп-1Потеря маркера, сбойв одном из процессовВозможные проблемыЗадержка с момента, когда процессу понадобилось войти в критическую область, до момента входа для этих трех алгоритмов также различна. Если критические области малы и используются редко, основным фактором задержки являетсямеханизм входа в критическую область.
Если критические области и используются постоянно, основным фактором задержки является ожидание своего хода.В таблице иллюстрируется первый случай. В случае централизованного алгоритма, для того чтобы войти в критическую область, требуется всего два сообщения.В случае распределенного алгоритма требуется 2(п - 1) сообщений, с учетом того, что они посылаются одно за другим. Для маркерного кольца время варьируется от О (маркер у процесса, входящего в критическую область) до w - 1 (маркербыл только что передан дальше по кольцу).И, наконец, все три алгоритма тяжело реагируют на сбои.
Чтобы сбой не привел к полному краху системы, приходится предпринимать специальные меры идополнительно усложнять алгоритм. Забавно, но распределенные алгоритмы более чувствительны к сбоям, чем централизованный. В защищенных от сбоя системах неприменим ни один из них, но если сбои нечасты, они будут работать.5.6.
Распределенные транзакцииКонцепция транзакций тесно связана с концепцией взаимных исключений. Алгоритмы взаимного исключения обеспечивают одновременный доступ не более чемодного процесса к совместно используемым ресурсам, таким как файл, принтери т. п. Транзакции, в общем, также защищают общие ресурсы от одновременногодоступа нескольких параллельных процессов. Однако транзакции могут и многоедругое. В частности, они превращают процессы доступа и модификации множе-306Глава 5.
Синхронизацияства элементов данных в одну атомарную операцию. Если процесс во время транзакции решает остановиться на полпути и повернуть назад, все данные восстанавливаются с теми значениями и в том состоянии, в котором они были до начала транзакции. В этом разделе мы поближе ознакомимся с понятием транзакции,и в частности сосредоточимся на возможностях транзакций по синхронизациинескольких процессов при защите совместно используемых данных.5 . 6 .
1 . Модель транзакцийБазовая модель транзакций пришла к нам из делового мира. Допустим, некой международной корпорации потребовалась партия каких-то штуковин. Они обращаются к потенциальному поставидику, ООО «Штуковины», хорошо известномуво всем мире качеством своих штуковин, с заказом на 100 000 10-сантиметровыхпурпурных штуковин с поставкой в июне.
ООО «Штуковины» предлагает100 000 4-дюймовых розовых штуковин с поставкой в декабре. Некая международная корпорация согласна с ценой, но не любит розовый цвет, хочет получитзаказ в июле и настаивает на 10-сантиметровых штуковинах для своих зарубежных заказчиков. ООО «Штуковины» отвечают предложением 3 15/16-дюймовыхлавандовых штуковин в октябре. После дальнейших переговоров они сходятся,наконец, на 3 959/1024-дюймовых фиолетовых штуковинах, которые будут поставлены к 15 августа.До этого самого момента обе стороны имели полную возможность прекратитьобсуждение, после чего мир вернулся бы к тому же состоянию, в котором он пребывал до начала переговоров. Однако после того, как обе компании подписаликонтракт, они связали себя обязательством выполнить сделку.
Таким образом,пока обе стороны шли к этому Рубикону, любая из них могла дать отбой, и ничего бы не произошло, но в момент появления подписей они перешли ту черту, изза которой нет возврата. После этого транзакция должна быть выполнена.Компьютерная модель выглядит очень похоже. Один процесс объявляет, чтохочет начать транзакцию с одним или несколькими другими процессами. Послеэтого они могут согласовывать различные условия, создавать и удалять сущности, выполнять операции. Затем инициатор объявляет, что он предлагает всемостальным подтвердить, что работа сделана. Если все это подтверждают, результаты утверждаются и становятся постоянными. Если один или несколько процессов отказываются (или до соглашения в них возникают сбои), ситуация возвращается к тому состоянию, которое имело место до начала транзакции, со всемивытекающими отсюда последствиями для файлов, баз данных и т.
д., все изменения в которых волшебным образом исчезают. Такое свойство «все или ничего»сильно упрощает работу программистам.Использование транзакций в компьютерных системах берет начало в шестидесятых годах. До этого дисков и сетевых баз данных не существовало, все данные хранились на магнитных лентах. Представьте себе супермаркет с автоматизированной системой инвентаризации. Каждый день после закрытия компьютерначинал работу с двумя магнитными лентами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
