Запрещение запуска процесса

Рассмотрим систему из п процессов и т различных типов ресурсов. Определим следующие векторы и матрицы:

Матрица требований, в которой каждая строка описывает один из процессов, указывает максимальные требования каждого процесса к разным ресурсам, т.е. С_ij — это требования процессом i ресурса j. Для работоспособности метода устранения взаимоблокировок эта информация должна быть объявлена процессом заранее. Аналогично, A_ij — текущее количество ресурса j, выделенное процессу i.

³ Термин "устранение" несколько запутывает ситуацию. В некотором смысле рас­сматриваемые в данном разделе стратегии можно считать примерами предотвращения взаимоблокировок, так как их использование действительно предотвращает появление последних.

Должны выполняться следующие соотношения.

1. для всех i: все ресурсы либо свободны, либо выделены.

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

3.для всех k и i: ни один процесс не может получить больше ресурсов, чем было затребовано им.

Когда все указанные величины определены, мы в состоянии создать стратегию устранения взаимоблокировок, которая запрещает запуск нового процесса, если его требования ресурсов могут привести к взаимоблокировке. Новый процесс Р_n+1 запускается только если

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

Запрет выделения ресурса

Стратегия запрета выделения ресурса, известная также как алгоритм банкира,⁴ впервые была предложена в работе [DIJK65]. Мы начнем рассмотрение с концепций состояния (state) и безопасного состояния (safe state). Остановимся на системе с фиксированным количеством процессов и фиксированным количеством ресурсов. В каждый момент времени процесс может иметь несколько выделенных ему ресурсов (или не иметь ни одного). Состояние системы представляет собой просто текущее распределение ресурсов по процессам. Следовательно, состояние можно представить как два ранее определенных вектора — ресурсов и доступности — и две матрицы — требований и распределения. Безопасное состояние — это такое состояние, в котором имеется по крайней мере одна последовательность, которая не приводит к взаимоблокировке (т.е. все процессы могут быть выполнены до завершения). Состояние, не являющееся безопасным, называется, соответственно, опасным состоянием.

Описанную концепцию иллюстрирует приведенный далее пример. На рис. 6.6,а показано состояние системы, образованной четырьмя процессами и тремя ресурсами. Общее количество ресурсов Rl, R2 и R3 составляет соответственно 9, 3 и 6 единиц. В результате сделанного к этому моменту распределения ресурсов по процессам доступными остались по одной единице ресурсов R2 и R3. Безопасно ли данное состояние?

⁴ Дейкстра воспользовался таким названием, сравнивая эту задачу с деятельно­стью банка, где клиент, который хочет осуществить заем денег, отождествляется с процессом, а деньги — с ресурсом. Банк имеет ограниченное количество денег для зай­мов, и список клиентов, у каждого из которых имеется своя предельная величина кре­дита. Клиент может неоднократно осуществлять заем в пределах этой величины, при­чем нет никакой гарантии, что он погасит хотя бы часть задолженности до того мо­мента, пока не займет всю возможную сумму. Таким образом, если несколько клиентов берут частичные займы, то гарантировать возврат этих денег банку может только некоторый резервный фонд. В худшем случае, когда все клиенты погашают займы только по достижении ими предельной суммы кредита, этот фонд должен обеспечить возможность выдать им эти максимальные суммы. Следовательно, при исчерпании де­нежных запасов до размеров резервного фонда банк будет вынужден отказать очередно­му клиенту в предоставлении займа, иначе деньги в банк могут никогда не вернуться.

Для ответа на этот вопрос зададимся другим вопросом, а именно — может ли какой-нибудь из четырех процессов быть выполнен при данных доступных ресурсах до завершения? Или, говоря иначе, могут ли при данном распределении ресурсов быть удовлетворены максимальные требования какого-то из процессов за счет оставшихся ресурсов? Ясно, что для процесса Р1 это невозможно, так как у него имеется только одна единица ресурса R1, и для полного удовлетворения ему требуется еще по две единицы ресурсов Rl, R2 и R3. Однако если выделить процессу Р2 одну единицу ресурса R3, то будут удовлетворены максимальные требования этого процесса и он сможет быть завершен.

Предположим, что именно так и произошло — процесс Р2 оказался завершен, и распределенные ему ресурсы вернулись в пул доступных. Это состояние системы показано на рис. 6.6,б. Вернувшись к вопросу о том, какой из процессов может быть завершен в данной ситуации, мы находим, что могут быть удовлетворены максимальные требования как процесса Р1, так и процесса РЗ. Предположим, что мы выбрали процесс Р1. По его завершении и возвращении захваченных им ресурсов в пул доступных ситуация будет выглядеть так, как показано на рис. 6.6,в. И, наконец, по завершении процесса РЗ мы придем к состоянию, изображенному на рис. 6.6,г. К этому моменту все процессы завершены, а, следовательно, исходное состояние (рис. 6.6,а) является безопасным. Описанная концепция автоматически приводит к стратегии устранения взаимоблокировок, которая гарантирует, что система процессов и ресурсов всегда находится в безопасном состоянии. Когда процесс делает запрос к некоторому множеству ресурсов, предполагается, что запрос удовлетворен, после чего определяется, является ли обновленное состояние системы безопасным. Если это так, то запрос удовлетворяется; в противном случае процесс блокируется до тех пор, пока удовлетворение его запроса не станет безопасным.

Рассмотрим состояние, определяемое матрицей на рис. 6.7,а. Предположим, что процесс Р2 делает запрос на одну дополнительную единицу ресурса R1 и одну — ресурса R3. Если запрос будет выполнен, то в результате состояние системы станет таким, как показано на рис. 6.6,а. Мы уже видели, что это состояние является безопасным. Таким образом, запрос можно удовлетворить. Теперь вернемся к состоянию, представленному на рис. 6.7,а, и предположим, что такой же запрос на одну дополнительную единицу ресурса R1 и одну — ресурса R3 делает процесс Р1. Если этот запрос будет удовлетворен, состояние системы станет таким, как показано на рис. 6.7,6. Является ли это состояние безопасным? В данном случае ответ — нет, поскольку каждому из процессов требуется по одной дополнительной единице ресурса R1, а в наличии свободных единиц этого ресурса уже нет. Следовательно, запрос процесса Р1 должен быть отклонен, а сам процесс блокирован.

Важно отметить, что состояние, представленное на рис. 6.7,6, не является взаимоблокировкой. Оно всего лишь может привести к ней. Например, при работе процесс Р1 может освободить по одной единице ресурсов R1 и R3, и система вновь вернется в безопасное состояние. Следовательно, стратегия устранения взаимоблокировок не занимается точным предсказанием взаимоблокировок; она лишь предвидит их возможность и устраняет ее.

В листинге 6.1 приведена логика работы алгоритма устранения взаимоблокировок. Основной алгоритм показан в части б. Состояние системы описывается структурой state, а вектор request [*] определяет ресурсы, затребованные процессом i. Сначала выполняется проверка того, что запрос не превышает исходные требования процесса. Если запрос корректен, то следующий шаг алгоритма состоит в определении возможности удовлетворения запроса (т.е. выясне­нии, достаточно ли для этого свободных ресурсов). Если нет — процесс приостанавливается; если же ресурсов достаточно, выполняется последняя проверка -безопасно ли выполнение запроса. Для этого процессу гипотетически выделяются требуемые ресурсы, в результате чего получается новое состояние системы newstate, которое и проверяется на безопасность с использованием алгоритма из листинга 6.1,в.

Листинг 6.1. Алгоритм устранения взаимоблокировок

struct state

{

int resource[m];

int available[m];

int claim [n] [m];

int alloc [n] [m];

}