strict N process synchronization using 2 semaphore

问题:

a few years ago I had an Operating Systems seminar. I had been tasked to create an algorithm for process synchronization using as few semaphores as possible. It should have looked like this:

P1 -> P2 -> P3 -> P4 -> P5

P(n) - process

Only one process running at a time and strict ordering was needed.

Last year I came with solution using 3 semaphores (effectively creating a barrier). Here is my algorithm:

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

(execution is from top to bottom, each lane is a single process) P - real work which needs to be done serialized
W(n) - waitn
S(n) - signaln
4W1 means "do 4 wait1s"
wait1 and signal1 operates with semaphore1 and so on...

Explanation of algorithm:

1. Every process lane starts
2. first process will run and others will do signal1()
3. every other process except the first one will wait for semaphore0 (doing wait0)
4. after process1 waits for 4 semaphores1 it sends 4 signals0, creating a barrier because other processes waits for first one to successfully complete.

The problem is I can't figure out how to make it work using 2 semaphores.

PS: this is not an assignment, it's a problem that's been lying in my head for too long.

回答1:

It can't be done using 2 semaphores. 3 is minimum.