Предотвращение тупиков, 3 стратегических принципа.

Основные направления исследований по проблеме тупиков

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

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

2.Процессы удерживают за собой ресурсы, уже выделенные им, ожидая в то же время дополнительных ресурсов (условие ожидания ресурсов).

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

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

4 основных направления:

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

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

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

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

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

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

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

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

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

3 стратегических принципа:

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

« Если процесс, удерживающий определенные ресурсы, получает отказ в удовлетворении запроса на дополнительные ресурсы, то он должен освободить свои первоначальные ресурсы и при необходимости запросить их снова вместе с дополнительными;

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

Первое условие не будем нарушать, т.к. надо предусмотреть возможность работы с закрепленными ресурсами.

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

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

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

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

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

3.4 Обход тупиков, Алгоритм банкира(предложил Дейкстра)

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

Рассмотрим проблему распределения некоторого количества t идентичных устройств.

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

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

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

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

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