When two or more concurrently running threads access a shared data item and the final result depends on the order of execution, we have a race condition. Let us take a look at an example. Suppose we have two threads A and B as shown below. Thread A increases the shared variable Count by 1 and thread B decreases Count by 1. Since Count is shared by two threads, we know it should be protected by a mutex lock or a binary semaphore.
If the access to Count is protected by a mutex lock or a semaphore, when both threads reach the critical section the order of execution is either Count++ followed by Count--, or Count-- followed by Count++. If the current value of Count is 10, both execution orders yield 10 because Count is increased by 1 followed by decreased by 1 for the former case, and Count is decreased by 1 followed by increased by 1 for the latter.
However, if Count is not protected by mutual exclusion, we might get difference results. Statements Count++ and Count-- may be translated to machine instructions as shown below:
If both statements are not protected, the execution of the instructions may be interleaved due to context switching. More precisely, while thread A is in the middle of executing Count++, the system may switch A out and let thread B run. Similarly, while thread B is in the middle of executing Count--, the system may switch B out and let thread A run. Should this happen, we have a problem. The following table shows the execution details. For each thread, this table shows the instruction executed and the content of its register. Note that registers are part of a thread's environment and different threads have different environments. Consequently, the modification of a register by a thread only affects the thread itself and will not affect the registers of other threads. The last column shows the value of Count in memory. Suppose thread A is running. After thread A executes its LOAD instruction, a context switch switches thread A out and switches thread B in. Thus, thread B executes its three instructions, changing the value of Count to 9. Then, the execution is switched back to thread A, which continues with the remaining two instructions. Consequently, the value of Count is changed to 11!
The following shows the execution flow of executing thread B followed by thread A, and the result is 9!
This example shows that without mutual exclusion, the access to a shared data item may generate different results if the execution order is altered. This is, of course, a race condition. This race condition is due to no mutual exclusion. However, keep in mind that improper mutual exclusion may also cause race conditions as will be discussed on subsequent pages.
|
|
|