2013 Nurmambetov_2-kr (1162818), страница 4
Текст из файла (страница 4)
===хорошо
Можно, конечно.
Потребуется 6 посылок по L/2 байт по каждому из двух маршрутов, например, следующего вида.
В этом случае время будет Т = 6*(Ts+(L/2)*Tb)
-
Все 10 процессов, находящихся на разных ЭВМ сети с шинной организацией (без аппаратных возможностей широковещания), одновременно выдали запрос на вход в критическую секцию. Сколько времени потребуется для прохождения всеми критических секций, если используется децентрализованный алгоритм с временными метками. Доступ к шине ЭВМ получают последовательно в порядке выдачи операции посылки сообщения (при одновременно выданных операциях - в порядке номеров ЭВМ). Время старта равно 100, время передачи байта равно 3 (Ts=100,Tb=3). Процессорные операции, включая чтение из памяти и запись в память, считаются бесконечно быстрыми.
Решение: Каждый процесс шлет запрос на вход в критическую секцию всем остальным 9 процессам. Итого: 9*10*(Ts+Tb*L)
После выполнения критической секции процесс смотрит свои запросы на вход в своем списке и шлет им Ok(Ok может отправляться и до входа в критическую секцию).
В результате на посылку Ok уходит 9*10*(Ts+Tb*Lok). ЧТО ТАКОЕ Lok? При этом мы считаем, что время прохождения КС=0. Пусть L=Lok
Итого: 2*9*10*(Ts+Tb*L)
Надо задавать размеры в байтах!
В ТРЕБОВАНИЯХ написано:
3. Длины сообщений должны быть объяснены. Пример: “предположим, что адрес переменной занимает 4 байта, а значение - 8 байтов. Тогда длина сообщения равна 120 байтов”. Это нужно для того, чтобы видеть, как Вы поняли алгоритм - что посылается в каждом сообщении (например, что такое логическое время, как идентифицируется модифицируемая переменная и т.п.)
Решение:
Децентрализованный алгоритм на основе временных меток.
Требуется глобальное упорядочение всех событий в системе по времени. Для целей упорядочения всех событий удобно потребовать, чтобы их времена никогда не совпадали. Это можно сделать, добавляя в качестве дробной части к времени уникальный номер процесса (40.1, 40.2) И ЭТО 1 БАЙТ???.
Вход в критическую секцию
Когда процесс желает войти в критическую секцию, он посылает всем процессам сообщение-запрос, содержащее имя критической секции, номер процесса и текущее время.
После посылки запроса процесс ждет, пока все дадут ему разрешение. После получения от всех разрешения, он входит в критическую секцию.
Поведение процесса при приеме запроса
Когда процесс получает сообщение-запрос, в зависимости от своего состояния по отношению к указанной критической секции он действует одним из следующих способов.
-
Если получатель не находится внутри критической секции и не запрашивал разрешение на вход в нее, то он посылает отправителю сообщение «OK».
-
Если получатель находится внутри критической секции, то он не отвечает, а запоминает запрос.
-
Если получатель выдал запрос на вхождение в эту секцию, но еще не вошел в нее, то он сравнивает временные метки своего запроса и чужого. Побеждает тот, чья метка меньше. Если чужой запрос победил, то процесс посылает сообщение «OK». Если у чужого запроса метка больше, то ответ не посылается, а чужой запрос запоминается.
Выход из критической секции
После выхода из секции он посылает сообщение «OK» всем процессам, запросы от которых он запомнил, а затем стирает все запомненные запросы.
Количество сообщений на одно прохождение секции - 2(n-1), где n - число процессов.
Кроме того, одна критическая точка заменилась на n точек (если какой-то процесс перестанет функционировать, то отсутствие разрешения от него всех остановит).
В сообщении-запрос содержится номер КС, номер процесса, и текущее время. Отведем по 1 байту каждому, получим размер сообщения – 3 байта. Пусть «ОК» занимает 1 байт.
Перед заходом в КС процесс должен всем отправить запрос и от всех получить «ОК».
Время одного прохождения КС Т1 = 9*(Ts+3b*Tb) + 9* (Ts+1b*Tb) = 9*109+9*103= 1908. Количество КС = 10.
Ответ: Общее время Т = 10*Т1 = 19080.
===отлично
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
