Как работают три семафора в синхронизированном выполнении трех потоков?

Question

В определенной системе выполнение трех потоков синхронизируется с использованием трех семафоров S1, S2 и S3, как показано ниже. Семафоры S1 и S2 инициализируются до нуля, а семафор S3 инициализируется равным 1. Все три семафора используются только в разделах кода, показанных ниже.

Thread A Thread B Thread C 
...  ...  ... 
P(S1)  P(S2)  P(S3) 
P(S1)  P(S1)  V(S1) 
x=3*x+4 x=x+7  x=x*5 
V(S2)  V(S2)  V(S1) 
V(S1)  V(S1)  V(S3) 

... ... ...

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

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

Если у вас есть какой-либо другой подобный пример для практики, не стесняйтесь связывать его.

Answer 1

Давайте рассмотрим этот процесс.

Перед началом работы прочитайте раздел Wikipedia Article: Semaphore programming: Semantics and implementation. Он объяснит, что делают операторы P() и V().

Начальное: S1 = 0, S2 = 0, S3 = 1

1. Поток А декрементирует S1 и резьба B декремента S2. S1 = -1, S2 = -1. Поскольку эти значения отрицательные, оба этих потока блокируются.

   Статус: S1 = -1, S2 = -1, S3 = 0, поток A блокируется на S1 (инструкция 1), блокировка потока B на S2 (инструкция 1), поток C не блокируется (инструкция 1) x = 1

2. Резьба C уменьшается S3, которая теперь равна 0. Поскольку это не отрицательно, этот поток не блокируется. Поток C теперь увеличивает S1. Thread 1, блокирующий S1, немедленно разблокирует и повторно уменьшает S1, заставляя его блокировать снова.

   Статус: S1 = -1, S2 = -1, S3 = 0, поток A блокируется на S1 (инструкция 2), блокировка потока B на S2 (инструкция 1), поток C не блокируется (инструкция 3) x = 1

3. Резьба C выполняет x=x*5, который изменяет x от 1 до 5. Резьба C затем увеличивает S1. Тема 1, блокирующая S1, сразу разблокируется. Затем поток C снова увеличивает S3 и заканчивается.

   Статус: S1 = 0, S2 = -1, S3 = 1, Нитки не блокирует (инструкция 3), тема B блокировки на S2 (инструкция 1), резьба C завершена, х = 5

4. Резьба A выполняет x=3*x+4, которая меняет x от 5 до 19. Затем поток A увеличивает S2. Thread B, блокирующий S2, немедленно разблокируется.Затем поток A снова увеличивает S1 и заканчивается.

   Статус: S1 = 1, S2 = 0, S3 = 1, Резьба полные, резьба В не блокирующих (инструкциях 2), резьба C полном, х = 19

5. резьба B декрементирует S1, который теперь равен нулю. Поскольку это не является отрицательным, он продолжается и выполняет x=x+7, который меняет x с 19 на 26. Затем поток B увеличивает S2, затем увеличивает S1 и заканчивается.

   Final Статус: S1 = 1, S2 = 1, S3 = 1

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

• S1 имеет начальное значение 0. Три вызова P (S1) уменьшают это до -3. Четыре V (S1) вызова увеличиваются до 1. Наши результаты показывают окончательный S1 = 1. CHECK
• S2 имеет начальное значение 0. Один вызов P (S2) уменьшил это значение до -1. Два V (S2) вызова увеличиваются до 1. Наши результаты показывают окончательный S2 = 1. CHECK
• S3 имеет начальное значение 1. Один вызов P (S3) уменьшил это значение до 0. Один V (S3)) вызова увеличивается, что 1. Наши результаты показывают, окончательный S3 = 1. ПРОВЕРКА

удачи на экзамене!