Реализация барьера (конструкции синхронизации) с использованием двоичного семафора

Question

Барьер - это конструкция синхронизации, в которой набор процессов синхронизируется глобально, т.е. каждый процесс в наборе достигает барьера и ожидает прибытия всех остальных, а затем все процессы покидают барьер.Пусть число процессов в наборе равно трем, а 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).

Answer 1

Упоминается, что есть 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, все процессы продолжают ждать. Отсюда тупик.

Answer 2

Хм ... ограничено тремя потоками и только двоичными семафорами, я хотел бы попробовать это, используя три семафора, A, B, C. A контролирует доступ к счетчику process_arrived, B и C для первого и второготемы ждать.A устанавливается в 1, B & C - в 0. Поток 1 получает A, поэтому вход 2 и 3 запрещен.Переключение на process_arrived заставляет поток 1 включить inc process_arrived, освободить A и ждать на B. Поток 2 получает A, а переключатель вызывает его на inc 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 равен нулю.