2007 Задачи (1162817), страница 3
Текст из файла (страница 3)
Итого - 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.
Наихудшийслучай будет, если на каждом следующем слое номер процесса будет больше, чем на предыдущем (т.е.выбираемый координатор находится в 3х3). Тогда каждому процессу (на всех слоях, кроме первого и последнего)надо будет потратить 2*(Ts + N*Tb) для информирования предыдущего слоя и начала выборов для следующего.Тогда общий ответ 6*2*(Ts + N*Tb).Если же выбираемый координатор находится где-то еще, а не в 3х3, то просто всем процессам на следующих слояхне надо пересылать сообщения обратно, что ускорит процесс.7.
Сколько времени потребует выбор координатора среди 16 процессов, находящихся в узлах транспьютернойматрицы размером 4*4, если используется круговой алгоритм? Время старта равно 100, время передачи байтаравно 1 (Ts=100,Tb=1). Процессорные операции, включая чтение из памяти и запись в память считаютсябесконечно быстрыми.Решение.Алгоритм основан на использовании кольца (физического или логического), но без маркера. Каждый процесс знаетследующего за ним в круговом списке.
Когда процесс обнаруживает отсутствие координатора, он посылаетследующему за ним процессу сообщение "ВЫБОРЫ" со своим номером. Если следующий процесс не отвечает, тосообщение посылается процессу, следующему за ним, и т.д., пока не найдется работающий процесс. Каждыйработающий процесс добавляет в список работающих свой номер и переправляет сообщение дальше по кругу.Когда процесс обнаружит в списке свой собственный номер (круг пройден), он меняет тип сообщения на"КООРДИНАТОР" и оно проходит по кругу, извещая всех о списке работающих и координаторе (процессе снаибольшим номером в списке). После прохождения круга сообщение удаляется.Предположим, что у нас в логическом кольце N живых процессов.
Заметим также, что отправка подтвержденийсообщений не отнимают у всего алгоритма времени.1-ый этап - рассылка сообщения ВЫБОРЫ (длинны А). Она происходит за N шагов.2-ой этап - рассылка КООРДИНАТОР (длинны B), это тоже N шагов. В сумме - N * ( Ts + A * Tb ) + N * ( Ts + B *Tb).Ответ: N * ( 2 * Ts + (A+B) * Tb )[ Ответ выписан с ошибкой :)Отмечу, что для матрицы 4х4 в простом случае можно взять N=16, A=B=3 байта (1 байт - тип сообщения + 16 бит битовый массив участников кольца). Если же не все процессы живы (что в данной задаче, похоже, неподразумевается), то нужно еще учитывать Timeout.] - [ Ответ починил. Про Timeout - точно, этот ответ годитсятолько для N = 16 ;) ]17Тема 5(См.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
