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

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

Проблему часто поясняют на таком, немного условном, примере. Пусть имеется система резервирования авиабилетов, в которой одновременно работают два процесса. Процесс 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. С их помощью действительно можно проще реализовать взаимное исключение, но для этого все равно требуется активное ожидание.

Двоичные семафоры Дейкстры

Совершенно иным образом подошел к проблеме взаимного исключения великий голландский ученый Э.Дейкстра (E.Dijkstra, 1966). Он предложил использовать новый вид программных объектов – семафоры. Здесь мы рассмотрим их простейший вариант – двоичные семафоры, они же мьютексы (mutex, от слов MUTual EXclusion – взаимное исключение).

Двоичным семафором называется переменная S, которая может принимать значения 0 и 1 и для которой определены только две операции.

· P(S) – операция занятия (закрытия) семафора. Она ожидает, пока значение S не станет равным 1, и, как только это случится, присваивает S значение 0 и завершает свое выполнение. Очень важно: операция P по определению неделима, т.е. между проверкой и присваиванием не может вклиниться другой процесс, который бы изменил значение S.

· V(S) – операция освобождения (открытия) семафора. Она просто присваивает S значение 0.

Чем переменная-семафор отличается от обычной булевой переменной? Тем, что для нее недопустимы никакие иные операции, кроме P и V. Нельзя написать в программе S:=1 или if(S)then..., если S определена как семафор.

Чем операция P отличается от варианта с проверкой и присваиванием, который мы выше признали неудовлетворительным? Неделимостью. Но это «по определению», а как на практике добиться этой неделимости? Это отдельный, вполне решаемый вопрос.

Заслуга Дейкстры как раз в том, что он разделил проблему взаимного исключения на две независимые проблемы разных уровней:

· на уровне реализации: как обеспечить работу семафоров в соответствии с их определением;

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

Решать эти две задачи по отдельности легче, чем обе вместе, при этом решать их обычно должны разные люди: первую – разработчики ОС, а вторую – разработчики прикладной программы.

Рассмотрим сначала реализацию. Очевидно, функции P и V удобнее и надежнее один раз реализовать в ОС, чем каждый раз по-новому – в прикладных программах. (Названия этих функций могут в конкретных системах быть и иными, более выразительными.)

Системная функция P(S) должна проверить, свободен ли семафор S. Если свободен (S = 1), то система занимает его (S:= 0) и на этом функция завершается. Если же семафор занят, то система блокирует процесс, вызвавший функцию P, и запоминает, что этот процесс блокирован по ожиданию освобождения семафора S. Таким образом, при реализации семафоров удается избежать активного ожидания.

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

Системная функция V(S) – это, конечно, не просто присваивание S:= 1. Кроме этого, система должна проверить, нет ли среди спящих процессов такого, который ожидает освобождения семафора S. Если такой процесс найдется, система разблокирует его, а переменная S в этом случае сохраняет значение 0 (семафор снова занят, теперь уже другим процессом).

Может ли случиться так, что несколько спящих процессов ждут освобождения одного и того же семафора? Да, так вполне может быть. Какой из этих процессов должен быть разбужен системой? С точки зрения корректности работы и соответствия определениям функций P и V – любой, но только один. С точки зрения эффективности работы – вероятно, надо разбудить самый приоритетный процесс, а в случае равенства приоритетов… ну, видимо, тот, который спит дольше.

Теперь, когда мы разобрались с реализацией семафоров, можно о ней забыть[9] и помнить только, что семафоры существуют и могут быть использованы при необходимости.

Рассмотрим теперь вторую половину задачи – использование семафоров для управления взаимодействием процессов. Как можно реализовать корректную работу процессов с критическими секциями, если использовать двоичный семафор? Да очень просто.

Процесс A:	Процесс B:
... P(S); (критическая секция A) V(S); ...	... P(S); (критическая секция B) V(S); ...

И все. Сложности ушли в реализацию семафоров. Надо только проследить, чтобы до начала работы процессов семафор S был открыт.