Тупики и методы борьбы с ними.
Определение. Множество процессов находится в тупиковой ситуации, если каждый процесс из множества ожидает события, которое только другой процесс данного множества может вызвать. Одновременно в нем может находится как 1, так и несколько процессов.
Определение 2. Процесс или поток находится в состоянии тупика, если он ожидает какого-либо события, которое никогда не произойдет.
Зависание системы (Dead Lock) – ситуация когда один или несколько потоков находятся в состоянии тупика.
Примеры тупиковых ситуаций:
1) транспортная пробка:
Потоки – «движение транспорта», ресурсы – «перекрестки, через которые нужно проехать».
Пусть организовано одностороннее движение à круговое ожидание.
Методы борьбы:
- предотвращение тупика, добавление ресурса (например добавить «мост»);
- обход тупика, то есть проверить условие, можно ли проехать перекресток;
- обнаружение тупика и возобновление потока, для этого нужно убрать один поток (метод наиболее радикальный, используется редко);
- разорвать цепь тупика по timeout.
2) 1 поток взаимодействует с каким либо устройством. Механизм
timeout, какое то другое устройство или поток контролирует время ожидания, при необходимости выводит из тупика.
timeout – время тупика не больше установленного значения.
В большинстве случаев необходимо делать функции обработки внутри процесса (программы) в другом потоке.
В 1971 г. Хавендер сформулировал следующие
четыре необходимых условия для возникновения тупиков.
1. Условие взаимоисключения (монопольности) (Mutual exclusion). Каждый ресурс выделен в точности одному процессу или доступен. Процессы требуют предоставления им монопольного управления ресурсами, которые им выделяются.
2. Условие ожидания ресурсов (Hold and wait). Процессы удерживают за собой ресурсы, уже выделенные им, ожидая в то же время выделения дополнительных ресурсов (которые при этом обычно удерживаются другими процессами).
3. Условие неперераспределяемости (No preemtion). Ресурс, данный ранее, не может быть принудительно забран у процесса. Освобождены они могут быть только процессом, который их удерживает.
4. Условие кругового ожидания (Circular wait). Существует кольцевая цепь процессов, в которой каждый процесс удерживает за собой один или более ресурсов, требующихся другим процессам цепи.
Тупик может возникнуть, если все 4 условия выполняются одновременно.
Методы борьбы:
1) предотвращение.
2) обход.
3) обнаружение и восстановление.
Предотвращение тупиков за счет нарушения условий возникновения тупиков (хотя бы одного).
Нарушение условия взаимоисключения
Если в системе отсутствуют выделенные ресурсы, тупиков не будет. Тем не менее, ясно, что обобществление, например, принтера, то есть, разрешение двум процессам писать на один принтер в одно и то же время приведет к хаосу. За счет организации спулинга одновременная печать для нескольких процессов становится возможной.
Нарушение условия ожидания дополнительных ресурсов
Хавендер в 1968 г. предложил следующую стратегию.
- Каждый процесс должен запрашивать все требуемые ему ресурсы сразу, причем не может начать выполняться до тех пор, пока все они не будут ему предоставлены.
Если же процесс, удерживает определенные ресурсы и получает отказ в выделении ему дополнительных ресурсов, то он должен освободить свои первоначальные ресурсы и, при необходимости, запросить их снова вместе с дополнительными.
Нарушение принципа неперераспределяемости.
В соответствии со вторым принципом Хавендера можно отбирать ресурсы у удерживающих их процессов до завершения этих процессов.
Нарушение условия кругового ожидания
Циклического ожидания можно избежать несколькими путями. Один из них действовать в соответствии с правилом, согласно которому каждый процесс может иметь только один ресурс в каждый момент времени. Если нужен второй ресурс - освободи первый. Другой способ - присвоить всем ресурсам уникальные номера и потребовать, чтобы процессы запрашивали ресурсы в порядке возрастания номеров. Тогда круговое ожидание возникнуть не может.
В большинстве ОС предотвращение идет по 4-том пункту.
