Тупик в OperaСистема ting: что такое циклическое ожидание (примеры)

Что такое тупик?

Deadlock это ситуация, которая возникает в операционная система Взаимная блокировка (deadlock) — это ситуация, когда один процесс переходит в состояние ожидания, потому что другой ожидающий процесс удерживает запрошенный ресурс. Это распространенная проблема в многопроцессорных системах, где несколько процессов совместно используют определенный тип взаимоисключающего ресурса, известного как программная блокировка (soft lock) или программная блокировка.

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

Пример тупика

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

Пример тупиковой ситуации

Что такое циклическое ожидание?

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

Например, процессу A выделяется ресурс B, когда он запрашивает ресурс A. Аналогично, процессу B выделяется ресурс A, когда он запрашивает ресурс B. Это создает замкнутый цикл ожидания.

Пример циклического ожидания

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

Пример циклического ожидания

Обнаружение взаимоблокировок в ОС

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

Предотвращение тупиковых ситуаций в ОС

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

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

Без упреждения

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

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

Взаимное исключение

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

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

Держись и жди

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

Круговое ожидание

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

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

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

уклонение Algorithms

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

Для отдельного экземпляра ресурса определенного типа:

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

Для нескольких экземпляров ресурса одного типа:

• Цикл необходим, но недостаточен для возникновения тупиковой ситуации.
• Использовать Банковский алгоритм.

Разница между голоданием и тупиком

Вот несколько важных различий между тупиковой ситуацией и голоданием:

Deadlock	Голодание
Взаимоблокировка возникает, когда один из процессов блокируется.	«Голодание» — это ситуация, когда все процессы с низким приоритетом блокируются, в то время как процессы с высоким приоритетом продолжают выполняться.
Тупик — это бесконечный процесс.	Голод – это долгое ожидание, но не бесконечный процесс.
В любой тупиковой ситуации всегда наступает голод.	Не каждая ситуация, связанная с голодом, обязательно заканчивается тупиком.
Взаимная блокировка возникает из-за одновременного возникновения взаимных исключений, ожидания и удержания, отсутствия вытеснения и циклического ожидания.	Это происходит из-за неконтролируемого распределения приоритетов и неэффективного управления ресурсами.

Преимущества тупика

Вот преимущества использования метода обработки взаимоблокировок:

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

Недостатки тупика

Вот недостатки использования метода обработки взаимоблокировок:

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

Часто задаваемые вопросы (FAQ)