В. Столлингс - Операционные системы (1114679), страница 137
Текст из файла (страница 137)
Для иллюстрации проблеи воспользуемся графиками процессов и событий (рис. 14.3 и 14,4). Гориэнтальными линиями на этих графиках представлены временные оси. Точка а оси соответствует событию (например„событию во внутреннем процессе, гправке или приему сообщения). Обведенный вокруг точки квадрат предгавляет состояние локального процесса в Фиксированный момент времени, эответствующий этой точке.
Стрелкой обозначается передача сообщения от диого процесса другому. Рие. 14 3. Примеры ояределения глобального состояния В нашем примере клиент банка имеет счет в двух его филиалах. Чтобы определить полную сумму, находящуюся на счету этого клиента, банк должен иметь сведения о количестве его денег в каждом из филиалов. Предположим, что запрос сделан ровно в 3:ОО.
В случае, показанном на рис. 14.3,а, общий счет окажется равным ИОО.ОО Однако возможна также ситуация, представленная на рис. 14.3,б, в котоРой во время запроса происходит перевод денег из филиала А в филиал В. В результате будет получен неправильный результат, равный $0.00. Эгу проблему можно Решить, проверяя во время запроса все сообщения о переводе денег. Нужно, чтобы в Филиале А хранились записи обо всех переводах из этого филиала, а также о том, кому эти переводы предназначены. Поэтому в "состояние" филиала А нужно включить как учет текущих счетов клиентов, так и записи о денежных переводах. Проверяя эти два пункта, служащий банка обнаружит денежный перевод, покинувший Филиал А и предназначенный для филиала В.
Так как эта сумма еще не пришла в Филиал В, она будет добавлена в общий счет. Любая сумма, которая была переведена и уже получена, учитывается только один раз.„она будет входить в текущий счет, содержащийся в Филиале-получателе. Глава 14. Управление распределенными процессами б~ Со~ласоегнное енобальное соетоннне Ве Рис. 14.4. Несогласованное глобальное состояние и согласованное глобальное состояние Такая стратегия не является полностью надежной. В примере, приведенном и рис. 14 З,в, часы в разных филиалах идут с некоторым относительным сдвиом, Проверка состояния счета клиента в филиале А в момент времени 3:ОО дает результат, равный 3100.00.
Однако впоследствии эта сумма переводится в фили1л В. В этот момент времени часы в филиале А показывают время 3:01, но в филиале В в этот же момент на часах — 2:59. Поэтому в запросе, производимом ~ 3:ОО„переводимая сумма учитывается дважды. Чтобы понять, с трудностью какого рода мы столкнулись, и сформулироить решение, определим некоторые понятия. Канал.
Если два процесса обмениваются сообщениями, между ними устанавливается канал. Канал можно представить как путь или способ, с помощью которого происходит передача сообщений. Для удобства каналы считаются однонаправленными. Таким образом, для обмена сообщениями между двумя процессами необходимы два канала, каждый из которых служит для передачи сообщений в одном направлении ° Состояние. Состояние процесса — это последовательность сообщений, отправленных и принятых по всем его каналам. ° Снимок.
Снимок фиксирует состояние процесса. В каждый снимок входят записи обо всех сообщениях, отправленных и полученных, начиная с того момента, когда был сделан предыдущий снимок. Глобальное состояние. Объединенное состояние всех процессов. Распределенный снимок. Множество снимков каждого процесса. Проблема состоит в том, что из-за задержки, необходимой для переда редачи сооб щений, невозможно определить истинное глобальное состояние расее щеделенной сис в одно мно.
темы. Можно попытаться определить глобальное состояние, объединив в о но жество снимки всех процессов. Например„в глобальном состоянии соответств , с тветствующем рис. 14.4,а, на момент выполнения снимков будет обнаружено что сооб одно щение передается по каналу <А,В>, одно — по каналу <А,С> и одно — по каналу <С,А>. Сообщения 2 и 4 будут представлены правильно, а сообщение 3 — нет. Распределен ный снимок покажет, что оно уже получено, но еще не отправлено.
Хотелось бы, чтобы распределенный снимок отображал глобальное состояние согласованно. Глобальное состояние будет согласованным если , е для каждого состояния процесса, в котором есть запись о получении сообщения, имеется соответствующая запись в состоянии процесса-отправителя. На рис. 14.4 б приведен пример такого состояния.
Несогласованное глобальное состояние возникает тогда, когда в процессе имеется запись о получении какого-то сообщения, а соответствующей записи в процессе, отправившем это сообщение, нет (рис. 14.4,а). Алгоритм распределенного снимка В [СН~~~Ч [СН~~1851 описан алгоритм распределенного снимка, который позволяет получить согласованное глобальное состояние. В этом алгоритме предполагается, что сообщения доставляются в том порядке, в котором они были отправлены, и что они не теряются. Надежный протокол передачи сообщений (например, ТСР) удовлетворяет этим требованиям.
В алгоритме используются специальные управляющие сообщения, которые называются маркерами (шаг(сег). Инициатором начала работы алгоритма выступает какой-то процесс, записывающий свое состояние и отправляющий маркер по всем своим исходящим каналам. В промежутке между моментом записи состояния и моментом отправки маркера никакие другие сообщения не отправляются. После этого каждый процесс р, первый раз получивший маркер (скажем, от процесса д), выполняет такие действия. 1.
Записывает свое состояние Я . 2. Д . Делает запись о том, что входной канал из о в р является пустым. 3. ассылает маркер всем соседним процессам, пользуясь для этого своими 3. Рас выходными каналами. Эти действия должны выполняться атомарно — т.е. до выполнения шага 3 нельзя отправлять или принимать никакие сообщения. П роцесс р, который уже записал свое состояние, получив по входному каналу маркер от какого-то другого процесса (скажем, от процесса г), выполняет следующее. 1. Записыв аписывает состояние канала из г в р как последовательность сообщений, полученных от процесса г за интервал времени от момента записи своего локального состояния 8е до момента получения маркера от процесса г.
Выполнение алгоритма процессом прекращается тогда, когда этот процесс получит маркеры по всем своим входным каналам. Гаева 14. Управление распределенными процессами В (АХВВ901 по поводу этого алгоритма сделаны такие замечания. Любой процесс может начать выполнение алгоритма, отправив маркер. Фактически решение о записи глобального состояния могут независимо принять несколько узлов, и это никак не повлияет на правильность выполнения алгоритма. 2. Если все сообщения (включая маркеры) передаются в течение конечного времени, время выполнения алгоритма тоже будет конечным.
3. Алгоритм является распределенным: каждый процесс сам отвечает за запись своего собственного состояния и состояния всех своих входных каналов. 4. После того как будут записаны все состояния (после завершения работы алгоритма во всех процессах), из них можно будет собрать глобальное состояние. Для этого нужно, чтобы каждый процесс отправил данные о своем состоянии по всем выходным каналам, а каждый процесс, получивший данные о состоянии других процессов, переслал их по всем своим выходным каналам. Можно предложить и другой метод сборки, в котором процесс- инициатор запрашивает в установленном порядке состояния всех других процессов, составляя из них глобальное состояние.
5. Алгоритм не влияет на другие распределенные алгоритмы, в которых принимают участие вовлеченные в него процессы, и не подвержен влиянию этих алгоритмов. В качестве примера применения описанного выше алгоритма (пример взят з (ВЕХ901) рассмотрим множество процессов, изображенных на рис. 14.о. Кажый процесс представлен кружком, а каждый однонаправленный канал — сопиняющей кружки линией со стрелкой„которая указывает направление.
Предоложим, что алгоритм снимка начинает работу; пусть при этом по каждому из ыходных каналов каждого процесса пересылается по девять сообщений. Решене о записи глобального состояния принимается независимо процессами 1 и 4. процесс 1 к этому времени отправил шесть сообщений, а процесс 4 — три сооб1ения. По завершении работы алгоритма собираются снимки всех процессов, в езультате чего получается глобальное состояние, показанное на рис.
14,6. Перед ем как записать свое состояние, процесс 2 отправил по каждому из своих выодных каналов по четыре сообщения процессам 3 и 4. До записи своего состояпя этот процесс успел получить от процесса 1 четыре сообщения, а сообщения 5 6 попали в запись о состоянии каналов. Читатель может убедиться в согласоанности моментального снимка: для каждого отправленного сообщения имеется ибо запись о его получении, либо запись о том, что оно передается по каналу. Процесс 1 Выходные каналы Канал 2: посланы для 1, 2, 3, 4, 5, 6 Канал 3: посланы для 1, 2. 3.
4, 5, 6 Входные каналы Процесс 4 Выходные каналы Канал 3: посланы 1, 2, 3 Входные каналы Канал 2: получены 1, 2; остались 3,-4". Рис. 14.6. Пример снимка Приведенный алгоритм получения распределенного снимка является мощ ным и гибким инструментом. Его можно использовать для адаптации любогс централизованного алгоритма к условиям распределенной среды,так как в осно ве любого централизованного алгоритма лежат знания о глобальном состоянии.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
