Recipes against deadlocks on signal variables

    Good day, dear Habrausers!

    With this post, I continue a series of articles aimed at fighting for the cleanliness and security of multithreaded programs being developed.

    Figure 1 - Mutual blocking of the 1st kind with the participation of a signal variable.

    As part of this post, we will look at the problems that arise when using signal variables, and show how they can be avoided.

    With your permission, I will skip long introductions, hoping that you are already familiar with the previous post and we equally understand:
    1. What is a deadlock?
    2. How the “transition model" of a multithreaded program is built and how it is read.
    3. How to avoid deadlocks when using mutexes.

    So, a signal variable (or a condition variable) is a synchronization tool that allows one thread to wait for a certain condition to be fulfilled by another thread.

    Extending the multi-threaded program transition model


    When describing a multi-threaded program that operates only on the operations of capturing and releasing mutexes, we only needed the notation - L (lock) and U (unlock). It is time to expand our transition model with new operations:
    • W (wait, wait) - puts the subject (stream) that caused this operation into the standby state of the signal from the corresponding signal variable. For the same signal variable, there can be an unlimited number of pending threads.
    • E (emit, send) - sends a single signal by a signal variable. A signal can receive only one of the streams waiting for it, regardless of the total number of waiting, it does not matter which thread performed the emit operation.
    • B (broadcast) - sends a signal for all streams waiting for a signal on the corresponding signal variable, it does not matter which stream performed the broadcast operation.

    The streams that received the signal awaken and continue their execution further along the chain. If at the moment of sending the signal there is no one waiting stream-consumer, then the signal is simply ignored, while the fact of sending the signal is not remembered. Therefore, if any thread performs an operation W, then it will be put on hold until a new signal is sent.

    We can draw an analogy with the previously considered operations L and U. The operation W has common features with the operation of capturing the mutex L, with the difference that L blocks the execution of the stream only if it tries to re-capture the already captured mutex, and W always blocks the execution of the stream. Operations E and B have common features with the operation of releasing the mutex U. Thus, a signal variable can be represented as a regular mutex, with the exception that the capture operation is performed by one thread and the release by another.

    Note that in practice, a signal variable is often used in conjunction with a mutex (for example, in the libpthread library). When constructing the model, we assume that the mutex, which is inextricably linked with the use of the signal variable, is taken into account in the logic of operations W, E, and B.

    Where is the danger?


    A signal variable can cause a deadlock in one of two cases.

    A signal variable is the cause of a mutual blocking of the first kind if the Kth stream is waiting for a signal to arrive at the Ith signal variable, while the Kth stream captures a certain mutex, which (directly or indirectly) blocks signal sending for the Ith variable condition from other entities (Figure 1).

    A signal variable causes a second-order blocking if the K-th stream is waiting for a signal to arrive on the I-th signal variable, and the streams that can send this signal are waiting for a signal to arrive on the J-th signal variable, which should send K th stream (Figure 2).


    Figure 2 - Mutual blocking of the 2nd kind with the participation of a signal variable.

    Two rules for the safe use of signal variables


    According to the established tradition, we formulate two rules that will allow us to avoid the situations described above.

    Rule 1

    A signal variable cannot cause a deadlock of the second kind if each stream that is a source stream for any signal variable is not a consumer stream for any signal variable.

    We call a consumer stream for a signal variable a stream whose execution chain contains at least one operation W of waiting for a signal for this signal variable.

    Let us call the source stream for a certain condition variable a stream whose execution chain contains at least one operation E or B of sending a signal along this signal variable.

    Rule 2

    Frankly, I had some difficulties formulating the second rule, because in our studies, it included concepts and definitions that I did not introduce in the framework of this post to simplify the presentation. Here's what happened:

    A signal variable cannot cause mutual blocking of the first kind of a multithreaded program that complies with the rules for safe use of mutexes , if for any dynamics of any execution variant of each thread where a signal from a certain signal variable is expected, all mutexes captured by this thread at the time of accessing this signal variable, they are not associated with a “more” order relation with any mutex of at least one thread sending a signal for this signal variable variable.

    This, in essence, means that until our thread “fell asleep” on W's call, it did not capture a single mutex that might be required to send E or B in order to “wake us up”.

    Expansion of scope


    In conclusion, let me draw attention to the fact that you should not perceive a signal variable exclusively as a kind of language primitive, for example, pthread_cond (libpthread library). A signal variable is a functional design that allows you to organize waiting in one thread for some condition to be fulfilled by another thread.

    An important special case of such a functional construction is the call to wait (or join) to wait for the completion of another thread. This expectation is often a member of the deadlock chain, but if you exclude this synchronization primitive from consideration, it is simply impossible to cure such a lock. This must be taken into account when building the transition model of your multi-threaded program!

    Soon "on screen"


    Thanks to the distinguished Habrausers for their interest in our series of posts on multithreaded programming. For me, this is another confirmation of the relevance of the problem and the importance of our research. This gives strength to write more and more articles. In our plans:
    1. Consideration of issues of “dynamic locks” using “soft synchronization tools” (non-blocking attempt to capture a mutex, waiting for a signal on a signal variable with a timeout, etc.).
    2. Consideration of the mathematical foundations and evidence of the theses presented in previous articles.
    3. Consideration of alternative models of multithreaded programs, in addition to the "transition model", for example, automata or Petri nets.

    And much, much more, if it will still be interesting to the audience of Habr. Thank you for your attention and interest! Program safely!

    Also popular now: