Лекция 6. Дедлоки. Управление ресурсами

Дедлок (тупиковая ситуация).

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

Условия возникновения дедлока.

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

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

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

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

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

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

Решение проблемы дедлоков.

Стратегия предотвращения дедлоков.

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

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

Методы предотвращения взаимоблокировок можно разбить на два класса.

1. Косвенный метод состоит в предотвращении одного из первых трех условий возникновения взаимоблокировки;
2. Прямой метод предотвращает циклическое ожидание (условие четыре).

Условие взаимного исключения подавляется путем неограниченного разделения ресурсов (это совершенно неприемлемо к совместно используемым переменным в критических интервалах и к последовательно используемым ресурсам)

Условие ожидания можно подавить, предварительно выделяя ресурсы. Процесс должен потребовать все ресурсы заранее, и он не сможет начать исполнение до тех пор, пока они ему не будут выделены. Неэффективность использования ресурсов (каждый процесс должен ждать, пока не получит всех необходимых ресурсов, даже если один из них используется к концу исполнения. Трудно сформулировать запросы на ресурсы в тех случаях, когда требуемые ресурсы становятся известны только после начала выполнения.

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

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

2. Общее исключение - отнимать у процесса, заблокированного при запросе дополнительного ресурса, все ресурсы.

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

1. Все ресурсы образуют иерархию

2. Процесс, затребовавший ресурс на одном уровне, может затем потребовать ресурс только на более высоком уровне;

3. Процесс может освободить ресурс на данном уровне только после освобождения всех ресурсов на более высоких уровнях;

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

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

Стратегия обхода дедлоков.

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

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

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

Существуют методы эффективного выполнения такого просмотра. Данный подход является примером контролируемого выделения ресурсов.

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

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

Классическое решение этой задачи «алгоритм банкира»

1. Банкир ссужает денежные суммы (в одной валюте), некоторому числу клиентов.
2. Каждый клиент заранее сообщает банкиру максимальную сумму, которая ему нужна.
3. Клиент может занимать эту сумму по частям, и нет никаких гарантий, что он возвратит часть денег до того, как сделает весь заём.

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

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

Решение:

1. Банкир предполагает, что он выполнил запрос, и оценивает сложившуюся ситуацию
2. Он определяет клиента, чей текущий заём наиболее близок к максимальному.
3. Если банкир не может ссудить оставшуюся сумму этому клиенту, то он отклоняет первоначальный запрос.
4. Если же он сможет ссудить эту сумму, то он удовлетворяет первоначальный запрос.

Если вместо «банкир», «клиент» и «денежные суммы» читать «операционная система», «процесс» и «ресурс», то этот алгоритм можно применить к операционным системам.

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

Для n процессов и m ресурсов простое решение требует время вычисления, пропорциональное mn² . Было предложено решение, требующее время, пропорциональное mn, но при этом для хранения информации необходим объем памяти, больший, чем при использовании медленного алгоритма.

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