В. Столлингс - Операционные системы (1114679), страница 143
Текст из файла (страница 143)
В этом случае переменной )))аьс аког присваивается значение транзакции, которая находится в начале цепочки запирающих транзакций. Наконец, запрашивающая транзакция рассылает всем другим транзакциям обновляющее сообщение со своим параметром йес(цезг 0, чтобы изменить значения всех подлежащих изменению переменных ))а1г аког. Получив обновляющее сообщение, транзакция обновляет свою переменную Иа1с аког. Это означает, что ожидаемая ею транзакция сейчас заблокирована другой. Затем выполняются действия по выявлению взаимоблокировки, в процессе которых проверяется, ожидает ли транзакция какую-то другую, которая, в свою очередь, ждет первую.
Если это условие не выполняется, транзакция передает обновляющее сообщение дальше. Если же условие выполняется, транзакция отправляет той транзакции, которая удерживает нужный ей объект данных, сообщение об освобождении своих объектов, предоставляя каждый объект данных транзакции, которая согласно очереди ьеоцез~ О запросила его первой. Оставшиеся запросы помещаются в очередь новой транзакции. На рис. 14.12 приведен пример работы описанного алгоритма. Когда транзакция То запрашивает объект данных, содержащийся в транзакции Т„возникает цикл. Транзакция То отправляет обновляющее сообщение, которое передается от Т, к Т2 и от Тз к Тл.
В этот момент транзакция Т, обнаруживает, что пересечение ее переменных (на1г. бог И йвс)цеБГ 6 отлично от нуля. Транзакция Т, отправляет транзакции Т2 сообщение об освобождении своих объектов данных, вследствие чего Т, удаляется из очереди йеццевг О(Т.-.), и освобождает свои объекты, активизируя транзакции Т4 и Т,. рие. 14.12. Пример работы алгоритма по выявлению раепреоеленных ееаимоблокироеок Глава 14. Управление-распределенными прсцессамп Вта11 бок Не16 Ьу Транзакция Та Та Тс Та Тк Т4~ Тв Та Тк Та Тз Тк Тк Тв 1 Состояние системы до запроса Транзакция Иаэс бок Не1а Ьу несузевт. о То т Тз То Та Тв т.
Те Тб то тк т„ Тз Тк Та Та тв Тз Та '1 Состояние системы после того, как запрос транзакции Та будет получен транзакцией Тз Взаимоблокировки, возникающие При обмене сообщениями Взаимное ожидание При обмене сообщениями взаимоблокировки возникают, если есть группа троцессов, каждый из которых ожидает сообщения от другого процесса, являюцегося членом этой группы, и не осталось ни одного сообщения в каналах.
Чтобы проанализировать зту ситуацию подробнее, определим понятие кножества зависимости (йерепйепсе эеФ вЂ” 1зБ) процесса. Для процесса Р„ко'орый не может выполняться из-за ожидания сообщения, множество 0Я(Р,) :остоит из всех процессов, от которых процесс Р, ждет сообщения. Обычно троцесс Р1 сможет продолжить свою работу после получения любого из сообцений.
Возможна также ситуация, когда процесс может продолжать работу 'олька после получения всех ожидаемых сообщений. Однако наиболее растространенной является первая ситуация, поэтому в данной книге рассмат>ивается именно она. Опираясь на приведенное выше определение, можно сформулировать опреМление взаимоблокировки множества процессов Я. Взаимоблокировка возникает ~ри таких условиях. 1. Все пропессы множества Я находятся в ожидании сообщений. 2. 8 содержит множества зависимости всех процессов, входящих в Я. 3. В каналах нет ни одного сообщения, передаваемого от одного члена множества Я другому.
Все процессы множества Б являются заблокированными так к как не моще; быть получено ни одно сообщение, благодаря которому хотя бы один процеск мог продолжить работу. Разницу меякду взаимоблокировкой, возникающей при обмене сообщениями ~1 в взаимоблокировкой, возникающей при распределении ресурсов, можно пояснить к помощью графов- Взаимоблокировка ресурсов возникает тогда, когда в графе зази симости процессов образуется замкнутый цикл.
В случае взаимоблокировки ресурсов один процесс зависит от другого, если последний обладает нужным ему ресурсо Ресурсом Условие взаимоблокировки сообщений состоит в том, что все последующие элементь любого входящего в множество Я члена сами входят в этот множество. Р Это положение проиллюстрировано на рис. 14.13. На рис. 14.13 а про т ожидает сообщения либо от процесса Ре, либо от процесса Рв; процесс Р не ожидает никаких сообщений, поэтому он может отправить сообщени ние процессу Р„тем самым выводя его из состояния ожидания. В результате звенья (Р Р ) Р Р ( „в) удаляются. На рис. 14.13,6 добавлена еще одна зависимость: процесс Р„ ожидает сообщения от процесса Р;, который ждет сообщения от проц Р РоЦееса вэ ожидающего сообщения от процесса Р„который, в свою очередь, ждет сообщения от процесса Рв В результате возникает взаимоблокировка.
в) Взвимобпакиоавкв отсутствует б) Взвимабпокировкв Рис. 14.13. Взаимоблокировка, возникающая при обмене сообщениями Проблему взаимоблокировки сообщений, как и проблему взаимоблокировки ресурсов, можно решить, предотвращая ее возникновение или выявляя образование взаимоблокировки. Некоторые примеры можно найти в 1ВА'к'М681. Недоступность буферов сообщений Еще одна причина, по которой в системе с обменом сообщениями может возникнуть взаимоблокировка, связана с распределением буферов, предназначенных для хранения передаваемых сообщений. Этот вид взаимоблокировок хорошо известен в сетях с коммутацией пакетов данных. Сначала разберем эту проблему в контексте сети передачи данных, а затем рассмотрим ее с точки зрения Распределенной операционной системы. Самым простым видом взаимоблокировки в сети передачи данных является непосредственная блокировка хранения и передачи сообщений (залоге-апк1-Хогэтагп Йеа61осй).
Она может возникнуть в том случае, когда узел пакетной коммутации использует единый буферный пул, буфера которого по мере необходимости предоставляются пакетам. На рис. 14.14,а показана ситуация, в которой все буферное пространство на узле А занято пакетами, предназначенными для узла В.
То же справедливо и для узла В. Ни один из узлов не может принять ни одного па- Глава 14. Управлеиие распределенными процессами Буферннй пуп заполнен а) Непоервдивенная блокнровха хранения н передачи Рие. 14.1б. Структурированный буферный аул, предотвращрюихий взаиноблокировки Часгъ,б. Распределеин~вге системы кета, поскольку их буфера заполнены. Таким образом, ни один из них не может передать или получить сообщение. Непосредственную блокировку хранения и передачи сообщений можно предотвратить, не позволяя всем буферам заполняться сообщениями„предназначенными для одного узла.
Этого можно достичь, используя раздельные буфера Фиксированного размера для каждой связи. Если сообщения, предназначенные для одного узла, не смогут занять все буферное пространство, взаимоблокировка не возникнет даже при использовании общего буферного пула. б) Косвенная бпохнровха хранвння н первдачн рие. 14.14. Блокировка хранения и нередачи сообщений На рис. 14.14,б проиллюстрирована более сложная разновидность взаимо- блокировки — косвенная блокировка хранения и передачи сообщений. Она возникает, если образуется замкнутый цикл узлов, на каждом из которых очередь сообщений, передаваемых на соседний узел, до отказа заполнена пакетами, предназначенными для узла, находящегося за соседним.
Одним из простых спо- собов предотвращения взаимоблокировки подобного типа является нспользова ние структурированного буферного пула (рис. 14.15). Такие буфера имеют ие, рархическую организацию. Использование пула памяти на нулевом ур уровне не ограничивается никакими правилами- там может храниться любой вх Ф входящий пакет. Буфера„ которые находятся на уровнях с первого по 1ч'-й (где Ф зте максимальное количество промежуточных узлов при передаче пакета по сети), резервируются следующим образом: буфера на уровне й зарезервированы для па. кетов, которые до этого подверглись не менее Й транзитным пересылкам. Т аким образом, при большой загрузке сети буфера заполнены от нулевого до Ф-го -го уров. ня.
Если заполнены все уровни до 1е-го включительно, то не принимается ни одно входящее сообщение, прошедшее менее й транзитных пересылок. Можно показать (см. (ООРА851), что при соблюдении такой стратегии удается избежать как прямых, так и косвенных взаимоблокировок. С описанной вьппе проблемой взаимоблокировок можно столкнуться в контек. сте коммуникационной архитектуры, обычно на сетевом уровне модели 081. Проблема такого же рода может возникнуть и в распределенной операционной системе, в которой межпроцессное взаимодействие происходит с помощью обмена сообщениями.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
