Concurrency in OS: Instruction Reordering & Memory Model

First of all, what is Instruction Reordering? For example, you have written some C++ code and you have compiled it into machine instructions with gcc. However, the order in which instructions are actually executed may be different from the order you’ve written in C++. Probably due to optimization by compiler, CPU and memory system to fill pipeline, increase throughput, etc.

In the context of single-threading, this isn’t a problem, because in single-threading, reordering doesn’t break the data dependency among instructions. Through context switching, the dependency is guaranteed.

But this problem matters when it comes to multi-threading. In terms of “ordering”, we have

1. the order defined in your C++ code
2. the order after compilation (could be different from the source code)
3. the order in which the CPU executes
4. the order that other observes

The concurrency bug refers to the 4th order. Let’s explain this with an example

1
2

data = 42;
flag = 1;

1
2

while (flag == 0) {}
std::cout << data;