Задача синхронизации предусматривает, что если один асинхронный процесс начал выполнение некоей группы команд (работа с ресурсом), другой асинхронный процесс не должен начинать выполнение своей группы команд, работающих с этим же ресурсом. Такая группа команд, выполнение которой должно быть синхронизировано с другими процессами, называется критическим участком (критическим блоком).
Если процесс 1 начал выполнение своего критического участка (КУ), процесс 2 не должен начинать выполнение своего КУ до завершения первым процессом выполнения КУ. Такая ситуация получила название задачи взаимоисключения.
Самый простой путь решения задачи взаимоисключения — после начала выполнения процессом КУ запретить активизацию другого, конкурирующего процесса. То есть запретить передиспетчеризацию процессов, например, запретив прерывания в системе. Кстати говоря, нечто подобное уже рассматривалось нами при знакомстве с организацией прерываний — программа имела возможность запретить обработку прерываний на время выполнения некоего участка кода, выполнение которого не может быть прервано.
Однако этот путь имеет большой недостаток. Дело в том, что время, необходимое для выполнения КУ процессом неизвестно. Вообще говоря, оно может быть достаточно большим. И если на это время запретить диспетчеризацию в системе, все остальные процессы (включая саму ОС) будут блокированы на неопределенное время. Такой подход не может быть признан корректным.
Следовательно, необходимо создание более гибких механизмов синхронизации. Попробуем познакомиться с такими механизмами на нескольких примерах. Сделаем следующие допущения:
В приведенных ниже примерах конструкция
Par_begin
  Proc1;
  Proc2;
Par_end;
означает, что процедуры Proc1 и Proc2 выполняются в двух параллельных потоках, принадлежащих двум асинхронным процессам.
Пример 1
Program 1;
Var ProcNum : integer;   {Глобальная переменная}
procedure Proc1;
  begin
  While True do        {Бесконечный цикл, выполняемый в процессе}
    begin
      While (ProcNum=2) do ;{*}{Проверка разрешения на вход в КУ}
      CrBlock1;        {Критический блок}
      ProcNum:=2;      {Передача разрешения на вход в КУ другому процессу}
...................    {Другие операции процесса, не входящие в КУ}
    end;
  end;
procedure Proc2;
  begin
  While True do        {Бесконечный цикл, выполняемый в процессе}
    begin
      While (ProcNum=1) do ;{*}{Проверка разрешения на вход в КУ}
      CrBlock2;        {Критический блок}
      ProcNum:=1;      {Передача разрешения на вход в КУ другому процессу}
...................    {Другие операции процесса, не входящие в КУ}
    end;
  end;
begin
  ProcNum:=1;     {Инициализация глобальной переменной}
  Par_begin       {Запуск параллельных процессов}
   Proc1;
   Proc2;
  Par_end;
end.
Процедура (подпрограмма) Proc1 выполняется процессом 1, процедура Proc2 — процессом 2. Собственно критический блок представлен процедурами (подпрограммами) CrBlock1 для процесса 1 и CrBlock2 для процесса 2. Так как процессы должны знать, что один из них вошел в свой критический блок, вводится глобальная (доступная обоим процессам) переменная ProcNum, которая, по сути дела, определяет номер процесса, имеющего право на вход в КУ. Цикл {*} представляет собой проверку разрешения на вход в КУ. Если данному процессу вход запрещен, процесс ожидает в этом цикле до установки переменной ProcNum в разрешающее значение.
В прим. 1 представлен вариант жесткой синхронизации — процессы могут выполнять свои критические участки только в определенной последовательности — сначала один, потом второй. Попробуем предложить вариант, когда возможно вхождение процессов в свои КУ в произвольном порядке.
Пример 2
Program 2;
Var CrB1, CrB2 : boolean;   {Глобальные переменная}
procedure Proc1;
  begin
  While True do        {Бесконечный цикл, выполняемый в процессе}
    begin
      While (CrB2) do ;{*}{Проверка разрешения на вход в КУ}
      CrB1:=True;      {**}{Сигнализируем второму процессу о вхождении к КУ}
      CrBlock1;        {Критический блок}
      CrB1:=False;     {Сигнализируем второму процессу о выходе из КУ}
...................    {Другие операции процесса, не входящие в КУ}
    end;
  end;
procedure Proc2;
  begin
  While True do        {Бесконечный цикл, выполняемый в процессе}
    begin
      While (CrB1) do ;{*}{Проверка разрешения на вход в КУ}
      CrB2:=True;      {**}{Сигнализируем первому процессу о вхождении к КУ}
      CrBlock2;        {Критический блок}
      CrB2:=False;     {Сигнализируем первому процессу о выходе из КУ}
...................    {Другие операции процесса, не входящие в КУ}
    end;
  end;
begin
  CrB1:=False;    {Инициализация глобальных переменных}
  CrB2:=False;    {Инициализация глобальных переменных}
  Par_begin       {Запуск параллельных процессов}
   Proc1;
   Proc2;
  Par_end;
end.
В прим. 2 каждый процесс имеет свою глобальную переменную, сообщающую о нахождении процесса в своем критическом блоке. Процесс, перед входом в критический блок, проверяет, не находится ли другой процесс уже внутри своего критического блока. Если находится — ждет, пока тот закончит выполнение КУ. Такая схема синхронизации является гибкой, так как процессы могут выполнять свои критические блоки в произвольном порядке (но не одновременно!).
Данный вариант механизма синхронизации имеет один серьезный недостаток. Так как процессы асинхронны, они оба одновременно могут подойти к выполнению строки {*}, выполнить проверку, увидеть, что конкурирующий процесс не выполняет критический блок и начать выполнение своего критического блока. То есть при одновременном выполнении процессами операции {*}, оба процесса одновременно входят в КУ и взаимоисключающая синхронизация нарушается.
Для выхода из создавшегося положения можно поменять местами операции {*} и {**}. Тогда процесс будет сигнализировать конкуренту о намерении выполнить КУ еще до проверки.
Пример 3
Program 3;
Var CrB1, CrB2 : boolean;   {Глобальные переменная}
procedure Proc1;
  begin
  While True do        {Бесконечный цикл, выполняемый в процессе}
    begin
      CrB1:=True;      {**}{Сигнализируем второму процессу о вхождении к КУ}
      While (CrB2) do ;{*}{Проверка разрешения на вход в КУ}
      CrBlock1;        {Критический блок}
      CrB1:=False;     {Сигнализируем второму процессу о выходе из КУ}
...................    {Другие операции процесса, не входящие в КУ}
    end;
  end;
procedure Proc2;
  begin
  While True do        {Бесконечный цикл, выполняемый в процессе}
    begin
      CrB2:=True;      {**}{Сигнализируем первому процессу о вхождении к КУ}
      While (CrB1) do ;{*}{Проверка разрешения на вход в КУ}
      CrBlock2;        {Критический блок}
      CrB2:=False;     {Сигнализируем первому процессу о выходе из КУ}
...................    {Другие операции процесса, не входящие в КУ}
    end;
  end;
begin
  CrB1:=False;    {Инициализация глобальных переменных}
  CrB2:=False;    {Инициализация глобальных переменных}
  Par_begin       {Запуск параллельных процессов}
   Proc1;
   Proc2;
  Par_end;
end.
В случае прим. 3 возможны проблемы, так как оба процесса могут одновременно подойти к выполнению строки {**}, одновременно установить переменные CrB1 и CrB2 в True, а затем при выполнении строки {*} будет происходить бесконечное ожидание процессами друг друга (так называемый deadlock — взаимная блокировка).
Попробуем предложить другую схему синхронизации, в которой эта проблема должна быть решена.
Пример 4
Program 4;
Var Enter1, Enter2 : boolean;   {Глобальные переменная}
procedure Proc1;
  begin
  While True do        {Бесконечный цикл, выполняемый в процессе}
    begin
      Enter1:=True;    {Сигнализируем о намерении войти в КУ}
      While (Enter2) do {Если конкурирующий процесс тоже хочет войти в КУ}
        begin
          Enter1:=False; {"Пропускаем" конкурирующий процесс}
          Delay;         {Задержка случайной длительности}
          Enter1:=True;  {*}{Снова пытаемся войти в КУ}
        end;
      CrBlock1;        {Критический блок}
      Enter1:=False;   {Сигнализируем о выходе из КУ}
...................    {Другие операции процесса, не входящие в КУ}
    end;
  end;
procedure Proc2;
  begin
  While True do        {Бесконечный цикл, выполняемый в процессе}
    begin
      Enter2:=True;    {Сигнализируем о намерении войти в КУ}
      While (Enter1) do {Если конкурирующий процесс тоже хочет войти в КУ}
        begin
          Enter2:=False; {"Пропускаем" конкурирующий процесс}
          Delay;         {Задержка случайной длительности}
          Enter2:=True;  {*}{Снова пытаемся войти в КУ}
        end;
      CrBlock2;        {Критический блок}
      Enter2:=False;   {Сигнализируем о выходе из КУ}
...................    {Другие операции процесса, не входящие в КУ}
    end;
  end;
begin
  Enter1:=False;  {Инициализация глобальных переменных}
  Enter2:=False;  {Инициализация глобальных переменных}
  Par_begin       {Запуск параллельных процессов}
   Proc1;
   Proc2;
  Par_end;
end.
Этот вариант предусматривает, что при намерении войти в КУ процесс сигнализирует конкуренту об этом. И если конкурент также пытается войти в КУ или находится в нем, "уступает" ему дорогу, вводя на случайное время задержку своего исполнения и сбросив на это время флаг Enter, сигнализирующий о намерении войти в КУ.
Вышеприведенная схема также не лишена недостатков. Если оба процесса одновременно подходят к выполнению строки {*} (а это вполне возможно в силу асинхронности выполнения процессов), они опять войдут в состояние взаимной блокировки, бесконечно "уступая" дорогу друг другу. Попробуем решить и эту проблему, введя приоритет, указывающий, какой из процессов должен "уступить" при попытке одновременного входа в КУ.
Пример 5
Program 5;
Var Enter1, Enter2 : boolean;   {Глобальные переменная}
    Pr_Choice :integer;  {Номер процесса, имеющего приоритет на вход}
procedure Proc1;
  begin
  While True do        {Бесконечный цикл, выполняемый в процессе}
    begin
      Enter1:=True;    {Сигнализируем о намерении войти в КУ}
      While (Enter2) do {Если конкурирующий процесс тоже хочет войти в КУ}
       If (Pr_Choice=2) Then  {{Ждем, пока другой процесс выйдет из КУ}
        begin
          Enter1:=False; {"Пропускаем" конкурирующий процесс}
          While (Pr_Choice=2) do ; {Ждем, пока другой процесс выйдет из КУ}
          Enter1:=True;  {*}{Снова пытаемся войти в КУ}
        end;
      CrBlock1;        {Критический блок}
      Enter1:=False;   {Сигнализируем о выходе из КУ}
      Pr_Choice=2;     {Передаем приоритет другому процессу}
...................    {Другие операции процесса, не входящие в КУ}
    end;
  end;
procedure Proc2;
  begin
  While True do        {Бесконечный цикл, выполняемый в процессе}
    begin
      Enter2:=True;    {Сигнализируем о намерении войти в КУ}
      While (Enter1) do {Если конкурирующий процесс тоже хочет войти в КУ}
       If (Pr_Choice=1) Then  {{Ждем, пока другой процесс выйдет из КУ}
        begin
          Enter2:=False; {"Пропускаем" конкурирующий процесс}
          While (Pr_Choice=1) do ; {Ждем, пока другой процесс выйдет из КУ}
          Enter2:=True;  {*}{Снова пытаемся войти в КУ}
        end;
      CrBlock2;        {Критический блок}
      Enter2:=False;   {Сигнализируем о выходе из КУ}
      Pr_Choice=1;     {Передаем приоритет другому процессу}
...................    {Другие операции процесса, не входящие в КУ}
    end;
  end;
begin
  Enter1:=False;  {Инициализация глобальных переменных}
  Enter2:=False;  {Инициализация глобальных переменных}
  Pr_Choice=1;    {Инициализируем приоритет}
  Par_begin       {Запуск параллельных процессов}
   Proc1;
   Proc2;
  Par_end;
end.
Последний пример, по сути дела, аналогичен прим. 4 за исключением того, что вводится новая глобальная переменная Pr_Choice. В случае если оба процесса одновременно подходят к своему КУ и сообщают о намерении войти в него, значение Pr_Choice определяет, какой из процессов "пропускает" конкурента при входе в КУ. Для того чтобы оба процесса имели равные права на вход в КУ, после выполнения КУ каждый процесс меняет приоритет, предоставляя в следующий раз другому процессу право на приоритетный вход в КУ.
Итак, мы рассмотрели несколько примеров решения задачи синхронизации асинхронных процессов. Последний пример лишен всех обнаруженных нами недостатков и может рассматриваться как вполне работоспособная система синхронизации. В процессе рассмотрения примеров мы пришли к следующим выводам:
Как правило, операционная система предоставляет процессам определенные средства для организации синхронизации. Наиболее распространенным из подобных средств являются семафоры.