Источник: Операционные системы распределенных вычислительных систем (распределенные ОС)
© Крюков Виктор Алексеевич. Зав. отделом ИПМ РАН, д.ф.-м.н.

Достоинства распределенных систем

Распределенная система - совокупность независимых компьютеров, которая представляется пользователю единым компьютером. Примеры: сеть рабочих станций (выбор процессора для выполнения программы, единая файловая система), роботизированный завод (роботы связаны с разными компьютерами, но действуют как внешние устройства единого компьютера, банк со множеством филиалов, система резервирования авиабилетов.

Почему создаются распределенные системы? В чем их преимущества перед централизованными ЭВМ?

1-ая причина - экономическая. Закон Гроша (Herb Grosh, 25 лет назад)- быстродействие процессора пропорциональна квадрату его стоимости. С появлением микропроцессоров закон перестал действовать - за двойную цену можно получить тот же процессор с несколько большей частотой.

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

3-я причина - естественная распределенность (банк, поддержка совместной работы группы пользователей ).

4-ая причина - надежность (выход из строя нескольких узлов незначительно снизит производительность).

5-я причина - наращиваемость производительности. В будущем главной причиной будет наличие огромного количества персональных компьютеров и необходимость совместной работы без ощущения неудобства от географического и физического распределения людей, данных и машин.

Почему нужно объединять PC в сети?

  1. Необходимость разделять данные.
  2. Преимущество разделения дорогих периферийных устройств, уникальных информационных и программных ресурсов.
  3. Достижение развитых коммуникаций между людьми. Электронная почта во многих случаях удобнее писем, телефонов и факсов.
  4. Гибкость использования различных ЭВМ, распределение нагрузки.
  5. Упрощение постепенной модернизации посредством замены компъютеров.

Недостатки распределенных систем:

  1. Проблемы ПО (приложения, языки, ОС).
  2. Проблемы коммуникационной сети (потери информации, перегрузка,развитие и замена).
  3. Секретность.

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

Обычно децентрализованные алгоритмы имеют следующие свойства:

  1. Относящаяся к делу информация распределена среди ЭВМ.
  2. Процессы принимают решение на основе только локальной информации.
  3. Не должно быть единственной критической точки, выход из строя которой приводил бы к краху алгоритма.
  4. Не существует общих часов или другого источника точного глобального времени.

Первые три пункта все говорят о недопустимости сбора всей информации для принятия решения в одно место. Обеспечение синхронизации без централизации требует подходов, отличных от используемых в традиционных ОС. Последний пункт также очень важен - в распределенных системах достигнуть согласия относительно времени совсем непросто. Важность наличия единого времени можно оценить на примере программы make в ОС UNIX. Главные теоретические проблемы - отсутствие глобальных часов и невозможность зафиксировать глобальное состояние (для анализа ситуации - обнаружения дедлоков, для организации промежуточного запоминания).

Синхронизация времени

Аппаратные часы (скорее таймер - счетчик временных сигналов и регистр с начальным значением счетчика) основаны на кварцевом генераторе и могут в разных ЭВМ различаться по частоте.

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

Для синхронизации логических часов Lamport определил отношение "произошло до". Выражение a->b читается как "a произошло до b" и означает, что все процессы согласны, что сначала произошло событие "a", а затем "b". Это отношение может в двух случаях быть очевидным:

  1. Если оба события произошли в одном процессе.
  2. Если событие a есть операция SEND в одном процессе, а событие b - прием этого сообщения другим процессом.

Отношение -> является транзитивным.

Если два события x и y случились в различных процессах, которые не обмениваются сообщениями, то отношения x->y и y->x являются неверными, а эти события называют одновременными.

Введем логическое время С таким образом, что если a->b, то C(a) < C(b)

Алгоритм:

  1. Часы Ci увеличивают свое значение с каждым событием в процессе Pi: Ci=Ci+d (d > 0, обычно равно 1)
  2. Если событие a есть посылка сообщения m процессом Pi, тогда в это сообщение вписывается временная метка tm=Ci(a). В момент получения этого сообщения процессом Pj его время корректируется следующим образом: Cj = max(Cj,tm+d)

Физические часы.
После изобретения в 17 веке механических часов время измерялось астрономически. Интервал между двумя последовательными достижениями солнцем наивысшей точки на небе называется солнечным днем. Солнечная секунда равняется 1/86400(24*3600) части солнечного дня.

В 1940-х годах было установлено, что период вращения земли не постоянен - земля замедляет вращение из-за приливов и атмосферы. Геологи считают, что 300 миллионов лет назад в году было 400 дней. Происходят и изменения длительности дня по другим причинам. Поэтому стали вычислять за длительный период среднюю солнечную секунду.

С изобретением в 1948 году атомных часов появилась возможность точно измерять время независимо от колебаний солнечного дня. В настоящее время 50 лабораторий в разных точках земли имеют часы, базирующиеся на частоте излучения Цезия-133. Среднее значение является международным атомным временем (TAI), исчисляемым с 1 июля 1958 года.

Отставание TAI от солнечного времени компенсируется становится добавлением секунды тогда, когда разница больше 800 мксек. Это скорректированное время, называеемое UTC (Universal Coordinated Time), заменило прежний стандарт (Среднее время по Гринвичу - астрономическое время). При объявлении о добавлении секунды к UTC электрические компании меняют частоту с 60 Hz на 61 Hz (c 50 на 51) на период времени в 60 (50) секунд. Для обеспечения точного времени сигналы WWV передаются коротковолновым передатчиком (Fort Collins, Colorado) в начале каждой секунды UTC. Есть и другие службы времени.

Алгоритмы синхронизации времени.
Две проблемы - часы не должны ходить назад (надо ускорять или замедлять их для проведения коррекции) и ненулевое время прохождения сообщения о времени (можно многократно замерять время прохождения и брать среднее).


Выбор координатора

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

Алгоритм "задиры"
Если процесс обнаружит, что координатор очень долго не отвечает, то инициирует выборы. Процесс P проводит выборы следующим образом:

  1. P посылает сообщение "ВЫБОРЫ" всем процессам с большими чем у него номерами.
  2. Если нет ни одного ответа, то P считается победителем и становится координатором.
  3. Если один из процессов с большим номером ответит, то он берет на себя проведение выборов. Участие процесса P в выборах заканчивается.

В любой момент процесс может получить сообщение "ВЫБОРЫ" от одного из коллег с меньшим номером. В этом случае он посылает ответ "OK", чтобы сообщить, что он жив и берет проведение выборов на себя, а затем начинает выборы (если к этому моменту он уже их не вел). Следовательно, все процессы прекратят выборы, кроме одного - нового координатора. Он извещает всех о своей победе и вступлении в должность сообщением "КООРДИНАТОР".

Если процесс выключился из работы, а затем захотел восстановить свое участие, то он проводит выборы (отсюда и название алгоритма).

Круговой алгоритм.
Алгоритм основан на использовании кольца (физического или логического), но без маркера. Каждый процесс знает следующего за ним в круговом списке. Когда процесс обнаруживает отсутствие координатора, он посылает следующему за ним процессу сообщение "ВЫБОРЫ" со своим номером. Если следующий процесс не отвечает, то сообщение посылается процессу, следующему за ним, и т.д., пока не найдется работающий процесс. Каждый работающий процесс добавляет в список работающих свой номер и переправляет сообщение дальше по кругу. Когда процесс обнаружит в списке свой собственный номер (круг пройден), он меняет тип сообщения на "КООРДИНАТОР" и оно проходит по кругу, извещая всех о списке работающих и координаторе (процессе с наибольшим номером в списке). После прохождения круга сообщение удаляется.


Взаимное исключение

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

Недостатки алгоритма - обычные недостатки централизованного алгоритма (крах координатора или его перегрузка сообщениями).

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

Проблемы:

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

Алгоритм древовидный маркерный (Raymond)
Все процессы представлены в виде сбалансированного двоичного дерева. Каждый процесс имеет очередь запросов от себя и соседних процессов (1-го, 2-х или 3-х) и указатель в направлении владельца маркера.

Вход в критическую секцию:
Если есть маркер, то процесс выполняет КС.
Если нет маркера, то процесс:

  1. помещает свой запрос в очередь запросов
  2. посылает сообщение "ЗАПРОС" в направлении владельца маркера и ждет сообщений.

Поведение процесса при приеме сообщений:
Процесс, не находящийся внутри КС должен реагировать на сообщения двух видов -"МАРКЕР" и "ЗАПРОС".

А) Пришло сообщение "МАРКЕР"

  • М1. Взять 1-ый запрос из очереди и послать маркер его автору (концептуально, возможно себе);
  • М2. Поменять значение указателя в сторону маркера;
  • М3. Исключить запрос из очереди;
  • М4. Если в очереди остались запросы, то послать сообщение "ЗАПРОС" в сторону маркера.

Б) Пришло сообщение "ЗАПРОС".

  1. Поместить запрос в очередь
  2. Если нет маркера, то послать сообщение "ЗАПРОС" в сторону маркера, иначе (если есть маркер) - перейти на пункт М1.

Выход из критической секции.
Если очередь запросов пуста, то при выходе ничего не делается, иначе - перейти к пункту М1.

Децентрализованный алгоритм на основе временных меток.
Алгоритм носит имя Ricart-Agrawala и является улучшением алгоритма, который предлжил Lamport.

Требуется глобальное упорядочение всех событий в системе по времени.

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

Источник: Операционные системы распределенных вычислительных систем (распределенные ОС)
© Крюков Виктор Алексеевич. Зав. отделом ИПМ РАН, д.ф.-м.н.