Atomic Operations
Several assembly language instructions are of type «read-modify-write» — that is, they access a memory location twice, the first time to read the old value and the second time to write a new value.
Suppose that two kernel control paths running on two CPUs try to «read-modify-write» the same memory location at the same time by executing nonatomic operations. At first, both CPUs try to read the same location, but the memory arbiter (a hardware circuit that serializes accesses to the RAM chips) steps in to grant access to one of them and delay the other. However, when the first read operation has completed, the delayed CPU reads exactly the same (old) value from the memory location. Both CPUs then try to write the same (new) value on the memory location; again, the bus memory access is serialized by the memory arbiter, and eventually both write operations succeed. However, the global result is incorrect because both CPUs write the same (new) value. Thus, the two interleaving «read-modify-write» operations act as a single one.
The easiest way to prevent race conditions due to «read-modify-write» instructions is by ensuring that such operations are atomic at the chip level. Any such operation must be executed in a single instruction without being interrupted in the middle and avoiding accesses to the same memory location by other CPUs. These very small atomic operations can be found at the base of other, more flexible mechanisms to create critical sections.
Let’s review 80 x 86 instructions according to that classification.
• Assembly language instructions that make zero or one aligned memory access are atomic. 12!
[2] A data item is aligned in memory when its address is a multiple of its size in bytes. For instance, the address of an aligned short integer must be a multiple of two, while the address of an aligned integer must be a multiple of four. Generally speaking, a unaligned memory access is not atomic.
• Read-modify-write assembly language instructions (such as inc or dec) that read data from memory, update it, and write the updated value back to memory are atomic if no other processor has taken the memory bus after the read and before the write. Memory bus stealing never happens in a uniprocessor system.
• Read-modify-write assembly language instructions whose opcode is prefixed by the lock byte (0xf0) are atomic even on a multiprocessor system. When the control
unit detects the prefix, it «locks» the memory bus until the instruction is finished. Therefore, other processors cannot access the memory location while the locked instruction is being executed.
• Assembly language instructions (whose opcode is prefixed by a rep byte (0xf2,
0xf3), which forces the control unit to repeat the same instruction several times)
are not atomic. The control unit checks for pending interrupts before executing a new iteration.
When you write C code, you cannot guarantee that the compiler will use a single, atomic instruction for an operation like a=a+1 or even for a++. Thus, the Linux kernel provides a
special atomic_t type (a 24-bit atomically accessible counter) and some special functions (see Table 5-2) that act on atomic_t variables and are implemented as single, atomic assembly language instructions. On multiprocessor systems, each such instruction is prefixed by a lock byte.
Table 5-2. Atomic operations in Linux