Параллельных вычислительных процессов.
На практике могут часто возникать ситуации, когда 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. Метод распознавания состоит в том, что система не прогнозирует тупиков, и если он случился, то только тогда система описывает ситуацию и начинает принимать методы по восстановлению (по принципу что удастся спасти). Метод используется чаще и дешевле других методов, система работает быстрее.