Unformatted text preview:

6.852 Lecture 22●Techniques for highly concurrent objects (continued)–“lazy” synchronization–illustrate on list-based sets, apply to other data structures●Transactional memory●Reading:–Herlihy-Shavit Chapter 8 (Chapter 9 in draft version)–Herlihy, Luchangco, Moir, Scherer paper–Dice, Shalev, Shavit paperReview●Techniques–coarse-grained locking●simple: works well for low contention–fine-grained locking●allows more concurrency, but also deadlock●greater time and space overhead (due to more locks)●simple two-phase policy guarantees atomicity (doesn't help list)●hand-over-hand locking●optimistic locking–lock-free techniques●separate “logical” and “physical” deletion●“announce” intention to facilitate helping (to guarantee progress)Review●Optimistic locking–search down list without locking; lock appropriate nodes–verify that nodes are adjacent and in list (validation)●requires traversing the list again●retry if validation fails–good if validation typically succeeds●note that the list can have changed between locking and validation–traversal is wait-free, but●must traverse list twice (why?)●even contains must lock node (is this true?)–contains is typically by far the most common operationLazy list algorithm●Idea: use “mark” from lock-free list to avoid retraversal–“lazy” removal: first mark node, then splice around it●like lock-free list, except mark can be separate from next pointer–still locks node to be removed and predecessor–validation: check nodes are adjacent and unmarked●unmarked implies in list: no need to retraverse●much shorter critical sectionLazy RemovalaabcdLazy RemovalaabcdPresent in listLazy RemovalaabcdLogically deletedLazy RemovalaabcdPhysically deletedLazy list algorithm●Observation: contains(x) doesn't need to lock/validate–find first node with key ≥ x–return true iff unmarked and key = x●what if some other node with key = x is in the list?Lazy list algorithma b ccontains(b)Lazy list algorithma b ccontains(b)Lazy list algorithma b ccontains(b)Lazy list algorithma b cremove(b)Lazy list algorithma b ca not markedLazy list algorithma b ca still points to bLazy list algorithma b clogical deleteLazy list algorithma b cphysical deleteLazy list algorithma b ccontains(b)Lazy list algorithma b cadd(b)Lazy list algorithma b cadd(b)bLazy list algorithma b ccontains(b)bIs this okay?Lazy list algorithma cadd(b)Lazy list algorithma cadd(b)bLazy list algorithma ccontains(b)bLazy list algorithma b ccontains(b)bIs this okay?Lazy list algorithm●Serializing contains(x) that returns false–if node found has key > x●when node.key is read?●when pred.next is read?●when pred is marked (if it is marked)?– if node with key = x is marked●when mark is read?●when pred.next is read?●when mark is set?Lazy list algorithm●Serializing contains(x) that returns false–if node found has key > x●when node.key is read?●when pred.next is read?●when pred is marked (if it is marked)?– if node with key = x is marked●when mark is read?●when pred.next is read?●when mark is set?Can we do this for the optimistic list?Review●Lock-free algorithm–“mark” nodes before removing from the list●marking is logical deletion–don't modify marked nodes●use CAS, mark and next pointer in same word–if encounter a marked node, help●physically delete node from list–if CAS fails, retry operation (except if you marked the node)Lock-free list with wait-free contains●add and remove just like lock-free list●contains does not help, does not retry–just like in lazy listApplication of list techniques●Trees●Skip lists–multiple layers of links–list at each layer is sublist of layer below–logarithmic expected search time if each list has half elements of next lower level●probabilistic guarantees258790Summary●Reduce granularity●Two-phase locking●Avoid deadlock by ordering locks●Optimistic techniques●Separate “logical” and “physical” changes●Enable helping (by “announcing” intention)●Optimize for the common case (usually reading)–analyze read-only operations separately●Maintain invariants●Weaken requirements: progress, invariantsOther techniques/issues●Pointer swinging–maintain extra level of indirection–current version of object is never modified–to modify object: copy, modify copy, then “swing pointer”–okay for small objects–vary granularity to trade between efficiency and simplicity–beware of ABA problem (garbage collection helps here)–only lets you change one object at a time●Keep copies–maintain an indicator of which is copy is “current”–like pointer swinging with pointer in reverse directionOther techniques/issues●Revocable locks/ownership records–like locks, but others can take away locks●they may undo your changes (aka rollback), or else help you finish●must leave undo or announcement info–contention can lead to “thrashing”●Keep logs–remember operations done, derive state●keep recent version to reduce overhead●can roll back by truncating log–like universal construction from consensusOther techniques/issues●Contention management–queuing–backoff–priorities●Composability–build algorithms/systems hierarchically–very hard with locks●Weaker progress guarantees–obstruction-freedom●Adaptive algorithms–overhead depends on actual rather than potential contentionProblems with locks●Reduce concurrency●Possibility of deadlock●Convoying●Priority inversion●Difficult to manage–everyone must follow locking convention; hard to enforce/check●Not composableProblems with CAS or LL/SC●Access only single location●ABA problem (for CAS)●Spurious failures (for LL/SC)●Typically complex algorithms●Helping interacts badly caching●Contention management can break progress guarantees●Difficult to compose (because of single-location limit)–bank transfer exampleTransactional memory●Raise level of abstraction–programmer specifies atomicity boundaries: transactions–system guarantees atomicity●commits if it can●aborts if not (roll back any changes)●possibly retry on abort–system manages contention (possibly separable functionality)–nested transactions compose●but large transactions may not commitTransactional memory●begin transaction●commit●“acquire”/“open” objects–differentiate reading and writing●validate●maintain


View Full Document

MIT 6 852 - Lecture Notes

Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?