1CMSC 433 – Programming LanguageTechnologies and ParadigmsSpring 2004Threads and SynchronizationApril 1, 2004(thanks to Doug Lea for some slides)54Administrivia• Project 4 posted– Don’t forget to submit exercises file– I.e., don’t just submit *.java• Remember to watch newsgroup, web page– Updates on web page– Some hints on project 4 on the newsgroup• Midterm “grades” mailed out in a few days– After project 3 regrades are done255Avoiding Interference:Synchronizationpublic class Example extends Thread { private static int cnt = 0; static Object lock = new Object(); public void run() { synchronized (lock) { int y = cnt; cnt = y + 1; } } …}Lock, for protecting the shared stateAcquires the lock;Only succeeds if notheld by anotherthreadReleases the lock56Applying Synchronizationint cnt = 0;t1.run() { synchronized(lock) { int y = cnt; cnt = y + 1; }}t2.run() { synchronized(lock) { int y = cnt; cnt = y + 1; }}cnt = 0Shared stateT1 acquires the lock357Applying Synchronizationint cnt = 0;t1.run() { synchronized(lock) { int y = cnt; cnt = y + 1; }}t2.run() { synchronized(lock) { int y = cnt; cnt = y + 1; }}cnt = 0Shared stateT1 reads cnt into yy = 058Applying Synchronizationint cnt = 0;t1.run() { synchronized(lock) { int y = cnt; cnt = y + 1; }}t2.run() { synchronized(lock) { int y = cnt; cnt = y + 1; }}cnt = 0Shared stateT1 is pre-empted.T2 attempts toacquire the lock but failsbecause it’s held byT1, so it blocksy = 0459Applying Synchronizationint cnt = 0;t1.run() { synchronized(lock) { int y = cnt; cnt = y + 1; }}t2.run() { synchronized(lock) { int y = cnt; cnt = y + 1; }}cnt = 1Shared stateT1 runs, assigningto cnty = 060Applying Synchronizationint cnt = 0;t1.run() { synchronized(lock) { int y = cnt; cnt = y + 1; }}t2.run() { synchronized(lock) { int y = cnt; cnt = y + 1; }}cnt = 1Shared stateT1 releases the lockand terminatesy = 0561Applying Synchronizationint cnt = 0;t1.run() { synchronized(lock) { int y = cnt; cnt = y + 1; }}t2.run() { synchronized(lock) { int y = cnt; cnt = y + 1; }}cnt = 1Shared stateT2 now can acquirethe lock.y = 062Applying Synchronizationint cnt = 0;t1.run() { synchronized(lock) { int y = cnt; cnt = y + 1; }}t2.run() { synchronized(lock) { int y = cnt; cnt = y + 1; }}cnt = 1Shared stateT2 reads cnt into y.y = 0y = 1663Applying Synchronizationint cnt = 0;t1.run() { synchronized(lock) { int y = cnt; cnt = y + 1; }}t2.run() { synchronized(lock) { int y = cnt; cnt = y + 1; }}cnt = 2Shared stateT2 assigns cnt, then releases the locky = 0y = 164Locks• Any Object subclass has (can act as) a lock• Only one thread can hold the lock on an object– Other threads block until they can acquire it• If a thread already holds the lock on an object– The thread can reacquire the same lock many times• ...Locks are reentrant– Lock is released when object unlocked thecorresponding number of times• No way to only attempt to acquire a lock– ...in Java 1.4– Either succeeds, or blocks the thread765Synchronized Statement• synchronized (obj) { statements }• Obtains the lock on obj before executingstatements in block• Releases the lock when the statement blockcompletes– Either normally, or due to a return, break, orexception being thrown in the block66Synchronized Methods• A method can be synchronized– Add synchronized modifier before return type• Obtains the lock on object referenced by thisbefore executing method– Releases lock when method completes• For a static synchronized method– Locks the Class object for the class• Accessible directly, e.g. Foo.class– Not the same as this!867Synchronization Examplepublic class State { private int cnt = 0; public int synchronized incCnt(int x) { cnt += x; } public int synchronized getCnt() { return cnt; }}public class MyThread extends Thread { State s; public MyThread(State s) { this.s = s; } public void run() { s.incCnt(1) } public void main(String args[]) { State s = new State(); MyThread thread1 = new MyThread(s); MyThread thread2 = new MyThread(s); thread1.start(); thread2.start(); }}Synchronizationoccurs in Stateobject itself,rather than inits caller.68Synchronization Style• Design decision– Internal synchronization (class is thread-safe)• Have a stateful object synchronize itself (e.g., withsynchronized methods)– External synchronization (class is thread-compatible)• Have callers perform synchronization before calling the object• Can go both ways:– Thread-safe: Random– Thread-compatible: ArrayList, HashMap, …969Synchronization not a Panacea• Two threads can block on locks held by theother; this is called deadlockObject A = new Object();Object B = new Object();T1.run() { synchronized (A) { synchronized (B) { … } }}T2.run() { synchronized (B) { synchronized (A) { … } }}70Deadlock• Quite possible to create code that deadlocks– Thread 1 holds lock on A– Thread 2 holds lock on B– Thread 1 is trying to acquire a lock on B– Thread 2 is trying to acquire a lock on A– Deadlock!• Not easy to detect when deadlock hasoccurred– Other than by the fact that nothing is happening1071Deadlock: Wait graphsA T1Thread T1 holds lock ABT2Thread T2 attempting toacquire lock BDeadlock occurs when there is a cycle in the graph72Wait graph exampleA T1BT2T1 holds lock on AT2 holds lock on BT1 is trying to acquire a lock on BT2 is trying to acquire a lock on A1173Key Ideas• Multiple threads can run simultaneously– Either truly in parallel on a multiprocessor– Or can be scheduled on a single processor• A running thread can be pre-empted at any time• Threads can share data– In Java, only fields can be shared– Need to prevent interference• Synchronization is one way, but not the only way– Overuse use of synchronization can create deadlock• Violation of liveness74Guaranteeing Safety• Ensure objects are accessible only when in aconsistent and appropriate state– All invariants are maintained– Presents subclass obligations• Use locks to enforce this– Rule of thumb 1: You must hold a lock whenaccessing shared data– Rule of thumb 2: You must not release a lockuntil shared data is in a valid state1275Guaranteeing Liveness• Ensuring availability of services– Called methods eventually execute• Ensuring progress of activities– Managing resource
View Full Document
Unlocking...