Transcript Въведение в java.util.concurrent

Михаил Стойнов
&
Красимир Семерджиев





Hardware evolution - free lunch is over
Java concurrency before Java SE 5
Atomic operations
Java.util.concurrent overview
Java SE5 vs. Java SE6




Moore’s law for CPU
clock speed is over
Intel talks about 100x
core CPU
Next major revolution in
software - concurrency
Majority of software is not
ready for that
“There ain’t no such thing
as a free lunch.”
—R. A. Heinlein,
?!?!?




Availability – faster response time, maximize
throughput, access DBs/backends
GUIs– autonomous objects, animation,
concurrent events
Parallelism – utilizing CPUs, overlapping I/O,
multiple clients
Protection – isolating different activities,

Hard to implement!

Higher resource usage

Need to start decomposing tasks

Deal with safety and isolation




System(VM) = Objects + Activities(Threads)
Activities touch/change objects’ state
Every called method should eventually
execute as soon as possible
Liveness and safety not enforced by
compilers
Java Virtual Machine
method
method






Object
Every object has a lock
lock
Every Class has a lock (being an Object)
Acquiring locks works through
“synchronized” blocks/methods
Can “temporarily release” the lock by calling
wait() or wait(ms)
Can wake up waiting threads by calling
notify() or notifyAll()
Synchronized blocks control atomicity
method




Objects represent a state and procedures over
it
Every Thread represents the state of a single
activity touching different objects
Synchronized block ensures thread-local cache
flush/reload
Volatile keyword ensures per-variable cache
flush/reload




Stateless objects – comprise mainly of
methods
Immutable objects – state never changes after
creation
Atomic objects – legal-to-legal state changes
only
Locking – exclusive access on state change


Make sure that a user always sees a legal state
(never sees a temporary state)
Make sure that you have only legal->legal
transitions







Java doesn’t guarantee fairness
Locks are reentrant
Wrong order of acquiring nested monitors
leads to deadlock
Once deadlocked – threads will hang forever
On wait(ms) you dunno whether it was a
notify() call or timeout that happened
Thread scheduling provides no guarantees
Lock contention is a scalability blocker



CAS stands for Compare-and-Swap
Atomic instruction at CPU level (cmpxchg,
load and reserve, store conditional, etc.).
Since Java SE 5 – adopted in Java to allowing
concurrent structures to be implemented.
Old
value
=
?
Ignore
Set it


Setting a reference to an existing object is an
atomic operation
Object construction is not an atomic
operation!



Too low level – hard to implement high level
structures (like latch, rendezvous and barrier)
Can’t pass a lock between threads
Can’t attach a lock to an Object while no
thread is working with it




Lock contention – too many threads/CPUs
Multiple-request data changes
Fine-grained locking
Keeping a lock without wasting a thread

The java.util.concurrent package aims to do
for concurrency what java.util.Collections did
for data structures. It makes
◦
◦
◦
◦



Some
Some
Some
Some
problems go away
problems trivial to solve by everyone
problems easier to solve by concurrent programmers
problems possible to solve by experts
Whenever you are about to use...
Object.wait, notify, notifyAll, synchronized, new
Thread();
Check first if there is a class that ...
◦ automates what you are trying to do, or
◦ would be a simpler starting point for your own solution



java.util.concurrent is based on over 3
years experience with
edu.oswego.cs.dl.util.concurrent
Many refactorings and functionality
improvements
Additional native/JVM support
◦ Timing, atomics, built-in monitor extensions







Executors, Thread pools, and Futures
Queues and blocking queues
Timing
Locks and Conditions
Synchronizers: Semaphores, Barriers, etc
Atomic variables
Miscellany

Flexibility at expense of verbosity
lock.lock();
try {
action();
}
finally {
lock.unlock();
}

Overcomes limitations of synchronized
◦
◦
◦
◦
Doesn’t force block structured locking/unlocking
Allow interruptible lock acquisition and “try lock”
Can define customized implementations
Fair/Unfair
interface Lock {
void lock();
void lockInterruptibly() throws IE;
boolean trylock();
boolean trylock(long timeout,
TimeUnit unit)throws IE;
void unlock();
Condition newCondition();
}

Concrete ReentrantLock implementation
◦ Fast, scalable with synchronized block semantics,
and additional query methods
◦ Also FairReentrantLock subclass with slower but
more predictable first-in-first-out arbitration
class ParticleUsingLock {
private int x, y;
private final Random rng = new Random();
private final Lock lock = new ReentrantLock();
public void move() throws InterruptedException {
lock.lockInterruptibly(); // allow cancellation
try {
x += rng.nextInt(3) - 1;
y += rng.nextInt(3) – 1;
}
finally { lock.unlock(); }
}
public void draw(Graphics g) {
int lx, ly;
lock.lock(); // no interrupts – AWT Event Thread
try {
lx = x; ly = y;
}
finally { lock.unlock(); }
g.drawRect(lx, ly, 10, 10);
} }
interface ReadWriteLock {
Lock readLock();
Lock writeLock();
}

A pair of locks for enforcing multiple-reader,
single-writer access
◦ Each used in the same way as ordinary locks

Concrete ReentrantReadWriteLock
◦ Almost always the best choice for apps
◦ Each lock acts like a reentrant lock


Remember Lock.newCondition(); ?
Condition factors out the Object monitor
methods (wait, notify and notifyAll)
◦ into distinct objects to give the effect of having
multiple wait-sets per object
◦ can combine them with the use of arbitrary Lock
implementations.

Where a Lock replaces the use of
synchronized methods and statements, a
Condition replaces the use of the Object
monitor methods.
interface Condition {
void await() throws IE;
void awaitUninterruptibly();
long awaitNanos(long nanos) throws IE;
boolean awaitUntil(Date deadline) throws IE;
void signal();
void signalAll();
}

Allows more than one wait condition per
object
◦ Even for built-in locks, via Locks utility class

Allows much simpler implementation of some
classic concurrent designs
Example

A small collection of small classes that:
◦ Provide good solutions to common specialpurpose synchronization problems
◦ Provide better ways of thinking about designs
 But worse ways when they don't naturally apply!
◦ Can be tricky or tedious to write yourself



Semaphore
CountDownLatch
CyclicBarrier

Semaphores can be seen as permit holders
◦
◦
◦
◦
◦

Create with initial number of permits
acquire takes a permit, waiting if necessary
release adds a permit
But no actual permits change hands.
Semaphore just maintains the current count.
Can use for both “locking” and “synchronizing”
◦
◦
◦
◦
With initial permits=1, can serve as a lock
Useful in buffers, resource controllers
Use in designs prone to missed signals
Semaphores “remember” past signals



A synchronization aid that allows one or more
threads to wait until a set of operations being
performed in other threads completes.
A CountDownLatch is initialized with a given
count
The await methods block until the current
count reaches zero due to invocations of the
countDown method, after which all waiting
threads are released and any subsequent
invocations of await return immediately. This
is a one-shot phenomenon -- the count
cannot be reset.
class Driver { // ...
void main(int N) throws InterruptedException {
final CountDownLatch startSignal = new CountDownLatch(1);
final CountDownLatch doneSignal = new CountDownLatch(N);
for (int i = 0; i < N; ++i) // Make threads
new Thread() {
public void run() {
try {
startSignal.wait();
doWork();
doneSignal.countDown();
}
catch(InterruptedException ie) {}
}}.start();
initialize();
startSignal.countDown(); // Let all threads proceed
doSomethingElse();
doneSignal.await();
// Wait for all to complete
cleanup();
}
}
Example
j.u.c.atomic contains classes representing
scalars supporting "CAS“
boolean compareAndSet(expectedV, newV)

◦ Atomically set to newV if holding expectedV
◦ Always used in a loop

Essential for writing efficient code on MPs
◦ Nonblocking data structures, optimistic algorithms,
reducing overhead and contention when updates center on
a single field

JVMs use best construct available on platform
◦ Compare-and-swap, Load-linked/Store-conditional, Locks

j.u.c.a also supplies reflection-based classes that
allow CAS on given volatile fields of other classes
class Random {
// snippets
private AtomicLong seed;
Random(long s) {
seed = new AtomicLong(s); }
long next(){
for(;;) {
long s = seed.get();
long nexts = s * ... + ...;
if (seed.compareAndSet(s,nexts)
return s;
}
}
}


Faster and less contention in programs with a
single Random accessed by many threads
Let’s see java.util.Random



There’s also an AtomicReference class
Why not use that to create a non-blocking
stack?
The idea is the same:
◦ The push() method observes the current top node
◦ constructs a new node to be pushed on the stack
◦ if the topmost node has not changed since the
initial observation, installs the new node
◦ If the CAS fails, it means that another thread has
modified the stack, so the process starts again
Example

The Segments
◦ The maps is split into segments, only they lock


The root link
Retries before resorting to locking – size()


Basic debugging support is added (in jconsole
and thread dumps) to detect deadlocks based
on java.util.concurrent structures
Double-ended deques added

Looking at thread dump (Ctrl+Break)
◦
◦
◦
◦
Locked monitors are noted
Monitors to wait for are shown
Owned synchronizers are listed
Java-level (synchronized) deadlocks are auto detected





These slides are for educational purpose only
In most of the cases synchronized blocks are
sufficient!
Synchronized blocks modes is intentionally
kept simple
java.util.concurrent is hard to debug and
needlessly complex for simple scenarios!
Do not use java.util.concurrent except if you
really HAVE to!
For further questions:
Михаил Стойнов
[email protected]
mihail.stoynov.com/blog
Красимир Семерджиев
[email protected]
Bulgarian Java Users Group
java-bg.org
groups.google.com/group/bg-jug