В. Столлингс - Операционные системы (1114679), страница 140
Текст из файла (страница 140)
° (Ве1еаэе, Т„Ф): процесс ~ ос ож Алгоритм работает следующим образом. Р жен доступ к ресурсу, он отпр отп авляет заир 1. Когда процессу, нужен д ой равняется текуще с в еменной меткой, значение которо (Вециевй, Т,, 1) с времен . Процесс помещает это с счетчика этого процесса. ро показанию локального счетч ['3 т его всем о ' общение в элемент емент своего собственного мас сиза И и рассылае тальным процессам. Когда процесс Р, получает запрос 1Вес)мезе, Т„)), он помещает его в элемент собственного массива д[1).
Если в элементе д[Д не содержится сообщения с запросом, то процесс Р, отправляет процессу Р~ ответ. Это именно то дейст вие, с помощью которого реализуется описанное ранее правило. Оно гаран тирует, что в момент принятия решения в каналах не осталось ни одного сообщения с запросом. Процесс Р, может получить доступ к ресурсу (войти в критический раздел), если соблюдаются два условия. а. Запрос д, поступивший от процесса Р, является первым сообщением в собственной очереди этого процесса; поскольку сообщения на всех узлах упорядочены одинаково, это сообщение предоставляет в каждый момент времени доступ к ресурсу одному и только одному процессу.
б, Все другие сообщения, содержащиеся в локальном массиве, являются более поздними, чем сообщение в элементе д[ф соблюдение этого правила гарантирует, что процессу Р; известно обо всех запросах, предшествующих его текущему запросу. Процесс Р; освобождает ресурс путем генерации сообщения (Ве1еаае, Т„[), которое он помешает в свой собственный массив и рассылает всем другим процессам.
Получив сообщение (Ве1еазе, Т„1), процесс Р; помещает его в элемент массива дЯ, заменяя его текущее содержимое этим сообщением. Получив сообщение (Вер1у, Т,, 1), процесс Р; помещает его в элемент массива дЯ, заменяя его текущее содержимое этим сообщением.
Легко показать, что этот алгоритм обеспечивает взаимоисключение, равноправность процессов, отсутствие взаимоблокировок и голодания. Взаимоисключение. Запросы на вход в критический раздел обрабатываются в том порядке, который определяется механизмом временных меток.
Если процесс Р; принимает решение войти в свой критический раздел, то в системе не может быть никаких других запросов, которые были переданы перед его запросом. Это утверждение является справедливым, так как процесс Р; к этому моменту получил от всех других узлов сообщения, помеченные более поздним временем, чем его запрос. В этом можно быть уверенным благодаря механизму ответных сообщений. Напомним, что при передаче сообщений их порядок не может быть нарушен.
Равноправность. Доступ по запросам предоставляется строго в соответствии с временными метками. Поэтому все процессы обладают равными возможностями. Отсутствие взаимоблокировок. Благодаря тому, что порядок временных меток на всех узлах совпадает, взаимоблокировки невозможны. Отсутствие голодания. Как только процесс Р„закончит выполнение своего критического раздела, он передает сообщение об освобождении (Ве1еазе). Это приводит к удалению на всех узлах запроса, поступившего от процесса Р„и предоставлению доступа к критическому разделу другому процессу. ~ лава 14. Упраалещае расщищелениыми процессами Чтобы оценить эффективность работы этого алгоритма, отметим, что для обеспечения исключения необходимо переслать Зх (Х - Ц сообщений: (Х - 1) сообщенийзапросон, (И - 1) ответных сообщений и (И - 1) сообщений об освобождении. временные метки своего запроса и зап запроса, полученного от другого п временная метка запроса другого проц процесса.
Ясли процесса является более поздней, о „, кладывается; в противном случае о ", отправка ответа ае ответ отправляется тут же. Вторая версия В 1В1САВЦ предложен улучшенный вариант алгоритма Лампорта. В нем предпринята попытка оптимизировать первоначальную версию этого алгоритма, исключив из него сообщения об освобождении ресурса. Остаются в силе все ранее сделанные предположения, за исключением того, что теперь нам не нужно, чтобы сообщения, отправленные одним процессом другому, приходили н том же порядке, в котором они были отправлены. Как и ранее, на каждом узле имеется один процесс, управляющий распределением ресурсов. Этот процесс поддерживает массив д и работает по следующим правилам.
1. Если процессу Р, нужен доступ к ресурсу, он генерирует запрос (Вес1пез1, Тн 1) с временной меткой, значение которой равняется текущему показанию локального счетчика этого процесса. Процесс помещает это сообщение н элемент своего собственного массива ОЯ и рассылает его всем остальным процессам.
2. Когда процесс Р, получает запрос (Вецпез|, Т;, 1), он действует следующим образом. а. Если процесс Р; н данное время находится в своем критическом разделе, '. он откладывает отправку ответного сообщения (см. правило 4 ниже). б. Если процесс Р, не ожидает, пока ему можно будет войти в свой критиче-: ский раздел (у него нет необработанных запросов), он передает процесс Р„ответ (Вер1у, Т;, у) в. Если процесс Р, ожидает, пока ему можно будет войти в свой критиче ' ский раздел, и если входящее сообщение следует после запроса процесс', Р„то он помещает это сообщение в элемент собственного массива дЯ откладывает отправку ответного сообщения. г.
Если процесс Р; ожидает, пока ему можно будет войти в свой критиче. ский раздел, и если входящее сообщение предшествует запросу процесс Р„то он помещает это сообщение в элемент собственного массива дЯ отправляет процессу Р, ответное сообщение (Вер1у, Т,, у).
3. Процесс Р, может получить доступ к ресурсу (войти в свой критически раздел), если он получил ответные сообщения от всех остальных процессов.' 4. После выхода из своего критического ресурса процесс Р; освобождает сурс, рассылая ответные сообщения на все ожидающие запросы. Диаграмма переходов каждого процесса из одного состояния в другое пок ' зана на рис. 14.10.
Итак, если процессу нужно войти в свой критический раздел, он рассыла всем другим процессам запрос с временной меткой. Когда он получит ответы от них, он сможет войти в свой критический раздел. Если процесс получает запрос другого процесса, он, н конце концов, должен отправить ему соответствующий отве Если пропессу не нужно входить в свой критический раздел, он отправляет этот вет сразу же. Если же ему нужно войти в свой критический раздел, то он сравнивае уд бслужен. диод е передачей маркера Несколько исследователей предложили мощью сове Реализовать взаимоисключения с совершенно иного подхода, в кото ом ором используется передача маркера .- ~лава.14. у правление распределенными процессами Рис.
И.10, Диаграмла состояний, соответстпв таянии, соответствующая алгоритму из ~ШСА8Ц П ри соблюдении этого метода т е да требуется 2х(Ж - 1) сообщений: (Ф - 1) сообени -запросов нужны для того, чтобы казать н тически раздел, и еще Ф - 1 отв у ать на намерение процесса Р, войти тавить за запрашиваемый доступ. 1 - ответных сообщений — чтобы предос- Ис гюль зование временных меток н этом ал ключение б этом алгоритме обеспечивает взаимоис- ие; лагодаря ему удается также изб последнее е из ежать взаимоблокировок. Докажем утверждение методом от п тинного: туация, ког ротивного: предположим, что возможна си- , когда в каналах не осталось ни о пРавил зап ос одного сообщения, каждый процесс От- апрос и не получил необходимого от ПстОМУ ЧГО д о ответа. Такая ситуация невозможна, то Решение о задержке ответа основы просоз.
Поэт основывается на порядке поступления за- оэтому найдется хотя бы о ин менной метки д запрос с минимальным значением вре- метки, который получит все нео х взаимобл окировка невозможна. еобходимые ответы. Благодаря этому Кроме т ого, поскольку зап осы по бежать, Так к р у орядочены, голодания также удается из- ак как запросы обслуживаются им каждый и роцесс рано или ся именно в порядке их расположения поздно становится самым старым и б ет о ся им О ~ЬП Ееп ) е1б а1Бе Г'Ог (1пг. ) = 1 ' 1; ~ < и; -)++) ГОКеп ргеБепг = га1БО," Бепс) (ассеББ, 1океп (~)); а) Первая часть (гссе1чеб (ВециеБГ., Е, ~)) геанеаг ()) = л.ах(тес(сеБг(„'), Е); (бо);еп ргеэепт.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
