Моделирование взаимоблокировок

Холт (Holt, 1972) показал, как эти четыре условия могут быть смоделированы с использованием направленных графов. У графов имеется два вида узлов: процессы, показанные окружностями, и ресурсы, показанные квадратами.
Направленное ребро, которое следует от узла ресурса (квадрата) к узлу процесса (окружности), означает, что этот ресурс был ранее запрошен, получен и на данный момент удерживается этим процессом. На рис. 6.1, а ресурс R в данное время выделен процессу A.

Направленное ребро, идущее от процесса к ресурсу, означает, что процесс в данное время заблокирован в ожидании высвобождения этого ресурса. На рис. 6.1, б процесс B ожидает высвобождения ресурса S. На рис. 6.1, в мы наблюдаем взаимоблокировку: процесс C ожидает высвобождения ресурса T, который в данный момент удерживается процессом D. Процесс D не собирается высвобождать ресурс T, поскольку он ожидает высвобождения ресурса U, удерживаемого процессом C. Оба процесса находятся в состоянии вечного ожидания. Циклическая структура графа означает, что мы имеем дело с взаимоблокировкой, включившей процессы и ресурсы в цикл (предполагается, что в системе есть только один ресурс каждого типа). В данном примере получился следующий цикл: C—T—D—U—C.

Рис. 6.1. Графы распределения ресурсов: а — ресурс занят; б — запрос ресурса;

в — взаимоблокировка


Рассмотрим пример того, как могут быть использованы графы ресурсов. Представим, что есть три процесса, А, В и С, и три ресурса, Я, Я и Т. Последовательности действий по запросу и высвобождению ресурсов, осуществляемые этими тремя процессами, показаны на рис. 6.2, а—в. Операционная система может в любое время запустить любой незаблокированный процесс, то есть она может принять решение запустить процесс А и дождаться, пока он не завершит всю свою работу, затем запустить процесс В и довести его работу до завершения и, наконец, запустить процесс С.

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

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

6.2, д—к. После выдачи запроса 4 процесс А, как показано на рис. 6.2, з, блокируется в ожидании ресурса Я. На следующих двух этапах процессы В и С также блокируются, что в итоге приводит к зацикливанию и возникновению взаимоблокировки, показанной на рис. 6.2, к.

Но как уже ранее упоминалось, от операционной системы не требовалось запускать процессы в каком-то определенном порядке. В частности, если удовлетворение конкретного запроса может привести к взаимоблокировке, операционная система может просто приостановить процесс, не удовлетворяя его запрос (то есть просто не планируя работу процесса) до тех пор, пока это не будет безопасно. На рис. 6.2, если операционная система знает о грядущей взаимоблокировке, она может приостановить процесс В, вместо того чтобы выделить ему ресурс Я. Запуская только процессы А и С, мы получим такую последовательность действий по запросу и высвобождению ресурсов, которая

Рис. 6.2. Пример возникновения и предупреждения взаимоблокировки



показана на рис. 6.2, л, а не ту, которая показана на рис. 6.2, г. Эта последовательность отображается ресурсным графом, показанным на рис. 6.2, м-с, и не приводит к взаимоблокировке.

По окончании этапа, показанного на рис. 6.2, с, процессу B может быть выделен ресурс S, поскольку процесс A завершил свою работу, а процесс C имеет все необходимое. Даже если B заблокируется при запросе ресурса T, взаимоблокировки не возникнет. Процесс B просто будет ждать, пока процесс C не завершит свою работу.

Далее в этой главе будет подробно рассмотрен алгоритм принятия решений по распределению ресурсов, которые не приводят к взаимоблокировкам. А сейчас нужно понять, что ресурсные графы являются инструментом, позволяющим понять, приводит ли данная последовательность запросов/возвратов ресурсов к взаимоблокировке. Мы всего лишь шаг за шагом осуществляем запросы и возвраты ресурсов и после каждого шага проверяем граф на наличие каких-либо циклов. Если образуется цикл, значит, возникла взаимоблокировка, а если нет, значит, нет и взаимоблокировки. Хотя здесь рассматривался граф ресурсов, составленный для случая использования по одному ресурсу каждого типа, ресурсные графы могут быть применены также для обработки нескольких ресурсов одного и того же типа (Holt, 1972).

Чаще всего для борьбы с взаимными блокировками используются четыре стратегии:

1. Игнорирование проблемы. Может быть, если вы проигнорируете ее, она проигнорирует вас.

2. Обнаружение и восстановление. Дайте взаимоблокировкам проявить себя, обнаружьте их и выполните необходимые действия.

3. Динамическое уклонение от них за счет тщательного распределения ресурсов.

4. Предотвращение за счет структурного подавления одного из четырех условий, необходимых для их возникновения.

В следующих четырех разделах будут рассмотрены по порядку каждый из этих методов.

6.3.

<< | >>
Источник: Э. ТАНЕНБАУМ Х. БОС. СОВРЕМЕННЫЕ ОПЕРАЦИОННЫЕ СИСТЕМ Ы 4-е ИЗДАНИЕ. 2015

Еще по теме Моделирование взаимоблокировок:

  1. Моделирование
  2. МОДЕЛИРОВАНИЕ
  3. Глава 4. Роль моделирования в социологии
  4. МОДЕЛИРОВАНИЕ ИЛИ ПОДРАЖАНИЕ?
  5. Тема 12. Иконологическое моделирование социальных процессов
  6. Уровни моделирования
  7. СОЦИАЛЬНОЕ МОДЕЛИРОВАНИЕ
  8. Тема 4. Роль моделирования в социологии
  9. РАЗДЕЛ 1. Системный и когнитивный аспекты методологии моделирования
  10. 12.1. Иконологическое моделирование
  11. Моделирование стратегий гениев