Моделирование взаимоблокировок

Лекция 8. Тупики

Tупик (deadlock) - это такая ситуация в мультипрограммной системе, когда процесс ожидает некоторого события, которое никогда не произойдет. Системная тупиковая ситуация, или “зависание” системы - это ситуация, когда один или более процессов оказываются в состоянии тупика.

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

Ресурсы

Ресурсами могут быть аппаратные устройства (например, привод накопителя на магнитной ленте) или какая-то часть информации (например, заблокированная запись базы данных). Под ресурсом понимается все, что должно предостав­ляться, использоваться и через некоторое время высвобождаться, поскольку в один и тот же момент времени может использоваться только одним процессом.

Выгружаемые и невыгружаемые ресурсы

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

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

Как правило, во взаимоблокировках фигурируют невыгружаемые ресурсы.

В наиболее общем виде при использовании ресурса происходит следующая последовательность событий:

1. Запрос ресурса.

2. Использование ресурса.

3. Высвобождение ресурса.

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

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

Моделирование взаимоблокировок

Холт (Holt, 1972) показал, как эти четыре условия могут быть смоделированы с ис­пользованием направленных графов. У графов имеется два вида узлов: процессы, показанные окружностями, и ресурсы, показанные квадратами. Направленное ребро, которое следует от узла ресурса (квадрата) к узлу процесса (окружности),означает, что этот ресурс был ранее запрошен, получен и на данный момент удер­живается этим процессом. На рис. 6.1, а, ресурс R в данное время выделен про­цессу Л.

Направленное ребро, идущее от процесса к ресурсу, означает, что процесс в дан­ное время заблокирован в ожидании высвобождения этого ресурса. На рис, 6.1, б процесс В ожидает высвобождения ресурса S. На рис. 6.1, в мы наблюдаем взаимо­блокировку: процесс С ожидает высвобождения ресурса Г, который в данный мо­мент удерживается процессом D. Процесс D не собирается высвобождать ресурс Т, поскольку он ожидает высвобождения ресурса U, удерживаемого процессом С. Оба процесса находятся в состоянии вечного ожидания. Циклическая структура графа означает, что мы имеем дело с взаимоблокировкой, включившей процессы и ресурсы в цикл (предполагается, что в системе есть только один ресурс каждого типа). В данном примере получился следующий цикл: C-T-D-U-C.

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

Ресурс 1 выделен Процесс_Y запрашивает

процессу_Х Ресурс 1 ресурс 1

Процесс_Х Процесс_Y

Процесс_Х запрашивает Ресурс 2 выделен

ресурс 2 Ресурс 2 процессу_ Y

Граф распределения ресурсов

Такое состояние кругового ожидания характерно для систем в тупиковом состоянии.

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