Несколько лет назад у меня был семинар по операционным системам.Мне было поручено создать алгоритм для синхронизации процессов, используя как можно меньше семафоров.Это должно было выглядеть так:
P1 -> P2 -> P3 -> P4 -> P5
P (n) - процесс
Только один процесс выполняется навремя и требовалось строгое упорядочение .
В прошлом году я пришел с решением с использованием 3 семафоров (эффективно создавая барьер).Вот мой алгоритм:
P S1 S1 S1 S1
4W1 W0 W0 W0 W0
4S0 P S2 S2 S2
3W2 W1 W1 W1
3S1 P S1 S1
2W1 W0 W0
2S0 P S2
W2 W1
S1 P
(выполнение сверху вниз, каждая дорожка - один процесс) P - реальная работа, которую необходимо выполнить сериализовано
W (n) - waitn
S (n) - signaln
4W1 означает «do 4 wait1s»
wait1 и signal1 работают с семафором1 и т. Д. *
Объяснение алгоритма:
- Каждая полоса процесса запускается
- первый процесс будет запущен, а другие будут выполнять signal1 ()
- , каждый другой процесс, кроме первого, будет ожидать семафор 0 (делает wait0)
- послеprocess1 ожидает 4 семафора1 и посылает 4 сигнала0, создавая барьер, потому что другие процессы ожидают успешного завершения первого.
Проблема в том, что я не могу понять, как заставить это работать, используя 2 семафора.
PS: это не задание, это проблема, которая лежала в моей головеслишком долго.