Комбинированный подход к обработке тупиков

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

Ключевые термины

Алгоритм банкира (banker’s algorithm) - алгоритм Э. Дейкстры для избежания тупиков при распределении ресурсов операционной системой.

Безопасная последовательность процессов – такая последовательность процессов <P₁, … P_n>, что для каждого процесса P_i ресурсы, которые он может запросить, могут быть выделены из текущих доступных ресурсов и ресурсов, удерживаемых процессами P_j, где j < i.

Безопасное состояние – состояние, перевод системы в которое не приведет к появлению тупиков.

Граф wait-for - ориентированный граф, вершины в которой соответствуют процессам, а дуга проводится из вершины P_i в вершину P_j, если процесс P_i ожидает процесса P_j.

Дуга потребности (claim edge) – дуга в графе распределения ресурсов, которая ведет из вершины-процесса в вершину- ресурс, обозначается пунктирной линией и означает, что данный процесс может потребовать данный ресурс.

Краткие итоги

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

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

Добавим к графу распределения ресурсов (лекция 13) новый вид дуг – дуги потребности. Она ведет из вершины-процесса в вершину- ресурс, обозначается пунктиром и означает, что процесс может потребовать данный ресурс. Дуга потребности преобразуется в дугу присваивания, когда система фактически выделяет данный ресурс процессу. При освобождении ресурса дуга присваивания преобразуется обратно в дугу потребности.

Алгоритм банкира (Э. Дейкстра) – алгоритм распределения ресурсов операционной системой, обеспечивающий избежание тупиков. Его условия и принципы: возможны множественные экземпляры ресурсов; каждый процесс должен априорно обозначить свои максимальные потребности в ресурсах; при запросе ресурса возможно ожидание процесса; после получения ресурсов процесс должен вернуть их за ограниченный период времени. Для работы алгоритма используются вектор доступности ресурсов каждого вида, матрица максимальных потребностей процессов, матрица фактического выделения системой ресурсов процессам, матрица оставшихся потребностей процессов в ресурсах.

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

Основной алгоритм банкира – алгоритм запроса ресурсов для процесса. Он проверяет, не превысил ли процесс свои максимальные потребности (иначе – исключительная ситуация). Далее проверяется, не превышает ли запрос имеющихся объемов доступных ресурсов, иначе – ожидание процесом их освобождения. Если все необходимые ресурсы для удовлетворения запроса имеются, алгоритм вычисляет новое состояние после удовлетворения запроса и проверяет его безопасность. Если новое состояние безопасно, запрос удовлетворяется. Если нет, происходит откат, и процесс ожидает освобождения необходимых ресурсов.

Другая возможная стратегия – обнаружение тупиков: позволить системе войти в состояние тупика, применить алгоритм обнаружения тупиков и выполнить схему восстановления после тупика. Если каждый ресурс существует в единственном экземпляре, для обнаружения тупиков используется граф wait-for, в котором вершины соответствуют процессам, а дуга ведет из вершины A в вершину B, если процесс A ожидает процесса B. Сложность алгоритма обнаружения цикла в графе wait-for – O(n**2), где n – число процессов.

Если имеются множественные экземпляры ресурсов, то для обнаружения тупиков используется алгоритм, аналогичный алгоритму построения безопасной последовательности процессов. Его сложность – O (m * n**2), где m – число типов ресурсов.

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

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

Вопросы для самопроверки:

1. Что такое безопасное состояние системы?

2. Что такое безопасная последовательность процессов?

3. Есть ли в системе тупики, если система находится в безопасном состоянии?

4. Возможны ли в системе тупики, если она находится в небезопасном состоянии?

5. В чем суть стратегии избежания тупиков?

6. Что такое дуга потребности в графе распределения ресурсов?

7. В какую дугу преобразуется дуга потребности при фактическом выделении ресурса?

8. В какую дугу преобразуется дуга присваивания при освобождении ресурса?

9. Каковы основные принципы алгоритма банкира?

10. Какие структуры данных используются для алгоритма банкира?

11. В чем идея и каковы основные шаги алгоритма определения того, является ли состояние системы безопасным?

12. В чем идея и каковы основные шаги алгоритма удовлетворения запроса процесса?

13. В каких случаях в алгоритме банкира процесс должени ждать освобождения ресурсов?

14. В какой момент проверяется безопасность следующего состояния в алгоритме банкира?

15. В чем основные принципы стратегии обнаружения тупиков?

16. Что такое граф wait-for и как он используется для обнаружения тупиков?

17. В чем идея и каковы основные шаги алгоритма обнаружения тупиков для ресурсов с множественными экземплярами?

18. Как происходит восстановление системы после тупика?

19. По каким принципам выбирается процесс-жертва, который необходимо прекратить для ликвидации тупика?

20. Почему при многократном выборе процессов-жертв для выхода из тупиков возможно голодание процессов?

Упражнения

1. Реализуйте граф распределения ресурсов с дугами потребностей, запросов и присваиваний и операциями преобразования дуги потребностей и дугу присваивания и обратно.

2. Реализуйте алгоритм проверки безопасности состояния системы.

3. Реализуйте основной алгоритм банкира – удовлетворение запроса процесса.

4. Ответьте на вопросы в примере использования алгоритма банкира.

5. Реализуйте граф wait-for и алгоритм обнаружения циклов в нем.

6. Реализуйте алгоритм обнаружения тупиков.