Взаимоблокировки. Обнаружение и устранение взаимоблокировок. Предотвращение взаимоблокировок.

Взаимоблокировка процессов

 

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

Ресурсы бывают выгружаемые и невыгружаемые, аппаратные и программные.

Выгружаемый ресурс - этот ресурс безболезненно можно забрать у процесса (например: память).

Невыгружаемый ресурс - этот ресурс нельзя забрать у процесса без потери данных (например: принтер).

Проблема взаимоблокировок процессов возникает при борьбе за невыгружаемый ресурсы.

 

Условия необходимые для взаимоблокировки:

 

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

 

. Обнаружение и устранение взаимоблокировок. Избежание взаимобло-кировок

 

Алгоритмы обнаружения взаимоблокировок с целью их последующего устранения можно представить в виде моделей (графов). Структурными единицами графов будем считать:

 

На такой модели очень хорошо проверить возникает ли взаимоблокировка. Если есть цикл, значит, есть и взаимоблокировка.

При последовательном выполнении процессов взаимоблокировка не возникает (рис. 3.12).

Рис. 3.12. Отсутствие взаимоблокировки

при последовательном выполнении процессов

 

При циклическом выполнении процессов возникает взаимоблокировка (рис. 3.13).

 

 

Рис. 3.13. Возникновение взаимоблокировки

при циклическом выполнении процессов

 

Рассмотрим тот же самый случай, но допустим, что система, зная о предстоящей взаимоблокировке, заблокирует процесс B (рис. 3.14).

 

 

Рис. 3.14. Устранение взаимоблокировки системой

при циклическом выполнении процессов

 

Как видно из рис.3.14, в данном случае взаимоблокировки не возникает.

 

Для избежания взаимоблокировок существуют следующие стратегии:

 

• пренебрежение проблемой в целом (возможно взаимоблокировка не возникнет);
• обнаружение и устранение (взаимоблокировка происходит, но оперативно ликвидируется);
• динамическое избежание взаимоблокировок;
• предотвращение условий возникновения взаимоблокировок.

 

В первом случае, если вероятность взаимоблокировки очень мала, то ею легче пренебречь, т.к. код исключения может очень усложнить ОС и привести к большим ошибкам. Также многие взаимоблокировки тяжело обнаружить. Этот алгоритм используется как в UNIX, так и в Windows. Поэтому (и не только) на серверах часто устанавливают автоматическую перезагрузку (раз в сутки, как правило ночью), если возникнет взаимоблокировка, то после перезагрузки ее не будет.

Во втором случае система не пытается предотвратить взаимоблокировку, а пытается обнаружить ее и устранить. Обнаружить взаимоблокировку можно:

 

• когда запрашивается очередной ресурс;
• через какой-то промежуток времени;
• когда загрузка процессора слишком велика.

После обнаружения взаимоблокировки возможны следующие способы выхода из нее:

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

В третьем случае ОС должна знать наперед, является ли предоставление ресурса безопасным или нет.

 

. Предотвращение взаимоблокировок

 

Для возникновения взаимоблокировок необходим ряд условий. Предотвращение этих условий предотвратит и сами взаимоблокировки.

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

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

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

Предотвращение условия циклического ожидания осуществляется следующими способами:

• прежде чем занять новый ресурс, процесс освобождает старый;
• упорядочение (нумерация) ресурсов, в результате чего процессы запрашивают ресурсы только по порядку.