4.3.4. Обход дедлоков

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

4.3.5. Алгоритм банкира

Алгоритм обхода тупиковых ситуаций, названный алгоритмом банкира, впервые был предложен Дейкстрой. Свое название он получил потому, что он как бы имитирует действия банкира, который, располагая определенным источником капитала, выдает клиентам денежные ссуды и принимает платежи. Банкир ссужает денежные суммы некоторому числу клиентов, каждый из которых заранее сообщает банкиру максимальную сумму, которая ему будет нужна. Клиент может занимать эту сумму по частям, и нет никаких гарантий, что он возвратит часть денег до того, как сделает весь займ. Весь капитал банкира обычно меньше, чем суммарные требования клиентов, так как банкир не предполагает, что все клиенты сделают максимальные займы одновременно. Если в некоторый момент клиент запросит денежную сумму, банкир должен знать, сможет ли он ссудить ее без риска попасть в ситуацию, когда не будет достаточного количества денег, чтобы обеспечить дальнейшие займы, а именно это в конце концов позволяет клиентам возвратить долг. Чтобы ответить на этот вопрос, банкир предполагает, что он выполнил запрос и оценивает сложившуюся ситуацию. Он определяет клиента, чей текущий займ наиболее близок к максимальному. Если банкир не может ссудить оставшуюся сумму этому клиенту, то он отклоняет первоначальный запрос. Если же банкир может ссудить оставшуюся сумму, то он предполагает, что этот клиент полностью рассчитался (вернул выделенные ему денежные средства), и обращает свое внимание на того клиента из оставшихся, чей запрос ближе всего к своему лимиту. Просматривая таким образом всех клиентов, банкир каждый раз проверяет, будет ли у него достаточно денег, чтобы удовлетворить минимальный займ клиенту и предоставить последнему полную сумму. В случае, если это так, банкир удовлетворяет первоначальный займ. Если вместо «банкир», «клиент» и «денежные суммы» предполагать «операционная система», «процесс» и «ресурс», то можно применить этот алгоритм к вычислительным системам.

Пусть в вычислительной системе, имеющей m различных типов ресурсов, исполняется n процессов. Введем в рассмотрение следующие векторы и матрицы:

- вектор ресурсов R , определяющий полное количество каждого ресурса в системе

- вектор наличия AV (AVailable), устанавливающий количество каждого ресурса, не закрепленного за процессами

- матрицу требований C (Claim), задающую требуемое количество каждого типа ресурса для каждого процесса

- матрицу распределения A (Allocation), описывающую текущее распределение ресурсов между процессами

Указанные векторы и матрицы удовлетворяют следующим условиям:

- все ресурсы должны быть или распределены между процессами, или иметься в наличии;

- ни один процесс не может запросить больше ресурсов, чем их имеется в системе;

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

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

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

Рассмотрим действие алгоритма банкира на следующем примере. Пусть вычислительная система, в которой исполняется четыре процесса, содержит три вида ресурсов, а векторы ресурсов R, наличия AV и матрицы требований C и распределения A принимают значения как показано на рис.4.18,а.

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

Рис. 4.18. Пример распределения ресурсов согласно алгоритму банкира

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

При распределении ресурсов согласно алгоритму банкира, предложенному Дейкстрой, условия «взаимного исключения», «ожидания дополнительных ресурсов» и «неперераспределяемости» выполняются. Процессы могут претендовать на монопольное использование ресурсов, которые им требуются. Процессам реально разрешается удерживать за собой ресурсы, запрашивая и ожидая выделения дополнительных ресурсов, причем ресурсы нельзя отбирать у процесса, которому они выделены. Пользователи не став­ят перед системой особенно сложных задач, запрашивая в каждый момент времени только один ресурс. Система может либо удовлетворить, либо отклонить каждый запрос. Если запрос отклоняется, пользователь удерживает за собой уже выделенные ему ресурсы и ждет определенный конечный период времени, пока этот запрос в конце концов не будет удовлетворен. Система удовлетворяет только те запросы, при кото­рых ее состояние остается надежным. Запрос пользователя, приводящий к переходу системы в ненадежное состояние, откладывается до момента, когда его все же можно будет выполнить. Таким образом, поскольку система всегда поддерживается в надежном состоянии, рано или поздно (т. е. в течение конечного времени) все запросы можно будет удовлетворить, и все пользователи смогут завершить свою работу.

Алгоритм банкира представляет интерес потому, что он дает возможность распределять ресурсы таким образом, чтобы обходить тупиковые ситуации. Он позволяет продолжать выполнение таких процессов, которым в случае системы с предотвращением тупиков пришлось бы ждать.­ Однако у этого алгоритма имеется ряд серьезных недостатков, из-за которых разработчик системы может оказаться вынужденным выбрать другой подход к решению проблемы тупиков:

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

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

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

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

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