506CS 538 Spring 2006©Synchronization in JavaWe often want threads to co-operate,typically in how they access shareddata structures.Since thread execution isasynchronous, the details of howthreads interact can be unpredictable.Consider a method update() { n = n+1; val = f(n);}that updates fields of an object.If two or more threads executeupdate concurrently, we might getunexpected or even illegal behavior.(Why?)507CS 538 Spring 2006©A Java method may be synchronized,which guarantees that at most onethread can execute the method at atime. Other threads wishing access,are forced to wait until the currentlyexecuting thread completes.Thusvoid synchronized update() { ... }can safely be used to update anobject, even if multiple threads areactive.There is also asynchronizedstatement in Java that forces threadsto execute a block of codesequentially.synchronized(obj) { obj.n = obj.n+1; obj.val = f(obj.n);}508CS 538 Spring 2006©Synchronization PrimitivesThe following operations are providedto allow threads to safely interact:wait() Sleep until awakenedwait(n) Sleep until awakenedor untiln millisecondspassnotify() Wake up one sleepingthreadnotifyAll() Wake up all sleepingthreadsUsing these primitives, correctconcurrent access to a shared datastructure can be programed.509CS 538 Spring 2006©Consider a Buffer class in whichindependent threads may try to storeor fetch data objects:class Buffer { private Queue q; Buffer() { q = new Queue(); } public synchronized void put(Object obj) { q.enqueue(obj); notify();//Why is this needed? } public synchronized Object get() { while (q.isEmpty()) {//Why a while loop? wait(); } return q.dequeue(); }}510CS 538 Spring 2006©Locks, Semaphores andMonitorsJava’s synchronization mechanismsare based upon the notion of a lock.Alock is a special value that can beheld by at most one thread.If a thread holds a lock, it haspermission to do some “critical”operation like writing a sharedvariable or restructuring a shareddata object.If a thread wants to do an operationbut doesn’t hold the necessary lock, itmust wait until it gets the lock.In Java there is a lock associated witheach run-time object.511CS 538 Spring 2006©Lock Granularity and AccessThough each Java object has a lock,you often don’t want to lock andunlock each object you access.If you are manipulating a large datastructure (like a tree or hash table),acquiring the lock for each object inthe tree or table can be costly anderror-prone.Instead, it is common to create a lockcorresponding to a group of objects.Hence holding the lock to the root ofa tree may give you permission toaccess the whole tree.There is a danger though—if all ormost of a large structure is held byone thread, then other threads won’tbe able to access that structureconcurrently.512CS 538 Spring 2006©For example, a large shared data base(like one used to record currentbookings for an airline) shouldn’t beheld exclusively by one thread—hundreds of concurrent threads maywant to access it at any time. Anintermediate lock, like all reservationsfor a single fight, is more reasonable.There is also an issue of how long youhold a lock. The ideal is to haveexclusive access for as short a periodas is necessary. Work that is notsubject to interference by otherthreads (like computations using localvariables) should be done before alock is obtained. Hence Java’ssynchronized statement allows amethod to get exclusive access to anobject for a limited region, enhancingshared access.513CS 538 Spring 2006©DeadlockA variety of programming problemsappear in concurrent programs thatdon’t exist in ordinary sequentialprograms.The most serious of these is deadlock:Two or more threads hold locks thatother threads require. Each waits forthe other thread to release a neededlock, and no thread is able to execute.As an example of how deadlock mayoccur, consider two threads,t1 andt2. Each requires two files, a masterfile and a log file. Since these files areshared, each has a lock.Assumet1 gets the lock for themaster file whilet2 (at the sameinstant) gets the lock for the log file.514CS 538 Spring 2006©Now each is stuck. Each has one file,and will wait forever for the other fileto be released.In Java deadlock avoidance is whollyup to the programmer. There are nolanguage-level guarantees thatdeadlock can’t happen.Some languages have experimentedwith ways to help programmers avoiddeadlock:• If all locks must be claimed at once,deadlock can be avoided. You eitherget all of them or none, but you can’tblock other threads while making noprogress yourself.• Locks (and the resources theycontrol) can be ordered, with the rulethat you must acquire locks in the515CS 538 Spring 2006©proper order. Now two threads can’teach hold locks the other needs.• The language can require that thelargest set of locks ever needed bedeclared in advance. When locks arerequested, the operating system cantrack what’s claimed and what maybe needed, and refuse to honorunsafe requests.516CS 538 Spring 2006©Fairness & StarvationWhen one thread has a lock, otherthreads who want the lock will besuspended until the lock is released.It can happen that a waiting threadmay be forced to wait indefinitely toacquire a lock, due to an unfairwaiting policy. A waiting thread thatnever gets a lock it needs due tounfair lock allocation faces starvation.As an example, if we place waitingthreads on a stack, newly arrivedthreads will get access to a lockbefore earlier arrivals. This can lead tostarvation. Most thread managers tryto be fair and guarantee that allwaiting threads have a fair chance toacquire a lock.517CS 538 Spring 2006©How are Locks Implemented?Internally, Java needs operations toacquire a lock and release a lock.These operations can be implementedusing the notion of a semaphore.A semaphore is an integer value(often just a single bit) with twoatomic operations: up and down.up(s) increments s atomically.down(s) decrements s atomically.But ifs is already zero, the processdoing thedown operation is put in await state untils becomes positive(eventually some other process shoulddo anup operation).Now locks are easy to implement.Youdoadown(lock) to claim a lock.If someone else has it, you are forced518CS 538 Spring 2006©to wait until the lock is released. Ifthe lock value is > 0 you get it and allothers are “locked out.”When you want to release a lock, youdoup(lock), which makes locknon-zero and eligible for