17. Synchronization Without Locks

MIT 6.172 Performance Engineering of Software Systems, Fall 2018
Instructor: Charles Leiserson

Prof. Leiserson discusses non-lock synchronization using memory models, Peterson's algorithm, instruction reordering, and hardware reordering. He discusses the compare-and-swap operation; lock-free stacks, pushes, and pops; and the ABA problem.

License: Creative Commons BY-NC-SA

[leixun]

*My takeaways:*
1. Memory model: sequential consistency 0:49
2. Mutual exclusion without locks 12:28
3. Relaxed memory consistency 34:16: never synchronize program through memory
4. Compare and swap 1:06:54
5. Lock free algorithm 1:18:15

[parzer]

Nice and clear. No pauses in between topics and slides. Excellent flow of information thats easily interpreted! Well done Prof!

[karthikeyans]

Very good lecture to get the idea of Memory models and an intro to Lock-free algorithms.

[isbestlizard]

This is a really good course, up there with 6.021 with Erik Demaine!

[tetraphobie]

53:30 In TSO, I think in rule (4), a LOAD may be reordered with a STORE to the the same location, too, if they happen on different cores of a multi-core CPU (so the write buffers are different and the order-preserving load bypass does not trigger). Otherwise, the suggested ordering on slide 29 would be impossible. Took me a while to realize this nuance. Another source I found seems to confirm it, though I'm still not 100% sure this explanation is fully correct.

[chrise]

53:55 Oops.. :D I do think he actually used the convention <Load|Store+location>. The student was right to point there was a mistake in the diagram where Load3 is Before Store3, and Load4 is before Store4 thus violating rule 4.

[bhagyalakshmi]

Nice 👍 database explain popular thank you this position on summer collection

[bhagyalakshmi]

How to storage working memory handle per files containers and how many for you containers also hear how to for handling

[cnc-ua]

Great example/proof performance=currency.
To get this course listen you had to pay $$$ to be sitting in a class in Fall 2018 instead of getting it for free a year later :))

[abdullaalmosalami]

What I'm not feeling great about is why is there a linear order? Isn't it assumed that the separate processor instructions are run CONCURRENTLY? Isn't that what the word means!

[magno]

1:12:58 Why is the race condition on the variable result??? The variable result is a local variable! Every thread has a separate instance of result! OTOH, myArray has external linkage, and that's the only variable in the example that's possibly shared across threads.

[bhagyalakshmi]

Hack, try hack, dictionary checking, story buffer

[ProfessorWaltherKotz]

The C++11 standard, not the C11 standard...

[bhagyalakshmi]

(pf, coie cookies po files)
Tomorrow meeting "good night "professor thanks for explaining.
Laughing to pariyon class explaining master. 🗃️