Synchronization in JavaSynchronization OverviewUnsufficient atomicityInsuffient Atomicity ExampleData RaceQuiz TimeAnswer: Yes!How Can This Happen?SynchronizationLockSynchronized Objects in JavaSynchronized Methods In JavaSlide 13Locks in JavaUsing synchronizationQuestionsNot sharing same lockSynchronization IssuesIssue 1) Using Same LockSlide 20Issue 2) Atomic TransactionsSlide 22Issue 3) Avoiding DeadlockDeadlock Example 1Deadlock Example 2Waiting for GodotAbstract Data Type – BufferBuffer usageBuffer ImplementationEliminating DeadlockWorks barely, if at allIssue 4) Using Wait & NotifyThread Class Wait & Notify MethodsUsing Wait & NotifyUsing Wait and NotifyAllActually, that won’t compileSlide 37Synchronization in JavaNelson Padua-PerezBill PughDepartment of Computer ScienceUniversity of Maryland, College ParkSynchronization OverviewUnsufficient atomicityData racesLocksDeadlockWait / NotifyUnsufficient atomicityVery frequently, you will want a sequence of actions to be performed atomically or indivisiblynot interrupted or disturbed by actions by any other threadx++ isn’t an atomic operationit is a read followed by a writeCan be a intermittent errordepends on exact interleavingInsuffient Atomicity Examplepublic class InsuffientAtomicity implements Runnable { static int x = 0; public void run() { int tmp = x; x = tmp+1; } public static void main(String[] args) { for (int i = 0; i < 3; i++) new Thread(new InsuffientAtomicity ()).start(); System.out.println(x); // may not be 3 }}Data RaceDefinitionConcurrent accesses to same shared variable, where at least one access is a writevariable isn’t volatileCan expose all sorts of really weird stuff the compiler and processor are doing to improve performanceQuiz Timex = y = 0x = 1j = yThread 1y = 1i = xThread 2Can this result in i = 0 and j = 0?start threadsAnswer: Yes!x = y = 0x = 1j = yThread 1y = 1i = xThread 2How can i = 0 and j = 0?start threadsHow Can This Happen?Compiler can reorder statementsOr keep values in registersProcessor can reorder themOn multi-processor, values not synchronized to global memoryThe memory model is designed to allow aggressive optimizationincluding optimizations no one has implemented yetGood for performancebad for your intuition about insufficiently synchronized codeSynchronizationUsesMarks when a block of code must not be interleaved with code executed by another threadMarks when information can/must flow between threadsNotesIncurs a small amount of runtime overhead if only used where you might need to communicate between threads, not significantused everywhere, can add upLockDefinitionEntity can be held by only one thread at a timePropertiesA type of synchronizationUsed to enforce mutual exclusionThread can acquire / release locksThread will wait to acquire lock (stop execution)If lock held by another threadSynchronized Objects in JavaAll Java objects provide locksApply synchronized keyword to objectMutual exclusion for code in synchronization block Example Object x = new Object(); void foo() { synchronized(x) { // acquire lock on x on entry ... // hold lock on x in block } // release lock on x on exitblockSynchronized Methods In Java Java methods also provide locks Apply synchronized keyword to methodMutual exclusion for entire body of methodSynchronizes on object invoking methodExample synchronized void foo() { …code… } // shorthand notation for void foo() { synchronized (this) { …code… } }blockSynchronized Methods In JavaLocks in JavaPropertiesNo other thread can get lock on x while in blockDoes not protect fields of xexcept by conventionother threads can access/update fieldsbut can’t obtain lock on xBy convention, lock x to obtain exclusive access to xLocked block of code critical sectionLock is released when block terminatesNo matter how the block terminates:End of block reachedExit block due to return, continue, breakException thrownUsing synchronizationpublic class UseSynchronization implements Runnable { static int x = 0;static Object lock = new Object(); public void run() { synchronized(lock) { int tmp = x; x = tmp+1; } }}QuestionsWhat would happen if the lock field were not static?Why don’t we just make the run method synchronized?Why don’t we just synchronize on x?Not sharing same lockpublic class NotSharingLock implements Runnable { static int x = 0;Object lock = new Object(); public void run() { synchronized(lock) { int tmp = x; x = tmp+1; } }}Synchronization IssuesUse same lock to provide mutual exclusionEnsure atomic transactionsAvoiding deadlockIssue 1) Using Same LockPotential problemMutual exclusion depends on threads acquiring same lockNo synchronization if threads have different locksExample void run() { Object o = new Object(); // different o per thread synchronized(o) { … // potential data race } }Locks in JavaSingle lock for all threads (mutual exclusion)Separate locks for each thread (no synchronization)Potential problemSequence of actions must be performed as single atomic transaction to avoid data race Ensure lock is held for duration of transactionExample synchronized(lock) { int tmp = x; // both statements must // be executed together x = tmp; // by single thread }Issue 2) Atomic TransactionsUsing synchronizationpublic class InsuffientAtomicity implements Runnable { static int x = 0;static Object lock = new Object(); public void run() { int tmp; synchronized(lock) { tmp = x; }; synchronized(lock) { x = tmp+1; } }Issue 3) Avoiding DeadlockIn general, want to be careful about performing any operations that might take a long time while holding a lockWhat could take a really long time?getting another lockParticularly if you get deadlockDeadlock Example 1Thread1() { Thread2() { synchronized(a) { synchronized(b) { synchronized(b) { synchronized(a) { … … } } } }} }// Thread1 holds lock for a, waits for b// Thread2 holds lock for b, waits for aDeadlock Example 2void moveMoney(Account a, Account b, int amount) { synchronized(a) { synchronized(b) { a.debit(amount); b.credit(amount); } }}Thread1() { moveMoney(a,b,10); } // holds lock for a, waits for bThread2() { moveMoney(b,a,100); } // holds lock for b, waits for aWaiting for Godot Sometimes, you need to wait for another thread else to do something before you can do somethingAbstract Data Type – BufferBuffer Transfers items from producers to
View Full Document