Примеры тупиковых ситуаций и причины их возникновения
Для понимания основных причин возникновения тупиков рассмотрим несколько простых характерных примеров.
Пример тупика на ресурсах типаCr
Пусть
имеются три процесса ПР1, ПР2 и ПРЗ,
которые вырабатывают соответственно
сообщения Ml,M2
и МЗ. Эти сообщения представляют собой
ресурсы типаCR. Пусть
процесс ПР1 является «потребителем»
сообщения МЗ, процесс ПР2 получает
сообщениеMl, а ПРЗ –
сообщение М2 от процесса ПР2, то есть
каждый из процессов является и
«поставщиком» и «потребителем»
одновременно, и вместе они образуют
«кольцевую» систему (рис. 7.2) передачи
сообщений через почтовые ящики (ПЯ).
Если связь с помощью этих сообщений со
стороны каждого процесса устанавливается
в порядке, изображенном в листинге 7.1,
то никаких трудностей не возникает.
Однако перестановка этих двух процедур
в каждом из процессов (
листинг
7.2) вызывает тупик:
Рис. 7.2.Кольцевая схема взаимодействия процессов
Листинг 7.1. Вариант без тупиковой ситуации
ПР1: . . .
ПОСЛАТЬ СООБЩЕНИЕ (ПР2, M1, ПЯ2);
ЖДАТЬ СООБЩЕНИЕ (ПР3, М3, ПЯ1);
. . .
ПР2: . . .
ПОСЛАТЬ СООБЩЕНИЕ (ПРЗ, М2, ПЯ3);
ЖДАТЬ СООБЩЕНИЕ (ПР1, M1, ПЯ2);
. . .
ПРЗ: . . .
ПОСЛАТЬ СООБЩЕНИЕ (ПР1, МЗ, ПЯ1);
ЖДАТЬ СООБЩЕНИЕ (ПР2, М2, ПЯ3);
. . .
Листинг 7.2. Вариант с тупиковой ситуацией
ПР1: . . .
ЖДАТЬ СООБЩЕНИЕ (ПР3, М3, ПЯ1);
ПОСЛАТЬ СООБЩЕНИЕ (ПР2, M1, ПЯ2);
. . .
ПР2: . . .
ЖДАТЬ СООБЩЕНИЕ (ПР1, M1, ПЯ2);
ПОСЛАТЬ СООБЩЕНИЕ (ПРЗ, М2, ПЯЗ);
. . .
ПРЗ: . . .
ЖДАТЬ СООБЩЕНИЕ (ПР2, М2, ПЯЗ);
ПОСЛАТЬ СООБЩЕНИЕ (ПР1, МЗ, ПЯ1);
. . .
В самом деле, во втором варианте ни один из процессов не сможет послать сообщения до тех пор, пока сам его не получит, а этого события никогда не произойдет, поскольку ни один процесс не может этого сделать.
Пример тупика на ресурсах типаCRиSr
Пусть некоторый процесс ПР1 должен обменяться сообщениями с процессом ПР2 и каждый из них запрашивает некоторый ресурс R, причем ПР1 требует три единицы этого ресурса для своей работы, а ПР2 – две единицы и только на время обработки сообщения. Всего же имеются только четыре единицы ресурса R. Запрос ресурса можно реализовать через соответствующий монитор с процедурамиREQUEST(R,N) – запрос N единиц ресурса R иRELEASE(R,N) – освобождение, возврат N единиц ресурса R. Обмен сообщениями будем осуществлять через почтовый ящикMB. Фрагменты программ ПР1 и ПР2 приведены в листинге. 7.3.
Листинг 7.3. Пример тупика на CR- и SR-pecypcax
. . .
. . .
ПР1: REQUEST (R, 3);
SEND_MESSAGE (ПР2, сообщение, MB);
WAIT ANSWER (ответ, MB);
. . .
. . .
RELEASE (R, 3);
. . .
. . .
. . .
. . .
ПР2: WAIT_MESSAGE (ПР1, сообщение, MB);
REQUEST (R, 2);
ОБРАБОТКА СООБЩЕНИЯ;
RELEASE (R, 2);
SEND_ANSWER (ответ, MB);
Эти два процесса всегда будут попадать в тупик. Процесс ПР2, если будет выполняться первым, сначала ожидает сообщения от процесса ПР1, после чего будет заблокирован при запросе ресурса R, часть которого будет уже отдана ПР1. Процесс ПР1, завладев частью ресурса R, будет заблокирован на ожидании ответа от ПР2, которого никогда не получит, так как для этого ПР2 нужно получить ресурс R, находящийся в распоряжении ПР1. Тупика можно избежать лишь при условии, что на время ожидания ответа от ПР2 процесс ПР1 будет отдавать хотя бы одну единицу ресурса R, которыми он сейчас владеет. В данном примере, как и в предыдущем, причиной тупика являются ошибки программирования.