Методы обхода тупиков

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

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

Наиболее известным алгоритмом предотвращения тупика (или его обхода) является “алгоритм банкира”, предложенный Дейкстрой. Этот алгоритм как бы имитирует действия банкира, который, обладая определенным капиталом, выдает ссуды и принимает платежи.

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

Максимальная потребность в ресурсах для любого процесса есть наибольшее число единиц каждого ресурса, в которых когда-либо будет нуждаться процесс. Эти потребности в системе можно представить числами C_ij (i=1,2,..., n, j=1,2,..., m), где C_ij представляет максимальную потребность процесса p_i в ресурсе R_j.

Для каждого процесса p_i и ресурса R_j в системе должно выполняться дополнительное ограничение на запросы

|(p_i, R_j)| + |(R_j, p_i)| £ C_ij £ c_j,

где c_j - емкость ресурса.

Граф потребностей для состояния S определяется как граф повторно используемых ресурсов состояния S, дополненный дугами запросов на n_ij единиц ресурса R_j для процесса p_i, где

n_ij = C_ij - (|(p_i, R_j)| + |(R_j, p_i)|).

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

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

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

Следующая теорема является основой для реализации данного метода обхода тупика:

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

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

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

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

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

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

Если априори известны только процессы-производители ресурсов и любой процесс является потенциальным потребителем CR-ресурсов, то ни одно состояние системы не является безопасным.

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

Пусть для каждого потребляемого ресурса R_j известно непустое множество процессов - его производителей - p ^P (R_j) Î p и непустое множество процессов-потребителей этого ресурса p ^C (R_j) Î p. Процесс p_i может запросить и приобрести ресурс R_j, только если p_i Î p ^C (R_j). Процесс p_i может освободить ресурс R_j, только если p_i Î p ^P (R_j).

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

¨ процесс p_i имеет выданный запрос на единицу ресурса R_j тогда и только тогда, когда p_i Î p ^C (R_j);

¨ у всех потребляемых ресурсов в системе нет доступных единиц (то есть все вершины, представляющие эти ресурсы в графе ПР имеют нулевые пометки).

Соответствующий граф называется графом потребляемых ресурсов с ограничением на требования. Для системы с ПР справедлива следующая теорема, являющаяся основанием для построения системы распределения ресурсов с предотвращением тупиков:

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

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