Раздел 3. Взаимодействие процессов
Тема 8. Проблема взаимного исключения и способы ее решения
Основные понятия
Два процесса называются параллельными (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) Процесс остается в КС только в течение ограниченного времени.
Существуют следующие подходы к достижению взаимного исключения.
- Программный – сам процесс является ответственным за достижение взаимного исключения. Т.е. процесс (и системный, и пользовательский) должен координировать свои действия с другими процессами для достижения взаимного исключения без поддержки со стороны ОС или языка программирования.
- Аппаратный – использование машинных команд специального назначения.
- Поддержка со стороны ОС или языка программирования (семафоры, мониторы и т.п.).