Can I implement a fair "wait on multiple events" with just events, mutexes, and semaphores?

Question

On a platform that only has events[1], mutexes, and semaphores[2] can I create a fair "wait on multiple events" implementation that returns when any of the events[3] is signaled/set. I'm assuming the existing primitives are fair.

[1] Event is a "flag" that has 4 ops: Set(), Clear(), Wait(), and WaitAndClear(). If you Wait() on an unset event, you block until someone Set()'s it. WaitAndClear() is what it sounds like, but atomic. All waiters are awoken.

[2] I do not believe the system supports semaphores values going negative.

[3] I say "events", but it could be a new object type that uses any of those primitives.

Answer 1

For windows, WaitForMultipleObjects with the third parameter set to false should work (also includes a timeout option). I've also seen a similar wait function implemented for a in house developed small kernel used in an X86 (80186) embedded device. For an in house kernel, if the maximum number of threads is fixed, then each event, semaphore, ..., can have an array of task control block addresses for any threads pending on that object. Another option is to make a rule that only one thread can wait for any event, semaphore, ... , (only one entry for each object type that would contain either null or the address of a pending task control block) and in the case where multiple threads need to be triggered, multiple events or semaphores would be used.

Answer 2

You need one of the following:

• A non-blocking event tester
• A ready made primitive, eg WaitForMultipleObjects
• One thread per waited object, plus some overhead

If you cant have one of those, i don't think its doable.