In bakery's algorithm, we have lock function as below
lock(integer i) {
Entering[i] = true;
Number[i] = 1 + max(Number[1], ..., Number[NUM_THREADS]);
Entering[i] = false;
for (integer j = 1; j <= NUM_THREADS; j++) {
// Wait until thread j receives its number:
while (Entering[j]) { /* nothing */ }
// Wait until all threads with smaller numbers or with the same
// number, but with higher priority, finish their work:
while ((Number[j] != 0) && ((Number[j], j) < (Number[i], i))) { /* nothing */ }
}
}
In wikipedia, I found the following claim
This algorithm is not built on top of some lower level "atomic" operation
But I don't really understand why.
If there is no atomic operation, I thought it possible for a compiler or an assembler to reorder the instructions like the following:
Number[i] = 1 + max(Number[1], ..., Number[NUM_THREADS]);
Entering[i] = true;
Entering[i] = false;
since it won't affect the result if it's a single thread process.
The mechanism of waiting the entering section is being corrupted.
Not very sure where I made a logical error