17. Synchronization Without Locks

MIT 6.172 Performance Engineering of Software Systems, Fall 2018
Instructor: Charles Leiserson
View the complete course: ocw.mit.edu/6-172F18
KZbin Playlist: • MIT 6.172 Performance ...
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
More information at ocw.mit.edu/terms
More courses at ocw.mit.edu

[@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

[@parzer0]

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

[@karthikeyans3]

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!

[@bhagyalakshmi1053]

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

[@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.

[@bhagyalakshmi1053]

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

[@chrise202]

53:55 Oops.. :D I do think he actually used the convention . 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.

[@martijncourteaux]

No, he's just numbering the stores and loads. The load3 and store3 just happen to be the third of their kind, and are in this example to be thought of as a load and store to different memory locations.

[@planetis-m6066]

ＲＥＳＰＥＣＴ to the processors order.

[@abdullahalmosalami2373]

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!

[@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 :))

[@Paul-fn2wb]

You get much more than just learning materials being in a class. Professors, TAs, peers, labs, exams. All are extremely important for effective learning. It takes a lot of determination to achieve the same level of quality on your own. If you have a chance to get into a good school, don't hesitate it. It's definitely worth it.

[@bhagyalakshmi1053]

Execution order 🚚 changes.

[@magno5157]

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.

[@guidomartinez5099]

In Cilk, result is actually shared. It's not like pthreads.

[@magno5157]

@@guidomartinez5099 Oh, that's just unusual.

[@phone_tube]

Need to know what was said at @40.00

[@davinciclone7277]

I think it was like this: Teacher: When is it safe to do this reordering? Student: If A equals B, but if you already have the value 1 in A/B. Just to be clear, that's why the teacher said, "But more generally when is it safe", because this is very specific to the value of A, and I think that the only part that would have been able to figure that out is the compiler, if the data is not dynamic.

[@bhagyalakshmi1053]

A and b one group

[@bhagyalakshmi1053]

Hack,try hack, dictionary checking, story buffer

[@ProfessorWaltherKotz]

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

[@EngSamieh]

In both en.m.wikipedia.org/wiki/C11_(C_standard_revision)

[@bhagyalakshmi1053]

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