Блог

Барьер — это конструкция синхронизации, в которой набор процессов синхронизируется глобально, т.Е. Каждый процесс в наборе достигает барьера и ожидает прибытия всех остальных, а затем все процессы покидают барьер. Пусть число процессов в наборе равно трем, а S — двоичный семафор с обычными функциями P и V. Рассмотрим следующую реализацию барьера на языке C с номерами строк, показанными слева.

 void barrier (void) {    
    1: P(S);
    2: process_arrived  ;
    3: V(S);
    4: while (process_arrived !=3);
    5: P(S);
    6: process_left  ;
    7: if (process_left==3) 
       {
         8: process_arrived = 0;
         9: process_left = 0;
    10: }
    11: V(S);
 }
  

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

Сработает ли вышеуказанная реализация? Я думаю, что это может привести к тупику, если два вызова барьера используются в непосредственной последовательности, поскольку первый процесс для входа в барьер не ожидает, пока process_arrived не станет равным нулю, прежде чем приступить к выполнению P (S).

Упоминается, что существует 3 процесса. Пусть это будут P1, P2 и P3. Каждый процесс достигает барьера, то есть завершает свой первый раздел кода. Следовательно, process_arrived = 3. Теперь предположим, что P1 продолжает свое выполнение и покидает барьер и делает process_left=1. Теперь предположим, что P1 снова немедленно вызывает функцию барьера. На этом этапе process_arrived =4. P1 теперь ожидает. Вскоре P2 покидает барьер, что делает process_left=2. Теперь P3 покидает барьер, который делает process_left=3. условие «Если» выполнено, и теперь process_arrived и process_left сбрасываются в 0. Мы знаем, что P1 ожидает. На этом этапе предположим, что P2 вызывает функцию барьера, следовательно, process_arrived=1 и ожидает. P3 вызывает функцию барьера, следовательно process_arrived=2. Все процессы достигли барьера, но поскольку process_arrived=2, все процессы продолжают ждать. Отсюда взаимоблокировка.

Хм … ограниченный тремя потоками и только двоичными семафорами, я бы испытал соблазн попробовать это, используя три семафора, A, B, C. A управляет доступом к счетчику process_arrived, B и C предназначены для ожидания первого и второго потоков. A инициализируется как 1, B amp; C — как 0. Поток 1 получает A, таким образом предотвращая ввод 2 и 3. Включение process_arrived приводит к тому, что поток 1 включает process_arrived, выпускает A и ожидает B. Поток 2 получает A, и переключатель заставляет его включать process_arrived, переключаться и, таким образом, отпускать A и ждать C. Поток 3 получает A, и переключатель заставляет его сигнализировать B, сигнализировать C, устанавливать process_arrived в 0, сигнализировать A и продолжать.

Потоки 1 и 2 не могут передавать B и C, пока 3 не подаст им сигнал. Когда B / C сигнализируется 3, 1/2 может выполняться, но не может выполнить обратный цикл и войти в барьер, пока 3 не освободит A, и в этот момент барьер находится в правильном состоянии, чтобы снова действовать как барьер — A имеет значение 1, B и C равны нулю, а process_arrived равен нулю.