Понятие тупиковой ситуации и выполнение

Параллельных вычислительных процессов.

 

На практике могут часто возникать ситуации, когда 2 и более процессов претендуют на один и тот же ресурс(ы). При этом все они оказываются в заблокированном состоянии (состоянии ожидания, когда освободится нужный ресурс). Однако при этом ресурсы им не предоставляются.

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

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

При рассмотрении проблемы тупиков вводится понятие классов ресурсов. Ресурсы разделяются на 2 класса: первый - ресурсы повторно используемые (SR), второй - расходуемые (CR).

 

- Повторно используемые это ресурсы со следующими свойствами:

1. число единиц ресурса постоянное.

2. Каждая единица ресурса доступна только одному процессу.

3. Процесс может освободить единицу ресурса, только если ранее он ее получил.

К ресурсам типа SR относятся: основная память, внешняя память, периферийные устройства, файлы данных и др.

- Расходуемые ресурсы имеют следующие свойства:

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

2. Единицы ресурса, которые приобретены (расходованы) в общем случае не возвращаются ресурсу.

К ресурсам класса CR относятся: синхронизирующие сигналы; передаваемые сообщения; данные, порождаемые как программами, так и аппаратурой.

 

Лекция 7.

Рассмотрим примеры образования тупиков:

Будем считать, что на момент времени t1 состояние системы описывается графом. Имеется 2 процесса P1 и P2),чки означают количество единиц ресурса.) стрелки означают запрос единицы ресурса, стрелки к процессу - получение единицы ресурса. Допустим, что в момент времени t2 процесс P1 получит единицу ресурса R2. в результате образовался тупик, т. к процесс P1 ждет 2 ух ресурсов, а их ему не хватает, т.к 2 отданы процессу P2. процессу P2 не хватает R2. оба процесса будут ждать бесконечно долго.

Замечание: Еслибы в момент t2 ресурс R2 был бы отдан процессу P2, тогда было бы все нормально, т.е. P2 работал бы т.к получил бы все необходимые ресурсы. А P1 ждал бы.

 

Допустим, что имеются 3 процесса взаимодействующие через почтовые ящики.

Допустим, что P1 является потребителем М1 через Р3. процесс Р2 получает сообщения М1 от Р1. А процесс Р3 сообщения М2 от Р2.

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

 

 

Р1: послать сообщение (Р2,М1, на2)

Ждать сообщение (Р3, М1 на 1)

Р2: послать сообщение (Р3, М2 на 3)

Ждать сообщение (Р1, М2 на 2)

Р3: послать сообщение (Р1, М3 на 1)

Ждать сообщение (Р2, М2 на 3)

При данном алгоритме реализация процессов будет нормальна функционировать.

Рассмотрим другой алгоритм:

Р1: Ждать сообщение (Р3, М1 на 1)

Послать сообщение (Р2,М1, на2)

Р2: Ждать сообщение (Р1, М2 на 2)

Послать сообщение (Р3, М2 на 3)

Р3: Ждать сообщение (Р2, М2 на 3)

Послать сообщение (Р1, М3 на 1)

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

 

Борются с тупиковой ситуацией разные ОС по-разному. Существует 3 основных метода борьбы с тупиками:

1. Предупреждение тупиков.
2. Обход тупиков.
3. Распознавание тупика с последующим восстановлением.

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

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

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

3. Метод распознавания состоит в том, что система не прогнозирует тупиков, и если он случился, то только тогда система описывает ситуацию и начинает принимать методы по восстановлению (по принципу что удастся спасти). Метод используется чаще и дешевле других методов, система работает быстрее.