Распределенная вычислительная система (РВС) представляет собой
совокупность автономных вычислительных узлов, которые не имеют общей
разделяемой глобальной памяти и взаимодействуют между собой
исключительно при помощи посылки друг другу сообщений через
коммуникационную среду.
В РВС не существует общесистемных часов и любой узел имеет только
частичную информацию о состоянии системы. У процесса на узлах существует
необходимость разделять общие аппаратные и программные ресурсы,
взаимодействуя таким образом, чтобы обеспечивать параллельную и
независимую друг от друга работу. Доступ к разделяемым ресурсам должен
быть синхронизированным для того, чтобы в данный момент времени только
один процесс мог использовать эти ресурсы.
Каждый процесс имеет один или несколько сегментов кода, называемых
критической секцией (КС), в которых процесс может использовать
разделяемые ресурсы. Проблема координации выполнения КС каждым процессом
решается с помощью предоставления взаимно-исключительного (монопольного)
доступа к КС во времени. Любой процесс циклически выполняет код в
последовательности критических и некритических сегментов, каждый из
которых имеет конечное время выполнения. Каждый процесс должен
запрашивать разрешение на вход в свою КС и должен освобождать КС после
того, как закончит выполнение кода в ней.
Любой алгоритм работы взаимных исключений должен организовывать работу в
соответствии со следующими требованиями:
Не больше чем один процесс может выполнять КС в данный момент времени.
Если ни один процесс не находиться в своей КС, то любой процесс,
запрашивающий доступ в КС, должен получить его за конечное время.
Если несколько процессов одновременно запрашивают доступ в свой КС, то
выбор не должен продолжаться бесконечно долго.
Запрашивающий процесс не должен быть прерван другим в течение некоторого
конечного промежутка времени.
Другими словами, алгоритм должен обеспечивать взаимно исключительный
доступ к ресурсам, не вызывать тупиковые ситуации, не вызывать зависания
и быть "беспристрастным" в определении порядка предоставления доступа.
При реализации алгоритмов взаимных исключений может быть использовано
два подхода.
Централизованный. В системе имеется узел, выполняющий функции
центрального координатора. Процессы запрашивают доступ на вход в КС
только у координатора и входят в нее только после получения
подтверждения от координатора. Координатор несет всю ответственность за
сбор информации о системе и за предоставление доступа к разделяемым
ресурсам.
Распределенный. Процесс принятия решение распределен по всей системе.
Решение проблемы взаимных исключений намного усложняется из-за сложности
получения полной информации о состоянии системы. Причиной этого является
отсутствие общей разделяемой памяти, общих физических часов и
непредсказуемость задержки сообщений.
В данной работе рассматриваются только распределенные алгоритмы.
В свою очередь, распределенные алгоритмы по принципу разработки могут
быть поделены на две группы:
На базе токена (маркера). Право входа в КС передается между не
координированными, но взаимодействующими узлами в виде специального
сообщения, называемого "token"(токен или маркер) или "privilege"
(привилегия).
На базе заявки или разрешения. Запрашивающий процесс ждет получения
разрешения от множества процессов в системе. Когда процесс получает
разрешение от достаточного количества узлов, он входит в КС.
Алгоритмы, представленные в работе, предполагают следующие допущения и
условия для распределенной среды:
Всем узлам в системе присвоены уникальные номера от 1 до N.
На каждом узле существует только один запрашивающий процесс.
Взаимное исключение реализовано на уровне узлов.
Процессы соревнуются за доступ к одному ресурсу.
В любой момент времени каждый процесс инициирует не больше одного
запроса для КС.
Все узлы в системе полностью соединены между собой.
Принимаются также следующие допущения относительно коммуникационной
сети, связывающей узлы:
Доставка сообщений гарантирована. Сообщения не теряются, не изменяются и
правильно доставляются адресату в течение конечного отрезка времени.
Сохранение порядка. Сообщения доставляются в том же порядке, в котором
они были отправлены.
Задержки передачи сообщений являются конечными, но непредсказуемыми.
Сообщения достигают адресата за конечное время, но время прибытия
непостоянно.
Топология сети известна. Узлы знают схему физического размещения узлов в
системе, а также знают путь друг к другу.
Алгоритм Naimi-Trehel
Данный алгоритм является распределенным и работающим на базе токена.
Как было упомянуто в разделе "Общие положения" на каждом узле работает,
только один процесс, использующий общие ресурсы, поэтому будем
отождествлять процесс с узлом.
В данном алгоритме используется динамическая структура в виде дерева с
корнем (rooted tree), в которой запрашивающие процессы логически
упорядочены по их требованиям токена. Как только запрос на токен от узла
i проходит по пути от узла i до корневого узла, узел i становится новым
родителем для каждого узла по пути, исключая самого себя. Таким образом,
узел i становится новым корнем дерева.
Необходимо обратить внимание на тот факт, что коневой узел не
обязательно является владельцем токена и наоборот. Если узел коневой, то
это значит, что именно он получит токен следующим. Эти положения станут
более понятны далее при рассмотрении примера.
У узлов и у токена нет необходимости вести очередь ожидающих запросов.
Эта очередь неявно поддерживается посредством состояния каждого узла в
системе. Каждый узел хранит две переменные целого типа, LAST и NEXT.
LAST идентифицирует последний узел, от которого был получен запрос, и
соседний узел по пути к корню, которому данный узел пошлет запрашивающее
сообщение при следующей попытке войти в КС. NEXT идентифицирует узел,
которому будет передан токен после того, как данный узел покинет КС.
Когда узел i хочет войти в КС, и LASTi<>i, (т.е. узел i не является
держателем токена), он посылает запрос к узлу LASTi, присваивает LASTi
:= i и ждет прибытия токена. Если узел владеет токеном или токен прибыл
от какого-либо узла, то он сразу входит в КС.
Когда запрос от узла i прибывает к непривилегированному узлу j по пути к
держателю токена (привилегированному узлу), узел j перенаправляет запрос
от узла i к узлу LASTj. Узел j присваивает LASTj:=i. Когда запрос от
узла i прибывает на привилегированный узел, например k, и k является
корневым узлом дерева (LASTk=k), и он находится в КС, то узел k
присваивает NEXTk:=i и LASTk:=i. Если k является корневым узлом и держит
незанятый токен, то он посылает токен к узлу i и присваивает LASTk:=i. В
случае если узел k не корневой узел, то он пересылает запрос от узла i к
узлу LASTk. Последнее происходит, когда узел k получает запрос от
другого узла до запроса от узла i и, таким образом, он становится частью
пути от узла i к корневому узлу.
Когда привилегированный узел k, держащий токен, покидает КС, он
посылает токен к узлу NEXTk и присваивает NEXTk:=0. Если нет ожидающих
запросов NEXTk=0, узел оставляет свободный токен у себя. У узла,
держащего не занятый токен, нет необходимости посылать запрос для
повторного входа в КС.
Очередь ожидающих запросов может быть получена при помощи обхода пути по
состояниям NEXT каждого узла. Началом очереди является привилегированный
узел. Токен передвигается последовательно, обходя этот путь по дереву.
Алгоритм не требует номеров последовательности для упорядочения событий.
Передаваемые сообщение очень малы, т.к. передаваемые переменные очень
просты. Это уменьшает накладные расходы в сети.
Среднее число передаваемых сообщений для входа в КС составляет log(N).
Как было упомянуто выше, алгоритм предполагает существование полностью
надежной коммуникационной сети. Задержки передачи конечны и сообщения
могут доставляться не в том же порядке, в котором они были отправлены.
Алгоритм включает в себя механизм обнаружения сбоев в узле и механизм
восстановления системы при сбоях в узлах. Этот механизм основан на
использовании двух таймаутов. Один из них (Twait) определяет вероятность
сбоя, а другой (Telec) контролирует широковещательную посылку вопросов и
прием ответов. Каждый узел может находиться в одном из пяти состояний:
waiting (ожидание)
consulting (консультация)
query (запрос)
candidate (кандидат)
observer (наблюдатель)
Рис. 1. Диаграмма состояний узла.
Когда узел i посылает запрашивающее сообщение, он входит в состояние
waiting. Если он не получает токен в течение времени Twait, то это
свидетельствует о сбое. Если произошел сбой, узел i "консультируется"
(consulting), содержит ли какой-либо узел k записи о запросах узла i
(NEXTk=i). После того, как выйдет время Telec, узел i запрашивает (query
) другие узлы обнаружить, присутствует ли токен в системе. Когда выйдет
время Telec, т.е. ответы не получены, узел i становится кандидатом
(candidate) для регенерации токена, посылает широковещательные сообщение
о выборах и активизирует еще один Telec. Если за период Telec появляется
несколько кандидатов, то выбирается узел с наименьшим номером. Все
остальные узлы в системе становятся наблюдателями (observer) и ожидают
сообщения CANDIDATE_ELECTED от выбранного узла для того, чтобы
продолжить функционирование. Выбранный узел владеет токеном и становится
корнем преобразованного дерева. Все узлы устанавливают свои переменные
LAST равными номеру выбранного узла, а переменные NEXT в 0.
Во время задержек на фазах consulting и query может прийти токен или
ответ от другого узла, и запрашивающий узел опять войдет в состояние
waiting. Алгоритм предполагает, что если узел недоступен, то он остается
недоступным в течение всего процесса выборов. Алгоритм не учитывает
случаи, когда недоступный узел восстанавливается и включается в систему.
Этот узел может содержать старый токен. В алгоритме также не учитываются
отказы коммуникационной сети.
Для более ясного понимания принципа работы алгоритма рассмотрим пример.
Будем рассматривать изменения только в логической структуре. Физичиские
межсоединения узлов в данном случае интереса не представляют.
В распределенной системе имеется 5 узлов. На каждом узле запущен один
процесс, использующий общие ресурсы, т.е. N=5 . Пусть только что
произошли выборы кандидата и им стал узел 5. Тогда будет иметь место
следующая картина.
Шаг 1. Выборы кандидата.
Рис. 2. Состояние процессов после выборов кандидата
LAST, NEXT – значения соответствующих переменных
State: - значение состояния процесса.
T- обозначение владельца токена
Стрелочками указывается узел, номер которого содержится в LAST.
Шаг 4. Прием токена на узле 1. Узел 3 хочет войти в КС.
4.1. 1 принимает токен. Уничтожает Twait. Входит в КС.
4.2. LAST3<>3. 3 посылает REQUEST к 5. LAST3:=3. Запускает Twait.
Рис 5. Узел 3 запросил токен у узла LAST3=5
Шаг 5. Обработка запроса на узле 5.
5.1. 5 перенаправляет запрос к LAST5=1. LAST5:=3
Рис 6. Обработка запроса на узле 5
Шаг 6. Обработка запроса на узле 1.
6.1. Принимает запрос REQUEST3.
6.2. Т.к. 1 находится в КС, то NEXT1:=3, LAST1:=3.
Рис 7. Обработка запроса на узле 1
Нетрудно заметить, что на этом шаге корневым является узел 3, а
владельцем токена – узел 1. Но узел 3 получит токен следующим, т.к.
NEXT1=3 (см. следующий шаг).
Шаг 7. узел 1 посылает токен узлу 3
7.1. 1 выходит из КС. NEXT1<>0, посылает токен NEXT1=3.
7.2. 3 принимает токен. Уничтожает Twait. Входит в КС.
Рис. 8. Узел 3 становить корневым узлом
Алгоритм Raynal
Michel Raynal предложил использование простых чисел для описания
глобального состояния системы. Простые числа используются для
упорядочивания событий в системе. Целью Raynal'a было не получение
эффективного алгоритма с точки зрения количества сообщений, а
демонстрация того, что простые числа и их свойства могут быть полезным
средством в разработке распределенных алгоритмов.
Инициализации узлов. Каждый узел i имеет атрибут Ai. Эти атрибуты
являются натуральными целыми числами отличными от единицы и попарно
простыми. Каждый узел поддерживает переменную Xi инициализированную
значением Ai (Xi:=Ai), за исключением одного узла, значение Xi которого
равно 1. Этот узел имеет первым право войти в КС. Узлы также знают, что
Q - это общее произведение всех простых чисел Ai (Q:=A0*A1*…*AN-1).
Вход в КС. Когда узел i решает войти в КС, он посылает сообщение-запрос
в форме REQUEST(i) всем остальным N-1 узлам и ждет получения ответного
сообщения от всех узлов. Ответное сообщение имеет форму REPLY(j, Xj).
После получения всех ответов узел i вычисляет величину T, равную
произведению значения Xi и всех полученных значений Xj
(T:=X0*X1*…*XN-1). Если T=Q/Ai (т.е. получены ответы ото всех узлов), то
узел i имеет право войти в КС. В противном случае он выжидает время и,
затем, повторно посылает сообщение-запрос всем остальным узлам.
Выход и КС. Когда узел i выходит из КС, он обновляет свою переменную Xi,
присваивая значение Xi:= Xi*Ai/Aj, где j:=(i+1)mod N. j циклически
принимает значения от 0 до N-1, т.е. право войти в КС циркулирует по
логическому кольцу из узлов.
Нетрудно заметить, что, на самом деле, топология сети передачи права
определяется алгоритмом выбора j в выражении Xi:= Xi*Ai/Aj, но в
оригинальной версии Raynal использовал именно кольцо, поэтому в
объяснении используется эта топология.
Узел обновляет свою переменную Xi только после того, как он выполнил все
действия в КС. Хитрость заключается в том, что узел i после изменения Xi
теряет право войти в КС и оно передается следующему узлу в кольце. Нужно
отметить, что "передача прав" происходит исключительно на уровне логики.
Никакие дополнительные сообщения или токен при этом не пересылаются.
Рассмотри пример.
Пусть N=4, т.е. в РВС имеется 4 узла.
Рис. 9. Начальное состояние.
Пунктирной линией показано направление, в котором циркулирует право
войти в КС.
Шаг 1.
Право войти в КС имеет узел 0, т.к. только для него выполняется условие
T=Q/Ai:
T0:=1*5*7*11;
Q/A0:=3*5*7*11/3=5*7*11
T1:=1*5*7*11;
Q/A1:=3*5*7*11/5=3*7*11
T2:=1*5*7*11;
Q/A2:=3*5*7*11/7=3*5*11
T3:=1*5*7*11;
Q/A3:=3*5*7*11/11=3*5*7
Пусть узел 0 запросил КС, вошел КС и вышел из КС. Тогда.
j:=(0+1)mod 4:=1
X0:=X0*A0/A1:= 1*3/5=3/5.
Право переходит к узлу 1, а узел 0 теряет право на вход. Т.е. если
сейчас узел 0 запросит доступ в КС, он не получит права, т.к. для него
не выполнится условие T=Q/Ai
Шаг 2.
Право войти в КС имеет узел 1, т.к. только для него выполняется условие
T=Q/Ai:
T0:=3/5*5*7*11:=3*7*11;
Q/A0:=5*7*11;
T1:=3*7*11;
Q/A1:=3*7*11;
T2:=3*7*11;
Q/A2:=3*5*11;
T3:=3*7*11;
Q/A3:=3*5*7;
Пусть узел 2 запросил КС, вошел КС и вышел из КС. Тогда.
j:=(1+1)mod 4:=2
X1:=X1*A1/A2:= 5*5/7
Право переходит к узлу 2.
Шаг 3.
Право войти в КС имеет узел 2, т.к. только для него выполняется условие
T=Q/Ai:
T0:=3/5*5*5/7*7*11:=3*5*11;
Q/A0:=5*7*11;
T1:=3*5*11;
Q/A1:=3*7*11;
T2:=3*5*11;
Q/A2:=3*5*11;
T3:=3*5*11;
Q/A3:=3*5*7;
Пусть узел 2 запросил КС, вошел КС и вышел из КС. Тогда.
j:=(2+1)mod 4:=3
X2:=X2*A1/A3:= 7*7/11.
Право переходит к узлу 3.
И т.д.
Алгоритм может вызывать тупики. В том случае, если следующий узел в
логическом кольце не хочет входить в КС, он никогда не обновит свою
переменную Xi и, значит, никогда не передаст полномочия на вход другому
узлу.
Алгоритм предполагает существование полностью надежной коммуникационной
сети. Задержки передачи не предсказуемы, но конечны и соблюдения порядка
следования сообщений не требуется. Количество сообщений для входа в КС
имеет верхнюю границу 2(N-1)2.
Существует модификация алгоритма, в которой решена проблема тупиковых
ситуация и уменьшено количество пересылаемых сообщений для входа в КС.
Во время инициализации каждый узел знает значения всех Xi. Узел с Xi=1
имеет право на вход в КС первым, так же как и в оригинальном алгоритме.
Узлам не нужно посылать запрашивающее сообщение. Они знают значения
каждого Xi и ждут момента, когда привилегированный узел (владеющий
правом на вход в КС выйдет из КС и обновит свое значение Xi. Разрешение
на вход в КС ото всех остальных узлов является неявным, за исключением
разрешения от привилегированного узла. Каждый узел поддерживает
локальную переменную для определения того, находится ли он в состоянии
запроса КС. Если узел i не находиться в состоянии запроса КС и является
следующим узлом в кольце для получения разрешения, то он должен вести
себя так, как будто он выходит из КС. Узел обновляет свою переменную Xi
и, тем самым, передает право другому узлу. Это исключает тупики. После
обновления он посылает сообщение в форме INFORM(i, Xi) всем остальным
N-1 узлам. Узел k получив сообщение, вычисляет T и проверят равно ли оно
Q/Ai. Если равно и узел находится в состоянии запроса КС, он входит в
КС. Если он не находится в состоянии запроса, но является следующим в
кольце, то он ведет себя как будто он только что вышел из КС. Общее
количество сообщений для входа в КС в худшем случае равно (N-1)2, когда
следующий ждущий входа в КС является самым удаленным от текущего
владельца права на вход.
