Редактирование: РОС, ответы на задачи
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
ПРЕДУПРЕЖДЕНИЕ: Длина этой страницы составляет 92 килобайт. Страницы, размер которых приближается к 32 КБ или превышает это значение, могут неверно отображаться в некоторых браузерах. Пожалуйста, рассмотрите вариант разбиения страницы на меньшие части.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 12: | Строка 12: | ||
Видимо, при отсутствии таких механизмов, необходимо воспользоваться паравиртуализацией (эмуляция аппаратных средств + гипервизор (ОС)). | Видимо, при отсутствии таких механизмов, необходимо воспользоваться паравиртуализацией (эмуляция аппаратных средств + гипервизор (ОС)). | ||
- | Защита памяти --- защита оперативной памяти. Привилегированный режим необходим для защиты внешней памяти | + | Защита памяти --- защита оперативной памяти. Привилегированный режим необходим для защиты внешней памяти. |
== Тема 2 == | == Тема 2 == | ||
Строка 48: | Строка 48: | ||
Имеется механизм двоичных семафоров. Опираясь на него, реализуйте P-операцию и V-операцию для общего (считающего) семафора. | Имеется механизм двоичных семафоров. Опираясь на него, реализуйте P-операцию и V-операцию для общего (считающего) семафора. | ||
- | '''Ответ | + | '''Ответ:''' |
<pre> | <pre> | ||
- | int | + | 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(); | ||
+ | } | ||
} | } | ||
- | + | ||
- | V( | + | void CountingSemaphore::V() { |
- | + | S.mutex.P(); | |
- | + | if (S.val < 0) | |
- | + | S.wait.V(); | |
+ | S.val++; | ||
+ | S.mutex.V(); | ||
} | } | ||
</pre> | </pre> | ||
Строка 75: | Строка 92: | ||
Semaphore wait = 1; // при помощи него мы будет реализовывать ожидание. | Semaphore wait = 1; // при помощи него мы будет реализовывать ожидание. | ||
- | P( | + | P(S) { |
- | + | P(wait); | |
- | + | P(access); | |
S = S – 1; | S = S – 1; | ||
- | If(S > 0) | + | If(S > 0) V(wait) |
- | + | V(access); | |
} | } | ||
- | V( | + | V(S) { |
- | + | P(access); | |
S++; | S++; | ||
- | If(S == 1) | + | If(S == 1) V(wait); |
- | + | V(access); | |
} | } | ||
</pre> | </pre> | ||
+ | |||
=== Задача 3 (события через двоичный семафор) === | === Задача 3 (события через двоичный семафор) === | ||
Строка 148: | Строка 166: | ||
float A[ L1 ][ L2 ]; | float A[ L1 ][ L2 ]; | ||
- | struct | + | 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; | ||
+ | |||
- | < | + | <del>IMHO, описанный выше алгоритм работает верно. Распараллеливание происходит только по внешнему циклу (по i), и каждая из нитей дожидается, пока будет пересчитан элемент, располагающийся НАД A[ i ][ j ].</del> |
+ | |||
+ | Во-первых, точно забыли назначить посчитанным первый столбец: | ||
for ( i = 0; i < L1; i++) // Это надо вставить до начала | for ( i = 0; i < L1; i++) // Это надо вставить до начала | ||
post( s[ i ][ 0 ]) // основного цикла | post( s[ i ][ 0 ]) // основного цикла | ||
+ | |||
+ | Во-вторых, в основном цикле нужно ждать не только пока посчитается предыдущая строка, но и предыдущий столбец т.к. он тоже участвует в вычислениях A[i,j]: | ||
+ | |||
+ | parfor ( i = 1; i < L1-1; i++) // Цикл 3 | ||
+ | for ( j = 1; j < L2-1; j++) | ||
+ | { | ||
+ | wait( s[ i-1 ][ j ]); | ||
+ | wait( s[ i ][ j-1 ]); // <- здесь ждем значение в предыдущем столбце | ||
+ | A[ i ][ j ] = (A[ i-1 ][ j ] + A[ i+1 ][ j ] + A[ i ][ j-1 ] + A[ i ][ j+1 ]) / 4; | ||
+ | post( s[ i ][ j ]); | ||
+ | } | ||
Т.е. конечный вариант: | Т.е. конечный вариант: | ||
- | </s> | ||
- | Нет, это не нужно, потому что этих событий никто никогда не ждет! Это нужно только для варианта алгоритма с двумя parfor (по i и по j) – в нем есть еще один wait. | ||
- | Так что события здесь использованы корректно, но для такого варианта достаточно и семафоров. | ||
- | <s> | ||
<pre> | <pre> | ||
float A[ L1 ][ L2 ]; | float A[ L1 ][ L2 ]; | ||
- | struct | + | struct condition s[ L1 ][ L2 ]; |
for ( i = 0; i < L1; i++) // Цикл 1 | for ( i = 0; i < L1; i++) // Цикл 1 | ||
Строка 200: | Строка 228: | ||
{ post( s[ 0 ][ j ]) } | { post( s[ 0 ][ j ]) } | ||
- | for ( i = 0; i < L1; i++) | + | for ( i = 0; i < L1; i++) // Это надо вставить до начала |
- | + | post( s[ i ][ 0 ]) // основного цикла | |
parfor ( i = 1; i < L1-1; i++) // Цикл 3 | parfor ( i = 1; i < L1-1; i++) // Цикл 3 | ||
for ( j = 1; j < L2-1; j++) | for ( j = 1; j < L2-1; j++) | ||
{ | { | ||
- | wait( s[ i-1 ][ j ]); | + | wait( s[ i-1 ][ j ]); |
+ | wait( s[ i ][ j-1 ]); // <- здесь ждем значение в предыдущем столбце | ||
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; | ||
post( s[ i ][ j ]); | post( s[ i ][ j ]); | ||
} | } | ||
</pre> | </pre> | ||
- | + | ||
- | + | ||
<u>Оценка времени выполнения</u>: | <u>Оценка времени выполнения</u>: | ||
Строка 222: | Строка 250: | ||
** как можно видеть, преимущество возникает только на таких таких строках 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: | Строка 306: | ||
'''Ответ:''' | '''Ответ:''' | ||
- | Пусть никакой буферизации не предусмотрено. Для получения суммы на одном из четырёх центральных процессов ((1,1),(2,1),(1,2),(2,2)) необходимо 4 операции (2 операции для получения суммы своего угла из 4 процессов для каждого центрального процесса, ещё две, чтобы получить общую сумму на всех - | + | Пусть никакой буферизации не предусмотрено. Для получения суммы на одном из четырёх центральных процессов ((1,1),(2,1),(1,2),(2,2)) необходимо 4 операции (2 операции для получения суммы своего угла из 4 процессов для каждого центрального процесса, ещё две, чтобы получить общую сумму на всех - на каждом такте складываем сумму на транспьтере с соседями (к примеру, (1,1) с (2,1) и (1, 2). После этого на каждом из 4х транспьютеров получается удвоенная сумма, из которой получается просто сумма)). Затем нужно ещё 2 операции, чтобы разослать информацию во все углы. Итого: 6*(Ts+Tb). |
- | [[Изображение:4x4sum. | + | [[Изображение: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: | Строка 322: | ||
=== Задача 7 (передача сообщения) === | === Задача 7 (передача сообщения) === | ||
- | В транспьютерной матрице размером 4*4, в каждом узле которой находится один процесс, необходимо переслать очень длинное сообщение (длиной L байт) из узла с координатами (0,0) в узел с координатами (3,3) | + | В транспьютерной матрице размером 4*4, в каждом узле которой находится один процесс, необходимо переслать очень длинное сообщение (длиной L байт) из узла с координатами (0,0) в узел с координатами (3,3)? Сколько времени потребуется для этого. А сколько времени потребуется для пересылки из узла с координатами (1,1) в узел с координатами (2,2)? Время старта равно времени передачи байта (Ts=Tb). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми. |
'''Ответ:''' | '''Ответ:''' | ||
Строка 411: | Строка 395: | ||
'''Ответ:''' | '''Ответ:''' | ||
- | Маркер находится у процесса 0. Он спокойно входит в КС, а все остальные шлют broadcast запросы о | + | Маркер находится у процесса 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 номеров последних запросов. |