2013 Задачи (1162820), страница 2

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

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

секция, каждый шлет всем сообщение о запросе крит. секции. Далее всеотвечают (т.к. монопольная модификация). И одно сообщение на передачу маркера.Итого:3*(9)*10*(Ts + req * Tb) + 3*9*10*(Ts + resp*Tb) + 3*10(Ts + marker*Tb)З.Ы. девятки убираются при широковещательной шине, тройки убираются, еслипоследовательно входим в критические секции на каждом процессе.Тема 7.Задача 1.Надежный и неделимый широковещательный алгоритм:В каждом процессоре – очередь поступающих сообщений. Идентификатор – логическоевремя прибытия (всегда разное).1) Отправляется сообщение группе процессов (в сообщении хранятся идентификаторыпроцессов!)При приеме:- помечается как «недоставленное», в качестве приоритета – временная метка- информируется отправитель о присланном сообщении и о текущем логическомвремени2) Получает ответы от всех адресатов- выбирает из присланных сообщений максимальный приоритет- рассылает всем этот приоритетПри приеме:- сообщение устанавливается как «доставленное»- если оно становится первым в очереди, то выполняется3) При обнаружении недоставленного сообщения (отправитель сломался) выполняетсяследующее:- отправляем всем соседям «запрос» о данном сообщении- все отвечают, у кого-то есть «доставленное» - приоритет посылается всем- нету доставленного -> начинаем заново (шлем всем, ждем отметок о времени).Решение задачи:- 5 сообщений посылается, после чего падает отправитель- 5 сообщений с временными метками возвращается- таймаут- 9 сообщений от какого-нибудь процесса о времени- 9 ответов о том, что «недоставлено» или нету- 9 сообщений-запросов- 9 ответов с временем- 9 сообщений с финальным временемИтого:55*Ts + 14*req*Tb + 9*ask*Tb + 9*ans*Tb + 9*time*Tb + 9*final*TbReq – сообщения запросы (например, 9 байт с идентификаторами, 1 полезный байт)Ask – сообщения вопрос типа «есть ли у кого-нибудь доставленное сообщение?» (1 байт сномером сообщения, 1 байт с полезной инфой)Ans – Ответы на вопрос (нету или недоставлено)Time – сообщения с логическим временемFinal – финальное сообщение с итоговым логическим временемЗадача 3.Консистентное и строго консистентное множества контрольных точек.1.

Множество контрольных точек называется строго консистентным, если во время егофиксации никаких обменов между процессами не было.2. Множество контрольных точек называется консистентным, если для любойзафиксированной операции приема сообщения, соответствующая операция посылки такжезафиксирована (нет сообщений-сирот).Простой метод фиксации консистентного множества контрольных точек фиксация локальной контрольной точки после каждой операции посылки сообщения.Синхронная фиксация контрольных точек и восстановление.Требование: надежная передача сообщений (сообщения всегда приходят, схема FIFO).Два вида точек – постоянная (уже точно установлена) и пробная – становится постояннойпосле окончания работы алгоритма.Сохранение:1) процесс создает пробную точку, шлет всемвсе создают пробную точку, отвечают процессу-инициаторуЗ.Ы. при этом нельзя посылать неслужебные сообщения2) процесс шлет всем информацию о создании новой постоянной точки, пробнаястановится постояннойОптимизация: если не было сообщений после последней контрольной точки, то можно несоздавать новуюВосстановление:1) инициатор шлет всем сообщение о готовке к откатувсе отвечают, что готовыЗ.Ы.

после этого до конца алгоритма не посылается неслужебных сообщений2) инициатор шлет сообщение об откате, все откатываютсяОптимизация: если не было сообщений с момента фиксации, то можно не откатываться.Асинхронный алгоритм.Предположение: есть стабильная область памяти, в которой хранится информация о всехприсланных и отосланных сообщениях.Точки создаются в произвольные моменты. Откат до консистентного состояния (когда всепринятые и отправленные сообщения совпадают) – множество контрольных точекнеконсистенто, может возникнуть эффект домино, но меньше нагрузки на создание точек.Получение строгой консистентности:- делаем нестрогую консистентность (по синхронному алгоритму)- при этом считаем количество отосланных сообщений каждому процессу- проверяем, все ли сообщения дошли до адресатов, для этого шлем им счетчикотосланных сообщений, если совпал – шлем «ок» процессу-инициатору консистентности!!!З.Ы.

этот пункт можно так сделать: все шлют одному процессу сообщения сосчетчиками (9 сообщений), он все суммирует и шлет каждому процессу сообщение собщим количеством сообщений, которое тот должен был принять (9 сообщений), всеотвечают готовностью, если готовы (9 сообщений) Итого 27 дополнительных сообщений;координатора проверять не надо, так как он уже всем отправлял сообщения -> каналыпусты.Итого: T1 + 3n (Ts + a*Tb)Задача 2.Протоколы голосования.1) Существует кворум записи Nw > N/2, кворум чтения Nr: Nw + Nr > N (N –количество процессов). Смысл в том, что мы должны быть уверены, что финальнаяверсия данных есть у Nw процессов, таким образом, если мы опросим Nrпроцессов, то из присланных ими данных обязательно будет один ответ с самойпоследней версией данных.2) Алгоритм:a. Запись: шлем всем(!) процессам запрос на модификацию – шлем M байтданных и K байт доп.

информации (куда пишем данные, версия данных)Должны получить Vw ответов об успешной записи.b. Чтение – шлем запрос всем (можно, наверное, не всем, а только Nrпроцессам), получаем необходимые данные (шлем K байт – идентификаторданных)Решении Задачи:N - число байт.10 – число процессов, с которыми контактирует данный процесс = M2 – число записей = w10 – число чтений = 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).

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

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