(2016) Ответы (1162879), страница 5
Текст из файла (страница 5)
Для успешного выполнения записи требуется, чтобы Nwсерверов ее выполнили. При этом у всех этих серверов должно быть согласиеотносительно номера текущей версии файла. Этот номер увеличивается на единицус каждой коррекцией файла. Для выполнения чтения достаточно обратиться к Nrсерверам и воспользоваться одним из тех, кто имеет последнюю версию файла.Значения для кворума чтения (Nr) и кворума записи (Nw) должны удовлетворятьсоотношению Nr + Nw > N. Поскольку чтение является более частой операцией, тоестественно взять Nr = 1.
Однако в этом случае для кворума записи потребуютсявсе серверы.Тема-6При ответах на вопросы по теме 6 следовать следующему плану.1) Определение модели консистентности.2) Алгоритм реализации в DSM с полным размножением (много писателей и многочитателей, каждый из которых имеет свою копию всех переменных). Алгоритмдолжен быть корректным для любой коммуникационной сети и обеспечиватьвысокую эффективность для конкретной сети, указанной в задаче. Описаниеалгоритма должно содержать ответы на следующие вопросы:a) что делается при записи;b) что делается при чтении;c) когда, кому и как рассылаются значения модифицируемых переменных;d) блокируется ли процесс на время выполнения записи или рассылкизначений переменных;e) если речь идет о моделях консистентности, связанных с синхронизацией, тообъяснить алгоритм синхронизации (например, алгоритм входа в КС ивыхода из нее).3) Оценить время работы описанного в пункте 2 алгоритма применительно кконкретной задаче.1.Последовательная консистентность памяти и алгоритм ее реализации в DSM сполным размножением.
Сколько времени потребует модификация 10 различныхпеременных 10-ю процессами (каждый процесс модифицирует одну переменную),находящимися на разных ЭВМ сети с шинной организацией (без аппаратныхвозможностей широковещания) и одновременно выдавшими запрос намодификацию. Время старта (время «разгона» после получения доступа к шинедля передачи сообщения) равно 100, время передачи байта равно 1(Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачизапроса на передачу (при одновременных запросах – в порядке номеров ЭВМ).Процессорные операции, включая чтение из памяти и запись в память,считаются бесконечно быстрыми.1) Результат любого действия такой же, как если бы операции (чтения и записи) всехпроцессов в хранилище данных выполнялись бы в некотором последовательномпорядке, причём операции каждого отдельного процесса выполнялись бы впорядке, определяемом его программой.2) Децентрализованный алгоритм.
Процесс посылает посредством механизмаупорядоченного широковещания (неделимые широковещательные рассылки)указание о модификации переменной всем владельцам копий соответствующейстраницы (включая и себя) и ждет получения этого своего собственного указания.Т.е. для одной модификации надо сделать одну неделимую широковещательнуюрассылку.Так как у нас нет упорядоченного широковещания, придется реализовать это вручную(возьмем алгоритм из лекции).Алгоритм надежных неделимых широковещательных рассылок сообщений.Алгоритм выполняется в две фазы и предполагает наличие в каждом процессореочередей для запоминания поступающих сообщений. В качестве уникальногоидентификатора сообщения используется его начальный приоритет - логическоевремя отправления, значение которого на разных процессорах различно.1-ая фаза:● Процесс-отправитель посылает сообщение группе процессов (список ихидентификаторов содержится в сообщении).● При получении этого сообщения процессы:○ Приписывают сообщению приоритет, помечают сообщение как«недоставленное» и буферизуют его.
В качестве приоритета используетсявременная метка (текущее логическое время).○ Информируют отправителя о приписанном сообщению приоритете.2-ая фаза:● При получении ответов от всех адресатов, отправитель:○ Выбирает из всех приписанных сообщению приоритетов максимальный иустанавливает его в качестве окончательного приоритета сообщения.○ Рассылает всем адресатам этот приоритет.● Получив окончательный приоритет, получатель:○ Приписывает сообщению этот приоритет.○ Помечает сообщение как «доставленное».○ Упорядочивает все буферизованные сообщения по возрастанию ихприписанных приоритетов.○ Если первое сообщение в очереди отмечено как «доставленное», то онобудет обрабатываться как окончательно полученное.Если получатель обнаружит, что он имеет сообщение с пометкой «недоставленное»,отправитель которого сломался, то он для завершения выполнения протоколаосуществляет следующие два шага в качестве координатора.● Опрашивает всех получателей о статусе этого сообщения.● Получатель может ответить одним из трех способов:○ Сообщение помечено как «недоставленное» и ему приписан такой-топриоритет.○ Сообщение помечено как «доставленное» и имеет такой-то окончательныйприоритет.○ Он не получал это сообщение.● Получив все ответы координатор выполняет следующие действия:○ Если сообщение у какого-то получателя помечено как «доставленное», тоего окончательный приоритет рассылается всем.
(Получив это сообщениекаждый процесс выполняет шаги фазы 2).○ Иначе координатор заново начинает весь протокол с фазы 1. (Повторнаяпосылка сообщения с одинаковым приоритетом не должна вызыватьколлизий).a) При записи делается неделимая широковещательная рассылка.b) При чтении происходит чтение из локальной памяти.c) Значениемодифицируемойпеременнойрассылаетсявсемнеделимошироковещательно при записи.d) На время выполнения записи или рассылки значений переменных процессблокируется, т.к. надо ждать завершения неделимой широковещательной рассылки.3) Оценка времени.Оценим время одной широковещательной рассылки.1 фаза. Процессов у нас 10. Т.е.
текущему процессу надо отправить девяти остальнымпроцессам адрес и значение модифицируемой переменной, список идентификаторовсообщений, кому ещё отправили (идентификаторов тоже девять штук). Пусть подадрес, значение и идентификатор отведем по 1 байту. Одно сообщение занимает 11байтов (если надежность гарантируется, можно список идентификаторов не отправлятьи на этом сэкономить. Тогда размер сообщения будет 2 байта.). Отправка одногосообщения займет T1 = Ts+11*Tb = 111 (T1 = Ts + 2*Tb = 102).
Отправка девятисообщений Т2 = 9*Т1 = 999 (Т2 = 9*Т1 = 918). Каждый из девяти процессов долженответить отправителю приписанным приоритетом. Пусть под приоритет отведем 1байт. Тогда все ответы займут Т3 = 9*(Ts+1*Tb) = 9*101 = 909.Первая фаза займет Т4 = Т2 + Т3 = 999 + 909 = 1908 (Т4 = Т2 + Т3 = 918 + 909 = 1827).2 фаза. Отправитель рассылает максимальный приоритет девяти процессам. Это займетТ5 = 9*(Ts+1*Tb) = 9*101 = 909.Общее время обеих фаз займет Т6 = Т4 + Т5 = 1908 + 909 = 2817 (Т6 = Т4 + Т5 = 2736).Это было время одной широковещательной упорядоченной рассылки. Нам нужнодесять таких. Итоговое время Т = 10*Т6 = 28170 (Т = 10*Т6 = 27360).2.Причинная консистентность памяти и алгоритм ее реализации в DSM с полнымразмножением при условии, что никаких сведений от компилятора о причиннойзависимости операций записи не имеется.
Сколько времени потребуетмодификация 10 различных переменных, если все 10 процессов (каждый процессмодифицирует одну переменную), находящихся на разных ЭВМ сети с шиннойорганизацией (без аппаратных возможностей широковещания), одновременновыдали запрос на модификацию своей переменной. Время старта (время«разгона» после получения доступа к шине для передачи сообщения) равно 100,время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получаютпоследовательно в порядке выдачи запроса на передачу (при одновременныхзапросах – в порядке номеров ЭВМ).
Процессорные операции, включая чтение изпамяти и запись в память, считаются бесконечно быстрыми.1) Последовательность операций записи, которые потенциально причинно зависимы,должна наблюдаться всеми процессами системы одинаково, параллельные операциизаписи могут наблюдаться разными узлами в разном порядке.2) Реализация причинной консистентности может осуществляться следующим образом:i)все модификации переменных на каждом процессоре нумеруются;ii)всем процессорам вместе со значением модифицируемой переменнойрассылается номер этой модификации на данном процессоре, а такженомера модификаций всех процессоров, известных данному процессору кэтому моменту;iii)выполнение любой модификации на каждом процессоре задерживается дотех пор, пока он не получит и не выполнит все те модификации другихпроцессоров, о которых ему было известно.a) При записи модификация рассылается всем процессам;b) При чтении происходит чтение из локальной памяти;c) Модифицируемая переменная рассылается всем процессам при записи;d) На время выполнения записи или рассылки значений переменных процесс неблокируется;3) Оценка времени.Например, первый процесс рассылает всем модификации, его модификация станетизвестна всем.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
