CSC 2/458, 30 Jan. and 4 Feb. 2008 Read Moir & Shavit for Monday 4 Feb. There will be a Part 3 to assignment 1, due a week from today WATCH THE WEB ---------------- Scalable Synchronization an issue for all busy-wait synchronization will address locks today; see papers for barriers recall problems with test-and-set locks contention unfairness test-and-test-and-set limits contention to release time on cache-coherent machines bounded exponential backoff reduces contention doesn't solve the problem, esp. on modern machines ticket locks fair, but still vulnerable to contention nice backoff option queue-based locks array-based Anderson Graunke & Thakkar linked list-based MCS CLH MCS code type qnode = record next : ^qnode locked : Boolean type lock = ^qnode // initialized to null // parameter I, below, points to a qnode record allocated // (in an enclosing scope) in shared memory locally-accessible // to the invoking processor procedure acquire_lock (L : ^lock, I : ^qnode) I->next := null predecessor : ^qnode := swap (L, I) if predecessor != null // queue was non-empty I->locked := true predecessor->next := I repeat while I->locked // spin procedure release_lock (L : ^lock, I: ^qnode) if I->next = null // no known successor if CAS (L, I, null) return // CAS returns true iff it stored repeat while I->next = null // spin I->next->locked := false CLH code type qnode = record succ_must_wait : Boolean type lock = ^qnode // initialized to point to an unowned qnode procedure acquire_lock (L : ^lock, I : ^qnode) I->succ_must_wait := true pred : ^qnode := I->prev := swap (L, I) repeat while pred->succ_must_wait procedure release_lock (ref I : ^qnode) pred : ^qnode := I->prev I->succ_must_wait := false I := pred // take pred's qnode performance results see paper note, esp., - Table II (p. 51): even w/exp. backoff, remote spinning impacts other operations - difference between Fig. 20 and 21 reflects broadcast v. network interconnect - Figure 22 and Table III don't build dance-hall machines! Is HW synch. needed? prob. not for locks, though const. factor can be recouped in particular, for small data structures, acquiring the lock can automatically grab colocated data Note that some big machines (e.g. Crays) provide HW barriers asymptotic benefit tradeoffs array-based locks require O(L*T) space; linked lists are O(L+T), which is optimal CLH requires cache coherence to avoid contention; MCS works on non-cache-coherent machines MCS has potential spin in release CLH requires only swap; MCS requires CAS or LL/SC CLH requires dummy node in empty lock (can be modified to remove, at the cost of an extra atomic op in release) CLH can be modified to work on NCC machines, with an extra level of indirection; MCS can be modified to eliminate spin in release. If you make these changes to both, you arrive at pretty much the same place (with dummy node and only swap). both MCS and CLH have non-standard interfaces; MCS can be modified (IBM K42 innovation) to use standard interface with no performance cost; CLH requires dynamic allocation of queue nodes any fair lock dramatically exacerbates the preemption problem (below) K42 extension: type element = record next : ^element tail : ^element #define MUST_WAIT 1 // not a valid pointer type lock = element // initialized to next = tail = null // If threads are waiting for a held lock, next points to the queue // node of the first of them, and tail to the queue node of the last. // A held lock with no waiters has value [&head, null]. // A free lock with no waiters has value [null, null]. procedure acquire_lock (L : ^lock) loop pred : ^element := L->tail if pred = null if CAS(&L->tail, null, L) return // else try again else // lock appears to be held I : element := [null, MUST_WAIT] if CAS(&L->tail, pred, &I) // I'm now in line pred->next = &I // changes the lock itself if I am the only waiter while (I.tail = MUST_WAIT) //spin // I now have the lock. L->tail points to me iff there // are no other waiters. L->next is not in use. L->next = null // guess I was the only waiter if !CAS(&L->tail, &I, L) // there is another waiter after all while (I.next == null) // spin L->next = I.next return procedure release_lock (L : ^lock) succ : ^element = L->next if succ == null if CAS(&L->tail, L, null) return while (succ = L->head) == null // spin succ->tail = null ---------------- reader-writer locks like mutex locks, come in several variants PPoPP'91 paper explores TAS and MCS analogues X reader-pref, writer-pref, and fair ================================================================ << how do results look from assignment 1 part 2? which locks seem fastest? why? what happens when thread count exceeds processor count? what might we do about that? >> ================================================================ preemption problem with all locks especially bad for fair locks solutions (or at least partial solutions) timeout (spin-then-yield, try-locks) spin-then-block don't preempt me (various variants) handshake when passing published time: allows one to _guess_ whether peer is preempted don't preempt that other thread (wider kernel interface) yield processor to specific other thread (likewise) lock-free data structures ---------------- timeout trivial for TAS locks no obvious solution for ticket locks problematic for queue-based locks (how do I get out of line?) series of papers, culminating in HiPC 2005 -- addresses both timeout and preemption tolerance several variants, most promising of which - marks deleted nodes (dynamically allocated), allowing successor to link them out of the queue. - uses _published time_ heuristic to detect preempted peers ---------------- summary of advantages of lock-free synchronization tolerate preemption thread failure page faults avoid deadlock priority inversion potentially higher concurrency than with coarse grain locks challenge of lock-free synchronization data structure-specific algorithms are hard to come up with -- every one is a publishable result general-purpose algorithms have historically been very slow, but this is changing! -- new algs., HW support