1.3.5. Проблема тупиков и методы борьбы с тупиками
Понятие тупика двух процессов
Тупиком называется такое состояние вычислительной системы, при котором два или более процессов находятся в заблокированном состоянии и каждый из них ожидает освобождения ресурса, занятого другим процессом.
Заблокированные процессы не потребляют время ЦП, но удерживают ресурсы и не выполняют полезной работы.
Модель Холта
Процессы представляются квадратами, а ресурсы – кружками, в которых показано количество ресурсов. Дуга, соединяющая процесс и ресурс, означает запрос единицы ресурса.
Рисунок 1-9 запрос 2 х единиц R1
Дуга, соединяющая ресурс и процесс – показывает выделение ресурса процессу.
Рисунок 1-10 - P2 владеет одной единицей ресурса R2
Пример модели Холта.
Рисунок 1-11 –модель Холта граф используемых ресурсов
В некоторый момент времени P1 запрашивает 2 единицы R1 и запрашивает 1 единицу R2. P2 – запрашивает 1 единицу R2 и владеет 2 единицами R1.
Каждому процессу нужны все требуемые ресурсы, чтобы он мог продолжить выполнение. Предположим, что процесс Р1 получил бы теперь запрошенную им единицу R2. Если удовлетворить запрос Р1 на ресурс R2 это может привести к тупиковой ситуации. P1 не сможет продолжиться до тех пор, пока Р2 не освободит единицу ресурса R1, а процесс Р2 не сможет продолжиться до тех пор, пока Р1 не освободит единицу R2.
Если не удовлетворить Р1 – отдать Р2 – он завершится.
Пример тупика двух конкурирующих процессов.
Процесс_1 Процесс_2
* *
* *
1: P(S2); 5: P(S1);
* *
* *
2: P(S1); 6: P(S2);
* *
* *
3: V(S1); 7: V(S1);
* *
* *
4: V(S2); 8: V(S2);
* *
Возникновение тупика возможно, Если выполнена последовательность 1..5 – теперь тупик неизбежен.
Условия возникновения тупика
Для возникновения тупика необходимо одновременное выполнение 4-х условий.
Взаимного исключения, при котором процессы имеют монопольный доступ к ресурсам;
Ожидания, при котором процесс, запрашивающий ресурс, ждет до тех пор, пока запрос не будет удовлетворен, удерживая ранее полученные ресурсы;
отсутствия перераспределения ресурсов – выделенные ресурсы нельзя отобрать у процесса;
кругового ожидания, при котором существует замкнутая цепь процессов, каждый из которых ждет ресурс, удерживаемый его предшественником в этой цепи.
Методы борьбы с тупиками
Имеются 3 метода:
предотвращение тупика (самый дорогой);
обход тупика;
распознавание тупика с последующим восстановлением.
Предотвращение тупика.
Дисциплина, предотвращающая тупик, должна гарантировать, что не может возникнуть какое-либо из четырех условий, необходимых для его наступления.
1 условие – условие взаимного исключения – можно устранить путем разрешения неограниченного разделения ресурсов. Это удобно для повторно-входимых программ и ряда драйверов, но совершенно неприемлемо к совместно используемым переменным в критических интервалах.
2 условие – условие ожидания - можно устранить, предварительно выделяя ресурсы. Процесс может начать исполнение, только получив все ресурсы. Не всегда заранее известны все ресурсы, необходимые процессу.
3 условие – условие отсутствия перераспределения – можно исключить, позволяя операционной системе отнимать у процесса ресурсы. Для этого в операционной системе должен быть предусмотрен механизм запоминания состояния процесса с целью последующего восстановления.
4 условие – условие кругового ожидания – исключить можно, предотвращая образование цепи запросов. Это можно сделать, если ресурсам приписать определенные номера. Все запросы на ресурсы должны выполняться в порядке возрастания номеров ресурсов. Если запросы следуют в порядке возрастания номеров, - 1,2,3,4 – то они удовлетворяются по мере того, как ресурсы становятся доступными.
Процесс, имеющий ресурс i-го уровня, в дальнейшем может потребовать только ресурсы i+1-го уровня. После того, как процесс получил, а потом освободил ресурсы данного уровня, он может запросить ресурсы на том же самом уровне. Освободить процесс i-го уровня можно только после освобождения всех ресурсов на более высоких уровнях.
Например, имеются процессы P1, P2, ресурсы R1, R2; уровни R1 – 1, R2 – 2. Если P1 получил R1, он может получить R2. Но P2 не может получить R2, пока не получит R1. Т.о. создание замкнутой цепи невозможно. Иерархическое выделение ресурсов часто не дает никакого выигрыша, если порядок использования ресурсов, определенный в описании процессов, отличается от порядка уровней иерархии. В этом случае ресурсы будут использоваться крайне неэффективно.
В целом стратегия предотвращения тупиков – это дорогое решение проблемы, и оно используется нечасто.
2. Обход тупиков.
Обход тупика – это запрет входа в опасное состояние (такое состояние, которое может привести к тупику).
Для обхода тупика перед выделением ресурса необходимо проверить, не приводит ли выделение ресурсов к опасному состоянию, и если да – ресурс выделять нельзя.
Необходимо иметь информацию о максимальных потребностях процессов в ресурсах.
Ресурсы должны быть одного типа.
Например, имеем 6 единиц ресурса и 2 процесса
|
Имеет |
Требует |
Максимальная потребность |
“Остаток” потребностей |
||
Р1 |
1 |
3 |
5 |
1 |
||
Р2 |
2 |
2 |
4 |
0 |
||
|
3 |
Резерв-3 |
9>6 |
|
||
возможны тупики!
1. Удовлетворение запроса Р1 – приведет к продолжению его выполнения – но состояние будет опасным – если он запросит еще – то ни Р1, ни Р2 не будут выполняться.
2. Удовлетворение запроса Р2 – он завершится.
Обход тупиков – это процесс определения, для каждого требования (предполагается, что требование удовлетворено), будет ли полученное состояние системы безопасным. Задача решается с помощью алгоритма банкира Дейкстры (практически не используется).
Его ограничения:
количество ресурсов в системе должно быть постоянным;
необходимо заранее указывать потребности в ресурсах;
число работающих процессов должно оставаться постоянным.
3. Распознавание с последующим восстановлением.
Данный метод основан на распознавании тупика и принудительном освобождении всех ресурсов попавших в тупик процессов. Обнаружение тупика возможно с помощью графа повторно используемых ресурсов (модель Холта).