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

План

Балансировка нагрузки
Выбор координатора
Модели консистентности
Создание общего состояния
Распределенные блокировки

Балансировка нагрузки

Дисбаланс уменьшает эффективность вычислений
Самый медленный процессор параллельной схемы заканчивает свою

Характеристики загруженности процессоров

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

Методы балансировки нагрузки

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

Алгоритмы статической балансировки нагрузки

Круговой алгоритм (round robin)
Задачи запускаются по очереди

Эффективность статического распределения

Эффективно при малом времени работы программ
При большом времени накапливается

Методы динамической балансировки нагрузки

Централизованная схема
Децентрализованная схема
Балансировка на основе миграции процессов
Требуют специальных

Централизованная схема

Один процессор – главный
Остальные – рабочие
На главном поддерживается очередь задача
Задачи

Децентрализованная схема

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

Балансировка на основании миграции процессов

Процессы во время выполнения мигрируют между процессорами

Оптимизация использования ресурсов

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

Целевая функция

Должна включать все количественные характеристики использования всех ресурсов
Характеристики использования ресурсов

Безразмерные характеристики использования ресурсов

Ресурсы – память, процессор, сеть, диск
Каждый ресурс имеет

Вид целевой функции

F – цена возможного состояния
Степенная функция – очень быстро

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

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

Во многих случаях возникает задача выбора одной главной машины среди

Условия

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

Алгоритм задиры (bully algorithm) 1982

Процесс i обнаружил пропажу координатора и

Пример

Узел 2 обнаружил потерю координатора
Отправляет сообщение узлам 3,4,5
Узлы 3 и 4

Кольцевой алгоритм (1977)‏

Узел i обнаружил потерю координатора, он отправляет сообщение E

Пример кольцевого алгоритма

Количество операций

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

Лампортовские метки – определение раньше-позже для определенной последовательности событий
Достаточно для

Метки Лампорта

Поддерживается счетчик событий
В начальном состоянии от равен 1
После каждого события

Пример

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

Доступ к общим ресурсам в сети требует синхронизации

Взаимоисключающий доступ

По аналогии с общей памятью
Есть некоторый общий ресурс (блок файловой

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

Один из процессов выбирается координатором
Все доступы к общему ресурсу выполняются

Пример работы централизованного менеджера блокировок

Особенности CLM

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

Алгоритм Token Ring

Создается логическое кольцо процессов
По кольцу передается маркер
Блокировку захватывает тот,

Особенности

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

Распределенный менеджер блокировок

Каждый узел может обмениваться с остальными
Возможны три типа сообщений
REQUEST
QUEUED
GRANT
Центральным

Алгоритм работы

Каждый узел выполняет общий алгоритм

Распределенный захват блокировки
Алгоритм захвата блокировки
Узел i, который желает захватить блокировку отправляет

Конфликт при захвате

Если после отправки сообщения REQUEST узел получает сообщение REQUEST

Распределенное удержание блокировки

Алгоритм работы узла в состоянии удержания блокировки
Узел j захватил

Освобождение распределенной блокировки

Алгоритм освобождения блокировки
Если в очереди i-го узла есть

Восстановление после сбоя узла

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

Сравнение алгоритмов блокировки

Консистентность

Консистентность – поддерживание общих ресурсов в распределенной системе в непротиворечивом состоянии
Пример

Модели консистентности

Строгая (последовательная) консистентность
Процессорная консистентность (ослабленная консистентность)‏
Слабая консистентность
Косистентность захвата-освобождения

Процессорная консистентность

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

Строгая (последовательная) консистентность

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

Слабая консистентность

Доступ разделяется на операции чтения-записи и операции синхронизации. Все операции

Косистентность захвата-освобождения

Доступ к ресурсу разделяется на операции захвата и освобождения
После

Другие модели консистентности

Консистентность областей
Ресурс разбивается на области и для каждой области

Алгоритмы сохранения общего консистентного состояния (snapshot)‏

Общее состояние
запись данных распределенной файловой

Алгоритм Ченди-Лампорта

Любой процесс распределенной системы может инициировать создание слепка
Инициатор передает сообщение