Object-Oriented Programming
Operating Systems
Lecture 3a
Dr Ronald Grau School of Engineering and Informatics Spring term 2018
Previously
Processes
Threads
Distinction to processes (lightweight sub-processes)
Single- and multi-threaded processes
Implementation
User-level threads
Kernel-level threads
Hybrid threads
1
Today
Programming with Threads
The relationship between processes and threads
Threads & Multiprogramming
Parallel vs concurrent execution
Data vs. Task vs. Pipeline parallelism
Single- and multi-core execution
Hyperthreading
Java thread library
Thread Safety
2
Recap: Processes and threads
Revisiting the key abstractions that a process provides
A private address space that provides the illusion that our program has exclusive
use of the memory system. This provides a way for the operating system to group
related resources together. Thus, a process provides a unit of resource ownership
abstraction to the running program
An independent logical thread of control that provides the illusion that our program
has exclusive use of the processor. Thus, process provides a unit of scheduling (or
dispatch) abstraction that runs on the processor.
3
The concept of a thread comes from the realisation that the two characteristics above
are independent and can be treated independently by the OS.
A thread is a unit of scheduling / dispatch that comes without the burden of extensive
resource ownership. Threads are therefore also called light-weight processes.
Recap: Processes and threads
Threads
4
Terminology
Process
Unit of resource ownership and protection
Consists of one or more threads
Thread
Unit for scheduling
Sequential thread of execution
Owned by a process
5
Terminology
Job
Generally, “work to be done” on the application level
Usually, groups of processes to be managed as a unit
Term originating from batch processing (e.g., IBM OS/360)
Task
Meaning depends on context
Generally, a “piece of work” that is part of a job
In the sense of multitasking: processes or threads executing concurrently / in parallel
6
Parallelism vs. Concurrency
Parallelism
N tasks execute at the same time
Requires >= N computing resources
7
Building a house…
Parallelism vs. Concurrency
Parallelism
N tasks execute at the same time
Requires >= N computing resources
Concurrency
N tasks progress at the same time
Competition for < N resources
8
Building a house…
Parallelism vs. Concurrency
Multiprogramming corresponds
to concurrency
Multiprocessing corresponds to
parallelism
9
Parallelising Applications
Challenges
Identifying tasks:
What can be run concurrently?
Balance:
Do tasks perform equal work of equal value?
Data splitting:
How best divide the data for parallel processing?
Data dependency:
Need consider dependencies?
Testing and debugging:
Many different execution paths are possible
10
Parallelising Applications
Thread safety
Ability to execute in multiple threads without race conditions.
Typically concerns library functions
Race conditions occur when program behaviour and
outputs vary as a result of the sequencing or timing of
concurrent threads.
11
Data vs Task Parallelism
12
… vs Pipeline Parallelism
13
Example
Worker model
Similar to the previous
webserver example
14
Example
Map-Reduce Model
Different functions for the
distribution (mapping),
distributed processing
and aggregation of
results (shuffle & sort),
and re-combination
(reducing) of data
E.g., counting word
occurrence in many
different data sources
15
Single-core CPUs
Single-core
Concurrent thread execution
16
Single-core vs Multi-core CPUs
17
Single-core
Concurrent thread execution
Multi-core
Parallel and concurrent thread execution
Hyperthreading
Multi-threaded virtual cores
18
Limits of parallelisation
How much speed can we gain from parallelisation?
Consider we have a program running on a single-core machine.
We are now running the same program on 2 / 4 / 8 cores.
Are we going to get a 2x / 4x / 8x speed increase as a result?
What are the factors that impact on parallelisation performance?
19
Limits of parallelisation
Amdahl's Law
Upper Bound on performance gains from parallelisation:
P: the portion of the program that can be executed in parallel
N: number of processing cores
Example: P = 0.75, N = 2.
20
Limits of parallelisation
Amdahl's Law
Trends
21
Java threads
How do threads work in Java?
Thread implementation dependent on the JVM implementation
Nowadays, 1:1 mapping on threads provided by kernel
E.g. in Linux, JVM calls POSIX thread functions
Implemented by a class that defines a task
run() will be executed as a thread
Task passed to constructor of Thread class
22
java.lang.Runnable
public interface Runnable {
public void run () ;
}
Java threads
Thread class
23
Java threads
Implementing Runnable vs Extending Thread
java.lang.Thread implements java.lang.Runnable.
Why not extend java.lang.Thread?
24
Java threads
Implementing Runnable vs Extending Thread
java.lang.Thread implements java.lang.Runnable.
Why not extend java.lang.Thread?
Multiple inheritance not supported in Java
Task and Runner (i.e. Thread) should not be tightly coupled
Task object can be created without being a thread
When is it a good idea to extend Thread?
25
Java threads
Example 1
26
public class RowSums {
static final int N = 10;
static int[][] matrix = new int[N][N];
static int[] rowSums = new int[N];
static class RowSumsTask implements Runnable {
// ... see Example (2) ...
}
public static void main(String[] args) {
// ... initialise matrix ...
Thread[] threads = new Thread[N];
for(int i=0; i