2013 Nurmambetov_2-kr (1162818), страница 2

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

Текст из файла (страница 2)

Данный алгоритм отличается от алгоритма для создания просто консистентного, что надо дополнительно отправлять списки процессов и количества сообщений. Пусть под номер процесса и количество сообщений отведем по 1 байту. Тогда сообщения со списком процессов и количеством сообщений от данного процесса занимают 9*(1+1)= 18 байтов. 9 – потому что всех процессов – 10, и надо знать сколько сообщений ожидать от всех процессов кроме себя. А инициатору тоже отправляется список кому и сколько сообщения было отправлено, тоже кроме себя. Такие обмены списками происходит дважды между каждым процессом и инициатором. Каждый обмен занимает Т2 = Ts + 18*Tb. Всего обменов 9*2 = 18.

Ответ: Общее время Т = Т1 + 18*Т2 = Т1+ 2124.

===отлично

1. В транспьютерной матрице размером 4*4, в каждом узле которой находится один процесс, необходимо выполнить операцию нахождения максимума среди 16 чисел (каждый процесс имеет свое число). Сколько времени потребуется для получения всеми максимального числа, если все процессы выдали эту операцию редукции одновременно. А сколько времени потребуется для нахождения максимума среди 64 чисел в матрице 8*8? Время старта равно 50, время передачи байта равно 1 (Ts=50,Tb=1). Процессорные операции, включая чтение из памяти и запись в память, считаются бесконечно быстрыми.

Решение: Покажем на картинке. Стрелками показаны передачи максимумов.

Как видно, нахождение максимума выполняется за 6 шагов. Шаги 1-4 само нахождение максимума, шаги 5-6 - рассылка. Пусть под число отводится байт.

Ответ: T = 6*(Ts+1*Tb) = 6*(50+1*1) = 306

В случае 8*8, модифицируем приведенное решение. Делим на 4 четверти по 4*4. В каждой четверти выполняем шаги 1-4. Потребуется еще 2 шага для пересылки максимумов каждой четверти к центральным узлам

(от (2,2) => (3,3) и т.д.). Еще 2 шага для нахождения глобального максимума (аналогично шагам 3-4 в случае 4*4), еще 6 шагов, чтобы разослать результат остальным узлам. Получили 4+2+2+6 = 14 шагов.

Ответ: T = 14*(Ts+1*Tb) = 14*(50+1*1) = 714

===отлично

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

Решение:
Последовательная консистентность – все процессы видят одну и ту же последовательность записей в память(как будто память едина и в каждый момент времени исполняется ровно одна команда какого-то процесса).

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

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

Реализация последовательной консистентности в DSM с полным размножением:

а) при записи:

• Посылается координатору запрос на модификацию.

• Координатор принимает запрос на модификацию, присваивает ей номер и высылает автору номер. Если координатор заведомо знает, что процесс не имеет каких-то модификаций, ОТКУДА ОН знает – он их не посылал? от высылает их сразу в этом ответе.

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

• Координатор рассылает всем (кроме автора) модификацию.

• Приняв модификацию, процесс проверяет, получил ли он предыдущие модификации, если не получил, то запрашивает их. Применяет все полученные модификации.

б)при чтении:

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

а также координатором автору новых модификаций после получения от него запроса на запись.

г) блокируется ли процесс на время выполнения записи или рассылки значений переменных:

процесс – автор блокируется до записи (ДО ЧЕГО?) для получения консистентной версии памяти.

Почему процесс сначала посылает координатору запрос? Почему сразу не посылает модификацию?

Нужен децентрализованный алгоритм прежде всего!

Всего 10 процессов. Один из них координатор.

Каждый процесс имеет все 10 переменных, всего процессов - 10. Тогда каждый цикл модификации

будет выглядеть как:

· Процесс i посылает координирующему процессу запрос (1 передача запроса размера A)

· Координирующий процесс через какое-то время высылает ответ с подтверждением и порядковым номером

модификации ( 9 передач подтверждения модификации каждой размера B)

Всего у нас будет 9 таких запросов, а поскольку используется шина и все эти соединения должны в любом случае

состоятся, то получаем общее время как сумму времен каждой передачи: 9 * ( 10 * Ts + (A + 9 * B) * Tb )

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

Т.е. для одной модификации надо сделать одну неделимую широковещательную рассылку.

Так как у нас нет упорядоченного широковещания, придется реализовать это вручную (возьмем алгоритм из лекции).

Алгоритм надежных неделимых широковещательных рассылок сообщений.

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

1-ая фаза.

Процесс-отправитель посылает сообщение группе процессов (список их идентификаторов содержится в сообщении).

При получении этого сообщения процессы:

• Приписывают сообщению приоритет, помечают сообщение как «недоставленное» и буферизуют его. В качестве приоритета используется временная метка (текущее логическое время).

• Информируют отправителя о приписанном сообщению приоритете.

2-ая фаза.

При получении ответов от всех адресатов, отправитель:

• Выбирает из всех приписанных сообщению приоритетов максимальный и устанавливает его в качестве окончательного приоритета сообщения.

• Рассылает всем адресатам этот приоритет.

Получив окончательный приоритет, получатель:

1. Приписывает сообщению этот приоритет.

2. Помечает сообщение как «доставленное».

3. Упорядочивает все буферизованные сообщения по возрастанию их приписанных приоритетов.

4. Если первое сообщение в очереди отмечено как «доставленное», то оно будет обрабатываться как окончательно полученное.

Если получатель обнаружит, что он имеет сообщение с пометкой «недоставленное», отправитель которого сломался, то он для завершения выполнения протокола осуществляет следующие два шага в качестве координатора.

1. Опрашивает всех получателей о статусе этого сообщения.

Получатель может ответить одним из трех способов:

• Сообщение отмечено как «недоставленное» и ему приписан такой-то приоритет.

• Сообщение отмечено как «доставленное» и имеет такой-то окончательный приоритет.

• Он не получал это сообщение.

2. Получив все ответы координатор выполняет следующие действия:

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

• Иначе координатор заново начинает весь протокол с фазы 1. (Повторная посылка сообщения с одинаковым приоритетом не должна вызывать коллизий).

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

Ответ по плану.

1. Результат выполнения должен быть тот же, как если бы операторы всех процессоров выполнялись бы в некоторой последовательности, в которой операторы каждого индивидуального процессора расположены в порядке, определяемом программой этого процессора.

2. а) при записи делается неделимая широковещательная рассылка;

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

в) значение модифицируемой переменной рассылается всем неделимо широковещательно при записи;

г) блокируется, т.к. надо ждать завершения неделимой широковещательной рассылки;

1. Оценка времени.

Оценим время одной широковещательной рассылки.

1 фаза. Процессов у нас 10. Т.е. текущему процессу надо отправить девятерым остальным процессам адрес и значение модифицируемой переменной, список идентификаторов сообщений кому еще отправили (идентификаторов тоже девять штук). Пусть под адрес, значение и идентификатор отведем по 1 байту. Одно сообщение занимает 11 байтов (если надежность гарантируется, можно список идентификаторов не отправлять и на этом сэкономить. Тогда размер сообщения будет 2 байта.). Отправка одного сообщения займет T1 = Ts+11b*Tb = 111 (T1 = Ts + 2b*Tb = 102). Отправка девяти сообщений Т2 = 9*Т1 = 999 (Т2 = 9*Т1= 918). Каждый из девяти процессов должен ответить отправителю приписанным приоритетом. Пусть под приоритет отведем 1 байт. Тогда все ответы займут Т3 = 9*(Ts+1b*Tb) = 9*101 = 909.

Первая фаза займет Т4 = Т2+Т3 = 999+909 = 1908 (Т4 = Т2 + Т3 = 918 + 909 = 1827).

2 фаза. Отправитель рассылает максимальный приоритет девятерым процессам. Это займет Т5 = 9*(Ts+1b*Tb) = 9*101 = 909.

Общее время обоих фаз займет Т6 = Т4 + Т5 = 1908 + 909 = 2817 (Т6 = Т4 + Т5 = 2736).
Это было время одной широковещательной упорядоченной рассылки. Нам нужно десять таких. Итоговое время Т = 10*Т6 = 28170 (Т = 10*Т6 = 27360).

===отлично

1. Имеется механизм двоичных семафоров. Опираясь на него, реализуйте P-операцию и V-операцию для общего (считающего) семафора.

Ответ:

Int S = N;

Semaphore access = 1; // семафор для монопольного доступа к S

Semaphore wait = 1;// при помощи него мы будет реализовывать ожидание.

P(Int S) {

wait.P();

access.P();

S = S – 1;

If(S > 0) wait.V(); //если мы последним вошли в критическую секцию(S == 0) - залочили после себя всех

access.V();

}

V(Int S) {

access.P();

S++;

If(S == 1) wait.V(); //мы освобождаем единственное место - надо разлочить ожидающих, если мы освобождаем второе и далее место - значит очереди нет, никого разлочивать не надо

access.V();

}

===отлично

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

Решение:

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

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