2007 Задачи (1162817), страница 5
Текст из файла (страница 5)
Если посмотреть на ее определение (см. след. задачу),то ясно что точно те же самые условия мы имеем и на локальном процессоре (операторы выполняютсявперемешку из разных процессов, но в нужном порядке относительно каждого процесса).Причинная консистентность удовлетворяет, поскольку она аналогична последовательной, если сделать всеуправляющие переменные причинно-зависимыми.PRAM консистентность не удовлетворяет (см. пример в лекциях про kill), т.к. процессы могутодновременно войти в Критическую СекциюПроцессорная консистентность удовлетворяет, т.к.
есть когерентность в памяти (согласие средипроцессов относительно порядка записи в каждую переменную)Слабая консистентность, к. по входу и по выходу не удовлетворяют. Нет работы с синхронизационнымипеременными, поэтому нет никакой согласованности вообще.2. Какие модели консистентности памяти удовлетворяют алгоритму Петерсона (алгоритм без каких-либоизменений будет работать правильно), а какие нет? Объясните ответ.Теория. Алгоритм Петерсона (1981).int turn;int flag[ 2 ];void enter_region( int i ){int other;/* номер другого процесса */other = 1 - i;flag[ i ] = TRUE;turn = i;while (turn == i &&flag[ other ] ==TRUE) /* пустой оператор */;}void leave_region( int i ){flag[ i ] = FALSE;}Решение.
По-моему - то же самое, что и в предыдущей задаче.3. Последовательная консистентность памяти и алгоритм ее реализации в DSM с полным размножением. Скольковремени потребует модификация 10 различных переменных 10-ю процессами (каждый процесс модифицируетодну переменную), находящимися на разных ЭВМ сети с шинной организацией (без аппаратных возможностейшироковещания) и одновременно выдавшими запрос на модификацию. Время старта (время разгона послеполучения доступа к шине) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получаютпоследовательно в порядке выдачи запроса (при одновременных запросах - в порядке номеров ЭВМ).Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.Теория.
Последовательна консистентность. По его определению, модель последовательной консистентностипамяти должна удовлетворять следующему условию: Результат выполнения должен быть тот-же, как если быоператоры всех процессоров выполнялись бы в некоторой последовательности, в которой операторы каждогоиндивидуального процессора расположены в порядке, определяемом программой этого процессора22Решение.Допустим, что каждый процесс имеет все 10 переменных, всего процессов - N. Тогда каждый цикл модификациибудет выглядеть как:••Процесс i посылает координирующему процессу запрос (1 передача запроса размера A)Координирующий процесс через какое-то время высылает ответ с подтверждением и порядковым номероммодификации ( N передач подтверждения модификации каждой размера B)Всего у нас будет N таких запросов, а поскольку используется шина и все эти соединения должны в любом случаесостоятся, то получаем общее время как сумму времен каждой передачи: N * ( (N + 1) * Ts + (A + N * B) * Tb )Ответ: N * ( (N + 1) * Ts + (A + N * B) * Tb )4.
Причинная консистентность памяти и алгоритм ее реализации в DSM с полным размножением. Скольковремени потребует модификация 10 различных переменных, если все 10 процессов (каждый процессмодифицирует одну переменную), находящихся на разных ЭВМ сети с шинной организацией (без аппаратныхвозможностей широковещания), одновременно выдали запрос на модификацию своей переменной. Время старта(время разгона после получения доступа к шине) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ кшине ЭВМ получают последовательно в порядке выдачи запроса (при одновременных запросах - в порядке23номеров ЭВМ). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечнобыстрыми. Никаких сведений от компилятора о причинной зависимости операций модификации не имеется.Решение.
"Причинная модель консистентности памяти определяется следующим условием: Последовательностьопераций записи, которые потенциально причинно зависимы, должна наблюдаться всеми процессами системыодинаково, параллельные операции записи могут наблюдаться разными узлами в разном порядке."Из условия (см. конец задачи) ясно, что процессы не знают о причинных зависимостях между переменными.Поэтому эта задача сводится к предыдущей.5. Процессорная консистентность памяти и алгоритм ее реализации в DSM с полным размножением. Скольковремени потребует модификация 10 различных переменных, если все 10 процессов (каждый процессмодифицирует одну переменную), находящихся на разных ЭВМ сети с шинной организацией (без аппаратныхвозможностей широковещания), одновременно выдали запрос на модификацию своей переменной.
Время старта(время разгона после получения доступа к шине) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ кшине ЭВМ получают последовательно в порядке выдачи запроса (при одновременных запросах - в порядкеномеров ЭВМ). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечнобыстрыми.Решение. "PRAM (Pipelined RAM) консистентность определяется следующим образом: Операции записи,выполняемые одним процессором, видны всем остальным процессорам в том порядке, в каком они выполнялись, нооперации записи, выполняемые разными процессорами, могут быть видны в произвольном порядке.Модель процессорной консистентности отличается от модели PRAM консистентности тем, что в нейдополнительно требуется когерентность памяти: Для каждой переменной x есть общее согласие относительнопорядка, в котором процессоры модифицируют эту переменную, операции записи в разные переменные параллельны.
Таким образом, к упорядочиванию записей каждого процессора добавляется упорядочивание записейв переменные или группы "Либо я чего-то не понимаю, либо ответ тот же самый, что и в предыдущих задачах. Просто возможны немногоразные последовательности посылки сигналов и содержимое сообщений различается - т.е. варьируются A и B.6. PRAM консистентность памяти и алгоритм ее реализации в DSM с полным размножением. Сколько временипотребует 3-кратная модификация 10 различных переменных, если все 10 процессов (каждый процесс 3 разамодифицирует одну переменную), находящихся на разных ЭВМ сети с шинной организацией (без аппаратныхвозможностей широковещания), одновременно выдали запрос на модификацию.
Время старта (время разгонапосле получения доступа к шине) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМполучают последовательно в порядке выдачи запроса (при одновременных запросах - в порядке номеров ЭВМ).Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.Решение. "PRAM (Pipelined RAM) консистентность определяется следующим образом: Операции записи,выполняемые одним процессором, видны всем остальным процессорам в том порядке, в каком они выполнялись, нооперации записи, выполняемые разными процессорами, могут быть видны в произвольном порядке."24То же самое.
Разница может быть только в том, когда было послано какое-то подтверждение и сколько ждалкакой-то процесс. 3-х кратная модификация - просто умножаем ответ на 3, все равно нужно посылать всесообщения.7. Слабая консистентность памяти и алгоритм ее реализации в DSM с полным размножением. Сколько временипотребует модификация одним процессом 10 обычных переменных, а затем 3-х различных синхронизационныхпеременных, если DSM реализована на 10 ЭВМ сети с шинной организацией (с аппаратными возможностямишироковещания).
Время старта (время разгона после получения доступа к шине для передачи) равно 100, времяпередачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса(при одновременных запросах - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти изапись в память считаются бесконечно быстрыми.Решение. Это может быть неверно.Пусть длинна сообщения при работе с синхр. перем. равна B. Мы получили время выполнения 3 * ( Ts + B * Tb ) +( Ts + A * Tb ) .Если принять, что синхронизационные переменные отвечают каждая за несколько обычныхпеременных, то таких цикла потребовалось бы 3 (размер сообщения при широковещани А стал бы другим), тополучим 3 * [ 3 * ( Ts + B * Tb ) + ( Ts + A * Tb ) ].Ответ: 3 * [ 3 * ( Ts + B * Tb ) + ( Ts + A * Tb ) ]Из другого места, описание алгоритма:25а)при модификации обычных данных записываются в локальную память.при модификации синхронизационных переменных все модификации данных посылаются координатору,который номерует модификации, рассылает модификации широковещательно и возвращаетпосылающему номер последней принятой модификации.
Если отправитель не имеет какой-либо записи, ондолжен её потребовать.б) при чтении обычных данных они берутся из локальной памятипри чтении синхр. переменных обращение к координатору происходит так же, как при записи.в) значения модифицируемых переменных рассылаются координатору после обращения к синхр. перем. идалее координатором либо при обработке такого обращения, либо когда требуют пропущенные фрагментымодификаций.г) процесс блокируется при обращении к синхр. переменным;8.
Консистентность памяти по выходу и алгоритм ее реализации в DSM с полным размножением. Сколько временипотребует трехкратное выполнение критической секции и модификация в ней 10 переменных каждым процессом ,если DSM реализована на 10 ЭВМ сети с шинной организацией (с аппаратными возможностями широковещания).Время старта (время разгона после получения доступа к шине для передачи) равно 100, время передачи байтаравно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса (приодновременных запросах - в порядке номеров ЭВМ).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
