Добавлен: 29.10.2018
Просмотров: 48186
Скачиваний: 190
6.1. Ресурсы
491
Все эти семафоры получают исходное значение, равное 1. С таким же успехом могут
использоваться и мьютексы. Перечисленные ранее три этапа затем воплощаются
в применение к семафору вызова down для получения ресурса, использование ресурса
и, в завершение, применение вызова up при высвобождении ресурса. Эти этапы по-
казаны в листинге 6.1, а.
Листинг 6.1. Использование семафоров для защиты: а — одного ресурса; б — двух
ресурсов
typedef int semaphore; typedef int semaphore;
semaphore resource_1; semaphore resource_1;
semaphore resource_2;
void process_A(void) { void process_A(void) {
down(&resource_1); down(&resource_1);
use_resource_1( ); down(&resource_2);
up(&resource_1); use_both_resources( );
} up(&resource_2);
up(&resource_1);
}
a б
Иногда процессы нуждаются в двух и более ресурсах. Их можно получать последо-
вательно, как показано в листинге 6.1, б. Если требуется больше двух ресурсов, их
запрашивают непосредственно один за другим.
Пока все идет хорошо. Пока речь идет только об одном процессе, все работает нор-
мально. Конечно, когда используется только один процесс, нет нужды в формальном
получении ресурсов, поскольку нет соперничества за обладание ими.
Теперь рассмотрим ситуацию с двумя процессами — A и B — и двумя ресурсами. В ли-
стинге 6.2 показаны два сценария: а — оба процесса запрашивают ресурсы в одном
и том же порядке; б — запрашивают ресурсы в разном порядке. Разница может пока-
заться несущественной, но это не так.
Листинг 6.2. Код: а — не вызывающий взаимоблокировки; б — в котором кроется
потенциальная возможность взаимоблокировки
typedef int semaphore;
semaphore resource_1; semaphore resource_1;
semaphore resource_2; semaphore resource_2;
void process_A(void) { void process_A(void) {
down(&resource_1); down(&resource_1);
down(&resource_2); down(&resource_2);
use_both_resources( ); use_both_resources( );
up(&resource_2); up(&resource_2);
up(&resource_1); up(&resource_1);
} }
void process_B(void) { void process_B(void){
down(&resource_1); down(&resource_2);
down(&resource_2); down(&resource_1);
492
Глава 6. Взаимоблокировка
use_both_resources( ); use_both_resources( );
up(&resource_2); up(&resource_1);
up(&resource_1); up(&resource_2);
} }
a б
В листинге 6.2, а один из процессов запрашивает первый ресурс раньше, чем это делает
второй процесс. Затем этот же процесс успешно получает второй ресурс и выполняет
свою работу. Если второй процесс попытается получить ресурс 1 до его высвобождения,
то он будет просто заблокирован до тех пор, пока ресурс не станет доступен.
В листинге 6.2, б показана другая ситуация. Может случиться, что один из процессов
получит оба ресурса и надежно заблокирует другой процесс до тех пор, пока не сделает
свою работу. Но может случиться и так, что процесс A получит ресурс 1, а процесс B
получит ресурс 2. Каждый из них теперь будет заблокирован при попытке получения
второго ресурса. Ни один из процессов не возобновит свою работу. Плохо то, что воз-
никнет ситуация взаимоблокировки.
Здесь мы видим, что происходит из-за небольшой разницы в стиле программирова-
ния: в зависимости от того, какой из ресурсов будет получен первым, программа либо
работает, либо дает трудноопределимый сбой. Поскольку взаимоблокировки могут
возникать столь просто, для борьбы с ними были проведены обширные исследования.
В этой главе подробно рассматриваются взаимоблокировки и средства борьбы с ними.
6.2. Введение во взаимоблокировки
Взаимоблокировкам можно дать следующее формальное определение.
Взаимоблокировка в группе процессов возникает в том случае, если каждый процесс
из этой группы ожидает события, наступление которого зависит исключительно от
другого процесса из этой же группы.
Поскольку все процессы находятся в состоянии ожидания, ни один из них не станет
причиной какого-либо события, которое могло бы возобновить работу другого про-
цесса, принадлежащего к этой группе, и ожидание всех процессов становится бес-
конечным. В этой модели предполагается, что у процессов есть только один поток,
а прерывания, способные возобновить работу заблокированного процесса, отсутствуют.
Условие отсутствия прерываний необходимо, чтобы не позволить заблокированному
по иным причинам процессу возобновить свою работу, скажем, по аварийному сигналу,
после чего вызвать событие, освобождающее другие имеющиеся в группе процессы.
В большинстве случаев событием, наступления которого ожидает каждый процесс,
является высвобождение какого-либо ресурса, которым на данный момент владеет
другой участник группы. Иными словами, каждый процесс из группы, попавшей
в ситуацию взаимоблокировки, ожидает ресурса, которым обладает другой процесс
из этой же группы. Ни один из процессов не может работать, ни один из них не может
высвободить какой-либо ресурс, и ни один из них не может возобновить свою работу.
Количество процессов и количество и вид удерживаемых и запрашиваемых ресурсов
не имеет значения. Этот результат сохраняется для любого типа ресурсов, включая ап-
паратные и программные ресурсы. Этот вид взаимоблокировки называется ресурсной
взаимоблокировкой
. Наверное, это самый распространенный, но далеко не единствен-
6.2. Введение во взаимоблокировки
493
ный вид. Сначала мы рассмотрим ресурсную взаимоблокировку, а в конце этой главы
вернемся к краткому обзору других видов взаимоблокировки.
6.2.1. Условия возникновения ресурсных
взаимоблокировок
Коффман (Coffman et al., 1971) показал, что для возникновения ресурсных взаимобло-
кировок должны выполняться четыре условия:
1. Условие взаимного исключения. Каждый ресурс либо выделен в данный момент
только одному процессу, либо доступен.
2. Условие удержания и ожидания. Процессы, удерживающие в данный момент ранее
выделенные им ресурсы, могут запрашивать новые ресурсы.
3. Условие невыгружаемости. Ранее выделенные ресурсы не могут быть принуди-
тельно отобраны у процесса. Они должны быть явным образом высвобождены
тем процессом, который их удерживает.
4. Условие циклического ожидания. Должна существовать кольцевая последователь-
ность из двух и более процессов, каждый из которых ожидает высвобождения
ресурса, удерживаемого следующим членом последовательности.
Для возникновения ресурсной взаимоблокировки должны соблюдаться все четыре
условия. Если одно из них не соблюдается, ресурсная взаимоблокировка невозможна.
Следует заметить, что каждое условие относится к той политике, которой придер-
живается или не придерживается система. Может ли данный ресурс быть выделен
одновременно более чем одному процессу? Может ли процесс удерживать ресурс
и запрашивать другой ресурс? Может ли ресурс быть отобран? Может ли получиться
циклическое ожидание? Чуть позже мы увидим, как взаимоблокировке может противо-
стоять попытка устранения некоторых из этих условий.
6.2.2. Моделирование взаимоблокировок
Холт (Holt, 1972) показал, как эти четыре условия могут быть смоделированы с ис-
пользованием направленных графов. У графов имеется два вида узлов: процессы,
показанные окружностями, и ресурсы, показанные квадратами. Направленное ребро,
которое следует от узла ресурса (квадрата) к узлу процесса (окружности), означает,
что этот ресурс был ранее запрошен, получен и на данный момент удерживается этим
процессом. На рис. 6.1, а ресурс R в данное время выделен процессу A.
Направленное ребро, идущее от процесса к ресурсу, означает, что процесс в данное
время заблокирован в ожидании высвобождения этого ресурса. На рис. 6.1, б процесс B
ожидает высвобождения ресурса S. На рис. 6.1, в мы наблюдаем взаимоблокировку:
процесс C ожидает высвобождения ресурса T, который в данный момент удерживается
процессом D. Процесс D не собирается высвобождать ресурс T, поскольку он ожидает
высвобождения ресурса U, удерживаемого процессом C. Оба процесса находятся в со-
стоянии вечного ожидания. Циклическая структура графа означает, что мы имеем
дело с взаимоблокировкой, включившей процессы и ресурсы в цикл (предполагается,
что в системе есть только один ресурс каждого типа). В данном примере получился
следующий цикл: C–T–D–U–C.
494
Глава 6. Взаимоблокировка
Рис. 6.1. Графы распределения ресурсов: a — ресурс занят; б — запрос ресурса;
в — взаимоблокировка
Рассмотрим пример того, как могут быть использованы графы ресурсов. Представим,
что есть три процесса, A, B и C, и три ресурса, R, S и T. Последовательности действий
по запросу и высвобождению ресурсов, осуществляемые этими тремя процессами, по-
казаны на рис. 6.2, а–в. Операционная система может в любое время запустить любой
незаблокированный процесс, то есть она может принять решение запустить процесс A
и дождаться, пока он не завершит всю свою работу, затем запустить процесс B и довести
его работу до завершения и, наконец, запустить процесс C.
Такой порядок не приводит к взаимоблокировкам (поскольку отсутствует борьба за
овладение ресурсами), но в нем нет и никакой параллельной работы. Кроме действий
по запросу и высвобождению ресурсов процессы занимаются еще и вычислениями,
и вводом-выводом данных. Когда процессы запускаются последовательно, отсутствует
возможность использования центрального процессора одним процессом, в то время
когда другой процесс ожидает завершения операции ввода-вывода. Поэтому строго
последовательное выполнение процессов может быть не оптимальным решением. В то
же время, если ни один из процессов не выполняет никаких операций ввода-вывода,
алгоритм, при котором кратчайшее задание выполняется первым, более привлекателен,
чем циклический алгоритм, поэтому при определенных условиях последовательный
запуск всех процессов может быть наилучшим решением.
Теперь предположим, что процессы занимаются как вводом-выводом, так и вычисле-
ниями, поэтому наиболее разумным алгоритмом планирования их работы является
циклический алгоритм. Запросы ресурсов могут происходить в том порядке, который
показан на рис. 6.2, г. Если эти шесть запросов выполняются именно в этом порядке, им
соответствую шесть результирующих ресурсных графов, показанных на рис. 6.2, д–к.
После выдачи запроса 4 процесс A, как показано на рис. 6.2, з, блокируется в ожида-
нии ресурса S. На следующих двух этапах процессы B и C также блокируются, что
в итоге приводит к зацикливанию и возникновению взаимоблокировки, показанной
на рис. 6.2, к.
Но как уже ранее упоминалось, от операционной системы не требовалось запускать
процессы в каком-то определенном порядке. В частности, если удовлетворение кон-
кретного запроса может привести к взаимоблокировке, операционная система может
просто приостановить процесс, не удовлетворяя его запрос (то есть просто не планируя
работу процесса) до тех пор, пока это не будет безопасно. На рис. 6.2, если операцион-
ная система знает о грядущей взаимоблокировке, она может приостановить процесс B,
вместо того чтобы выделить ему ресурс S. Запуская только процессы A и C, мы получим
такую последовательность действий по запросу и высвобождению ресурсов, которая
6.2. Введение во взаимоблокировки
495
Рис. 6.2. Пример возникновения и предупреждения взаимоблокировки