Recipes against deadlocks on signal variables
Good day, dear Habrayuzer!
With this post I continue a series of articles aimed at fighting for the purity and safety of the developed multi-threaded programs.
Figure 1 - Interlocking 1st kind with the participation of the signal variable.
As part of this post, we will look at the problems that arise when using signal variables, and show how to avoid them.
')
With your permission, I will miss the long introductions, hoping that you are already familiar with the previous post and we equally understand:
So, the signal variable (or condition variable, the English condition condition) is a synchronization tool that ensures that one thread can wait for a certain condition to be met by another thread.
When describing a multithreaded program that operates only with 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:
The streams that receive the signal wake up and continue their execution further along the chain. If at the moment of sending the signal there is no waiting consumer stream, then the signal is simply ignored, and the fact that the signal was sent is not remembered. Therefore, if any thread performs the operation W, then it will be transferred to the waiting state until a new signal is sent.
It is possible to draw an analogy with the previously considered operations L and U. Operation W has common features with the operation of capturing mutex L, except that L blocks the flow only in case of an attempt to re-capture the already captured mutex, and W blocks the flow always. Operations E and B have common features with the release operation of the mutex U. Thus, the signal variable can be represented as a normal mutex, except that the capture operation is performed by one thread and the release by another.
Note that in practice, the signal variable is often used in conjunction with a mutex (for example, in the libpthread library). When building a model, we will assume that the mutex, which is inextricably linked with the use of the signal variable, is taken into account in the logic of the execution of operations W, E and B.
A signaling variable can cause a deadlock in one of two cases.
The signaling variable causes the occurrence of interlocking of the 1st kind if the Kth thread waits for a signal on the Ith signaling variable, while the Kth thread has captured a mutex, which (directly or indirectly) blocks sending the signal for the Ith variable condition on the part of other subjects (Figure 1).
A signal variable causes a 2nd kind of interlock to occur if the K-th stream waits for a signal at the I-th signal variable, and streams that can send this signal wait for a signal at the J-th signal variable that K should send th stream (Figure 2).
Figure 2 - Interlocking of the 2nd kind with the participation of a signal variable.
According to the already established tradition, we formulate two rules that will avoid the situations described above.
A signal variable cannot cause a 2nd kind of interlock to occur 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 flow for some signal variable a flow in the execution chain of which there is at least one operation W waiting for a signal for this signal variable.
Let us call a source stream for some condition variable a stream in the execution chain of which there is at least one operation E or B sending a signal on this signal variable.
Frankly, I had some difficulty in formulating the second rule, because In our studies, it contained concepts and definitions that I did not introduce for the sake of simplicity in this post. Here's what happened:
The signal variable cannot cause a mutual blocking of the 1st kind of multi-threaded program that complies with the rules of safe use of mutexes , if with any dynamics of any execution variant of each thread where a signal from a certain signal variable is expected, all the mtexts captured by this thread by the time of access to this signal variable is not related by the order of "more" with any mutex at least one stream that sends the signal for this signal variable.
This, in essence, means that until the moment our thread “fell asleep” on the W call, it did not capture any mutexes that may be required to send E or B to “wake up”.
In conclusion, let me draw your attention to the fact that it is not necessary to perceive a signal variable solely as a kind of language primitive, for example, pthread_cond (the libpthread library). A signal variable is a functional design that allows you to organize the waiting in one thread for the fulfillment of a condition by another thread.
An important special case of such a functional structure is to call wait (or join) to wait for the completion of another thread. This wait is often a member of the mutual blocking chain, but if this synchronization primitive is excluded 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!
Thanks to the respected Habrayusers for their interest in our series of posts about multi-threaded programming. For me, this is another confirmation of the relevance of the problem and the importance of our research. It gives strength to write all new and new articles. In our plans:
And much more, if it will still be interesting for Habr's audience. Thank you for your attention and interest! Program safely!
With this post I continue a series of articles aimed at fighting for the purity and safety of the developed multi-threaded programs.
Figure 1 - Interlocking 1st kind with the participation of the signal variable.
As part of this post, we will look at the problems that arise when using signal variables, and show how to avoid them.
')
With your permission, I will miss the long introductions, hoping that you are already familiar with the previous post and we equally understand:
- What is interlocking.
- How is the “transition model” of a multi-threaded program constructed and read?
- How to avoid deadlocks when using mutexes.
So, the signal variable (or condition variable, the English condition condition) is a synchronization tool that ensures that one thread can wait for a certain condition to be met by another thread.
Extension of the multithreaded program transition model
When describing a multithreaded program that operates only with 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, waiting) - puts the subject (stream) that caused this operation into the state of waiting for a signal from the corresponding signal variable. For the same signal variable, there may be an unlimited number of pending flows.
- E (emit, send) - sends a single signal on the signal variable. A signal can only be received by one of the threads waiting for it, regardless of the total number of waiting, it does not matter which thread performed the emit operation.
- B (broadcast, broadcast) - sends a signal to all streams waiting for a signal on the corresponding signal variable, and it does not matter which stream performed the broadcast operation.
The streams that receive the signal wake up and continue their execution further along the chain. If at the moment of sending the signal there is no waiting consumer stream, then the signal is simply ignored, and the fact that the signal was sent is not remembered. Therefore, if any thread performs the operation W, then it will be transferred to the waiting state until a new signal is sent.
It is possible to draw an analogy with the previously considered operations L and U. Operation W has common features with the operation of capturing mutex L, except that L blocks the flow only in case of an attempt to re-capture the already captured mutex, and W blocks the flow always. Operations E and B have common features with the release operation of the mutex U. Thus, the signal variable can be represented as a normal mutex, except that the capture operation is performed by one thread and the release by another.
Note that in practice, the signal variable is often used in conjunction with a mutex (for example, in the libpthread library). When building a model, we will assume that the mutex, which is inextricably linked with the use of the signal variable, is taken into account in the logic of the execution of operations W, E and B.
Where is the danger?
A signaling variable can cause a deadlock in one of two cases.
The signaling variable causes the occurrence of interlocking of the 1st kind if the Kth thread waits for a signal on the Ith signaling variable, while the Kth thread has captured a mutex, which (directly or indirectly) blocks sending the signal for the Ith variable condition on the part of other subjects (Figure 1).
A signal variable causes a 2nd kind of interlock to occur if the K-th stream waits for a signal at the I-th signal variable, and streams that can send this signal wait for a signal at the J-th signal variable that K should send th stream (Figure 2).
Figure 2 - Interlocking of the 2nd kind with the participation of a signal variable.
Two rules for safe use of signal variables
According to the already established tradition, we formulate two rules that will avoid the situations described above.
Rule 1
A signal variable cannot cause a 2nd kind of interlock to occur 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 flow for some signal variable a flow in the execution chain of which there is at least one operation W waiting for a signal for this signal variable.
Let us call a source stream for some condition variable a stream in the execution chain of which there is at least one operation E or B sending a signal on this signal variable.
Rule 2
Frankly, I had some difficulty in formulating the second rule, because In our studies, it contained concepts and definitions that I did not introduce for the sake of simplicity in this post. Here's what happened:
The signal variable cannot cause a mutual blocking of the 1st kind of multi-threaded program that complies with the rules of safe use of mutexes , if with any dynamics of any execution variant of each thread where a signal from a certain signal variable is expected, all the mtexts captured by this thread by the time of access to this signal variable is not related by the order of "more" with any mutex at least one stream that sends the signal for this signal variable.
This, in essence, means that until the moment our thread “fell asleep” on the W call, it did not capture any mutexes that may be required to send E or B to “wake up”.
Expansion of a scope
In conclusion, let me draw your attention to the fact that it is not necessary to perceive a signal variable solely as a kind of language primitive, for example, pthread_cond (the libpthread library). A signal variable is a functional design that allows you to organize the waiting in one thread for the fulfillment of a condition by another thread.
An important special case of such a functional structure is to call wait (or join) to wait for the completion of another thread. This wait is often a member of the mutual blocking chain, but if this synchronization primitive is excluded 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 the screen"
Thanks to the respected Habrayusers for their interest in our series of posts about multi-threaded programming. For me, this is another confirmation of the relevance of the problem and the importance of our research. It gives strength to write all new and new articles. In our plans:
- 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 timeout, etc.).
- Consideration of mathematical foundations and evidence of theses presented in previous articles.
- Consideration of alternative models of multi-threaded programs, in addition to the "transition model", for example, automata or Petri nets.
And much more, if it will still be interesting for Habr's audience. Thank you for your attention and interest! Program safely!
Source: https://habr.com/ru/post/178623/
All Articles