Теоретический материал

Процесс находится в состоянии тупика, если он ожидает события, которое никогда не произойдет. «Зависание» системы – ситуация, когда один или более процессов находятся в состоянии тупика.

Основные направления исследований по проблеме тупиков. Можно выделить четыре направления нацеленные на устранения тупиков:

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

· обход тупиков;

· обнаружение тупиков;

· восстановление после тупиков.

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

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

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

Алгоритм банкира (предложил Э. Дейкстра). Рассмотрим проблему распределения некоторого количества t идентичных устройств. ОС должна обеспечить распределение фиксированного числа t одинаковых устройств между некоторым фиксированным числом пользователей u. Каждый пользователь заранее указывает максимальное число устройств, которое ему потребуется. ОС принимает запрос пользователя в случае, если максимальная потребность этого пользователя в устройствах не превышает t. Пользователь может занимать или освобождать устройства по одному. Возможно, что иногда пользователю придется ждать выделения дополнительных устройств, однако ОС гарантирует, что ожидание будет конечным. Текущее число устройств, выделенных пользователю, никогда не превысит указанную максимальную потребность этого пользователя. Если ОС в состоянии удовлетворить максимальную потребность пользователя в устройствах, то пользователь гарантирует, что эти устройства после использования будут возвращены ОС в течение конечного периода времени. Текущее состояние называется надежным, если ОС может обеспечить всем текущим пользователям завершение их заданий в течение конечного времени. В противном случае состояние ненадежное. Алгоритм банкира говорит о том, что выделять устройства пользователям можно только в случае, когда после очередного выделения состояние системы остается надежным. Ненадежное состояние – состояние, которое может со временем привести к тупику.

Пример надежного состояния

	Текущее количество выделенных устройств		Максимальная потребность
Пользователь 1
Пользователь 2
Пользователь 3
Резерв

Имеется 12 одинаковых устройств. Это состояние надежное, т.к. дает возможность всем трем пользователям закончить работу. Если 2 резервных устройства дать пользователю 2, то он сможет завершить свою работу и освободить свои 6 устройств.

Пример ненадежного состояния

	Текущее количество выделенных устройств		Максимальная потребность
Пользователь 1
Пользователь 2
Пользователь 3
Резерв

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

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

Распределение ресурсов согласно алгоритму банкира. Распределение ресурсов согласно алгоритму банкира осуществляется при выполнении условий «взаимоисключения», «ожидания дополнительных ресурсов» и «неперераспределяемости». То есть процессы могут претендовать на монопольное использование ресурсов, которые им требуются. Процессам реально разрешается удерживать за собой ресурсы, запрашивая и ожидая выделения дополнительных ресурсов, причем система удовлетворяет только те запросы, при которых ее состояние остается надежным. Запрос пользователя, приводящий к переходу системы в ненадежное состояние, откладывается до момента, когда его все же можно будет выполнить.

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

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

2. Алгоритм требует, чтобы распределитель ресурсов гарантированно удовлетворял все запросы за конечный период времени. Очевидно, что для реальных систем необходимы более конкретные гарантии.

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

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

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

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

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

КОНТРОЛЬНЫЕ ВОПРОСЫ

1) Что такое тупик?

2) Что такое зависание системы?

3) Перечислите направления нацеленные на устранение тупиков?

4) Опишите алгоритм банкира.

5) Укажите недостатки алгоритма банкира.

6) Что такое обнаружение тупика?

7) Как осуществляется восстановление после тупика?