Лекция 12 (26.11.20) - chrislvt/OS GitHub Wiki

Взаимоисключение в распределенных системах (продолжение)

(7:38)

Централизованный алгоритм

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

Распределенный алгоритм

Второй тип алгоритма это распределенный алгоритм.

Алгоритм формулируется следующим образом:

  1. Когда процесс хочет войти в критическую секцию, он формирует сообщение.
    • В этом сообщении он указывает:
      • идентификатор нужной ему критической секции;
      • свой номер (идентификатор);
      • время формирования сообщения по своим локальным часам.
    • Предполагается, что передача сообщения надёжна: получение каждого сообщения сопровождает подтверждение.
    • Протокол - соглашение о том, какие действия выполняют процессы при передаче и получении сообщения. Надёжный протокол всегда предполагает подтверждение получения сообщения.
  2. Это сообщение, сформированное процессом, процесс рассылает всем взаимодействующим процессам (то есть n - 1 сообщение)
  3. Получив такое сообщение, процесс проверяет, в какой ситуации он сам находится по отношению к критической секции.
    • Возможны 3 ситуации:
      1. получивший сообщение процесс не собирается входить в данную критическую секцию (и не находится в ней). В этом случае процесс посылает сообщение-ответ с разрешением войти в критический участок;
      2. процесс, получивший сообщение, находится в данной критической секции. В этом случае никакое сообщение не посылается;
      3. Процесс, получивший сообщение, сам формировал сообщение запрос на вход в данную критическую секцию, но еще не успел это сделать.
        • (на доске: хочет войти в ту же критическую секцию). Тогда процесс проверяет временную метку создания своего сообщения, сравнивает ее с временной меткой полученного сообщения. Если его сообщение было сформировано раньше, то никакого сообщения-ответа процесс не посылает. Если в результате таких рассылок процесс получает n - 1 сообщение подтверждения входа в критический участок, то процесс может войти в критический участок. Если он не получает хотя бы одно сообщение, то в критический участок процесс войти не может.

В этом случае процесс должен послать n - 1 сообщение-запрос и в ответ получить n - 1 сообщение-разрешение на вход, иначе войти не может.

Алгоритм Токен Ринг (Token Ring)

(20:36)

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

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

Сравнение приведенных алгоритмов

Самый надежный алгоритм: централизованный алгоритм. За счет возможности выбора нового координатора.

В случае распреденного алгоритма: Если какой-то из процессов перестал существовать, то процесс, разославший n - 1 сообщение-запрос, не сможет получить n - 1 сообщение-ответ: потеря работоспособности по конкретной критической секции.

В случае Токен Ринг: если какой-то процесс перестает существовать, то цепь разрывается. Чтобы ее восстановить, надо предпринять соответствующие действия. Если циркулирование токена по каким-то причинам прервано, то есть только одно средство определения: таймаут.

Неделимые транзакции

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

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

Транзакцией называется последовательность операций над одним или несколькими объектами базы данных, такими как файлы, записи и тому подобное, которая переводит систему из одного целостного состояния в другое целостное состояние.

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

Такое свойство транзакции называется "все или ничего".

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

  • begin_transaction
  • end_transaction
  • abort_transaction (прерывание означает необходимость восстановления исходных значений)
  • read_transaction, write transaction (позволяют читать или писать данные)

Примечание: begin и end определяют границы транзакции.

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

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

Механизмы реализации транзакций

Существует два основных подхода к реализации механизма транзакций:

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

  2. Список намерений. В данном подходе модифицируются сами файлы/записи/объекты, но перед любым изменением выполняется запись в специальный файл, который называется журнал регистрации. В этом журнале отмечается, какая транзакция делает изменения, какой файл/запись изменяется и в этот журнал записывается старое и новое значения изменяемого файла записи. Только после того, как транзакция успешно выполнена, указаные изменения сохраняются в исходном файле. Если транзакция фиксируется (выполняется успешно), то об этом делается запись в журнале регистрации, но записи не удаляются. Если транзакция прерывается, то журнал регистрации используется для приведения файлов (записей) в исходное состояние - такое действие называется откатом.

Протокол фиксации транзакций

В распределённых системах фиксация транзакции может потребовать взаимодействия нескольких процессов, которые выполняются на разных машинах. В этом случае каждая такая отдельная машина хранит какие-то переменные/файлы базы данных. Для достижения неделимости транзакции в распределенных системах, используется специальный протокол - протокол двухфазной фиксации транзакций.
Это не единственный протокол для фиксации транзакции, но он считается наиболее надежным. Суть протокола: для обеспечения выполнения транзакции в распределенной системе один из взаимодействующих процессов выполняет функции координатора.

            координатор                    подчиненный процесс
------------------------------------      ----------------------
|      Записать "приготивиться"     |     |                    |
| Послать сообщения "приготовиться" | ->  | Записать "готов"   |   1 фаза
|                                   | <-  | Послать "готов"    |
|   Собрать сообщения-ответы        |     |                    |
-------------------------------------     ----------------------
|   Запись в журнале                |     |                    |   
|   Послать сообщение "завершить"   | ->  |Записать "завершил" |   2 фаза
|   Собрать ответы                  | <-  | Послать "завершил" |   
-------------------------------------     --------------------

alt text

Протокол

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

    • координатор должен записать в журнал регистрации приглашение для других процессов участвующих в транзакции: например, "приготовиться".
    • после того, как эта запись сделана в журнале регистрации, выполняется рассылка сообщений процессам, участвующим в транзакции.
    • подчинённый процесс, получив сообщение "приготовится", в журнал регистрации выполняет запись о готовности завершить транзакцию, например, "готов".
    • после успешной записи в журнал регистрации, подчинённый процесс может послать сообщение координатору.

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

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

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

Временные метки

В явном виде в распределенном организме присутствуют временные отметки. В системе важно, чтобы соблюдалось отношение "случилось до / случилось после".

(59:30)

Алгоритм Лампорта

Алгоритм Лампорта применяется для синхронизации временных ответок (для соблюдения отношения "случилось до / случилось после") (см. оффлайн лекции).

Алгоритм Лампорта - не единственное решение, которое позволяет согласовывать действия процессов, обеспечивать отношение "случилось до / случилось после".

Векторные часы

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

(61:20)

В отличие от временных меток Лампорта, векторные часы содержат вектор отметок.

Каждый раз, когда какой-то процесс выполняет какие-то действия (когда в процессе происходит какое-то событие) в векторе отметок фиксируется отметка.

alt text image

64:55

Взаимодействуют три процесса: A, B, C. В начальный момент времени вектор обнулен. В некоторый момент в каком-то процессе происходит событие: отправка или прием сообщения (собственно другие события, которые происходят на локальных машинах, нас не интересуют). Скажем, процесс в какой-то момент времени сформировал сообщение и сделал в своем векторе отметку и проставил значение 1.

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

Получение процессом сообщения так же является событием. Вектор, фиксированный процессом B - B:1. После этого процесс B формирует соообщение процессу A c отметкой B:2. Процесс А формирует ответное сообщение процессу B c отметкой А:2. (см ее комментарии к рисунку на записи, вроде в личный кабинет выложит (см. мыльный рисунок выше))

Важно различать причину и следствие. Пунктиром выделены действия, которые являются причиной. За пунктиром - следствия.

Каждый раз, когда процесс получает сообщение, он увеличивает собственную логическую переменную - собственные логические часы в векторе - +1. Каждое событие инкрементирует собственное значение счетчика событий процесса.

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

Алгоритм Лампорта можно считать отправной точкой развития этой темы (взаимодействие процессов в распределенной системе).

77:50

Вызов удаленных процедур (RPC)

Наличие такого высокоуровневого средства взаимодействия как транзакции, это самый нижний уровень взаимодействия процессов в распределенных системах.

RPC - remote procedure call

RPC является важнейшим механизмом для приложений типа клиент-сервер. Он был разработан Sun Microsystems. Он представляет собой набор библиотечных функций, например:

  • RPC -> NIS (Network Information System)
  • RPC -> NFS (Network File System)

Основы

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

RPC внешне напоминает именно такие действия. Но вызываемая функция выполняется (может выполняться) на совершенно другой машине. Это взаимодействие выполняется по модели клиент-сервер. Процесс, который вызывает функцию RPC является клиентским. Процесс, который выполняет функцию на этой же или на другой машине, является серверным.

image

86:38

RPC. Этапы работы.

Клиентский процесс

  • [прикладная программа]
  • интерфейс (определяется с помощью языка IDL)
  • (клиентский stab)
  • [библиотека RTL RPC]
  • (сокет BSD; клиент)

Серверный процесс

  • (сокет BSD; сервер)
  • [библиотека RTL RPC]
  • (серверный stab)
  • интерфейс (определяется с помощью языка IDL)
  • [прикладная программа сервера]

Формируется ответ и посылается ответ обратно по той же схеме (снизу - вверх)

Прикладная программа заинтересована в выполнении каких-то действий на удаленной машине. Прикладная программа, выполняемая клиентским процессом, выполняет вызов удаленной процедуры. При этом для этой программы это просто вызов на локальной машине. В системе существует интерфейс, то есть вызов, выполняемый приложением, преобразуется в вызов так называемого клиентского stab'a (фиктивный модуль клиента; клиентская заглушка).

Более подробно о работе с ее слов:

В результате вызова начинает выполняться этот stab. Происходит вызов функции стандартной библиотеки. Взаимодействие выполняется через сокеты.

Механизм сокетов был предложен и реализован в ОС Unix BSD

В результате вызова библиотечной функции, происходит обращение к местному сокету (сокету BSD).

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

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

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

На серверной стороне через сокет пакет поступает на машину, на которой выполняется процесс-сервер. Вызывается библиотека и её функции. На стороне сервера имеется серверный stab.

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

С RPC связано очень много понятий. Это низкоуровневый механизм взаимодействия в распределенных системах. RPC достигает прозрачности следующим образом: если вызываемая процедура/функция действительно является удаленной, в библиотеку помещается вместо локальной функции, другая версия этой функции, которая называется клиентским stab'ом (вызов подменяется другим вызовом).

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

Иллюстрация выше (86:38) - очень общая.

Процесс клиента

101:32

Вызов клиентского стаба, действия:

  • Подготовка буфера сообщения
  • Упорядочивание параметров в буфере
  • Добавление в собщение полей заголовков
  • Системный вызов, в результате которого происходит переход в режим ядра и выполняется переключение контекста
  • В ядре для того, чтобы обработать сообщение, оно должно быть скопировано в буфер ядра (В режиме пользователя свой буфер, в режиме ядра - свой)
  • Определение адреса назначения
  • Адрес помещается в заголовок сообщения
  • Инициализируется сетевой интерфейс
  • Включается таймер

Первые 4 действия выполняет стаб клиента

Сообщение исходное, которое для процесса-клиента не является сообщением. Он вызывает функцию, затем уже начинает работать система и соответствующая библиотека и формирует пакет.

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

(записывает снизу вверх)

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

Действия:

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

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

Этот стаб берет на себя задачу на дальнейшее продвижение запроса и его преобразования.

И на стороне сервера выполняется необходимая работа (Выполнение требуемой работы).

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

Динамическое связывание (Binding)

117:37

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

  1. маршалинг
  2. сериализация

Маршалинг - это перекодировка и упаковка данных в формат сообщения, принятый в системе.

Сериализация - преобразование сообщения в последовательность байтов.

На стороне сервера выполняются обратные действия:

  1. десериализация
  2. демаршалинг

Связывание может быть статическим и динамическим. Динамическое называется binding.

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

Binder - сервер имен и каталогов.

IPC - Inter Process Communication

Средства взаимодействия параллельных процессов. Мы рассматриваем средства IPC System V.

К ним принято относить:

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