There is a task to make 3 threads execute always in a specific order like so:
zero // prints 0s only
odd // prints odd numbers
even // prints even numbers
each of the functions (zero, even, odd) are passed to 3 threads respectively, so the output should be:
0102 for n = 2
010203 for n = 3
01020304 for n = 4
and so on
In code:
class ZeroEvenOdd {
private:
int n;
std::atomic<int> turn{0};
bool flag = false;
public:
ZeroEvenOdd(int n) {
this->n = n;
}
void zero(std::function<void(int)> printNumber) {
int i = 0;
while (i < n) {
while (turn > 0) {// 1 or 2
std::this_thread::yield();
}
printNumber(0);
turn = !flag ? 1 : 2;
flag = !flag;
++i;
}
}
void even(std::function<void(int)> printNumber) {
int i = 2;
while (i <= n) {
while (turn < 2) {// 0 or 1
std::this_thread::yield();
}
printNumber(i);
turn = 0;
i += 2;
}
}
void odd(std::function<void(int)> printNumber) {
int i = 1;
while (i <= n) {
//while (turn <= 2 && turn != 1) {// 0 or 2 // how does this expression eliminate the race ???
while (turn == 0 || turn == 2) { // this causes race condition
std::this_thread::yield();
}
printNumber(i);
turn = 0;
i += 2;
}
}
};
Lets look at function odd:
In the inner while loop I need to check if turn is 0 or 2:
If I the check this way: while (turn == 0 || turn == 2) {...} the race condition appears with a wrong and not complete output.
for n = 24
it might be:
010203040506709080110100130120150140170160190180210200230220...(waiting)
We see here that after 6 7 is printed which is wrong...
But if I check this way while (turn <= 2 && turn != 1) {...} no races appears and output is correct always.
Analogous races appear for other functions zero and even when their inner while loops are changed to use || operator.
I know that combining atomic operations in expression may not necessarily make the whole expression atomic, but I just can't get my head around what scenario can cause race condition with this check while (turn == 0 || turn == 2) {...} ???
Update
Full code example to reproduce the issue:
#include <iostream>
#include <thread>
#include <atomic>
#include <functional>
class ZeroEvenOdd {
private:
int n;
std::atomic<int> turn{0};
bool flag = false;
public:
ZeroEvenOdd(int n) {
this->n = n;
}
void zero(std::function<void(int)> printNumber) {
int i = 0;
while (i < n) {
while (turn > 0) {// 1 or 2
std::this_thread::yield();
}
printNumber(0);
turn = !flag ? 1 : 2;
flag = !flag;
++i;
}
}
void even(std::function<void(int)> printNumber) {
int i = 2;
while (i <= n) {
while (turn < 2) {// 0 or 1
std::this_thread::yield();
}
printNumber(i);
turn = 0;
i += 2;
}
}
void odd(std::function<void(int)> printNumber) {
int i = 1;
while (i <= n) {
//while (turn <= 2 && turn != 1) {// 0 or 2 // how does this expression eliminate the race ???
while (turn == 0 || turn == 2) { // this causes race condition
std::this_thread::yield();
}
printNumber(i);
turn = 0;
i += 2;
}
}
};
int main() {
int n = 24;
std::function<void(int)> printNum = [](int x) {
std::cout << x << std::flush;
};
ZeroEvenOdd zeroEvenOdd(n);
std::thread t1(&ZeroEvenOdd::zero, &zeroEvenOdd, printNum);
std::thread t2(&ZeroEvenOdd::even, &zeroEvenOdd, printNum);
std::thread t3(&ZeroEvenOdd::odd, &zeroEvenOdd, printNum);
t1.join();
t2.join();
t3.join();
return 0;
}
command to compile:
g++ -std=c++14 -fsanitize=thread -pthread test.cpp -o test
For those like me who couldn't glean it immediately from the explanation/code, here is a quick summary:
zero can only leave the inner while loop if turn == 0. It then sets turn to either 1 or 2.
even can only leave the inner while loop if turn == 2. It then sets turn to 0.
The intention is that odd can only leave the inner while loop if turn == 1 (it then sets turn to 0.), but this is not implemented correctly.
Since the conditions for leaving the spin loops are (supposed to be) mutually exclusive, no more than one thread should be outside its own spin loop at a given time, so no concurrent modifications should be possible (and the program should then be race-free).
The problem is that turn == 0 || turn == 2 is not atomic. The following can happen:
zero completes one iteration and sets turn = 2.
odd checks turn == 0, which is false.
Meanwhile, even also sees turn == 2, exits the spin loop, completes an iteration and sets turn = 0.
odd now checks the right side of the || operator: turn == 2, which is false.
odd leaves its spin loop (even though turn == 0!) which is of course unintended and leads to a race between zero and odd.
In short, the problem is that the left hand side of || might be false but become true by the time the right hand side is evaluated. At no point above was the entire turn == 0 || turn == 2 equal to false if evaluated atomically, but since it is not atomic you got a "mix" of false || true and true || false (namely false || false).
The expression turn <= 2 && turn != 1 does not have this problem as the first condition is always true, and the second condition is the check you really want.
In the general case, the solution is to read the atomic once, into a local tmp, and check that. That's better for performance because it allows the compiler to optimize your conditions together, or optimize together whatever you're going to do.
while (true) {
int t = turn;
if (!(t == 0 || t == 2)) break;
yield();
}
Or perhaps hack that into one line with a comma operator. Comma is a "sequence point" so you can assign to t and then read it. But this is not very human-readable.
int tmp;
while (tmp=turn, (tmp == 0 || tmp == 2)) {
yield();
}
If you actually wanted to wait for turn to be odd, you could use turn % 2 == 0 or
while ( turn&1 == 0 )
yield();