4.6. Проблема тупиков при взаимодействии процессов
Рассмотрим пример.
Есть два процесса Р1 и Р2, два ресурса R1 и R2 и два семафора S1 и S2. Пусть имеют место следующие последовательности выполнения процессов:
P1 P2
... ...
S1.P; Захват R1; S2.P; Захват R2;
... ...
S2.P; Ожидание R2; S1.P; Ожидание R1;
... ...
S2.V; S1.V;
... ...
S1.V; S2.V;
... ...
Оба процесса будут заблокированы на неопределенное время.
Второй пример.
Процесс 1 захватил ресурс, а процесс 2 приостановил процесс 1 и перешел к ожиданию этого же ресурса. Снова оба процесса будут заблокированы на неопределенное время.
Третий пример.
Бесконечное ожидание процесса из-за непродуманных алгоритмов блокировки и активизации процессов. Перечисленные ситуации являются примерами тупиков. Но, строго говоря, к тупикам относят ситуации, похожие на ситуацию первого примера. Т.е. взаимные блокировки процессов при ожидании ресурсов.
Истоки возникновения тупиков лежат в принципах распределения ресурсов в вычислительной системе.
В системах со статическим распределением ресурсов тупики не возникают.
Динамическое распределение ресурсов способствует возникновению тупиков.
Поскольку динамическое распределение ресурсов является основой всех современных многозадачных систем, то понимание причин возникновения тупиков и путей их преодоления имеет большое значение.
Проблема тупиков впервые возникла достаточно давно, в системе пакетной обработки IBM-360. Однако, при всей неприятности тупика в системе пакетной обработки, его можно устранить, перезапустив систему. Гораздо опаснее возникновения тупика в системах реального времени, управляющей каким-нибудь технологическим процессом.
В общем виде проблема тупиков формулируется следующим образом.
Процесс 1 Процесс 2
Захватил R1; Захватил R2;
Ждет R2; Ждет R1;
Широко используются графы в теоретических исследованиях тупиков. (Отметим, что теория тупиков с использованием графов является наиболее удачным примером теоретического исследования операционных систем.)
Отметим, что наличие циклов в графе свидетельствует о потенциальной опасности тупика.
Указанная ситуация была обобщена на любое число процессов, что позволило сформулировать четыре необходимых условия возникновения тупика:
Взаимное исключение - монопольное владение ресурсом. (мы все время добивались обеспечения этого)
Ожидание ресурсов - процессы ждут новых ресурсов, не освобождая уже выделенные.
Неперераспределяемость - процессы сами возвращают ресурсы после использования.
Круговое ожидание - существует кольцевая цепь процессов, от 1 до N, такая что, процесс i захватил ресурс i и ожидает ресурс i+1, занятый процессом i+1.
Существуют два основных направления решения проблемы тупиков.
Предотвращение тупиков, при котором обеспечиваются такие условия функционирования системы, что тупики не возникают вообще. Это, как правило, обеспечивается за счет нерационального использования ресурсов. Такие средства должны использоваться в системах реального времени, где тупиков не должно быть вообще. Примером могут служить алгоритмы монитора, рассмотренные ранее, в которых ситуация бесконечного ожидания процесса, ждущего большого количества ресурса, устранялась за счет ограничения в предоставлении имеющихся ресурсов процессам, требующим малого их количества.
Обнаружение и исправление. Никаких предупредительных мер против тупиков не принимается, но если тупик возник, его обнаруживают и исправляют. Такие методы ориентированы на системы пакетной обработки, т. к. исправление - это всегда перезапуск одного или нескольких, или всех процессов, с начала или с некоторых точек перезапуска. Исправление обычно происходит с потерями информации.
Предотвращение тупиков
Методы предотвращения тупиков делятся на:
Методы априорного предотвращения, которые обеспечивают условия, исключающие саму возможность появления тупика за счет жестких требований к процессам с точки зрения их запросов к ресурсам;
Методы обхода, более мягкие по своим ограничениям.
Методы априорного предотвращения тупиков
Как доказано в теории тупиков, если снято хотя бы одно из четырех условий возникновения тупика, то тупик возникнуть не может.
Поэтому методы априорного предотвращения заключаются в снятии одного из трех условий возникновения тупиков, кроме первого - взаимного исключения.
Требование взаимного исключения остается всегда!
Метод глобального предотвращения снимает условие возникновения тупиков. Каждый процесс заранее запрашивает все необходимые ресурсы и не запускается до тех пор, пока эти ресурсы не будут ему предоставлены. Затем, когда процесс выполняется, он уже не ждет ресурсов. Это очень жесткое требование, которое на практике может исключить вообще всякий параллелизм выполнения процессов.
Нарушение условия неперераспределяемости. Если процесс, владеющий одним ресурсом, запрашивает другой ресурс и вынужден ждать его, то он освобождает и ранее захваченный ресурс, а затем запрашивает его вместе со вторым. Данный способ тоже является чрезвычайно жестким.
Метод упорядоченных ресурсов устраняет условие кругового ожидания. Ресурсы делятся на классы К1, К2,..., Кк. Порядок запроса ресурсов всеми процессами определяется классами. Процесс может запросить и получить ресурс из класса Кi, если он освободил ресурс из класса Кi-1. Таким образом, разрывается цикл кругового ожидания. Данный способ тоже является чрезвычайно жестким и неудобным. Если процессу требуется получение ресурсов в порядке, отличном от порядка классов ресурсов, то он не сможет функционировать в системе.
Алгоритм банкира - алгоритм обхода тупиков
Алгоритм банкира предложен Дейкстрой и имитирует работу банка по выдаче займов и приему платежей.
Каждый процесс заранее указывает верхнюю границу запросов на каждый ресурс.
Алгоритм при каждом запросе просчитывает, может ли система попасть в тупик или нет, если выдаст процессу требуемое количество ресурсов.
Если выдача ресурсов может привести систему к тупику, то ресурс не выдается, а процесс переходит в состояние ожидания.
Если тупик возникнуть не может, то ресурс выдается процессу.
Вводятся понятия надежного и ненадежного состояния.
Состояние является надежным, если из него нельзя оказаться в тупике.
Состояние ненадежно, если из него можно оказаться в тупике.
Система так выдает ресурсы процессам, чтобы все время находиться в надежном состоянии.
Известно общее количество ресурсов данного вида, которое имеется в системе, и максимальное количество ресурсов данного вида, которое может запросить каждый из процессов.
Пример надежного состояния.
Всего ресурсов - 12. Остаток - 2.
|
Выделено |
Макс. Потребность |
Процесс 1 |
1 |
4 |
Процесс 2 |
4 |
6 |
Процесс 3 |
5 |
8 |
Почему это состояние является надежным?
Предположим, что процесс 1 запросил 2 ресурса.
Дать их ему или нет?
Предположим, что дать.
Тогда ситуация сложится следующим образом. Всего ресурсов - 12. Остаток - 0.
|
Выделено |
Макс. Потребность |
Процесс 1 |
3 |
4 |
Процесс 2 |
4 |
6 |
Процесс 3 |
5 |
8 |
Каждый из процессов еще может запросить ресурсы по своему протоколу, а свободных ресурсов нет в наличии. Это может привести к тупиковой ситуации. Поэтому запрос процесса 1 на 2 ресурса будет отложен. Предположим, что процесс 2 запросил 2 ресурса. Дать их ему или нет?
Условие функционирования процессов следующее. После получения максимального количества ресурсов они все ресурсы отдают системе и завершают свою работу. Это означает, что получив 6 ресурсов, процесс 2 успешно завершится и вернет их системе. Свободных ресурсов будет 6 и их хватит процессам 1 и 3, чтобы завершить работу. Т. е. все три процесса могут успешно завершить работу. Поэтому такое состояние является надежным.
Пример ненадежного состояния.
Всего ресурсов - 12. Остаток - 1.
|
Выделено |
Макс. Потребность |
Процесс 1 |
1 |
4 |
Процесс 2 |
4 |
6 |
Процесс 3 |
6 |
8 |
Каждый из процессов может запросить по своему протоколу еще ресурсы, но их нет в наличии.
Отметим, что это не обязательно тупик. Это – опасность возникновения тупика при определенном варианте появления запросов.
Очевидно, что из надежного состояния можно попасть в ненадежное, если раздавать ресурсы беспорядочно.
Например, при первой таблице удовлетворить запрос процесса 1 на 2 ресурса.
Алгоритм банкира так выдает ресурсы, что система переходит из одного надежного состояния в другое до завершения всех процессов.
Запрос, который приведет систему к ненадежному состоянию, откладывается до момента, когда он сможет выполниться.
Таким образом, алгоритм при каждом запросе ресурсов строит прогноз на надежность всех состояний до завершения всех процессов.
Если в прогнозе на определенном этапе выявляется ненадежное состояние, т. е. появляются процессы, которые не смогут завершиться, то запрос откладывается, а процесс блокируется.
Если в прогнозе все процессы смогут завершиться, то запрос удовлетворяется.
Замечания по алгоритму банкира
Алгоритм банкира показывает возможность решения проблемы тупиков в принципе.
Алгоритм обладает рядом ограничений:
Алгоритм исходит из фиксированного количества ресурсов, хотя на самом деле оно может меняться;
Алгоритм исходит из фиксированного количества процессов, хотя оно тоже может меняться на самом деле;
Алгоритм требует возвращения ресурсов процессами в конечное, но не определенное, время;
Алгоритм требует, чтобы процессы заранее объявили о максимальном количестве используемых ими ресурсов, что не всегда возможно;
Алгоритм предполагает, что процессы завершаются, использовав однажды требуемое количество ресурсов, не ясно как быть с процессами типа «бесконечный цикл»;
Сам просчет надежности состояния приводит к затратам времени.
Алгоритм Габермана обхода тупиков
Алгоритм Габермана отличается от алгоритма банкира исходными условиями функционирования процессов.
Ресурсы не делятся на доли, но по-прежнему необходимо знать заранее, какие ресурсы может использовать каждый из процессов.
Данные условия представляются в виде следующей матрицы:
Процессы Ресурсы
A B C D E
Р1 1 1
Р2 1 1 1
Р3 1 1 1
Р4 1 1 1
При каждом запросе ресурса строится граф следующего вида:
Вершины - процессы;
Дуга jk между вершинами j и k существует, если процесс j использует ресурс, который может запросить процесс k.
Например, Р4 использует ресурс С:
Если при запросе ресурса появится цикл в графе, то такое состояние считается ненадежным и запрос откладывается.
Обнаружение тупиков
Обнаружение тупика - это установление факта, что возникла тупиковая ситуация, а также определение процессов и ресурсов, вовлеченных в тупик.
Алгоритмы обнаружения могут выполняться с любой требуемой частотой и часто выполняются при отказе в запросе ресурса.
Стратегии распознавания тупиков основаны на моделировании развития каждого незаблокированного процесса.
Незаблокированный процесс приобретает все ресурсы, в которых он нуждается, освобождает все занятые им ресурсы и прекращает работу.
Освобождение ресурсов позволяет продолжить выполнение другим процессам, ранее заблокированным.
Это моделирование продолжается до тех пор, пока не останется незаблокированных процессов.
Если таковые остались, то система находится в состоянии тупика.
Для моделирования такой процедуры широко используются графы.
Завершение работы процесса и возвращение всех ресурсов системе эквивалентно тому, что вершина процесса становится изолированной.
Такая операция называется редукцией графа на процесс.
Если граф можно редуцировать на все процессы, то это означает, что тупиковой ситуации нет.
А если остались нередуцированные процессы, то они и составляют группу процессов, вовлеченных в тупик.
Для обнаружения тупика может быть использован алгоритм банкира.
Если в текущем состоянии системы при данном наборе запросов нельзя найти полную последовательность надежных состояний, то система находится в состоянии тупика.
Заметим, что оба метода - редуцирование графа состояний системы и алгоритм банкира - это одно и то же.
Различие состоит в форме представления состояния системы.
Восстановление после тупиков
Самый эффективный способ восстановления после тупиков – это использование механизмов приостановки/возобновления процессов.
Существующие механизмы восстановления обычно состоят в принудительном выводе некоторого процесса из системы, чтобы можно было использовать его ресурсы.
Перечислим методы восстановления по степени уменьшения их "грубости".
Перезапуск всех процессов - перезагрузка.
Принудительное завершение процессов, находящихся в тупике.
Принудительное завершение процессов, находящихся в тупике, но - по одному. Возможно, на определенном этапе тупик рассосется.
Перезапуск процессов с контрольных точек.
Нормальное завершение незаблокированных процессов.