Синхронизация параллельных процессов необходима в двух случаях:

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

На рис. 1 момент времени - момент, когда процесс A получает доступ к некоторой критической области; - момент времени, когда процесс Б пытается получить доступ к этой критической области, но не получает его и блокируется; - момент, когда процесс A завершает использование критической области и покидает ее, а процесс Б - получает доступ к критической области; - момент, когда процесс Б завершает использование критической области и покидает ее; - период нахождения процесса А в критической области; - период блокирования процесса Б; - период нахождения процесса Б в критической области.

Во многих операционных системах средства синхронизации процессов относят к средствам межпроцессорного взаимодействия - Inter Process Communications (IPS), в которые входят также средства межпроцессного обмена данными.

Современным низкоуровневым решением проблемы взаимного исключения является использование семафоров Дейкстры (E.W.Dijkstra), 1965г. Семафор (semaphore) – это специальный тип переменных, которые могут принимать только неотрицательные значения, и над которыми определены только три следующие операции ( – переменная типа «семафор»):

Если семафор закрыт (процессом 1, с помощью операции P(S)), то процесс 2, вызвавший операцию , ждет, пока семафор откроется (процессом 1, с помощью операции V(S)).

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

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

Простейшим семафором является двоичный семафор, который может принимать лишь два состояния – 0 и 1. Иногда двоичный семафор называют мьютексом (mutex – сокращение от mutual exclusion).

begin
   semaphore S; 
   --описание общих (глобальных) переменных процессов process1, process2
   INIT(S);
   parbegin
      process1: begin
          --описание локальных переменных процесса process1
          ...
          P(S);
          <критическая секция>
          V(S);
          ...
          end;
      process2: begin
          --описание локальных переменных процесса process1
          ...
          P(S);
          <критическая секция>
          V(S);
          ...
          end;
   parend;
end;

Прежде отметим, что в стандарте POSIX семафоры полностью аналогичны семафорам Дейкстры. Для инициализации значения таких семафоров применяется функция sem_init(), аналогом операции служит функция sem_wait(), а аналогом операции – функция sem_post().

В современных операционных системах Unix набор операций над семафорами отличается от классического набора операций Дейкстры. Этот набор включает в себя три операции:

Изначально все семафоры инициируются нулевым значением.

Легко видеть, что операции Дейкстры () соответствует операция (,1), а операции () - операция (,1).

Системный вызов semget(key, nsems, semflag) обеспечивает создание набора семафоров. Здесь параметр key можно интерпретировать как имя набора семафоров, nsems – количество семафоров в наборе, параметр semflag определяет, главным образом, права различных пользователей при доступе к данному набору семафоров.

Системный вызов semop(). Системный вызов semop() обладает довольно сложной семантикой и используется для выполнения рассмотренных выше операций A, D и Z над семафорами из заданного набора семафоров.

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

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

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

Одним из способов решения указной проблемы является использование алгоритма двоичного экспоненциального отката, который применяется в сетях Ethernet. Между опросами вставляется цикл задержки. Вначале задержка равна времени выполнения одной команды. Если семафор занят, задержка удваивается, учетверяется и т.д. до некоторого максимального уровня. Этот уровень устанавливается, исходя из следующих соображений: низкий уровень обеспечивает высокую реактивность, но и высокую загрузку коммуникационной среды; высокий уровень, напротив, - низкую загрузку среды, но и низкую реактивность.