Что такое тупик?
Говорят, что набор процессов находится в тупиковой ситуации, когда каждый процесс в наборе ожидает события, которое может быть вызвано другим процессом в наборе.
В приведенном выше примере процессы P1 и P2 находятся в тупиковой ситуации. Оба процесса требуют R1 и R2 для завершения своего выполнения.
Процесс P1 имеет R1, но ожидает ресурс R2, а процесс P2 имеет R2, но ожидает R1.
Теперь в этом случае оба процесса ожидают некоторого ресурса, который уже получен другим процессом, который также ожидает, пока какой-либо ресурс завершит свою задачу. Этот сценарий называется «тупиком» в информатике.
Необходимые условия взаимоблокировки
Тупик может возникнуть тогда и только тогда, когда все следующие условия в системе выполняются одновременно. Эти условия называются условиями Кофмана.
Взаимное исключение
Каждый ресурс может быть назначен только одному процессу одновременно.
Подождите
Процесс удерживает какой-то ресурс и все еще ожидает какой-то другой ресурс, который удерживается другим процессом.
Без вытеснения
Ни один ресурс не может быть вытеснен из процесса в любое время.
Циклическое ожидание
Процесс P1 ожидает некоторый ресурс, который удерживается P2, P2 ожидает ресурса, который удерживается P3, и так далее… Pn ожидает ресурса, который удерживается P1.
Предотвращение взаимоблокировки
Чтобы избежать взаимоблокировки, любое из четырех условий должно быть нарушено.
Взаимное исключение
Чтобы нарушить взаимное исключение, ресурс должен быть разделен между процессами одновременно. Это практически невозможно, потому что такие ресурсы, как принтер, не могут быть доступны одновременно.
Подождите
Чтобы выйти из состояния удержания и ожидания, ни один процесс не должен ждать после получения доступа к требуемому ресурсу. Лучший способ — предоставить все ресурсы, которые требуются процессу. Но тогда практически ресурсы не будут использоваться должным образом.
Без вытеснения
Чтобы нарушить условие отсутствия вытеснения, мы должны гарантировать, что процесс сначала освободит полученный ресурс, прежде чем запрашивать другие ресурсы. ОС может иметь матрицу процесса и ресурса для отслеживания выделенных и нераспределенных ресурсов.
Циклическое ожидание
Чтобы нарушить циклическое ожидание, мы должны убедиться, что существует некоторый восходящий или нисходящий порядок для запроса ресурсов у процесса, который удерживает этот ресурс. Возьмем пример восходящего порядка: P1 может запросить ресурс, которым владеет P2, но P2 не может запросить ресурс, которым владеет P1. Мы должны поддерживать порядок.
Предотвращение взаимоблокировки
Да, можно предотвратить взаимоблокировку в системе до того, как ОС обнаружит ее. Там тоже есть свои условия.
ОС должна знать о точных требованиях к ресурсам для выполнения процесса. ОС должна знать о количестве выделенных, доступных и общем количестве ресурсов в системе в любой момент времени.
Чтобы предотвратить взаимоблокировку, ОС сначала необходимо найти последовательность, в которой процесс может запрашивать ресурс. Последовательность может быть любой (не обязательно по порядку).
Если мы возьмем в качестве примера 5 процессов с именами P1, P2, … P5. Последовательность для предотвращения взаимоблокировки может быть P3, P4, P1, P2, P5 или может быть P2, P1, P5, P3, P4.
Эта последовательность называется безопасной последовательностью, потому что если обработать запрос на ресурсы и ОС выделит ресурсы для обработки в этой последовательности, взаимоблокировки не произойдет. Чтобы найти безопасную последовательность, у нас есть алгоритм Банкера. Если ОС может иметь безопасную последовательность из этого алгоритма, то можно сказать, что система находится в безопасном состоянии.
