Распределённые операционные системы. Задачи и ответы. (esyr) (1158846), страница 3
Текст из файла (страница 3)
Сколько времени потребуется для этого? А сколько времени потребуется для пересылки из узла с координатами (1,1) в узел сopen in browser PRO versionAre you a developer? Try out the HTML to PDF APIpdfcrowd.comкоординатами (2,2)? Время старта равно времени передачи байта (Ts=Tb). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.Ответ:В задаче 3.2 был получен результат 6*(Ts+Tb*L/K)+(K-1)*(Ts+Tb*L/K).
При передаче из одного в угла другой можно получить то же время, деля это длинное сообщ ение на Kкусков. Кроме того, его можно распилить пополам и пустить двумя путями (больше не получится -- около углов узкое место), тогда время будет такое: 6*(Ts+Tb*L/(2K))+(K1)*(Ts+Tb*L/(2K)).С передачей из (1,1) в узел с координатами (2,2) немного сложнее. Строго говоря, там возможны 4 пути: два длины 2 и два длины 6. Пусть есть N - часть сообщ ения L, которуюмы пустим по коротким каналам. Тогда 0.5L < N < L из соображений здравого смысла, и будем N дробить на K1 частей, а (L-N) на K2 частей.
Тогда получаем формулу: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.Ответ (вариант 2):На консультации сказали, что если в задании есть слова очень длинное сообщение, то можно пренебречь временем старта, временем разгона конвейера и длиной маршрута.Таким образом, у нас остается только Tb. Тогда из (0,0) в (3,3) можно переслать сообщ ение за время L*Tb/2 (т.
к. возможно два маршрута), из (1,1) в (2,2) -- за время L*Tb/4 (т. к. вэтом случае 4 маршрута).Задача 8 (буферизуемая передача сообщения)[править]В транспьютерной матрице размером 4*4, в каждом узле которой находится один процесс, необходимо переслать сообщ ение длиной L байт из узла с координатами (0,0) в узел скоординатами (3,3).
Сколько времени потребуется для этого, если передача сообщ ений выполняется в буферизуемом режиме MPI? А сколько времени потребуется прииспользовании синхронного режима и режима готовности? Время старта равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Процессорные операции, включая чтение изпамяти и запись в память считаются бесконечно быстрыми.Ответ: Если все транспьютеры готовы к приёму, то ничем не отличается от предыдущ их задач (если хочется учитывать квитанции, надо добавлять, например, посылку-приёмбайта перед передачей содержательной информации).Задача 9 (блокирующая/неблокирующая передача сообщения)[править]В транспьютерной матрице размером 4*4, в каждом узле которой находится один процесс, необходимо переслать сообщ ение длиной L байт из узла с координатами (0,0) в узел скоординатами (3,3).
Сколько времени потребуется для этого при использовании а) неблокирующ их и б) блокирующ их операций MPI? Время старта равно 100, время передачибайта равно 1 (Ts=100,Tb=1). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.Ответ: Блокирующ ие и неблокирующ ие операции по времени ничем не должны отличаться. Поэтому решется аналогично задачам, описанным выше.Тема 4[править]Задача 1 (Круговой маркерный алгоритм)[править]1.
Все 16 процессов, находящ ихся в узлах транспьютерной матрицы размером 4*4, одновременно выдали запрос на вход в критическую секцию. Сколько времени потребуетсядля прохождения всеми критических секций, если используется круговой маркерный алгоритм. Время старта равно 100, время передачи байта равно 1 (Ts=100,Tb=1).Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.Ответ: Все процессы составляют логическое кольцо, когда каждый знает, кто следует за ним.
По кольцу циркулирует маркер, дающ ий право на вход в критическую секцию.Получив маркер (посредством сообщ ения точка-точка) процесс либо входит в критическую секцию (если он ждал разрешения) либо переправляет маркер дальше. После выходаиз критической секции маркер переправляется дальше, повторный вход в секцию при том же маркере не разрешается. 15*(Ts + 1*Tb)Задача 2 (Древовидный маркерный алгоритм)[править]2. Все 16 процессов, находящ ихся на разных ЭВМ сети с шинной организацией (без аппаратных возможностей широковещ ания), одновременно выдали запрос на вход вкритическую секцию. Сколько времени потребуется для прохождения всеми критических секций, если используется древовидный маркерный алгоритм.
Время старта (времяразгона после получения доступа к шине) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса (приодновременных запросах - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.open in browser PRO versionAre you a developer? Try out the HTML to PDF APIpdfcrowd.comОтвет:Составляем сбалансированное дерево, например, такое.
Где бы ни находился маркер, нужно 15 посылок запросов для инициализации (по каждому ребру либо в обну, либо вдругую сторону). Далее, надо, начиная с вершины, где есть маркер, обойти в глубину дерево. Кажется, что оптимально это можно сделать за 26 операций. В самом деле, начнёмобход из корня (0), и будем обходить сначала правые поддеревья, потом левые. Тогда по каждому ребру придётся пройти 2 раза (вперёд и назад), кроме последнихчетырёх(рёбра 0-1, 1-2, 2-3, 3-4), так как из вершины 4 маркер возвращ аться не будет (очередь пуста). Итого: (15+26)(Ts+1*Tb).Замечание: в приведенном выше решении, на мой взгляд, имеется ошибка - не учтены повторные посылки запроса после того, как маркер покидает вершину, в направленииушедшего маркера (они выполняются, если очередь запросов в узле не пуста).
Их количество считается вручную (мысленно проводим обход дерева и при каждом переходе вследующ ую вершину смотрим, остались ли ещ е запросы на только что покинутой). На приведенном выше рисунке, таким образом, строя обход в глубину справа налево, нужно кответу добавить 11*(Ts+1*Tb). Данное решение принято аспирантом на экзамене, кроме того, им было сделано замечание, что запрос может посылаться вместе с маркером водном сообщ ении, тогда удастся избежать лишних накладных расходов на инициацию передачи и к ответу добавится просто 11*Tb.Замечание2: А если начать обход не с 0 вершины, а с 15? тогда нам потребуется только 23 операции (т.к не придется дважды проходить 15-13, 13-9, 9-0)Задача 3 (Децентрализованный алгоритм с временными метками)[править]3.
Все 16 процессов, находящ ихся на разных ЭВМ сети с шинной организацией (без аппаратных возможностей широковещ ания), одновременно выдали запрос на вход вкритическую секцию. Сколько времени потребуется для прохождения всеми критических секций, если используется децентрализованный алгоритм с временными метками. Времястарта (время «разгона» после получения доступа к шине для передачи сообщ ения) равно 100, время передачи байта равно 1 (Ts=100,Tb=1).
Доступ к шине ЭВМ получаютпоследовательно в порядке выдачи запроса на передачу (при одновременных запросах - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти и запись впамять, считаются бесконечно быстрыми.Ответ:Каждый процесс шлет запрос на вход в критическую секцию всем остальным 15 процессам. Итого: 15*16*(Ts+Tb*L)После выполнения критической секции процесс смотрит свои запросы на вход в своем списке и шлет им Ok.В результате на посылку Ok уходит 15*16*(Ts+Tb*Lok)Итого: 15*16*(2Ts+Tb*(L+Lok))Задача 4 (Широковещательный маркерный алгоритм)[править]Все 16 процессов, находящ ихся на разных ЭВМ сети с шинной организацией (без аппаратных возможностей широковещ ания), одновременно выдали запрос на вход вкритическую секцию. Сколько времени потребуется для прохождения всеми критических секций, если используется широковещ ательный маркерный алгоритм (маркером владеетнулевой процесс).
Время старта равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Процессорные операции, включая чтение из памяти и запись в память, считаютсяopen in browser PRO versionAre you a developer? Try out the HTML to PDF APIpdfcrowd.comбесконечно быстрыми.Ответ:Маркер находится у процесса 0.
Он спокойно входит в КС, а все остальные шлют broadcast запросы о желнии войти в КС. Им нужно для этого 15*16 тактов, так как нет аппаратнойподдержки широковещ ания. После этого у маркера сформировалась очередь из 15 желающ их войти в КС, и он по очереди удовлетворяет их желания (на каждое нужна однапересылка маркера). Всего получается 15*16+15 тактов. Можно чередовать операции рассылки и передачи маркера, но их всё равно будет столько же. Ответ: 15*16*(Ts+Tb*Lreq)+ 15*(Ts+Tb*Lmark).Заметьте, что здесь Lmark довольно большая. В сообщ ение должны помещ аться очередь длины 1..15 и массив из 16 номеров последних запросов.Задача 5 (Централизованный алгоритм)[править]5.
15 процессов, находящ ихся в узлах транспьютерной матрицы размером 4*4, одновременно выдали запрос на вход в критическую секцию. Сколько времени потребуется дляпрохождения всеми критических секций, если используется централизованный алгоритм (координатор расположен в узле 0,0)? Время старта равно 100, время передачи байтаравно 1 (Ts=100,Tb=1). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.Ответ:Как известно, для обработки КС централизованным алгоритмом нужно 3 сообщ ения (запрос, разрешение, подтверждение окончания). Всего от всех процессов до (0,0) нужносовершить 48 переходов (2*1 + 3*2 + 4*3 + 3*4 + 2*5 + 6).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
