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

⇐ ПредыдущаяСтр 37 из 50Следующая ⇒

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

При параллельном исполнении процессов могут возникать ситуации, при которых два или более процесса всё время находятся в заблокированном состоянии. Самым простым является случай, когда каждый из двух процессов ожидает ресурс, занятый другим процессом. Из-за такого ожидания ни один из процессов не может продолжить исполнение и освободить в конечном итоге ресурс, необходимый другому процессу. Эта тупиковая ситуация называется дедлоком1, тупиком или клинчем. Говорят, что в мультипрограммной системе процесс находится в состоянии тупика, если он ждёт события, которое никогда не произойдёт. Тупики чаще всего возникают из-за конкуренции несвязанных параллельных процессов за ресурсы вычислительной системы, но иногда к тупикам приводят и ошибки программирования.

При рассмотрении проблемы тупиков целесообразно понятие ресурсов системы обобщить и разделить их все на два класса – повторно используемые (или системные) ресурсы (типа RR или SR – reusable resource или system resource) и потребляемые (или расходуемые) ресурсы (типа CR – consumable resource).

Повторно используемый ресурс (SR) есть конечное множество идентичных единиц со следующими свойствами [92]:

¨ число единиц ресурса постоянно;

¨ каждая единица ресурса или доступна, или распределена одному и только одному процессу (разделение либо отсутствует, либо не принимается во внимание, так как не оказывает влияния на распределение ресурсов, а значит, и на возникновение тупиковой ситуации);

¨ процесс может освободить единицу ресурса (сделать её доступной), только если он ранее получил эту единицу, то есть никакой процесс не может оказывать какое-либо влияние ни на один ресурс, если он ему не принадлежит.

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

Расходуемый ресурс (CR) отличается от ресурса типа SR в нескольких важных отношениях [37]:

¨ число доступных единиц некоторого ресурса типа CR изменяется по мере того, как приобретаются (расходуются) и освобождаются (производятся) отдельные их элементы выполняющимися процессами, и такое число единиц ресурса является потенциально неограниченным; процесс «производитель» увеличивает число единиц ресурса, освобождая одну или более единиц, которые он «создал»;

¨ процесс «потребитель» уменьшает число единиц ресурса, сначала запрашивая и затем приобретая (потребляя) одну или более единиц. Единицы ресурса, которые приобретены, в общем случае не возвращаются ресурсу, а потребляются (расходуются). Эти свойства потребляемых ресурсов присущи многим синхронизирующим сигналам, сообщениям и данным, порождаемым как аппаратурой, так и программным обеспечением, и могут рассматриваться как ресурсы типа CR при изучении тупиков. В их число входят: прерывания от таймера и устройств ввода/вывода; сигналы синхронизации процессов; сообщения, содержащие запросы на различные виды обслуживания или данные, а также соответствующие ответы.

Для исследования параллельных процессов и, в частности, проблемы тупиков было разработано несколько моделей. Одной из них является модель повторно используемых ресурсов Холта [92]. Согласно этой модели система представляется как набор (множество) процессов и набор ресурсов, причём каждый из ресурсов состоит из фиксированного числа единиц. Любой процесс может изменять состояние системы с помощью запроса, получения или освобождения единицы ресурса.

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

Одно из состояний примера системы из двух процессов с ресурсами типа SR представлено на рис. 7.1.

Пусть процесс Р1 запрашивает две единицы ресурса R1 и одну единицу ресурса R2. Процессу Р2 принадлежат две единицы ресурса R1 и ему нужна одна единица R2. Предположим, что процесс Р1 получил бы теперь запрошенную им единицу R2. Если принято правило, по которому процесс должен получить все запрошенные им ресурсы, прежде чем освободить хотя бы один из них, то удовлетворение запроса Р1 приведет к тупиковой ситуации: Р1 не сможет продолжиться до тех пор, пока Р2 не освободит единицу ресурса R1, а процесс Р2 не сможет продолжиться до тех пор, пока Р1 не освободит единицу R2. Причиной этого дедлока являются неупорядоченные попытки процессов войти в критический интервал, связанный с

выделением соответствующей единицы ресурса.

Рис. 7.1. Пример модели Холта для системы из двух процессов

Примеры тупиковых ситуаций и причины их возникновения

Для понимания основных причин возникновения тупиков рассмотрим несколько простых характерных примеров.

Пример тупика на ресурсах типа 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, которыми он сейчас владеет. В данном примере, как и в предыдущем, причиной тупика являются ошибки программирования.

Пример тупика на ресурсах типа SR

Предположим, что существуют два процесса ПР1 и ПР2, разделяющих два ресурса типа SR: R1 и R2. Пусть взаимное исключение доступов к этим ресурсам реализуется с помощью семафоров S1 и S2 соответственно. Процессы ПР1 и ПР2 обращаются к ресурсам следующим образом [37] (рис. 7.3):

Процесс ПР1 Процесс ПР2

: :

1: P(S2); 5: P(S1);

: :

2: P(S1); 6: P(S2);

: :

3: V(S1); 7: V(S1);

: :

4: V(S2); 8: V(S2);

: :

Рис. 7.3. Пример последовательности операторов для двух процессов, которые

могут привести к тупиковой ситуации

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

Горизонтальная ось задаёт выполнение процесса ПР1, вертикальная – ПР2. Вертикальные линии, пронумерованные от 1 до 4, соответствуют операторам 1– 4 процесса ПР1. Аналогично горизонтальные линии, пронумерованные от 5 до 8, соответствуют операторам 5 – 8 программы ПР2. Точка на плоскости определяет состояние вычислений в некоторый момент времени. Так, точка А соответствует ситуации, при которой ПР1 начал исполнение, но не достиг оператора 1, а ПР2 выполнил оператор 6, но не дошел до оператора 7. По мере выполнения точка будет двигаться горизонтально вправо, если исполняется ПР1, и вертикально вверх, если исполняется ПР2.

Интервалы исполнения, во время которых ресурсы R1 и R2 используются каждым процессом, показаны с помощью фигурных скобок. Линии 1 – 8 делят пространство вычислений на 25 прямоугольников, каждый из которых задаёт состояние вычислений. Закрашенные серым цветом состояния являются недостижимыми из-за взаимного исключения ПР1 и ПР2 при доступе к ресурсам R1 и R2.

Рассмотрим последовательность исполнения 1–2–5–3–6–4–7–8, представленную траекторией Т1. Когда процесс ПР2 запрашивает ресурс R1 (оператор 5), ресурс недоступен (оператор выполнен, семафор закрыт). Поэтому процесс ПР2 заблокирован в точке В. Как только процесс ПР1 достигнет оператора 3, процесс ПР2 деблокируется по ресурсу R1. Аналогично в точке С процесс ПР2 будет заблокирован при попытке доступа к ресурсу R2 (оператор 6). Как только процесс ПР1 достигнет оператора 4, процесс ПР2 деблокируется по ресурсу R2.

Если же, например, выполняется последовательность 1–5–2–6, то процесс ПР1 заблокируется в точке Х при выполнении оператора 2, а процесс ПР2 заблокируется в точке Y при выполнении оператора 6. При этом процесс ПР1 ждёт, когда процесс ПР2 выполнит оператор 7, а ПР2 ждёт, когда ПР1 выполнит оператор 4. Оба процесса будут находиться в тупике, ни ПР1, ни ПР2 не могут закончить выполнение. При этом все ресурсы, которые получили ПР1 и ПР2, становятся недоступными для других процессов, что резко снижает возможности вычислительной системы по обслуживанию их. Отметим одно очень важное обстоятельство: тупик будет неизбежным, если вычисления зашли в прямоугольник D, являющийся кри

тическим состоянием.

Рис. 7.4. Пространство состояний системы двух параллельных конкурирующих процессов

Для того чтобы возник тупик, необходимо, чтобы одновременно выполнялись четыре условия [37, 92]:

¨ взаимного исключения, при котором процессы осуществляют монопольный доступ к ресурсам;

¨ ожидания, при котором процесс, запросивший ресурс, ждёт до тех пор, пока запрос не будет удовлетворен, при этом удерживая ранее полученные ресурсы;

¨ отсутствия перераспределения, при котором ресурсы нельзя отобрать у процесса, если они ему уже выделены;

¨ кругового ожидания, при котором существует замкнутая цепь процессов, каждый из которых ждёт ресурс, удерживаемый его предшественником в этой цепи.

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

⇐ Предыдущая 32 33 34 35 363738 39 40 41 Следующая ⇒