Раздел 3. Взаимодействие процессов Тема 8. Проблема взаимного исключения и способы ее решения

8.1. Основные понятия

Два процесса называются параллельными (concurrent), если их выполнение может перекрываться во времени. Это означает, что второй процесс начинается прежде, чем первый завершится. В мультипроцессорной системе достигается физическая параллельность. Если в процессоре чередуется выполнение нескольких процессов, то достигается логическая параллельность. Два процесса называются последовательными (serial), если они не являются параллельными.

Виды взаимодействия процессов:

• Обмен информацией: процессы непосредственно осведомлены о наличии друг друга.

• Конкуренция за доступ к ресурсам: процессы не осведомлены о наличии друг друга. ОС должна регулировать такие обращения.

• Согласование действий процессов: процессы косвенно осведомлены друг о друге. Например, процесс А поставляет данные, процесс В выводит их на печать.

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

• разделяемые переменные;

• передача сообщений.

И в однопроцессорных и в многопроцессорных системах из-за невозможности предсказать относительную скорость работы процессов при работе параллельных процессов возникают следующие проблемы:

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

2. Блокировки и взаимоблокировки при доступе к ресурсам. Процесс А может затребовать и получить контроль над некоторым УВВ, после чего временно приостановить работу. Нежелательно, чтобы ОС при этом блокировала УВВ и не давала другим процессам возможности использовать его – это может привести к взаимоблокировке.

3. Трудно обнаруживаемые программные ошибки, т.к. результат работы программы перестает быть детерминированным и воспроизводимым.

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

void echo()

{

chin = getchar();

chout = chin;

putchar(chout);

}

Рассмотрим следующую последовательность событий:

1. Процесс А выполняет оператор chin = getchar(); Введен символ x.

2. Процесс В выполняет процедуру echo до конца. Введен и выведен символ у.

3. Процесс А продолжает выполнение. Будет выведен у, а не х. Т.е. у выведен дважды, а х – потерян.

Решение данной проблемы – в каждый момент времени только один процесс может входить в процедуру echo, и она обязательно должна быть полностью выполнена вошедшим в нее процессом до того, как станет возможным ее выполнение другим процессом. Та же проблема остается и в многопроцессорной системе:

Взаимное исключение (mutual exclusion) – это механизм, который гарантирует, что в любой момент времени, только один процесс выполняет некоторую определенную последовательность действий и, тем самым, исключает возможность работы другого процесса.

Критический ресурс – это ресурс, к которому в каждый момент времени возможен доступ только одного процесса. Доступ к такому ресурсу осуществляется в критической секции (КС) – части кода, которая в любой момент времени может выполняться только одним процессом.

Взаимное исключение может привести к двум проблемам:

1. Взаимная блокировка (deadlock), которая обсуждается в теме 4.

2. Голодание (starvation). Пусть имеются процессы А, В и С. Каждому из процессов периодически требуется доступ к ресурсу Р. Пусть процесс А использует Р, В и С – ждут. Потом В использует Р, затем опять А использует Р и т.д. Т.е. процесс С может никогда не получить доступ к ресурсу Р, несмотря на то, что никакой взаимной блокировки нет. Такая ситуация называется голоданием.

Итак, чтобы избежать гонок, мы должны избегать нахождения двух процессов в критических секциях одновременно. Но этого требования недостаточно. Для правильной совместной работы параллельных процессов необходимо выполнение шести условий для достижения взаимного исключения.

1. Два процесса не должны одновременно находиться в критических секциях.

2. В программе не должно быть предположений о скорости или количестве процессоров.

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

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

5. Когда в КС нет ни одного процесса, любой процесс, запросивший возможность входа в КС, должен немедленно ее получить.

6. Процесс остается в КС только в течение ограниченного времени.

Существуют следующие подходы к достижению взаимного исключения.

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

• Аппаратный – использование машинных команд специального назначения.

• Поддержка со стороны ОС или языка программирования (семафоры, мониторы и т.п.).