Some question about Lamport's bakery algorithm

83 Views Asked by At

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

0

There are 0 best solutions below