2007 Задачи (1162817), страница 6
Текст из файла (страница 6)
Процессорные операции, включая чтение из памяти и записьв память считаются бесконечно быстрыми.Решение.9. Консистентность памяти по входу и алгоритм ее реализации в DSM с полным размножением. Сколько временипотребует трехкратное выполнение критической секции и модификация в ней 10 переменных каждым процессом,если DSM реализована на 10 ЭВМ сети с шинной организацией(с аппаратными возможностями широковещания).Время старта (время разгона после получения доступа к шине для передачи) равно 100, время передачи байтаравно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса (приодновременных запросах - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти и записьв память считаются бесконечно быстрыми.Решение.26Тема 7(См.
Лекция 7: "Отказоустойчивость")1. Проблемы бесконечного восстановления и потери сообщений. Какие методы их решения существуют? Дайтеоценку накладных расходов для сети из 10 ЭВМ с шинной организацией (без аппаратных возможностейшироковещания). Время старта (время разгона после получения доступа к шине для передачи) равно 100, времяпередачи байта равно 1 (Ts=100,Tb=1).
Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса(при одновременных запросах - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти изапись в память считаются бесконечно быстрыми.Решение.Cломался х и откатился на х2. Y получил сообщение-призрак, потому что в состоянии х2 Х его еще не посылал, иоткатился на y2. Теперь В x содержится информация о сообщении-призраке и он откатывается на х1.
(Если я всеправильно понимаю, нам все равно, синее сообщение принято до или после х2).Методы решения: 1. простой консистентный метод (по локальным точкам после отправки, отправка и фиксациянеделимы. Получается просто консистентное множество контрольных точек.) 2. Синхронная фиксацияконтрольных точек (получается строго консистентное множество).Задачка: Поскольку синхронная фиксация в следующем вопросе, рассмотрим простой консистентный метод.Считается, что сохранение точки происходит мгновенно, тогда расход - это перепосылка в случае отката. Т.е. Длякаждого отката накладные расходы складываются из пересылки "квитанций" (см.
Лекции) + пересылки самихсообщений. Для одного сломавшегося процесса из 10-ти и каждого из n сообщений длиной Li байт и квитанции в 1байт этоSum(i=1 to n){Li + 1}какой-то бред2. Консистентное множество контрольных точек и алгоритмы их фиксации. Дайте оценку накладных расходов насинхронную фиксацию консистентного множества контрольных точек для сети из 10 ЭВМ с шинной организацией(без аппаратных возможностей широковещания).
Время старта (время разгона после получения доступа к шинедля передачи) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получаютпоследовательно в порядке выдачи запроса (при одновременных запросах - в порядке номеров ЭВМ). Операции сфайлами и процессорные операции, включая чтение из памяти и запись в память, считаются бесконечнобыстрыми.Решение. Алгоритмы - простой консистентный, синхронный и асинхронныйЗадачка: Пусть первый - инициатор (алгоритм см. 7.1.5 в лекциях).1-ый стартует ко 2-му и пересылает один байт. Структура сообщений такова, что одного байта на это сообщениедостаточно.
(100 + 1)1-ый стартует к 3-му....Итого: на начало первой фазы нужно 909=(Ts + Tb)*9 времениТеперь ждем 9 ответов - столько же времени.Теперь проводим третью фазу - тоже столько жеИтого (Ts + Tb)*9*3 = 27273. Протоколы голосования. Алгоритмы и применение. Дайте оценку времени выполнения одним процессом 2-хопераций записи и 10 операций чтения одного байта информации с файлом, размноженным на остальных 10 ЭВМсети с шинной организацией (без аппаратных возможностей широковещания). Определите оптимальные значениякворума чтения и кворума записи. Время старта (время разгона после получения доступа к шине для передачи)равно 100, время передачи байта равно 1 (Ts=100,Tb=1).
Доступ к шине ЭВМ получают последовательно в порядке27выдачи запроса (при одновременных запросах - в порядке номеров ЭВМ). Операции с файлами и процессорныеоперации, включая чтение из памяти и запись в память, считаются бесконечно быстрыми.Про алгоритмы см. в лекциях (раздел "Алгоритмы голосования").Рассмотрим механизм статического распределения голосов (еще можно оценивать вес голоса каждого из серверовв зависимости от его надежности, либо использовать динамическое распределение голосов/изменение составаголосующих (кстати, как это работает?))Положим Vw = 10, Vr = 1 (Vw > N/2, Vr+Vw>N, а Vr удобно выбирать поменьше, потому что операций чтениямного)При модификации файла сервер сначала посылает 10 запросов на запись размером в 1 байт (тип сообщения),затем получает Vw ответов, содержащих номер последней версии файла (отведем под него 4 байта + 1 для типасообщения).Внимание: мы считаем, что локальная копия файла актуальна (номер версии равен максимальному из полученныхномеров).
Если это не так, придется обновить копию, передавая по сети файл целиком, а его размера в задаче нет.Кроме того, подразумевается, что в момент рассылки запросов никакой другой сервер не начнет делать то жесамое - иначе придется учитывать таймауты и повторять рассылку еще раз.После этого сервер модифицирует файл и рассылает остальным данные об изменениях (6 байт: собственноизменения + какая-нибудь информация о позиции в тексте + тип сообщения).Продолжительность операции записи: ((100+1) + (100+5) + (100+6)) * 10 = 3120При чтении данных сервер посылает запросы Vr другим серверам (5 байт - тип сообщения и информация опозиции в тексте) и получает Vr ответов (6 байт - тип сообщения, номер версии файла и данные), а затем выбираетнаиболее актуальный.Продолжительность операции чтения: ((100+5) + (100+6)) * 1 = 211Ответ: 3120*2 + 211*10 = 8350Желающие могут поэкспериментировать с Vr и Vw, но это приведет к увеличению времениПримечание: в задаче написано про десять остальных серверов.
Так что я предполагал, что всего их 11.4. Алгоритм надежных и неделимых широковещательных рассылок сообщений. Дайте оценку временивыполнения одной операции рассылки для сети из 10 ЭВМ с шинной организацией (без аппаратных возможностейшироковещания). Время старта (время разгона после получения доступа к шине для передачи) равно 100, времяпередачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса(при одновременных запросах - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти изапись в память, считаются бесконечно быстрыми.Решение. Первый процесс массово рассылает сообщение M остальным.1) В сообщении хранится n=9 байт номеров + k=1 полезных байт.
(k взято с потолка. Но так велели наконсультации)2) Это сообщение уходит n=9 раз, для каждого раза разгоняемся => время 1 фазы =(Ts + (n+k)*Tb)*n3) Приходит n=9 ответов по Lt = 1 байт с временными (приоритетными) метками => время =(Ts + Lt*Tb)*n4) Процесс-отправитель рассылает максимальную метку (опять длина = Lt) => время =(Ts + Lt*Tb)*nСуммируя, получаем ответ: n*(3*Ts + (n + k + 2*Lt)*Tb) = 280828.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
