Редактирование: РОС, ответы на задачи
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
ПРЕДУПРЕЖДЕНИЕ: Длина этой страницы составляет 94 килобайт. Страницы, размер которых приближается к 32 КБ или превышает это значение, могут неверно отображаться в некоторых браузерах. Пожалуйста, рассмотрите вариант разбиения страницы на меньшие части.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 148: | Строка 148: | ||
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 | ||
Строка 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; | ||
- | + | Нет, события использованы неправильно, так как забыли назначить посчитанным первый столбец: | |
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 | + | struct condition s[ L1 ][ L2 ]; |
for ( i = 0; i < L1; i++) // Цикл 1 | for ( i = 0; i < L1; i++) // Цикл 1 | ||
Строка 211: | Строка 207: | ||
} | } | ||
</pre> | </pre> | ||
- | + | ||
Причем, wait( s[ i ][ j-1 ]); делать во внутреннем цикле "Цикл 3" не нужно, так как внутри мы имеем for, а не parfor - это отличие данного алгоритма от алгоритма в лекциях. | Причем, wait( s[ i ][ j-1 ]); делать во внутреннем цикле "Цикл 3" не нужно, так как внутри мы имеем for, а не parfor - это отличие данного алгоритма от алгоритма в лекциях. | ||
Строка 233: | Строка 229: | ||
<pre> | <pre> | ||
- | semaphore sem_r | + | semaphore sem_r, sem_w; |
int readers_count = 0; | int readers_count = 0; | ||
r_enter() { // Читатель хочет начать читать | r_enter() { // Читатель хочет начать читать | ||
sem_r.P(); | sem_r.P(); | ||
- | sem_ra.P(); | ||
++readers_count; | ++readers_count; | ||
if (readers_count == 1) | if (readers_count == 1) | ||
sem_w.P(); // Первый читатель блокирует возможность писать | sem_w.P(); // Первый читатель блокирует возможность писать | ||
- | sem_ra.V(); | ||
sem_r.V(); | sem_r.V(); | ||
} | } | ||
r_leave() { // Читатель выходит из области чтения | r_leave() { // Читатель выходит из области чтения | ||
- | sem_ra.P(); | ||
--readers_count; | --readers_count; | ||
if (readers_count == 0) | if (readers_count == 0) | ||
sem_w.V(); // Последний читатель освобождает семафор | sem_w.V(); // Последний читатель освобождает семафор | ||
- | sem_ra.V(); | ||
} | } | ||
Строка 266: | Строка 258: | ||
</pre> | </pre> | ||
+ | |||
+ | Можно добавить ещё семафор для защиты перемнной readers_count в случае если операции инкремента/декремента не атомарны. | ||
== Тема 3 == | == Тема 3 == | ||
Строка 322: | Строка 316: | ||
'''Ответ:''' | '''Ответ:''' | ||
- | Пусть никакой буферизации не предусмотрено. Для получения суммы на одном из четырёх центральных процессов ((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). | ||
Строка 411: | Строка 405: | ||
'''Ответ:''' | '''Ответ:''' | ||
- | Маркер находится у процесса 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 номеров последних запросов. |