Проблема тупика и ее решение

Размещено на http://www.allbest.ru/

Проблема тупика и ее решение

Максаков Павел Александрович

ФГБОУ ВО «Брянский государственный университет имени академика И. Г. Петровского»

Брянск, Россия

Резюме: В статье рассматривается понятие тупика, методы и пути ее обхода и предотвращения, приводятся примеры тупиковых ситуаций.

Ключевые слова: тупик, проблема тупика, тупиковые ситуации, самостоятельная работа, дедлок.

Summary: The article discusses the concept of deadlock, the ways to prevent it. There are also given examples of deadlocks.

Keywords: independent work, deadlock, deadlock prevention,

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

Простейший способ возникновения тупика был продемонстрирован Холтом в программе, написанной им на языке PL/I (листинг 1).

Листинг 1

FUNCTION: PROCEDURE OPTIONS(MAIN, TASK);

WAIT(EVENT);

END FUNCTION;

Данный процесс никогда не получит сигнала о прекращении события EVENT. Системе придется самостоятельно обнаружить зависание процесса и только потом аннулировать задание. Обычно такие ошибки замечаются системой

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

Рисунок 1 - Транспортная пробка как пример тупика

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

Рисунок 2 - Простой пример тупика при распределении ресурсов

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

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

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

Широко известны 2 метода борьбы с тупиковыми ситуациями:

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

Обход тупика;

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

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

Условие взаимного исключения

Условие ожидания

Условие отсутствия перераспределения

Условие кругового ожидания

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

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

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

Четвертое условие ограничивается через разрешение неограниченного разделения ресурсов.

Обход тупика можно трактовать как запрет входа в опасное состояние.

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

Алгоритм банкира - классический пример решения данной задачи. Принятие решение в отношении клиента складывается из информации о запросах клиента и свободных денежных средствах банка.

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

тупик опасный обход запрет

Таблица 2 - Пример алгоритма банкира 1

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

Большинство способов борьбы с проблемой, не смотря на кажущуюся простоту, являются достаточно ресурсозатратными, а методы их реализации совершенно неприменимы в современных мультипроцессорных системах. Так, способ обхода тупиков (на примере алгоритма банкира) для корректной работы требует, чтобы количество ресурсов в системе было фиксировано, максимальные потребности в ресурсах были строго определены, а число активных процессов оставалось постоянным. Предотвращение же тупиков (запрет опасных состояний) требует ограничения 4-х условий. Условие взаимного исключения подавляется путем разрешения неограниченного разделения ресурсов, что неприемлемо к совместно используемым переменным. Условие ожидания подавляется предварительным выделением ресурсов, но при этом общее число затребованных ресурсов не может превышать возможности системы. Поэтому эффективность работы системы может снижаться. Запрет условия отсутствия перераспределения реализуется достаточно легко, но перераспределение устройств ввода/вывода является нежелательным. Условие кругового ожидания исключается с помощью принципа иерархического выделения ресурсов, но он часто не дает никакого выигрыша, если порядок использования ресурсов, отличается от порядка уровней иерархии.

Данная проблема чаще нивелируется в современных ОС, т.к. они используют меньше неразделяемых ресурсов.

Список литературы

Теория сетей Петри и моделирование систем /Питерсон Дж - М.: Мир, 2012. -19с.

Операционные системы. / Гордеев А. В - СПб: Питер,2001 - 204с.

Элементы операционных систем. Введение для пользователей. / Кейлитерт П. В - М: Мир,2001. - 16с.

Размещено на Allbest.ru