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

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

Перейти к: навигация, поиск

Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.

ПРЕДУПРЕЖДЕНИЕ: Длина этой страницы составляет 90 килобайт. Страницы, размер которых приближается к 32 КБ или превышает это значение, могут неверно отображаться в некоторых браузерах. Пожалуйста, рассмотрите вариант разбиения страницы на меньшие части.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.

Текущая версия Ваш текст
Строка 12: Строка 12:
Видимо, при отсутствии таких механизмов, необходимо воспользоваться паравиртуализацией (эмуляция аппаратных средств + гипервизор (ОС)).
Видимо, при отсутствии таких механизмов, необходимо воспользоваться паравиртуализацией (эмуляция аппаратных средств + гипервизор (ОС)).
-
Защита памяти --- защита оперативной памяти. Привилегированный режим необходим для защиты внешней памяти (''SkyHawk:'' Неправда, привилегированный режим необходим для реализации защиты памяти, иначе любой процесс сможет делать то же, что и ОС, а именно влезать в чужую память.).
+
Защита памяти --- защита оперативной памяти. Привилегированный режим необходим для защиты внешней памяти.
== Тема 2 ==
== Тема 2 ==
Строка 48: Строка 48:
Имеется механизм двоичных семафоров. Опираясь на него, реализуйте P-операцию и V-операцию для общего (считающего) семафора.
Имеется механизм двоичных семафоров. Опираясь на него, реализуйте P-операцию и V-операцию для общего (считающего) семафора.
-
'''Ответ (не реализовано "блокирование" в случае если процесс ждет входа, заменено циклом)'''
+
'''Ответ:'''
<pre>
<pre>
-
int count = N;
+
struct CountingSemaphore {
-
boolSemaphore sem = 1;
+
int val;
-
 
+
BinarySemaphore wait; // ждём здесь, чтобы ждать для S
-
P(s) {
+
BinarySemaphore mutex; // защищает val
-
bool success = false;
+
-
while(!success) {
+
CountingSemaphore(int k) {
-
P(sem);
+
val = k;
-
if(count > 0) {count--; success = true;}
+
wait = 0;
-
V(sem);
+
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();
 +
}
}
}
-
 
+
-
V(s) {
+
void CountingSemaphore::V() {
-
P(sem);
+
S.mutex.P();
-
count++;
+
if (S.val < 0)
-
V(sem);
+
S.wait.V();
 +
S.val++;
 +
S.mutex.V();
}
}
</pre>
</pre>
Строка 75: Строка 92:
Semaphore wait = 1; // при помощи него мы будет реализовывать ожидание.
Semaphore wait = 1; // при помощи него мы будет реализовывать ожидание.
-
P(Int S) {
+
P(S) {
-
wait.P();
+
P(wait);
-
access.P();
+
P(access);
S = S – 1;
S = S – 1;
-
If(S > 0) wait.V(); //если мы последним вошли в критическую секцию(S == 0) - залочили после себя всех
+
If(S > 0) V(wait)
-
access.V();
+
V(access);
}
}
-
V(Int S) {
+
V(S) {
-
access.P();
+
P(access);
S++;
S++;
-
If(S == 1) wait.V(); //мы освобождаем единственное место - надо разлочить ожидающих, если мы освобождаем второе и далее место - значит очереди нет, никого разлочивать не надо
+
If(S == 1) V(wait);
-
access.V();
+
V(access);
}
}
</pre>
</pre>
 +
=== Задача 3 (события через двоичный семафор) ===
=== Задача 3 (события через двоичный семафор) ===
Строка 148: Строка 166:
float A[ L1 ][ L2 ];
float A[ L1 ][ L2 ];
-
struct event s[ L1 ][ L2 ];
+
struct condition s[ L1 ][ L2 ];
for ( i = 0; i < L1; i++) // Цикл 1
for ( i = 0; i < L1; i++) // Цикл 1
Строка 177: Строка 195:
for ( j = 1; j < L2-1; j++)
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;
A[ i ][ j ] = (A[ i-1 ][ j ] + A[ i+1 ][ j ] + A[ i ][ j-1 ] + A[ i ][ j+1 ]) / 4;
- 
-
<s>Нет, события использованы неправильно, так как забыли назначить посчитанным первый столбец:
 
- 
-
for ( i = 0; i < L1; i++) // Это надо вставить до начала
 
-
post( s[ i ][ 0 ]) // основного цикла
 
- 
-
Т.е. конечный вариант:
 
-
</s>
 
- 
-
Нет, это не нужно, потому что этих событий никто никогда не ждет! Это нужно только для варианта алгоритма с двумя parfor (по i и по j) – в нем есть еще один wait.
 
-
Так что события здесь использованы корректно, но для такого варианта достаточно и семафоров.
 
-
<s>
 
-
<pre>
 
-
float A[ L1 ][ L2 ];
 
-
struct event 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
+
IMHO, описанный выше алгоритм работает верно. Распараллеливание происходит только по внешнему циклу (по i), и каждая из нитей дожидается, пока будет пересчитан элемент, располагающийся НАД A[ i ][ j ].
-
{ post( s[ 0 ][ j ]) }
+
-
 
+
-
for ( i = 0; i < L1; i++)
+
-
{ post( s[ i ][ 0 ]) }
+
-
 
+
-
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 ]);
+
-
}
+
-
</pre>
+
-
</s>
+
-
Причем, wait( s[ i ][ j-1 ]); делать во внутреннем цикле "Цикл 3" не нужно, так как внутри мы имеем for, а не parfor - это отличие данного алгоритма от алгоритма в лекциях.
+
<u>Оценка времени выполнения</u>:
<u>Оценка времени выполнения</u>:
Строка 220: Строка 205:
** каждый процессор (кроме последнего) получает для обработки <math>\lceil (L1-2) / N \rceil </math> строк.
** каждый процессор (кроме последнего) получает для обработки <math>\lceil (L1-2) / N \rceil </math> строк.
** пока первая нить обрабатывает все свои строки, кроме своей последней, все остальные нити простаивают. Преимущество возникает, когда первая нить начинает обрабатывать свою последнюю строку. После того, как первая нить подсчитает первый элемент этой строки, в работу включится вторая нить, и L2-3 элемента первая и вторая нить будут обрабатывать параллельно. Далее первая нить будет простаивать, а работать будет вторая нить.
** пока первая нить обрабатывает все свои строки, кроме своей последней, все остальные нити простаивают. Преимущество возникает, когда первая нить начинает обрабатывать свою последнюю строку. После того, как первая нить подсчитает первый элемент этой строки, в работу включится вторая нить, и L2-3 элемента первая и вторая нить будут обрабатывать параллельно. Далее первая нить будет простаивать, а работать будет вторая нить.
-
** как можно видеть, преимущество возникает только на таких таких строках m, что: m-я строка распределена k-й нити, а строка m+1 - нити с номером k+1. В каждом таком случае мы получаем преимущество по времени равное <math>(L2-3)</math>. Всего таких номеров m ровно N-1. Суммарный выигрыш получается равным <math>(N-1)*(L2-3)</math>
+
** как можно видеть, преимущество возникает только на таких таких строках m, что: m-я строка распределена k-й нити, а строка m+1 - нити с номером k+1. В каждом таком случае мы получаем преимущество по времени равное <math>(L2-3)</math>. Всего таких номеров m ровно N-1. Суммарные выигрыш получается равным <math>N*(L2-3)</math>
-
** итого, время параллельного выполнения составляет ''' <math>(L1-2) * (L2-2) - (N-1)*(L2-3) </math>'''
+
** итого, время параллельного выполнения составляет ''' <math>(L1-2) * (L2-2) - N*(L2-3) </math>'''
-
 
+
-
=== Задача 6 (Писатели и читатели) ===
+
-
Имеется механизм двоичных семафоров. Опираясь на него, реализуйте задачу читателей и писателей (алгоритмы предоставления прав доступа процессам-читателям и процессам-писателям):
+
-
 
+
-
''Процесс-писатель должен получать исключительный (монопольный) доступ к базе данных (других писателей или каких-либо читателей быть не должно). Произвольное число процессов-читателей может работать одновременно, но любой читатель может получить доступ только при отсутствии работающих писателей. ''
+
-
 
+
-
Запросы на доступ должны удовлетворяться “справедливо” - в порядке их поступления (можно исходить из “справедливости“ удовлетворения запросов на двоичные семафоры).
+
-
 
+
-
'''Ответ:'''
+
-
 
+
-
<pre>
+
-
semaphore sem_r = 1, sem_ra = 1, sem_w = 1;
+
-
int readers_count = 0;
+
-
 
+
-
r_enter() { // Читатель хочет начать читать
+
-
sem_r.P();
+
-
sem_ra.P();
+
-
++readers_count;
+
-
if (readers_count == 1)
+
-
sem_w.P(); // Первый читатель блокирует возможность писать
+
-
sem_ra.V();
+
-
sem_r.V();
+
-
}
+
-
 
+
-
r_leave() { // Читатель выходит из области чтения
+
-
sem_ra.P();
+
-
--readers_count;
+
-
if (readers_count == 0)
+
-
sem_w.V(); // Последний читатель освобождает семафор
+
-
sem_ra.V();
+
-
}
+
-
 
+
-
w_enter() { // Писатель хочет писать
+
-
sem_r.P(); // Чтобы новые читатели не начинали читать и чтобы
+
-
// избежать блокировки при одновременном входе читателя и писателя.
+
-
sem_w.P();
+
-
}
+
-
 
+
-
w_leave() { // Писатель выходит из области записи
+
-
sem_w.V();
+
-
sem_r.V();
+
-
}
+
-
 
+
-
</pre>
+
== Тема 3 ==
== Тема 3 ==
Строка 322: Строка 263:
'''Ответ:'''
'''Ответ:'''
-
Пусть никакой буферизации не предусмотрено. Для получения суммы на одном из четырёх центральных процессов ((1,1),(2,1),(1,2),(2,2)) необходимо 4 операции (2 операции для получения суммы своего угла из 4 процессов для каждого центрального процесса, ещё две, чтобы получить общую сумму на всех - <s>на каждом такте складываем сумму на транспьтере с соседями (к примеру, (1,1) с (2,1) и (1, 2). После этого на каждом из 4х транспьютеров получается удвоенная сумма, из которой получается просто сумма)</s> Неправильно, при таких операциях получатся числа вида 3a+2b+2c+2d, 2a+3b+2c+2d и т. п.. На самом деле нужно на первом такте (3) переслать числа по вертикали (от (2,1) к (3,1) и обратно, от (2,2) к (3,2) и обратно, при этом каждый прибавляет полученное значение к своему, так получатся a+c, c+a и b+d, d+b. На втором такте (4) – аналогично по горизонтали, получится полная сумма во всех четырех вершинах). Затем нужно ещё 2 операции, чтобы разослать информацию во все углы. Итого: 6*(Ts+Tb).
+
Пусть никакой буферизации не предусмотрено. Для получения суммы на одном из четырёх центральных процессов ((1,1),(2,1),(1,2),(2,2)) необходимо 4 операции (2 операции для получения суммы своего угла из 4 процессов для каждого центрального процесса, ещё две, чтобы получить общую сумму на всех - на каждом такте складываем сумму на транспьтере с соседями (к примеру, (1,1) с (2,1) и (1, 2). После этого на каждом из 4х транспьютеров получается удвоенная сумма, из которой получается просто сумма)). Затем нужно ещё 2 операции, чтобы разослать информацию во все углы. Итого: 6*(Ts+Tb).
-
[[Изображение:4x4sum.png]]
+
[[Изображение:4x4sum.jpg]]
Если процессов 64, то разобьём квадрат на 4 подквадрата. Как было показано ранее, за 4 операции пожно получить сумму своего квадрата в (2,2), (5,2), (2,5) и (5,5). Ещё две операции нужно на пересылку в центральные процессы. Там за 2 операции получаем сумму на всех из них (как и в первом случае), и ещё 6 на рассылку. Итого: 14*(Ts+Tb).
Если процессов 64, то разобьём квадрат на 4 подквадрата. Как было показано ранее, за 4 операции пожно получить сумму своего квадрата в (2,2), (5,2), (2,5) и (5,5). Ещё две операции нужно на пересылку в центральные процессы. Там за 2 операции получаем сумму на всех из них (как и в первом случае), и ещё 6 на рассылку. Итого: 14*(Ts+Tb).
Строка 338: Строка 279:
=== Задача 7 (передача сообщения) ===
=== Задача 7 (передача сообщения) ===
-
В транспьютерной матрице размером 4*4, в каждом узле которой находится один процесс, необходимо переслать очень длинное сообщение (длиной L байт) из узла с координатами (0,0) в узел с координатами (3,3). Сколько времени потребуется для этого? А сколько времени потребуется для пересылки из узла с координатами (1,1) в узел с координатами (2,2)? Время старта равно времени передачи байта (Ts=Tb). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.
+
В транспьютерной матрице размером 4*4, в каждом узле которой находится один процесс, необходимо переслать очень длинное сообщение (длиной L байт) из узла с координатами (0,0) в узел с координатами (3,3)? Сколько времени потребуется для этого. А сколько времени потребуется для пересылки из узла с координатами (1,1) в узел с координатами (2,2)? Время старта равно времени передачи байта (Ts=Tb). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.
'''Ответ:'''
'''Ответ:'''
Строка 389: Строка 330:
Замечание: в приведенном выше решении, на мой взгляд, имеется ошибка - не учтены повторные посылки запроса после того, как маркер покидает вершину, в направлении ушедшего маркера (они выполняются, если очередь запросов в узле не пуста). Их количество считается вручную (мысленно проводим обход дерева и при каждом переходе в следующую вершину смотрим, остались ли еще запросы на только что покинутой). На приведенном выше рисунке, таким образом, строя обход в глубину справа налево, нужно к ответу добавить 11*(Ts+1*Tb). Данное решение принято аспирантом на экзамене, кроме того, им было сделано замечание, что запрос может посылаться вместе с маркером в одном сообщении, тогда удастся избежать лишних накладных расходов на инициацию передачи и к ответу добавится просто 11*Tb.
Замечание: в приведенном выше решении, на мой взгляд, имеется ошибка - не учтены повторные посылки запроса после того, как маркер покидает вершину, в направлении ушедшего маркера (они выполняются, если очередь запросов в узле не пуста). Их количество считается вручную (мысленно проводим обход дерева и при каждом переходе в следующую вершину смотрим, остались ли еще запросы на только что покинутой). На приведенном выше рисунке, таким образом, строя обход в глубину справа налево, нужно к ответу добавить 11*(Ts+1*Tb). Данное решение принято аспирантом на экзамене, кроме того, им было сделано замечание, что запрос может посылаться вместе с маркером в одном сообщении, тогда удастся избежать лишних накладных расходов на инициацию передачи и к ответу добавится просто 11*Tb.
- 
-
Замечание2: А если начать обход не с 0 вершины, а с 15? тогда нам потребуется только 23 операции (т.к не придется дважды проходить 15-13, 13-9, 9-0)
 
===Задача 3 (Децентрализованный алгоритм с временными метками)===
===Задача 3 (Децентрализованный алгоритм с временными метками)===
Строка 411: Строка 350:
'''Ответ:'''
'''Ответ:'''
-
Маркер находится у процесса 0. Он спокойно входит в КС, а все остальные шлют broadcast запросы о желании войти в КС. Им нужно для этого 15*16 тактов, так как нет аппаратной поддержки широковещания. После этого у маркера сформировалась очередь из 15 желающих войти в КС, и он по очереди удовлетворяет их желания (на каждое нужна одна пересылка маркера). Всего получается 15*16+15 тактов. Можно чередовать операции рассылки и передачи маркера, но их всё равно будет столько же. Ответ: 15*16*(Ts+Tb*Lreq) + 15*(Ts+Tb*Lmark).
+
Маркер находится у процесса 0. Он спокойно входит в КС, а все остальные шлют broadcast запросы о желнии войти в КС. Им нужно для этого 15*16 тактов, так как нет аппаратной поддержки широковещания. После этого у маркера сформировалась очередь из 15 желающих войти в КС, и он по очереди удовлетворяет их желания (на каждое нужна одна пересылка маркера). Всего получается 15*16+15 тактов. Можно чередовать операции рассылки и передачи маркера, но их всё равно будет столько же. Ответ: 15*16*(Ts+Tb*Lreq) + 15*(Ts+Tb*Lmark).
Заметьте, что здесь Lmark довольно большая. В сообщение должны помещаться очередь длины 1..15 и массив из 16 номеров последних запросов.
Заметьте, что здесь Lmark довольно большая. В сообщение должны помещаться очередь длины 1..15 и массив из 16 номеров последних запросов.
Строка 599: Строка 538:
Консистентность памяти по входу и алгоритм ее реализации в DSM с полным размножением. Сколько времени потребует трехкратное выполнение критической секции и модификация в ней 11 переменных каждым процессом, если DSM реализована на 10 ЭВМ сети с шинной организацией(с аппаратными возможностями широковещания). Время старта (время разгона после получения доступа к шине для передачи) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса (при одновременных запросах - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.
Консистентность памяти по входу и алгоритм ее реализации в DSM с полным размножением. Сколько времени потребует трехкратное выполнение критической секции и модификация в ней 11 переменных каждым процессом, если DSM реализована на 10 ЭВМ сети с шинной организацией(с аппаратными возможностями широковещания). Время старта (время разгона после получения доступа к шине для передачи) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса (при одновременных запросах - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.
-
''Примечание: решение не верное, лектор сказал надо использовать какой-нибудь алгоритм с маркером.'' <br>
 
'''Ответ:''' Консистентность памяти по входу (она же поэлементная в Таненбауме), закрепляет каждую разделяемую переменную за своей синхронизационной переменной. Поэтому для изменения каждой переменной необходимо производить свой захват и освобождение синхронизационной переменной. Так как Крюков сказал, что нужны децентрализованные алгоритмы, пользуемся таким.
'''Ответ:''' Консистентность памяти по входу (она же поэлементная в Таненбауме), закрепляет каждую разделяемую переменную за своей синхронизационной переменной. Поэтому для изменения каждой переменной необходимо производить свой захват и освобождение синхронизационной переменной. Так как Крюков сказал, что нужны децентрализованные алгоритмы, пользуемся таким.
Строка 627: Строка 565:
Сначала прогоняем синхронную фиксацию консистентного множества КТ. Это потребует T1. Эти контрольные точки будем считать промежуточными.
Сначала прогоняем синхронную фиксацию консистентного множества КТ. Это потребует T1. Эти контрольные точки будем считать промежуточными.
-
Исходя из определения, для того, чтобы консистентное множество точек стало строго консистентным, надо убедиться, что между процессами нет никаких сообщений. Для этого мы можем просто пропустить по всем каналам свои собственные сообщения. Если они все пройдут, значит, каналы пусты и множество строго консистентно. Однако, стоит обратить внимание, что координатор уже посылал всем служебные сообщения, так что его каналы проверять не нужно. У нас остается 11 ЭВМ, которые хотят проверить по 10 каналов каждая. ЭВМ запоминают, по каким каналам им приходят эти служебные сообщения. Если придут по всем 10, посылают сообщение координатору с указанием того, что они готовы к созданию точки. Если координатору придут все сообщения, он рассылает уведомление о фиксации множества.
+
Изходя из определения, для того, чтобы консистентное множество точек стало строго консистентным, надо убедиться, что между процессами нет никаких сообщений. Для этого мы можем просто пропустить по всем каналам свои собственные сообщения. Если они все пройдут, значит, каналы пусты и множество строго консистентно. Однако, стоит обратить внимание, что координатор уже посылал всем служебные сообщения, так что его каналы проверять не нужно. У нас остается 11 ЭВМ, которые хотят проверить по 10 каналов каждая. ЭВМ запоминают, по каким каналам им приходят эти служебные сообщения. Если придут по всем 10, посылают сообщение координатору с указанием того, что они готовы к созданию точки. Если координатору придут все сообщения, он рассылает уведомление о фиксации множества.
-
 
+
-
''Примечание: n(n-1) - плохая оценка, надо не проверять все каналы, а просто считать отосланные сообщения''
+
Итак, по полочкам:
Итак, по полочкам:

Пожалуйста, обратите внимание, что все ваши добавления могут быть отредактированы или удалены другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. eSyr's_wiki:Авторское право).
НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!


Отменить | Справка по редактированию (в новом окне)

Шаблоны, использованные на этой странице:

Получено с 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
Личные инструменты
Разделы