(2016) Ответы (1162879), страница 7
Текст из файла (страница 7)
Такие общие переменные называютзащищенными переменными.2) Алгоритм. Фактически, используется маркер, в котором хранится информация омодификациях. Маркер присутствует у процесса, который выполнил последниепреобразования с критической секцией (или выполняет). Все преобразованиязаносятся в маркер. Ленивая реализация: после преобразований процесс неотсылает результаты, а передает их по требованию.
Процесс, которому нужендоступ в секцию, отсылает запрос о маркере.a) при записи обычной (не синхронизационный) переменной – запись влокальную память;b) чтение – из локальной памяти;c) выход из критической секции – запись всех модификаций в маркер, вход вкритическую секцию – запрос маркера у всех процессов, блокировка допоявления маркера; если пришел запрос о маркере – запоминается;d) блокировка – только при входе в критическую секцию;3) Процесс посылает всем запрос на маркер, T1 = Ts + Lзапроса*Tb (учтенавозможность аппаратного широковещания).
В ответ один из процессов передаётему маркер, T2 = Ts + Lмаркера*Tb. Это делает каждый процесс, 3 раза.Итого: T = 3*10*(T1 + T2) = 30*(2*Ts + (Lзапроса + Lмаркера)*Tb).Возможна реализация, когда каждый процесс 3 раза выполняет критическуюсекцию, после чего только выполняет передачу маркера. В таком случае время в 3раза меньше.7.Консистентность памяти по входу и алгоритм ее реализации в DSM с полнымразмножением. Сколько времени потребует трехкратное выполнениекритической секции и модификация в ней 10 переменных каждым процессом,если DSM реализована на 10 ЭВМ сети с шинной организацией (с аппаратнымивозможностями широковещания).
Время старта (время «разгона» послеполучения доступа к шине для передачи сообщения) равно 100, время передачибайта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно впорядке выдачи запроса на передачу (при одновременных запросах – в порядкеномеров ЭВМ). Процессорные операции, включая чтение из памяти и запись впамять считаются бесконечно быстрыми.1) Консистентность по входу - совместно используемые данные, относящиеся кданной критической области, становятся непротиворечивыми при входе в этуобласть.2) Тут опять маркер.
Реализация почти как в предыдущем алгоритме, только с каждойсинхронизационной переменной связан свой маркер и в нем хранятся модификацииопределенных переменных (т.к. с каждой синхронизационной переменной связанысвои переменные). Если процесс хочет захватить переменную в немонопольномрежиме, то ждет сообщения от владельца переменной (хотя бы одного). Если вмонопольном, то нужен ответ от всех процессов (либо ок, либо маркер).a) запись – из локальной памяти;b) чтение – из локальной памяти;c)i)захват переменной в немонопольный режим – шлем всем сообщение«немонопольный захват», ждем маркер;ii)захват в монопольном режиме – шлем всем сообщение«монопольный захват», ждем ответа от всех;iii)если пришел «монопольный захват», маркера нет и он нам не нужен,то шлем «ок»;iv)если пришел «монопольный захват», маркера нет, но он нужен, тождем маркер и потом отправляем «ок»;v)если пришел «монопольный захват» и есть маркер, шлем маркер;vi)если пришел «немонопольный захват», есть маркер, которым мывладеем немонопольно, то шлем копию маркера запросившемупроцессу;vii)при выходе из секции модифицируем маркер;d) при каждом запросе «монопольный захват» или «немонопольный захват» блокировка до получения необходимых ответов;3) Все модификации монопольные.
3 раза критическая секция, каждый шлет всемсообщение о запросе критической секции. Далее все отвечают (т.к. монопольнаямодификация), при этом будет 8 сообщений «ок» и одно с маркером. Это делаеткаждый процесс, 3 раза.T1 = Ts + Tb*Lзапроса (учтена возможность аппаратного широковещания);T2 = 8*(Ts + Tb*Lок);T3 = Ts + Tb*Lмаркера;Итого: 3*10*(T1 + T2 + T3) = 30*(10*Ts + (Lзапроса + 8*Lок + Lмаркера)*Tb).В нашем случае нет необходимости в независимом параллельном доступе кпеременным. Но если считать, что с каждой переменной связана своясинхронизационная переменная, то ответ увеличивается в 10 раз.Тема-71.Алгоритм надежных и неделимых широковещательных рассылок сообщений.Дайте оценку времени выполнения одной операции рассылки для сети из 10ЭВМ с шинной организацией (без аппаратных возможностей широковещания),если отправитель сломался после посылки 5-го сообщения. Время старта (время«разгона» после получения доступа к шине для передачи сообщения) равно 100,время передачи байта равно 1 (Ts=100,Tb=1).
Доступ к шине ЭВМ получаютпоследовательно в порядке выдачи запроса на передачу (при одновременныхзапросах – в порядке номеров ЭВМ). Процессорные операции, включая чтение изпамяти и запись в память, считаются бесконечно быстрыми.Алгоритм выполняется в две фазы и предполагает наличие в каждом процессоре очередейдля запоминания поступающих сообщений. В качестве уникального идентификаторасообщения используется его начальный приоритет - логическое время отправления,значение которого на разных процессорах различно.1-ая фаза.1.
Процесс-отправитель посылает сообщение группе процессов (список ихидентификаторов содержится в сообщении).2. При получении этого сообщения процессы:a. Приписывают сообщению приоритет, помечают сообщение как«недоставленное» и буферизуют его. В качестве приоритета используетсявременная метка (текущее логическое время).b. Информируют отправителя о приписанном сообщению приоритете.2-ая фаза.При получении ответов от всех адресатов, отправитель:1. Выбирает из всех приписанных сообщению приоритетов максимальный иустанавливает его в качестве окончательного приоритета сообщения.2.
Рассылает всем адресатам этот приоритет.3. Получив окончательный приоритет, получатель:a. Приписывает сообщению этот приоритет.b. Помечает сообщение как «доставленное».c. Упорядочивает все буферизованные сообщения по возрастанию ихприписанных приоритетов.d. Если первое сообщение в очереди отмечено как «доставленное», то онобудет обрабатываться как окончательно полученное.Если получатель обнаружит, что он имеет сообщение с пометкой «недоставленное»,отправитель которого сломался, то он для завершения выполнения протоколаосуществляет следующие два шага в качестве координатора.1.
Опрашивает всех получателей о статусе этого сообщения. Получатель можетответить одним из трех способов:● Сообщение помечено как «недоставленное» и ему приписан такой-топриоритет.● Сообщение помечено как «доставленное» и имеет такой-то окончательныйприоритет.● Он не получал это сообщение.2 Получив все ответы, координатор выполняет следующие действия:a. Если сообщение у какого-то получателя помечено как «доставленное», тоего окончательный приоритет рассылается всем. (Получив это сообщениекаждый процесс выполняет шаги фазы 2).b.
Иначе координатор заново начинает весь протокол с фазы 1. (Повторнаяпосылка сообщения с одинаковым приоритетом не должна вызыватьколлизий).Итого:●●●●●●●●●5 сообщений посылается, после чего падает отправитель5 сообщений с временными метками возвращаетсятайм-аут8 сообщений от какого-нибудь процесса о времени (т.к. адресатов изначально было9, один из них рассылает сообщения остальным)4 ответа о том, что не доставлено + приоритет4 ответа о том, что не получал8 сообщений от координатора8 ответов с временными метками8 сообщений с финальным временем55*Ts + 5*req*Tb + 5*time*Tb + 8*ask*Tb + 4*ans*Tb + 4*none*Tb + 8*req*Tb + 8*time*Tb+ 8*final*TbВРЕМЯ СОСТОИТ ИЗ СЧЕТЧИКА СОБЫТИЙ И НОМЕРА ПРОЦЕССА!Req – сообщения-запросы (например, 9 байт с идентификаторами, 2 байта на начальныйприоритет - счетчик событий и номер процесса, 1 байт - содержательная информация всообщении), 12 байт.Time – сообщения с логическим временем, 2 байта.Ask – сообщения-вопрос типа «есть ли у кого-нибудь доставленное сообщение?» (1 байт сномером сообщения, 1 байт с полезной инфой).Ans – ответы на вопрос координатора типа “не доставлено, приоритет такой-то”, 2 байта.None - ответы на вопрос координатора типа “не получал”, 1 байт.Final – финальное сообщение с итоговым логическим временем, 2 байта.2.Протоколы голосования.
Алгоритмы и применение. Дайте оценку временивыполнения одним процессом 2-х операций записи и 10 операций чтения Nбайтов информации с файлом, расположенным (размноженным) на остальных 10ЭВМ сети с шинной организацией (без аппаратных возможностейшироковещания). Определите оптимальные значения кворума чтения и кворумазаписи для N=300. Время старта (время «разгона» после получения доступа кшине для передачи) равно 100, время передачи байта равно 1 (Ts=100,Tb=1).Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса (приодновременных запросах – в порядке номеров ЭВМ). Операции с файлами ипроцессорные операции, включая чтение из памяти и запись в память,считаются бесконечно быстрыми.Общая схема использования голосования при размножении файлов может бытьпредставлена следующим образом.Файл может модифицироваться разными процессами только последовательно (приоткрытии файла на запись процесс-писатель будет ждать закрытия файла другимписателем или всеми читателями), а читаться всеми одновременно (протоколписателей-читателей).
Все модификации файла нумеруются, и каждая копия файлахарактеризуется номером версии – количеством ее модификаций. Каждой копииприписано некоторое количество голосов Vi Пусть общее количество приписанных всемкопиям голосов равно V. Определяется кворум записи Vw и кворум чтения Vr так, чтоVw + Vr > VДля записи информации в файл писатель рассылает ее всем владельцам копий файла идолжен получить Vw голосовот тех, кто успешно выполнил запись.Для получения права на чтение читателю достаточно получить необходимое числоголосов (Vr) от любых серверов.
Кворум чтения выбран так, что хотя бы один из техсерверов, от которых получено разрешение, является владельцем текущей копии файла. Зачтением информации из файла читатель может обратиться к любому владельцу текущейкопии файла.Описанная схема базируется на статическом распределении голосов. Различие в голосах,приписанных разным серверам, позволяет учесть их особенности (надежность,эффективность). Еще большую гибкость предоставляет метод динамическогоперераспределения голосов.Для того чтобы выход из строя некоторых серверов не привел к ситуации, когданевозможно получить кворум, применяется механизм изменения состава голосующих.Различают протокол принятия единого решения и протокол принятия согласованныхрешений.Хотя собственно алгоритм предписывает назначить каждой копии отдельное числоголосов, будем считать, что у каждой копии ровно 1 голос.Алгоритм:Запись:● Посылаем всем процессам запрос на модификацию длины Lreq● Должны получить все ответы с текущими версиями файла.● Предположим, что имеет место согласие всех серверов относительно версии файла,тогда достаточно произвести Vw записей.Чтение:● Посылаем запрос на чтение из К байт служебной информации Vr процессам.● Получаем Vr ответов с текущими версиями файла.● Выбираем наиболее свежую и читаем её.Одна запись требует 10*(Ts + Lreq*Tb) + 10*(Ts + Lresp*Tb) + Vw*(Ts + N*Tb).Одно чтение требует Vr*(Ts + Lreq*Tb) + Vr*(Ts + Lresp*Tb) + 1*(Ts + N*Tb).Итого 2*[10*(Ts + Lreq*Tb) + 10*(Ts + Lresp*Tb) + Vw*(Ts + N*Tb)] + 10*[Vr*(Ts +Lreq*Tb) + Vr*(Ts + Lresp*Tb) + 1*(Ts + N*Tb)].Если принять Lresp = Lreq = 1 байт, то необходимо минимизировать 2*(400*Vw + 2020) +10*(202*Vr + 400) = 800*Vw + 8040 + 2020*Vr.Наилучший результат при Vw = 10, Vr = 1.3.Консистентное и строго консистентные множества контрольных точек.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
