Computer Systems Concurrency & Threads
A view of an operating System
Slide #2 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 #3 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 #4 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 #5 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 #6 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 #7 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
This is unlikely:
• but possible!
• and hard to debug!
Store new value
Find Balance Acc2
Store new value
Subtract Transfer
Subtract Transfer
Slide #8 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 #9 of 35
Multiple Processes
Operating System design is concerned with the management of processes and threads
Multiprogramming (Multitasking) Multiprocessing
Distributed Processing
Slide #10 of 35
Concurrency in Different Contexts
Slide #11 of 35
Concurrency: Key Terms
Slide #12 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 #13 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 #14 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 #15 of 35
Process Interaction
Slide #16 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 #17 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 #18 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 #19 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 #20 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 #21 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 #22 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 #23 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 #24 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 #25 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 #26 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 #27 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 #28 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 #29 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 #30 of 35
Shared Lock – Problem
Solution: Use Atomic Instructions for Shared Lock!
Slide #31 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 #32 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 #33 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 #34 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 #35 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 #36 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 #37 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 #38 of 35
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 #39 of 55
From Processes to Threads
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
Multi-threading is the ability of an OS to support multiple, concurrent paths of execution within a single process.
Slide #40 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 #41 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 #42 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 #43 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 #44 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 #45 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 #46 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 #47 of 55
Parallelism
Slide #48 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 #49 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 #50 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 #51 of 55
Multicore and Multi-threading (cont’d)
Slide #52 of 55
Multicore and Multi-threading (cont’d)
Slide #53 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 #54 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 #55 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 #56 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 #57 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 #58 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 #59 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 #60 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 #61 of 55
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 #62 of 35
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 #63 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 #64 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 #65 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 #66 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 #67 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 #68 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 #69 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()
Slide #70 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
Slide #71 of 55
Inter-thread Communication
• Threads communicate by sharing data: • Efficient!
• We now have the same problems that we discussed earlier!
• Solution?
• Synchronize!
Slide #72 of 55
An Example
class Counter { private int c = 0;
public void increment() { c++;
}
public void decrement() { c–;
}
public int value() { return c;
} }
Slide #73 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 #74 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 #75 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 #76 of 55
Synchronized Methods
Add the synchronized keyword to a method declaration
public synchronized void increment(){ c++;
}
Slide #77 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 #78 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 #79 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 #80 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 #81 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 #82 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 #83 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 William Stallings
https://docs.oracle.com/javase/tutorial/essential/concurr ency/locksync.html
http://tutorials.jenkov.com/java-concurrency/creating- and-starting-threads.html
Slide #84 of 55