operating-systemcomputer-sciencesemaphoresystems-programmingbarrier

Implementing an N process barrier using semaphores


I'm currently training for an OS exam with previous iterations and I came across this:

Implement a "N Process Barrier", that is, making sure that each process out of a group of them waits, at some point in its respective execution, for the other processes to reach their given point.

You have the following ops available:

init(sem,value), wait(sem) and signal(sem)

N is an arbitrary number. I can make it so that it works for a given number of processes, but not for any number.

Any ideas? It's OK to reply with the pseudo-code, this is not an assignment, just personal study.


Solution

  • This is well presented in The Little Book of Semaphores.

    n = the number of threads
    count = 0
    mutex = Semaphore(1)
    barrier = Semaphore(0)
    
    
    mutex.wait()
    count = count + 1
    mutex.signal()
    
    if count == n: barrier.signal() # unblock ONE thread
    
    barrier.wait()
    barrier.signal() # once we are unblocked, it's our duty to unblock the next thread