19    Возникновение     тупиковых     ситуаций.     Временная     диаграмма     deadlock'a. Предотвращение deadlock.

При параллельном исполнении процессов могут возникать ситуации, при кото­рых два или более процесса все время находятся в заблокированном состоянии. Самым простым является случай, когда каждый из двух процессов ожидает ре­сурс, занятый другим процессом. Из-за такого ожидания ни один из процессов не может продолжить исполнение и освободить в конечном итоге ресурс, необхо­димый другому процессу. Эта тупиковая ситуация называется deadlock, тупи­ком или клинчем. Говорят, что в мультипрограммной системе процесс находится в состоянии тупика, если он ждет события, которое никогда не произойдет. Ту­пики чаще всего возникают из-за конкуренции несвязанных параллельных про­цессов за ресурсы вычислительной системы, но иногда к тупикам приводят и ошибки программирования.

Возникновение тупика характеризуются четырьмя условиями:

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

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

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

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

На временной диаграмме семафорных операций deadlock выглядит следующим образом:

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

1.      Предотвращение тупика.

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

2.      Обход тупика.

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

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

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