Тупики.
При рассмотрении проблемы тупиков, понятия ресурсов системы целесообразно обобщить и разделить их все на два класса:
- повторноиспользуемые (системные) типа SR;
- потребляемые или расходуемые типа CR.
Повторноиспользуемый ресурс- конечное множество идентичных единиц со свойствами:
1. число единиц ресурса постоянно;
2. каждая единица ресурса или доступна или распределена только одному ресурсу;
3. процесс может освободить единицу ресурса, только если он ранее получил эту единицу, т.е. не какой процесс не может оказывать влияние ни на один ресурс если он ему не принадлежит.
Расходуемый ресурс обладает свойствами:
1. число свободных единиц изменяется, по мере того как приобретается и освобождается отдельные их элементы выполняющимися процессами и такое число единиц ресурса потенциально неограниченно;
2. процесс потребитель уменьшает число единиц ресурса, приобретая одну или более единиц. Единицы ресурса, которые приобретены, не возвращаются ресурсу.
тупик:
Р1
Послать сообщение (Р2, М1,ПЯ2)
Ждать сообщение (Р3, М3,ПЯ1)
Р2
Послать сообщение (Р3, М2,ПЯ3)
Ждать сообщение (Р1, М1,ПЯ2)
Р3
Послать сообщение (Р1, М3,ПЯ1)
Ждать сообщение (Р2, М2,ПЯ3)
Группа процессов находится в тупиковой ситуации, если каждый процесс из группы ожидает события, которое может вызвать только другой процесс из этой же группы. Из- за того, что все процессы находятся в состоянии ожидания ни один из них не будет причиной какого- либо события, которое могло бы активизировать другой процесс в группе и все процессы могут ждать до бесконечности. Т.е. каждый участник в группе процессов зашедший в тупик доступ к ресурсу, принадлежащему другому процессу. Количество процессов и количество видов ресурсов не имеет значения.
Для возникновения ситуации взаимоблокировки должны выполнится 4-е условия:
1. Условие взаимного исключения, при котором процесс осуществляет монопольный доступ к ресурсу;
2. Условие ожидания и удержания. Процессы в данный момент удерживающие полученные ранее ресурсы могут запрашивать новые ресурсы;
3. Условие отсутствия принудительной выгрузки ресурса. У процесса нельзя забрать ранее полученные ресурсы пока он сам не освободит их;
4. Условие циклического ожидания. Должна существовать круговая последовательность из двух или более процессов, каждый из которых ждет доступа к ресурсу удерживаемому следующим членом последовательности.
При столкновении со взаимоблокировкой используется 4-е стратегии:
1. Пренебрежение проблемой в целом;
2. Обнаружение и восстановление, т.е. позволить взаимоблокировке произойти, обнаружить ее и предпринять какие- либо действия;
3. Динамическое избежание тупиковых ситуаций с помощью аккуратного распределения ресурсов (или обход тупиков);
4. Предотвращение тупиков с помощью опровержения условий необходимых для взаимоблокировки.
Распознавание тупика с последующим восстановлением. При использовании этого метода при попадании системы в тупик она старается определить, когда это случилось и за тем совершает некоторые действия по возврату системы в состояние имевшему место до того как система попала в тупик.
Обнаружение взаимоблокировки при наличии одного ресурса каждого типа
Рассмотрим ситуацию на примере. Для системы можно сконструировать граф ресурсов, если этот граф содержит один или более циклов значит, произошла взаимоблокировка и заблокированы все процессы являющиеся частью цикла.
Система имеет 7-6 процессов и 6 ресурсов. Состояние системы на данный момент соответствует списку:
1. Процесс П1 занимает ресурс Р1 и хочет получить Р2;
2. Процесс П2 ничего не использует, но хочет получить Р3;
3. Процесс П3 ничего не использует, но хочет получить Р2;
4. Процесс П4 занимает ресурс Р4 и хочет получить Р2 и Р3;
5. Процесс П5 занимает ресурс Р3 и хочет получить Р5;
6. Процесс П6 занимает ресурс Р6 и хочет получить Р2;
7. Процесс П7 занимает ресурс Р5 и хочет получить Р4.
Рассмотрим алгоритм, который изучает граф и завершается когда находит цикл или когда показывает, что цикла нет. В алгоритме используется структура данных называющаяся список узлов L. Во время работы алгоритма на ребрах графа ставится метка, говорящая о том, что ребро проверено. Для каждого узла N выполняется 5 шагов:
1. Задаются начальное условие: L- пустой список(все ребра не маркированные);
2. Текущий узел добавляется в конец списка L и проверяется количество появлений узла в списке. Если узел присутствует в двух местах, значит, граф содержит цикл и работа алгоритма завершается;
3. Для заданного узла определяется, выходит ли из него хотя бы одно не маркированное ребро, если да то к шагу 4, нет то к 5;
4. Выбирается любое, не маркированное исходное ребро, помечается и за тем по нему осуществляется переход к новому текущему узлу и выполняется шаг 3;
5. Система в тупике. Удаляется последний узел из списка и происходит возврат к предыдущему узлу, т.е. к тому который был текущим перед тупиковым узлом. Если это первоначальный узел, то граф не содержит циклов и происходит завершение алгоритма.
Обнаружение взаимоблокировки при наличии нескольких ресурсов каждого типа. При рассмотрении используются матрицы, в которых:
m- число классов ресурсов,
В любой момент времени некоторые из ресурсов могут оказаться заняты следовательно, вводится понятие A- вектор доступных ресурсов, C- матрица текущего распределения, R- матрица запросов.
Матрица текущего распределения показывает, какие и сколько ресурсов в данный момент использует процесс
R- показывает сколько ресурсов может потребоваться каждому процессу.
Для обнаружения тупиков нужно составить матрицу.
Алгоритм обнаружения взаимоблокировки основан на обнаружении векторов. Пусть в исходном положении все процессы не маркированы. По мере продвижения алгоритма на процессы будет ставиться отметка служащая признаком того что они могут закончить свою работу т.е. они не находятся в тупике.
После завершения алгоритма известно, что любой, не маркированный процесс, находится в тупике.
Алгоритм обнаружения тупиков состоит из шагов:
1. Ищем не маркированный процесс,
2. Если такой процесс найден, то прибавляем i-ю строку матрицы текущего распределения С к вектору А, маркируем процесс и возвращаемся к шагу 1;
3. Если таких процессов не существует, то работа алгоритма завершается.
Завершение алгоритма означает, что все, не маркированные процессы, находятся в тупике.
На первом шаге алгоритм ищет процесс, который может доработать до конца, такой процесс характеризуется тем, что все требуемые для него должны находится среди доступных в данный момент ресурсов. Тогда выбираемый процесс проработает до своего завершения и после этого вернет ресурсы, которые он занимал в общий фонд доступных ресурсов. Если окажется, что все процессы могут работать, тогда не один из них в данный момент не заблокирован и может быть выбран для работы. Если некоторые из процессов никогда не смогут запуститься, значит, они попали в тупик.
Восстановление при помощи принудительной выгрузки ресурса. Иногда можно временно отобрать ресурс у его текущего ресурса и отдать его другому владельцу. Возможность забирать ресурс у процесса в значительной мере зависит от свойств ресурса. Большинство процессов владеющие ресурсом не могут отдать его другому процессу.
Восстановление через откат. Если разработчики системы знают о вероятности появления взаимоблокировки, то они могут организовать работу так что бы процессы периодически создавали контрольные точки, т.е.
запись состояния процесса в файл из которого он может быть возобновлен. Контрольные точки содержат не только образ памяти, но и состояние ресурсов. Для большей эффективности во время выполнения процесса образуется целая последовательность контрольных точек. Когда тупик обнаружен, достаточно понять, какие ресурсы необходимы процессам. Что бы выйти из тупика процесс занимает необходимый ресурс и откатывается к тому моменту времени перед которым он получил данный ресурс для чего зап-ся с одной из его контрольных точек. Освобожденный ресурс предоставляется одному из процессов попавших в тупик, если возобновленный процесс снова пытается получить данный ресурс, то ему придется ждать, когда ресурс станет свободным.
Восстановление путем уничтожения процессов. Простейший способ выхода из тупиковой ситуации заключается в уничтожении одного или нескольких процессов. Можно уничтожить процесс находящийся в цикле взаимоблокировки или процесс не находящийся в цикле, что бы он освободил свои ресурсы.
