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

Последовательный процесс - это работа по выполнению программы, производимая последовательным процессором. Если времена существования последовательных процессов при их исполнении хотя бы частично перекрываются, такие процессы становятся “параллельными” и возникает проблема синхронизации использования устройств ВС, доступа к данным со стороны этих процессов. В этом случае процессы могут конкурировать за использование общих ресурсов (как аппаратных, так и информационных), выполняемые ими функции могут зависеть друг от друга и требовать определенной последовательности исполнения для реализации общей работы. Эта проблема становится особенно острой, если процессы являются взаимодействующими.

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

Рассмотрим пример. В ВС существует несколько процессов P₁, P₂,..., P_n, каждый из которых увеличивает значение разделяемой (общей) переменной C (например, выполняются программы, обслуживающие некоторые запросы, и требуется считать общее количество выполненных в ВС запросов). Таким образом, в каждой из выполняющихся программ должны быть операторы вида

C:= C + 1.

Причем для выполнения этого оператора процесс должен прочитать текущее значение переменной C (обозначим оператор чтения read(C)) и сохранить новое значение этой переменной после увеличения (обозначим операцию записи write(C)). Следовательно, увеличение значения счетчика C выполняется с помощью последовательности из трех (как минимум) операций: чтения (выборки из общей памяти или из общего файла) текущего значения переменной, увеличения значения этой переменной на 1 и сохранения (записи в память или в файл) увеличенного значения:

read(C);

inc(C);

write(C).

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

	Порядок выполнения операций процессами
Процесс
Pi	read(C)	inc(C)	write(C)	...
Pj	...	read(C)	inc(C)	write(C)

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

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

Примером еще одной проблемы, которая требует решения задачи синхронизации выполнения процессов, является задача “производитель-потребитель” (“писатель-читатель”).

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

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

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

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