Due to that the Linux kernel supports symmetric multi-processing (SMP) so it must use a set of synchronization mechanisms to achieve predictable results, free of race conditions.
To avoid race conditions the programmer must first identify the critical section that can generate a race condition. The critical section is the part of the code that reads and writes shared memory from multiple parallel contexts.
A classical race condition example is an incorrect implementation for a release operation of resource counter:
void release_resource()
{
counter--;
if(!counter)
free_resource();
}The code above will generate a race condition that can cause freeing the resource twice.
In most cases the release_resource() function will only free the resource once. However, in the scenario above, if thread A is preempted right after decrementing counter and thread B calls release_resource() it will cause the resource to be freed. When resumed, thread A will also free the resource since the counter value is 0
One of approaches to identify race conditions is that use atomic operations that are provided by hardware.
Definition – What does Atomic Operation mean?
Atomic operations in concurrent programming are program operations that run completely independently of any other processes.
Atomic operations are used in many modern operating systems and parallel processing systems.
Atomic Operation
Atomic operations are often used in the kernel, the primary component of most operating systems. However, most computer hardware, compilers and libraries also provide varying levels of atomic operations.
In loading and storing, computer hardware carries out writing and reading to a word-sized memory. To fetch, add or subtract, value augmentation takes place through atomic operations. During an atomic operation, a processor can read and write a location during the same data transmission. In this way, another input/output mechanism or processor cannot perform memory reading or writing tasks until the atomic operation has finished.
Where data is being used by an atomic operation that is also in use by other atomic or non-atomic operations, it can only exist in either sequential processing environments or locking mechanisms have to be used to avoid data errors. Compare and swap is another method but does not guarantee data integrity for atomic operation results.
The problem comes when two operations running in parallel (concurrent operations) utilize the same data and a disparity between the results of the operations occurs. Locking locks variable data and forces sequential operation of atomic processes that utilize the same data or affect it in some way.
Linux provides a unified API to access atomic operations:
- integer based:
Simple: atomic_inc(), atomic_dec(), atomic_add(), atomic_sub()
Conditional: atomic_dec_and_test(), atomic_sub_and_test()
- Bit based:
Simple: test_bit(), set_bit(), change_bit()
Conditional: test_and_set_bit(), test_and_clear_bit(), test_and_change_bit()
For example, we could use atomic_dec_and_test() to implement the resource counter decrements and value checking atomic:
void release_resource()
{
if(atomic_dec_and_test(&counter))
free_resource();
}Discussion
One complication with atomic operations is encountered in multi-core systems, where an atomic operation is not loger atomic at the system level (but still atomic at the core level).
To understand why, we need to decompose the atomic operation in memory loads and stores. Then we can construct race condition scenarios where the load and store operations are interleaved across CPUs, like in the example below where incrementing a value from two processors will produce an unexpected result:
In order to provide atomic operations on SMP systems different architectures use different techniques. For example, on x86 a LOCK prefix is used to lock the system bus while executing the prefixed operation:
On ARM the LDREX and STREX instructions are used together to guarantee atomic access: LDREX loads a value and signals the exclusive monitor that an atomic operation is in progress. The STREX attempts to store a new value but only succeeds if the exclusive monitor has not detected other exclusive operations. So, to implement atomic operations the programmer must retry the operation (both LDREX and STREX) until the exclusive monitor signals a success.