PowerPoint Presentation
Computer Systems
Concurrency & Threads
Slide #2 of 35
A view of an operating System
Slide #3 of 35
What does this imply?
Multiple ‘users’
Working independently
The operating system:
Protects memory from interference from other processes
Interleaves execution of each process to:
Maximise resource utilisation
Responsiveness of each process
Preserves the states of each process so it can
resume execution
Slide #4 of 35
Historically ….
Computers were expensive:
Maximise utilisation
Now:
Users expect concurrent execution of multiple tasks
Stream music
Update software
Edit file
Test program
Monitor SNS
Etc.
Slide #5 of 35
So?
The problem is that these processes do not always work
independently:
They can compete for access to resources:
Devices, files, data etc. that are local (or remote)
They can co-operate – through messages, shared memory,
files etc.
Applications are distributed:
So, potentially, millions of people are reading or updating
information at the same time
SNS, bank accounts, on line shopping ….
Slide #6 of 35
And …
We need to build applications that can interleave multiple independent
(but potentially conflicting) tasks:
Consider an app with a GUI:
do we want it to freeze when it is performing some time
consuming task?
What about a database of bank accounts?
Do we want to wait in a queue to perform a transaction?
What about programmers’ efficiency & effectiveness?
Do we want them to have to ‘build an OS’ for every app?
What about the effectiveness of use of our computing resources?
We want to maximise the efficiency
Slide #7 of 35
This leads us to two things:
How can we manage concurrency?
How can we ensure that our concurrent execution
behaves correctly?
How can we do this conveniently?
How can we do this efficiently?
To maintain responsiveness
How can we provide programming mechanisms within
a program to allow concurrency?
Threads
Slide #8 of 35
Let’s think about a bank transfer
Find Balance
Acc1
Subtract
transfer
Store new
value
Find Balance
Acc2
Add
transfer
Store new
value
Find Balance
Acc1
Store new
value
Subtract
Transfer
Find Balance
Acc2
Store new
value
Subtract
Transfer
This is unlikely:
• but possible!
• and hard to debug!
Slide #9 of 35
Concurrency
Introduction to Concurrency
OS Concerns and Process Interaction
Process Synchronization
Critical Section Problem
Requirements for Solutions to CS Problem
Software Solutions
Hardware Solutions
High Level OS Support
Slide #10 of 35
Multiple Processes
Operating System design is concerned with the
management of processes and threads
Multiprogramming (Multitasking)
Multiprocessing
Distributed Processing
Slide #11 of 35
Concurrency in Different Contexts
Slide #12 of 35
Concurrency: Key Terms
Slide #13 of 35
Principles of Concurrency
Interleaving and Overlapping
Can be viewed as examples of concurrent processing
Both present the same problems
Uniprocessor – the relative timing of execution of
processes cannot be predicted:
Depends on activities of other processes
The way the OS handles interrupts
Scheduling policies of the OS
Slide #14 of 35
Difficulties of Concurrency
Sharing of global resources
Difficult for the OS to manage the allocation of
resources optimally
Coordination of ‘parallel’ and asynchronous ‘processes’
Ensuring correct behaviour
Debugging of programming errors:
behaviour can be non-deterministic and,
therefore, hard to identify and reproduce
Slide #15 of 35
Operating System Concerns
Design and management issues raised by the
existence of concurrency:
The OS must:
• be able to keep track of various processes
• allocate and de-allocate resources for each active
process
• protect the data and physical resources of each process
against interference by other processes
• ensure that the processes and outputs are independent
of the processing speed
Slide #16 of 35
Process Interaction
Slide #17 of 35
Resource Competition
Concurrent processes come into conflict when they are
competing for use of the same resource
for example: I/O devices, memory, processor time, clock
In the case of competing processes three control
problems must be faced:
Mutual Exclusion – to ensure correct behaviour
Deadlocks
Starvation
Slide #18 of 35
Synchronization of Processes – Example
We expect
When process1 finishes, shared variable x is reduced by 5
When process2 finishes, shared variable x is increased by 2
Slide #19 of 35
Synchronization of Processes – Example
Context switches may occur at any time
Process 2 has its result overwritten by process 1
Process 1 operates with outdated information
Slide #20 of 35
What is a Race Condition?
Occurs when multiple processes or threads read
and write shared data items
The processes “race” to perform their read /write
actions
The final result depends on the order of execution
The “loser” of the race is the process that performs the
last update and determines the final value of a shared
data item
Slide #21 of 35
Why do Race Conditions Occur?
Order of Execution: Whenever the state of a
shared resource depends on the precise execution
order of the processes
Scheduling: Context switches at arbitrary times
during execution
Outdated Information: Processes / Threads
operate with Stale or Dirty copies of memory values
in registers / local variables
Other processes may already have changed the original
value in the shared memory location
How can we avoid race conditions?
Slide #22 of 35
Critical Section
Part of the program code that accesses a shared resource
In order to avoid race conditions, we have to control the
concurrent execution of the critical sections
Strict Serialization i.e. Mutual Exclusion
Slide #23 of 35
Critical Section
Entry Protocol
Process requests permission for entering a critical
section; May have to wait / suspended until entry is granted
Process has to communicate that it entered critical section
Exit Protocol
Process communicates to other processes that it has left
the critical section
Slide #24 of 35
Critical Section / Mutual Exclusion
Important: A process can finish the execution of it’s critical
section, even if it is preempted or interrupted.
Slide #25 of 35
Deadlock and Starvation
Enforcing mutual exclusion creates two new problems
Deadlocks – Processes wait forever for each other to free
resources
Starvation – A Process waits forever to be allowed to enter
its critical section
Implementing mutual exclusion has to account for these
problems!
Slide #26 of 35
Requirements for Solutions to the
Critical Section Problem
1) Serialization of Access: Only one process at a time is
allowed in the critical section for a resource
2) Bounded Waiting (No Starvation):
A process waiting to enter a critical section, must be
guaranteed entry (within some defined limited waiting time)
Scheduling algorithm has to guarantee that process is
eventually scheduled and can progress
Slide #27 of 35
Requirements for Solutions to the
Critical Section Problem (cont’d)
3) Progress (Liveness, No Deadlock)
A process that halts in its noncritical section must do so
without interfering with other processes currently waiting to
enter their critical section
Only processes currently waiting to enter their critical section
are involved in the selection of the one process that may
enter
A process remains inside its critical section for a finite time
only
Slide #28 of 35
Solutions to the Critical Section Problem
1) Software Solutions
Shared lock variables
Busy Waiting (Polling / Spinning / Strict Alternation)
2) Hardware Solutions
Disabling Interrupts
Special H/W Instructions (like compare & swap)
3) Higher Level OS Constructs
Semaphores, Monitors, Message Passing
Slide #29 of 35
Lock Variables
Critical sections must be
protected by some form of a
“lock”, where a lock is:
A shared data item
Processes have to “acquire”
such a lock before entering a
critical section
Processes have to “release” a
lock when exiting critical section
A lock is also called a Mutex.
Slide #30 of 35
Shared Lock / Mutex
Two State Lock (shared variable)
True = Critical Section Locked, False = Critical Section Unlocked
Problem: As lock variable is itself a shared
resource, race conditions can occur on it!
Slide #31 of 35
Shared Lock – Problem
Solution: Use Atomic Instructions for Shared Lock!
Slide #32 of 35
Busy Waiting (Polling, Spinning)
A process continuously evaluates whether a lock has
become available
Lock is represented by a data item held in shared
memory (IPC via shared memory)
Process consumes CPU cycles without any progress
A process busy waiting may prevent another process
holding the lock from executing and completing its critical
section and from releasing the lock
Spin locks are used at kernel level (special HW
instructions)
Slide #33 of 35
Busy Waiting (Strict Alternation)
Strict alternation between two processes – a process
waits for its turn
Use a “token” as shared variable – usually process ID
indicates which process is the next to enter critical section, set by
previous process
Entry to critical section
Process Pi busy-waits until token == i (its own process ID)
Exit from critical Section
Process Pi sets token to next process ID
Slide #34 of 35
Busy Waiting (Strict Alternation)
Mutual exclusion is guaranteed!
Liveness / Progression problem
Both process depend on a change of the “turn” variable
If one of the processes is held up in its non-critical section, it
cannot do that and will block the other process
Slide #35 of 35
Hardware Solutions – Disabling Interrupts
In uniprocessor systems, concurrent processes cannot
be overlapped, they can only be interleaved.
Disabling interrupts guarantees mutual exclusion!
However, the efficiency of execution could be noticeably
degraded.
This approach will not work in a multiprocessor
architecture
Slide #36 of 35
Special H/W Instructions
Applicable to any number of processes on either
uniprocessor or multiprocessors sharing main memory
Simple and easy to verify
Can be used to support multiple critical sections
Busy-waiting is employed
Starvation and Deadlocks are possible!
Slide #37 of 35
Abstractions
Usually, we build upon abstractions:
The system implements mechanisms correctly and
efficiently and we use these:
Database systems
Java
There are other solutions to these problems that may
be more efficient – in some circumstances
Slide #38 of 35
Summary
What is concurrency and what are OS and Process
concerns w.r.t to concurrency.
We have been introduced to the notion of process
synchronization, its need and the critical section
problem.
We have seen requirements for solutions to the CS
problem i.e. mutual exclusion, progress & bounded
waiting time.
Slide #39 of 55
Threads
What is a thread?
Parallelism vs. Concurrency
Multicore and Multi-threading
Multi-threading Models
Java Threads
Limitations of Threads
Threading Issues
Thread Interference & Memory Consistency
Synchronized Methods and Statements
Slide #40 of 55
From Processes to Threads
Multi-threading is the ability of an OS to support multiple,
concurrent paths of execution within a single process.
Process model
assumed a process was
an executing program
with a single thread of
control
All modern OS’s
provide features
enabling a process to
contain multiple
threads of control
Slide #41 of 55
What is a Thread?
A thread is part of a process
Contains:
Thread ID (TID)
Program Counter (PC)
Register Set
Stack
All threads in the same process, share:
Code section
Data section:
Objects
Open files
Network connections
Etc.
Slide #42 of 55
What is a Thread?
If a process has multiple threads of control, it can
perform more than one task at a time!
Slide #43 of 55
Why Threads?
Most applications are multi-threaded
Application:
Process with several threads of control
Web browser:
Threads for each tab
Threads for each extension/helper
Utility threads
Java Program: main thread + service threads
+ GUI threads
Server Processes
Slide #44 of 55
Multi-threaded Server Architecture
Threads have a critical role in systems which provide
services:
Servers: web servers, database servers ….
When a server receives a message, that request is
serviced using a separate thread:
Slide #45 of 55
Benefits of Threads
Responsiveness: user interaction in a GUI can be responded to by
a separate thread from one running a computationally intense
algorithm.
Resource Sharing: Variables & objects can be shared. This is
especially important for things like network or DB connections.
Economy: “Light-Weight Processes” due to smaller memory
footprint than using multiple processes & efficiency of switching
between threads.
Scalability: Easier to make use of parallel processing in a multi-
threaded processor
Reduce programming complexity: Problems often are better
broken down into independent parallel tasks, rather than having to
build complex mechanisms to interleave their execution.
Slide #46 of 55
Multicore Programming
Multiple processing
elements on a single chip
Multi-threaded
programming:
Allows efficient use of
the multiple processing
elements and improved
parallelism
Slide #47 of 55
Concurrency
On a single Processing element, concurrency means
that the execution of threads will be interleaved over
time.
Only one thread at a time is actually running
Slide #48 of 55
Parallelism
Slide #49 of 55
Parallelism vs Concurrency
A system is parallel if it can perform more than one task
simultaneously
A concurrent system supports more than one task by
allowing all the tasks to make progress.
It is possible to have concurrency without parallelism
This is incredible!
I can do so much
more! There must
be a catch …
Slide #50 of 55
Multicore systems and Multithreading
Performance of software on Multicore systems
Amdahl’s law states that:
(1-f) : Inherently serial code
f : parallelizable code with no scheduling overhead
Slide #51 of 55
Multicore and Multithreading (cont’d)
Amdahl’s law makes the multicore organizations look attractive!
But even a small amount of serial code has noticeable impact on
the overall performance
Example:
10% serial, 90% parallel, 8 CPUs→~4.7x speedup
There are overheads to parallelism:
Memory access
Cache load
Etc.
Slide #52 of 55
Multicore and Multi-threading (cont’d)
Slide #53 of 55
Multicore and Multi-threading (cont’d)
Slide #54 of 55
Parallel Programming Challenges
Pressure placed on system designers and application
programmers to better use multiple cores
System designers must write scheduling algorithms that
use multiple processing core to allow parallel execution
Challenge to modify existing programs
Challenge to design new programs that are
multithreaded
Slide #55 of 55
Parallel Programming Challenges (cont’d)
Identifying tasks: which areas of an application can be
divided into separate, concurrent (and ideally independent)
tasks?
Balance: how do we balance the tasks on the multiple cores
to achieve maximum efficiency?
Data splitting: how can data sets be split for processing in
parallel?
Data dependency: Certain tasks will rely on data from
another. In this case, how do we synchronise the access to
this data?
Testing and debugging: Due to complexities of concurrent
and parallel execution (multiple pathways etc.), how do we
debug such an application?
Slide #56 of 55
Multithreading Models
Threads may either be at the user or kernel thread
level
User threads managed above kernel
Kernel threads are managed directly by the OS
Three types of relationships between user and kernel
threads are possible.
Many-to-One
One-to-One
Many-to-Many
Slide #57 of 55
Many-to-One Model
Maps many user-level threads to one
kernel thread
Thread management done by the
thread library, in user space.
Therefore, efficient!
But, entire process will block if a
thread makes a blocking system call
Only one thread can access kernel at
a time – lacks parallelism on multicore
systems
Not many systems use this due to
inability to take advantage of multiple
cores
Slide #58 of 55
One-to-One Model
Maps each user thread to a kernel thread
Overcomes blocking issue – so more concurrent
Allows for parallelism
But, for each user thread, there has to be a kernel thread
Slide #59 of 55
Many-to-Many Model
A software developer can
create as many user
threads as necessary i.e. a
Thread Pool.
Corresponding kernel
threads can run in parallel
on a multiprocessor
If a thread blocks, kernel
can schedule another for
execution
Slide #60 of 55
How can we use Threads?
Through use of a thread library
POSIX Pthreads (user/kernel level)
Windows (kernel)
Java Threads (on top of Windows/Pthreads)
API for creating and managing threads
Slide #61 of 55
Java Threads
Fundamental model of program execution in a Java
program
Java API provides a rich feature set for the creation and
management of threads
All programs consist of at least a single thread of control
– main()
Java threads available on any system that contains a
JVM
Slide #62 of 35
Warning!
This section does NOT expect you to be able to
program using threads in JAVA:
It is just to give a flavour of what you can do!
Java threads will be covered in semester 2
Slide #63 of 55
Creating a Thread in Java (Method # 1)
Create a new class derived from the Thread class and
over-rides its run() method
public class MyThread extends Thread{
public void run(){
// Code below overrides run()
System.out.println(“My first thread”);
}
Slide #64 of 55
Test for MyThread
Here is an example for testing MyThread
public class TestMyThread {
public static void main(String[] args) {
MyThread t = new MyThread();
t.start();
}
}
}
The above code currently doesn’t do a lot!
In case you are interested:
Modify the run and main methods to do something useful.
Slide #65 of 55
Creating a Thread in Java (Method # 2)
Implement the Runnable interface, which is defined as:
public interface Runnable{
public abstract void run();
}
When a class implements Runnable, it must define a
run() method
It’s this code, in the run() method, that runs as a
separate thread
Slide #66 of 55
Implementing Runnable (Method # 2)
public class HelloRunnable implements Runnable{
// implement run method here
public void run(){
System.out.println(“Thread by implementing
Runnable”);
}
}
Slide #67 of 55
Testing Runnable (Method # 2)
public class TestHelloRunnable{
public static void main(String[] args){
HelloRunnable ht = new HelloRunnable();
Thread t = new Thread(ht);
t.start();
}
}
Slide #68 of 55
Which way of Creating Threads is Better ?
Implementing the Runnable interface is preferred over
extending Thread class
Java does not support multiple inheritance!
But multiple inheritance can almost be achieved in java by
using interfaces
e.g. class A extends B implements Runnable {}
Slide #69 of 55
Pausing Execution with Sleep
Thread.sleep() causes the current thread to suspend
execution for a specified period
This is an efficient way of making processor time
available to other threads of an application
It takes an argument that denotes the time (in
milliseconds) that you would like a thread to pause for.
Slide #70 of 55
Stopping a Thread
The only safe way to stop a thread is for it to stop itself
A thread t1 can interrupt the running of a thread t2 by
invoking its interrupt method
This sets a flag indicating that the thread should be
terminated right away.
For more details:
https://docs.oracle.com/javase/7/docs/api/java/lang/Thread.html#interrupt()
https://docs.oracle.com/javase/7/docs/api/java/lang/Thread.html#interrupt
Slide #71 of 55
Some Interesting Statistics
64-bit Mac OS X 10.9, Java 1.7.0_45 – JVM dies after
#2031 threads have been created
64-bit Ubuntu Linux, Java 1.7.0_45 – JVM dies after
#31893 threads have been created
64-bit Windows 7, Java 1.7.0_45 – due to a different
thread model used by the OS, this error seems not to be
thrown on this particular platform. On thread #250,000 the
process was still alive, even though the swap file had grown
to 10GB and the application was facing extreme
performance issues.
More at:
https://plumbr.eu/outofmemoryerror/unable-to-create-new-native-
thread
https://plumbr.eu/outofmemoryerror/unable-to-create-new-native-thread
Slide #72 of 55
Inter-thread Communication
• Threads communicate by sharing data:
• Efficient!
• We now have the same problems that we discussed
earlier!
• Solution?
• Synchronize!
Slide #73 of 55
An Example
class Counter {
private int c = 0;
public void increment() {
c++;
}
public void decrement() {
c–;
}
public int value() {
return c;
}
}
Slide #74 of 55
Why is there a problem?
Functions seem simple and atomic
But, to increment, there are three steps
Retrieve the current value of integer
Add 1 to this value
Store the incremented value back to the variable
Slide #75 of 55
Thread Interference
If multiple threads all reference the same object:
thread interference can occur
Happens when two functions, operating on the same
data, interleave
Unpredictable
Difficult to debug
Slide #76 of 55
Memory Consistency
Memory consistency errors occur when different
threads have inconsistent views of the same data
Happens-before relationship
Guarantee that memory writes by one statement are visible
to another
To create a happens-before relationship, we can:
synchronize
Synchronization in Java
Synchronized methods
Synchronized statements
Slide #77 of 55
Synchronized Methods
Add the synchronized keyword to a method
declaration
public synchronized void increment(){
c++;
}
Slide #78 of 55
Synchronized Methods – Effects
Two invocations of a synchronized method on the
same object cannot interleave
All other threads are blocked until first thread is done
When a synchronized method exits, it automatically
establishes a happens-before relationship with any
subsequent invocation of a synchronized method on
the same object
Slide #79 of 55
Locks
Synchronization built around the notion of intrinsic
locks
Enforce exclusive access
Establish happen-before relationships
Thread needs to acquire lock before it can do
anything
Slide #80 of 55
Synchronized Statements
Alternatively, synchronized statements must specify
the object that provides the lock.
public void addName(String name) {
synchronized(this) {
lastName = name;
nameCount++;
}
nameList.add(name);
}
Slide #81 of 55
Object Locks
Used where execution can be interleaved
For example, where two different variables are being
updated.
private Object lock = new Object();
object created purely to act as a lock in a synchronized
statement.
Use with care – ensure it is absolutely safe to all
access to fields to interleave
Slide #82 of 55
Object Locks – Example
public class ObjectsAsLocksExample {
private long c1 = 0;
private long c2 = 0;
private Object lock1 = new Object();
private Object lock2 = new Object();
public void inc1() {
synchronized(lock1) {
c1++;
}
}
public void inc2() {
synchronized(lock2) {
c2++;
}
}
}
Slide #83 of 55
Summary
In this part, we have introduced:
The concept of threads and multithreading.
The differences between parallelism and concurrency
The Amdahl’s law for performance on multicore
Multithreading Models and Java Threads
Threading Issues including thread interference &
memory consistency
The use of synchronized methods and statements to
address the threading issues.
Slide #84 of 55
References / Links
Chapter # 4: Threads, Operating System Concepts (9th
edition) by Silberschatz, Galvin & Gagne
Chapter # 4: Threads, Operating System Internals and
Design Principles (7th edition) by
https://docs.oracle.com/javase/tutorial/essential/concurr
ency/locksync.html
http://tutorials.jenkov.com/java-concurrency/creating-
and-starting-threads.html
https://docs.oracle.com/javase/tutorial/essential/concurrency/locksync.html
http://tutorials.jenkov.com/java-concurrency/creating-and-starting-threads.html