Проблема тупиков
Тупики и бесконечное откладывание
Проблема тупиков
Рассмотрим случай, когда два процесса монопольно владеют соответственно ресурсом R1 и ресурсом R2. Затем при выполнении каждому из них потребовался ресурс, занятый другим процессом. Такая ситуация возможна, если процессы выполняют запросы на ресурсы в следующей последовательности:
p1: ... p2: ...
запрос R1; запрос R2;
... ...
запрос R2; запрос R1;
... ...
Если система реализует запросы в следующей последовательности:
1) p1 запросил R1;
2) p1 получил R1;
3) p2 запросил R2;
4) p2 получил R2;
5) p1 запросил R2;
6) p1 блокируется или переводится в состояние ожидания R2;
7) p2 запросил R1;
8) p2 блокируется или переводится в состояние ожидания R1;
то оба процесса не могут выполняться дальше. Они попали в тупиковую ситуацию, так как каждый ожидает ресурс занятый другим процессом.
Наиболее наглядно тупики изображаются с помощью модели Холта [], в основе которой лежит направленный граф. Модель содержит узлы, принадлежащие двум множествам: множеству ресурсов и множеству процессов, и стрелки, показывающие запросы на ресурсы и распределения. В графическом виде ресурсы изображаются квадратами, процессы - кружками (рис.5.1).
Тупиковая ситуация (тупик) - это ситуация, возникающая в результате монопольного использования разделяемых ресурсов, когда процесс, владея ресурсом, запрашивает другой ресурс, занятый непосредственно или через цепочку запросов другим процессом, ожидающим освобождения ресурса занятого первым процессом.
Таким образом, процессы блокируют друг друга, и ни один из них не может продолжить выполняться.
Рассмотрим пример не тупиковой ситуации для случая двух процессов и двух ресурсов. Данная ситуация показана на рис.5.2 а), б), в) в соответствии с последовательностью запросов и приобретений. Если система обрабатывает запросы следующим образом:
1) p1 запросил R1;
2) p1 получил R1;
3) p2 запросил R2;
4) p2 блокируется в ожидании R2;
5) p1 запросил R2;
6) p1 получил R2;
7) p1 освободил R1;
8) p1 освободил R2;
9) p2 получил R2;
10) p2 запросил R1;
11) p2 получил R1;
- оба процесса продолжают выполняться.
Тупик становится очевидной проблемой в тот момент, когда он случается. Вероятность тупиков в современных системах, для которых характерно динамическое порождение параллельно выполняющихся процессов и динамическое распределение ресурсов, количество которых изменяется (особенно быстро меняется количество ресурсов типа «сообщение»), увеличивается. Первостепенное значение проблема тупиков имеет для систем реального времени.