Алгоритмы работы распределенных систем

свою работу последним
Все остальные в это время простаивают
Балансировка нагрузки

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

задач на узле (workload)‏
Логична, когда процессоры не перегружены
Средняя загруженность процессора

(load average)‏
Количество процессов, которые были готовы к выполнению или выполнялись в течение интервала времени (1минута, 5 минут, 15 минут)‏
Чем больше процессов выполняется, тем меньше времени уделяется каждому процессу
Эффективная загруженность процессора
Отношение средней загруженности процессора к производительности процессора
Более быстрый процессор выполняет одну и ту же работу быстрее, чем более медленный

программ
Динамические
Распределение выполняется в процессе работы программ

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

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

накапливается дисбаланс нагрузки
Не требует специальной поддержки программ и операционной системы
Используется

в системах пакетного режима для Beowulf кластеров

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

задача
Задачи раздаются рабочим процессорам по мере выполнения ими предыдущих заданий
Более

быстрый процессор выполнит больше работы
Требует специальной поддержки программ

выполняет балансировку по централизованной схеме
Более эффективна, чем централизованная схема –

меньше узких мест

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

время и мало обмениваются между собой

принимает большие значения при увеличении использования ресурса
Процессы перемещаются (запускаются)

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

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

бы одного из ресурсов
Если использование ресурса превышает максимально допустимое значение, то функция должна сильно возрастать

имеет свою количественную характеристику
Процессор – эффективная загруженность
Память – объем свободной

памяти
Сеть – объем передаваемой информации
Безразмерность обеспечивается введением отношения текущего значения ресурса к его максимально-допустимому значению
Память – объем памяти машины
Процессор – максимальная эффективная загрузка

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

значение функции уменьшается

среди равноправных – координатора (инициатора)‏
Это позволяет динамически реализовать централизованные схемы
Применение
Протокол

NetBIOS - координатор выбирается для службы имен
Сеть Token Ring – одна машина выбирается координатором для обмена маркером

процесс имеет уникальный номер
Выбрать процесс с наибольшим номером и сообщить

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

и отправляет сообщение E о начале выборов всем узлам (с

большим номером)‏
Если процесс i не получил ни от кого ответа A в течение интервала времени T, то он назначает себя координатором и отправляет всем узлам (с меньшим номером) сообщение С – выбран новый координатор
Если процесс j получил сообщение о начале выборов E (от процесса с меньшим номером) то но отвечает ему сообщением A и запускает алгоритм для себя
Если процесс i получил ответ A от узла j, то значит, что узел j имеет больший номер и может стать координатором. Если в течение интервала времени T не было получено сообщения С, алгоритм повторяется через интервал времени T1.
При появлении нового процесса он запускает алгоритм для себя
Процесс с максимальным номером становится координатором

4 приняли сообщение узла 2, сказали ему остановиться и запускают

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

E со своим номером узлу с номером i+1 и если

нет подтверждения, то узлу с номером i+2 и т.д.
Если узел j не встретил в E сообщении своего номера, то он добавляет туда свой номер и отправляет его дальше
Если узел j встретил в E сообщении свой номер, то значит E сообщение обошло кольцо и максимальный номер в нем – номер координатора. Узел j меняет тип сообщения на C и отправляет его дальше
После того, как C сообщение обошло все узлы, оно уничтожается и все узлы знают номер координатора

для многих проблем

события счетчик увеличивается на 1
Если одно событие произошло раньше другого,

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

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

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

файловой системы)‏
Его может изменять только один процесс
Необходимо обеспечить блокировку, которая

бы давала возможность защитить доступ к ресурсу
Типы алгоритмов блокировки
Централизованный (CLM)‏
С передачей маркера (TLM)‏
Распределенный менеджер блокировок (DLM)‏

выполняются через координатора
Для доступа к ресурсу процессы посылают запрос координатору
Если

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

плане производительности

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

его удерживают, или он потерян?
Как добавить новых участников?
Не поддерживается порядок

захвата блокировки
При большом количестве узлов получаются большие задержки

сообщений
REQUEST
QUEUED
GRANT
Центральным узлом для блокировки является узел, захвативший блокировку
Узлы могут быть

в трех состояниях
Удержание блокировки
Ожидания
Свободное состояние

отправляет сообщение REQUEST всем остальным n-1 узлам (multicast)‏
Все узлы отвечают

i-му n-1 сообщением, которые могут быть следующего типа
GRANT – разрешение захвата - ответ узла, который не удерживает блокировку
QUEUED - информация, что запрос поставлен в очередь на узле, который захватил блокировку
После получения n-1 сообщения узел i выполняет следующие действия
Если все сообщения были типа GRANT, то узел i считается владельцем блокировки
Если одно сообщение типа QUEUED, то узел ждет сообщения типа GRANT

REQUEST с узла j (или других узлов) до того, как

получены все сообщения от других узлов
Каждое сообщение содержит Лампортовскую метку времени
Если метка полученного сообщения меньше, чем локальная, то узлу j отправляется сообщение GRANTED
Иначе запрос ставится в очередь и отправляется сообщение QUEUED

захватил блокировку и поддерживает очередь запросов на захват
Если получено сообщение

REQUEST от i-го узла, то
Установить в очередь запрос от узла i
Отправить узлу i сообщение QUEUED

есть запросы на захват, он отправляет сообщение GRANTED первому в

очереди и удаляет его из очереди

блокировку
Количество участников уменьшается на 1
Вышел из строя узел, который

удерживает блокировку
Этот узел отключается от операций с общим ресурсом (fence)‏
Восстанавливается состояние общего ресурса из журнала
Количество участников уменьшается на 1
Все очереди уничтожаются
Запускается новый процесс захвата блокировки

состоянии
Пример
Эмуляция общей памяти на распределенной системе
Работа с общими дисковыми

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

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

данных пакетами (блоками)‏

строго в той последовательности, в которой поступил запрос (как в

случае машины с общей памятью)‏
Реализуется по централизованной схеме
Не эффективна

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

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

освобождения
После захвата (GET) можно эксклюзивно обращаться к ресурсу
После освобождения (PUT)

ресурс может захватить другой процесс
Два подхода
Агрессивный подход – PUT синхронизирует данные
Ленивый подход - GET синхронизирует данные

области используется своя модель консистентности
Консистентность структур данных
С каждой структурой данных

связывается своя модель консистентности

файловой системы
Checkpoint распределенной программы

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

начинается запись общего состояния
После записи общего состояния начинается запись всех сообщений от всех процессов, пока не будет получено сообщение о завершении записи состояния
Продолжить работу