Ответы на задачи (1162829), страница 4
Текст из файла (страница 4)
При этом ещёза время 10*(Ts+Tb*9*Lm) все процессы получат полный набор модификаций.4. PRAM консистентность памяти и алгоритм ее реализации в DSM с полнымразмножением. Сколько времени потребует 3-кратная модификация 10различных переменных, если все 10 процессов (каждый процесс 3 разамодифицирует одну переменную), находящихся на разных ЭВМ сети сшинной организацией (без аппаратных возможностей широковещания),одновременно выдали запрос на модификацию. Время старта (время«разгона» после получения доступа к шине для передачи сообщения) равно100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМполучают последовательно в порядке выдачи запроса на передачу (приодновременных запросах - в порядке номеров ЭВМ).
Процессорныеоперации, включая чтение из памяти и запись в память, считаютсябесконечно быстрыми.PRAM консистентность – действия каждого процесса правильно упорядочены ст.зрения любого другого процесса. Взгляд на последовательность действий разныхпроцессов может отличаться для двух процессов.Производя запись процессор должен записать в локальную память и разослать всемсвои изменения.Здесь требуется надёжность при передаче сообщений по каналам присохранении их порядка.а)при записи- рассылаются изменения всем через координатора.б)при чтении - данные берутся из локальной памятив) значения модифицируемых переменных рассылаются другим процессам при изменении(записи)переменных.г) процесс на время выполнения записи не блокируетсяПотребуется 9*3* (Ts+Tb*Lm)5.
Слабая консистентность памяти и алгоритм ее реализации в DSM с полнымразмножением. Сколько времени потребует модификация одним процессом10 обычных переменных, а затем 3-х различных синхронизационныхпеременных, если DSM реализована на 10 ЭВМ сети с шинной организацией(с аппаратными возможностями широковещания). Время старта (время«разгона» после получения доступа к шине для передачи сообщения) равно100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМполучают последовательно в порядке выдачи запроса на передачу (приодновременных запросах - в порядке номеров ЭВМ). Процессорныеоперации, включая чтение из памяти и запись в память, считаютсябесконечно быстрыми.Слабая консистентность:– доступ к синхронизационным переменным – по последовательнойконсистентности.
– доступ к синхронизационным переменным блокируется, пока не выполнились всеоперации записи других процессов, обращавшихся к синхр. переменной. – доступ к данным запрещенпока не выполнились обращения к синзрон. перем.18а) при модификации обычных данных записываются в локальную память.при модификации синхронизационных переменных все модификации данных посылаютсякоординатору, который номерует модификации, рассылает модификации широковещательнои возвращает посылающему номер последней принятой модификации.
Если отправитель неимеет какой-либо записи, он должен её потребовать.б) при чтении обычных данных они берутся из локальной памятипри чтении синхр. переменных обращение к координатору происходит так же, как при записи.в) значения модифицируемых переменных рассылаются координатору после обращения к синхр.перем. и далее координатором либо при обработке такого обращения, либо когда требуютпропущенные фрагменты модификаций.г) процесс блокируется при обращении к синхр. переменным;Временная оценка: Ts+Tb*Lm*11+Ts*2+Tb*Lm*2=3*Ts+13*Lm6.
Консистентность памяти по выходу и алгоритм ее реализации в DSM сполным размножением. Сколько времени потребует трехкратноевыполнение каждым процессом критической секции, в котороймодифицируются 10 переменных, если DSM реализована на 10 ЭВМ сети сшинной организацией (с аппаратными возможностями широковещания).Время старта (время «разгона» после получения доступа к шине дляпередачи сообщения) равно 100, время передачи байта равно 1 (Ts=100,Tb=1).Доступ к шине ЭВМ получают последовательно в порядке выдачи запросана передачу (при одновременных запросах - в порядке номеров ЭВМ).Процессорные операции, включая чтение из памяти и запись в память,считаются бесконечно быстрыми.3*10*(2*(Ts+Tb*Lcs)+(Ts+Tb*Lv*10+Tb*Lcs))7.
Консистентность памяти по входу и алгоритм ее реализации в DSM сполным размножением. Сколько времени потребует трехкратноевыполнение критической секции и модификация в ней 10 переменныхкаждым процессом, если DSM реализована на 10 ЭВМ сети с шиннойорганизацией (с аппаратными возможностями широковещания). Времястарта (время «разгона» после получения доступа к шине для передачисообщения) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ кшине ЭВМ получают последовательно в порядке выдачи запроса напередачу (при одновременных запросах - в порядке номеров ЭВМ).Процессорные операции, включая чтение из памяти и запись в памятьсчитаются бесконечно быстрыми.3*10*(2*(Ts+Tb*Lcs)+(Ts+Tb*Lv*10+Tb*Lcs))Тема-71.
Алгоритм надежных и неделимых широковещательных рассылоксообщений. Дайте оценку времени выполнения одной операции рассылкидля сети из 10 ЭВМ с шинной организацией (без аппаратных возможностейшироковещания), если отправитель сломался после посылки 5-госообщения. Время старта (время «разгона» после получения доступа к шинедля передачи сообщения) равно 100, время передачи байта равно 1(Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядкевыдачи запроса на передачу (при одновременных запросах - в порядкеномеров ЭВМ). Процессорные операции, включая чтение из памяти и записьв память, считаются бесконечно быстрыми.1920Итого получаются следующие результаты: 5+8 отправок сообщения, 5+8 запросов, 8 уведомлений,5+8 ответов.Времени надо: 13*(Ts+N*Tb)+13*(Ts+Lz*Tb)+8*(Ts+Ln*Tb)+13(Ts+La*Tb)Выделив основные компоненты, получим: 47*Ts+13*N*Tb2.
Протоколы голосования. Алгоритмы и применение. Дайте оценку временивыполнения одним процессом 2-х операций записи и 10 операций чтения Nбайтов информации с файлом, расположенным (размноженным) наостальных 10 ЭВМ сети с шинной организацией (без аппаратныхвозможностей широковещания). Определите оптимальные значениякворума чтения и кворума записи для N=300. Время старта (время «разгона»после получения доступа к шине для передачи) равно 100, время передачибайта равно 1 (Ts=100,Tb=1).
Доступ к шине ЭВМ получают последовательнов порядке выдачи запроса (при одновременных запросах - в порядке номеровЭВМ). Операции с файлами и процессорные операции, включая чтение изпамяти и запись в память, считаются бесконечно быстрыми.Хотя собственно алгоритм предписывает назначить каждой копии отдельное число голосов, будемсчитать, что у каждой копии ровно 1 голос.Одна запись в память потребует:Vw*(Ts+Tb*Lz)+Vw*(Ts+Tb*Lo)+Vw*(Ts+Tb*N), или приведя VwVw*(3*Ts+Tb*Lz+Tb*Lo+Tb*N)Возможно, если писатель не обладает актуальной копией, ему придется запросить её заTs+Tb*Lz+Ts+Tb*NОдно чтение потребует:Vr*(Ts+Tb*Lz)+Vr*(Ts+Tb*Lo)Возможно, если читатель не обладает актуальной копией, ему придется запросить её заTs+Tb*Lz+Ts+Tb*NПолучается, что надо минимизировать Vw(1000+2Lz+2Lo)+Vr(2000+10Lz+10Lo)Наилучший результат будет при Vw=9, Vr=1.
То есть, согласие на запись должны дать все, согласие начтение должен дать любой процесс.3. Консистентное и строго консистентные множества контрольных точек.Дайте оценку накладных расходов на синхронную фиксацию строгоконсистентного множества контрольных точек для сети из 10 ЭВМ с шинной21организацией (без аппаратных возможностей широковещания), еслинакладные расходы на синхронную фиксацию консистентного множестваравны Т1.
Время старта (время «разгона» после получения доступа к шинедля передачи сообщения) равно 100, время передачи байта равно 1(Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядкевыдачи запроса на передачу (при одновременных запросах - в порядкеномеров ЭВМ). Процессорные операции, включая чтение из памяти и записьв память, считаются бесконечно быстрыми.Шаг 1. Рассылка всем сообщений с требованием начать фиксацию локальной контрольной точки.Процессы должны перестать посылать сигналы (кроме служебных), но обязательно приниматьприходящие по линиям связи сигналы (и служебные и не служебные). Процессы должны запоминатьсигналы в своих буферах.Шаг 2. Получение результатов операции.Шаг 3. Когда 2 успешно, то есть все процессы перестали посылать сигналы.Посылается операция проверки каналов:Каждый процесс должен получив такое сообщение поставить его в очередь для данного канала.Когда сообщение пройдет через данный канал, значит все неслужебные сообщения были отправлены.Если сообщение проверки приходит по прочищенному каналу или в очереди канала уже стоит такое сообщение, тогда не следует его распространять дальше.Шаг 4: Когда 3 успешно, то есть все процессоры освободили свои исходящие очереди.
Когда у каждого процессора все входящие каналы прочищены (по ним получен сигнал очистки), тогда он долженпослать сигнал готовности к фиксации строго консистентной контрольной точки.Шаг 5: Когда координатор получит все сообщения о готовности к строго консистентной контрольной точке, он принимает её.Если известно, что физическая среда единая и очередь сообщений к ней одна, тогда координаторделает следующее: рассылает всем сообщение о прочистке канала. Каждый узел должен вернуть этосообщение. Получив любое информационное сообщение процесс его буферизует и фиксирует новуюточку консистентности.
Получив все сообщения координатор вправе считать, что все процессы строгоконсистентны. После чего он должен разослать сообщение о принятии строго консистентногомножества контрольных точек. При получении такого сообщения процесс обязан зафиксироватьимеющуюся контрольную точку как принадлежащую множеству строго консистентных КТ и дальшееё не модифицировать.Далее каждый процесс должен запросить разрешение на посылку сообщений (на нормальный режимработы).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
