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