Concurrency in Java

Concurrency in Java : Concurrency in Java Last Updated: Fall 2005 © 2005: Paul Ammann

Agenda : Agenda Some General Concurrency Mechanisms Concurrency in Java Synchronization in Java Rules for Threads Liskov Abstraction Example Kalin’s Dining Philosophers

Concepts to be covered : Concepts to be covered Threads, concurrency Interleaving, race conditions Atomicity of execution Mutual exclusion Thread states Synchronization, locks Inter-thread communication

Some General Concurrency Mechanisms : Some General Concurrency Mechanisms Rendevous (Ada) Obviates need for certain low level primitives In practice: Web Servers Single server, scores of clients! Waiting time? Threads Subject of today’s talk Database mechanisms Concurrency entirely hidden from user ACID properties

Everyday examples : Everyday examples Restaurant 1: One kitchen Single recipe 2 cooks Restaurant 2: 1 Client Order 2 waiters On a Machine Memory Code Threads

Interleaving : Interleaving c.inc(); // c is a counter c.inc(); System.out.println(c.get()); Suppose 2 threads are created Each executes the 3 statements Order in which they are executed? Does thread 1 get to execute all 3 before thread 2?

Atomicity of execution : Atomicity of execution What is the smallest unit of execution that cannot be interleaved? Can we ensure atomicity across multiple statements? // broken because of interleaving private static int nextSerialNumber = 0; // in short nSN public static int generateSerialNumber(){ return nextSerialNumber++; } // nSN = nSN + 1

Atomic read and write : Atomic read and write Time Thread 1 reads nSN = 4 Thread 2 reads nSN = 4 //should read 5 Thread 3 reads nSN = 4 //should read 6 Thread 1 writes nSN = 5 Thread 2 writes nSN = 5 //should write 6 Thread 4 reads nSN = 5 //should read 7

Concurrency in Java : Concurrency in Java Two mechanisms to obtain a Thread Extend the Thread class class T extends Thread { … public void run() {…} } Thread t = new T(); t.start(); // start() calls run() Implement the Runnable interface Examples: Counter1.java, Counter2.java

Thread states : Thread states Initial – prior to start() Runnable – started, but not necessarily running (may be preempted) Blocked – waiting for some event to occur Stop – the run() method has returned (avoid other ways of entering Stop state) The join() method waits for a thread to stop

Synchronization in Java : Synchronization in Java Threads use a “lock” model Lock is associated with an object “this” for synchronized methods Specified object for synchronized block Only one thread at a time may hold the lock Examples Wacky.java, Wacky1.java BoundedQueue.java SyncBoundedQueue.java

Communication among Threads : Communication among Threads wait() – enter blocked state and release the lock notify() – wake up some (other) blocked thread notifyAll() – wake up all the (other) blocked threads. This is harder than it looks! Example: BoundedQueueWithGuards.java

What can go Wrong? : What can go Wrong? Deadlock – no progress possible Starvation – no access to a resource Simultaneous access to shared resources – unpredictable behavior Various tools to analyze these issues

Rules for Threads (from Joshua Bloch’s Effective Java) : Rules for Threads (from Joshua Bloch’s Effective Java) Synchronize access to shared mutable data (48) Avoid excessive synchronization (49) Never invoke wait() outside a loop (50) Don’t depend on thread scheduler (51) Document thread safety (52) Avoid thread groups (53)

Liskov Abstraction Example : Liskov Abstraction Example Consider a Dining Philosophers Solution Kalin pages 465-468 File: DiningPhils.java What is the Liskov Documenation? What is the Abstraction Function? What is a Typical Element? What should toString() look like?

Finding a Typical Element : Finding a Typical Element Classes contain Instance variables Methods Typical element is a notion of state Therefore look at instance variables For Philosopher class: host isEating index ts

So What is the State? : So What is the State? Instance variables may reflect Critical aspects of the state Or they may be redundant In this case host – notion of a table (critical) isEating – state of philosoper (critical) index – philosopher’s seat at table (critical) ts – how long to pause (redundant)

A Possible Typical Element : A Possible Typical Element A typical philosopher is a tuple Where: table is the group of philosophers with whom this philosopher is dining seat is the index at the table activity is eating or thinking

Abstraction Function : Abstraction Function AF(c) is table = c.host seat = c.index activity = c.isEating ? eating : thinking

toString() Implementation : toString() Implementation Direct implementation of AF(c) Note that c.host has its own toString()