Методы борьбы с тупиками

36. Понятие тупиковой ситуации при выполнении параллельных вычислительных процессов

? При параллельном исполнении процессов могут возникать тупиковые ситуации, когда два или более процесса блокируют друг друга, вынуждая ожидать наступления события, связанного с освобождением ресурса.

? Самый простой случай: каждый из двух процессов ожидает ресурс, занятый другим процессом, ни один из процессов не может продолжить исполнение и освободить ресурс, необходимый другому процессу.

? Эта ситуация называется тупиком, дедлоком, или клинчем.

Ресурсы системы разделяют на два класса:

• повторно используемые (Reusable Resource, RR), или системные (System Resource, SR), ресурсы;

• потребляемые, или расходуемые, ресурсы (Consumable Resource, CR).

? Системные ресурсы (SR) – конечное множество идентичных единиц некоторого вида ресурсов, обладающих свойствами:

• число единиц ресурса в системе неизменно;

• каждая единица ресурса либо доступна, либо выделена одному и только одному процессу;

• процесс может освободить единицу ресурса (сделать ее доступной), только если он ранее получил эту единицу.

? Особенности расходуемых ресурсов (CR):

• число доступных единиц некоторого ресурса типа CR изменяется по мере того, как выполняющимися процессами они расходуются (приобретаются) и освобождаются (производятся);

• процесс «потребитель» уменьшает число единиц ресурса, сначала запрашивая и затем приобретая (потребляя) одну или более единиц.

? Для исследования параллельных процессов и проблемы тупиков было разработано несколько моделей. Одна из них – модель повторно используемых ресурсов Холта. Согласно этой модели система представляется как набор (множество) процессов и набор ресурсов, каждый из ресурсов состоит из фиксированного числа единиц. Любой процесс может изменять состояние системы путем выдачи запроса на получение или освобождение единицы ресурса.

? В графической форме процессы и ресурсы представляются квадратами и кружками соответственно. Каждый кружок содержит некоторое количество маркеров (фишек) в соответствии с существующим количеством единиц этого ресурса.

? Дуга из «процесса» на «ресурс» означает запрос одной единицы этого ресурса. Дуга из «ресурса» на «процесс» – выделение ресурса процессу.

? Т.к. каждая единица ресурса типа SR может быть выделена одновременно не более чем одному процессу, то число дуг из ресурса к различным процессам не может превышать общего числа единиц этого ресурса. Такая модель называется графом повторно используемых ресурсов.

? Удовлетворение запроса Пр1 приведет к тупиковой ситуации: Пр1 не сможет продолжиться до тех пор, пока Пр2 не освободит единицу ресурса R1, а процесс Пр2 не сможет продолжиться до тех пор, пока Пр1 не освободит единицу R2.

37. Примеры тупиковых ситуаций и причины их возникновения

? Пример тупика на ресурсах типа CR? Пусть имеется три процесса Пр1, Пр2 и ПрЗ, которые вырабатывают сообщения Ml, M2 и МЗ, соответственно. Эти сообщения представляют собой ресурсы типа CR. Пусть процесс Пр1 является потребителем сообщения МЗ, процесс Пр2 должен получить сообщение Ml, а ПрЗ – сообщение М2 от процесса Пр2. Таким образом, каждый из этих трех процессов является и поставщиком, и потребителем одновременно, и вместе они образуют кольцевую систему (рис. 7.2) передачи сообщений через почтовые ящики (ПЯ).

? Если связь с помощью этих сообщений со стороны каждого процесса устанавлива­ется программным кодом в порядке, когда они сначала посылают сообщение следующему процессу, а затем ожидают от предыдущего, то никаких проблем не возникает. Но перестановка этих двух процедур (сначала – ожидают, затем – посылают свое) в каждом из процессов вызывает тупик.

Пример тупика на ресурсах типа CR и SR

? Пусть процесс Пр1 должен обменяться сообщениями с процессом Пр2 и каждый из них запрашивает ресурс R, причем Пр1 требует три единицы этого ресурса для своей работы, а Пр2 — две единицы и только на время обработки сообщения. Всего же имеется только четыре единицы ресурса R. Запрос и освобождение ресурса можно реализовать через соответствующий монитор с процедурами запроса N единиц ресурса R, и освобождения (возврата) N единиц ресурса R. Обмен сообщениями осуществляется через почтовый ящик MB.

? Эти два процесса всегда будут попадать в состояние тупика. Процесс Пр2, выполняясь первым, сначала будет ожидать сообщения от процесса Пр1, затем будет заблокирован при запросе ресурса R, часть которого уже отдана процессу Пр1.

? Процесс Пр1, завладев частью ресурса R, будет заблокирован ожиданием ответа от Пр2, которого никогда не получит, так как для этого Пр2 нужно получить ресурс R, находящийся в распоряжении Пр1.

? Тупика можно избежать лишь при условии, что на время ожидания ответа от Пр2 процесс Пр1 отдаст хотя бы одну из единиц ресурса R, которыми он владеет.

? В данном примере, как и в предыдущем, причиной тупика являются ошибки программирования.

Пример тупика на ресурсах типа SR – не рассматриваем, но возможен.

? Для возникновения тупиковой ситуации необходимо одновременное выполнение следующих четырех условий:

? взаимного исключения, при котором процессы осуществляют монопольный доступ к ресурсам;

? ожидания, при котором процесс, запросивший ресурс, ждет до тех пор, пока запрос не будет удовлетворен, при этом удерживая ранее полученные ресурсы;

? отсутствия перераспределения, при котором ресурсы нельзя отобрать у процесса, если они ему уже выделены;

? кругового ожидания, при котором существует замкнутая цепь процессов, каждый из которых ждет ресурс, удерживаемый его предшественником в цепи.

38. Методы борьбы с тупиками

? Борьба с тупиковыми ситуациями основывается на одной из трех стратегий:

? предотвращение тупика;

? обход тупика;

? распознавание тупика с последующим восстановлением.

Предотвращение тупиков Предотвращение тупика основывается на предположении о чрезвычайно высокой его стоимости Этот подход используется в наиболее ответственных системах, обычно в системах реального времени.

Предотвращение можно рассматривать как запрет существования опасных состояний. Поэтому подсистема распределения ресурсов, предотвращающая тупик, должна гарантировать, что ни одного из четырех условий, необходимых для его наступления, не возникнет.

? Условие взаимного исключения можно подавить путем разрешения неограниченного разделения ресурсов.

? Условие ожидания можно подавить, предварительно выделяя ресурсы. При этом процесс может начать исполнение, только получив все необходимые ресурсы заранее. Это может привести к снижению эффективности работы вычислительной системы в целом, часто невозможно.

? Условие отсутствия перераспределения можно исключить, позволяя ОС отнимать у процесса ресурсы. Для этого в ОС должен быть предусмотрен механизм запоминания состояния процесса с целью последующего восстановления хода вычислений.

? Условие кругового ожидании можно исключить, предотвращая образование цепи запросов. Это можно обеспечить с помощью принципа иерархического выделения ресурсов. Все ресурсы образуют иерархию. Процесс, затребовавший ресурс на одном уровне, может затем потребовать ресурсы только на более высоком уровне. Он может освободить ресурсы на данном уровне, только после освобождения всех ресурсов на всех более высоких уровнях. После того как процесс получил, а потом освободил ресурсы данного уровня, он может запросить ресурсы на том же самом уровне.

Обход тупиков

? Обход тупика можно рассматривать как запрет входа в опасное состояние. Если ни одно из упомянутых четырех условии не исключено, то вход в опасное состояние можно предотвратить при наличии у системы информации о последовательности запросов, связанных с каждым параллельным процессом.

? Доказано, что если вычисления находятся в любом неопасном состоянии, то существует, по крайней мере, одна последовательность состояний, которая обходит опасное состояние. Поэтому достаточно проверить, не приведет ли выделение затребованного ресурса сразу же к опасному состоянию. Если да, то запрос отклоняется, если нет, его можно выполнить. Определение того, является состояние опасным или нет, требует анализа последующих запросов от процессов.

? Классическое решение этой задачи предложено Дейкстрой и известно как алгоритм банкира.

? Каждый раз, когда что-то может быть выделено из числа остающихся незанятыми ресурсов, предполагается, что соответствующий процесс работает, пока не окончится, а затем его ресурсы освобождаются.

? Если в итоге все ресурсы освобождаются, значит, все процессы могут завершиться, и система находится в безопасном состоянии.? Т.е., согласно алгоритму банкира система удовлетворяет только те запросы, при которых ее состояние остается надежным. Новое состояние безопасно тогда и только тогда, когда каждый процесс может окончиться. Именно это условие и проверяется в алгоритме банкира.

39.Обнаружение тупика

Чтобы распознать тупиковое состояние, необходимо для каждого процесса определить, сможет ли он когда-либо снова развиваться, то есть изменять свои состояния.

Обнаружение тупика посредством редукции графа повторно используемых ресурсов:

? Граф повторно используемых ресурсов сокращается процессом Рi, который не является ни заблокированной, ни изолированной вершиной, путем удаления всех ребер, входящих в вершину Рi и выходящих из Рi.

? Граф повторно используемых ресурсов несокращаем, если он не может быть сокращен ни одним процессом.

? Граф ресурсов типа SR является полностью сокращаемым, если существует последовательность сокращений, которая удаляет все дуги графа.

Лемма: для ресурсов типа SR порядок сокращений дуг графа повторно используемых ресурсов несуществен; все последовательности ведут к одному и тому же несокращаемому графу.

Теорема о тупике: Состояние S есть состояние тупика тогда и только тогда, когда граф повторно используемых ресурсов в состоянии S не является полностью сокращаемым.

Первое следствие: процесс не находится в тупике тогда и только тогда, когда серия сокращений приводит к состоянию, в котором он не заблокирован.

Второе следствие: если S есть состояние тупика (по ресурсам типа SR), то по крайней мере два процесса находятся в тупике в S.

? Из теоремы о тупике следует и алгоритм обнаружения тупиков. Нужно попытаться сократить граф; если граф полностью не сокращается, то начальное состояние было состоянием тупика для тех процессов, вершины которых остались в несокращенном графе.

? Лемма позволяет предложить алгоритмы обнаружения тупика. Например, можно представить систему посредством графа повторно используемых ресурсов и попробовать выполнить его редукцию.

Методы обнаружения тупика по наличию замкнутой цепочки запросов

? Первая теорема: цикл в графе повторно используемых ресурсов является необходимым условием тупика.

? Вторая теорема: тупик может быть вызван только при запросе, который не удовлетворен немедленно. Т.е. проверка на тупиковое состояние может быть выполнена боле эффективно, если она проводится непрерывно (по мере развития процессов).

? Состояние называется фиксированным, если каждый процесс, выдавший запрос, заблокирован.

? Третья теорема: если состояние системы фиксированное (все процессы, имеющие запросы, удовлетворены), то наличие узла в соответствующем графе повторно используемых ресурсов – достаточное условие тупика.

? Четвертая теорема: граф повторно используемых ресурсов с единичной емкостью указывает на состояние тупика тогда и только тогда, когда он содержит цикл.

Алгоритм обнаружения тупика по наличию замкнутой цепочки запросов? Распознавание тупика может быть основано на анализе модели распределения ресурсов. Один из алгоритмов, основанный на методе обнаружения замкнутой цепи запросов, был разработан сотрудниками фирмы IBM. Он использует информацию о состоянии системы, содержащуюся в двух таблицах: таблице текущего распределения ресурсов и таблице заблокированных процессов. При каждом запросе на получение или освобождение ресурсов содержимое этих таблиц модифицируется, а запрос анализируется в соответствии с заданным алгоритмом.

? Распознавание тупика требует дальнейшего восстановления вычислений. Восстановление можно интерпретировать как запрет постоянного пребывания в опасном состоянии.

Методы восстановления:

? принудительный перезапуск системы с потерей информации обо всех процессах, существовавших до перезапуска;

? принудительное завершение процессов, находящихся в тупике;

? принудительное последовательное завершение процессов, находящихся в тупике, с последующим вызовом алгоритма распознавания после каждого завершения до исчезновения тупика;

? перезапуск процессов, находящихся в тупике, с некоторой контрольной точки;

? перераспределение ресурсов с последующим последовательным перезапуском процессов, находящихся в тупике.