Индекс
НазадОглавлениеВперед


Глава 8
Параллельное выполнение процессов

8.1. Постановка проблемы

Параллельными называются процессы, у которых "интервалы времени выполнения перекрываются за счет использования разных ресурсов одной и той же вычислительной системы или за счет перераспределения одного и того же набора ресурсов"[4]. При рассмотрении параллельности мы несколько расширим (только в пределах этой главы) понятие процесса: будем понимать под процессом любую последовательность действий. Процесс у нас имеет строго последовательную структуру, он выполняется операция за операцией, команда за командой. Но в один и тот же момент времени в системе могут выполняться несколько таких последовательностей. Такое расширение понимания процесса позволит нам включить в рассмотрение и такие последовательности действий, которые формально процессами не являются: отдельные нити одного процесса, модули ядра ОС, обработчики прерываний, процессы на внешних устройствах и т.д. С концептуальной точки зрения не имеет значения, является ли одновременность выполнения реальной (достигаемой за счет аппаратного распараллеливания) или виртуальной (достигаемой за счет разделения времени), хотя это различие, как мы увидим ниже, может сказываться на механизмах реализации.

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

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

Основной задачей управления параллельным выполнением является задача взаимного исключения (mutual exclusion, сокращенно - mutex): два процесса не могут выполнять одновременный доступ к разделяемым ресурсам. Обратим внимание на то обстоятельство, что взаимное исключение обеспечивается уже на аппаратном уровне. Если процессор одновременно получает два запроса, то он выполняет их последовательно по тем или иным правилам арбитража. Каждая процессорная команда обладает свойством атомарности: она или выполняется полностью, или вообще не выполняется. Так же атомарно каждое обращение к памяти. Арбитражные свойства аппаратуры являются основой для построения более сложных механизмов взаимного исключения.

Последовательность операций в процессе, которая выполняет такую единицу работы (транзакцию) с разделяемым ресурсом, во время которой никакой другой процесс не должен иметь доступа к этому ресурсу, составляет критическую секцию. Чтобы процесс мог обеспечить безопасность выполнения своей критической секции, в его распоряжении должны быть средства - "скобки критической секции" - которыми он эту критическую секцию обозначит и защитит. Назовем эти скобки csBegin и csEnd и посвятим дальнейшее рассмотрение взаимного исключения механизмам реализации этих скобок. Для доказательства правильности каждой реализации для нее необходимо показать следующее:

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

Типичным примером задачи синхронизации является обеспечение выполнения "графа синхронизации", подобного тому, который представлен на Рисунке 8.1. Граф синхронизации задает порядок выполнения действий. В программной реализации мы можем представлять действия A, B, ..., I как отдельные процессы и выполнять явную синхронизацию или, использовать неявную синхронизацию, представляя в виде процессов тройки ABC, DEF, GIH или ADG, BEH, CFI, и вводить явные точки синхронизации внутри процессов.

Более сложные задачи синхронизации, такие как "читатели-писатели" и "производители-потребители" мы рассмотрим отдельно ниже.


Рис.8.1. Пример графа синхронизации

8.2. Взаимное исключение запретом прерываний

Большинство компьютерных архитектур предусматривает в составе своей системы команд команды запрета прерываний (иногда - селективного запрета). В микропроцессорах Intel-Pentium, например, такими командами являются CLI (запретить прерывания) и STI (разрешить прерывания). Такие команды и могут составить "скобки критической секции": запрет прерываний при входе в критическую секцию и разрешение - при выходе из нее. Поскольку вытеснение процесса возможно только по прерыванию, процесс, находящийся в критической секции, не может быть прерван. Этот метод, однако, обладает большим числом недостатков:

8.3. Взаимное исключение через общие переменные

Следующая группа решений базируется на непрерываемости памяти. Представляя эти алгоритмы, мы в основном следуем первоисточнику [7] и приводим в качестве примеров как правильные, так и неправильные или неудачные варианты решений.

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

Вариант 1: общая переменная исключения.

Введем булевскую переменную mutEx, которая должна получать значение true (1), если вхождение в критическую секцию запрещено, или false (0), если вхождение разрешено. Попытка организовать "скобки критической секции" представлена следующим программным кодом:

    1   static char mutEx = 0; 
    2   void csBegin ( void ) {
    3      while ( mutEx ); 
    4      mutEx = 1;
    5  }
    6  void csEnd ( void ) {
    7      mutEx = 0;
    8  } 

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

Это решение базируется на непрерываемости доступа к памяти - к переменной mutEx, но оно является НЕПРАВИЛЬНЫМ. Рассмотрим такой случай. Пусть процесс A вошел в свою критическую секцию и установил mutEx=1. Пока процесс A выполняется внутри своей критической секции, два других процесса - B и C также подошли к своим критическим секциям и обратились к функции csBegin. Поскольку переменная mutEx установлена в 1, процессы B и C зацикливаются в строке 3 кода функции csBegin. Когда процесс A выйдет из своей критической секции и установит mutEx=0, другой процесс, например B, выйдет из цикла строки 3, но имеется вероятность того, что прежде, чем процесс B успеет выполнить строку 4 кода и этим запретить вход в критическую секцию другим процессам, выйдет из цикла строки 3 и процесс C. Таким образом, два процесса - B и C входят в критическую секцию, задача взаимного исключения не выполняется.

Хотя это решение и не выполняет взаимного исключения, оно может быть приемлемо для решения некоторых частных задач. Например, граф синхронизации, представленный на Рис.8.1, может быть обеспечен, если мы введем массив done, каждый элемент которого свяжем с определенным событием. События пронумерованы и номер события является параметром функции, сигнализирующей о завершении события - finish и функции ожидания события - waitFor:

    1  static char done[9] = {0,0,0,0,0,0,0,0,0}; 
    2  void finish ( int event ) { 
    3     done[event] = 1;
    4  }
    5  void waitFor ( int event ) { 
    6     while ( ! done[event] ); 
    7  } 

Теперь работа процессов может быть синхронизирована таким образом (функциями типа WorkX() представлена работа, выполняемая процессом X):

    1   processA() {
    2      /* работа процесса A */ 
    3      workA();  
    4      /* отметка о завершении процесса A */
    5      finish(0);
    6   }
    7   processB() {
    8      /* ожидание завершения процесса A */
    9      waitFor(0); 
    10     /* работа процесса B */ 
    11     workB(); 
    12     /* отметка о завершении процесса B */ 
    13     finish(1); 
    14  }
    15  . . . 
    16  processE() { 
    17     /* ожидание завершения процесса B */ 
    18     waitFor(1); 
    19     /* ожидание завершения процесса D */ 
    20     waitFor(3); 
    21     /* работа процесса E */ 
    22     workE(); 
    23     /* отметка о завершении процесса E */
    24     finish(4); 
    25  }
    26  . . . 

Можно сократить запись, например, так (используя естественную последовательность, заложенную в строках графа):

    1   processABC() {
    2      workA(); finish(0); 
    3      workB(); finish(1); 
    4      workC(); finish(2); 
    5   } 
    6   processDEF() {
    7      waitFor(0); workD(); finish(3); 
    8      waitFor(1); workE(); finish(4);
    9      waitFor(2); workF(); finish(5); 
    10  }
    11  processGHI() {
    12     waitFor(3); workG(); finish(6); 
    13     waitFor(4); workH(); finish(7); 
    14     waitFor(5); workI(); finish(8); 
    15  } 

или иным образом (запишите самостоятельно) - с использованием последовательности в столбцах.

Вариант 2: переменная-переключатель

Введем общую переменную right, значением ее будет номер процесса, который имеет право входить в критическую секцию. Реализация "скобок критической секции" для двух процессов с номерами 0 и будет следующей:

    1   static int right = 0; 
    2   void csBegin ( int proc ) { 
    3      while ( right != proc ); 
    4   }
    5   void csEnd( int proc ) { 
    6      if ( proc == 0) right = 1; 
    7      else right = 0; 
    8   } 

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

Данный алгоритм обеспечивает разделение процессов 0 и 1. Два процесса могут одновременно войти в функцию csBegin, но при этом они только читают переменную right. Одновременное вхождение двух процессов в функцию csEnd невозможно. При обобщении алгоритма на большее число процессов первый процесс переключает право на второй, второй - на третий и т.д., последний - на первый. Если процессы используют разные группы разделяемых данных, то каждая группа может быть защищена своим переключателем, таким образом, не запрещается одновременный доступ к разным разделяемым данным. Это делает политику более либеральной, но при наличии двух и более групп разделяемых данных возможно возникновение тупика, так как группа разделяемых данных - тот же монопольный ресурс. Для предотвращения тупика возможно введение иерархии ресурсов, как было описано в главе 5.

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

Вариант 3: неальтернативные переключатели.

Введем для каждого процесса свою переменную, отражающую его нахождение в критической секции. Эти переменные сведены у нас в массив inside. Элемент массива inside[i] имеет значение 1, если i-й процесс находится в критической секции, и 0 - в противном случае.

Для примеров этого варианта введем функцию, определяющую номер процесса-конкурента:

    int other (int proc ) {
       if ( proc == 0 ) return 1;
       else return 0;
    } 

Первое решение в этом варианте:

    1  static char inside[2] = { 0,0 }; 
    2  void csBegin ( int proc ) { 
    3     int competitor; /* конкурент */ 
    4     competitor = other ( proc ); 
    5     while ( inside[competitor] );
    6     inside[proc] = 1; 
    7  }
    8  void csEnd (int proc ) {
    9     inside[proc] = 0; 
    10 } 

Здесь и во всех последующих решениях параметр proc функций csBegin и csEnd - номер процесса, желающего войти в свою критическую секцию или выйти из нее.

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

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

В следующем решении мы меняем местами установку своего признака входа и проверку признака конкурента:

    1   static char inside[2] = { 0,0 };
    2   void csBegin ( int proc ) { 
    3      int competitor; 
    4      competitor = other ( proc ); 
    5      inside[proc] = 1; 
    6      while ( inside[competitor] ); 
    7   } 
    8   void csEnd (int proc ) {
    9      inside[proc] = 0; 
    10  } 

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

Новое решение:

    1   static char inside[2] = { 0,0 }; 
    2   void csBegin ( int proc ) { 
    3      int competitor; 
    4      competitor = other ( proc ); 
    5      do {
    6         inside[proc] = 1; 
    7         if ( inside[competitor] ) inside[proc] = 0; 
    8         } while ( ! inside[proc] ); 
    9   }
    10  void csEnd (int proc ) { 
    11     inside[proc] = 0; 
    12  } 

Процесс устанавливает свой признак вхождения (строка 6). Но если он обнаруживает, что признак вхождения конкурента тоже установлен (строка 7), то он свой признак сбрасывает. Эти действия будут повторяться до тех пор, пока наш процесс не сохранит свой признак взведенным (строка 8), а это возможно только в том случае, если признак конкурента сброшен.

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

Алгоритм Деккера

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

    1   static int right = 0; 
    2   static char wish[2] = { 0,0 }; 
    3   void csBegin ( int proc ) { 
    4      int competitor; 
    5      competitor = other ( proc ); 
    6      while (1) {
    7         wish[proc] = 1; 
    8         do { 
    9            if ( ! wish[competitor] ) return; 
    10           }
    11        while ( right != competitor ); 
    12        wish[proc] = 0; 
    13        while ( right == competitor ); 
    14        }
    15  } 
    16  void csEnd ( int proc ) { 
    17     right = other ( proc ); 
    18     wish[proc] = 0; 
    19  } 

Алгоритм предусматривает, во-первых, общую переменную right для представления номера процесса, который имеет преимущественное (но не абсолютное) право на вход в критическую секцию. Во-вторых, массив wish, каждый элемент которого соответствует одному из процессов и представляет "желание" процесса войти в критическую секцию. Процесс заявляет о своем "желании" войти в секцию (строка 7). Если при этом выясняется, что процесс-конкурент не выставил своего "желания" (строка 9), то происходит возврат из функции, то есть, процесс входит в критическую секцию независимо от того, кому принадлежало преимущественное право на вход. Если же в строке 9 выясняется, что конкурент тоже выставил "желание", то проверяется право на вход (строка 10). Если право принадлежит нашему процессу, то повторяется проверка "желания" конкурента (строки 8 - 10), пока оно не будет отменено. Конкурент вынужден будет отменить свое "желание", потому что он в этой ситуации перейдет к строке 11, где процесс, не имеющий преимущественного права, должен это сделать. После отмены своего желания процесс ждет, пока преимущественное право не вернется к нему (строка 12), а затем вновь повторяет заявление "желания" и т.д. (строки 6 - 13). Таким образом, процесс в функции csBegin либо повторяет цикл 7 - 14, либо выходит из функции и входит в критическую секцию (10).

При выходе из критической секции (функция csEnd) процесс передает преимущественное право входа конкуренту (строка 16) и отказывается от своего желания (строка 17).

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

Приведем также обобщение алгоритма Деккера на N процессов:

    1   static char wish[N+1] = { 0, ..., 0 }; 
    2   static char claimant[N+1] = { 0, ..., 0 }; 
    3   static int right = N; 
    4   void csBegin ( int proc ) { 
    5      int i; 
    6      clainmant[proc] = 1; 
    7      do { 
    8         while ( right != proc) { 
    9            wish[proc] = 0; 
    10           if(!clainmant[right]) right=proc; 
    11           }
    12        wish[proc] = 1; 
    13        for (i = 0; i<N; i++ ) 
    14           if ((i!=proc) && wish[i]) break; 
    15        } 
    16     while (i<N); 
    17  } 
    18  void csEnd ( int proc ) {
    19     right = N; 
    20     wish[proc] = clainmant[proc] = 0; 
    21  } 

Ограничимся здесь только общими замечаниями к этому алгоритму. Процессы нумеруются от 0 до N-1. Мы вводим два массива для переменных состояния, размеры массивов на 1 больше числа процессов. Последние элементы каждого из массивов соответствуют несуществующему N-му процессу, который используется как абстрактный "другой" процесс. Понятие "конкурент" здесь заменяется понятием "претендент" (clainmant). Процесс становится претендентом, входя в функцию csBegin (строка 6). В отличие от "желания", "претензия" процесса не снимается до тех пор, пока она не будет удовлетворена (строка 18). Если преимущественное право на вход в критическую секцию принадлежит другому процессу, но этот другой процесс не является претендентом, то наш процесс забирает это право себе (строки 7 - 11). При выполнении этих действий наш процесс, однако, отказывается от своего "желания", давая тем самым возможность участвовать в состязании за захват секции другим процессам (строка 9). Получив право, процесс заявляет о своем "желании" (строка 12). В последующем цикле for проверяются "желания" других процессов (строки 13 - 14). Если есть другие "желающие" то повторяется получение права и т.д. (строки 7 - 15). Если же в цикле for другие желающие не выявлены (строка 15), наш процесс входит в критическую секцию. При выходе из секции процесс сбрасывает свои "претензию" и "желание" (строка 18) и передает право несуществующему N-му процессу (строка 19).

Алгоритм Питерсона

Более компактная и изящная модификация алгоритма Деккера известна, как алгоритм Питерсона. Вот его вариант для двух процессов:

    1   static int right; 
    2   static char wish[2] = { 0,0 }; 
    3   void csBegin ( int proc ) { 
    4      int competitor; 
    5      if ( proc == 0 ) competitor = 1; 
    6      else competitor = 0; 
    7      wish[proc] = 1; 
    8      right = competitor; 
    9      while ( wish[competitor] && ( right == competitor ); 
    10  }
    11  void csEnd ( int proc ) { 
    12     wish[proc] = 0; 
    13  } 

При входе в критическую секцию процесс заявляет о своем "желании" (строка 7) и отказывается от своего преимущественного права (строка 8). Процесс будет ожидать, если его конкурент заявил свое "желание" и имеет преимущественное право (строка 9). Если нет интереса конкурента или если независимо от интереса конкурента наш процесс имеет преимущественное право, то наш процесс входит в критическую секцию. Если наш процесс отказался от своего права в строке 8, то как же это право может к нему вернуться? Право нашего процесса может быть восстановлено конкурентом, когда последний тоже войдет в функцию csBegin своего кода и выполнит строку 8. При выходе из критической секции процесс просто снимает свой интерес, и тогда его конкурент, возможно, ожидающий в строке 8, получает возможность выхода из цикла строки 9 по первой части условия.

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

Но:

8.4. Команда testAndSet и блокировки

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

    int atomic testAndSet ( char *lock ) { 
       char var;
       var = *lock;
       *lock = 1; 
       return var; 
    } 

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

Команда проверяет (возвращает) значение некоторой переменной, а затем устанавливает ее значение в 1. Введенный нами описатель функции atomic показывает, что функция непрерываемая, во время ее выполнения никакой другой процесс не имеет доступа к той памяти, с которой работает функция (к переменной lock). Функция, как мы видим, выполняет два обращения к переменной lock, но оба они выполняются как одна транзакция.

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

Так, для реализации "канонической" функции testAndSet при помощи команды XCHG нужны две команды:
    MOV al,1
    XCHG al,lock 

Переменная lock устанавливается в 1, а ее прежнее значение сохраняется в регистре AL.

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

Наличие в арсенале программиста команды testAndSet позволяет ему организовать простую и надежную защиту критической секции при помощи переменной-замка:

    1   void csBegin ( char *lock ) { 
    2      while ( testAndSet( lock ) ); 
    3   }
    4   void csEnd ( char *lock ) { 
    5      *lock = 0; 
    6   } 

Команда testAndSet (строка 2) будет возвращать 1 до тех пор, пока другой процесс находится в критической секции, защищенной замком. Как только этот другой процесс выйдет из критической секции и установит замок в 0 (строка 5), наш процесс тут же вновь установит его в 1 и выйдет из цикла. Вследствие атомарности testAndSet никакой другой процесс не сможет изменить состояние замка между теми моментами, когда наш процесс считает его нулевое значение и установит его значение в 1.

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

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

Замки, обеспечиваемые командой testAndSet, обладают, следовательно, такими свойствами:

8.5. Семафоры

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

Такая возможность обеспечивается:

V-операция есть операция с одним операндом, который должен быть семафором. Выполнение операции состоит в увеличении значения аргумента на 1, это действие должно быть атомарным.

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

Атомарность P-операции и является потенциальной задержкой: если процесс пытается выполнить P-операцию над семафором, значение которого в данный момент нулевое, данная P-операция не может завершиться пока другой процесс не выполнит V-операцию над этим семафором. Несколько процессов могут начать одновременно P-операцию над одним и тем же семафором. Тогда при установке семафора в 1 только одна из P-операций завершится, какая именно - мы обсудим позже.

Защита разделяемых ресурсов теперь выглядит следующим образом. Каждый ресурс защищается своим семафором, значение которого может быть 1 - свободен или 0 - занят. Процесс, выполняющий доступ к ресурсу, инициирует P-операцию (эквивалент csBegin). Если ресурс занят - процесс задерживается в своей P-операции до освобождения ресурса. Когда ресурс освобождается, P-операция процесса завершается, и процесс занимает ресурс. При освобождении ресурса процесс выполняет V-операцию (эквивалент csEnd).

Э.Дейкстра [7], вводя семафорные примитивы для синхронизации и взаимного исключения, исходил из гипотезы о том, что P- и V-операции реализованы в нашей вычислительной системе аппаратно. На самом же деле, в составе любого набора команд таких операций нет - и это оправданно. Программная реализация семафоров позволяет нам включить в них блокировку и диспетчеризацию процессов, чего нельзя было бы делать на аппаратном уровне.

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

    1   typedef struct { 
    2      int value; 
    3      char mutEx;
    4      process *waitList; 
    5   } semaphore; 

Здесь value - та самая целочисленная переменная, которая представляет значение семафора в приведенном выше определении. mutEx - переменная взаимного исключения, которая обеспечивает, как мы увидим ниже, атомарность операций над семафорами. waitList - указатель на список процессов, ожидающих установления этого семафора в 1. (Здесь мы предполагаем линейный однонаправленный список, но очередь ожидающих процессов может быть представлена и любым другим образом.)

Мы начинаем рассмотрение с, так называемых, двоичных семафоров, для которых допустимые значения - 0 и 1. Если семафор защищает критическую секцию, то начальное значение поля value = 1. Начальные значения других полей: mutEx = 0; waitList = NULL.

Операции над семафорами можно представить в виде следующих функций:

    1   void P ( semaphore *s ) {
    2      csBegin (&s->mutEx);
    3      if (!s->value) block(s); 
    4      else { 
    5         s->value--; 
    6         csEnd (&s->mutEx); 
    7         } 
    8   }
    9   void V ( semaphore *s ) { 
    10     csBegin (&s->mutEx);
    11     if(s->waitList!= NULL) unBlock(s);
    12     else s->value++; 
    13     csEnd (&s->mutEx); 
    14  } 

В нашей реализации вы видите "скобки критической секции" как элементарные операции. Они обеспечивают атомарность выполнения семафоров и могут быть реализованы любым из описанных выше корректных способов. Здесь мы ориентируемся на команду testAndSet с использованием поля семафора mutEx в качестве замка, но это может быть и любая другая корректная реализация (в многопроцессорных версиях Unix, например, используется алгоритм Деккера). Вопрос: в чем же мы выигрываем, если в csBegin все равно используется занятое ожидание? Дело в том, что это занятое ожидание не может быть долгим. Этими "скобками критической секции" защищается не сам ресурс, а только связанный с ним семафор. Выполнение же семафорных операций происходит быстро, следовательно, и потери на занятое ожидание будут минимальными.

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

Когда процесс выполняет V-операцию (освобождает ресурс), проверяется очередь ожидающих процессов и разблокируется один из них. В системном вызове unBlock можно реализовать любую дисциплину обслуживания очереди, в том числе, и такую, которая предупреждает возможность бесконечного откладывания процессов в очереди. Если разблокируется какой-либо процесс, то значение семафора так и остается нулевым, если же очередь ожидающих пуста, то значение семафора увеличивается на 1.

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

Итак, общие свойства решения задачи взаимного исключения с помощью семафоров таковы:

Для решения задачи взаимного исключения достаточно двоичных семафоров. Мы, однако, описали тип поля value как целое число. В приведенном нами выше определении Дейкстры речь тоже идет о целочисленном, а не о двоичном значении. Семафор, который может принимать неотрицательные значения, большие 1, называется общим семафором. Такой семафор может быть очень удобен, например, при управлении не единичным ресурсом, а классом ресурсов. Начальное значение поля value для такого семафора устанавливается равным числу единиц ресурса в классе. Каждое выделение единицы ресурса процессу сопровождается P-операцией, уменьшающей значение семафора. Семафор, таким образом, играет роль счетчика свободных единиц ресурса. Когда этот счетчик достигнет нулевого значения, процесс, выдавший следующий запрос на ресурс, будет заблокирован в своей P-операции. Освобождение ресурса сопровождается V-операцией, которая разблокирует процесс, ожидающий ресурс, или наращивает счетчик ресурсов.

Общие семафоры могут быть использованы и для простого решения задачи синхронизации. В этом случае семафор связывается с каким-либо событием и имеет начальное значение 0. (Событие может рассматриваться как ресурс, и до наступления события этот ресурс недоступен). Процесс, ожидающий события, выполняет P-операцию и блокируется до установки семафора в 1. Процесс, сигнализирующий о событии, выполняет над семафором V-операцию. Для графа синхронизации, например, показанного на рис.8.1, мы свяжем с каждым действием графа одноименный семафор. Тогда каждое действие (например, E) должно быть оформлено следующим образом:

    1   procE () {
    2      /*ожидание событий B и D*/
    3      P(B); P(D); 
    4      . . . 
    5      /* сигнализация о событии E для двух 
    6      ожидающих его действий (F и H) */ 
    7      V(E); V(E); 
    8   } 

Ниже мы рассмотрим применение семафоров для более сложного варианта задачи синхронизации.

8.6. "Производители-потребители"

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

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

    1   static semaphore *portCnt = { 0, 0, NULL };
    2   static ... buffer ...; 
    3   /* процесс-производитель */ 
    4   void producer ( void ) { 
    5      while (1) { 
    6         < производство порции > 
    7         < добавление порции в буфер > 
    8         V(portCnt); 
    9         } 
    10  } 
    11  /* процесс-потребитель */ 
    12  void consumer ( void ) { 
    13     while (1) { 
    14        P(portCnt) 
    15        < выборка порции из буфера > 
    16        < обработка порции > 
    17        }
    18  } 

Исходное значение семафора portCnt - 0. Производитель каждую итерацию своего цикла заканчивает V-операцией, увеличивающей значение счетчика. Потребитель каждую свою итерацию начинает P-операцией. Если буфер пуст, то потребитель задержится в своей P-операции до появления в буфере очередной порции. Таким образом, если потребитель работает быстрее производителя, он будет время от времени простаивать, если производитель работает быстрее - в буфере будут накапливаться порции.

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

    1   static semaphore *portCnt = { 0, 0, NULL }, 
    2   *freeCnt = { BSIZE, 0, NULL }, 
    3   static ... buffer [BSIZE]; 
    4   /* процесс-производитель */ 
    5   void producer ( void ) { 
    6      while (1) { 
    7         < производство порции > 
    8         P(freeCnt); 
    9         < добавление порции в буфер >
    10        V(portCnt); 
    11        } 
    12  }
    13  /* процесс-потребитель */ 
    14  void consumer ( void ) { 
    15     while (1) { 
    16        P(portCnt) 
    17        < выборка порции из буфера >
    18        V(freeCnt); 
    19        < обработка порции > 
    20        } 
    21  } 

Попытаемся теперь обобщить решение для произвольного числа производителей и потребителей. Но в таком обобщении мы сталкиваемся с еще одной существенной особенностью. В вышеприведенных решениях мы допускали одновременное выполнение операций <добавление порции в буфер> и <выборка порции из буфера> . Очевидно, что при любой организации буфера производитель и потребитель могут одновременно работать только с разными порциями информации. Иначе обстоит дело с многочисленными производителями и потребителями. Два производителя могут попытаться одновременно добавить порцию в буфер и выбрать для этого одно и то же место в буфере. Аналогично, два потребителя могут попытаться выбрать из буфера одну и ту же порцию. В следующем примере мы для наглядности представляем буфер в виде кольцевой очереди с элементами (порциями) одинакового размера:

    1   typedef ... portion; /* порция информации */ 
    2   static portion buffer [BSIZE]; 
    3   static int wIndex = 0, rIndex = 0; 
    4   static semaphore *portCnt = { 0, 0, NULL }, 
    5   *freeCnt = { BSIZE, 0, NULL }, 
    6   *rAccess = { 1, 0, NULL }, 
    7   *wAccess = { 1, 0, NULL };
    8   /* имеется NP аналогичных процессов-производителей */ 
    9   void producer ( void ) { 
    10     portion work;
    11     while (1) { 
    12        < производство порции в work > 
    13        P(wAccess); 
    14        P(freeCnt); 
    15        /* добавление порции в буфер */ 
    16        memcpy(buffer+wIndex,&work, sizeof(portion) ); 
    17        if ( ++wIndex == BSIZE ) w_index = 0; 
    18        V(portCnt); 
    19        V(wAccess); 
    20     } 
    21  } 
    22  /* имеется NC аналогичных процессов-потребителей */ 
    23  void consumer ( void ) { 
    24     portion work; 
    25     while (1) { 
    26        P(rAccess); 
    27        P(portCnt) 
    28        /* выборка порции из буфера */ 
    29        memcpy(&work, buffer+rIndex, sizeof(portion) ); 
    30        if ( ++rIndex == BSIZE ) rIndex = 0; 
    31        V(freeCnt); 
    32        V(rAaccess); 
    33        < обработка порции в work> 
    34     } 
    35  } 

Мы оформляем обращения к буферу как критические секции, защищая их семафорами rAccess и wAccess. Поскольку конфликтовать (пытаться работать с одной и той же порцией в буфере) могут только однотипные процессы, мы рассматриваем буфер как два ресурса: ресурс для чтения и ресурс для записи и каждый такой ресурс защищается своим семафором. Таким образом запрещается одновременный доступ к буферу двух производителей или двух потребителей, но разрешается одновременный доступ одного производителя и одного потребителя.

8.7. Конструкции критических секций в языках программирования

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

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

    shared int x;
    . . .
    section ( x ) {
       < операторы, работающие с переменной x >
    } 

Конструкция section определяет критическую секцию. Вместо специальных "скобок критической секции" используется заголовок section и обычные операторные скобки. Последнее дает возможность проверять правильность оформления критической секции на синтаксическом уровне - на этапе трансляции программы, а не ее выполнения и предупреждает возможность появления самой распространенной ошибки программистов - непарных скобок. Определение переменной x со специальным описателем shared позволяет выявить (опять на этапе компиляции) все попытки доступа к ней вне критической секции.

Реализация этой конструкции очевидна: переменная x защищается скрытым семафором, над которым производится P-операция при входе в секцию и V-операция - при выходе из нее.

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

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

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

    1   shared struct { 
    2      portion buffer [BSIZE]; 
    3      int stPtr; 
    4   } stack = { {...}, 0 }; 
    5   void producer ( void ) { 
    6      portion work; 
    7      while (1) { 
    8         < производство порции в work > 
    9         section ( stack ) { 
    10           await ( stack.stRtr < BSIZE ); 
    11           memcpy ( stack.buffer + stack.stPtr++, &work, sizeof(portion) ); 
    14        } 
    15     }
    16  }
    17  void consumer ( void ) { 
    18     portion work; 
    19     while (1) { 
    20        section ( stack ) { 
    21        await( stack.stPtr > 0 ); 
    22        memcpy ( &work, stack.buffer + --stack.stPtr, sizeof(portion) ); 
    25        }
    26     < обработка порции в work> 
    27     } 
    28  } 

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

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

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

8.8. Мониторы

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

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

Если в задаче "производители-потребители" процессы программируются пользователем, то вид этих процессов может быть таким:

    1   #include <monitor.h> 
    2   /*== процесс-производитель (может быть отдельным модулем) ==*/ 
    3   void producer ( void ) { 
    4      portion work; 
    5      while (1) { 
    6         < производство порции в work > 
    7         putPortion ( &work ); 
    8      }
    9   }
    10  /*== процесс-потребитель (может быть отдельным модулем) ==*/ 
    11  void consumer ( void ) { 
    12     portion work; 
    13     while (1) { 
    14        getPortion ( &work ); 
    15        < обработка порции в work> 
    16     }
    17  } 

Обратим внимание на то, что процессы, во-первых, никоим образом не заботятся о разделении данных, во-вторых, не используют никакие общие данные. Такая "беззаботная" работа процессов, однако, должна быть поддержана монитором, входные точки которого описаны в файле monitor.h, а определение его имеет такой вид:

    1   /*== монитор производителей-потребителей (отдельный модуль) ==*/ 
    2   #define BSIZE ... 
    3   /* буфер */ 
    4   static portion buffer [BSIZE];       
    5   /* индексы буфера для чтения и записи*/ 
    6   static int rIndex = 0, wIndex = 0; 
    7   /* счетчик заполнения */ 
    8   static int cnt = 0; 
    9   /* события НЕ_ПУСТ, НЕ_ПОЛОН */ 
    10  static event nonEmpty, nonFull; 
    11  /*== процедура занесения порции в буфер ==*/ 
    12  void guard putPortion ( portion *x ) { 
    13     /* если буфер полон - ожидать события НЕ_ПОЛОН */ 
    14     if ( cnt == BSIZE ) wait (nonFull); 
    15     /* запись порции в буфер */ 
    16     memcpy ( buffer + wIndex, x, sizeof(portion) ) ;
    17     /* модификация индекса записи */ 
    18     if ( ++wIndex == BSIZE ) wIndex = 0;
    19     cnt++; /* подсчет порций в буфере */ 
    20     /* сигнализация о том, 
    21        что буфер НЕ_ПУСТ */ 
    22     signal (nonEmpty); 
    23  }
    24  /*== процедура позучения порции из буфера ==*/ 
    25  void guard getPortion ( portion *x ) { 
    26     if ( cnt == 0 ) wait (nonEmpty); 
    27     memcpy ( x, buffer + rIndex, sizeof(portion) ) ; 
    28     if ( ++rIndex == BSIZE ) rIndex = 0; 
    29     cnt++; 
    30     signal (nonFull); 
    31  } 

В реализации монитора нам пришлось прибегнуть к некоторым новым обозначениям. Во-первых, функции монитора даны с описателем guard (охрана). Это означает, что они должны выполняться в режиме взаимного исключения. В литературе часто употребляется образное сравнение мониторов с комнатой, в которой может находиться только один человек. Такая комната показана на Рисунке 8.2. Если человек (процесс) желает войти в комнату (охраняемую процедуру монитора), то он становится во входную очередь к двери 1, в которой он ожидает (блокируется) до тех пор, пока комната (монитор) не освободится. Дверь 1 (вход) отпирается только в том случае, если комната пуста, пропускает только одного человека и запирается за ним. Дверь 2 (выход) не заперта, когда она открывается, отпирается и дверь 1.


Рис. 8.2. Простая модель монитора

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

Другие наши нововведения связаны с блокировками внутри охраняемой процедуры. Мы ввели тип данных, названный нами event. Этот тип представляет некоторое событие. Примитив wait проверяет наступление этого события и переводит процесс в ожидание, если событие еще не произошло. Примитив signal сигнализирует о наступлении события. Событие является потребляемым ресурсом: если два процесса ожидают одного и того же события, то при наступлении события разблокирован будет только один из процессов, другой будет вынужден ждать повторного наступления такого же события.

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

Общий подход к решению этой проблемы иллюстрируется расширением модели "одноместной комнаты", показанным на Рисунке 8.3. Для каждого события, которое может ожидаться в мониторе, мы водим свою очередь с соответствующими входными и выходными дверями для нее. На рисунке эти очереди показаны внизу монитора. Мы вводим также очередь, которую мы называем приоритетной. Процессы, находящиеся в очередях, не считаются находящимися в мониторе. "Правила для посетителей" комнаты-монитора следующие.

  1. Новый процесс поступает во входную очередь. Новый процесс может войти в монитор через дверь 1 только, если в мониторе нет других процессов.
  2. Если процесс выходит из монитора через дверь 2 (выход), то в монитор входит процесс из двери 4 - из приоритетной очереди. Если в приоритетной очереди нет ожидающих, входит процесс из двери 1 (если есть ожидающие за ней).
  3. Процесс, выполняющий операцию wait, выходит из монитора в дверь, ведущую в соответствующую очередь (5 или 7).
  4. Если процесс выполняет операцию signal, то проверяется очередь, связанная с событием. Если эта очередь непуста, то сигнализирующий процесс уходит в приоритетную очередь (дверь 3), а в монитор входит один процесс из очереди к событию (дверь 6 или 8). Если очередь пуста, сигнализирующий процесс остается в мониторе.
  5. Все очереди обслуживаются по дисциплине FCFS.


Рис.8.3. Расширенная модель монитора

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

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

Возможно решение, в котором операция signal разблокирует все процессы, находящиеся в соответствующей очереди. Поскольку все ожидавшие процессы не могут вместе войти в монитор, в нем остается только один из них, успевший "подхватить" событие, а остальные направляются в приоритетную очередь. Процесс, который разблокировался таким образом, уже не может, однако, быть уверенным в том, что его разблокирование гарантирует наступление события (событие могло быть перехвачено другим процессом). Поэтому в проверке условия ожидания оператор if для такой реализации должен быть заменен оператором while, например, строки 11, 12 последнего примера должны выглядеть так:

11  / если буфер полон - ожидать события НЕ_ПОЛОН */ 
12  while ( cnt == BSIZE ) wait (nonFull); 

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

8.9. "Читатели-писатели" и групповые мониторы

Еще одна классическая задача синхронизации называется задачей "читателей-писателей" и формулируется следующим образом. Имеется произвольное число процессов-писателей и процессов-читателей, которые совместно используют какие-то данные (обычно имеется в виду файл). В любой момент процесс-читатель может потребовать прочитать данные. В любой момент процесс-писатель может потребовать прочитать или записать данные. Чтение и запись данных - операции длительные, но конечные. В то время, когда процесс записывает данные, никакие другие читатели или писатели не должны иметь доступа к данным. Любое число процессов может читать данные одновременно. Решение должно обеспечивать целостность данных и отсутствие бесконечного откладывания процессов.

Существенные отличия этой задачи от задачи производителей-потребителей состоят в следующем:

Нам не удастся решить эту задачу при помощи мониторов, описанных в предыдущем разделе, так как, если мы сделаем процедуры read и write охраняемыми, то, во-первых, у нас получатся слишком большие (длительные) критические секции, а во-вторых, мы исключим параллельное выполнение читателей.

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

где proc - идентификатор процесса.

Структура самого монитора в общих чертах следующая:

    1     int rdCnt = 0;  /* счетчик читателей */
    2     char wrFlag = 0; /* признак активности записи */
    3     /* списки - писателей и читателей */ 
    4     process *wrCrowd=NULL, *rdrowd=NULL;
    5     /* события: МОЖНО_ЧИТАТЬ, МОЖНО_ПИСАТЬ */ 
    6     event mayRead, mayWrite; 
    7     /*== процедура регистрации читателя ==*/ 
    8     void guard startRead ( process *p ) { 
    9        rdCnt++;  /* подсчет читателей */
    10       /* если идет запись - ожидать МОЖНО_ЧИТАТЬ */ 
    11       if ( wrFlag ) wait (mayRead); 
    12       /* дублирование сигнала для другого читателя */ 
    13       signal (mayRead); 
    14       /* включение в список читателей */ 
    15       inCrowd ( rdCrowd, p ); 
    16    }
    17    /*== процедура открепления читателя ==*/ 
    18    void guard endRead ( process *p ) { 
    19       /* исключение из списка читателей */ 
    20       fromCrowd ( rdCrowd, p ); 
    21       /* уменьшение числа читателей, 
    22          если читателей больше нет - сигнализация МОЖНО_ПИСАТЬ */ 
    23       if ( --rdCnt==0 ) signal(mayWrite); 
    24    }
    25    /*== процедура регистрации писателя ==*/ 
    26    void guard startWrite ( process *p ) {
    27       /* если есть другие читатели или писатели - ждать */ 
    28       if ( wrFlag||rdCnt ) wait(mayWrite); 
    29       /* установка признака записи */ 
    30       wrFlag = 1; 
    31       /* писатель включается в оба списка*/ 
    32       inCrowd ( rdCrowd, p ); 
    33       inCrowd ( wrCrowd, p ); 
    34    }
    35    /*== процедура открепления писателя ==*/ 
    36    void guard endWrite ( process *p ) { 
    37       wrFlag=0; /* сброс признака записи */ 
    38       /* исключение из списков */ 
    39       fromCrowd ( rdCrowd, p ); 
    40       fromCrowd ( wdCrowd, p ); 
    41       /* если есть претенденты-читатели - разрешение им */ 
    42       if ( rdCnt ) signal (mayRead); 
    43       /* иначе - разрешение на запись */ 
    44       else signal (mayWrite); 
    45    }
    46    /*== процедура чтения ==*/ 
    47    void read ( process *p, 
    48          < другие параметры > ) { 
    49       /* если процесс не зарегистрирован читателем - отказ */ 
    50       if (!checkCrowd(rdCrowd, p)) <отказ>; 
    51       else < чтение данных >; 
    52    }
    53    /*== процедура записи ==*/ 
    54    void write ( process *p, 
    55           < другие параметры > ) { 
    56       /* если процесс не зарегистрирован писателем - отказ */ 
    57       if (!checkCrowd(wrCrowd,p)) <отказ>; 
    58       else < запись данных >; 
    59    } 

Прежде, чем процесс получит доступ к данным, он должен зарегистрироваться как читатель или как писатель. В нашем примере переменные rdCrowd и wrCrowd (строка 4) являются указателями на списки читателей и писателей соответственно, хотя можно интегрировать процессы в группы и любым другим способом. Используемые (но не определенные) нами функции inCrowd и fromCrowd обеспечивают включение процесса в группу и исключение из группы, а функция checkCrowd возвращает 1, если указанный процесс входит в группу (иначе - 0). Процедура read выполняется только для процессов, включенных в группу читателей (строки 50, 51), а write - только для включенных в группу писателей (строки 57, 58). Переменная rdCnt (строка 2) - счетчик текущего числа читателей, переменная wrFlag (строка 4) - счетчик писателей (или признак наличия писателя, так как писателей не может быть более одного). События mayRead и mayWrite (строка 9) являются разрешениями читать и писать соответственно.

Входная точка startRead (строка 8) выполняет регистрацию читателя. Это охраняемая процедура. Она наращивает счетчик читателей, но если в данный момент работает писатель, то потенциальный читатель блокируется до наступления события mayRead (строка 11). После того, как процесс будет разблокирован (или если он не блокировался вообще), он выдает сигнал mayRead (строка 13), который предназначается для другого читателя, возможно, также ждущего разрешения на чтение (можно сказать, что процесс этим восстанавливает потребленный им ресурс), и включается в список читателей. После завершения доступа читатель обращается к входной точке endRead (строка 18). Эта процедура исключает процесс из списка читателей, уменьшает счетчик читателей и, если читателей больше не осталось, сигнализирует разрешение на запись.

Писатель регистрируется/разрегистрируется через входные точки startWrite/endWrite (строки 26-36). При регистрации потенциальный писатель может быть заблокирован, если в настоящий момент зарегистрирован другой писатель или хотя бы один читатель (строка 28). Сигнал mayWrite разблокирует писателя, и он включается в обе группы (строки 32, 33), так как имеет право и читать, и писать. При откреплении писатель исключается из групп. Если за время его работы попытался зарегистрироваться хотя бы один читатель, выдается разрешение на чтение (строка 42), в противном случае - разрешение на запись для другого писателя, возможно, ждущего своей очереди (строка 44).

8.10. Примитивы синхронизации в языках программирования

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

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

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

Вот как решается с помощью счетчиков событий задача для одного производителя и одного потребителя:

    1   typedef unsigned int eventcounter; /* тип данных - счетчик событий */  
    2   static eventcounter inCnt = 0, outCnt = 0; /* счетчики для чтения и записи */
    3   static portion buffer [BUFSIZE]; /* буфер */ 
    4   /*== процесс-потребитель ==*/ 
    5   void consumer ( void ) { 
    6     int portNum;  /* номер порции */ 
    7     portion work; /* рабочая область порции */
    8     /* цикл потребления */ 
    9     for ( portNum = 1; ; portNum++ ) {
   10        /* ожидание доступности порции по номеру */ 
   11        await (inCnt, portNum); 
   12        /* выборка из буфера */
   13        memcpy (&work, buffer + portNum % BSIZE, sizeof(portion) ); 
   14        /* продвижение счетчика записи */ 
   15        advance (outCnt); 
   16        < обработка порции в work > 
   17     } 
   18  }
   19  /*== процесс-производитель ==*/ 
   20  void producer ( void ) { 
   21     int portNum;  /* номер порции */ 
   22     portion work; /* рабочая область для порции */ 
   23     /* цикл производства */ 
   24     for ( portNum = 1; ; portNum++ ) { 
   25        < производство порции в work >
   26        /* ожидание доступности порции по номеру */ 
   27        await (outCnt, portNum - BSIZE); 
   28        /* запись в буфер */ 
   29        memcpy (buffer + portNum % BSIZE, &work, sizeof(portion) ); 
   30        /* продвижение счетчика чтения */ 
   31        advance (inCnt); 
   32     } 
   33  } 

Как мы уже отмечали выше, производитель и потребитель работают с разными секциями буфера, и взаимное исключение для них не требуется. Процессы - производитель и потребитель - могут перекрываться в любых своих фазах, кроме операций advance (строки 15 и 31). Переменные inCnt и outCnt являются счетчиками событий - производства порции и потребления порции соответственно. Кроме того, каждый процесс хранит в собственной локальной переменной portNum - номер порции, с которой ему предстоит работать (счет начинается с 1). Потребитель ждет, пока счетчик производств не достигнет номера очередной его порции, затем выбирает порцию из буфера и увеличивает счетчик потреблений. Производитель работает симметрично. Обратите внимание на второй параметр операции await в производителе (строка 27). Он задается таким, чтобы обеспечить отсутствие ожидания при наличии хотя бы одной свободной секции в буфере.

Другой механизм синхронизации носит название секвенсоров (sequencer). Буквальный перевод этого слова - "упорядочиватель" - так называются средства, которые выстраивают неупорядоченные события в определенном порядке. Как и счетчик событий, секвенсор представляется целым числом, над которым выполняется единственная операция: ticket. Операция ticket(S) возвращает текущее значение секвенсора и увеличивает его на 1. Операция является атомарной. Начальное значение секвенсора - 0.

Имея в своем распоряжении секвенсоры мы можем так записать решение задачи производителей-потребителей для произвольного числа процессов:

    1   /* типы данных - счетчик событий и секвенсор */ 
    2   typedef unsigned int eventcounter;
    3   typedef unsigned int sequencer; 
    4   static eventcounter inCnt = 0, outCnt = 0; /* счетчики для чтения и записи */
    5   /* секвенсоры для чтения и записи */
    6   static sequencer inSeq = 0, outSeq = 0;
    7   static portion buffer [BUFSIZE]; /* буфер */ 
    8   /*== процесс-производитель ==*/ 
    9   void producer ( void ) { 
   10      int portNum;  /* номер порции */ 
   11      portion work; /* рабочая область для порции */ 
   12      /* цикл производства */ 
   13      while (1) {
   14         < производство порции в work > 
   15         /* получение "билета"  на запись порции */ 
   16         portNum = ticket (inSeq); 
   17         /* ожидание номера порции */ 
   18         await (inCnt, portNum); 
   19         /* ожидание свободного места в буфере */ 
   20         await (outCnt, portNum - BSIZE+1); 
   21         /* запись в буфер */ 
   22         memcpy (buffer + portNum % BSIZE, &work, sizeof(portion) ); 
   23         /* продвижение счетчика чтения */ 
   24         advance (inCnt); 
   25      } 
   26   }
   27   /*= процесс-потребитель =*/ 
   28   void consumer ( void ) { 
   29      int portNum;  /* номер порции */ 
   30      portion work; /* рабочая область для порции */ 
   31      /* цикл потребления */ 
   32      while (1) { 
   33         /* получение "билета" на выборку порции */ 
   34         portNum = ticket (outSeq);
   35         /* ожидание номера порции */ 
   36         await (outCnt, portNum); 
   37         /* ожидание появления в буфере */ 
   38         await (inCnt, portNum+1); 
   39         /* выборка порции */ 
   40         memcpy (&work, buffer + portNum % BSIZE, sizeof(portion) ); 
   41         /* продвижение счетчика записи */ 
   42         advance (outCnt); 
   43         < обработка порции в work > 
   44      }
   45   } 

Каждый производитель получает "билет" со своим номером в очереди на запись в буфер (строка 16). Затем он ожидает, когда до него дойдет очередь (строка 18), ожидает освобождения места в буфере (строка 20), записывает информацию (строки 22, 23) и наращивает счетчик производств (строка 24). Увеличение счетчика событий inCnt является сигналом к разблокированию как для потребителя, получившего "билет" на выборку этой порции и ожидающего в строке 36, так и для производителя, получившего "билет" на запись следующей порции и ожидающего в строке 20. Полученный процессом "билет" определяет и адрес в буфере той секции, с которой будет работать процесс. Хотя каждый процесс работает со своей секцией в буфере, одновременный доступ к буферу однотипных процессов исключается ожиданием в строке 18 или 36. Если разрешить одновременный доступ к буферу двух, например, производителей, то процесс, получивший "билет" на запись порции в n-ю секцию буфера может закончить запись раньше, чем процесс, пишущий порцию в n-1-ю секцию, даже если последний начал запись раньше. Процесс, закончивший запись, увеличит счетчик inCnt и выйдет из ожидания потребитель, имеющий билет на n-1-ю секцию, запись в которую еще не закончена.

8.11. Рандеву

Модель взаимодействия процессов, названная рандеву, рассматривает синхронизацию и передачу данных как единую деятельность. Когда процесс A намерен передать данные процессу B, оба процесса должны объявить о своей готовности установить связь, выдав запросы на передачу и прием данных соответственно. Если процесс A выдает заявку на передачу прежде, чем процесс B выдал заявку на прием, то процесс A приостанавливается до выдачи заявки процессом B. И наоборот: если процесс B выдал заявку на прием раньше, чем процесс A на передачу, то приостанавливается процесс B. Таким образом, процессы взаимодействуют только при встрече (рандеву) их заявок на передачу и прием.

В абстрактной записи взаимодействие между процессами записывается так:

    1   processA { 
    2      объявление локальной переменной x; 
    3      . . . 
    4      B!x; 
    5      . . . 
    6   } 
    7   processB { 
    8      объявление локальной переменной y; 
    9      . . . 
    10     A?y;
    11     . . . 
    12  } 

Нотация B!x в строке 4 означает, что процесс A передает процессу B значение своей переменной x. A?y в строке 10 означает, что процесс B принимает значение, переданное процессом A, и записывает его в свою переменную y.

Эта запись отражает, так называемую, синхронную модель рандеву. Запись асинхронной модели мы можем получить, заменив строку 10 на:

    10  ?y; 

В синхронной модели оба процесса должны указывать в операторах приема или передачи имя процесса-корреспондента. В асинхронной модели только процесс-передатчик указывает имя процесса-приемника. "Безадресный" оператор приема соответствует идеям структуризации данных и программирования "снизу вверх", развивавшимся автором моделей рандеву и мониторов - К.Хоаром [6]. Асинхронная модель делает возможным разработку библиотечных процессов, которые, во-первых, могут использоваться в разных разработках, а во-вторых, играть роль процессов-серверов, обрабатывающих запросы от разных параллельно выполняющихся процессов-клиентов.

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

Процесс в языке ADA называется задачей и описание задачи состоит из спецификаций задачи и ее тела. Спецификация имеет структуру:

    task ИМЯ_ЗАДАЧИ is
       < описания входных точек >
    end; 
Тело имеет структуру:
    task body ИМЯ_ЗАДАЧИ is
       < переменные и операторы >
    end ИМЯ_ЗАДАЧИ; 

В спецификации указываются точки входа задачи для рандеву. Их описания идентичны описаниям процедур: имя и параметры с указанием направления передачи параметров: in, out или inout. В задаче, обращающейся ко входной точке, обращение выглядит точно так же, как обращение к процедуре. Однако, выполняется такое обращение иначе. В задаче-приемнике такое обращение обрабатывается оператором приема. В простейшем случае такой оператор имеет вид:

    accept ИМЯ_ВХОДА ( < параметры > ) do
       < операторы >
    end; 

Оператор приема входит в структуру последовательно выполняемых операторов тела задачи. Если при обращении к данному входу выполнение задачи-приемника еще не дошло до оператора приема, то задача-передатчик блокируется. Если выполнение дошло до оператора приема, но обращения к данному входу не было, блокируется задача-приемник.

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

    select
       < оператор accept >
       < другие операторы >
    or
       < оператор accept >
       < другие операторы >
    or
       . . .
    else
       < другие операторы >
    end; 

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

Операторы accept, составляющие альтернативы отбора, могут быть "защищены" условиями. Заголовок оператора в этом случае выглядит так:

    when <логическое выражение > =>
       accept 
       ... 

Защищенный оператор приема включается в число альтернатив отбора только в том случае, если логическое выражение имеет значение "истина".

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

    1   PROD_CONS: declare; 
    2   /* пустая спецификация производителя */ 
    3   task PRODUCER is 
    4      end; 
    5   /* тело производителя */ 
    6   task body PRODUCER is 
    7      /* рабочая область для порции */ 
    8      WORK : PORTION;   
    9      begin 
    10        loop /* цикл производства */ 
    11           < производство порции в WORK > 
    12           PUTPORTION(WORK); /* запись порции */ 
    13           end loop; /* конец цикла производства */ 
    14        end PRODUCER;/* конец тела производителя */ 
    15  /* пустая спецификация потребителя */ 
    16  task CONSUMER is 
    17     end; 
    18  /* тело потребителя */ 
    19  task body CONSUMER is 
    20     /* рабочая область для порции */ 
    21     WORK : PORTION;   
    22     begin 
    23        loop /* цикл потребления */ 
    24           GETPORTION ( WORK ); /* выборка порции */ 
    25           < обработка порции в WORK > 
    26           end loop; /* конец цикла потребления */ 
    27        end CONSUMER; /* конец тела потребителя */
    28  /* спецификация задачи-сервера */ 
    29  task SERVER is  
    33     /* описание входных точек сервера */ 
    37     entry GETPORTION(PORT : out PORTION); 
    32     entry PUTPORTION(PORT : in PORTION); 
    33     end; 
    34  /* тело сервера */ 
    35  task body SERVER is  
    36     /* буфер */
    37     BUFFER : array [1..BSIZE] of PORTION; 
    38     /* индексы для чтения и записи */ 
    39     INCNT, OUTCNT : INTEGER range 1..BSIZE := 1; 
    40     /* счетчик порций в буфере */ 
    41     PORTCNT : INTEGER range 0..BSIZE := 0; 
    42     begin 
    43        loop  /* цикл обслуживания */ 
    44           /* выбор из наступивших событий */ 
    45           select when PORTCNT < BSIZE => 
    46           /* если буфер не полон, обслуживается запись */ 
    47              accept PUTPORTION(PORT:in PORTION) do
    48                 BUFFER[INCNT] := PORT; /* запись */ 
    49                 end; 
    50              /* модификация счетчиков */ 
    51              INCNT := INCNT mod BSIZE + 1; 
    52              PORTCNT := PORTCNT + 1; 
    53           or 
    54           /* или если буфер не пуст, обслуживается выборка */ 
    55              accept GETPORTION(PORT:out PORTION) do
    56                 PORT := BUFFER[OUTCNT]; /* выборка */ 
    57                 end; 
    58              /* модификация счетчиков */ 
    59              OUTCNT := OUTCNT mod BSIZE + 1; 
    60              PORTCNT := PORTCNT - 1; 
    61           end select;  /* конец выбора */ 
    62           end loop; /* конец цикла обслуживания */ 
    63     end SERVER; /* конец тела сервера */ 
    64  /* главная процедура */ 
    65  begin 
    66     /* запуск всех задач */ 
    67     initiate SERVER, PRODUCER, CONSUMER; 
    68     end. 

В нашу программу входят:

Главная процедура запускает три другие задачи оператором initiate (строка 67) и переходит в ожидание. Она завершится, когда завершатся все запущенные ею задачи. Задачи PRODUCER и CONSUMER не имеют операторов приема, поэтому их спецификации (строки 2 - 4 и 15 - 17) вырожденные - пустые. Тела этих задач содержат простые бесконечные циклы (loop), в которых выполняется подготовка или обработка порции и обращение к соответствующей входной точке сервера. Задача SERVER является аналогом монитора. В ее спецификации (строки 28 - 33) описаны две входные точки: GETPORTION и PUTPORTION. Сам буфер является локальным в теле сервера (строка 37), также локальны и индексы чтения и записи (строки 39, 40) и счетчик порций (строкa 41). Выполнение сервера представляет собой бесконечный цикл (строки 43 - 62), в каждой итерации которого обрабатывается одно обращение. Оператор select (строки 45 - 61) обеспечивает выбор из обращений: GETPORTION или PUTPORTION. В зависимости от значения счетчика PORTCNT из числа альтернатив может исключаться GETPORTION - если буфер пуст или PUTPORTION - если полон. Если к началу очередной итерации обращений нет или есть обращение, которое не позволяет принять защита when, сервер ожидает. Обратите внимание на операторные скобки do ... end, следующие за операторами accept (строки 47 - 49 и 55 - 57). Они ограничивают критическую секцию. Выполнение процесса-передатчика не возобновится до тех пор, пока процесс-приемник не выйдет из критической секции. Мы включили в критические секции приемов только операторы, непосредственно работающие с параметрами вызовов, так как основное предназначение этой секции - защита параметров от преждевременного их изменения. Остальные операторы, выполняемые в ходе обработки вызовов (модификация индексов и счетчика), выполняются уже вне критической секции.

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

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

    1   task SEMAPHORE is 
    2      entry P; 
    3      entry V; 
    4      end; 
    5   task body SEMAPHORE is 
    6      begin 
    7      loop 
    8         accept P; 
    9         accept V; 
    10        end loop; 
    11     end SEMAPHORE; 

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

Асимметричные рандеву являются дальнейшим развитием идеи мониторов. В большинстве ADA-приложений задачи четко разделяются на задачи-клиенты, выдающие вызовы, и задачи-серверы, их принимающие. Но концептуально рандеву являются более универсальным и гибким средством взаимодействия процессов. Обратите внимание на то, что взаимодействующие задачи не используют общих переменных. Это делает язык ADA независимым от конкретной реализации параллельной работы в системе: это может быть однопроцессорная система с разделением времени, мультипроцессорная система с общей памятью или многомашинная система (сеть).

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

Контрольные вопросы

  1. Покажите, что задача синхронизации является частным случаем задачи взаимного исключения.
  2. Для каких задач использование единственной общей переменной исключения может быть оправданным?
  3. Сопоставьте свойства алгоритмов взаимного исключения, использующих атомарность команд и использующих атомарность обращений к памяти.
  4. В состав семафора входит переменная взаимного исключения и скобки критической секции. Почему же потери на занятое ожидание в семафоре не могут быть значительными?
  5. Какие ограничения имеются в решении задачи "производители-потребители" методом семафоров?
  6. В чем преимущества встраивания критической секции в язык программирования? Покажите, как используются скрытые семафоры для реализации встроенной критической секции.
  7. В чем преимущество использования мониторов? Покажите, как используются скрытые семафоры для реализации защищенных процедур.
  8. Проблема вложенных вызовов мониторов может быть решена при помощи иерархической дисциплины, описанной в разделе 5.3. Покажите пути такой реализации.
  9. Почему при применении групповых мониторов процедуры read и write не должны быть защищенными?
  10. Покажите реализацию задачи "читатели-писатели" с исключением возможности бесконечного откладывания процесса-писателя.
  11. В чем преимущества решения задачи "производители-потребители" методами счетчиков событий или секвенсоров перед методом семафоров?
  12. Как, используя семафоры, реализовать счетчики событий и секвенсоры?
  13. В каких ситуациях процесс, участвующий во взаимодействии по модели рандеву, может быть заблокирован?
  14. Объясните реализацию семафора через рандеву.

НазадОглавлениеВперед
Индекс