В. Столлингс - Операционные системы (1114679), страница 142
Текст из файла (страница 142)
В качестве варианта подхода, при котором предварительные сведения такого рода не нужны, рассмотрим два алгоритма, предложенные в 1ВОЯБ783. Глава Х4. Управление распределенными процессами ~ба они были разработаны в контексте работы с базами данных, и поэтому мы „.удем говорить не о процессах, а о транзакциях. Б предложенных методах используются временные метки. В каждой транакции на протяжении ее времени жизни хранится временная метка, соответствующая времени ее создания.
Таким образом среди транзакций устанавливается ;трогий порядок. Если ресурс В, который используется транзакцией Т1, запра.ппвается другой транзакцией Т2, конфликт разрешается с помощью сравнения их временных меток. Соблюдение этого условия позволяет предотвратить образование циклического ожидания. Авторы предложили две разновидности этого базового метода и назвали их методом 'ожидания-перезапуска ' ( 'ъ'а1),-п1е ) и методом "прекращения-ожидания" ("коппс)- ь а1»'*). Предположим, что в текущий момент транзакция Т1 владеет ресурсом В, а транзакция Т2 генерирует запрос на этот ресурс.
Алгоритм метода ожидания- перезапуска, который используется распределителем ресурсов, показан в листинге 14.2„а. Временные метки двух транзакций обозначены как е(Т1) и е(Т2). Если транзакция Т2 старше, она блокируется до тех пор, пока транзакция Т1 не освободит ресурс  — либо сгенерировав запрос, либо в результате того, что она будет "убита"' при запросе другого ресурса. Если транзакция Т2 моложе, то она перезапускается с той же временной меткой, что и раньше.
Листинг 14.2. Методы предотвращения взаимоблокировок (е(Т2) < е(Т1) ) );а.'с Т2 ('~а1~ '); е.1 зе ):111 Т2 ','Же'); а3 Метод охидании-перезапуска 1» (е(Т2) < е(Т1) ) 11)1 Т1 ('хозгод'); )~а1» Т2 (*~з1»'); б) Метод прекращении-охидания Таким образом, при возникновении конфликта преимуществом обладает более старая транзакция. Благодаря тому что "убитая" транзакция восстанавливается со своей предыдущей временной меткой, она становится старше, и ее приоритет возрастает. Узлам не нужно знать о состоянии распределения всех ресурсов. Бсе„что нужно, — это временные метки транзакций, запрашивающих ресурс.
Как показано в листинге 14.2,6, метод прекращения-ожидания предоставляет немедленный доступ к запрашиваемому ресурсу старшей транзакции, удаляя владеющую этим ресурсом младшую транзакцию. Б отличие от метода ожидания-перезапуска, транзакция не должна ждать, пока ей будет предоставлен ресурс, использующийся младшей транзакцией. Избежание взаимоблокировок Избежание взаимоблокировок — зто метод динамического принятия решения о том, может ли предоставление данного ресурса по запросу привести к взаимоблокировке. В 1БП)О94Ь) отмечено, что избежание распределенных взаимоблокировок является непрактичным по таким причинам. 1.
Каждый узел должен следить за глобальным состоянием системы, ч то требует значительных накладных расходов на хранение и обмен информацией 2. Процесс проверки безопасного глобального состояния должен быть взаимо исключающим. В противном случае вопрос о предоставлении ресурса а двум различным ресурсам может рассматриваться на двух узлах, и они оба одно временно могут принять решение о том, что удовлетворение запроса являет ся безопасным.
В результате возникнет взаимоблокировка. 3. В распределенной системе с большим количеством процессов и ресурсов проверка безопасности состояния приводит и значительным накладным расходам на обработку запросов. Выявление взаияоблокировок При методе выявления взаимоблокировок процессам позволено получать незанятые ресурсы по первому требованию, а наличие взаимоблокировок опраде.
ляется при их возникновении. Если обнаружена взаимоблокировка, выбирается один из состааляюи~мх (сопзФйпеп1) процессов, к которому предъявляется ще. бование освободить ресурсы, необходимые для снятия взаимоблокировки. При выявлении распределенных взаимоблокировок возникают тру)~в(ости, состоящие в том, что каждый узел обладает сведениями только о сваих ресурсах, в то время как взаимоблокировка может включать в себя расп)ве-. деленные ресурсы. Б зависимости от того, как управляется система — централизовано, иерархически или распределенно, — можно использовать различные подходы 1см.
табл. 14.1). При централизованном управлении ответственность за выявление взаимоблокировок возлагается на один узел. Все сообщения с запросами и освобоящениями ресурсов отправляются центральному процессу, а также процессу, контролирующему данный ресурс. Поскольку центральный процесс обладает всеми необходимыми сведениями, он в состоянии определить наличие взаимоблакировки. Такой подход требует передачи большого количества сообщений; ои также уязвим по отношению к отказу центрального узла.
Кроме того, не исключена возможность выявления фиктивных взаимоблокировок. При иерархическом Управлении узлы организованы в древовидную структуру, в которой один из них выступает в роли корня дерева. На каждом узле, не являющемся листом, собрана информация о распределении ресурсов между всеми зависимыми от него узлами.
Это позволяет выявлять взаимоблокировки, возникающие на более низких по отношению к корневому узлу уровнях. Другими словами, взаимоблокировка, в которой участвует какое-то множество ресурсов, будет выявлена тем узлом, который является общим "предком" всех узлов, ресурсы которых принимают участие в конфликте. При распределенном управленми все процессы выявляют взаимоблокировку сообща.
Вообще говоря, это означает необходимость интенсивного обмена информацией, включающей временные метки; в результате возникают значительные накладные расходы. В 1ИАУХЗЗ) можно найти несколько ссылок на алгоритмы распределенного управления, а в (РАТТ90) приводится подробное изучение одного из таких подходов. Глава 14. Управление раснределенными процессами '» б о Ю о ~ о о »д '»» Д Ж о о а о.о о ~о~и~ »'~»»»» >ъ Ф~ о» оыЯ ооо в Й к~ ыМо ~~о (~ к ~Во х»~ ооо~Фо»»овфо »о о Ф о ч о ~»" Й»»~ и м »»,Д » Ю дно д о Р' о» ~ й э( 6 й х ~ ~( э ~ й ~ ~р »"-(М о й»га)ю Транзакция з » оМФю~43 я ~ щ о»~ ~~ и о»»с Ь" д в й То Т! Т» Т» О О ч о ~~ о в ") ))) д Ф ак ~ в фчюф Ф о »д лло ~я22 Та То Т» То Т1 3'~ ~» о Й» Цк~ а „"~ к 4 с~ й д ойдо $»»» ы ойо е»д Р' о Й $ х а о »Ф з ж о. Ф Щ 4 д И к о.
о »»$ М й в Х Ф» »» о. )»' М я Ф о я Ф я я о Приведем пример алгоритма, предназначенного для выявления распреде ленных взаимоблокировок Я»'-)АТТ92, ЛОНИ911). Этот алгоритм работает с рас пределенной базой данных, в которой на каждом узле поддерживается некоторая часть базы данных; транзакции могут инициироваться каждым узлом. В каждой транзакции может быть не больше одного запроса ресурса. Если транзакция ну. ждается в нескольких объектах данных, второй объект данных можно запраши вать только после того, как будет предоставлен первый объект данных.
С каждым объектом данных ) на узле связаны два параметра: уникальный идентификатор 1); и переменная ЬасКей Ьу(0~). Эта переменная имеет нулевое значение, если объект данных не заблокирован ни одной транзакцией. В противном случае ее значение равно идентификатору блокирующей транзакции. С каждой транзакцией у на узле связано четыре параметра: ° уникальный идентификатор Т;; ° переменная Не1о Ьу (Т';), значение которой равно нулю, если транзакция Т~ находится в состоянии выполнения или готовности; в противном случае ее значение равно идентификатору транзакции, которая удерживает объект данных, требующийся транзакции Т~, ° переменная Иа1г Еог(Т~), значение которой равно нулю, если транзакция Т; не ожидает никаких других транзакций; в противном случае ее значение равно идентификатору транзакции, которая находится во главе упорядоченного списка блокированных транзакций; ° очередь Ре~аеэ~ 0(Т~), в которой содержатся все необработанные запросы объектов данных, удерживаемых транзакцией Т~, каждый элемент очереди имеет вид (Т», О»), где Т» — запрашивающая транзакция, а»1» — объект данных, удерживаемый транзакцией Т;.
Предположим, например, что транзакция Тэ ожидает предоставления объекта данных, закрепленного за транзакцией Т», которая, в свою очередь, ожидает предоставления объекта данных, закрепленного за транзакцией Тэ. При этом параметры имеют такие значения: Иал.с йох ие1о Ьу в»куаевс я Этот пример дает возможность понять разницу между параметрами Э)а1Ь Гаг (Т») и Не1с( Ьу(Т~) . Ни один процесс не может продолжаться, пока То не освободит объект данных, нужный для Т„который после этого сможет выполнить необходимые действия с этим объектом данных и освободить его для Тэ. Б листинге 14.3 приведен алгоритм, использующийся для выявления вэаимоблокировок.
Когда транзакция делает запрос на блокировку объекта данных. связанный с этим объектом данных обслуживающий процесс либо удовлетворяет запрос, либо отказывает в его удовлетворении. Если требуемый ресурс не предоставляется, обслуживающий процесс возвращает идентификатор транзакции» удерживающей этот объект данных. Главе Х4. Упревленне реепределеннымн процеасамн Бело (отказ транзакции) для Т„; зелб (Ьоскеб Ьу((),)) для Т„ Епс(цеце (7„, йеццезГ () (7„) ); листинг 14.3. Алгоритм выявления распределенных взаимоблокировок получение Объектом данных (), запроса 1ос1 ББЯцезв (7,) */ (1„ос~ос) Ьу(0 ) == пц11) зевс (ягалсес)) Р' :1зе Транзакция Т1 выполняет блокирувций зацрос Объекта данных 6., ;елб ('ООЕ гес)Беву(Т,)) Ддя б; ожидание предоставления/Отказа; (агав".еб) 1;оскреб Ьу(б,) = Т,.
)(е1б Ьу(Т,) = Я; 1зе /* Считаем, что (), используется транзакцией Т; */ ( йе1с) Ьу(Т„) = Т,; Ело(цеце (Т,, Веццезс Я(7;) ); 11 (Ма11 йот (Т,) == лц11) ИБТГ. аког(Т,) = Т4 е1зе ХБТБ ~ог (74) = ХБТГ Гох'(7,): црба~е (Ка1Г аког (74), Рес)цевь () (7,) ); Получение транзакцией Т, обновлякадего сообщения *I Тг (()аз Ь аког(Т,) !=- ИБТГ аког(7,)) ()а1~ аког (Т.,) = Ха1с Уог (Т,.); 17 (Тлсегвесс (Ка1~ аког(Т,), Бее(цезв О(7,) ) = пц11) црба~е(На11 7ох (Т,), йес~цезг О(Т„-) ) ' е1зе ббъявление взаимоблокировки / началО разрежения БзаимОблОкировки */ l* выбирается. Т,, которая должна быть лрекраиена /* Т, освобождает все удерживаемые ею Объекты данных +~ Бепб с1еаг(7;, )(е1с) Ьу(Т;))' каждый Освобожяенный Объект ланныл Е34 Гцрелоставляется транзакции Тк, наколяьтейся БО хлеве Очереди ЯеЯцеЯС (л~T,.~; аког(каждОЙ транзакции Тв из Очереди йецыез~ 6(7,)к залрашивак4лей Объе кт дан ныхр кОтОрых нахОдится в 71 ) /'~ ПОЛУЧЕНИЕ тРанзакцией Т,.
сосб1аениЯ с1еаг (Т:, Т, ) */ удаление транзакции 7; из Очереди Яее1цезс С (ТЛ ' ., „. Час,)(, ~. распределенные системы Когда запрашивающая транзакция получает ответ о том будет удовлетворен она блокируе г объекг данну ~х В против прашивающая транзакция обновляет свою переменную Ке1б Ьу, присваивая ей идентификатор транзакции, удерживающей объект данных„и добавляет свой идентификатор в очередь транзакций ке~)цезБ 0. Транзакция также об новляет переменную Хаус ~ог, присваивая ей либо идентификатор транзакции, удерживающей объект данных (если эта транзакция не находится в ожидании), либо тот идентификатор транзакции, который хранится в пере менной пахс 4 о= удерживающей транзакции.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
