Ответы на задачи (1158843), страница 2
Текст из файла (страница 2)
Все 16 процессов, находящихся на разных ЭВМ сети с шиннойорганизацией (без аппаратных возможностей широковещания),одновременно выдали запрос на вход в критическую секцию. Скольковремени потребуется для прохождения всеми критических секций, еслииспользуется древовидный маркерный алгоритм (маркером владеетнулевой процесс). Время старта (время «разгона» после получениядоступа к шине для передачи сообщения) равно 100, время передачибайта равно 1 (Ts=100,Tb=1).
Доступ к шине ЭВМ получаютпоследовательно в порядке выдачи запроса на передачу (приодновременных запросах - в порядке номеров ЭВМ). Процессорныеоперации, включая чтение из памяти и запись в память, считаютсябесконечно быстрыми.Теория:1Алгоритм древовидный маркерный (Raymond).Все процессы представлены в виде сбалансированного двоичного дерева. Каждыйпроцесс имеет очередь запросов от себя и соседних процессов (1-го, 2-х или 3-х) и указательв направлении владельца маркера.Вход в критическую секциюЕсли есть маркер, то процесс выполняет КС.Если нет маркера, то процесс: помещает свой запрос в очередь запросов посылает сообщение «ЗАПРОС» в направлении владельца маркера и ждет сообщений.Поведение процесса при приеме сообщенийПроцесс, не находящийся внутри КС должен реагировать на сообщения двух видов-«МАРКЕР» и «ЗАПРОС».А) Пришло сообщение «МАРКЕР»М1.
Взять 1-ый запрос из очереди и послать маркер его автору (концептуально, возможносебе);М2. Поменять значение указателя в сторону маркера;М3. Исключить запрос из очереди;М4. Если в очереди остались запросы, то послать сообщение «ЗАПРОС» в сторонумаркера.Б) Пришло сообщение «ЗАПРОС».a) Поместить запрос в очередьb) Если нет маркера, то послать сообщение «ЗАПРОС» в сторону маркера, иначе (если естьмаркер) - перейти на пункт М1.Выход из критической секцииЕсли очередь запросов пуста, то при выходе ничего не делается, иначе - перейти кпункту М1.Решение: Задачи с ответами.doc2. Все 16 процессов, находящихся на разных ЭВМ сети с шиннойорганизацией (без аппаратных возможностей широковещания),одновременно выдали запрос на вход в критическую секцию.
Скольковремени потребуется для прохождения всеми критических секций, еслииспользуется децентрализованный алгоритм с временными метками.Время старта (время «разгона» после получения доступа к шине дляпередачи сообщения) равно 100, время передачи байта равно 1(Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно впорядке выдачи запроса на передачу (при одновременных запросах - впорядке номеров ЭВМ). Процессорные операции, включая чтение изпамяти и запись в память, считаются бесконечно быстрыми.Теория:Децентрализованный алгоритм на основе временных меток.Алгоритм носит имяпредложил Lamport.Ricart-Agrawalaиявляетсяулучшением алгоритма, которыйТребуется глобальное упорядочение всех событий в системе по времени.Вход в критическую секциюКогда процесс желает войти в критическую секцию, он посылает всем процессамсообщение-запрос, содержащее имя критической секции, номер процесса и текущее время.После посылки запроса процесс ждет, пока все дадут ему разрешение.
Послеполучения от всех разрешения, он входит в критическую секцию.Поведение процесса при приеме запросаКогда процесс получает сообщение-запрос, в зависимости от своего состояния поотношению к указанной критической секции он действует одним из следующих способов.1. Если получатель не находится внутри критической секции и не запрашивалразрешение на вход в нее, то он посылает отправителю сообщение «OK».2. Если получатель находится внутри критической секции, то он не отвечает, азапоминает запрос.3.
Если получатель выдал запрос на вхождение в эту секцию, но еще не вошел в нее,то он сравнивает временные метки своего запроса и чужого. Побеждает тот, чьяметка меньше. Если чужой запрос победил, то процесс посылает сообщение «OK».Если у чужого запроса метка больше, то ответ не посылается, а чужой запросзапоминается.Выход из критической секцииПосле выхода из секции он посылает сообщение «OK» всем процессам, запросы от которыхон запомнил, а затем стирает все запомненные запросы.Решение: Для 10 процессов 2013 Nurmambetov_2-kr.docx3. Все 16 процессов, находящихся на разных ЭВМ сети с шиннойорганизацией (без аппаратных возможностей широковещания),одновременно выдали запрос на вход в критическую секцию. Скольковремени потребуется для прохождения всеми критических секций, еслииспользуется широковещательный маркерный алгоритм (маркеромвладеет нулевой процесс). Время старта равно 100, время передачибайта равно 1 (Ts=100,Tb=1).
Процессорные операции, включая чтениеиз памяти и запись в память, считаются бесконечно быстрыми.Теория:Алгоритм широковещательный маркерный (Suzuki-Kasami).Маркер содержит: очередь запросов; массив LN[1...N] с номерами последних удовлетворенных запросов.Вход в критическую секцию1. Если процесс Pk, запрашивающий критическую секцию, не имеет маркера, то онувеличивает порядковый номер своихзапросовRNk[k]и посылаетшироковещательно сообщение «ЗАПРОС», содержащее номер процесса (k) иномер запроса (Sn = RNk[k]).2. Процесс Pk выполняет критическую секцию, если имеет (или когда получит)маркер.Поведение процесса при приеме запроса1.
Когда процесс Pj получит сообщение-запрос от процесса Pk, он устанавливаетRNj[k]=max(RNj[k],Sn). Если Pj имеет свободный маркер, то он его посылает Pkтолько в том случае, когда RNj[k]==LN[k]+1 (запрос не старый).Выход из критической секции процесса Pk.1. Устанавливает LN[k] в маркере равным RNk[k].2. Для каждого Pj, для которого RNk[j]=LN[j]+1, он добавляет его идентификатор вмаркерную очередь запросов (если там его еще нет).3. Если маркерная очередь запросов не пуста, то из нее удаляется первый элемент, а маркерпосылается соответствующему процессу (запрос которого был первым в очереди).Решение: Задачи с ответами.doc4.
15 процессов, находящихся в узлах транспьютерной матрицы размером4*4, одновременно выдали запрос на вход в критическую секцию.Сколько времени потребуется для прохождения всеми критическихсекций, если используется централизованный алгоритм (координаторрасположен в узле 0,0)? Время старта равно 100, время передачи байтаравно 1 (Ts=100,Tb=1). Процессорные операции, включая чтение изпамяти и запись в память, считаются бесконечно быстрыми.Теория:Централизованный алгоритм.Все процессы запрашивают у координатора разрешение на вход в критическую секциюи ждут этого разрешения. Координатор обслуживает запросы в порядке поступления.Получив разрешение процесс входит в критическую секцию.
При выходе из нее онсообщает об этом координатору. Количество сообщений на одно прохождениекритической секции - 3.Недостатки алгоритмаобычные недостаткикоординатора или его перегрузка сообщениями).централизованного алгоритма (крахРешение: 2013 Nurmambetov_2-kr.docx5. Сколько времени потребует выбор координатора среди 16 процессов,находящихся на разных ЭВМ сети с шинной организацией (безаппаратных возможностей широковещания),если используетсяалгоритм «задиры»? «Задира» расположен в узле с координатами (0,0) иимеет уникальный номер 0.
Время старта (время «разгона» послеполучения доступа к шине для передачи сообщения) равно 100, времяпередачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получаютпоследовательно в порядке выдачи запроса на передачу (приодновременных запросах - в порядке номеров ЭВМ). Процессорныеоперации, включая чтение из памяти и запись в память, считаютсябесконечно быстрыми.Теория:Алгоритм «задиры».Если процесс обнаружит, что координатор очень долго не отвечает, то инициируетвыборы. Процесс P проводит выборы следующим образом:1.
P посылает сообщение «ВЫБОРЫ» всем процессам с большими чем у негономерами.2. Если нет ни одного ответа, то P считается победителем и становитсякоординатором.3. Если один из процессов с большим номером ответит, то он берет на себяпроведение выборов. Участие процесса P в выборах заканчивается.В любой момент процесс может получить сообщение «ВЫБОРЫ» от одного из коллег сменьшим номером. В этом случае он посылает ответ «OK», чтобы сообщить, что он жив иберет проведение выборов на себя, а затем начинает выборы (если к этому моменту он ужеих не вел). Следовательно, все процессы прекратят выборы, кроме одного - новогокоординатора. Он извещает всех о своей победе и вступлении в должность сообщением«КООРДИНАТОР».Решение: Esyr или 2013 Saktaganov_3-kr.docx6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
