COMP 409 Lecture Notes - Lecture 15: Openmp, Memory Barrier, Data Model
22 Mar 2018
School
Department
Course
Professor
Document Summary
If success, we have done our part (leave a) If failure, restart to resolve push/pop: busy: 2 threads, 3rd thread to show up give up, 2nd thread has completed the exchange, grab the value (b, set state to empty. Spin set pair to (cid:1731)null, empty(cid:1732) get b. We can associate an exchange for the state. // get a: push(x) is expected to exchange x for null, pop() is expected to exchange null for x. If successful, do not need to actually go through the state. Lock free: lock free linked list, lock free stack, elimination stack (exchanger, na ve (cid:314) aba. Garbage collection: not a problem: y is not deallocated while live, we could still reuse y. Universal construction: almost any data structure and make lock-free version, assume our data structure has an interface public interface seqobject { public response apply(invocation i); Idea: represent the state of our data structure by a log of operations (ordered invocations) (cid:315) tail.
