Synchronization in JavaSynchronization OverviewData RaceData Race ExampleSlide 5Slide 6SynchronizationLockSynchronized Objects in JavaSynchronized Methods In JavaSlide 11Locks in JavaSynchronization ExampleLock ExampleSynchronization IssuesIssue 1) Using Same LockSlide 17Lock Example – Incorrect VersionIssue 2) Atomic TransactionsSlide 20Issue 3) Avoiding DeadlockDeadlock Example 1Deadlock Example 2Abstract Data Type – BufferBuffer ImplementationBuffer ImplementationEliminating DeadlockDeadlockIssue 4) Using Wait & NotifyThread Class Wait & Notify MethodsUsing Wait & NotifyExample – Using Wait & NotifyExample – Cashiers at CheckoutSynchronization SummarySynchronization in JavaFawzi EmadChau-Wen TsengDepartment of Computer ScienceUniversity of Maryland, College ParkSynchronization OverviewData racesLocksDeadlockWait / NotifyData RaceDefinitionConcurrent accesses to same shared variable, where at least one access is a write PropertiesOrder of accesses may change result of programMay cause intermittent errors, very hard to debug Examplepublic class DataRace extends Thread { static int x; // shared variable x causing data race public void run() { x = x + 1; } // access to x}Data Race Examplepublic class DataRace extends Thread { static int common = 0; public void run() { int local = common; // data race local = local + 1; common = local; // data race } public static void main(String[] args) { for (int i = 0; i < 3; i++) new ThreadExample().start(); System.out.println(common); // may not be 3 }}Data Race ExampleSequential execution outputData Race ExampleConcurrent execution output (possible case)Result depends on thread execution order!SynchronizationDefinitionCoordination of events with respect to timePropertiesMay be needed in multithreaded programs to eliminate data racesIncurs runtime overhead Excessive use can reduce performanceLockDefinitionEntity 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 (non-Mutable) Java objects provide locksApply synchronized keyword to objectMutual exclusion for code in synchronization block Example Object x = new Object(); 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 foo() { …code… } // shorthand notation for foo() { synchronized (this) { …code… } }blockSynchronized Methods In JavaLocks in JavaPropertiesNo other thread can get lock on x while in blockOther threads can still access/modify x!Locked block of code critical sectionLock is released when block terminatesEnd of block reachedExit block due to return, continue, breakException thrownSynchronization ExampleLock Examplepublic class DataRace extends Thread { static int common = 0; static Object o; // all threads use o’s lock public void run() { synchronized(o) { // single thread at once int local = common; // data race eliminated local = local + 1; common = local; } } public static void main(String[] args) { o = new Object(); … }}Synchronization Issues1. Use same lock to provide mutual exclusion2. Ensure atomic transactions3. Avoiding deadlock4. Use wait & notify to improve efficiencyIssue 1) Using Same LockPotential problemMutual exclusion depends on threads acquiring same lockNo synchronization if threads have different locksExample foo() { 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)Lock Example – Incorrect Versionpublic class DataRace extends Thread { static int common = 0; public void run() { Object o = new Object(); // different o per thread synchronized(o) { int local = common; // data race local = local + 1; common = local; // data race } } public static void main(String[] args) { … }}Issue 2) Atomic TransactionsPotential problemSequence of actions must be performed as single atomic transaction to avoid data race Ensure lock is held for duration of transactionExample synchronized(o) { int local = common; // all 3 statements must local = local + 1; // be executed together common = local; // by single thread }Lock Example – Incorrect Versionpublic class DataRace extends Thread { static int common = 0; static Object o; // all threads use o’s lock public void run() { int local; synchronized(o) { local = common; } // transaction not atomic synchronized(o) { // data race may occur local = local + 1; // even using locks common = local; } }}Issue 3) Avoiding DeadlockPotential problemThreads holding lock may be unable to obtain lock held by other thread, and vice versaThread holding lock may be waiting for action performed by other thread waiting for lockProgram is unable to continue execution (deadlock)Deadlock Example 1Object a;Object b;Thread1() { 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 swap(Object a, Object b) { Object local; synchronized(a) { synchronized(b) { local = a; a = b; b = local; } }}Thread1() { swap(a, b); } // holds lock for a, waits for bThread2() { swap(b, a); } // holds lock for b, waits for aAbstract Data Type – BufferBuffer Transfers items from producers to consumersVery useful in multithreaded programsSynchronization needed to prevent multiple consumers removing same itemBuffer Implementation Class BufferUser() { Buffer b = new Buffer(); ProducerThread() { // produces items Object x = new Object(); b.add(x); } ConsumerThread() { // consumes items Object y; y = b.remove(); }}Buffer Implementationpublic class Buffer { private Object [] myObjects; private int numberObjects = 0; public synchronized add( Object x ) { myObjects[ numberObjects++ ] = x;
View Full Document
Unlocking...