Безопасные и небезопасные состояния

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

Алгоритм банкира для одного вида ресурса

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

На рис. 7.5, а представлены четыре процесса, каждый из которых получил определенное число единиц ресурса. Всего имеется 10 единиц ресурса. В последней колонке содержится величина максимального запроса ресурса каждым процессом. В некоторый момент возникает ситуация, показанная на рис. 7.5, б. Это состояние безопасно, потому что остались две единиц, и ОС может задержать все запросы, кроме запросов процесса C, таким образом, позволяя процессу C завершиться и вернуть все четыре единицы ресурса.

Рассмотрим, что могло бы произойти, если бы в ситуации на рис. 7.5, б был бы удовлетворен запрос еще одной единицы ресурса для процесса B. Мы попали бы в состояние рис. 4.5, в, не являющееся безопасным. Если бы все процессы запросили свое максимальное число единиц ресурса, то ОС не смогла бы их обеспечить, и мы попали бы в тупик.

Алгоритм банкира можно обобщить для управления системой с несколькими видами ресурсов.

1. Ищем в матрице R строку, соответствующую процессу, чьи неудовлетворенные потребности ресурсов меньше или равны вектору A. Если такой строки не существует, то система, в конце концов, попадет в тупик, т.к. ни один процесс не может проработать до успешного завершения.

Алгоритм банкира для нескольких видов ресурсов

2. Допускаем, что процесс, строку которого выбрали в пункте 1, запрашивает все необходимые ресурсы и заканчивает работу. Отмечаем этот процесс как завершенный и прибавляем все его ресурсы к вектору A.

3. Повторяем шаги 1 и 2 до тех пор, пока или все процессы будут помечены как завершенные – и состояние в этом случае является безопасным, или произойдет взаимоблокировка – тогда состояние небезопасно.

Вопросы для самоконтроля

1. Дайте определение понятию "взаимоблокировка".

2. В чем отличие повторно используемого ресурса от расходуемого ресурса?

3. Приведите примеры расходуемых и повторно используемых ресурсов.

4. В чем отличие монопольного режима от разделяемого режима при доступе к ресурсу?

5. Приведите примеры взаимоблокировок с повторно используемыми ресурсами.

6. Приведите примеры взаимоблокировок с расходуемыми ресурсами.

7. Перечислите условия возникновения взаимоблокировок.

8. Что представляет собой обобщенный ресурсный граф?

9. Дайте определения понятиям "дуга запроса", "дуга назначения", "дуга производителя".

10. Приведите пример графа ресурсов.

11. Как обнаружить взаимоблокировку при наличии одного ресурса каждого типа?

12. Как обнаружить взаимоблокировку при наличии нескольких ресурсов каждого типа?

13. Дайте определение понятиям "безопасное состояние", "небезопасное состояние".

14. Поясните работу алгоритма банкира для одного вида ресурса.

15. Поясните работу алгоритма банкира для нескольких видов ресурсов.

16. Пусть в системе существует два процесса и три одинаковых ресурса. Каждому процессу требуется минимум два ремурса. Возможна ли взаимоблокировка? Объясните ваш ответ