Path: csiph.com!usenet.pasdenom.info!aioe.org!.POSTED!not-for-mail
From: Kaz Kylheku <kaz@kylheku.com>
Newsgroups: comp.programming
Subject: Re: randezvous with semaphore have a deadlock
Date: Tue, 4 Mar 2014 08:35:28 +0000 (UTC)
Organization: Aioe.org NNTP Server
Lines: 112
Message-ID: <20140303232823.685@kylheku.com>
References: <365a702c-a9ed-41a4-9560-d689c72f990f@googlegroups.com>
NNTP-Posting-Host: X+c6YNb3AaWMPA3YfA4opg.user.speranza.aioe.org
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
X-Complaints-To: abuse@aioe.org
User-Agent: slrn/pre1.0.0-18 (Linux)
X-Notice: Filtered by postfilter v. 0.8.2
Xref: csiph.com comp.programming:4127

On 2014-03-03, bertanimauro@gmail.com <bertanimauro@gmail.com> wrote:
> Hi, I have a problem with an implementation of a randezvous with the
> semaphore structures.

There is a problem implementing almost anything with semaphores.

Semaphores are the "goto" of process synchronization.

Which is why it is so amusing that they were proposed by Dijkstra, the
staunch proponent of proving programs correct and opponent of goto.

> What I want to do is: The synchronization requirement is that no thread
> executes critical point until after all threads have executed rendezvous. You
> can assume that there are n threads and that this value is stored in a
> variable, n, that is accessible from all threads. When the first n − 1 threads
> arrive they should block until the nth thread arrives, at which point all the
> threads may proceed.

This is also called a "barrier": a synchronization primitive which waits for N
threads to call a single function, "wait".

A useful further refinement in the barrier (an essential feature, I would say)
is that one of these threads returns from the barrier with a special return
value which tells it it is the "serial thread".  The serial thread can then
perform some action that only one thread should do.

For instance N threads can "map" some data in parallel in one processing
phase, rendezvous at the barrier, and then the serial
thread can "reduce" the the outputs of the prior parallel computations.

> I try this soltion:
> multiplex = new Semaphore(4) //n = 4
> mutex = new Semaphore(1)
>
> multiplex.wait()
> mutex.wait()
> criticalSection()
> mutex.signal()
> multiplex.signal()
> I have instantiace 10 threads and the program reaches deadlock
> before three threads remains in the multiplex

Although this is not a correct approach to implementing barriers, the threads
should be able to pass through this flow without deadlock. Every wait is
balanced by a signal.

Possibly, you might be using some poorly designed semaphore type which
saturates at (does not increment past) a maximum value, thereby 
causing lost wakeups.

You should show your actual source code with the real types that you're using.

The solution you have cannot work because it doesn't exhibit the behavior of
blocking n - 1 threads, and then releasing the whole herd when thread n
arrives.  Semaphores do not do this "out of the box"; you have to
orchestrate the semaphores into a clever "mouse trap".

One idea is to implement the barrier with a "barrier manager" thread.  The
barrier wait operation posts a request to the manager's receive queue and
blocks, waiting for a reply. The manager monitors the queue, and counts the
requests.  When it collects ten requests, then it replies to all of the
messages.

Here is a simpler idea:

  n_waiting = 0
  mutex = Semaphore(0)
  barrier = Semaphore(0)

  wait_op:
    mutex.wait()               // acquire lock
    if (++n_waiting == n)      // am I thread n?  
      n_waiting = 0
      repeat n-1               // yes: wake the other n-1
          barrier.signal()
      mutex.signal()           // give up lock
      return true              // report: "I am the serial thread"
    else                       // I am not thread #n
      mutex.signal()           // give up lock   
      barrier.wait()           // wait for thread #n to signal me
      return false             // report: "I am not the serial thread"

We keep the lock over the barrier.signal() operation, because as soon as we
kick the barrier semaphore, the threads will want to spin around and call
wait_op again. That will interfere with the count.

We can actually allow them to do that, by doing it like this.
This should still work:

  n_waiting = 0
  mutex = Semaphore(0)
  barrier = Semaphore(0)

  wait_op:
    I_am_serial = false

    mutex.wait()
    if (n_waiting == n - 1)
      n_waiting = 0
      i_am_serial = true
    else
      n_waiting++
    mutex.signal()

    if (I_am_serial)
      repeat n - 1   
        barrier.signal()
    else
      barrier.wait()

    return I_am_serial