Обход дедлоков
Если ни одно из упомянутых четырех условий не исключено, тем не менее вход в опасное состояние можно все же предотвратить, если у системы есть информация о последовательности запросов, связанных с каждым параллельным процессом. Можно доказать, что если вычисления находятся в любом неопасном состоянии, то существует по крайней мере одна последовательность состояний, которая обходит опасное состояние. Следовательно, достаточно проверить, не приведет ли выделение затребованного ресурса сразу же к опасному состоянию. Если да, то запрос отклоняется. Если нет, его можно выполнить. Проверка того, является состояние опасным или нет, требует анализа последующих запросов процессов. Существуют методы эффективного выполнения такого просмотра. Данный подход является примером контролируемого выделения ресурса.
Часто бывает так, что последовательность запросов, связанных с каждым процессом, неизвестна заранее. Однако если заранее известен общий запрос на ресурсы каждого типа, то выделение ресурсов можно контролировать. В этом случае необходимо для каждого требования, в предположении, что оно удовлетворено, определить, существует ли среди общих запросов от всех процессов некоторая последовательность требований, которая может привести к опасному состоянию.
Классическое решение этой задачи известно как алгоритм банкира. Он выполняется следующим образом. Банкир ссужает денежные суммы, все в одной валюте, некоторому числу клиентов, каждый из которых заранее сообщает банкиру максимальную сумму, которая ему будет нужна. Клиент может занимать эту сумму по частям, и нет никаких гарантий, что он возвратит часть денег до того, как сделает весь займ. Весь капитал банкира обычно меньше, чем суммарные требования клиентов, так как банкир не предполагает, что все клиенты сделают максимальные займы одновременно. Если в некоторый момент клиент запросит денежную сумму, банкир должен знать, сможет ли он ссудить ее без риска попасть в ситуацию, когда не будет достаточного количества денег, чтобы обеспечить дальнейшие займы, а именно это в конце концов позволяет клиентам возвратить долг.
Чтобы ответить на этот вопрос, банкир предполагает, что он выполнил запрос и оценивает сложившуюся ситуацию. Он определяет клиента, чей текущий займ наиболее близок к максимальному. Если банкир не может ссудить оставшуюся сумму этому клиенту, то он отклоняет первоначальный запрос. Если же банкир может ссудить оставшуюся сумму, то он предполагает, что этот клиент полностью рассчитался, и обращает свое внимание на того клиента из оставшихся, чей запрос ближе всего к своему лимиту. Просматривая таким образом всех клиентов, банкир каждый раз проверяет, будет ли у него достаточно денег, чтобы удовлетворить минимальный займ клиенту и предоставить последнему полную сумму. В случае если это так, банкир удовлетворяет первоначальный займ. Если вместо “банкир”, “клиент” и “денежные суммы” читать “операционная система”, “процесс” и “ресурс”, то можно применить этот алгоритм к вычислительным системам.
Если используются несколько типов ресурсов, нужно проводить аналогию с международным банкиром, который ссужает деньги в разной валюте. Недостаточно применить одновалютный алгоритм к каждой валюте в отдельности. Вместо этого необходимо проверять общие запасы разной валюты, а необходимый для этого алгоритм более сложен. Для п процессов и р ресурсов простое решение требует время вычисления, пропорциональное рn3. Были предложены решения, требующие время, пропорциональное рn, но при этом для хранения информации необходим объем памяти, больший чем при использовании медленного алгоритма. Основным накладным расходом стратегии обхода дедлока с помощью контролируемого выделения ресурса является время выполнения алгоритма, поскольку он вызывается при каждом запросе. Более того, этот алгоритм работает наиболее медленно, когда система близка к дедлоку. Из-за того, что на каждом шаге предполагается самая плохая ситуация, такая стратегия может приводить к плохому использованию ресурсов. Кроме того, стратегия обхода дедлоков может оказывать существенное влияние на планирование. Поток работ, требующих мало ресурсов, может отложить на неопределенное время выбор в решении работы, требующей больших ресурсов. Конечно, обход дедлоков неприменим в случае отсутствия информации о требованиях процессов на ресурсы.
