Waiting on multiple semaphores without busy-waitin

Question

If I have more than one semaphore, how can I have a process block until at least one of the semaphores is free? I know I can do this with a busy-wait loop such as:

// blocks until one of the semaphores in sems is free, returns
// index of semaphore that was available
int multiple_sem_wait(sem_t **sems, int num_sems) {
   while (true) {
      for (int i = 0; i < num_sems; ++i) {
         if (sem_trywait(sems[i]) == 0) {
            return i;
         }
      }
   }
}

But is there a way to do this without a busy-loop? Perhaps there's some IPC technique other than semaphores that I should be using?

Thanks

Answer 1

Here (developers.sun.com, via the Internet Archive) is a short paper from Sun about how they implemented their WaitForMultipleObjects emulation in Solaris. The basic idea is to associate a list of condition variables to a handle (protected by a mutex), and signal all of the condition variables whenever the handle is signaled. Each time you call the emulated WaitForMultipleObjects, a new condition variable is created and added to the list of all handles you are interested in. In the WaitForMultipleObjects emulation, you block on the condition variable, and check each of your handles when you wake up.

The reason why there is a list of condition variables (and not a single one) is that you may have two threads blocking on handles: thread 1 is blocked on A and B, and thread 2 is blocked on A and C. Signaling B should not wake up thread 2. Since each call to WaitForMultipleObjects create a new condition variable, in this scenario, B and C will have one distinct condition variable each, and A will have both condition variables.

For more detailed info, you will need to read the article itself.

Answer 2

Use multiple separate waiter threads, as in:

• Each thread waits on a separate semaphore.
• Upon successfully waiting on the semaphore, any given waiter thread signals (via another semaphore, condition variable, or whatever primitive is most convenient) the thread that wants to "wait on multiple semaphores".