Решения 6 и 7 тем (1162832), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Итого:

55*Ts + 14*req*Tb + 9*ask*Tb + 9*ans*Tb + 9*time*Tb + 9*final*Tb

Req – сообщения запросы (например, 9 байт с идентификаторами, 1 полезный байт)

Ask – сообщения вопрос типа «есть ли у кого-нибудь доставленное сообщение?» (1 байт с номером сообщения, 1 байт с полезной инфой)

Ans – Ответы на вопрос (нету или недоставлено)

Time – сообщения с логическим временем

Final – финальное сообщение с итоговым логическим временем

Задача 3.

Консистентное и строго консистентное множества контрольных точек.

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

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

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

Синхронная фиксация контрольных точек и восстановление.

Требование: надежная передача сообщений (сообщения всегда приходят, схема FIFO).

Два вида точек – постоянная (уже точно установлена) и пробная – становится постоянной после окончания работы алгоритма.

Сохранение:

1. процесс создает пробную точку, шлет всем

все создают пробную точку, отвечают процессу-инициатору

З.Ы. при этом нельзя посылать неслужебные сообщения

1. процесс шлет всем информацию о создании новой постоянной точки, пробная становится постоянной

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

Восстановление:

1. инициатор шлет всем сообщение о готовке к откату

все отвечают, что готовы

З.Ы. после этого до конца алгоритма не посылается неслужебных сообщений

1. инициатор шлет сообщение об откате, все откатываются

Оптимизация: если не было сообщений с момента фиксации, то можно не откатываться.

Асинхронный алгоритм.

Предположение: есть стабильная область памяти, в которой хранится информация о всех присланных и отосланных сообщениях.

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

Получение строгой консистентности:

- делаем нестрогую консистентность (по синхронному алгоритму)

- при этом считаем количество отосланных сообщений каждому процессу

- проверяем, все ли сообщения дошли до адресатов, для этого шлем им счетчик отосланных сообщений, если совпал – шлем «ок» процессу-инициатору консистентности

!!!З.Ы. этот пункт можно так сделать: все шлют одному процессу сообщения со счетчиками (9 сообщений), он все суммирует и шлет каждому процессу сообщение с общим количеством сообщений, которое тот должен был принять (9 сообщений), все отвечают готовностью, если готовы (9 сообщений) Итого 27 дополнительных сообщений; координатора проверять не надо, так как он уже всем отправлял сообщения -> каналы пусты.

Итого: T1 + 3n (Ts + a*Tb)

Задача 2.

Протоколы голосования.

1. Существует кворум записи Nw > N/2, кворум чтения Nr: Nw + Nr > N (N – количество процессов). Смысл в том, что мы должны быть уверены, что финальная версия данных есть у Nw процессов, таким образом, если мы опросим Nr процессов, то из присланных ими данных обязательно будет один ответ с самой последней версией данных.

2. Алгоритм:

   1. Запись: шлем всем(!) процессам запрос на модификацию – шлем M байт данных и K байт доп. информации (куда пишем данные, версия данных)

Должны получить Vw ответов об успешной записи.

1. Чтение – шлем запрос всем (можно, наверное, не всем, а только Nr процессам), получаем необходимые данные (шлем K байт – идентификатор данных)

Решении Задачи:

N - число байт.

10 – число процессов, с которыми контактирует данный процесс = M

2 – число записей = w

10 – число чтений = r

Накладные расходы сообщения (пускай 5 байт), в которых хранятся версия переменной и указание области памяти = k

На запись: w[M(Ts + (N + k)*Tb) + Vw*(Ts + Tb)] – отсылка записи и ответы от заданного числа процессов

На чтение: r[Vr(Ts + k *Tb) + Vr(Ts + N*Tb) ]– запрос на чтение у Vr процессов и получение ответа от Vr процессов.

Считаем Vr + Vw = 11, после чего минимизируем число сообщений для Vr и Vw (при Т = 300)

Характеристики

Список файлов ответов (шпаргалок)