ПРЕДОТВРАЩЕНИЕ ТУПИКОВ, 3 стратегических принципа.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ОБХОД ТУПИКОВ, Алгоритм банкира(предложил Дейкстра)

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

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

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

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

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

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

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