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

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

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

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

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

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

Текущая версия Ваш текст
Строка 12: Строка 12:
Видимо, при отсутствии таких механизмов, необходимо воспользоваться паравиртуализацией (эмуляция аппаратных средств + гипервизор (ОС)).
Видимо, при отсутствии таких механизмов, необходимо воспользоваться паравиртуализацией (эмуляция аппаратных средств + гипервизор (ОС)).
-
Защита памяти --- защита оперативной памяти. Привилегированный режим необходим для защиты внешней памяти (''SkyHawk:'' Неправда, привилегированный режим необходим для реализации защиты памяти, иначе любой процесс сможет делать то же, что и ОС, а именно влезать в чужую память.).
+
Защита памяти --- защита оперативной памяти. Привилегированный режим необходим для защиты внешней памяти.
== Тема 2 ==
== Тема 2 ==
Строка 75: Строка 75:
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); //если мы последним вошли в критическую секцию(S == 0) - залочили после себя всех
-
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>
Строка 148: Строка 148:
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
Строка 178: Строка 178:
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++) // Это надо вставить до начала
for ( i = 0; i < L1; i++) // Это надо вставить до начала
Строка 184: Строка 184:
Т.е. конечный вариант:
Т.е. конечный вариант:
-
</s>
 
-
Нет, это не нужно, потому что этих событий никто никогда не ждет! Это нужно только для варианта алгоритма с двумя parfor (по i и по j) – в нем есть еще один wait.
 
-
Так что события здесь использованы корректно, но для такого варианта достаточно и семафоров.
 
-
<s>
 
<pre>
<pre>
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
Строка 211: Строка 207:
}
}
</pre>
</pre>
-
</s>
+
 
Причем, wait( s[ i ][ j-1 ]); делать во внутреннем цикле "Цикл 3" не нужно, так как внутри мы имеем for, а не parfor - это отличие данного алгоритма от алгоритма в лекциях.
Причем, wait( s[ i ][ j-1 ]); делать во внутреннем цикле "Цикл 3" не нужно, так как внутри мы имеем for, а не parfor - это отличие данного алгоритма от алгоритма в лекциях.
Строка 222: Строка 218:
** как можно видеть, преимущество возникает только на таких таких строках 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-1)*(L2-3)</math>
** итого, время параллельного выполнения составляет ''' <math>(L1-2) * (L2-2) - (N-1)*(L2-3) </math>'''
** итого, время параллельного выполнения составляет ''' <math>(L1-2) * (L2-2) - (N-1)*(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: Строка 274:
'''Ответ:'''
'''Ответ:'''
-
Пусть никакой буферизации не предусмотрено. Для получения суммы на одном из четырёх центральных процессов ((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: Строка 290:
=== Задача 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). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.
'''Ответ:'''
'''Ответ:'''
Строка 411: Строка 363:
'''Ответ:'''
'''Ответ:'''
-
Маркер находится у процесса 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 номеров последних запросов.

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

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

Личные инструменты
Разделы