Лычев А.В. Распределенные автоматизированные системы

Подождите немного. Документ загружается.

Распределенные автоматизированные системы

160

текущем времени Т

, определения среднего времени задержки

передачи

ТТ

ПО

−

и исправления этим значением полученного

точного времени. Однако и здесь имеется некоторая погреш-

ность, обусловленная разным временем пересылки запросного и

ответного сообщений вследствие разной загрузки сети. Эту

погрешность учесть невозможно, так как невозможно с высокой

долей вероятности спрогнозировать текущую загрузку сети

ЭВМ;

2. Алгоритм Беркли. Периодически, не реже чем через

каждые

единиц времени, сервер единого времени опрашива-

ет системные часы каждой ЭВМ сети и предлагает им устано-

вить их системные часы на новое время. Проблемы алгоритма

те же, что и у алгоритма Кристиана, но вторая проблема ре-

шается сложнее и с бóльшими погрешностями.

Всем известно, что существует возможность синхрониза-

ции системных часов ЭВМ с помощью Интернета. Во всемирной

сети существует протокол сетевого времени NTP (Network Time

Protocol). Однако вследствие неустановленного времени за-

держки передачи сообщений о точном времени, с помощью этого

протокола можно обеспечить синхронизацию времени не точнее

пятидесяти миллисекунд, и то только на выделенных линиях

оптоволоконного качества. Такая точность, безусловно, более

чем достаточна для большинства прикладных программ реально-

го масштаба времени, но процессы, требующие более высокую

точность измерения времени, вынуждены пользоваться непо-

средственно данными Всемирной службы точного времени.

§ 2. Синхронизация процессов в распределенных системах

Для процессов, не критичных к использованию точного

времени, используются другие виды синхронизации, основным

из которых является синхронизация, называемая «логические

часы Лампорта». Любое пересылаемое сообщение содержит в

своем заголовке информацию о времени отправки по системным

часам ЭВМ-отправителя. Если при доставке сообщения систем-

ные часы ЭВМ-получателя показывают время более раннее, чем

время отправки, получатель быстро подводит свои часы таким

образом, чтобы они показывали время на единицу большее вре-

мени отправки.

С целью упорядочивания одновременно происходящих собы-

тий к значению времени справа через точку добавляется номер

процесса (например: 42.1). Причинно-следственная связь меж-

ду процессами может быть соблюдена с помощью так называемых

векторных отметок времени, когда к значению времени и номе-

ра процесса добавляется ещё и номер сообщения, вызвавшего

Распределенные автоматизированные системы

161

активность данного процесса (например: 42.1.6). Метка вре-

мени, таким образом, получает кортеж (вектор) параметров.

Большинство распределенных алгоритмов требуют, чтобы

один из процессов выполнял главенствующую роль над другими.

В разных источниках такой процесс называется координатором,

инициатором, диспетчером и так далее. В настоящем пособии

процесс, выполняющий в распределенной системе главенствую-

щую роль над другими, будем называть ведущим или пилотным

процессом. Процессы, подчиненные ведущему процессу, будем

называть ведомыми процессами. Для определения ведущего про-

цесса существуют два алгоритма, построенных на наличии уни-

кальных приоритетных номеров у всех процессов, функциони-

рующих в системе:

1. Мажоритарный алгоритм. Когда один из процессов за-

мечает, что ведущий процесс перестал отвечать на запросы,

он посылает всем процессам с бóльшими, чем у себя номерами,

сообщение «голосование». Если никто не отвечает, то про-

цесс, пославший данное сообщение, становится ведущим, о чем

уведомляет все остальные процессы. Если один из процессов с

бóльшим номером ответил, то процесс, пославший данное сооб-

щение, остается ведомым. В любой момент времени процесс мо-

жет получить сообщение «голосование» от другого процесса с

меньшим номером. При получении такого сообщения процесс да-

ет квитанцию о готовности стать ведущим и сам, в свою оче-

редь, организует отправку сообщения «голосование». ведущим

процессом в мажоритарном алгоритме всегда является самый

приоритетный процесс;

2. Кольцевой алгоритм. Этот алгоритм работает при на-

личии физического или логического упорядочивания процессов,

то есть когда каждый процесс имеет информацию о том, какой

процесс является его преемником. Когда один из процессов

замечает, что ведущий процесс перестал отвечать на запросы,

он посылает своему преемнику сообщение «голосование», со-

держащее свой уникальный в системе приоритетный номер. Про-

цесс, получивший сообщение «голосование», добавляет к со-

держащемуся там номеру свой приоритетный номер и посылает

сообщение дальше своему преемнику. Получение процессом со-

общения «голосование», содержащее его собственный приори-

тетный номер означает, что кольцо голосования замкнулось,

все активные процессы приняли участие в голосовании. При

этом процесс, инициировавший голосование, получает сообще-

ние «голосование», содержащее номера всех активных процес-

сов, принявших участие в голосовании.

Получив сообщение «голосование» с номерами всех актив-

ных процессов в системе, процесс, инициировавший голосова-

ние, формирует сообщение «ведущий», содержащее номера всех

активных процессов в системе, и вновь отправляет его по

Распределенные автоматизированные системы

162

кругу преемников. Процессы, принявшие сообщение «ведущий»,

получают информацию о ведущем процессе (процессе с наиболь-

шим приоритетным номером) и список всех активных функциони-

рующих в системе процессов.

§ 3. Взаимное исключение процессов

В распределенных системах существует опасность одно-

временного использования одних и тех же ресурсов различными

процессами. Для исключения такой возможности применяются

три алгоритма:

1. Централизованный алгоритм. Процесс, нуждающийся в

каком-либо ресурсе, запрашивает разрешение на доступ к это-

му ресурсу у ведущего процесса. Если ни один из процессов

не работает с данным ресурсом, ведущий процесс дает разре-

шение запрашивающему процессу на доступ к ресурсу. Если за-

прашиваемый ресурс занят, ведущий процесс организует оче-

редь запросов и предоставляет ресурс последовательно каждо-

му из запрашивающих процессов. Проблемы в централизованном

алгоритме возникают при отказе ведущего процесса. Для реше-

ния этой проблемы необходимо переопределение ведущего про-

цесса;

2. Распределенный алгоритм. Если процессу необходим

какой-либо ресурс, он создает сообщение, содержащее имя ре-

сурса, свой номер и значение текущего момента времени. За-

тем это сообщение рассылается всем активным в системе про-

цессам, в том числе и самому себе. Когда процесс получает

вышеуказанное сообщение, возможны три варианта действий:

а) Если процесс-получатель не работает с указанным ре-

сурсом и не собирается его занимать, он отсылает отправите-

лю квитанцию о приеме сообщения;

б) Если процесс-получатель работает с указанным ресур-

сом, он ничего не отвечает, а помещает запрос в очередь;

в) Если процесс-получатель собирается занять указанный

ресурс, то есть он также разослал всем активным в системе

процессам сообщение о намерении занять ресурс, но еще его

не занял, он сравнивает метку времени полученного сообщения

с меткой времени сообщения, которое он сам разослал. Если

полученное сообщение послано раньше, процесс получатель от-

сылает отправителю квитанцию о приеме сообщения и ничего не

делает. Если его собственное сообщение послано раньше, то

процесс-получатель ничего не отвечает, ставит запрос в оче-

редь и занимает нужный ему ресурс.

Проблемы в распределенном алгоритме возникают при от-

казе одного из процессов. Данная ситуация может быть вос-

принята неправильно другими процессами как отказ в доступе

к ресурсу (занятость ресурса);

Распределенные автоматизированные системы

163

3. Алгоритм маркерного кольца. Все активные процессы в

системе программно упорядочиваются и из них создается логи-

ческое кольцо. По кольцу от процесса к процессу запускается

маркерное сообщение. Процесс может занять какой-либо ре-

сурс, лишь получив маркерное сообщение. Отправить маркерное

сообщение дальше по кольцу процесс может лишь после освобо-

ждения ресурса. Для каждого ресурса существует свое маркер-

ное сообщение. Проблемы в алгоритме маркерного кольца воз-

никают при потерях маркера.

§ 4. Распределенные транзакции

Транзакция – это сложная многоступенчатая операция,

выполняющаяся как единый неделимый единовременный процесс.

Свойства транзакций:

1. Атомарность. Для окружающего мира транзакция неде-

лима, то есть она либо полностью выполняется, либо полно-

стью не выполняется, причем если она выполняется, то как

одна неделимая одновременная операция;

2. Непротиворечивость. Транзакция не нарушает инвари-

антов (ключевых свойств) системы;

3. Изолированность. Одновременно выполняющиеся тран-

закции не влияют друг на друга;

4. Долговечность. После завершения транзакции резуль-

таты её работы неизменны.

Виды транзакций:

1. Плоская транзакция – это транзакция, строго удовле-

творяющая четырем вышеизложенным свойствам транзакций;

2. Вложенная транзакция – это транзакция, состоящая из

дочерних транзакций, способных работать параллельно без

взаимных блокировок (у дочерних транзакций отсутствует

свойство долговечности);

3. Распределенная транзакция – это набор плоских тран-

закций, совместно выполняющих одну общую задачу.

При реализации транзакции на локальной ЭВМ, процесс,

её выполняющий, получает закрытое рабочее пространство опе-

ративной памяти, в котором производит все промежуточные

действия до тех пор, пока транзакция не выполнится или не

прервется.

При реализации распределенных транзакций на различных

ЭВМ сети, необходим алгоритм управления для сохранения

свойств транзакций. Для управления распределенными транзак-

циями служат три иерархических процесса:

1. Менеджер данных. Менеджер данных находится на верх-

нем уровне иерархии и осуществляет транзактнонезависимые

операции чтения и записи данных;

Распределенные автоматизированные системы

164

2. Планировщик. Планировщик определяет, в какой момент

времени и какой транзакции разрешается передать операцию

чтения или записи менеджеру данных;

3. Менеджер транзакций. Менеджер транзакций находится

на нижнем уровне иерархии и обрабатывает команды транзак-

ций, преобразуя их в запросы к планировщику.

Планировщик и менеджер данных размещаются на каждой из

ЭВМ распределенной системы и, работая совместно, обеспечи-

вают гарантии непротиворечивости локальных данных. Менеджер

транзакций размещается только на сервере транзакций.

Для обеспечения свойства изолированности транзакций

необходима синхронизация конфликтующих операций. Две опера-

ции конфликтуют, если они работают с одним и тем же элемен-

том данных, и хотя бы одна из них является операцией запи-

си. Синхронизация конфликтующих операций при выполнении

транзакций производится двумя методами:

1. Двухфазная блокировка. Когда процесс в ходе тран-

закции нуждается в чтении или записи элемента данных, он

делает запрос планировщику заблокировать для него этот эле-

мент данных. Когда необходимость в этом элементе данных ис-

чезает, процесс делает запрос планировщику снять блокиров-

ку. Задача планировщика состоит в том, чтобы устанавливать

и снимать блокировку, не допуская некорректного перемежения

операций, выполняемых различными транзакциями над одним и

тем же элементом данных. При двухфазной блокировке различа-

ют две фазы:

а) Фаза подъема, на которой планировщик устанавливает

все необходимые блокировки;

б) Фаза спада, на которой планировщик снимает все не-

обходимые блокировки.

При этом выполняются три правила:

а) Если запрашивается операция, конфликтующая с опера-

циями, уже получившими блокировку, то её выполнение откла-

дывается;

б) Если менеджер данных уведомил планировщик, что он

осуществляет операцию с элементом данных, планировщик не

снимет блокировку с этого элемента данных до окончания ра-

боты менеджера данных с этим элементом данных;

в) Если планировщик снял блокировку с данных по требо-

ванию какой-либо транзакции, он никогда больше не заблоки-

рует данные по требованию этой транзакции.

Варианты двухфазной блокировки:

а) Строгая двухфазная блокировка. В этом варианте бло-

кировки фаза спада не начинается до тех пор, пока транзак-

ция не завершится;

б) Централизованная двухфазная блокировка. В отличие

от классического варианта, в этом случае за установку и

Распределенные автоматизированные системы

165

снятие блокировок отвечает один централизованный процесс-

планировщик, называемый менеджер блокировок;

в) Первичная двухфазная блокировка. В этом варианте

блокировки с каждого элемента данных снимается копия, на

которую устанавливаются блокировки. В отличие от централи-

зованной двухфазной блокировки, первичная двухфазная блоки-

ровка может быть распределена по нескольким ЭВМ сети;

г) Распределенная двухфазная блокировка. Этот вариант

блокировки применяется, когда данные распределены по не-

скольким ЭВМ сети. При этом планировщики каждой ЭВМ сети

отвечают не только за установку и снятие блокировок, но и

за пересылку операций локальным менеджерам данных.

2. Упорядочивание по меткам времени. Упорядочивание по

меткам времени может быть двух видов:

а) Пессимистическое упорядочивание по меткам времени.

В момент начала каждой транзакции ей присваивается метка

времени. Каждая операция, являющаяся частью транзакции,

также получает метку времени, эквивалентную метке времени

транзакции, частью которой она является. Каждый элемент

данных получает метку времени записи и метку времени считы-

вания. Метка времени записи эквивалентна метке времени

транзакции, которая последней записывала этот элемент дан-

ных. Метка времени считывания эквивалентна метке времени

транзакции, которая последней считывала этот элемент дан-

ных. В случае конфликта двух операций выполняется операция

с меньшим значением метки времени, операция с бóльшим зна-

чением метки времени переводится в режим ожидания;

б) Оптимистическое упорядочивание по меткам времени.

Параллельно выполняемые транзакции не обращают никакого

внимания друг на друга. По окончании выполнения каждой

транзакции результаты её работы анализируются на достовер-

ность и либо принимаются, либо отбрасываются, причем в по-

следнем случае инициируется повторное выполнение транзак-

ции. Анализ результатов работы транзакции на достоверность

основан на проверке факта изменения элемента данных, с ко-

торым работает транзакция, другой транзакцией. Если в про-

цессе выполнения транзакции, элемент данных, с которым она

работает, был изменен другой транзакцией, результаты работы

обеих транзакций признаются недостоверными.

§ 5. Механизмы синхронизации процессов в ОС РВ QNX

Операционная система реального масштаба времени QNX

использует связь посредством сообщений как средство взаимо-

действия между любыми процессами, как локальными, так и

распределенными. Для синхронизации процессов в ОС РВ QNX

используются следующие механизмы:

Распределенные автоматизированные системы

166

1. Переменные синхронизации (мутексы). В каждый момент

времени переменной синхронизации может владеть только один

поток выполнения. Другие потоки, которые пытаются захватить

эту переменную, блокируются до момента её освобождения. По-

сле освобождения переменной синхронизации очередным потоком

выполнения переменную синхронизации захватывает поток с

наивысшим приоритетом из всех потоков, ожидающих возможно-

сти захватить эту переменную. В большинстве процессоров за-

хват переменной синхронизации не требует обращения к микро-

ядру, а выполняется аппаратно специальными командами про-

цессора (например, такие команды имеются в процессорах х86,

RISC и т.д.). Действие операционной системы при этом сво-

дится только к управлению приоритетами. Если поток выполне-

ния, который пытается захватить переменную синхронизации,

имеет более высокий приоритет, чем поток, непосредственно

владеющий этой переменной, то действующий приоритет текуще-

го владельца устанавливается равным приоритету блокирован-

ного потока, ожидающего эту переменную синхронизации. Такой

механизм обеспечивает минимальное время ожидания переменной

синхронизации и решает проблему инверсии приоритетов;

2. Условные переменные. Условная переменная использу-

ется для блокировки выполняемого потока выполнения по како-

му-либо условию. Физически условная переменная представляет

собой подпрограмму-функцию, ассоциированную с конкретным

потоком выполнения и реализующую проверку какого-либо логи-

ческого условия. В вызывающую программу условная переменная

может возвращать только два значения – TRUE и FALSE. Усло-

вие может быть сколь угодно сложным и не зависит от услов-

ной переменной. Пока условие является истинным, поток вы-

полнения, владеющий переменной синхронизации, блокирован.

Условная переменная всегда используется совместно с пере-

менной синхронизации. Разблокировать блокированный условной

переменной поток выполнения может другой активный поток,

изменив условие блокировки и сделав его ложным;

3. Барьеры. Барьер – это механизм синхронизации, по-

зволяющий скоординировать работу нескольких взаимодействую-

щих потоков выполнения таким образом, чтобы каждый из них

блокировался в заданной точке в ожидании остальных потоков,

прежде чем продолжить свою работу. После того, как заданное

количество потоков достигает установленного барьера, все

эти потоки разблокируются и продолжают свою работу;

4. Ждущие блокировки. Ждущая блокировка работает ана-

логично условной переменной, но не для одного потока выпол-

нения, а одновременно для нескольких потоков. При этом ис-

пользуется только одна переменная синхронизации, а условные

переменные создаются динамически для каждого потока выпол-

нения;

Распределенные автоматизированные системы

167

5. Блокировки по чтению-записи. Блокировка по чтению-

записи применяется при необходимости предоставить доступ к

данным по чтению всем потокам выполнения, которые его за-

прашивают, а по записи – только одному потоку. Этот меха-

низм синхронизации предоставляет доступ по чтению всем по-

токам выполнения, которые его запрашивают. Если поток за-

прашивает блокировку по записи, запрос отклоняется до тех

пор, пока все потоки, выполняющие чтение, не снимут свои

блокировки по чтению. Множество потоков выполнения, желаю-

щих произвести запись данных, помещаются в очередь в поряд-

ке своих приоритетов. Потоки выполняют запись после снятия

всех блокировок по чтению в порядке очереди. Читающие пото-

ки выполнения получают доступ к данным только после опусто-

шения очереди. Приоритеты читающих потоков не учитываются.

Реализация блокировок по чтению-записи происходит не в мик-

роядре, а посредством переменных синхронизации и условных

переменных, предоставляемых микроядром;

6. Семафоры. Семафор – это вариант условной переменной

с единственным условием: поток выполнения блокируется при

неположительном значении счетчика семафора. Изменить значе-

ние счетчика семафора может любой активный процесс. Семафо-

ры специально предназначены для применения в программах об-

работки асинхронных событий и, в отличие от условных пере-

менных, могут управляться обработчиками сигналов;

7. Синхронизация с помощью FIFO-планирования. Этот ме-

ханизм синхронизации применяется при недостатке ресурсов

процессоров для осуществления параллельной обработки пото-

ков выполнения;

8. Синхронизация с помощью обмена сообщениями. Это

единственный механизм синхронизации, способный работать в

сети (смотри: связь посредством сообщений). Он осуществля-

ется неявно с помощью блокировок;

9. Синхронизация с помощью атомарных операций. Этот

механизм синхронизации применяется при необходимости гаран-

тировать выполнение какой-либо операции, исключая возмож-

ность её вытеснения более приоритетным потоком.

Глава 5. Репликация в распределенных системах

§ 1. Понятие непротиворечивости

Цель репликации заключается в повышении надежности

системы и её производительности. В то же время возникнове-

ние любой копии какого-либо ресурса ставит проблему сохра-

нения непротиворечивости реплик. Под непротиворечивостью

реплики ресурса понимается сохранение актуальности копий

ресурса. Набор копий ресурса актуален, если операция чтения

Распределенные автоматизированные системы

168

данных дает одинаковые результаты для каждой из копий. Об-

новление данных должно распространяться на все копии до то-

го, как начнется следующая операция чтения данных, то есть

обновление данных должно являться транзакцией.

Как правило, в распределенных системах данные сущест-

вуют не автономно, а в составе объектов. Поэтому правильнее

говорить не о репликации данных, а о репликации объектов.

Репликация с целью увеличения производительности сис-

темы часто одновременно используется и в качестве способа

масштабирования. Это происходит за счет сокращения времени

доступа к реплике ресурса при её территориальном приближе-

нии к потребителю ресурса. Однако, с ростом сети и числа

реплик одного ресурса, увеличивается время на обновление

данных, вследствие чего общая производительность распреде-

ленной системы падает. Таким образом, при репликации необ-

ходим разумный компромисс между количеством реплик одного

ресурса и значением общей производительности распределенной

системы. Решение данной проблемы заключается в жертвовании

требованием об атомарности обновления данных, то есть не-

противоречивостью. Для этого производители сетевого про-

граммного обеспечения разрабатывают протоколы непротиворе-

чивости, под которыми понимают соглашения о том, какие пра-

вила должны выполнять процессы, чтобы хранилище данных ра-

ботало правильно. При этом внутри системы возможны отдель-

ные состояния нарушения непротиворечивости данных, которые

должны скрываться от клиентов. Существует два вида протоко-

лов непротиворечивости:

1. Протоколы непротиворечивости, ориентированные на

данные. Эта группа протоколов обеспечивает непротиворечивое

представление данных;

2. Протоколы непротиворечивости, ориентированные на

клиента. Эти протоколы допускают нарушения непротиворечиво-

сти данных, но обеспечивают сокрытие факта нарушений от

клиента.

Рассмотренные протоколы определяют одноименные виды

непротиворечивости.

§ 2. Непротиворечивость, ориентированная на данные

Непротиворечивость, ориентированная на данные, бывает

двух видов:

1. Непротиворечивость, не требующая операций синхрони-

зации. В свою очередь, этот вид непротиворечивости разбива-

ется на четыре подвида:

а) Строгая непротиворечивость. При этой непротиворечи-

вости всякое чтение элемента данных возвращает значение,

соответствующее результату последней записи этого элемента

Распределенные автоматизированные системы

169

данных. Когда хранилище данных строго непротиворечиво, все

операции записи мгновенно замечаются всеми процессами. Вы-

держивается абсолютный глобальный порядок во времени. Если

элемент данных изменяется, все последующие операции чтения

этого элемента данных возвращают новое значение. Строгая

непротиворечивость – это идеализированный вид непротиворе-

чивости, который в распределенной системе достигнуть очень

сложно, а чаще всего невозможно. Поэтому на практике в за-

висимости от конкретной ситуации применяют другие, менее

строгие виды непротиворечивости;

б) Последовательная непротиворечивость. Это менее

строгая непротиворечивость. Хранилище данных последователь-

но непротиворечиво, если результат любого действия над эле-

ментом данных такой же, как если бы операции чтения и запи-

си элемента данных выполнялись бы в некотором последова-

тельном порядке. При последовательной непротиворечивости

все процессы видят одно и то же чередование операций записи

элемента данных. Процесс видит операции записи всех процес-

сов, но только свои собственные операции чтения. Недостаток

последовательной непротиворечивости заключается в том, что

для всякого последовательно непротиворечивого хранилища

данных увеличение скорости чтения вызывает падение скорости

записи и наоборот;

в) Причинная непротиворечивость. Этот вид непротиворе-

чивости представляет собой ослабленный вариант последова-

тельной непротиворечивости, при котором проводится разделе-

ние между событиями, потенциально обладающими причинно-

следственной связью, и событиями, ею не обладающими. Чтение

связано с записью, предоставляющей данные для этого чтения,

причинно-следственной связью. Операции, не имеющие причин-

но-следственной связи, называются параллельными. Хранилище

данных поддерживает причинную непротиворечивость, если опе-

рации записи, потенциально связанные причинно-следственной

связью, наблюдаются всеми процессами в одинаковом порядке,

а параллельные операции записи могут наблюдаться в произ-

вольном порядке. Реализация причинной непротиворечивости

требует отслеживания, какие процессы какие операции записи

видели. Одним из способов такого отслеживания является ис-

пользование векторных меток времени для определения причин-

но-следственной связи;

г) Непротиворечивость FIFO. Данная непротиворечивость

подчиняется следующему условию: операции записи, осуществ-

ляемые единичным процессом, наблюдаются всеми остальными

процессами в том порядке, в котором они осуществляются, но

операции записи, осуществляемые различными процессами, мо-

гут наблюдаться всеми остальными процессами в разном поряд-

ке. Непротиворечивость FIFO предполагает, что все операции