Sync N processes using semaphore - condition race

Question

I'm trying to order N processes using only semaphores (no mutex).

P1 -> P2 -> P3 -> ... -> Pn

Im dealing with this problem:

if you call:

s = 1;

P1 {
wait(s1)
...
signal(s1)
}

P2 {
wait(s1)
...
signal(s1)
}

How to prevent that it wouldn't start to loop in one proccess? Like the one process that released semaphore wont take it over again? I need all processes to get a turn eventually.

I would also appreciate any suggestions on how to solve this kind of problem (syncing N processes) ONLY using semaphores, without using N semaphores, I read that possible minimum is 3.

Thanks.

Answer 1

Here are some options. Because you are always calling signal immediately followed by wait, the co-routine option is probably the best. You have no parallelisable code, so can not benefit from normal threads. It will also be useful to learn about avoiding the need for synchronisation.

• You can use more than one semaphore. Where each thread, explicitly hands control to the next.

• You can have a Whose-turn-is-next variable. After getting the lock, a thread will check to see if it is its turn, if not it will free the lock. This could result in spinning, doing nothing. So we would have to add another lock. After checking we would wait on another lock has-somethread-finished. This will be freed after a thread has done some work. Now threads don't spin. However every time a thread finishes, every other thread will check to see if it is next.

The solutions so far while directly answering your question, are anti-patterns. You are just making a multi-threaded program, run single threaded, by using semaphores to fully synchronise the threads.

This one is nether a pattern or anti-pattern, just a note

• On Unix a thread will eventually get de-scheduled, if it hogs the processor, and there are other threads ready to run.

Better ways to do it.

• Avoid need for synchronisation:
  (see https://www.youtube.com/watch?v=2yXtZ8x7TXw) If you don't use mutable variables, then concurrency is easy, and there is no need for synchronisation.

• Consider pipes and filters: in this pattern threads can communicate via a pipe (fifo). You can use a minimal locking circular buffer for this (just ensure that you only put immutable data into the buffer). |In Unixes (such as Gnu/Linux), you can use pipes and processes. You can do this all within one program, using fork. Or you can connect several programs together (bash is a good tool for this).

• Consider micro-threads / co-routines / co-operative threads:
  Sometimes it is nice to write a program with several independent threads. But if your threads do not spend a significant amount of time running concurrently (for example because you always call signal; wait), then you do not need threads. And threads produce a significant amount of complexity to the code. Therefore use co-routines (or what ever they are called on your system), they allow you to write several routines to be scheduled independently, but control will only be handed over to another co-routine when yield is called (similar to calling signal; wait, but the mechanism will prefer to hand over to the next co-routine in the ring.