27

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.

Community
  • 1
  • 1
F. P.
  • 5,018
  • 10
  • 55
  • 80

4 Answers4

48

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
cnicutar
  • 178,505
  • 25
  • 365
  • 392
  • Thanks! I thought of something VERY close. – F. P. Jun 13 '11 at 15:24
  • 1
    Would it be better to put the `if count...` in the mutex block to make sure it's only entered once? The way it stands now it looks like you could potentially enter it twice. – Jean-Bernard Pellerin Oct 19 '11 at 00:08
  • 1
    nvm - looked at the little book and it's ok for it to be signaled twice since this barrier is not being reused so it's final state doesn't matter as long as it accomplished it's goal. – Jean-Bernard Pellerin Oct 19 '11 at 00:15
  • if you would want to reuse it, you would have to aquire your mutex again right after the last barrier.signal() and decrement the count variable. don't forget to unlock the mutex after that. but why isn't it necessary to hold the mutex while the if performs a check on count? – Hafnernuss May 08 '15 at 08:00
  • 3
    to provide an example: let's say, thread 5 aquires the mutex, increments count and releases the mutex. Now the scheduler switches in another thread, which again aquires the mutex, increments count and releases the mutex. count is now 6, and the barrier will never signal it's thread. – Hafnernuss May 08 '15 at 08:04
  • 2
    Upvoted for the reference to the Little Book of Semaphores. It's great! Thanks! – rocarvaj May 09 '16 at 19:01
2

Using N semaphores. Not very sure...

semaphore barr[N]
semaphore excl=1
int count=0

int i=1
while (i<=N)
   barr[i]=0 #initialization
   i=i+1

# use, each thread (tid)
wait(excl)
count=count+1
if (count==N)
   int j=1
   while (j<=N)
       signal(barr[j])
       j=j+1
   count=0
signal(excl)
wait(barr[tid])
Sergio.Uma
  • 52
  • 5
0

Only 2 barrier semaphores, but not sure...

semaphore barr[0..1] # two semaphores: barr[0] and barr[1]
semaphore excl=1
int count=0
int whichOne=0 # select semaphore to avoid race conditions

barr[0]=0 #initialization
barr[1]=0

# sample use
int current   #local for each thread
wait(excl)
current=whichOne
count=count+1
if (count==N)
   int j=1
   while (j<=N)
       signal(barr[current])
       j=j+1
   count=0
   whichOne=1-whichOne # swap barrier to avoid race conditions
signal(excl)
wait(barr[current])
Sergio.Uma
  • 52
  • 5
0

I think this should also work, using only one semaphore (at least if the barrier is not required to be reusable)?

n = number of threads
barrier = Semaphore(1 - n)

barrier.signal()
barrier.wait()
barrier.signal()
user19668187
  • 1
  • 1