Transcript Thread 1

Concurrent Programming
Acknowledgements: Some slides
adapted from David Evans, U. Virginia
Why Concurrent Programming
• Abstraction: Some problems are clearer to
program concurrently
– Modularity: Don’t have to explicitly interleave
code for different abstractions (especially: user
interfaces)
– Modeling: Closer map to real world problems:
things in the real world aren’t sequential
• Efficiency: Can leverage the power of
multicores in modern machines
2
Learning Objectives
• Define threads and how to create them in Java
• Identify the challenges with writing multithreaded code
• Apply synchronized methods to ADTs to avoid
race conditions
• Use fine-grained locks in place of coarse
grained locks
• Avoid locks entirely, if possible
3
Concept of threads
• A thread is an independent unit of control that
lives in the same address space as the
application, but has its own execution context
• Each thread has its own stack/local variables
• All objects on the heap are freely accessible to
every thread in the program – shared data
4
Threads in Java
• Every thread in Java inherits from Thread class
• Thread’s constructor takes an object that
implements an interface Runnable
– Any class that implements Runnable, must
implement a run() method with no arguments and
no return value
– The run method can do pretty much anything it
wants to, including spawn new threads.
5
Using threads – Example 1
public class MyRunnable implements Runnable {
private long start, end, sum;
MyRunnable(long start, long end) {
this.start = start; this.end = end;
}
public void run() {
sum = 0;
for (long i = start; i < end; i++)
sum += i;
}
public long getSum() { return sum; }
}
6
Using threads – Example 2
public static void main(String[] args) {
Vector<Thread> threads = new Vector<Threads>();
Vector<Runnable> tasks = new Vector<Runnable>();
long sum = 0;
for (int i = 0; i < 100; i++) {
Runnable task = new MyRunnable(i * 10000, (i + 1) *
10000) );
Thread worker = new Thread(task);
threads.add(worker); tasks.add(task).
worker.start();
}
sleep(100);
// Wait for 100 ms (not required)
for (int i = 0; i < threads.size(); ++i) {
threads[i].join();
sum += tasks[j].getSum();
}
7
Learning Objectives
• Define threads and how to create them in Java
• Identify the challenges with writing multithreaded code
• Apply synchronized methods to ADTs to avoid
race conditions
• Use fine-grained locks in place of coarse
grained locks
• Avoid locks entirely, if possible
8
Challenge of Concurrency
Thread 1
Thread 2
Thread 3
Instruction Streams
DataStore
Coordinated access to
shared data!
Example: Scheduling Meetings
Alice wants to schedule a meeting with Bob and Colleen
Bob
“When can
you meet
Friday?”
Alice “When can
you meet
Friday?”
Colleen
“11am or 3pm”
“9am or 11am”
Picks meeting
time
Reserves 11am
for meeting
“Let’s meet at
11am”
“Let’s meet at
11am”
Reserves 11am
for meeting
10
Race Condition
Bob
Doug
“When can
you meet
Friday?”
“When can
you meet
Friday?”
Alice “When can
you meet
Friday?”
Colleen
“9, 11am or 3pm”
“9am or 11am”
“9, 11am or 3pm”
“Let’s meet at
11am”
Reserves 11am
for Doug
“Let’s meet at
11am”
Picks meeting
time
“Let’s meet at
11am”
“I’m busy
then…”
11
Locking
Doug
“When can
you meet
Friday?”
Bob
“When can
you meet
Friday?”
Alice “When can
you meet
Friday?”
Colleen
“9, 11am or 3pm”
“9am or 11am”
Locks calendar
“3pm”
“Let’s meet at
11am”
Picks meeting
time
“Let’s meet at
11am”
“Let’s meet at
3”
12
Doug
“When can
you meet
Friday?”
Deadlocks
Bob
Alice
“When can
you meet
Friday?”
Colleen
“When can
you meet
Friday?”
“When can
you meet
Friday?”
Locks
calendar
for Doug,
can’t
respond to
Alice
“9, 11am or 3pm”
Can’t schedule
meeting, no
response from
Bob
Locks calendar
for Alice, can’t
respond to Doug
Can’t schedule
meeting, no
response from
Colleen
13
Why are threads hard?
Too few ordering constraints: race conditions
Too many ordering constraints: deadlocks,
poor performance, livelocks, starvation
Hard/impossible to reason about modularly
– If an object is accessible to multiple threads, need to think
about what any of those threads could do at any time!
Testing is even more difficult than for sequential code
– Even if you test all the inputs, you don’t know it will work if
threads run in different order
Learning Objectives
• Define threads and how to create them in Java
• Identify the challenges with writing multithreaded code
• Apply synchronized methods to ADTs to avoid
race conditions
• Use fine-grained locks in place of coarse
grained locks
• Avoid locks entirely, if possible
15
Example: IntSet ADT
public void insert (int x) {
// MODIFIES: this
// EFFECTS: adds x to the set such that
//
this_post = this
u {x}
if ( getIndex(x) < 0 )
elems.add( new Integer(x) );
}
16
Example: IntSet
Thread 1
public void insert (int x) {
// MODIFIES: this
// EFFECTS: adds x to the set
// this_post = this u {x}
if ( getIndex(x) < 0 )
elems.add( new
Integer(x) );
}
Thread 2
public void insert (int x) {
// MODIFIES: this
// EFFECTS: adds x to the set
// this_post = this u {x}
if ( getIndex(x) < 0 )
elems.add( new
Integer(x) );
}
Can you violate the rep invariant in any way ?
17
What’s the Problem ?
• If two threads execute the method
simultaneously, it is possible for the rep
invariant to be violated (i.e., no duplicates)
– Occurs in some interleavings, but not others
– Frustrating to track down problem
– Leads to subtle errors in other parts of the IntSet
• We need to prevent multiple threads from
executing the insert method simultaneously
18
Synchronized Methods
• In Java, you can declare a method as follows:
public synchronized void insert( int x ) {
…
}
• Only one thread may execute a synchronized
method at any point in time
– Other threads queued up at the method’s entry
– Enter the method when the current thread leaves
the method or throws an exception
19
What happens in this case ?
Thread 1
public synchronized void insert
(int x) {
// MODIFIES: this
// EFFECTS: adds x to the set
// this_post = this u {x}
if ( getIndex(x) < 0 )
elems.add( new
Integer(x) );
}
Thread 2
pubic void remove(int x)
{
// MODIFIES: this
// EFFECTS: this_post = this - {x}
int i = getIndex(x);
if (i < 0) return; // Not found
elems.set(i, elems.lastElement() );
elems.remove(elems.size() – 1);
}
20
What’s the problem ?
• The two methods conflict with each other
– While a thread is inserting an object, another
thread can remove the same object (so the postcondition will not be satisfied)
– While a thread is removing an object, if a thread
tries to insert a (different) object, the inserted
object will be removed, and not the original one
• To solve the problem, the insert and remove
methods should not execute simultaneously
21
synchronized to the rescue
• Luckily for us, Java allows multiple methods to be
declared exclusive using the synchronized keyword
public synchronized void insert(int x) { … };
public synchronized void remove(int x) { … };
Only one thread can execute any synchronized method of
the object at any time
Other threads queued up at the entry of their
respective methods, and executed when this leaves
22
What about these methods ?
public int size() {
return elems.size();
}
public boolean isIn(int x) {
return getIndex(x) >= 0;
}
Constructors cannot be synchronized in Java
23
Synchronized Methods
• Declare two methods synchronized if and only
if their simultaneous executions are
incompatible – typically mutator methods
• Observers need not be declared synchronized
– Provided they do not change the rep in any way
– But you do not get any guarantees about the state
when they are executed simultaneously with
mutator methods – may result in inconsistencies
24
IntSet toString() method
public String toString() {
String str = “{ ”;
for (i=0; i<elems.size(); ++i) {
str = str + “ “ + elems.get(i).toString();
return str + “ }”;
}
Does this method need to be synchronized ?
25
Should toString be synchronized ?
• Consider the following code operating on an
IntSet s = {2, 3, 5}.
System.out.println( s.toString() );
Assume that another thread is executing this at
the same time as the set is being printed:
s.remove(3);
This method can print {2, 3, 3}  Breaks the RI
26
Take-aways
• Rules for synchronizing ADTs
– Mutator methods of an ADT should almost always
be synchronized – otherwise, unintended changes
– Observer methods need not be synchronized only
if they are simple return operations
– Observer methods that access the ADTs data
multiple times should be synchronized
– Constructors should never be synchronized
– Underlying data structures should be thread-safe
27
Group Activity
• Consider the intStack ADT which you had
worked on previously. Which methods will you
make synchronized and why ? You must make
the minimal set of methods synchronized to
ensure that the ADT’s implementation is
correct
• What if your ADT had a peek method ? How
would your answer change, if at all ?
28
Learning Objectives
• Define threads and how to create them in Java
• Identify the challenges with writing multithreaded code
• Apply synchronized methods to ADTs to avoid
race conditions
• Use fine-grained locks in place of coarse
grained locks
• Avoid locks entirely, if possible
29
Granularity of Locks
Coarse-grained
• Entire object is protected
with a single lock
• Only one method may be
executed at any time
• Easier to reason about
correctness, but slow !
Fine-grained
• Each part of the object is
protected with separate
locks or not at all protected
• Allows multiple methods to
be executed simultaneously
• Harder to reason about
correctness, but faster !
30
Example: hashTable
• Consider a hashtable where each table entry is
stored in a vector. We can allow updates of
one entry even while another entry is read, as
the two do not interfere with each other.
• However, implementing this ADT using
synchronized methods in Java will mean that
all threads are locked out of the table when
one is executing a synchronized method
31
Solution: Fine-grained locks
• Create lock objects and synchronize on them
explicitly  arbitrary code inside blocks
synchronized(lock1) {
doOperation1();
doOperation2();
}
32
Fine-grained locks: How to use
them ?
• You will need as many lock objects as the
number of synchronization operations needed
in the ADT. For the hash-table example, you
can update a hash-table entry as follows:
int index = hashMap.get(key);
synchronized( lock[index] ) {
hashMap.update(key, value);
}
33
Learning Objectives
• Define threads and how to create them in Java
• Identify the challenges with writing multithreaded code
• Apply synchronized methods to ADTs to avoid
race conditions
• Use fine-grained locks in place of coarse
grained locks
• Avoid locks entirely, if possible
34
Locks are problematic …
• Cause unnecessary synchronization
– Performance overheads can be extremely high
• May lead to deadlocks and/or starvation
• Not straightforward to compose code together
which has locks  can lead to deadlocks
35
Better to avoid locks entirely …
• But how ?
– We care about the invariant/spec being preserved.
Locking is only a means to the end.
• One solution: Use only immutable ADTs
– Immutable ADTs cannot be modified, so no
problem of concurrent modifications
– Default in functional languages such as Haskell
36
Immutable ADTs
• Consider an ADT ImmutableIntSet, which does
not allow insert/remove operations. The only
operations it supports are union, and different
both of which result in a new ImmutableIntSet
• Show that the ADT does not require any
synchronized operations for correctness.
37
ImmutableIntSet ADT
class ImmutableIntSet {
private Vector<Integer> elems;
ImmutableIntSet(Vector<Integer> e);
public ImmutableIntSet union(ImmutableIntSet,
ImmutableIntSet);
public ImmutableIntSet difference
(ImmutableIntSet, ImmutableIntSet);
public int size();
public boolean isIn(int x);
}
38
Group Activity
• Implement the union and difference
operations of ImmutableIntSet, and show that
they will be correct in a multi-threaded
context even if no lock is taken during their
execution.
39
Learning Objectives
• Define threads and how to create them in Java
• Identify the challenges with writing multithreaded code
• Apply synchronized methods to ADTs to avoid
race conditions
• Use fine-grained locks in place of coarse
grained locks
• Avoid locks entirely, if possible
40