1CMSC 330: Organization of Programming LanguagesThreadsCMSC 330 2Synchronization• Refers to mechanisms allowing a programmer to control the execution order of some operations across different threads in a concurrent program.• Different languages have adopted different mechanisms to allow the programmer to synchronize threads.• Java has several mechanisms; we'll look at locks first.2CMSC 330 3Locks (Java 1.5)• Only one thread can hold a lock at once– Other threads that try to acquire it block (or become suspended) until the lock becomes available• Reentrant lock can be reacquired by same thread– As many times as desired– No other thread may acquire a lock until has been released same number of times it has been acquiredinterface Lock {void lock();void unlock();... /* Some more stuff, also */}class ReentrantLock implements Lock { ... }CMSC 330 4Avoiding Interference: Synchronizationpublic class Example extends Thread {private static int cnt = 0;static Lock lock = new ReentrantLock();public void run() {lock.lock();int y = cnt;cnt=y+1;lock.unlock();}}…}Lock, for protecting the shared stateAcquires the lock;Only succeeds if notheld by anotherthreadReleases the lock3CMSC 330 5Applying Synchronizationint cnt = 0;t1.run() {lock.lock();int y = cnt;cnt=y+1;lock.unlock();}t2.run() {lock.lock();int y = cnt;cnt=y+1;lock.unlock();}cnt = 0Shared stateT1 acquires the lockCMSC 330 6Applying Synchronizationint cnt = 0;t1.run() {lock.lock();int y = cnt;cnt=y+1;lock.unlock();}t2.run() {lock.lock();int y = cnt;cnt=y+1;lock.unlock();}cnt = 0Shared stateT1 reads cnt into yy = 04CMSC 330 7Applying Synchronizationint cnt = 0;t1.run() {lock.lock();int y = cnt;cnt=y+1;lock.unlock();}t2.run() {lock.lock();int y = cnt;cnt=y+1;lock.unlock();}cnt = 0Shared stateT1 is preempted.T2 attempts toacquire the lock but failsbecause it’s held byT1, so it blocksy = 0CMSC 330 8Applying Synchronizationint cnt = 0;t1.run() {lock.lock();int y = cnt;cnt=y+1;lock.unlock();}t2.run() {lock.lock();int y = cnt;cnt=y+1;lock.unlock();}cnt = 1Shared stateT1 runs, assigningto cnty = 05CMSC 330 9Applying Synchronizationint cnt = 0;t1.run() {lock.lock();int y = cnt;cnt=y+1;lock.unlock();}t2.run() {lock.lock();int y = cnt;cnt=y+1;lock.unlock();}cnt = 1Shared stateT1 releases the lockand terminatesy = 0CMSC 330 10Applying Synchronizationint cnt = 0;t1.run() {lock.lock();int y = cnt;cnt=y+1;lock.unlock();}t2.run() {lock.lock();int y = cnt;cnt=y+1;lock.unlock();}cnt = 1Shared stateT2 now can acquirethe lock.y = 06CMSC 330 11Applying Synchronizationint cnt = 0;t1.run() {lock.lock();int y = cnt;cnt=y+1;lock.unlock();}t2.run() {lock.lock();int y = cnt;cnt=y+1;lock.unlock();}cnt = 1Shared stateT2 reads cnt into y.y = 0y = 1CMSC 330 12Applying Synchronizationint cnt = 0;t1.run() {lock.lock();int y = cnt;cnt=y+1;lock.unlock();}t2.run() {lock.lock();int y = cnt;cnt=y+1;lock.unlock();}cnt = 2Shared stateT2 assigns cnt, then releases the locky = 0y = 17CMSC 330 13Different Locks Don’t Interact• This program has a race condition– Threads only block if they try to acquire a lock held by another threadstatic int cnt = 0;static Lock l =new ReentrantLock();static Lock m =new ReentrantLock();void inc() {l.lock();cnt++;l.unlock();}void inc() {m.lock();cnt++;m.unlock();}CMSC 330 14Reentrant Lock Example• Reentrancy is useful because each method can acquire/release locks as necessary– No need to worry about whether callers have locks– Discourages complicated coding practicesstatic int cnt = 0;static Lock l =new ReentrantLock();void inc() {l.lock();cnt++;l.unlock();}void returnAndInc() {int temp;l.lock();temp = cnt;inc();l.unlock();}8CMSC 330 15Deadlock• Deadlock occurs when no thread can run because all threads are waiting for a lock– No thread running, so no thread can ever release a lock to enable another thread to runThread 1l.lock();m.lock();...m.unlock();l.unlock();Lock l = new ReentrantLock();Lock m = new ReentrantLock();Thread 2m.lock();l.lock();...l.unlock();m.unlock();This code candeadlock…-- when will it work?-- when will it deadlock?CMSC 330 16Deadlock (cont’d)• Some schedules work fine– Thread 1 runs to completion, then thread 2• But what if...– Thread 1 acquires lock l– The scheduler switches to thread 2– Thread 2 acquires lock m• Deadlock!– Thread 1 is trying to acquire m– Thread 2 is trying to acquire l– And neither can, because the other thread has it9CMSC 330 17Wait Graphsl T1Thread T1 holds lock lmT2Thread T2 attempting to acquire lock mDeadlock occurs when there is a cycle in the graphCMSC 330 18Wait Graph Examplel T1mT2T1 holds lock on lT2 holds lock on mT1 is trying to acquire a lock on mT2 is trying to acquire a lock on l10CMSC 330 19Another Case of Deadlock•lnot released if exception thrown– Likely to cause deadlock some time laterstatic Lock l = new ReentrantLock();void f () throws Exception {l.lock();FileInputStream f =new FileInputStream("file.txt");// Do something with ff.close();l.unlock();}CMSC 330 20Solution: Use Finallystatic Lock l = new ReentrantLock();void f () throws Exception {l.lock();try {FileInputStream f =new FileInputStream("file.txt");// Do something with ff.close();}finally {// This code executed no matter how we// exit the try blockl.unlock();}}11CMSC 330 21Synchronized• This pattern is really common– Acquire lock, do something, release lock under any circumstances after we’re done• Even if exception was raised etc.• Java has a language construct for this– synchronized (obj) { body }• Every Java object has an implicit associated lock– Obtains the lock associated with obj– Executes body– Release lock when scope is exited• Even in cases of exception or method returnCMSC 330 22Example– Lock associated with o acquired before body executed• Released even if exception thrownstatic Object o = new Object();void f() throws Exception {synchronized (o) {FileInputStream f =new FileInputStream("file.txt");// Do something with ff.close();}}12CMSC 330 23Discussion• An object and its associated lock are different!– Holding the lock on an object does not affect what you can do with that object in any way–Ex:synchronized(o) { ... } // acquires lock named oo.f (); // someone else can call o’s methodso.x = 3; // someone else can read and write o’s fieldsobject oo’s lockCMSC 330 24Example: Synchronizing on this• Does this program have a data race?– No, both threads acquire locks on the same object before they
View Full Document
Unlocking...