РОС, ответы на задачи

Материал из eSyr's wiki.

Версия от 09:04, 2 июня 2009; Tehhi (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Содержание

1 Тема 1
2 Тема 2
3 Тема 3
4 Тема 4
5 Тема 5
6 Тема 6
7 Тема 7
8 Прочие вкусности от лектора
9 Задачи из лекций Вали Глазковой
10 Ссылки

Тема 1

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

Ответ:

Для реализации мультипрограммного режима необходимы:

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

Видимо, при отсутствии таких механизмов, необходимо воспользоваться паравиртуализацией (эмуляция аппаратных средств + гипервизор (ОС)).

Защита памяти --- защита оперативной памяти. Привилегированный режим необходим для защиты внешней памяти.

Тема 2

Задача 1 (Деккер)

Если в алгоритме Деккера (enwiki) не изменять значение переменной turn при выходе из критической секции, то каким требованиям он перестанет удовлетворять? Объясните, почему.

Ответ:

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

Задача 2 (считающий семафор через двоичный)

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

Ответ:

struct CountingSemaphore { 
  int val;
  BinarySemaphore wait;  // ждём здесь, чтобы ждать для S 
  BinarySemaphore mutex; // защищает val 
  
  CountingSemaphore(int k) {
    val = k;
    wait = 0;
    mutex = 1;
  }
  void P();
  void V();
} S;
  
void CountingSemaphore::P() { 
  S.mutex.P(); 
  if (S.val <= 0) { 
    S.val--;
    S.mutex.V(); 
    S.wait.P(); 
  } 
  else { 
    S.val--;
    S.mutex.V(); 
  }
}
  
void CountingSemaphore::V() { 
  S.mutex.P(); 
  if (S.val < 0)
    S.wait.V(); 
  S.val++;
  S.mutex.V();
}

Ответ (2 вариант, из лекций)

Int S = N;
Semaphore access = 1; // семафор для монопольного доступа к S
Semaphore wait = 1;	// при помощи него мы будет реализовывать ожидание.

P(S) {
	P(wait);
	P(access);
	S = S – 1;
	If(S > 0) V(wait)
	V(access);
}

V(S) {
	P(access);
	S++;
	If(S == 1) V(wait);
	V(access);
}

Задача 3 (события через двоичный семафор)

Имеется механизм двоичных семафоров. Опираясь на него, реализуйте операторы POST(имя переменной-события) и WAIT(имя переменной-события).

Ответ:

 BinarySemaphore sem;
 
 void event::POST() {
   sem.V();
 }
 void event::WAIT() {
   sem.P();
   sem.V();
 }

Задача 4 (двоичный семафор через TSL/прерывания)

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

Ответ: Чтобы не заморачиваться на регистровый вариант TSL можно предложить его логический аналог { bool tsl(bool val){

bool i = val;
lock = 1;
return i;

} val = 0 // пусть это означает, что семафор свободен void P(){

r = tsl(val) // получили старое значение val и поменяли его
if(r){
 <добавляем себя в списрк ждущих>
 <ждем прерывания>
}

}

void V(){

if(<список ждущих не пуст>){
 <шлем прерывание 1 из списка>
}
else{val = 0}

} }

Задача 5 (верхняя релаксация)

Правильно ли использованы события в алгоритме, который реализует метод верхней релаксации? Оцените, насколько этот алгоритм можно выполнить быстрее, чем последовательный, если число процессоров мультипроцессора = N, время выполнения одного оператора присваивания (A[i][j]=....) равно 1, временами выполнения остальных операторов можно пренебречь.

 float  A[ L1 ][ L2 ];
 struct condition s[ L1 ][ L2 ];
 
 for ( i = 0; i < L1; i++)         // Цикл 1
     for ( j = 0; j < L2; j++) 
         { clear( s[ i ][ j ]) }
 
 for ( j = 0; j < L2; j++)         // Цикл 2
     { post( s[ 0 ][ j ]) }
 
 parfor ( i = 1; i < L1-1; i++)    // Цикл 3
     for ( j = 1; j < L2-1; j++) 
     {
         wait( s[ i-1 ][ j ]);
         A[ i ][ j ] = (A[ i-1 ][ j ] + A[ i+1 ][ j ] + A[ i ][ j-1 ] + A[ i ][ j+1 ]) / 4;
         post( s[ i ][ j ]);
     }

Ответ: Введу читателя в курс дела:

Механизм событий
- POST(S) – объявление события S (является аналогом "V(S);" - освобождение семаформа S)
- WAIT(S) – процесс ожидает, когда произойдет событие S (является аналогом "P(S);V(S);" - освобождение семаформа S)
- CLEAR(S) – чистим значение S (я полагаю, эквивалентно S := 0, если продолжать аналогию с семаформа)
Parfor - это цикл, витки которого распределяются между нитями (или процессами).
Алгоритм последовательной верхней релаксации выглядит так:

 for ( i = 1; i < L1-1; i++)
   for ( j = 1; j < L2-1; j++) 
        A[ i ][ j ] = (A[ i-1 ][ j ] + A[ i+1 ][ j ] + A[ i ][ j-1 ] + A[ i ][ j+1 ]) / 4;

IMHO, описанный выше алгоритм работает верно. Распараллеливание происходит только по внешнему циклу (по i), и каждая из нитей дожидается, пока будет пересчитан элемент, располагающийся НАД A[ i ][ j ].

Оценка времени выполнения:

Остановимся на оценке времени выполнения Цикла 3.
Последовательное выполнение (без операторов wait и post) требует $(L 1 - 2) * (L 2 - 2)$ присваиваний.
При работе на N процессорах (без учета операторов wait и post):
- каждый процессор (кроме последнего) получает для обработки $\lceil (L1-2) / N \rceil$ строк.
- пока первая нить обрабатывает все свои строки, кроме своей последней, все остальные нити простаивают. Преимущество возникает, когда первая нить начинает обрабатывать свою последнюю строку. После того, как первая нить подсчитает первый элемент этой строки, в работу включится вторая нить, и L2-3 элемента первая и вторая нить будут обрабатывать параллельно. Далее первая нить будет простаивать, а работать будет вторая нить.
- как можно видеть, преимущество возникает только на таких таких строках m, что: m-я строка распределена k-й нити, а строка m+1 - нити с номером k+1. В каждом таком случае мы получаем преимущество по времени равное $(L 2 - 3)$ . Всего таких номеров m ровно N-1. Суммарные выигрыш получается равным $N * (L 2 - 3)$
- итого, время параллельного выполнения составляет $(L 1 - 2) * (L 2 - 2) - N * (L 2 - 3)$

Тема 3

Задача 1 (MPI_BARRIER)

В транспьютерной матрице размером 4*4, в каждом узле которой находится один процесс, необходимо выполнить операцию барьер (MPI_BARRIER) для всех процессов. Сколько времени потребуется для этого, если все процессы выдали ее одновременно. Время старта равно $T s$ , время передачи байта равно $T b$ ( $T_s=10~,~~T_b=2$ ). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.

Ответ: MPI_Barrier останавливает выполнение вызвавшей ее задачи до тех пор, пока не будет вызвана изо всех остальных задач, подсоединенных к указываемому коммуникатору. Гарантирует, что к выполнению следующей за MPI_Barrier инструкции каждая задача приступит одновременно с остальными.

Задача 2 (MPI_BCAST)

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

Ответ:

Операция MPI_BCAST осуществляет посылку сообщений всем соседям данного транспьютера. Следовательно, каждая посылка сообщения в транспьютерной матрице операцией (MPI_BCAST) заполняет очередную диагональ матрицы: 0 - (0, 0); 1 - (1, 0), (0, 1); 2 - (2, 0), (1, 1), (0, 2) и т.д (где (i, j) - координата процесса). Следовательно, для осуществения операции MPI_BCAST в матрице 4x4 нужно 6 * (Ts + N*Tb) единиц времени.

Задача 3 (MPI_GATHER)

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

Ответ:

Задача 4 (MPI_SCATTER)

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

Ответ:

Задача 5 (суммирование)

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

Ответ:

Задача 6 (максимум)

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

Ответ:

Задача 7 (передача сообщения)

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

Ответ:

Задача 8 (буферизуемая передача сообщения)

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

Ответ:

Задача 9 (блокирующая/неблокирующая передача сообщения)

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

Ответ:

Тема 4

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

Ответ: Все процессы составляют логическое кольцо, когда каждый знает, кто следует за ним. По кольцу циркулирует маркер, дающий право на вход в критическую секцию. Получив маркер (посредством сообщения точка-точка) процесс либо входит в критическую секцию (если он ждал разрешения) либо переправляет маркер дальше. После выхода из критической секции маркер переправляется дальше, повторный вход в секцию при том же маркере не разрешается. 15*(Ts + 1*Tb)

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

Ответ:

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

Ответ:

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

Ответ:

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

Ответ:

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

Ответ:

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

Ответ:

Тема 5

1. Какие принципиальные решения приходится принимать при обеспечении файлового сервиса?

Ответ:

2. Интерфейс сервера директорий.

Ответ:

3. Семантика разделения файлов.

Ответ:

4. Серверы с состоянием и без состояния. Достоинства и недостатки.

Ответ:

5. Алгоритмы обеспечения консистентности кэшей в распределенных файловых системах.

Ответ:

6. Способы организации размножения файлов и коррекции копий.

Ответ:

Тема 6

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

Ответ: не слабее последовательной консистентности. При последовательной консистентности невозможно, чтобы оба процесса прочли false, читая флаги другого процесса. Таким образом требование того, что в критической секции не могут одновременно находиться находиться оба процесса, выполнение. Тупика тоже для модели последовательной консистентности не будет

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

Ответ:

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

Ответ:

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

Ответ:

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

Ответ:

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

Ответ:

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

Ответ:

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

Ответ:

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

Ответ:

Тема 7

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

Ответ:

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

Ответ:

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

Ответ:

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

Ответ:

Прочие вкусности от лектора

1. Какую модель консистентности можно реализовать в мультипроцессорах (с общей памятью)?

Ответ:

Последовательную. Строгую не можем, так как у процессоров имеется кэш.

2. MPI. В синхронизационном режиме отправка сообщения не начинается, пока у процесса, который должен принять сообщение, не появится RECEIVE. А как мы это узнаем?

Ответ:

Процесс, в котором появился SEND, должен отправить запрос, есть ли на другом конце RECEIVE. Это должен сделать именно он, так как:

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

3. Зачем в задаче 2.4 необходимо наличие возможности прерывания, ведь и без него, казалось бы, всё можно реализовать?

Ответ:

Задачи из лекций Вали Глазковой

Задача 1

Реализовать модель причинной консистентности без сервера и упорядоченного широковещания (кто и где будет блокироваться?).

Задача 2

Пример "смерти процессов" возможен для PRAM консистентонсти и невозможен для последовательной. Возможен ли он для причинной консистентности?

Задача 3

Написать алгоритмы Деккера и Петерсона.

Алгоритм Деккера (enwiki)

Суть алгоритма -- не дать двум параллельным процессам одновременно войти в критическую секцию.

 flag[0] := false
 flag[1] := false
 turn := 0   // or 1

 p0:                                      p1:
     flag[0] := true                          flag[1] := true
     while flag[1]=true {                     while flag[0]=true {
         if turn ≠ 0 {                           if turn ≠ 1 {
             flag[0] := false                        flag[1] := false
             while turn ≠ 0 {                        while turn ≠ 1 {
             }                                       }
             flag[0] := true                         flag[1] := true
         }                                       }
     }                                        }

    // critical section                       // critical section 
    ...                                       ...
    // remainder section                      // remainder section
    turn := 1                                 turn := 0
    flag[0] := false                          flag[1] := false

Алгоритм Петерсона (enwiki)

 flag[0]   = 0
 flag[1]   = 0
 turn      = 0
 
 P0: flag[0] = 1                        P1: flag[1] = 1
     turn = 1                               turn = 0
     while( flag[1] && turn == 1 );         while( flag[0] && turn == 0 );
             // do nothing                          // do nothing
     // critical section                    // critical section 
     ...                                    ...
     // end of critical section             // end of critical section
     flag[0] = 0                            flag[1] = 0

Задача 4

Читатель не должен читать сырые данные. Читать могут сразу много. Писать – только один.

Int rd = 0; // количество читателей
Semaphore access = 1; 
Semaphore reader = 1;	// семафор для читателей
Semaphore writer = 1;	// семафор для писателей

Void writer_enter(){
	// мы должны дождаться, пока другие писатели закончат писать
	P(writer);

	// мы должны удостовериться, что в этот момент нет никаких читалелей
	P(reader);
}

Void writer_leave(){
	V(reader);
	V(writer);
}

Void reader_enter(){
	P(writer);	// а нет ли внутри писателя?

	// критическая секция
	P(access);
	Rd++;
	If(rd == 1) P(reader);	// теперь писатель будет знать, что кто-то читает
	V(access);
	V(writer);
}
Void reader_leave ( ) {
	P(access);
	Rd--;
	If(rd == 0) V(reader); // теперь писатель будет знать, что никто больше не читает
	V(access);
}

Задача 5

Каким (какого размера? - наверное это имеется ввиду) должен быть квант информации, чтобы минимизировать время передачи в конвейере?

Ссылки

Получено с http://esyr.org/wiki/%D0%A0%D0%9E%D0%A1%2C_%D0%BE%D1%82%D0%B2%D0%B5%D1%82%D1%8B_%D0%BD%D0%B0_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B8

РОС, ответы на задачи

Материал из eSyr's wiki.

Содержание

Тема 1

Тема 2

Задача 1 (Деккер)

Задача 2 (считающий семафор через двоичный)

Задача 3 (события через двоичный семафор)

Задача 4 (двоичный семафор через TSL/прерывания)

Задача 5 (верхняя релаксация)

Тема 3

Задача 1 (MPI_BARRIER)

Задача 2 (MPI_BCAST)

Задача 3 (MPI_GATHER)

Задача 4 (MPI_SCATTER)

Задача 5 (суммирование)

Задача 6 (максимум)

Задача 7 (передача сообщения)

Задача 8 (буферизуемая передача сообщения)

Задача 9 (блокирующая/неблокирующая передача сообщения)

Тема 4

Тема 5

Тема 6

Тема 7

Прочие вкусности от лектора

Задачи из лекций Вали Глазковой

Задача 1

Задача 2

Задача 3

Задача 4

Задача 5

Ссылки

Просмотры

Личные инструменты

Навигация

инструменты

Разделы

Спецкурсы

9 семестр

7 семестр

5 семестр

3 семестр

Поиск

Инструменты