Overview of synchronization primitives - mutex and cond
Synchronization is needed in any program. (Unless, of course, it consists of 100% of lokless algorithms, which is unlikely). Be it an application or a kernel component of a modern operating system.
All of the below, of course, concerns me more from the point of view of developing an OS kernel. But almost everything applies to custom code.
By the way, the kernels of the old OS did not need synchronization primitives, since there was no preamptive multitasking inside the kernel in the good old days. (Already for the 7th version of Unix, I answer. Not.) More precisely, the only method of synchronization was the prohibition of interruptions. But more about that later.
')
First, we list the characters. I know the following synchronization primitives:
User / kernel mode: mutex + cond, sema, enter / leave critical section.
Kernel only: spinlock, interrupt control.
Why all this is needed, the reader probably knows, but still we will clarify.
If a certain data structure can be accessed by two parallel threads (or threads and interrupts), and is an entity that cannot be accessed atomic access, then work with such a structure should be done so that only one thread simultaneously performs complex manipulations with the state of the structure. .
A simple example. List.
Insert item into the list.
Everything is primitive. But if this code is executed by two threads in parallel, then instead of a coherent list, there will be an explosion at the macaroni factory. For example, if the second thread starts at the moment when the first thread has finished line 3, then bypassing the list from left to right we will meet one object in the same place, and another object from right to left.
Unpleasant
Apply the mutex - mutually exclusive lock. This lock prohibits the parallel execution of code locked by it - if one thread starts to execute it, the second one will wait at the entrance until the first one is finished.
Now good. (Well, it’s not very good if we have more than a hundred processors and they have a lot of code, but this is a completely separate conversation.)
What's happening? Thread A makes a mutex_lock call for the list-> mutex mutex. Which, obviously, belongs to the list that we want to change, and protects access to it. It is not locked, thread A locks the mutex (now it knows that it is locked, and knows who locked it) and continues to work. If now thread B tries to enter the same region of the code (or another one protected by the same mutex - for example, in the function of deleting a list item), then it will not work to lock the locked mutex a second time. Thread B will wait for thread A to trigger mutex_unlock.
By the way, if you and I are nuclear developers, then it is important to understand one more uninteresting feature for an application programmer is the mutex (as well as all the "heavy" synchronization primitives) - if we try to lock a mutex that is already locked with another thread, we are not just waiting - our thread will be "removed from the processor", a context switch will occur. This is valuable because it allows you to load the processor much more efficiently, but there are also problems. Inside an interrupt handler, for example, such primitives cannot be used at all, because context switching inside an interrupt is prohibited and threatens to cause a fair amount of disruption to the operation of the system. But, probably, it will be necessary to write about it separately.
This completely solves the problem if you need to work with a complex data structure. But there are other tasks. For example, inform another thread about the event that that other thread is waiting for.
Consider the functions alloc_mem and free_mem:
What's going on here? Everything is trite. In the memory allocation function, we look at the global free memory count. If it is empty, there is no free memory, we wait until someone releases the memory - we call wait_cond, which suspends us, until someone signals it - ready, the memory is released.
This, of course, the free_mem () function - it returns memory to the heap, increases the free memory counter and calls signal_cond - informs the suffering ones that there is memory. The one who slept inside wait_cond will “wake up” after such a signal, check that yes, there is memory, and allocate it. All right
Well, no, of course. If the alloc_mem function is called by two threads at once, then there will be trouble - one of them will receive the signal first, will wake up, make sure that there is free memory, and then suddenly take the scheduler and remove it from the processor. And let me wake up the second such thread. The second thread will wake up, also see that there is a memory, will take it and end it. Themafia wakes up the first thread, and everything is bad with it. She just checked the free_mem variable, made sure that everything is there, and now - there is no free memory in the pool. Trouble
For this case, the trouble is not fatal - you can simply return to the beginning of the function and again wait for the weather by the sea. Although, of course, this is bad - we lose processor time for empty throwing.
But, it seems, we know the answer? Add mutex!
So good? Not. Memory release will not happen - the alloc_mem () function locked it, fell asleep while waiting for cond, and no one else can enter the mutex, and no one will release the memory, and it will not beep.
Trouble But okay, we know what to do! Before we fall asleep while waiting for the cond, we will heat the mutex, and let others enter free and return our memory. Like this:
In the commentary, you already see that again, not thanks to God. Now what? And now there is a slit, a thin line between the moment when we woke up and left the wait_cond function, receiving a free memory signal from free_mem, and capturing a mutex. At this point, the mutex is not taken, and other threads can again get ahead of us and re-create. It is for this reason that the wait_cond function looks a little different:
It works like this: the function takes a conditional variable as input, which will give us a wake-up signal and a locked mutex:
The wait_cond function will unlock the mutex, firstly, independently, and secondly, it will do it atomically with respect to the transition to the sleeping state. That is, the thread entering wait_cond will first fall asleep, and then, without interrupting sleep, will unlock the mutex. Conversely, waking up, she first captures the mutex, and then wakes up and continues to work. (This requires the thread switch code to be a good deal of trick, I will try to tell about it in one of the following notes.)
Only such semantics provides 100% consistency and the absence of "race" - race conditions.
Note that the free function code is completely correct:
Only taking into account the above, it should be understood that although we formally awaken the allocator on line 4, it will actually wake up after the execution of line 5, because until this point it is not able to capture the mutex.
Probably, it makes sense to add to the above that the real signal_cond function does not awaken all the waiting threads, but only one (usually with the highest priority), so the situation in the given example is somewhat simpler and more complicated at the same time. It’s simpler because a mechanism is already built inside the alarm, which after one free will only wake up one alloc, and more complicated because it really doesn’t solve anything - we don’t know if the given section is suitable for the freed section, so you need to use broadcast_cond instead of signal_cond, which will awaken all the suffering, giving them the opportunity in a fair fight to decide who will get the resource.
Look at the actual implementation of these primitives here:
mutex.c , cond.c
In the next series - sema semaphore, which alone replaces both mutex and cond. Virtually without ensemble.
This is a series of articles "Overview of synchronization primitives":
All of the below, of course, concerns me more from the point of view of developing an OS kernel. But almost everything applies to custom code.
By the way, the kernels of the old OS did not need synchronization primitives, since there was no preamptive multitasking inside the kernel in the good old days. (Already for the 7th version of Unix, I answer. Not.) More precisely, the only method of synchronization was the prohibition of interruptions. But more about that later.
')
First, we list the characters. I know the following synchronization primitives:
User / kernel mode: mutex + cond, sema, enter / leave critical section.
Kernel only: spinlock, interrupt control.
Why all this is needed, the reader probably knows, but still we will clarify.
If a certain data structure can be accessed by two parallel threads (or threads and interrupts), and is an entity that cannot be accessed atomic access, then work with such a structure should be done so that only one thread simultaneously performs complex manipulations with the state of the structure. .
A simple example. List.
struct list { list *next; list *prev }; Insert item into the list.
new_el->next = curr_el->next; new_el->prev = curr_el; curr_el->next->prev = new_el; // 3 curr_el->next = new_el; Everything is primitive. But if this code is executed by two threads in parallel, then instead of a coherent list, there will be an explosion at the macaroni factory. For example, if the second thread starts at the moment when the first thread has finished line 3, then bypassing the list from left to right we will meet one object in the same place, and another object from right to left.
Unpleasant
Apply the mutex - mutually exclusive lock. This lock prohibits the parallel execution of code locked by it - if one thread starts to execute it, the second one will wait at the entrance until the first one is finished.
mutex_lock( &list->mutex); new_el->next = curr_el->next; new_el->prev = curr_el; curr_el->next->prev = new_el; // 3 curr_el->next = new_el; mutex_unlock( &list->mutex); Now good. (Well, it’s not very good if we have more than a hundred processors and they have a lot of code, but this is a completely separate conversation.)
What's happening? Thread A makes a mutex_lock call for the list-> mutex mutex. Which, obviously, belongs to the list that we want to change, and protects access to it. It is not locked, thread A locks the mutex (now it knows that it is locked, and knows who locked it) and continues to work. If now thread B tries to enter the same region of the code (or another one protected by the same mutex - for example, in the function of deleting a list item), then it will not work to lock the locked mutex a second time. Thread B will wait for thread A to trigger mutex_unlock.
By the way, if you and I are nuclear developers, then it is important to understand one more uninteresting feature for an application programmer is the mutex (as well as all the "heavy" synchronization primitives) - if we try to lock a mutex that is already locked with another thread, we are not just waiting - our thread will be "removed from the processor", a context switch will occur. This is valuable because it allows you to load the processor much more efficiently, but there are also problems. Inside an interrupt handler, for example, such primitives cannot be used at all, because context switching inside an interrupt is prohibited and threatens to cause a fair amount of disruption to the operation of the system. But, probably, it will be necessary to write about it separately.
This completely solves the problem if you need to work with a complex data structure. But there are other tasks. For example, inform another thread about the event that that other thread is waiting for.
Consider the functions alloc_mem and free_mem:
// NB! ! alloc_mem() { while(total_free_mem <= 0) { wait_cond(&got_free_mem); } // actually allocate } free_mem() { // actually free mem total_free_mem++; signal_cond(&got_free_mem); } What's going on here? Everything is trite. In the memory allocation function, we look at the global free memory count. If it is empty, there is no free memory, we wait until someone releases the memory - we call wait_cond, which suspends us, until someone signals it - ready, the memory is released.
This, of course, the free_mem () function - it returns memory to the heap, increases the free memory counter and calls signal_cond - informs the suffering ones that there is memory. The one who slept inside wait_cond will “wake up” after such a signal, check that yes, there is memory, and allocate it. All right
Well, no, of course. If the alloc_mem function is called by two threads at once, then there will be trouble - one of them will receive the signal first, will wake up, make sure that there is free memory, and then suddenly take the scheduler and remove it from the processor. And let me wake up the second such thread. The second thread will wake up, also see that there is a memory, will take it and end it. The
For this case, the trouble is not fatal - you can simply return to the beginning of the function and again wait for the weather by the sea. Although, of course, this is bad - we lose processor time for empty throwing.
But, it seems, we know the answer? Add mutex!
// NB! ! alloc_mem() { mutex_lock( &allocator_mutex ); while(total_free_mem <= 0) { wait_cond(&got_free_mem); } // actually allocate mutex_unlock( &allocator_mutex ); } free_mem() { mutex_lock( &allocator_mutex ); // actually free mem total_free_mem++; signal_cond(&got_free_mem); mutex_unlock( &allocator_mutex ); } So good? Not. Memory release will not happen - the alloc_mem () function locked it, fell asleep while waiting for cond, and no one else can enter the mutex, and no one will release the memory, and it will not beep.
Trouble But okay, we know what to do! Before we fall asleep while waiting for the cond, we will heat the mutex, and let others enter free and return our memory. Like this:
// NB! ! alloc_mem() { mutex_lock( &allocator_mutex ); while(total_free_mem <= 0) { mutex_unlock( &allocator_mutex ); wait_cond(&got_free_mem); mutex_lock( &allocator_mutex ); } // actually allocate mutex_unlock( &allocator_mutex ); } In the commentary, you already see that again, not thanks to God. Now what? And now there is a slit, a thin line between the moment when we woke up and left the wait_cond function, receiving a free memory signal from free_mem, and capturing a mutex. At this point, the mutex is not taken, and other threads can again get ahead of us and re-create. It is for this reason that the wait_cond function looks a little different:
wait_cond( cond *c, mutex *m ); It works like this: the function takes a conditional variable as input, which will give us a wake-up signal and a locked mutex:
alloc_mem() { mutex_lock( &allocator_mutex ); while(total_free_mem <= 0) { wait_cond(&got_free_mem,&allocator_mutex); } // actually allocate mutex_unlock( &allocator_mutex ); } The wait_cond function will unlock the mutex, firstly, independently, and secondly, it will do it atomically with respect to the transition to the sleeping state. That is, the thread entering wait_cond will first fall asleep, and then, without interrupting sleep, will unlock the mutex. Conversely, waking up, she first captures the mutex, and then wakes up and continues to work. (This requires the thread switch code to be a good deal of trick, I will try to tell about it in one of the following notes.)
Only such semantics provides 100% consistency and the absence of "race" - race conditions.
Note that the free function code is completely correct:
free_mem() { mutex_lock( &allocator_mutex ); // actually free mem total_free_mem++; signal_cond(&got_free_mem); // 4 mutex_unlock( &allocator_mutex ); // 5 } Only taking into account the above, it should be understood that although we formally awaken the allocator on line 4, it will actually wake up after the execution of line 5, because until this point it is not able to capture the mutex.
Probably, it makes sense to add to the above that the real signal_cond function does not awaken all the waiting threads, but only one (usually with the highest priority), so the situation in the given example is somewhat simpler and more complicated at the same time. It’s simpler because a mechanism is already built inside the alarm, which after one free will only wake up one alloc, and more complicated because it really doesn’t solve anything - we don’t know if the given section is suitable for the freed section, so you need to use broadcast_cond instead of signal_cond, which will awaken all the suffering, giving them the opportunity in a fair fight to decide who will get the resource.
Look at the actual implementation of these primitives here:
mutex.c , cond.c
In the next series - sema semaphore, which alone replaces both mutex and cond. Virtually without ensemble.
This is a series of articles "Overview of synchronization primitives":
Source: https://habr.com/ru/post/278413/
All Articles