2013 Saktaganov_3-kr (1162819)

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

Текст из файла

23

Задачи и их оценки
1-4-

2-5-

3-5-

4-4-

5-4-

6-5-

7-3

8-5-

9-5-

10-5-

11-5-

12-5-

данные оценки были получены за 3 отправки.

первый текст - черный. второй - красный. третий зеленый.

6, 7 , 9 - с последней отправки, он их не прокомментил, просто поставил оценки, т.к. уже хватало.

Вариант 9

1. Слабая консистентность памяти и алгоритм ее реализации в DSM с полным размножением. Сколько времени потребует модификация одним процессом 10 обычных переменных, а затем выполнение 3-х операций синхронизации, если DSM реализована на 18 ЭВМ сети с шинной организацией (с аппаратными возможностями широковещания). Время старта (время «разгона» после получения доступа к шине для передачи) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи операции посылки сообщения (при одновременно выданных операциях - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти и запись в память, считаются бесконечно быстрыми.

Решение:

1. При слабой консистентности соблюдается последовательная непротиворечивость между группами операций, а не между отдельными операциями. Для выделения этих групп используются переменные синхронизации (Таненбаум – «Распределнные системы», слабая непротиворечивость).

2. а) пишется в локальную память;

б) читается из локальной памяти;

в) при вызове операции синхронизации значения модифицируемых переменных рассылаются всем;

г) процесс, вызвавший операцию синхронизации блокируется пока не завершится операция синхронизации;

д) Алгоритм. Процесс, вызвавший операцию синхронизации посылает всем процессам указание о модификации переменных посредством механизма упорядоченного широковещания (аналог децентрализованного алгоритма для последовательной непротиворечивости, который приведен в лекциях, т.к. образом достигается последовательная консистентность для групп операций).

1. Оценка времени. При модификации переменных, пишется в локальную память. Когда вызывается первая операция синхронизации, модификация рассылается широковещательно. В сообщений содержатся адреса переменных и значения. Не нарушая общность рассуждений, для простоты отведем под адрес и значение по 1 байту. Тогда первая синхронизация займет T_S1 = Ts + 10*(SIZE_ADDRESS + SIZE_VALUE)*Tb = 120.

Т.к. после первой синхронизации ничего не модифицировали, можем не делать широковещательную рассылку, т.к. в силу данного алгоритма при чтении всегда имеем актуальные копии (то, которое записал какой-то процесс, успевший сообщить об этом всем посредством синхронизации памяти, а если не имели бы актуальные копии, то пришлось бы их доставать). Поэтому, при вызове операции синхронизации имеет смысл делать широковещательную рассылку только при наличии модификации после предыдущего вызова операции синхронизации. Т.е. при вызове остальных синхронизации не будет никаких обменов сообщений.

Ответ: Общее время T = T_S1 = 120.

Вопросы.

1. Как определяются переменные, которые модифицировались?

2. Если при синхронизации в процессе А все измененные им переменные рассылались всем, то зачем процессу Б требуется перед чтением переменной давать операцию синхронизации?

Ответы:

1. Модифицированные переменные, как Вы рассказывали, можно определить двумя способами:

а) с помощью компилятора, т.е. компилятор вместо операций присваивания может вставлять вызовы определенных функции;

б) запоминать старые значения переменных, и потом сравнивать. В данном случае можно каждый раз сразу же после операции синхронизации обновлять значения запомненных переменных, и при вызове сравнивать текущие значения переменных с запомненными. Если есть расхождение, то рассылать текущие значения переменных, если нет расхождений, то ничего делать. Т.о. перечень действий при вызове операции синхронизации:

а) сравнить текущие значения с сохраненными;

б) если есть расхождения то разослать текущие значения переменных, которые расходятся, а также обновляем значения сохраненных переменных.

Это верно

2. В книге «Распределенные системы» Таненбаума говорится «…если процесс Р1 вызывает операцию synchronlze(Sl) в то же самое время, когда процесс Р2 вызывает операцию synchron1ze(S2), результат будет точно таким же, как если бы операция synchronlze(Sl) была вызвана раньше операции synchronize(S2), или наоборот». В нашем случае может случиться так: процесс А выдает синхронизацию и занимает шину для рассылки модификации. Моментом позже, когда рассылка еще не кончилась, процесс Б тоже выдает синхронизацию (пусть Б ничего не менял, и соответственно, не будет делать рассылку) перед чтением. Б должен дождаться завершения широковещательной рассылки, инициированной А. Произвести модификации, и только потом произвести операцию чтения, следующей после операции синхронизации. Но в общем случае мы не знаем что именно мы принимаем, пока не завершится операция приема. Поэтому мы должны ждать, если шина занят/принимаем любое сообщение. В этом недостаток данного алгоритма. Ответ не изменится (Т=120), т.к. только один процесс вызывает операцию синхронизации и он не будет ждать завершения какого-либо приема сообщения. Однако, можно модифицировать алгоритм и рассылать «пустые модификации» в случае отсутствия модификаций. Пусть размер «пустой модификации» будет 1 байт. Тогда добавится еще 3*(100+1)=303 времени. В итоге займет 120+303 = 423 (По-моему, лучше алгоритм не модифицировать таким образом, а оставить как было).

В конспектах лекций и в книге «Распределенные системы» Таненбаума не очень четко объясняется эта ситуация. На лекции я объяснял специально – компилятор может хранить значения переменных на регистрах (или другой более быстрой памяти), обновить которые другие процессы не могут, поэтому операция синхронизации нужна, чтобы компилятор обновил такие значения (а в его памяти они будут обновлены при выполнении операциях синхронизации, выданных другими процессами) .

===Хорошо

1. Какие модели консистентности памяти удовлетворяют алгоритму Деккера (алгоритм без каких-либо изменений будет работать правильно), а какие нет? Объясните ответ.

===Отлично

1. В транспьютерной матрице размером 4*4, в каждом узле которой находится один процесс, необходимо выполнить операцию рассылки данных (длиной 18 байт) всем процессам от одного (MPI_SCATTER) - процесса с координатами (0,0). Сколько времени потребуется для этого, если все процессы выдали ее одновременно. Время старта равно 100, время передачи байта равно 3 (Ts=100,Tb=3). Процессорные операции, включая чтение из памяти и запись в память, считаются бесконечно быстрыми.

Решение:

Узел (0,0) рассылает данные. Он имеет 2 исходящих канала. Принимающих узлов 15, значит минимальное количество передач – 8. Этот минимум легко достичь, передавая сообщения по двум конвейерным маршрутам.

Например:

Ответ: T = 8*(Ts+18*Tb) = 8*(100+54) = 1232

Даже грубое решение (посылка 6 сообщений по 15 байт) дает лучшее время.

Правильное время = 618

Пересмотрена и зачитана Вами на «Отлично»

===Отлично

1. Сколько времени потребует выбор координатора среди 18 процессов, находящихся на разных ЭВМ сети с шинной организацией (без аппаратных возможностей широковещания), если используется алгоритм «задиры»? Время старта равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми. «Задира» расположен на ЭВМ с номером 0 и имеет уникальный номер процесса 0.

Решение:

Процесс 0 отправляет сообщение «ВЫБОРЫ» всем 17 «старшим» процессам. От всех получает ответ «ОК». Процесс 1 аналогично, но уже «старших» процессов 16 и т.д. Процесс 17 никому не отправляет сообщение «ВЫБОРЫ».

Получили 17+16+15+….+1 = 153 сообщений «ВЫБОРЫ» и столько же сообщений «ОК». Пусть размеры сообщений по 1 байту.

Ответ: T = 153*(Ts+SIZE_VYBOR*Tb)+153*(Ts+SIZE_OK*Tb) = 153*101*2=30906

И да, я забыл добавить рассылку сообщений «КООРДИНАТОР». Их 17 штук, добавляем 17*(100+1) = 1717, ответ 30906+1717=32623.

А если посылать сообщения в другом порядке (сначала процессам с самыми большими номерами?

Описание алгоритма задиры:
«Алгоритм «задиры».

Если процесс обнаружит, что координатор очень долго не отвечает, то инициирует выборы. Процесс P проводит выборы следующим образом:

1. P посылает сообщение «ВЫБОРЫ» всем процессам с большими чем у него номерами.

2. Если нет ни одного ответа, то P считается победителем и становится координатором.

3. Если один из процессов с большим номером ответит, то он берет на себя проведение выборов. Участие процесса P в выборах заканчивается.

В любой момент процесс может получить сообщение «ВЫБОРЫ» от одного из коллег с меньшим номером. В этом случае он посылает ответ «OK», чтобы сообщить, что он жив и берет проведение выборов на себя, а затем начинает выборы (если к этому моменту он уже их не вел). Следовательно, все процессы прекратят выборы, кроме одного - нового координатора. Он извещает всех о своей победе и вступлении в должность сообщением «КООРДИНАТОР». »

Пункт 1 гласит что надо отправить «ВЫБОРЫ» ВСЕМ процессам с большими чем у него номерами.

Но не обязательно отправлять сообщения в порядке возрастания номеров – можно начинать с проесса с самым большим номером (в порядке уменьшения номеров)

В описании алгоритма говорится если процесс получит «ВЫБОРЫ», должен отправителю ответить «ОК», а затем НАЧИНАЕТ выборы. Т.е., строго следуя алгоритму, т.к. у нас выборы инициирует процесс с наименьшим номером, в конечном итоге выборы проведут все процессы. Из этих выводов получаем что общее время не зависит от порядка рассылки. Любая модификация будет уже другим алгоритмом.

===Хорошо

1. Протоколы голосования при размножении файлов. Дайте оценку времени выполнения одним процессом 2-х операций записи и 12 операций чтения N байтов информации с файлом, размноженным на остальных 18 ЭВМ сети с шинной организацией (без аппаратных возможностей широковещания). Определите оптимальные значения кворума чтения и кворума записи для N=300. Время старта (время «разгона» после получения доступа к шине для передачи) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса (при одновременных запросах - в порядке номеров ЭВМ). Операции с файлами и процессорные операции, включая чтение из памяти и запись в память, считаются бесконечно быстрыми.

Решение:

Количество всех ЭВМ – N = 19.

Почему N=19? Серверов же 18 (на них размножен файл)

N_R - кворум чтения, N_W - кворум записи.

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

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

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