1CMSC 132: Object-Oriented Programming IISynchronization in JavaDepartment of Computer ScienceUniversity of Maryland, College Park2Multithreading OverviewMotivation & background ThreadsCreating Java threadsThread statesSchedulingSynchronizationData racesLocksDeadlock3Data RaceDefinitionConcurrent accesses to same shared variable, where at least one access is a writePropertiesOrder 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 racepublic void run() { x = x + 1; } // access to x}4Data Race Examplepublic class DataRace extends Thread {static int common = 0;public void run() {int local = common; // data racelocal = local + 1;common = local; // data race}public static void main(String[] args) throws InterruptedException {int max = 3;DataRace[] allThreads = new DataRace[max];for (int i = 0; i < allThreads.length; i++)allThreads[i] = new DataRace();for (DataRace t : allThreads)t.start();for (DataRace t : allThreads)t.join();System.out.println(common); // may not be 3}}5Data Race ExampleSequential execution output6Data Race ExampleConcurrent execution output (possible case)Result depends on thread execution order!7SynchronizationDefinitionCoordination of events with respect to timePropertiesMay be needed in multithreaded programs to eliminate data racesIncurs runtime overhead Excessive use can reduce performance8LockDefinitionEntity can be held by only one thread at a timePropertiesA type of synchronizationUsed to enforce mutual exclusionThread can acquire / release locksOnly 1 thread can acquire lock at a timeThread will wait to acquire lock (stop execution)If lock held by another threadUsed to implement monitorsOnly 1 thread can execute (locked) code at a time9Synchronized Objects in JavaJava objects provide locksApply synchronized keyword to objectWill acquire / release lock associated with objectMutual exclusion for code in synchronization blockExampleObject x = new Object();synchronized(x) { // acquire lock on x on entry... // hold lock on x in block} // release lock on x on exitblock10Synchronized Methods In Java Java methods also provide locks Apply synchronized keyword to methodMutual exclusion for entire body of methodSynchronizes on object invoking methodExamplesynchronized foo() { …code… }// shorthand notation forfoo() {synchronized (this) { …code… }}block11Synchronized Methods In Java12Locks 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 thrown13Synchronization Example14Lock Examplepublic class DataRace extends Thread {static int common = 0;static Object o; // all threads use o’s lockpublic void run() {synchronized(o) { // single thread at onceint local = common; // data race eliminatedlocal = local + 1;common = local; }}public static void main(String[] args) {o = new Object();…}}15Synchronization Issues1. Use same lock to provide mutual exclusion2. Ensure atomic transactions3. Avoiding deadlock16Issue 1) Using Same LockPotential problemMutual exclusion depends on threads acquiring same lockNo synchronization if threads have different locksExamplefoo() {Object o = new Object(); // different o per threadsynchronized(o) {… // potential data race}}17Locks in JavaSingle lock for all threads (mutual exclusion)Separate locks for each thread (no synchronization)18Lock Example – Incorrect Versionpublic class DataRace extends Thread {static int common = 0;public void run() {Object o = new Object(); // different o per threadsynchronized(o) {int local = common; // data racelocal = local + 1;common = local; // data race}}public static void main(String[] args) {…}}19Issue 2) Atomic TransactionsPotential problemSequence of actions must be performed as single atomic transaction to avoid data race Ensure lock is held for duration of transactionExamplesynchronized(o) {int local = common; // all 3 statements mustlocal = local + 1; // be executed togethercommon = local; // by single thread}20Lock Example – Incorrect Versionpublic class DataRace extends Thread {static int common = 0;static Object o; // all threads use o’s lockpublic void run() {int local;synchronized(o) { local = common; } // transaction not atomicsynchronized(o) { // data race may occurlocal = local + 1; // even using lockscommon = local; }}}21Issue 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)22Deadlock 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 a23Deadlock 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 a24DeadlockAvoiding deadlockIn general, avoid holding lock for a long timeEspecially avoid trying to hold two locksMay wait a long time trying to get 2ndlock25Synchronization SummaryNeeded in multithreaded programsCan prevents data races Java objects support synchronizationMany other tricky issuesTo be discussed in future
View Full Document