Тупики, типы ресурсов для изучения тупиковых ситуаций, необходимые условия возникновения тупиков, стратегии предотвращения тупиков (СПО)

Тупики и близкая к ним проблема бесконечного откладывания - важные факторы, которые должны учитывать разработчики ОС.

Тупик (deadlock) - это такая ситуация в мультипрограммной системе, когда процесс ожидает некоторого события, которое никогда не произойдет. Системная тупиковая ситуация, или “зависание” системы - это ситуация, когда один или более процессов оказываются в состоянии тупика.

При рассмотрении проблемы тупиков все ресурсы разделяются на два класса: повторно используемые (или системные) ресурсы (типа RR - reusable resource и SR - system resource) и потребляемые (или расходуемые) ресурсы (типа CR - consumable resource).

Повторно используемый ресурс (SR) есть конечное множество идентичных единиц со следующими свойствами:

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

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

Расходуемый ресурс (CR) отличается от ресурса типа SR следующим:

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

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

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

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

Необходимые условия возникновения тупиков

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

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

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

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

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

Борьба с возникновением тупиков может вестись по четырем основным направлением: предотвращение тупиков; обход тупиков; обнаружение тупиков; восстановление после тупиков.

Методы борьбы с тупиками

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

предотвращение тупика;

обход тупика;

обнаружение (распознавание) тупика с последующим восстановлением.

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

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

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

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

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

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

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

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

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

Обход тупиков

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

Обнаружение тупиков. Графы распределения ресурсов

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