Понятие тупиковой ситуации

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

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

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

Причины:

- нехватка ресурсов,

- выход из строя устройств,

- ошибки, допущенные при разработке параллельных программ

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

П1 -> Ф2; П2 -> Ф1.   

Обычно тупик моделируется циклом в графе, состоящем из узлов двух видов: процессы и ресурсы, как показано на рис.1 Стрелки от ресурса к процессу означают, что ресурс выделен данному процессу. Стрелки от процесса к ресурсу означают, что процесс запрашивает данный ресурс.

                                        Рис. 1

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

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

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

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

2. Процесс ожидает выделения дополнительно ресурса, удерживая за собой ресурс уже выделенный ему (условие ожидания ресурса). Т.е. разрешено удерживать объект, в процессе ожидания. Допустима ситуация, когда процесс удерживает одни объекты, запрашивая другие. Если запрос не может быть удовлетворен, процесс блокируется до тех пор, пока нужный ему объект не освободится.

3. Ресурс нельзя отобрать (условие отсутствия перераспределения). Т.е. отсутствует возможность отозвать объект. Операционная система не может отозвать предоставленный процессу объект. Получив доступ к объекту, процесс работает с ним сколько ему необходимо, а затем освобождает.

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

8.2. Методы борьбы с тупиками (предотвращение тупиков)

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

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

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

В общем случае избежать монопольного доступа к ресурсу невозможно. В частности, возможны приемы, когда неделимые ресурсы становятся разделяемыми. Например, операционная система для процессов, запрашивающих принтер, организует формирование промежуточных процессов на диске - разделяемом устройстве (spooling). В любом случае реализованная в системе политика управления параллельным управлением должна быть максимально гибкой. Рассмотрим функцию управления параллельным доступом, которая может быть реализована как часть файлового сервиса операционной системы. Считалось приемлемым, если операционная система обеспечивает монопольную блокировку для записи и блокировку с обеспечением совместного доступа для чтения. Рассмотренная политика является недостаточно гибкой, т. е. она навязывает процессам правила, которые не соответствуют их задачам. Группе процессов иногда требуется возможность параллельной записи в совместно используемые файлы. Однако в определенных ситуациях при параллельном доступе к объектам в целях обеспечения правильности и согласованности их значений процессу в доступе к объекту может быть отказано.

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

Избежать условия ожидания дополнительных ресурсов можно попробовать, применив следующую стратегию (стратегия двухфазного захвата)

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

- Если в первой фазе некоторые запрашиваемые ресурсы были заняты, он освобождает все ресурсы, которые были ему выделены и повторяет первую фазу.

Очевидные недостатки:

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

- Противоречие принципу модульности в программировании (приложение должно знать о запросах к ресурсам во всех модулях).

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

3. Условие отсутствия перераспределения (отсутствует возможность отозвать объект (ресурс)).

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

4. Имеет место круговое ожидание (условие  кругового ожидания)

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

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

Вопросы для самопроверки

1. Что в вычислительных системах понимают под тупиковой ситуацией.

2. Укажите причины возникновения тупиковой ситуации.

3. Каковы необходимые условия возникновения тупика

4. Какие существуют возможности по предотвращению тупиковых ситуаций.

 

Тема № 9. Вопросы безопасности и надежности операционных систем.

План

9.1. Основные аспекты защищенных операционных систем

9.2. Разграничение доступа к объектам операционной системы.

9.3. Механизмы контроля доступа в операционных системах

 

⇐ Предыдущая13141516171819202122Следующая ⇒

Поделиться: