4 ms·
(EDITED; misread algorithm earlier.) No, sorry, that doesn't work. Consider the following sequence: 1. A sets g1 = A 2. A reads g2 = none 3. A reads g1 = A
by colanderman 13y ago
(EDITED; misread algorithm earlier.) No, sorry, that doesn't work. Consider the following sequence:
1. A sets g1 = A
2. A reads g2 = none
3. A reads g1 = A
4. B sets g1 = B
5. B reads g2 = none
6. B reads g1 = B
7. A sets g2 = A (read in #3)
8. A reads g1 = B
9. A retries
10. A reads g2 = A
11. A succeeds
12. B sets g2 = B (read in #6)
13. B reads g1 = B
14. B reads g2 = B
15. B succeeds
You also are missing memory fences, which are needed to ensure proper ordering of memory operations. (Otherwise the processor is free to speculate reads and delay writes between cores.) See https://www.kernel.org/doc/Documentation/memory-barriers.txt https://www.kernel.org/doc/Documentation/memory-barriers.txt for a thorough explanation.
- mgraczyk 13y agoDid you miss the check at line 32?
- jacquesm 13y agoThat check does nothing, you're about to loop and then do the 'if' without all the checks, see my other comment.
- keithgabryelski 13y agothe order you supply here can not happen (at least if i understand what you are saying) if step #9 happens then #10 will be skipped by the "if (state->g2 == SPIN_LOCK_NO_LOCKER) {" what am i missing?
- wzdd 13y agoThread A sets g1 to A (line 31), thread A enters the "if" statement (line 32), thread A reads the value of g1 and is about to write that value to g2 but gets pre-empted (half of line 33). Thread B sets g1 to B (line 31), thread B enters the "if" statement (because A hasn't yet written g1 to g2, line 32), thread B reads the value of g1 (half of line 33) and writes that value to g2 (the other half), then does its tests and returns OK. Thread A sets g2 to A (the other half of line 33). Thread A does its tests and notices that g1 != g2. Thread A returns to the top of the loop and notices that g2 == A (line 22). Thread A returns OK. This is assuming that reads are strongly ordered between processes and cores, and that code executes in-order, none of which is true.
- colanderman 13y agoI misread the algorithm, sorry. On second read, it appears to check out (modulo memory barriers!) up to the retry-on-fail, which, as Jacques Mattheij points out elsewhere, leads to a failure in mutual exclusion. I've updated my reply to reflect this failure mode.