Редактирование: РОС, ответы на задачи
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
ПРЕДУПРЕЖДЕНИЕ: Длина этой страницы составляет 71 килобайт. Страницы, размер которых приближается к 32 КБ или превышает это значение, могут неверно отображаться в некоторых браузерах. Пожалуйста, рассмотрите вариант разбиения страницы на меньшие части.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 12: | Строка 12: | ||
Видимо, при отсутствии таких механизмов, необходимо воспользоваться паравиртуализацией (эмуляция аппаратных средств + гипервизор (ОС)). | Видимо, при отсутствии таких механизмов, необходимо воспользоваться паравиртуализацией (эмуляция аппаратных средств + гипервизор (ОС)). | ||
- | Защита памяти --- защита оперативной памяти. Привилегированный режим необходим для защиты внешней памяти | + | Защита памяти --- защита оперативной памяти. Привилегированный режим необходим для защиты внешней памяти. |
== Тема 2 == | == Тема 2 == | ||
Строка 18: | Строка 18: | ||
=== Задача 1 (Деккер) === | === Задача 1 (Деккер) === | ||
Если в алгоритме Деккера ([http://en.wikipedia.org/wiki/Dekker%27s_algorithm enwiki]) не изменять значение переменной turn при выходе из критической секции, то каким требованиям он перестанет удовлетворять? Объясните, почему. | Если в алгоритме Деккера ([http://en.wikipedia.org/wiki/Dekker%27s_algorithm enwiki]) не изменять значение переменной turn при выходе из критической секции, то каким требованиям он перестанет удовлетворять? Объясните, почему. | ||
- | |||
- | 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 | ||
- | |||
'''Ответ:''' | '''Ответ:''' | ||
Строка 48: | Строка 26: | ||
Имеется механизм двоичных семафоров. Опираясь на него, реализуйте 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: | Строка 70: | ||
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: | Строка 144: | ||
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: | Строка 173: | ||
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 ]) } | ||
- | + | IMHO, описанный выше алгоритм работает верно. Распараллеливание происходит только по внешнему циклу (по i), и каждая из нитей дожидается, пока будет пересчитан элемент, располагающийся НАД A[ i ][ j ]. | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
<u>Оценка времени выполнения</u>: | <u>Оценка времени выполнения</u>: | ||
Строка 220: | Строка 183: | ||
** каждый процессор (кроме последнего) получает для обработки <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. | + | ** как можно видеть, преимущество возникает только на таких таких строках m, что: m-я строка распределена k-й нити, а строка m+1 - нити с номером k+1. В каждом таком случае мы получаем преимущество по времени равное <math>(L2-3)</math>. Всего таких номеров m ровно N-1. Суммарные выигрыш получается равным <math>N*(L2-3)</math> |
- | ** итого, время параллельного выполнения составляет ''' <math>(L1-2) * (L2-2) - | + | ** итого, время параллельного выполнения составляет ''' <math>(L1-2) * (L2-2) - N*(L2-3) </math>''' |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
== Тема 3 == | == Тема 3 == | ||
Строка 322: | Строка 241: | ||
'''Ответ:''' | '''Ответ:''' | ||
- | Пусть никакой буферизации не предусмотрено. Для получения суммы на одном из четырёх центральных процессов ((1,1),(2,1),(1,2),(2,2)) необходимо 4 операции (2 операции для получения суммы своего угла из 4 процессов для каждого центрального процесса, ещё две, чтобы получить общую сумму | + | Пусть никакой буферизации не предусмотрено. Для получения суммы на одном из четырёх центральных процессов ((1,1),(2,1),(1,2),(2,2)) необходимо 4 операции (2 операции для получения суммы своего угла из 4 процессов для каждого центрального процесса, ещё две, чтобы получить общую сумму). Затем нужно ещё 4 операции, чтобы разослать информацию во все углы. Итого: 8*(Ts+Tb). |
- | + | Если процессов 64, то разобьём квадрат на 4 подквадрата. Как было показано ранее, за 4 операции пожно получить сумму своего квадрата в (2,2), (5,2), (2,5) и (5,5). Ещё две операции нужно на пересылку в центральные процессы. Там за 2 операции получаем сумму на одном из них, и ещё 8 на рассылку. Итого: 16*(Ts+Tb). | |
- | + | ||
- | Если процессов 64, то разобьём квадрат на 4 подквадрата. Как было показано ранее, за 4 операции пожно получить сумму своего квадрата в (2,2), (5,2), (2,5) и (5,5). Ещё две операции нужно на пересылку в центральные процессы. Там за 2 операции получаем сумму на | + | |
=== Задача 6 (максимум) === | === Задача 6 (максимум) === | ||
Строка 338: | Строка 255: | ||
=== Задача 7 (передача сообщения) === | === Задача 7 (передача сообщения) === | ||
- | В транспьютерной матрице размером 4*4, в каждом узле которой находится один процесс, необходимо переслать очень длинное сообщение (длиной L байт) из узла с координатами (0,0) в узел с координатами (3,3) | + | В транспьютерной матрице размером 4*4, в каждом узле которой находится один процесс, необходимо переслать очень длинное сообщение (длиной L байт) из узла с координатами (0,0) в узел с координатами (3,3)? Сколько времени потребуется для этого. А сколько времени потребуется для пересылки из узла с координатами (1,1) в узел с координатами (2,2)? Время старта равно времени передачи байта (Ts=Tb). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми. |
'''Ответ:''' | '''Ответ:''' | ||
Строка 347: | Строка 264: | ||
: max{ 2*(Ts+Tb*N/(2K1))+(K1-1)*(Ts+Tb*N/(2K1)), 6*(Ts+Tb*(L-N)/(2K2))+(K2-1)*(Ts+Tb*(L-N)/(2K2)) }. | : max{ 2*(Ts+Tb*N/(2K1))+(K1-1)*(Ts+Tb*N/(2K1)), 6*(Ts+Tb*(L-N)/(2K2))+(K2-1)*(Ts+Tb*(L-N)/(2K2)) }. | ||
И эту жесть надо минимизировать по N, K1, K2. | И эту жесть надо минимизировать по N, K1, K2. | ||
- | |||
- | '''Ответ (вариант 2):''' | ||
- | |||
- | На консультации сказали, что если в задании есть слова ''очень длинное сообщение'', то можно пренебречь временем старта, временем разгона конвейера и длиной маршрута. Таким образом, у нас остается только Tb. Тогда из (0,0) в (3,3) можно переслать сообщение за время L*Tb/2 (т. к. возможно два маршрута), из (1,1) в (2,2) -- за время L*Tb/4 (т. к. в этом случае 4 маршрута). | ||
=== Задача 8 (буферизуемая передача сообщения) === | === Задача 8 (буферизуемая передача сообщения) === | ||
Строка 357: | Строка 270: | ||
'''Ответ:''' | '''Ответ:''' | ||
- | Если все транспьютеры готовы к приёму, то ничем не отличается от предыдущих задач (если хочется учитывать квитанции, надо добавлять, например, посылку-приём байта перед передачей содержательной информации). | ||
=== Задача 9 (блокирующая/неблокирующая передача сообщения) === | === Задача 9 (блокирующая/неблокирующая передача сообщения) === | ||
Строка 364: | Строка 276: | ||
'''Ответ:''' | '''Ответ:''' | ||
- | Блокирующие и неблокирующие операции по времени ничем не должны отличаться. Поэтому решется аналогично задачам, описанным выше. | ||
== Тема 4 == | == Тема 4 == | ||
Строка 386: | Строка 297: | ||
[[Изображение:Derevo.JPG]] | [[Изображение:Derevo.JPG]] | ||
- | Составляем сбалансированное дерево, например, такое. Где бы ни находился маркер, нужно 15 посылок запросов для инициализации (по каждому ребру либо в обну, либо в другую сторону). Далее, надо, начиная с вершины, где есть маркер, обойти в глубину дерево. Кажется, что оптимально это можно сделать за 26 операций. В самом деле, начнём обход из корня (0), и будем обходить сначала правые поддеревья, потом левые. Тогда по каждому ребру придётся пройти 2 раза (вперёд и назад), кроме последних четырёх | + | Составляем сбалансированное дерево, например, такое. Где бы ни находился маркер, нужно 15 посылок запросов для инициализации (по каждому ребру либо в обну, либо в другую сторону). Далее, надо, начиная с вершины, где есть маркер, обойти в глубину дерево. Кажется, что оптимально это можно сделать за 26 операций. В самом деле, начнём обход из корня (0), и будем обходить сначала правые поддеревья, потом левые. Тогда по каждому ребру придётся пройти 2 раза (вперёд и назад), кроме последних четырёх, так как из вершины 4 маркер возвращаться не будет (очередь пуста). Итого: (15+26)(Ts+1*Tb). |
- | + | ===Задача 3 (Децентрализованный алгоритм с маркерными метками)=== | |
- | + | 3. [Updated] Все 16 процессов, находящихся на разных ЭВМ сети с шинной организацией (без аппаратных возможностей широковещания), одновременно выдали запрос на вход в критическую секцию. Сколько времени потребуется для прохождения всеми критических секций, если используется децентрализованный алгоритм с временными метками. Время старта (время «разгона» после получения доступа к шине для передачи сообщения) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса на передачу (при одновременных запросах - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти и запись в память, считаются бесконечно быстрыми. | |
- | + | ||
- | + | ||
- | ===Задача 3 (Децентрализованный алгоритм с | + | |
- | 3. Все 16 процессов, находящихся на разных ЭВМ сети с шинной организацией (без аппаратных возможностей широковещания), одновременно выдали запрос на вход в критическую секцию. Сколько времени потребуется для прохождения всеми критических секций, если используется децентрализованный алгоритм с временными метками. Время старта (время «разгона» после получения доступа к шине для передачи сообщения) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса на передачу (при одновременных запросах - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти и запись в память, считаются бесконечно быстрыми. | + | |
'''Ответ:''' | '''Ответ:''' | ||
Строка 407: | Строка 314: | ||
===Задача 4 (Широковещательный маркерный алгоритм)=== | ===Задача 4 (Широковещательный маркерный алгоритм)=== | ||
- | Все 16 процессов, находящихся на разных ЭВМ сети с шинной организацией (без аппаратных возможностей широковещания), одновременно выдали запрос на вход в критическую секцию. Сколько времени потребуется для прохождения всеми критических секций, если используется широковещательный маркерный алгоритм (маркером владеет нулевой процесс). Время старта равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Процессорные операции, включая чтение из памяти и запись в память, считаются бесконечно быстрыми. | + | [Updated] Все 16 процессов, находящихся на разных ЭВМ сети с шинной организацией (без аппаратных возможностей широковещания), одновременно выдали запрос на вход в критическую секцию. Сколько времени потребуется для прохождения всеми критических секций, если используется широковещательный маркерный алгоритм (маркером владеет нулевой процесс). Время старта равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Процессорные операции, включая чтение из памяти и запись в память, считаются бесконечно быстрыми. |
'''Ответ:''' | '''Ответ:''' | ||
- | Маркер находится у процесса 0. Он спокойно входит в КС, а все остальные шлют broadcast запросы о | + | Маркер находится у процесса 0. Он спокойно входит в КС, а все остальные шлют broadcast запросы о желнии войти в КС. Им нужно для этого 15 тактов. После этого у маркера сформировалась очередь из 15 желающих войти в КС, и он по очереди удовлетворяет их желания (на каждое нужна одна пересылка маркера). Всего получается 30 тактов шины. Можно чередовать операции рассылки и передачи маркера, но их всё равно будет 30. Ответ: 30*(Ts+Tb*L). |
- | Заметьте, что здесь | + | Заметьте, что здесь L довольно большая. В сообщение должны помещаться очередь длины 1..15 и массив из 16 номеров последних запросов. |
===Задача 5 (Централизованный алгоритм)=== | ===Задача 5 (Централизованный алгоритм)=== | ||
Строка 420: | Строка 327: | ||
'''Ответ:''' | '''Ответ:''' | ||
- | Как известно, для обработки КС централизованным алгоритмом нужно 3 сообщения (запрос, разрешение, подтверждение окончания). Всего | + | Как известно, для обработки КС централизованным алгоритмом нужно 3 сообщения (запрос, разрешение, подтверждение окончания). Всего переходов между парами узлов нужно совершить 42. Значит, всего потратим времени 3*42*(Ts+Tb). |
- | + | ||
- | + | ||
- | + | ||
===Задача 6 (Алгоритм задиры)=== | ===Задача 6 (Алгоритм задиры)=== | ||
- | 6. Сколько времени потребует выбор координатора среди 16 процессов, находящихся | + | 6. Сколько времени потребует выбор координатора среди 16 процессов, находящихся в узлах транспьютерной матрицы размером 4*4, если используется алгоритм задиры? Время старта равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми. Задира расположен в узле с координатами (0,0) и имеет уникальный номер 0. |
'''Ответ:''' | '''Ответ:''' | ||
- | Так как задирой является процесс с наименьшим номером, то он пошлет сообщение ВЫБОРЫ всем остальным процессам и получит от всех ответ ОК. После этого все остальные процессы будут инициировать выборы, рассылая сообщения процессам с бОльшими номерами и получая ответы. Процесс же с наибольшмим номером (15) разошлет всем сообщения КООРДИНАТОР, тем самым закончив выборы. | ||
- | Итого: (1 + 2 + ... + 15)(Ts + Tb * Lvybory) + (1 + 2 + ... + 15)(Ts + Tb * Lok) + 15(Ts + Tb * Lcoordinator) = | ||
- | 120(2Ts + Tb(Lvybory + Lok)) + 15(Ts + Tb * Lcoordinator) | ||
===Задача 7 (Круговой алгоритм)=== | ===Задача 7 (Круговой алгоритм)=== | ||
Строка 437: | Строка 338: | ||
'''Ответ:''' | '''Ответ:''' | ||
- | |||
- | Инициатор посылает сообщение ВЫБОРЫ со своим номером следующему по кругу. Следующий живой процесс добавляет свой номер и посылает дальше. Так, пока не будет пройден круг (процесс увидел в сообщении свой номер). Тогда он выбирает максимальный номер и посылает сообщение КООРДИНАТОР с этим номером, оповещая о новом координаторе. Всего получается два круга сообщений. Итого: 16*(Ts + Tb*Lvibory) + 16*(Ts + Tb*Lcoordinator). | ||
== Тема 5 == | == Тема 5 == | ||
Строка 532: | Строка 431: | ||
# Метод голосования. Идея - запрашивать чтение и запись файла у многих серверов (запись - у всех!). Запрос может получить одобрение у половины серверов плюс один. При этом должно быть согласие относительно номера текущей версии файла. Этот номер увеличивается на единицу с каждой коррекцией файла. Можно использовать различные значения для кворума чтения (Nr) и кворума записи (Nw). При этом должно выполняться соотношение Nr+Nw>N. Поскольку чтение является более частой операцией, то естественно взять Nr=1. Однако в этом случае для кворума записи потребуются все серверы. | # Метод голосования. Идея - запрашивать чтение и запись файла у многих серверов (запись - у всех!). Запрос может получить одобрение у половины серверов плюс один. При этом должно быть согласие относительно номера текущей версии файла. Этот номер увеличивается на единицу с каждой коррекцией файла. Можно использовать различные значения для кворума чтения (Nr) и кворума записи (Nw). При этом должно выполняться соотношение Nr+Nw>N. Поскольку чтение является более частой операцией, то естественно взять Nr=1. Однако в этом случае для кворума записи потребуются все серверы. | ||
- | == Тема 6 | + | == Тема 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). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса (при одновременных запросах - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми. | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | Консистентность памяти по входу и алгоритм ее реализации в DSM с полным размножением. Сколько времени потребует трехкратное выполнение критической секции и модификация в ней | + | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
'''Ответ:''' | '''Ответ:''' | ||
Строка 622: | Строка 477: | ||
'''Ответ:''' | '''Ответ:''' | ||
- | 2. Консистентное | + | 2. Консистентное множество контрольных точек и алгоритмы их фиксации. Дайте оценку накладных расходов на синхронную фиксацию консистентного множества контрольных точек для сети из 10 ЭВМ с шинной организацией (без аппаратных возможностей широковещания). Время старта (время разгона после получения доступа к шине для передачи) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса (при одновременных запросах - в порядке номеров ЭВМ). Операции с файлами и процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми. |
'''Ответ:''' | '''Ответ:''' | ||
- | + | Идея - нужно придумать протокол при котором известно сколько сообщений должен получить и отправить каждый процесс к какому-то моменту. После чего уже можно строить контрольные точки - будем уверены, что сообщений в канале не будет. | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + 11*(Ts + Tb * L_coord) // фиксация множества | ||
3. Протоколы голосования. Алгоритмы и применение. Дайте оценку времени выполнения одним процессом 2-х операций записи и 10 операций чтения одного байта информации с файлом, размноженным на остальных 10 ЭВМ сети с шинной организацией (без аппаратных возможностей широковещания). Определите оптимальные значения кворума чтения и кворума записи. Время старта (время разгона после получения доступа к шине для передачи) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса (при одновременных запросах - в порядке номеров ЭВМ). Операции с файлами и процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми. | 3. Протоколы голосования. Алгоритмы и применение. Дайте оценку времени выполнения одним процессом 2-х операций записи и 10 операций чтения одного байта информации с файлом, размноженным на остальных 10 ЭВМ сети с шинной организацией (без аппаратных возможностей широковещания). Определите оптимальные значения кворума чтения и кворума записи. Время старта (время разгона после получения доступа к шине для передачи) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса (при одновременных запросах - в порядке номеров ЭВМ). Операции с файлами и процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми. | ||
Строка 779: | Строка 621: | ||
* [http://jakob.engbloms.se/archives/65 Алгоритм Деккера и модели консистентности памяти] | * [http://jakob.engbloms.se/archives/65 Алгоритм Деккера и модели консистентности памяти] | ||
* [http://ilya-evseev.narod.ru/articles/mpi/ мануал по MPI] | * [http://ilya-evseev.narod.ru/articles/mpi/ мануал по MPI] | ||
- | |||
- | {{Курс РОС}} |