'&$%CSE 303:Concepts and Tools for Software DevelopmentHal PerkinsAutumn 2008Lecture 23— Concurrency Part II: LocksCSE303 Autumn 2008, Lecture 23 1'&$%Where are weDone:• Basics of shared-mem ory multithreading• Fork-join parallelism• Critical sections via atomicDoing:• Critical sections via careful use of locks (a.k.a. mutexes)• Pitfalls of using locks• Other concurrency gotchasCSE303 Autumn 2008, Lecture 23 2'&$%Lock basicsA lock is acquired and released by a thread.• At most one thread “holds it” at any moment• Acquiring it “blocks” until the holder releases it and the blockedthread acquires it– Many threads might be waiting; one will “win”.– The lock-im pleme ntor avoids race conditions on thelock-acquire• So to keep two things from happening at the same time , surroundthem with the same lock-acquire/lock-releaseCSE303 Autumn 2008, Lecture 23 3'&$%Locks in C/JavaC: Need to initialize and destroy mutexes (a synonym for locks).• The joys of CAn initialized (pointer to a) mutex can be loc ked or unlocked vialibrary function calls.Java: A synchronized statement is an acquire/release.• Any object can serve as a lock.• Lock is released on any control-transfer out of the block (return,break, exception, ...)• “Synchronized methods” just save keystrokes.CSE303 Autumn 2008, Lecture 23 4'&$%Choosing how to lockNow we know what locks are (how to make them, whatacquiring/releasing means), but programming with them correctly andefficiently is difficult...• As before, if critical sections are too small we have races; if too bigwe m ay not communicate enough to get our work done efficiently.• But now, if two “synchronized blocks” grab different locks, t heycan be interleaved e ven if they access the same memory– A “data race”• Also, a lock-acquire blocks until a loc k is available and only thecurrent-holder can release it.– Can have “deadlock” ...CSE303 Autumn 2008, Lecture 23 5'&$%DeadlockObject a;Object b;void m1() { void m2() {synchronized a { synchronized b {synchronized b { synchronized a {... ...}} }}}A cycle of threads waiting on locks means none will ever run again!Avoidance: All code acquires locks in the same order (very hard todo). Ad hoc: Don’t hold onto locks too long or while calling intounknown code.Recovery: detect deadlocks, kill off and rerun one of the processes(databases)CSE303 Autumn 2008, Lecture 23 6'&$%Rules of ThumbAny one of the following are sufficient for avoiding races:• Keep data thread-loc al (an object is reachable, or at least onlyaccessed by, one thread).• Keep data read-only (do not assign to object fields after anobject’s constructor)• Use loc ks c onsiste ntly (all access es to an object are made w hileholding a particular lock)• Use a partial-order to avoid deadlock (over-simple example: donot hold multiple locks at once?)These are tough invariants to get right, but that’s the price ofmultithreaded programming today.But... one way to do all the above is to have “one lock for all shareddata” and that is inefficient...CSE303 Autumn 2008, Lecture 23 7'&$%False sharing“False s haring” refers to not allowing separate things to happen inparallel.Example:synchronized x { synchronized x {++y; ++z;} }More realistic e xample: one lock for all bank accounts rather than onefor each accountOn the other hand, acquiring/releasing locks is not so c heap, so“locking more with the same lock” can improve performance.This is the “locking granularity” question• Coarser vs. finer granularityCSE303 Autumn 2008, Lecture 23 8'&$%Very challenging situationA favorite example for ridiculing locks:If each bank account has its own lock, how do you write a “transfer”method s uch that no other thread can see the “wrong total balance”?// race (not data race) // potential deadlockvoid xfer(int a,Acct other){ void xfer(int a,Acct other){synchronized(this) { synchronized(this) {balance += a; synchronized(other) {other.balance -= a; balance += a;} other.balance -= a;} }}}The problem is there is no relative order among accounts, so “inversetransfers” could deadlockCSE303 Autumn 2008, Lecture 23 9'&$%A final gotchaYou would naturally assume that all memory accesses happen in “someconsistent order” that is “determined by the code”.Unfortunately, compilers and chips are often allowed to cheat(reorder)! The assertion in the right thread may fail!initially flag==falsedata = 42; while(!flag) {}flag = true; assert(data==42);To disallow reordering the programmer must:• Use loc k acquires (no reordering across them), or• Declare flag to be volatile (for experts, not us)CSE303 Autumn 2008, Lecture 23 10'&$%ConclusionThreads make a lot of otherwise- correct approaches incorrect.• Writing “thread-safe” libraries can be excruciating.• Use an expe rt implem entation, e.g., Java’s ConcurrentHashMap?But they are increasingly important for efficient use of computingresources (“the multicore revolution”).Locks and shared-memory are (just) one common approach.Learn about other useful synchronization mechanisms (e.g., conditionvariables) in CSE451.CSE303 Autumn 2008, Lecture 23
View Full Document
Unlocking...