Can I implement a fair “wait on multiple events” with events, mutexes and semaphores only?

Question

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

[1] An event is a “flag” that has 4 ops: Set (), Clear (), Wait () and WaitAndClear (). If you wait () in an unoccupied event, you block until someone installs it (). WaitAndClear () is what it seems, but atomic. All the waiters woke up.

[2] I do not believe that the system supports semaphore values ​​that are negative.

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

Answer 1

For windows WaitForMultipleObjects with the third parameter set to false should work (also includes a timeout parameter). I also saw a similar wait function implemented for the embedded small kernel used in the X86 embedded device (80186). For the internal kernel, if the maximum number of threads is fixed, then every event, semaphore, ..., can have an array of addresses of the task control block for any threads waiting for a response to this object. Another option is to create a rule according to which only one thread can expect any event, a semaphore, ... (only one record for each type of object, which will contain either zero or the address of the pending control block of the task), and in the case where it is necessary to use multiple threads; multiple events or semaphores can be used.

Answer 2

You need one of the following:

• Non-Blocking Event Tester
• Ready primitive, e.g. WaitForMultipleObjects
• One thread per expected object, as well as some overhead

If you do not have one of them, I do not consider it feasible.