Способы предотвращения тупиков

Условия возникновения тупиков

Условия возникновения тупиков были сформулированы Коффманом, Элфиком и Шошани в 1970 г.:

1. Условие взаимоисключения (Mutual exclusion). Одновременно использовать ре­сурс может только один процесс.

2. Условие ожидания ресурсов (Hold and wait). Процессы удерживают ресурсы, уже выделенные им, и могут запрашивать другие ресурсы.

3. Условие неперераспределяемости (No preemtion). Ресурс, выделенный ранее, не может быть принудительно забран у процесса. Освобождены они могут быть только процессом, который их удерживает.

4. Условие кругового ожидания (Circular wait). Существует кольцевая цепь про­цес­сов, в которой каждый процесс ждет доступа к ресурсу, удерживаемому дру­гим процессом цепи.

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

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

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

1) Способы предотвращения тупиков путем тщательного распределения ре­сур­сов. Алгоритм банкира

Можно избежать взаимоблокировки, если распределять ресурсы, придержива­ясь определенных правил. Среди такого рода алгоритмов наиболее известен алго­ритм банкира, предложенный Дейкстрой, который базируется на так называемых безопасных или надежных состояниях (safe state). Безопасное состояние – это такое состояние, для которого имеется по крайней мере одна последовательность собы­тий, которая не приведет к взаимоблокировке. Модель алгоритма основана на дей­ствиях банкира, который, имея в наличии капитал, выдает кредиты.

Суть алгоритма состоит в следующем.

· Предположим, что у системы в наличии n устройств, например лент.

· ОС принимает запрос от пользовательского процесса, если его максимальная потребность не превышает n.

· Пользователь гарантирует, что если ОС в состоянии удовлетворить его за­прос, то все устройства будут возвращены системе в течение конечного времени.

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

· В соответствии с алгоритмом банкира выделение устройств возможно, только если состояние системы остается надежным.

2) Предотвращение тупиков за счет нарушения условий возникновения тупиков

В отсутствие информации о будущих запросах единственный способ избежать взаимоблокировки – добиться невыполнения хотя бы одного из условий раздела «Условия возникновения тупиков».

a) Нарушение условия взаимоисключения

В общем случае избежать взаимоисключений невозможно. Доступ к некоторым ресурсам должен быть исключительным. Тем не менее некоторые устройства удает­ся обобществить. В качестве примера рассмотрим принтер. Известно, что пытаться осуществлять вывод на принтер могут несколько процессов. Во избежание хаоса ор­ганизуют промежуточное формирование всех выходных данных процесса на диске, то есть разделяемом устройстве. Лишь один системный процесс, называемый серви­сом или демоном принтера, отвечающий за вывод документов на печать по мере ос­вобождения принтера, реально с ним взаимодействует. Эта схема называется спу­лингом (spooling). Таким образом, принтер становится разделяемым устройством, и тупик для него устранен.

К сожалению, не для всех устройств и не для всех данных можно организовать спулинг.

b) Нарушение условия ожидания дополнительных ресурсов

Условия ожидания ресурсов можно избежать, потребовав выполнения страте­гии двухфазного захвата:

· В первой фазе процесс должен запрашивать все необходимые ему ресурсы сразу. До тех пор пока они не предоставлены, процесс не может продолжать выпол­нение.

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

В известном смысле этот подход напоминает требование захвата всех ресурсов заранее. Естественно, что только специально организованные программы могут быть приостановлены в течение первой фазы и рестартованы впоследствии.

Таким образом, один из способов – заставить все процессы затребовать нужные им ресурсы перед выполнением («все или ничего»). Если система в состоянии выде­лить процессу все необходимое, он может работать до завершения. Если хотя бы один из ресурсов занят, процесс будет ждать.

c) Нарушение принципа отсутствия перераспределения

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

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

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

d) Hарушение условия кругового ожидания

Трудно предложить разумную стратегию, чтобы избежать последнего условия из раздела «Условия возникновения тупиков» – циклического ожидания.

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

Задачи синхронизации при использовании разделяемых ресурсов

Дата добавления: 2014-01-07