Решённые задачи к экзамену (1162834), страница 3
Текст из файла (страница 3)
Первые 15*(Ts + 1 * Tb) тактов будутотправляться ЗАПРОСы от устройств 2-16. На рисунках же обозначена последовательность получения доступа кшине следующая: 2-е, 1-е, 3-е и т.д. устройства.Другой вопрос заключается в том, что последним устройством на 4-м уровне дерева будет 15-е устройство.
Тогдакуда ни присоединишь 16-е, дерево будет не сбалансированным.] - [ Про нулевой момент - можно поспорить. Ведьу нас все бесконечно быстрое, кроме передач по сети, а шину получает процесс с меньшим номером. Значит, пока1-ому есть, что передавать, он будет передавать. По-моему это самая простая из допустимых интерпретация, т.к. вдругих случаях получаем взрыв мозга :) А про дерево - куда бы ни присоединить 16-ый - оно будетсбалансированным.
У сбалансированного дерева нижний уровень не должен быть до конца заполнен. ]3. Все 16 процессов, находящихся в узлах транспьютерной матрицы размером 4*4, одновременно выдали запрос навход в критическую секцию. Сколько времени потребуется для прохождения всеми критических секций, еслииспользуется децентрализованный алгоритм с временными метками. Время старта равно 100, время передачибайта равно 1 (Ts=100,Tb=1). Процессорные операции, включая чтение из памяти и запись в память считаютсябесконечно быстрыми.Решение.Вообще, для случая равных временных меток в алгоритме ничего не сказано (он зависает), даже наВикипедии. Поэтому доопределим его сами, например при равных временных метках выигравает процесс сменьшим номером. Также не будем учитывать размера ОК и ЗАПРОСа в байтах.Предположим, что процессы за один сеанс передачи могут передать все скопившиеся у них сообщения в даннуюсторону.
Тогда первому процессу для получения согласия от всех потребуется ждать 12 шагов (время отзывасамого дальнего процесса, 6 передач ЗАПРОСа и 6 передач ОК). За это время все успеют все передать и останутся14стоять в очередях лишь отложенные запросы. Поэтому когда 1-ый выполнит КС, то он передаст ОК за 1 шаг.Далее по аналогии, можно дать номера вершинам таким образом (змейкой), что ОК будет передаваться все времяна расстояние 1. Итого - 15 передач ЩЛ, 15 * Ts.Ответ: 15 * Ts + 12 * Ts[Временная метка и маркер - это совершенно разные понятия.Алгоритм временных меток:1. Рассылка всем процессам сообщение-запрос о входе в КС.2. Ожидание приема подтверждений.Порядок входа в КС (змейкой или не змейкой) здесь абсолютно не важен. Временная метка -- это просто локальноевремя.Оно есть на каждом устройстве. Поэтому выражение "отдаст метку" лишено всякого смысла.]- [ Спасибо, исправил.
Про порядок - не совсем, в этом алгоритме используется глобальное время (см. лекции).Поэтому с учетом доопределения алгоритма он важен. ]4. Все 16 процессов, находящихся в узлах транспьютерной матрицы размером 4*4, одновременно выдали запрос навход в критическую секцию. Сколько времени потребуется для прохождения всеми критических секций, еслииспользуется широковещательный маркерный алгоритм.
Время старта равно 100, время передачи байта равно 1(Ts=100,Tb=1). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечнобыстрыми.Решение. Время работы зависит от того, в каком порядке запросы будут занесены в очередь, которая находится всамом маркере. При обычной (слева-направо, сверху-вниз) нумерации процессов и нахождении маркераизначально в 1-ом процессе, запросы будут внесены в маркер практически по возрастанию (вроде бы).Предположим, что это действительно так.
Тогда маркер будет переходить по матрице в порядке номеров вершин.Пусть длинна маркера в битах - А, тогда проход маркера по всем вершинам займет 1 + 1 + 1 + 4 (3 перехода поверхней строке + один переход на новую строчку) - так 3 раза + еще 3 перехода, итого - 24 перехода. Время - 24 *( Ts + A * Tb ). Размер маркера может быть около 16 (список номеров запросов) + 16 (очередь запросов) байт.Плюс время передачи запроса от 2-го к 1-му (в самом начале, B - размер запроса).Ответ: 24 * ( Ts + A * Tb) + 1 * ( Ts + B * Tb )[В ответе не учтены отправки широковещательных сообщений «ЗАПРОС»:Вход в критическую секцию1) Если процесс Pk, запрашивающий критическую секцию, не имеет маркера, то он увеличиваетпорядковый номер своих запросов RNk[k] и посылает широковещательно сообщение «ЗАПРОС»,содержащее номер процесса (k) и номер запроса (Sn = RNk[k]).] - [ Вроде теперь учтены ]5.
15 процессов, находящихся в узлах транспьютерной матрицы размером 4*4, одновременно выдали запрос навход в критическую секцию. Сколько времени потребуется для прохождения всеми критических секций, еслииспользуется централизованный алгоритм (координатор расположен в узле 0,0)? Время старта равно 100, времяпередачи байта равно 1 (Ts=100,Tb=1). Процессорные операции, включая чтение из памяти и запись в памятьсчитаются бесконечно быстрыми.15Решение.Пусть для одновременно пришедших запросов координатор отдает предпочтение процессу с меньшимномером, и все запросы ставит в очередь.
Тогда 2 процесс начнет выполняться уже через 1 (запрос) + 1(разрешение) передачи сообщений, 3-ий - через 1 (2-ой сказал К что закончил) + 2 (К разрешил 3-ему работать), ит.д.В общем виде - путь от предыдущего узла до Координатора + путь от координатора до текущего узла. В итогеимеем:[ 0 + 1+1 + 1+2 + 2+3 ] +[ 3+1 + 1+2 + 2+3 + 3+4 ] +[ 4+2 + 2+3 + 3+4 + 4+5 ] +[ 5+3 + 3+4 + 4+5 + 5+6 ]= 91 обмен сообщениями.Если принять что в каждом запросе было по 1 байту, то получил 91 * ( Ts + 1 * Tb ).Ответ: 91 * ( Ts + 1 * Tb ).6. Сколько времени потребует выбор координатора среди 16 процессов, находящихся в узлах транспьютернойматрицы размером 4*4, если используется алгоритм задиры? Время старта равно 100, время передачи байта равно1 (Ts=100,Tb=1).
Процессорные операции, включая чтение из памяти и запись в память считаются бесконечнобыстрыми. Задира расположен в узле с координатами (0,0) и имеет уникальный номер 0.Решение.Если процесс обнаружит, что координатор очень долго не отвечает, то инициирует выборы. Процесс P проводитвыборы следующим образом:1.2.3.P посылает сообщение "ВЫБОРЫ" всем процессам с большими чем у него номерами.2.
Если нет ни одного ответа, то P считается победителем и становится координатором.3. Если один из процессов с большим номером ответит, то он берет на себя проведение выборов. Участиепроцесса P в выборах заканчивается.В любой момент процесс может получить сообщение "ВЫБОРЫ" от одного из коллег с меньшим номером. В этомслучае он посылает ответ "OK", чтобы сообщить, что он жив и берет проведение выборов на себя, а затем начинаетвыборы (если к этому моменту он уже их не вел). Следовательно, все процессы прекратят выборы, кроме одного нового координатора.
Он извещает всех о своей победе и вступлении в должность сообщением "КООРДИНАТОР".Во втором пункте алгоритма нужно убедиться, что нет ни одного ответа - пусть для этого нужно будет подождатьвремя Timeout.ВЫБОРЫ от 0 до 15-го процесса доходят за 6 шагов, он ждет Timeout и дальше за 6 шагов всех оповещает о новомкоординаторе. Все вместе это занимает 6 * (Ts + A * Tb) + 6 * (Ts + 1 * Tb) + Timeout времени, где A - среднееколичество байт для передачи в начальные моменты, его мне оценить не удалось, поэтому лучше вообщепренебречь Tb (тем более что Tb << Timeout).Ответ: 12 * Ts + Timeout[Забавность ситуации состоит в том, что задира имеет самый меньший из всех транспьютеров уникальный номер 0.Вот уж кто точно не станет координатором.] - [ Если все остальные скончались - то станет ]Мне кажется, не очень здорово вводить параметр Timeout - этим мы делаем предположение о скорости работыпроцессов, что в лекциях не рекомендуется.16Попробую предложить другое решение.
Пусть передается сообщение между процессами в двух соседних узлах.Если номер отправителя меньше, то получатель первым делом шлет ему "ОК", продолжает выборы, пересылаявсем остальным уже свой номер. Если же номер отправителя больше, получатель понимает, что не быть емукоординатором, ничего не возвращает отправителю, всем остальным рассылает сообщение от имени отправителя суже его номером. [Не знаю, можно ли так делать, но выглядит оптимальнее, чем один будет еще и еще раз слатьвсе всем остальным].Теперь, по условию, у нас решетка 4х4, сообщения идут из 0х0 "по слоям" решетки в сторону 3х3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
