3

Recently I see this problem which is pretty similar to First reader/writer problem.

Implementing an N process barrier using semaphores

I am trying to modify it to made sure that it can be reuse and work correctly.

n = the number of threads
count = 0
mutex = Semaphore(1)
barrier = Semaphore(0)


mutex.wait()
count = count + 1
if (count == n){ barrier.signal()}
mutex.signal()

barrier.wait()

mutex.wait()
count=count-1
barrier.signal()
if(count==0){ barrier.wait()}
mutex.signal()

Is this correct?

I'm wondering if there exist some mistakes I didn't detect.

Community
  • 1
  • 1
王智寬
  • 415
  • 1
  • 5
  • 17

1 Answers1

1

Your pseudocode correctly returns barrier back to initial state. Insignificant suggestion: replace 

barrier.signal()
if(count==0){ barrier.wait()}

with IMHO more readable

if(count!=0){ barrier.signal()} //if anyone left pending barrier, release it

However, there may be pitfalls in the way, barrier is reused. Described barrier has two states:

  1. Stop each thread until all of them are pending.
  2. Resume each thread until all of them are running

There is no protection against mixing them: some threads are being resumed, while other have already hit the first stage again. For example, you have bunch of threads, which do some stuff and then sync up on barrier. Each thread body would be:

while (!exit_condition) {
  do_some_stuff();
  pend_barrier(); // implementation from current question
}

Programmer expects, that number of calls for do_some_stuff() will be the same for all threads. What may (or may not) happen depending on timing: the first thread released from barrier finishes do_some_stuff() calculations before all threads have left the barrier, so it reentered pending for the second time. As a result he will be released along with other threads in the current barrier release iteration and will have (at least) one more call to do_some_stuff().

nnovich-OK
  • 2,900
  • 2
  • 13
  • 16
  • Thank you very much!Then what if I use another semaphore "size=semaphore(n)" and size.wait(), to control the entry .And use "if(count==0){for(i=1~n){size.signal()}" to refresh it. Is that right? – 王智寬 Jan 19 '17 at 16:10