WaitForMultipleObjects on top of PThreads?



  • Is it possible to realise analog of WinAPI function WaitForMultipleObjects using PThreads functions?

    For example, can I make waiting for multiple condition variables without risk of deadlock?



  • If you want to wait for all objects to finish/emit a signal, you can call pthread_join (wait for a thread to finish) or pthread_cond_wait (wait for a conditional variable to emit a signal) multiple times (one call for each object). I think there shouldn't be a problem with deadlocks.
    If you want to wait for one object of many to finish/emit a signal, I think the only way to do this with pthread is to poll for a thread termination or signal emition in an infinite loop (but this would increase CPU usage).
    Another way would be to implement threads yourself with clone () and pipes (but this would be a bit more complex).



  • devkid schrieb:

    If you want to wait for all objects to finish/emit a signal, you can call [...] pthread_cond_wait (wait for a conditional variable to emit a signal) multiple times (one call for each object). I think there shouldn't be a problem with deadlocks.

    It can be deadlock. Consider, for example, the Dinning Philosophers problem: each philosopher needs two forks to eat. This is WaitForMultipleObjects. But if he will take (wait) forks one-by-one, then there is a risk that all philosophers acquire only left forks or only right ones.

    The beauty of WaitForMultipleObjects (when waiting for all objects) is that it is not equal to waiting these objects one-by-one. It atomically acquire all the needed resources and wake up the thread only when they all become free at one moment of time.



  • Hm... My fault, of course multiple pthread_cond_wait () calls would block... But I think pthread hasn't got any other mechanisms to do so. Would working with pipes be an alternative for you? You could create one pipe as a "conditional variable" for each thread and (in the waiting thread) put all these pipes into a FD_SET and call select () on it.



  • My students often ask me «How does the WaitForMultipleObjects works?»

    So, I decide to make the reference realisation of it on top of the PThreads primitives.

    I thinked up the following algorithm (using mutexes, for example):

    1. Obtain list of mutexes to acquire: M1,...,Mn;
    2. Acquire first mutex (pthread_mutex_lock);
    3. Try to acquire (pthread_mutex_trylock) other mutexes one-by-one;
    4. If we acqured all mutexes, then function retuns;
    5. If some of the mutexes is busy, then
        a) Release all acquired objects
        b) Move the mutex that was busy to the first place of the list (shifting others right)
        c) Go to step number 2)

    So, this function never holds any resource while waiting, cause no deadlock by itself (it still can be deadlock in the upper-level user algorithm). The mutex which is the most probably busy is at the beginning of the list, so, the function will not "spin" trying to acquire mutexes: it will sleep most of the waiting time.

    The problem is that this algorithm can miss the moment when all of the mutexes were free. The WinAPI function will never miss such moments.

    This caused by the fact that when function awake from first mutex, it is time lag between the first and the last mutex it acquires.

    I thinked about it, and concluded, that to prevent this situation, we need to enclose work with all of the mutexes in the set in one "big" mutex M. So, if in any place of the program we want to acquire some of the mutexes M1,...,Mn, we first need to acquire M, then acquire Mi, than release M (to let other threads acquire other mutexes of the set).

    The problem is that when waiting, WaitForMultipleObjects will hold M, giving no chance for other threads to acquire any of M1,...,Mn (they can only be released).

    If we decided not to hold M while waiting for M1, then we need to acquire M1 and M atomically, coming to the same problem: WaitForMultipleObjects require WaitForMultipleObjects to work 😞

    Another problem is is that we can have intersecting sets of mutexes in different calls to WaitForMultipleObjects. For example: (m1,m2,m3) and (m3,m4,m5)

    So, I wonder if the calssic alghorithm for WaitForMultipleObjects exists?


Log in to reply