Проблема взаимного исключения процессов

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

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

Процесс A:	Процесс B:
... R1:= N; R1:= R1 - 1; N:= R1; ...	... R2:= N; R2:= R2 + 1; N:= R2; ...

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

1) R1:= N; R2:= N; R2:= R2 + 1; N:= R2; R1:= R1 - 1; N:= R1;

2) R2:= N; R2:= R2 + 1; R1:= N; R1:= R1 - 1; N:= R1; N:= R2;

3) R1:= N; R1:= R1 - 1; N:= R1; R2:= N; R2:= R2 + 1; N:= R2;

Ну и что? А то, что в случае 1 значение N в результате окажется уменьшенным на 1, в случае 2 — увеличенным на 1, и только в случае 3 значение N, как и положено, не изменится.

Можно привести менее экзотические примеры.

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

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

 Если два процесса одновременно пытаются обратиться к диску, каждый со своим запросом, то что именно каждый из них в результате прочтет или запишет на диск — сказать трудно.

Ситуация понятна: нельзя разрешать двум процессам одновременно обращаться к одним и тем же данным, если при этом происходит изменение этих данных.

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

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

Для более четкого описания ситуации было введено понятие критической секции.

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

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

А как им это запретить?

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

Процесс A:	Процесс B:
... while not Free do ; Free:= false; (критическая секция A) Free:= true; ...	... while not Free do ; Free:= false; (критическая секция B) Free:= true; ...

В обоих процессах цикл while не делает ничего, кроме ожидания, пока другой процесс выйдет из своей критической секции.

А не нужно ли было что-нибудь сделать с переменной Free еще до запуска процессов A и B?

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

Беда в том, что такое решение ничего не решает. Если реализовать его на практике, то «неприятности» станут реже, но не исчезнут. В первом, бесхитростном варианте программы угрожаемыми участками были критические секции обоих процессов. Теперь же уязвимый участок сузился до одной точки, отмеченной в программе каждого процесса штриховой линией. Это точка между проверкой переменной Free и изменением этой переменной. Если переключение процессов произойдет, когда вытесняемый процесс будет находиться именно в этой точке, то сначала в критическую секцию войдет (с полным правом на это) другой процесс, а потом, когда управление вернется к первому процессу, он без дополнительной проверки тоже войдет в свою критическую секцию.

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

 в любой момент времени не более, чем один процесс может находиться в критической секции;

 если критическая секция свободна, то процесс может беспрепятственно войти в нее;

 все процессы равноправны.

Попробуйте сами найти такое решение. В книгах /3/ и /4/ можно найти несколько вариантов решения с анализом их ошибок.

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

Для любознательных приводим решение Питерсона. В нем используются булевы переменные flagA, flagB, изначально равные false, и переменная перечисляемого типа turn: A..B.

Процесс A:	Процесс B:
... flagA:= true; turn:= B; while flagB and turn = B do ; (критическая секция A) flagA:= false; ...	... flagB:= true; turn:= A; while flagA and turn = A do ; (критическая секция B) flagB:= false; ...

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

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