Проблемы взаимодействия процессов
Чуть получше алгоритм нумерованных ресурсов. Он заключается в том, что все ресурсы, имеющиеся в системе, нумеруются целыми числами в произвольном порядке (хотя, вероятно, для повышения эффективности лучше всего пронумеровать их в порядке возрастания дефицитности ресурса). Далее применяется простое правило: запрос процесса на выделение ему ресурса с номером K удовлетворяется только в том случае, если процесс в данный момент не владеет никаким другим ресурсом с номером N і K. Другими словами, запрос ресурсов следует выполнять только в порядке возрастания номеров. Нетрудно показать, что это правило является достаточным условием отсутствия тупиков. Но это условие слишком ограничивающее, оно отсекает много ситуаций, когда тупик на самом деле не возник бы.
Наиболее изящен алгоритм банкира, предложенный тем же Дейкстрой. В нем предполагается, что каждый процесс при старте должен объявить системе, на какие ресурсы и в каком максимальном количестве он может в будущем претендовать. Далее, вводится понятие безопасного (в отношении тупиков) состояния системы. Текущее состояние, в котором имеется набор процессов, каждый из которых владеет некоторыми ресурсами, считается безопасным, если имеющихся в наличии свободных ресурсов достаточно для того, чтобы ОС смогла в определенной последовательности удовлетворить максимальные запросы каждого процесса.
Это определение проще понять, если рассмотреть, как проверяется безопасность заданного состояния. Согласно алгоритму, среди имеющихся процессов ищется такой, чьи максимальные заявленные запросы система может удовлетворить, используя имеющиеся свободные ресурсы. Если хотя бы один такой процесс найден, то он вычеркивается из общего списка и все ресурсы, которые он уже успел занять, считаются свободными (т.е. считается, что система смогла завершить этот процесс). Далее, при увеличившихся свободных ресурсах, ищется следующий процесс, чьи запросы система может удовлетворить, и т.д. Если в результате удается вычеркнуть все процессы, то анализируемое состояние системы является безопасным.
предыдущаяследующая