Department of Computer Science © Ritwik Banerjee
Multithreaded Programming
Part II
CSE 219
Stony Brook University, Department of Computer Science
Department of Computer Science © Ritwik Banerjee
Thread Scheduling
❏ In a Java application, main is a thread on its own
❏ Once multiple threads are made Runnable
❏ the thread scheduler of the Java Runtime Environment (JRE) decides
❏ when each thread is scheduled to run
❏ based on a simple algorithm called fixed-priority scheduling
❏ this algorithm schedules threads on the basis of their priority relative to other Runnable threads
❏ Every thread has a priority associated with it
❏ An int constant ranging between 1 (MIN_PRIORITY) and 10 (MAX_PRIORITY)
❏ The default value is the middle value, 5 (NORM_PRIORITY)
❏ When a thread is created, it inherits its priority from the thread that created it
Department of Computer Science © Ritwik Banerjee
Thread Priorities
❏ The JRE chooses the Runnable thread with the highest priority
❏ Only when this thread stops, yields, or becomes not-Runnable does a lower priority
thread get its chance to run
❏ If multiple threads with the same priority are ready to run, the scheduler picks one
randomly, and the chosen thread will run until one of the following happens:
i. a higher priority thread becomes Runnable
ii. this thread yields or its run() method exits
iii. the time-slicing of the OS decides this thread’s time allocation is over
❏ At any given time, the highest priority thread is running. But there is NO guarantee! The thread scheduler may
some times run a lower-priority thread to avoid starvation (we will soon see what this means)
❏ Therefore, use priorities for efficiency, but do NOT rely on them for 100% correct algorithm
Department of Computer Science © Ritwik Banerjee
Thread State Transitions
New
Dead
Runnable Blocked
Thread t = new Thread();
t.start()
t.sleep(…)
sleep time over!
t.stop()
t.stop(), or
run() method exits t.stop()
This is a slightly simplified picture. For details, see the Thread.State enumerable type:
❏ http://docs.oracle.com/javase/7/docs/api/java/lang/Thread.State.html
http://docs.oracle.com/javase/7/docs/api/java/lang/Thread.State.html
Department of Computer Science © Ritwik Banerjee
Thread State Transitions
New
Dead
Runnable Blocked
Thread t = new Thread();
t.start()
t.sleep(…)
sleep time over!
t.stop()
t.stop(), or
run() method exits t.stop()❏ Newly constructed Thread
❏ Not yet start()ed
❏ Not yet Runnable
❏ Not yet known to the thread
scheduler
Department of Computer Science © Ritwik Banerjee
Thread State Transitions
New
Dead
Runnable Blocked
Thread t = new Thread();
t.start()
t.sleep(…)
sleep time over!
t.stop()
t.stop(), or
run() method exits t.stop()
❏ After being start()ed
❏ Is Runnable
❏ Can be scheduled by the
thread scheduler
Multiple threads can be in this state
at a given time
Department of Computer Science © Ritwik Banerjee
Thread State Transitions
New
Dead
Runnable Blocked
Thread t = new Thread();
t.start()
t.sleep(…)
sleep time over!
t.stop()
t.stop(), or
run() method exits t.stop()❏ Thread is made un-Runnable
by the sleep() method
❏ In this state, the thread is
waiting for a monitor lock to
enter (or re-enter) a
synchronized block/method
Department of Computer Science © Ritwik Banerjee
Thread State Transitions
New
Dead
Runnable Blocked
Thread t = new Thread();
t.start()
t.sleep(…)
sleep time over!
t.stop()
t.stop(), or
run() method exits t.stop()
❏ run() method exits
❏ stop() method called
❏ Deprecated method. Do NOT use.
❏ In fact, avoid deprecated methods as a
rule of thumb
❏ Once in the dead state, a thread cannot
be scheduled again
❏ Use isAlive() to take a pulse. A
thread is said to be alive if it has been
started and has not yet died
Department of Computer Science © Ritwik Banerjee
Executing a thread: start()ing or run()ning?
public class StartRunning {
private static class Wool extends Thread {
@Override
public void run() {
System.out.println(“Run me for the winter.”);
}
}
public static void main(String… args) {
Wool t = new Wool();
t.run();
System.out.println(“Put a break point on me and use the debugger to see
how many threads are running.”);
t.start();
System.out.println(“How about now?”);
System.out.println(“That was cozy!”);
}
}
Department of Computer Science © Ritwik Banerjee
Thread Interference
class Counter {
private int c = 0;
public void increment() { c++; }
public void decrement() { c–; }
public int value() { return c; }
}
❏ Even simple unary operations like c++
are not atomic
❏ It consists of three steps:
i. Retrieve current value of c
ii. Increment the retrieved value by 1
iii. Store the incremented value back in c
❏ An atomic transaction is one that
cannot be broken down into
sub-transactions
❏ It either runs completely, or not at
all
❏ In this context, a transaction is
simply a code execution that
changes stored data
❏ Parts of a code that need to be
atomic (for multithreading to work
properly) are called critical areas of
the code
Department of Computer Science © Ritwik Banerjee
Thread Interference
class Counter {
private int c = 0;
public void increment() { c++; }
public void decrement() { c–; }
public int value() { return c; }
}
❏ Thread interference leads to the
result of thread A being lost, as it is
overwritten by thread B
❏ Suppose this application has two
threads A and B
❏ A calls increment() at around the
same time as B calls decrement()
❏ Their actions being not atomic, the
actual sequence of transactions may
be the following:
i. A: retrieve c
ii. B: retrieve c
iii. A: increment() with result = 1
iv. B: decrement() with result = -1
v. A: store result in c; c is now 1
vi. B: store result in c; c is now -1
Department of Computer Science © Ritwik Banerjee
Memory Inconsistency
❏ Memory consistency errors occur when different threads have inconsistent
views of what should be the same data.
❏ Can be avoided by understanding the happens-before relationship
❏ Guarantees that memory writes by one statement are visible to another statement
❏ Example:
❏ As before, suppose A and B are two threads
❏ And A increments the value:
❏ Then B prints the value:
❏ The printed value may still be zero!
❏ Because there is no guarantee that A’s action happens-before that of B
int c = 0; // int defined and initialized
c++;
System.out.println(c);
Department of Computer Science © Ritwik Banerjee
Creating the happens-before relation
❏ Invoking a thread’s start() method
❏ Everything before calling start() is within a single thread, so transactions happen in the
order of the code (i.e., line by line)
❏ Every statement before calling start() happens before every statement of the new
thread
❏ Terminating a thread and causing another thread to return via join()
❏ Then, all the statements executed by the terminated thread have a happens-before
relation with all the statements following the successful join
❏ But the most important way of establishing the happens-before relation is
via synchronization
Department of Computer Science © Ritwik Banerjee
Synchronization
❏ Prevents thread interference and memory inconsistency
❏ But can cause thread contention
❏ multiple threads try to access the same resource at the same time, and
❏ cause the JRE to execute threads more slowly (or even suspend thread execution)
❏ Types of thread contention are
❏ Starvation
❏ Livelock
Department of Computer Science © Ritwik Banerjee
Synchronization
❏ Synchronization is built around an internal entity known as the intrinsic
lock or monitor lock
❏ Enforces exclusive access to an object’s state
❏ Establishes happens-before relations required for correct visibility
❏ Every object has an intrinsic lock associated with it
❏ A thread that requires exclusive access acquires this lock
❏ And after accomplishing its task, releases this lock
❏ There are other types of locks as well, like the ReentrantLock
❏ See the bank example in the code examples
Department of Computer Science © Ritwik Banerjee
Synchronization
❏ Methods can be synchronized
public class SynchronizedCounter {
private int c = 0;
public synchronized void increment() {
c++;
}
public synchronized void decrement() {
c–;
}
public synchronized int value() {
return c;
}
}
❏ Just add the synchronized keyword to
the method declaration
❏ Each invocation to a synchronized
method is atomic
❏ When one thread is executing a
synchronized method for this, all other
threads that invoke synchronized
methods for the same objectsuspend
execution until the first thread is done
❏ When a synchronized method exits, it
establishes a happens-before relation
with any future invocation of a
synchronized method for the same
object
Department of Computer Science © Ritwik Banerjee
Synchronization
❏ Code blocks can be synchronized
❏ A synchronized statement can be used to acquire a lock on any object, not
just this object, when executing a block of the code in a method:
synchronized (expr) {
statements;
}
❏ The expression expr must evaluate to an object reference
❏ If the object is already locked by another thread, the thread is blocked until the lock is
released
❏ When a lock is obtained on the object, the statements in the synchronized block are
executed, and then the lock is released
Department of Computer Science © Ritwik Banerjee
Liveness
❏ A concurrent application’s ability to execute in a timely manner is known as
its liveness
❏ The most common problem of liveness is deadlock
❏ Two other types of liveness problems:
a. Starvation
b. Livelock
Department of Computer Science © Ritwik Banerjee
The Dining Philosopher’s Problem
❏ Five silent philosophers sit at a table around a
bowl of spaghetti, and a fork is placed between
each pair of adjacent philosophers
❏ Each philosopher must alternately think and eat
❏ A philosopher can only eat spaghetti when he
has both left and right forks
❏ A philosopher can grab the fork on his right or
the one on his left as they become available, but
can’t start eating before getting both of them
❏ The possibility of a deadlock: if all 5 philosophers
pick up the left fork at the same time and wait
until the right fork is available, then no progress
is possible again (starvation)
Department of Computer Science © Ritwik Banerjee
Deadlocks
❏ Deadlock Resolution
❏ One technique: don’t let waiting threads lock other data!
❏ Release all their locks before making them wait
❏ There are all sorts of proper algorithms for thread lock ordering (beyond the scope of this
course)
A thread T1 holds a lock on
L1 and wants lock L2
A thread T2 holds a lock on
L2 and wants lock L1
Department of Computer Science © Ritwik Banerjee
Starvation
❏ A situation where a thread is unable to gain regular access to shared
resources and is unable to make progress
❏ This happens when shared resources are made unavailable for long periods
by greedy threads. For example:
❏ Suppose an object provides a synchronized method that often takes a long time to return
❏ If one thread invokes this method frequently, other threads that also need frequent
synchronized access to the same object will often be blocked
Department of Computer Science © Ritwik Banerjee
❏ A thread T1 acts in response to the action of another thread T2
❏ T2, in turn, acts in response to another thread T3
❏ T3, in turn, acts in response to T4
❏ …
❏ Livelock: threads not blocked, but too busy responding to each other
❏ The responses could be cyclical T1 → T2 → T3 → … → T1
❏ A and B are walking in opposite directions in a corridor, and
❏ A moves to his left to let B pass while B moves to her right to let A pass
❏ Seeing that they are still blocking each other, A moves to his right, while B moves to her
left
❏ They’re still blocking each other, so it goes on …
Livelock
Department of Computer Science © Ritwik Banerjee
Executors
❏ There is a close connection between
❏ the task being done by a new thread (the Runnable object), and
❏ the thread itself (the Thread object)
❏ Putting them together works fine for simple applications
❏ But at larger scales
❏ separate thread management and thread creation from the rest of the application
❏ Objects that encapsulate these functions are known as executors
❏ Three executor object types defined by the executor interfaces
(1) Executor, (2) ExecutorService, and (3) ScheduledExecutorService
Department of Computer Science © Ritwik Banerjee
Executor Interfaces
The java.util.concurrent package defines three executor interfaces:
Executor ExecutorService ScheduledExecutorService
A simple interface that
supports launching new
tasks
Subinterface of Executor that adds
features to manage the lifecycle of
individual tasks as well as of the
evecutor itself
A subinterface of ExecutorService
that supports future and/or periodic
execution of tasks
Department of Computer Science © Ritwik Banerjee
Executor Service
Thread Pool
❏ A thread pool is a software design pattern for concurrent programs
Submitter 1
Submitter 2
Submitter 3
Task submitters
Task Task Task Task
Thread 1
Thread 2
Thread 3
Thread 4
Task queue
Thread Pool
Department of Computer Science © Ritwik Banerjee
Thread Pool and Executors
❏ The Executors class contains several methods for creation of
pre-configured thread pool instances
❏ A simple example of using Executors to acquire an Executor instance
backed by a single thread pool and an unbounded queue for executing
tasks sequentially
❏ The Executor and ExecutorService interfaces are used to work with
different thread pool implementations in Java
❏ Usually, it is a good idea to keep your code decoupled from the actual implementation of
the thread pool and use these interfaces throughout your application
Executor executor = Executors.newSingleThreadExecutor();
executor.execute(() -> System.out.println(“Hello World”));