This summary is based on the course “Parallele Programmierung (ParProg)” at the HSR in Rapperswil. I visited the course in this years spring semester and now I want to make a little summary.
- Parallelism vs. Concurrency
- Multithreading basics
- Monitor Synchronization
- Specific Synchronization Primitives
- Risks of concurrency
We work with Java, but the principles can be transfered to other languages.
Parallelism vs. Concurrency
There are often confusions with the terms ‘Parallelism’ and ‘Concurrency’. This terms actually mean not the same, but they are two aspects of the same principle.
Parallelism basically means the splitting up of a process in simultaneously executable and collaborating sub-processes.
Concurrency means that two processes can start, run, and complete in overlapping time periods. They are independant but they compete for shared resources.
Process vs. Thread
A Process is a heavy weight program instance. Each process has his own address space.
A Thread in contrast is a light weight parallel program instance inside a process. Threads share the same address space.
Create a thread in Java
Implement a thread in java:
Create thread instance:
Start the thread:
A real thread is started only if you call the start() method. The start() method calls the run() method of the thread. If a thread throws an unhandled exception, all other threads are still running.
As an alternative to extend the class Thread, you can implement the Runnable interface.
Shorter with Java 8 Lambda
Ad-Hoc implementation of a 1-Method interface:
Anonymous inner class
With Thread.sleep(milliseconds) you can put a thread in the waiting state. After milliseconds he will go to ready state again.
Thread.yield() forces the thread to release the processor. (forces thread switch)
Thread.join() blocks until the thread is terminated. After a thread is terminated t.isAlive() will be false.
- It’s possible that blocking methods (sleep(), join()) throw an InterruptedException
- Threads can be interrupted from outside: myThread.interrupt()
Threads have to share their address space and heap. They can access same objects and variables. That’s why access to resources have to be synchronized enough, otherwise race conditions are possible. (uncontrolled or wrong interactions between threads)
Methods or code blocks which should be executed by only one thread at one time are called Critical sections. No parallel execution should be possible for this sections. (mutual exclusion)
Java Synchronized Methods
With the synchronized modifier, the body of a method is marked as critical section:
How does synchronized work?
Each object has a lock (monitor lock) and only one thread at a time can have this lock. If a thread enter’s a synchronized block he takes the lock if it’s free. Otherwise he has to wait until the lock gets free.
If you add the synchronized modifier to multiple methods in the class, only one thread can enter one of this methods at one time.
Synchronized Statement Blocks
With synchronized statement blocks you can mark critical sections inside methods. Additionally you can define the Lock-Object explicitly.
In this example we make a monitor lock on this:
The following example …
… is equal to …
Wait & Signal Mechanism
With the Wait & Signal mechanism threads can wait for conditions. Threads can also signal other threads to wake up.
- wait() releases the monitor lock temporary. Thread is inactive until wakeup.
- notify() wakes a specific thread
- notifyAll() wakes all threads which are waiting for entering the monitor
- With multiple conditions
- notifyAll() wakes all threads
- all threads enter monitor one after another
- condition maybe only for one thread fulfilled
- all other threads call wait() again
- context switches
- high synchronization costs
In Java you cannot be sure that you have a FIFO queue, so it’s possible that you have threads which never wake up. (reason to use notifyAll())
Specific Synchronization Primitives
A semaphore is an object with a counter that counts the amount of free resources. With the acquire() method you can get one resource and the counter decrements. release() passes the resource back and the counter increments.
A semaphore with a counter which can only be 0 or 1 is called Binary Semaphore.
By default the semaphore in Java is not fair. If you like a fair semaphore you have to pass an additional parameter to the constructor:
In this case the semaphore uses a FIFO queue.
You can also acquire and release multiple resources:
Lock & Conditions
The Lock & Conditions primitive is basically a monitor with multiple waiting lists for different conditions.
- Lock-Object: Lock for entering monitor
- Condition-Object: Wait & Signal for conditions
- Multiple conditions per lock possible
Mutual exclusion often is not needed for read access but for write access. In this case you can use ReadWrite-Locks.
ReadWriteLocks with conditions: Conditions are supported for WriteLocks only!
Count Down Latch
A count down latch is a synchronization primitive with a counter. This is used if all threads wait for one single condition. When the condition is fulfilled, all threads will work further. The counter can be decremented by threads with the method countDown(). Threads can wait until the counter is zero with the await() method.
Example: All Cars have to wait for the startSignal. And the startSignal must wait until all cars are ready.
Latches can only be used once. You cannot reset the counter. If you need a new synchronization you have to create a new latch.
- A cyclic barrier is a meeting point for a fixed amount of threads. The threads can wait until all other threads arrived. (await())
- The amount of threads must be defined from beginning.
- Cyclic Barrier’s are re-usable
The barrier closes automatically for next round:
- is a generalized cyclic barrier
- participants can register and de-register (effective in next round)
- barrier with information exchange
- special case: 2 participants
- 2 threads meet und exchange objects
- blocks, until other thread calls exchange()
- provides argument x of the other thread
Risks of concurrency
What are possible problems if we have concurrency?
- Race conditions
- Not enough synchronization
- mutual exclusion of threads
- fairness problems
Race conditions leads to unexpected behaviors because multiple threads access shared resources without enough synchronization. There are two different levels of race conditions:
- data races (low-level)
- semantically higher race conditions (high-level)
A program with race conditions is incorrect. There can be errors from time to time, but they are usually very hard to find.
Data races happen if threads access shared variables or objects and there is at least one writing access. (Read-Write, Write-Read, Write-Write)
Semantically higher race conditions
- Critical sections not protected
- Low-Level data races eliminated with synchronization
- But not big enough synchronized blocks
Should we synchronize everything?
It does not help if we just synchronize all methods. There can be semantically higher race conditions anyway and the synchronization is very expensive. (costs)
When isn’t synchronization needed?
- Objects with read access only and final variables
- Object belongs only to one thread
- all variables are final
- methods with read access only
- after constructor object can be used without synchronization (at least in java)
Structure guarantees that object is only accessed by one thread at same time.
- Thread confinement
- Object is referenced from one thread
- Object confinement
- Object is encapsulated in an already synchronized object
What means thread safety?
- classes / methods which are synchronized internally
- no data races
- critical sections only inside methods
- Semantically higher race conditions still possible
- other concurrency problems possible
- There is no clear definition of this term
Java collections and thread safety
Old java collections (Java 1.0) like Vector, Stack, Hashtable are threadsafe. Modern collections (java.util > 1.0) like HashSet, TreeSet, ArrayList, LinkedList, HashMap or TreeMap are not threadsafe. If you need concurrent collections, use classes in java.util.concurrent. (ConcurrentHashMap, ConcurrentLinkedQueue, CopyOnWriteArrayList, …)
Why are the modern collections in java.util not threadsafe anymore?
- often synchronization isn’t needed => confinement
- synchronization is mostly insufficient => elements not synchronized
- old java 1.0 collections are historically threadsafe (backward compatibility)
It’s also possible to use wrappers which synchronizes all methods. The elements are still not synchronized! (available for List, Set, Collection, SortedList, SortedSet)
Iterating with concurrency
Iteration of a synchronized collection is not synchronized completely. Only single accesses are synchronized. It’s still possible that another thread changes the collection parallel to your iteration. (semantically higher race conditions)
Nested locks can lead to deadlocks. Example:
What’s the problem here? In the worst case, thread 2 will lock listB directly after thread 1 locked listA. That scenario will block both threads because thread 1 is waiting for listB and thread 1 for listA.
Programs with potential Deadlocks are incorrect:
- threads can block each other
- errors can happen sporadically
- difficult to find through tests
Special case: Livelocks
If threads block each other permanently but still use CPU, this is called livelock. Example:
Starvation means that a thread never gets a chance to access a resource.
- while the resource again and again gets free (it’s always another thread which gets it)
- other threads overtake him
Starvation is a liveness / fairness problem:
- threads have to wait for undefined time
- exceptions can happen sporadically, or not
- very hard to find through tests
How to avoid starvation?
- use fair synchronization constructs
- give threads which had to wait longer more priority
- enable fairness in Java Semaphore’s, Lock & Condition and Read-Write-Lock’s
- Remember: Java Monitor has fairness problems and is very susceptible to starvation
- Starvation is also possible if you set thread priority
- HSR: Module ‘Parallele Programmierung’ (ParProg)