8

Лекция 8 Глава 7. Тупики Тупики

Тупики и близкая к ним проблема бесконечного откладывания - важные факторы, которые должны учитывать разработчики ОС.

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

Рассмотрим простой пример тупика при распределении ресурсов.

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

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

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

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

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

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

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

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

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

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

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

Необходимые условия возникновения тупиков

Необходимые условия наличия тупика могут быть сформулированы следующим образом¹⁰ .

• Условие взаимоисключения - когда процессы требуют предоставления им права монопольного управления ресурсами, которые им выделяются.

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

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

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

Борьба с возникновением тупиков может вестись по четырем основным направлением: предотвращение тупиков; обход тупиков; обнаружение тупиков; восстановление после тупиков.

Стратегии предотвращения тупиков

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

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

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

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

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