4 ms·
One additional clarification is useful to make, which is WHY the algorithm is robust to non-atomic reads and writes. Basically, if one process is reading a val
by eigenvalue 3y ago
One additional clarification is useful to make, which is WHY the algorithm is robust to non-atomic reads and writes.
Basically, if one process is reading a value while it is being written to by another process, then it’s possible that the reading process will not just get an old value, but it might get a complete garbage value caused by a partially written or garbled memory value. But even then it still works, and doesn’t even require any kind of “retry” logic, for this reason:
Recall that when a process wants to enter the critical section, it first looks at the numbers (or tickets) assigned to other processes to determine its own number. The process chooses a number that is one higher than the highest number it observes.
Now, if a process reads a garbage value due to a concurrent write, it typically just ignores this value. This is because the garbage value is unlikely to be higher than the maximum valid number it can read from other processes. As a result, this garbage value does not impact the process’s decision about what number to take for itself.
The key is that the process bases its decision on the valid numbers it can read. The algorithm does not depend on every read being perfect. If a process cannot determine a clear maximum due to a garbage value, it bases its decision on the highest valid number it can discern.
The process then enters a waiting phase where it checks if it’s its turn to enter the critical section, based on its number and others’. Again, the presence of a garbage value in one of the reads does not impede this process, as the algorithm only requires a relative ordering based on numbers.
Despite the possibility of reading invalid values, the bakery algorithm maintains safety (no two processes are in the critical section simultaneously) and liveness (every process eventually gets its turn). This is because its core logic - ordering based on numbers and waiting for its turn - remains intact.
- vlovich123 3y agoBut stochastically, it’s possible you’re given a legal value that violates mutual exclusion, no? I’m very fuzzy as to how the busy wait loop that checks all sibling threads for their lock counter number can distinguish this scenario. Cause you could be TID 1, and obtain ticket X even though TID 2 got there first and entered mutual exclusion because at the time when it checked you weren’t even assigned a ticket and entered mutual exclusion… I’m missing something subtle about the algorithm.
- eigenvalue 3y agoThe concern is that if a process reads a partially updated ticket number from another process, it might end up with a ticket number that falsely represents its position in the queue. The algorithm is designed to handle such cases: If the read value is too low (because of a partial update), the process will wait longer than necessary, which doesn’t violate mutual exclusion but may affect fairness temporarily. If the read value is too high, it doesn’t allow the reading process to jump ahead in the queue unfairly. The key point is that even if a process reads a partially updated value, it either waits longer than necessary or gets a number that still respects the ordering. This is because the algorithm uses relative ordering (i.e., based on comparing ticket numbers) rather than absolute values.
- vlovich123 3y agoYeah something wasn’t sitting well with me about this reasoning and Wikipedia says this: > Lamport's bakery algorithm assumes a sequential consistency memory model. Few, if any, languages or multi-core processors implement such a memory model. Therefore, correct implementation of the algorithm typically requires inserting fences to inhibit reordering So yeah, you do need fences because a multi processor superscalar CPU is going to reorder the entering and ticket variables and break the exclusion rules. But then if you have fences, don’t you have the ability to implement a simpler mutual exclusion mechanism by definition?