(2016) Ответы (1162879), страница 3
Текст из файла (страница 3)
Сколько времени потребуется для прохождениявсеми критических секций, если используется древовидный маркерныйалгоритм (маркером владеет нулевой процесс). Время старта (время «разгона»после получения доступа к шине для передачи сообщения) равно 100, времяпередачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получаютпоследовательно в порядке выдачи запроса на передачу (при одновременныхзапросах – в порядке номеров ЭВМ). Процессорные операции, включая чтение изпамяти и запись в память, считаются бесконечно быстрыми.Решение для 18 процессов (число не имеет значения). Сначала будет 18инициализирующих посылок Request.Далее с 0-го процесса идет рассылка маркера. Главное правило: если в очередипроцесса остаётся один последний запрос, то соответствующему процессу посылаетсятолько Marker.
Иначе по первому в очереди запросу отправляется Marker+Request.MR – Marker + Request.M – Marker.R – Request.0—MR—1—MR—2—MR—3—MR—4—M—3—MR—5—M—3—M—2—MR—6—MR—7—M—6—M—2—M—1—MR—8—MR—9—M—8—MR—10—M—8—M—1—M—0—M—11—MR—12—MR—13—M—12—MR—14—M—12—M—11—M—15—MR—16—M—15—M—17.Получили 17R + 14MR + 17M сообщений. Пусть Маркер и Запрос занимают по 1байту. Маркер+Запрос занимает 2 байта.Ответ: T = 17*(Ts+Tb*SIZER) + 14*(Ts+Tb*SIZEMR) + 17*(Ts+Tb*SIZEM) = 48*Ts +34*1 + 14*2 = 4800 + 62 = 4862.2.Все 16 процессов, находящихся на разных ЭВМ сети с шинной организацией (безаппаратных возможностей широковещания), одновременно выдали запрос навход в критическую секцию.
Сколько времени потребуется для прохождениявсеми критических секций, если используется децентрализованный алгоритм свременными метками. Время старта (время «разгона» после получения доступак шине для передачи сообщения) равно 100, время передачи байта равно 1(Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачизапроса на передачу (при одновременных запросах – в порядке номеров ЭВМ).Процессорные операции, включая чтение из памяти и запись в память,считаются бесконечно быстрыми.Рассмотрим каждый процесс отдельно.
Он должен послать 15 запросов и получить 15подтверждений.В сообщении-запросе содержится номер КС, номер процесса, и текущее время.Отведем по 1 байту каждому, получим размер сообщения – 3 байта. Пусть «ОК» занимает1 байт.Перед заходом в КС процесс должен всем отправить запрос и от всех получить «ОК».Время одного прохождения КС Т1 = 15*(Ts+3*Tb) + 15* (Ts+1*Tb).Количество КС = 16.Общее время Т = 16*Т1.3.Все 16 процессов, находящихся на разных ЭВМ сети с шинной организацией (безаппаратных возможностей широковещания), одновременно выдали запрос навход в критическую секцию.
Сколько времени потребуется для прохождениявсеми критических секций, если используется широковещательный маркерныйалгоритм (маркером владеет нулевой процесс). Время старта равно 100, времяпередачи байта равно 1 (Ts=100,Tb=1). Процессорные операции, включая чтениеиз памяти и запись в память, считаются бесконечно быстрыми.Предположим, что используется режим с блокировкой процессов.
То есть сообщениене может прийти, если не доставлены ранее отправленные.Маркер у процесса 0 – он входит в критическую секцию.Все, кроме 0-го пошлют широковещательные запросы. Это займет время15*15*(Ts+Lзапроса*Tb).После этого будет передаваться только маркер, содержащий очередь запросов. Всегобудет 15 передач. Каждая за время Ts+Lмаркера*Tb.Итого 225*(Ts+Lзапроса*Tb)+15*(Ts+Lмаркера*Tb).Замечание. Нельзя отбросить Lмаркера, так как он содержит очередь запросов иможет быть достаточно большим (как минимум сравним с Ts).4.15 процессов, находящихся в узлах транспьютерной матрицы размером 4*4,одновременно выдали запрос на вход в критическую секцию. Сколько временипотребуется для прохождения всеми критических секций, если используетсяцентрализованный алгоритм (координатор расположен в узле 0,0)? Время стартаравно 100, время передачи байта равно 1 (Ts=100,Tb=1).
Процессорные операции,включая чтение из памяти и запись в память, считаются бесконечно быстрыми.Как известно, для обработки КС централизованным алгоритмом нужно 3 сообщения(запрос, разрешение, подтверждение окончания).Если считать, что очередь запросов уже сформирована, то с каждым процессом укоординатора происходит обмен двумя сообщениями.Мысленно пронумеруем диагонали (белый – координатор на первой диагонали).Для каждого из 2 процессов на 2 диагонали требуется 1 передача для связи скоординатором, запоминаем 2*1 = 2;для каждого из 3 процессов на 3 диагонали – 2 передачи: 3*2 = 6;4 процесса на 4 диагонали – 3 передачи: 4*3 = 12;3 процесса на 5 диагонали – 4 передачи: 3*4 = 12;2 процесса на 6 диагонали – 5 передач: 2*5 = 10;1 процесс на 7 диагонали – 6 передач: 1*6 = 6.2 + 6 + 12 + 12 + 10 + 6 = 48.Итого потребуется 2*48 = 96 сообщенийПусть размер одного сообщения 1 байт (т.к.
содержится только разрешение).Тогда ответ Т = 96*(Ts+1*Tb).Если очередь запросов не сформирована, то можно считать, что запросы приходятпоследовательно, тогда 48 умножится не на 2, а на 3 сообщения (каждый процессотправит запрос, получит разрешение, отправит подтверждение окончания).В этом случае ответ 3*48*(Ts+1*Tb).Можно считать, что запросы координатор собирает параллельно. Тогда время сборазапросов можно считать равным времени работы команды MPI_GATHER. Далее попервому пункту.5.Сколько времени потребует выбор координатора среди 16 процессов,находящихся на разных ЭВМ сети с шинной организацией (без аппаратныхвозможностей широковещания), если используется алгоритм «задиры»?«Задира» расположен в узле с координатами (0,0) и имеет уникальный номер 0.Время старта (время «разгона» после получения доступа к шине для передачисообщения) равно 100, время передачи байта равно 1 (Ts=100,Tb=1).
Доступ кшине ЭВМ получают последовательно в порядке выдачи запроса на передачу(при одновременных запросах – в порядке номеров ЭВМ). Процессорныеоперации, включая чтение из памяти и запись в память, считаются бесконечнобыстрыми.В алгоритме «задиры» не определяется, в каком порядке процесс, инициирующийвыборы, рассылает сообщение «ВЫБОРЫ».
Говорится, что он посылает сообщение всемпроцессам с большими чем у него номерами.В случае, если задира (процесс с наименьшим номером) начнёт рассылку сообщенияВЫБОРЫ в порядке возрастания номеров процессов, то он пошлет сообщениеВЫБОРЫ всем остальным процессам и получит от всех ответ ОК.
После этого всеостальные процессы будут инициировать выборы (предположим, что по той же схеме повозрастанию номеров), рассылая сообщения процессам с бóльшими номерами и получаяответы. Процесс же с наибольшим номером (15) разошлет всем сообщенияКООРДИНАТОР, тем самым закончив выборы. Итого: (1 + 2 + ... + 15)*(Ts + Tb *Lвыборы) + (1 + 2 + ... + 15)*(Ts + Tb * Lок) + 15*(Ts + Tb * Lкоординатор).В случае, если задира сразу выберет процесс с наибольшим номером, он отправитему сообщение ВЫБОРЫ, получит ОК, на этом выборы завершаются, процесс с номером15 рассылает 15 сообщений КООРДИНАТОР.Итого: (Ts + Tb * Lвыборы) + (Ts + Tb * Lок) + 15*(Ts + Tb * Lкоординатор).6.Сколько времени потребует выбор координатора среди 16 процессов,находящихся в узлах транспьютерной матрицы размером 4*4, если используетсякруговой алгоритм? Время старта равно 100, время передачи байта равно 1(Ts=100,Tb=1).
Процессорные операции, включая чтение из памяти и запись впамять считаются бесконечно быстрыми.Алгоритм основан на использовании кольца (физического или логического). Каждыйпроцесс знает следующего за ним в круговом списке. Когда процесс обнаруживаетотсутствие координатора, он посылает следующему за ним процессу сообщение«ВЫБОРЫ» со своим номером. Если следующий процесс не отвечает, то сообщениепосылается процессу, следующему за ним, и т.д., пока не найдется работающий процесс.Каждый работающий процесс добавляет в список работающих свой номер иперенаправляет сообщение дальше по кругу. Когда процесс обнаружит в списке свойсобственный номер (круг пройден), он меняет тип сообщения на «КООРДИНАТОР» и онопроходит по кругу, извещая всех о списке работающих и координаторе (процессе снаибольшим номером в списке). После прохождения круга сообщение удаляется.Пусть кольцо имеет следующий вид.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
