How do three semaphores work in a synchronised execution of three threads?

Question

In a certain system, the execution of three threads is synchronised using three semaphores, S1, S2 and S3, as shown below. Semaphores S1 and S2 are initialised to zero, while semaphore S3 is initialised to 1. All three semaphores are used only in the sections of code shown below.

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)

... ... ...

If the variable x is defined as an integer shared variable, initialised to 1, and is not assigned a value in any other sections of the code apart from those shown above, what will be its value when all threads have finished executing? What will be the values in the three semaphores?

I am trying to solve this past paper in order to prepare for my Operating System exam. I don't get how the variable x is modified and how the three semaphores work together. If someone could show me step by step how semaphores work together and how the variable gets modified, I would be grateful.

If you have got any other similar example to practice with, don't hesitate to link it.

Answer 1

Let's walk through this process.

Please read the Wikipedia Article: Semaphore programming: Semantics and implementation section before starting. It will explain what the P() and V() operators do.

Initial: S1=0, S2=0, S3=1

1. Thread A decrements S1 and Thread B decrement S2. S1=-1, S2=-1. Because these values are negative, both of these threads block.

   Status: S1=-1, S2=-1, S3=0, Thread A blocking on S1 (instruction 1), Thread B blocking on S2 (instruction 1), Thread C not blocking (instruction 1), x = 1

2. Thread C decrements S3 which is now 0. Because this is not negative, this thread doesn't block. Thread C now increments S1. Thread 1, blocking on S1, immediately unblocks and re-decrements S1, causing it to block again.

   Status: S1=-1, S2=-1, S3=0, Thread A blocking on S1 (instruction 2), Thread B blocking on S2 (instruction 1), Thread C not blocking (instruction 3), x = 1

3. Thread C executes x=x*5, which changes x from 1 to 5. Thread C then increments S1. Thread 1, blocking on S1, immediately unblocks. Thread C then increments S3 again and ends.

   Status: S1=0, S2=-1, S3=1, Thread A not blocking (instruction 3), Thread B blocking on S2 (instruction 1), Thread C complete, x = 5

4. Thread A executes x=3*x+4, which changes x from 5 to 19. Thread A then increments S2. Thread B, blocking on S2, immediately unblocks. Thread A then increments S1 again and ends.

   Status: S1=1, S2=0, S3=1, Thread A complete, Thread B not blocking (instruction 2), Thread C complete, x = 19

5. Thread B decrements S1, which is now zero. Because this is not negative, it continues and executes x=x+7, which changes x from 19 to 26. Thread B then increments S2, then increments S1 and ends.

   Final Status: S1=1, S2=1, S3=1

Now let's doublecheck our results by counting the P() and V() calls for each semaphore and make sure we didn't miss anything. Since there was no looping, we can easily do this since each instruction in all three threads was executed exactly once.

• S1 has an initial value of 0. Three P(S1) calls decremented that to -3. Four V(S1) calls incremented that to 1. Our results show a final S1 = 1. CHECK
• S2 has an initial value of 0. One P(S2) call decremented that value to -1. Two V(S2) calls incremented that to 1. Our results show a final S2 = 1. CHECK
• S3 has an initial value of 1. One P(S3) call decremented that value to 0. One V(S3) call incremented that to 1. Our results show a final S3 = 1. CHECK

Good luck on your exam!