Синхронизация в распределенных системах Выполнила: Студентка ТИ-41м Склярова Мария

Введение Параллельное решение некоторой задачи на нескольких процессорах требует наличие между последними определенного взаимодействия. Две фундаментальные проблемы параллельных вычислений: возникновение тупиков; недетерминированность параллельных вычислений.

ЗАДАЧА ДЕЙКСТРЫ «Обедающие философы» ( о модели параллельных процессов ) дворецкий философы

Задача Дейкстры. Детали -Детали задачи: -сев за стол очередной философ берет 2 вилки – свою и любую свободную и насыпает спагетти -одновременно 5 человек подошли к столу -Состояние модели: «Тупик» или «Клинч» -Необходимы изменения в правилах для избегания данного состояния

ВАРИАНТЫ РЕШЕНИЯ ПРОБЛЕМЫ: дворецкий должен пропускать к столу не более 4 человек одновременно – исключение состояния тупик если все вилки заняты и никто не ест, все кладут вилки и через некоторое время повторяют попытку (возможно состояние «тупика»); если все вилки заняты и никто не ест, один из философов кладет свою вилку -возникает вопрос какой из философоф должен положить вилку; -передача маркера. Задача Дейкстры. Правила

КОРРЕКТНАЯ РАБОТА ПАРАЛЛЕЛЬНЫХ ПРОГРАММ: - организация правильного взаимодействия последовательных процессов; - обеспечение синхронизации между последовательными процессами. Недооценка роли синхронизации взаимодействующих процессов является одной из основных причин появления трудно уловимых логических ошибок. РАЗДЕЛЯЕМЫЕ РЕСУРСЫ

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

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

Алгоритм синхронизации логических часов (алгоритм Лампорта) a ® b a ® b и b ® c a ® c " a случилось до b" и означает, что все процессы в системе считают, что сначала произошло событие a, а потом - событие b cвойство транзитивности: Механизма ведения времени a Т(а) а ® b Т(а) < Т(b) Т(а)- время с которым согласны все процессы в системе

Алгоритм синхронизации логических часов (алгоритм Лампорта) А B C D

Алгоритм синхронизации логических часов(алгоритм Лампорта) Часы Тi увеличивают свое значение с каждым событием в процессе Pi: Тi=Тi+d (d > 0;1) Если событие a - посылка сообщения m процессом Pi, тогда в это сообщение вписывается временная метка tm=Тi(a). В момент получения этого сообщения процессом Pj его время корректируется следующим образом: Тj = max(Тj,tm+d) А B C D

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

Алгоритмы голосования Выбор координатора Алгоритм «задиры» Круговой алгоритм выборы

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

Критический интервал – последовательность действий, выполнение которых должно выглядеть со стороны как одна непрерывная операция. Защита критического интервала от одновременного вхождения в него 2-ух последовательных процессов циклических процесса P1 и P2 2. Внутри КИ Р1 и Р2 находятся ограниченное время Критический интервал

Алгоритмы взаимного исключения Централизованный алгоритм Запрос критическая секция i Разрешение

Распределенный алгоритм Процесс Аi критическая зона N, Ai, T(a) Процесс Aj: 1.Если получатель не находится и не собирается входить в критическую секцию в данный момент, то он отсылает назад процессу-отправителю сообщение с разрешением. 2.Если получатель уже находится в критической секции, то он не отправляет никакого ответа, а ставит запрос в очередь. 3.Если получатель хочет войти в критическую секцию, но еще не сделал этого, то он сравнивает временную отметку поступившего сообщения со значением времени, которое содержится в его собственном сообщении, разосланном всем другим процессам. Если время в поступившем к нему сообщении меньше, то он посылает сообщение-разрешение, в обратном случае он не посылает ничего и ставит поступившее сообщение-запрос в очередь.

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

Алгоритм Token Ring Каждому процессу назначается положение в кольце При инициализации кольца процесс 1 получает маркер, или токен Токен передается от процесса k процессу k + 1 сквозными сообщениями Входить в другую критическую область, используя один и тот же маркер, запрещено

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

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

Неделимые транзакции В распределенных системах используется специальный протокол - проток двухфазной фиксации транзакций.

Спасибо за внимание!