Редактирование: РОС, ответы на задачи
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
ПРЕДУПРЕЖДЕНИЕ: Длина этой страницы составляет 95 килобайт. Страницы, размер которых приближается к 32 КБ или превышает это значение, могут неверно отображаться в некоторых браузерах. Пожалуйста, рассмотрите вариант разбиения страницы на меньшие части.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 559: | Строка 559: | ||
PRAM консистентность памяти и алгоритм ее реализации в DSM с полным размножением. Сколько времени потребует 3-кратная модификация 10 различных переменных, если все 10 процессов (каждый процесс 3 раза модифицирует одну переменную), находящихся на разных ЭВМ сети с шинной организацией (без аппаратных возможностей широковещания), одновременно выдали запрос на модификацию. Время старта (время разгона после получения доступа к шине) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса (при одновременных запросах - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми. | PRAM консистентность памяти и алгоритм ее реализации в DSM с полным размножением. Сколько времени потребует 3-кратная модификация 10 различных переменных, если все 10 процессов (каждый процесс 3 раза модифицирует одну переменную), находящихся на разных ЭВМ сети с шинной организацией (без аппаратных возможностей широковещания), одновременно выдали запрос на модификацию. Время старта (время разгона после получения доступа к шине) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса (при одновременных запросах - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми. | ||
- | '''Ответ:''' Семантике PRAM консистентности больше соответствует алгоритм с координатором — при записи в переменную соответствующий процесс посылает изменение координатору, а сам продолжает работу. Тем не менее, поскольку записи одного процесса должны видеться всеми остальными процессами в одном порядке, придётся учитывать и время рассылки обновлений от координатора к остальным процессам. Итак, если процесс, изменяющий переменную, не совпадает с координатором, то при каждом изменении переменной потребуется <math>(T_s + T_b*l_1)</math> на отправку изменённого значения координатору и ещё <math>(N-2)*(T_s + T_b*l_2)</math> на рассылку нового значения остальным процессам от координатора (где N — число процессов; процессу, изначально изменившему переменную, и координатору не надо рассылать новое значение по шине). Если же процесс-модификатор переменной совпадает с координатором, то | + | '''Ответ:''' Семантике PRAM консистентности больше соответствует алгоритм с координатором — при записи в переменную соответствующий процесс посылает изменение координатору, а сам продолжает работу. Тем не менее, поскольку записи одного процесса должны видеться всеми остальными процессами в одном порядке, придётся учитывать и время рассылки обновлений от координатора к остальным процессам. Итак, если процесс, изменяющий переменную, не совпадает с координатором, то при каждом изменении переменной потребуется <math>(T_s + T_b*l_1)</math> на отправку изменённого значения координатору и ещё <math>(N-2)*(T_s + T_b*l_2)</math> на рассылку нового значения остальным процессам от координатора (где N — число процессов; процессу, изначально изменившему переменную, и координатору не надо рассылать новое значение по шине). Если же процесс-модификатор переменной совпадает с координатором, то (Ts + Tb*l1) уже не нужно, зато нужно <math>(N-1)*(T_s + T_b*l_2)</math> на рассылку. Ещё необходимо учесть, что каждый процесс меняет переменную трижды. Итого получается <math>3*(N-1)*\Bigl((T_s+T_b*l_1)+(N-2)*(T_s+T_b*l_2)\Bigr)+3*(N-1)*(T_s+T_b*l_2)</math>, т.е. <math>3*(N-1)*\Bigl((T_s+T_b*l_1)+(N-1)*(T_s+T_b*l_2)\Bigr)</math>. |
Алгоритм без координатора также возможен — в этом случае процессу-модификатору самому необходимо рассылать остальным N-1 процессам новые значения переменной после её модификации. Всего в этом случае потребуется <math>3*N*(N-1)*(T_s + T_b*l_2)</math>. | Алгоритм без координатора также возможен — в этом случае процессу-модификатору самому необходимо рассылать остальным N-1 процессам новые значения переменной после её модификации. Всего в этом случае потребуется <math>3*N*(N-1)*(T_s + T_b*l_2)</math>. |