CE303 Lecture 2
PART I
Introduction
Concurrent Systems
A system is concurrent if some of its activities can occur simultaneously
“at the same time”
execution of activities can overlap
Concurrent systems are everywhere
human body, university, car, …
Concurrency in computing
physical: distributed systems, multi-processor machines, graphics processor, devices (RAM, I/O, sound card), …
logical: multiple apps/threads running “in parallel” on one device
Concurrency may just be virtual, like when using time slicing to run processes concurrently on a single-core machine
3
Processes and threads
Process is an OS entity corresponding to an app instance
A process, in the simplest terms, is an executing program
Each process has its own address space
Each process’s address space is isolated
OS are usually capable of running several processes
Special mechanisms for processes to communicate: sockets, signals, remote method invocation, …
Processes and threads
Thread is an OS entity corresponding to a stream of instructions
One or more threads run in the context of the process
Each thread belongs to exactly one process and uses its address space
Each process has at least one thread (think of the main function)
A thread can execute any part of the process code, including parts currently being executed by another thread.
OS support of parallelism
OS will run all the threads ‘in parallel’
What if there are more threads than CPU cores?
OS uses time slicing to run several threads concurrently on a single core
Switching processes is expensive (because it involves address space switching)
Switching threads is cheaper
Allocation of computing resources (i.e. CPU time) is controlled by process and thread priorities
time
Image Source: http://web.mit.edu/6.031/www/fa17/classes/19-concurrency/
On most systems, time slicing happens unpredictably and non-deterministically, meaning that a thread may be paused or resumed at any time.
6
Operating System Processes
Modern OS like Unix or Windows support multiple processes (“multitasking”)
java MyProg creates a new process
Each process has an independent address space: processes do not share variables
Managed by the operating system
OS ensures processes do not interfere (“isolated”)
need special mechanisms for communication like signals, sockets, remote method invocation
Switching processes is relatively slow
requires a lot of copying and loading
7
(Java) Threads
“Lightweight” concurrent processing
Each thread is an independent flow of control with its own local variables
A process can have many threads
Threads can share some part of the address space
In Java, this means that there may be shared objects that can be accessed from different threads
Java threads are managed by JVM
scheduler activates/ deactivates threads
Each Java program starts with one thread: main()
Switching threads is relatively fast
8
Shared Memory
Each thread has its own context
Stack: local variables, call stack
CPU registers including the program counter pc
Any items on the heap are potentially shared
…
pc=…
…
pc=…
…
pc=…
…
Not shared:
locals and
registers
Shared:
objects and
static fields
END OF PART I
PART II
Threads in Java
Defining and Running a New Thread in Java
Define a class that implements Runnable
Runnable has only one method: void run()
This method defines what the thread should do, similar to the main() method; the thread terminates when run() exits
Construct an object of this class
Construct a thread from the object
Start thread
Alternatively, use a lambda expression
Alternatively, obtain a Thread object by extending class Thread and override run()
This approach can save some lines of code
Disadvantage: can not inherit from other classes (as you’ve already extended Thread)
12
public class Greeter implements Runnable {
private String greeting;
private static final int REPETITIONS = 8;
private static final int DELAY = 100;
public Greeter(String aGreeting) { greeting = aGreeting; }
public void run() {
try {
for (int i = 1; i <= REPETITIONS; i++) {
System.out.println(i + ": " + greeting);
Thread.sleep(DELAY);
}
} catch (InterruptedException exception) {}
}
public static void main(String[] args) { … }
Concurrent Greeter Threads (Java, slide 1)
13
Concurrent Greeter Threads (Java, slide 2)
public static void main(String[] args) {
Runnable r1 = new Greeter("Hello, World!");
Runnable r2 = new Greeter("Goodbye, World!");
Thread t1 = new Thread(r1);
Thread t2 = new Thread(r2);
t1.start();
t2.start();
}
Thread.start() returns immediately after launching the thread – it does not wait for it to finish.
Question: What would happen if main called r1.run() and r2.run() instead of starting new threads?
14
Greeter Threads: Two Sample Program Runs
Run 1
1: Hello!
1: Goodbye!
2: Hello!
2: Goodbye!
3: Hello!
3: Goodbye!
4: Hello!
4: Goodbye!
5: Hello!
5: Goodbye!
6: Hello!
6: Goodbye!
7: Hello!
7: Goodbye!
8: Goodbye!
8: Hello!
Run 2
1: Hello!
1: Goodbye!
2: Hello!
2: Goodbye!
3: Goodbye!
3: Hello!
4: Hello!
4: Goodbye!
5: Goodbye!
5: Hello!
6: Hello!
6: Goodbye!
7: Goodbye!
7: Hello!
8: Hello!
8: Goodbye!
15
Thread state diagram
New
Runnable
Dead
Blocked
Started
Finished or terminated
Suspended,
entered sleeping,
acquiring lock,
waiting for another thread
Resumed,
sleeping finished,
acquired lock,
another thread finished
Java and C# define more states, e.g., they have variations of the Blocked state
16
Thread states
Each thread has a state
Once created, a thread needs to be started
Thread runs until its main method exits or it is terminated
When a thread runs, it switches between the runnable and blocked states
Runnable means actually running the code (utilising CPU)
Blocked means waiting for something
In real life, a typical thread spends most of the time in the blocked state
Waiting for user input
Waiting for I/O
Waiting to acquire some shared resource
Sleeping
Etc.
17
Thread scheduling
JVM and .NET Framework include thread schedulers – usually only wrappers for the functionality of the operating system
Scheduler de-activates a thread if
run() exits
the thread calls yield() – voluntarily give up CPU resource
the thread is blocked (waits for something)
OS decides to switch to another thread (time slicing)
Scheduler looks only at the runnable threads
prefers threads with higher priority, also aging schemes
Scheduler is likely to activate a blocked thread immediately after it being unblocked – better than using timers and check periodically some variable’s state
Blocked thread consumes very little computational resources
18
It is the resposibility of the OS (or the JVM in Java) to switch the context based on underlying operating system and memory model.
We can write code to control the scheduling of the threads
More info about scheduling: https://www.tutorialandexample.com/thread-scheduler-in-java/
Terminating threads
Thread terminates when run() exits
If you want to tell a thread to terminate, you can inform it by calling Thread.interrupt()
this will set a boolean field in the Thread data structure
A thread should check regularly if it is meant to stop
call isInterrupt() or
perform sleep or wait, and catch InterruptedException
You can also use shared variable(s) to communicate that a thread should stop
Method isAlive() returns true if a thread has been started but it has not terminated yet
Threads are not re-startable
19
Typical Structure: Runnable with Loop
public class MyRunnable implements Runnable {
public void run() {
try {
while (…) {
doWork();
Thread.sleep(…);
}
}
catch (InterruptedException e) { … }
}
}
20
END OF PART II
PART III
Synchronisation
Concurrency: Interleaving
Consider threads t1, t2 with run() methods consisting of two statements each:
t1: public void run() {a; b}
t2: public void run() {c; d}
Assume execution of individual statements is “atomic” and “mutually exclusive”
Can a be executed before c?
Can a be executed after d?
Execution of t1 and t2 is “interleaved”
All you know is “a before b” and “c before d”
even that could be wrong due to compiler optimisations
23
public class CounterThread extends Thread
{
static int TOTAL = 0;
static int REPETITIONS = 1000;
public CounterThread() {
this.start();
}
public static void inc() {
TOTAL++;
}
@Override
public void run() {
for (int i = 0; i < REPETITIONS; i++)
inc();
}
public static void main(String[] args) throws Exception{
Thread t1 = new CounterThread();
System.out.println("Total = " + TOTAL);
}
}
CounterThread (Java, slide 1)
What is the TOTAL value going to be when we print it?
24
CounterThread
It’s not necessarily 1000!!!
The main method is also running on one thread
This is the default main thread in Java created by the JVM
When our thread t1 is inside the loop counting the values between 0 and 1000, the main thread does not wait
Thus it prints the value of TOTAL at that instance
public static void main(String[] args) throws Exception
{
Thread t1 = new CounterThread();
t1.join();
System.out.println("Total = " + TOTAL);
}
}
CounterThread (Java, slide 2)
The TOTAL now would be 1000, as expected!
26
Thread Method join()
t.join() waits for thread t to terminate before proceeding
t.join(maxTime) waits at most for maxTime (in ms)
This is useful when a parent thread creates one or more child threads to do some work
Parent thread waits for answers before proceeding
Also useful if you want to calculate how long it took until a started thread has finished
In our example, it is needed in CounterThread.main() to ensure that it prints the total after the t1 thread has finished
27
public static void main(String[] args) throws Exception
{
Thread t1 = new CounterThread();
Thread t2 = new CounterThread();
t1.join();
t2.join();
System.out.println("Total = " + TOTAL);
}
}
CounterThread (Java, slide 3)
What is the TOTAL value going to be when we print it?
28
Results from Running CounterThread
Run 1:
total = 2000
Run 2:
total = 2000
Run 3:
total = 1743
Run 4:
total = 2000
Run 5:
total = 1209
29
Thread Interleaving – CounterThread
Thread t1.inc()
Thread t2.inc()
total++
total++
fetch total
return
fetch total
return
total
0
0
1
1
1
1
30
Race Conditions in Threads
When two or more concurrent threads access a common variable – potential trouble!
problem caused by interleaved reading and writing of shared objects, reading on its own is ok
sometimes called race conditions as result depends on who gets access first
Missing atomicity of statements
a thread can yield control half-way through updating a shared object, leaving it in an inconsistent state
Leads to very bad kind of programming errors
program works “nearly always”
Java solution: synchronisation and locks
31
Synchronised Methods and Locks
Java offers synchronized methods
“mutual exclusion” for critical code
public synchronized void myMethod (…) {…}
Each Java object has a built-in “monitor lock”
when a synchronised method is started, it needs to obtain the lock of the object to which it is applied
this stops more than one synchronized method to be applied to this object at the same time.
A static synchronized method locks the class object
Java also has an interface Lock and several implementing classes including ReentrantLock
explicit lock()/unlock() methods
good for coding more sophisticated locking behaviour
32
Visualizing Locks
Object = phone booth
Thread = person
Locked object = closed booth
Blocked threads =
people waiting for booth to open
Monitor/lock = ensures at most one
person is in the booth at any time
33
Source: [Horstmann OOP&D]
Synchronized CounterThread
Change inc() declaration to:
public static synchronized void inc() { … }
Now the value of total is always the same as the
overall number of invocations of method inc():
Run 1:
total = 2000
Run 2:
total = 2000
Run 3:
total = 2000
34
CounterThread: Which Object is Locked?
Method inc() is static. This means that the lock is on the CounterThread.class object
There is only one of these in the JVM
so at most one thread can carry out method inc() at any point in time
Warning: if method inc() was not static, the program above would synchronise on instances of class CounterThread
This would mean, there would be two locks,
one for thread t1 and one for thread t2
Thus there would be no contention for the locks, and no protection against concurrent modification of total
For more information, see:
http://tutorials.jenkov.com/java-concurrency/synchronized.html
35
There can of course be cases that we don’t want to synchronize a static method. E.g., imagine we only have a single object instance, and we want to parallelize a method of this class. Then it does not need to be static.
CounterThread Synchronized
Thread t1.inc()
Thread t2.inc()
total++
total++
fetch total
return
fetch total
return
total
0
0
1
1
2
2
36
Block Synchronization
Can also synchronise a block of code by associating it explicitly with an object that gets locked / unlocked
Suppose we have two bank account objects
use synchronisation to avoid interference when transferring money from one account to another
synchronized (account1) {
synchronized (account2) {
account1.transfer( -amount );
account2.transfer( amount );
}
}
37
To synchronize a single variable, we can use AtomicReference, see the example with AtomicInteger a few slides later.
Remarks about synchronized
CounterThread is correct after adding synchronized
We have made method inc() “atomic”, so two calls of this method can no longer overlap
But: the code is a LOT slower than the incorrect, unsynchronised version, up to a factor ~100 during testing
Only use synchronisation when necessary
When you do need it, be sure to use it!
38
Threads in C#
C# API for handling threads is mainly similar to that in Java
C# neatly uses delegates to create threads – functionality unavailable in Java
When creating a thread, you specify which method it will run
C# supports synchronized blocks (it uses keyword lock instead)
C# does not have synchronized methods
Greeter in C# (slide 1)
public class Greeter
{
private readonly String greeting;
private static readonly int repetitions = 8;
private static readonly int delay = 100;
public Greeter(string greeting)
{
this.greeting = greeting;
}
public void Run()
{
for (int i = 1; i <= repetitions; i++)
{
Console.WriteLine(i + ": " + greeting);
Thread.Sleep(delay);
}
}
}
Greeter in C# (slide 2)
class Program
{
static void Main(string[] args)
{
Greeter g1 = new Greeter("Hello, World!");
Greeter g2 = new Greeter("Goodbuy, World!");
Thread t1 = new Thread(g1.Run);
Thread t2 = new Thread(g2.Run);
t1.Start();
t2.Start();
t1.Join();
t2.Join();
}
}
CounterThread in C# (slide 1)
class Program
{
static void Main(string[] args)
{
var t1 = new Thread(Run);
var t2 = new Thread(Run);
t1.Start();
t2.Start();
t1.Join();
t2.Join();
Console.WriteLine(total);
}
…
CounterThread in C# (slide 2)
…
static int total = 0;
const int repetitions = 1000;
private static object sync = new object();
public static void Inc()
{
lock (sync)
total++;
}
public static void Run()
{
for (int i = 0; i < repetitions; i++)
Inc();
}
}
More efficient synchronisation: AtomicInteger (Java)
The object stores a single integer
Provides synchronised functionality with integers
int getAndIncrement() equivalent to value++
int addAndGet(int delta) equivalent to
value += delta
int getAndSet(int newValue) sets the value and returns the old value
All operations are thread safe
Much faster then using synchronized methods / blocks
Where possible, exploits platform-specific instructions
Most CPUs (e.g. x86 since 80486) support this on the hardware level
Interlocked (C#)
Interlocked class gives access to the same functionality, i.e. enables efficient atomic operations with integers
As C# has call-by-reference, you don’t need to create special objects – you use static methods of class Interlocked:
public static void Inc()
{
Interlocked.Increment(ref total);
}
If you were not using call-by-reference, then we’d have the relevant variable sitting outside the method, and then we’d need to lock it in a different way, such as creating an object and lock it, like we did in Java.
45
END OF PART III
PART IV
Deadlocks
Dining Philosophers
48
Deadlock (“Starvation”)
Dining philosophers example:
philosophers sit at a round table
eat spaghetti with two forks
assume a philosopher first picks up fork to the right, then picks up fork to the left, then eats, then drops forks
what if everyone picks up fork to their right immediately?
Deadlock situation can arise whenever you have at least two threads and two locks (think of only 2 philosophers and 2 forks):
Thread (Philosopher) 1 acquires lock on object (fork) A
Thread (Philosopher) 2 acquires lock on object (fork) B
Thread (Philosopher) 1 waits for lock on object (fork) B
Thread (Philosopher) 2 waits for lock on object (fork) A
Deadlock avoidance
programs need to ensure deadlocks are impossible
49
Coarse-grained Concurrency
Res. 1
Res. 2
Res. 3
Res. n
Uses a single lock for an entire set of resource objects (indicated by the "orange border" in the image)
When one thread has acquired the lock, it stops all others threads from accessing any of the objects in the set
No danger of deadlock
Potentially inefficient as it may cause unnecessary blocking of threads
50
Fine-grained Concurrency
A separate lock for each resource
A thread acquires locks for those objects involved in the current transaction.
Potentially more efficient than a more coarse-grained strategy
less blocking of threads
actual gain depends on various factors such as processor cores, etc.
Danger of deadlock if threads need to acquire (and return) multiple locks for a transaction
Res. 1
Res. 2
Res. 3
Res. n
51
Coarse-Grained Dining Philosophers
Implementing a coarse-grained solution for the dining philosophers is straightforward
The synchronisation is done on the entire set of forks
So at most one philosopher can access the forks
This prevents deadlock
But it makes for slow eating
If we interpret the philosophers as processors and eating as “doing work”, then at most one processor is actually working at any point in time
52
public abstract class Philosopher implements Runnable {
static class Fork {
int holder;
Fork(int holder) { this.holder = holder; }
}
final static int COUNT = 5;
final static Fork[] forks = new Fork[COUNT];
static {
for (int i = 0; i < COUNT; i++)
forks[i] = new Fork(-1);
}
int id;
Philosopher(int id) { this.id = id; }
public abstract void run();
public void takeFork(int i) {…}
public void dropFork(int i) {…}
public void eat() {…}
}
53
public class PhilosopherCoarse extends Philosopher {
public PhilosopherCoarse(int id) {
super(id);
}
@Override
public void run() {
int fst = id;
int snd = (id + 1) % COUNT;
synchronized (forks) {
takeFork(fst);
takeFork(snd);
eat();
dropFork(snd);
dropFork(fst);
}
}
}
54
Program Output: PhilosopherCoarse
Philosopher 0 takes fork 0
Philosopher 0 takes fork 1
Philosopher 0 is eating...
Philosopher 0 drops fork 1
Philosopher 0 drops fork 0
Philosopher 9 takes fork 9
Philosopher 9 takes fork 0
Philosopher 9 is eating...
Philosopher 9 drops fork 0
Philosopher 9 drops fork 9
Philosopher 7 takes fork 7
...
duration = 5053 ms
Fine-grained Dinging Philosophers
Lock only the forks needed by each philosopher
the synchronisation ensures that no two philosophers can pick up one fork at the same time
BUT: need to be careful about how we request the locks
Otherwise, could end up in a state of deadlock
Simple deadlock-avoidance strategy: restrict order of requests:
first philosopher takes right fork first, then left fork;
all other philosophers take left fork first, then right fork
Other deadlock-avoidance strategies are possible
56
public class PhilosopherFine extends Philosopher {
public PhilosopherFine(int id) { super(id); }
@Override
public void run() {
// Deadlock prevention
int fst = (id == 0 ? id : (id + 1) % COUNT);
int snd = (id == 0 ? 1 : id);
synchronized (forks[fst]) {
takeFork(fst);
synchronized (forks[snd]) {
takeFork(snd);
eat();
dropFork(snd);
}
dropFork(fst);
}
}
}
57
Program Output: PhilosopherFine
Philosopher 0 takes fork 0
Philosopher 2 takes fork 3
Philosopher 1 takes fork 2
Philosopher 0 takes fork 1
Philosopher 3 takes fork 4
Philosopher 0 is eating...
Philosopher 5 takes fork 6
Philosopher 5 takes fork 5
Philosopher 5 is eating...
Philosopher 6 takes fork 7
Philosopher 7 takes fork 8
Philosopher 8 takes fork 9
...
duration = 2543 ms
END OF PART IV
PART V
More advanced synchronisation
Synchronisation primitives
Synchronized/lock sections have very limited functionality
There exist multiple synchronisation primitives (tools) including
Mutex allows at most one thread at a time to access some resource
Semaphore allows at most n threads at a time to access some resource
Barrier synchronises several threads; a thread will wait until all other threads complete some task
61
Cyclic Barriers
CyclicBarrier in Java (Barrier in C#) allows a fixed number of threads to wait for each other at some common barrier point
CyclicBarrier.await() blocks until that has happened
Called “cyclic” because the barrier can be re-used after waiting threads have been released
Cyclic barrier can be set up with a barrier action that is executed once per barrier point, after the last thread in the party arrives, but before any threads are released.
Java example: CyclicBarrierDemo
62
public class CyclicBarrierDemo {
final static int COUNT = 3; final static int REPEATS = 3;
final static CyclicBarrier cb = new CyclicBarrier(COUNT,
() -> System.out.println(“All done”));
static class Task implements Runnable {
int id;
Task(int id) { this.id = id; }
public void run() {
for (int i = 0; i < REPEATS; i++) {
System.out.println("Thread " + id + " done");
try { cb.await(); } catch (Exception e) {}
}
}
}
public static void main(String[] args) {
for (int i = 0; i < COUNT; i++)
new Thread(new Task(i)).start();
}
}
COUNT refers to the number of threads
REPEATS to the number of iterations
63
CyclicBarrierDemo Output
Thread 0 done
Thread 2 done
Thread 1 done
All done
Thread 1 done
Thread 2 done
Thread 0 done
All done
Thread 2 done
Thread 0 done
Thread 1 done
All done
Concurrency in GUI
GUI libraries usually do not support concurrency
The entire GUI is supposed to operate from a single thread
Events such as user interactions, system updates and timers are added to a queue and then processed one by one
Trying to access GUI from another thread will cause problems
Having a lengthy operation in a GUI application will lead to GUI freezing
Concurrency in GUI – solutions
Do the long operation in another thread; use special function to update the GUI once the operation is finished
C#: Control.Invoke()
Java: EventQueue.invokeLater()
(A variation of the previous approach) Use a special class for lengthy operations
C#: BackgroundWorker
Java: SwingWorker
Multi-Threaded Servers (“Concurrency”)
Many applications have to deal with “real world” concurrency
Like multiple users who may issue task requests concurrently and non-deterministically
Threads can help to code such server applications
Run a separate thread for each concurrent interaction
Servers are often built on top of a standardised multi-threaded environment such as a servlet container like Tomcat
Server threads may be blocked a lot of the time, because they are waiting for the next request
During waiting times, they do not actually use up CPU time
Often requires some access control for shared resources
Such as a database
67
Parallel Programming (“Parallelism”)
Parallel programming tries to divide a computation-intensive task into sub-tasks and execute these at the same time
Can be coded for multi-core or distributed machines
Parallelisation requires a careful breakdown into sub-tasks and allocation over different cores / processors / machines
Try to reduce idle (waiting) times
Not every algorithm can be efficiently parallelised
Communication and memory access are often the bottlenecks
Simply increasing the number of CPUs does not necessarily improve the performance
In fact, overheads may even worsen the performance
68
Summary
Java and C# fully support multi-threaded programming
Synchronised methods, synchronised blocks (Java) and locks (C#) can be used to control access to shared objects
Choice of synchronisation (locking) strategy
coarse-grained concurrency is simpler, less danger of deadlock, potentially poorer performance
fine-grained concurrency is more complex, needs more care to avoid deadlocks, potentially better performance
Barriers and semaphores can help to coordinate the progress of different threads
GUI: use special classes to execute background tasks
Multi-threaded servers versus parallel programming
69
END OF LECTURE