Operating Systems Lecture 3a
Dr Ronald Grau School of Engineering and Informatics Spring term 2020
PAL Sessions 1 Peer-Assisted Learning sessions
A great way to study and get additional help with your exercises from experienced students
They run at fixed hours in the lab classes
There is a time table on Facebook – for details, visit
https://www.facebook.com/informaticspal/
Find more information about the tutors on https://sussexpal.com
How do I pass this module? 2 The lecture notes & recordings will give you some relevant pointers,
but you need to do more to succeed! Successful students will normally
Do the suggested readings and attempt to solve the self-study questions every week. Prepare for and attend lab classes regularly.
Brush up on their programming skills independently, if necessary.
Do the exercises BEFORE the solutions are posted, and review their work afterwards. Explore additional material and readings independently.
Study and adhere to all assignment guidelines very carefully. Make an effort to do well in their coursework assignments.
Previously 3 Processes
Threads
Distinction to processes (lightweight sub-processes) Single- and multi-threaded processes
Implementation User-level threads Kernel-level threads Hybrid threads
Today 4 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
Recap: Processes and threads 5 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.
The concept of a thread comes from the realisation that the two characteristics above are independent and can be handled 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 6 Threads
Terminology 7
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
Terminology 8
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
Parallelism vs. Concurrency
9
Parallelism
N tasks execute at the same time Requires >= N computing resources
Building a house…
Parallelism vs. Concurrency
10
Concurrency
N tasks progress at the same time Competition for < N resources
Building a house...
Parallelism vs. Concurrency 11 Multiprogramming corresponds
to concurrency
Multiprocessing corresponds to parallelism
Parallelising Applications 12 Challenges
Identification of suitable 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 to consider dependencies?
Testing and debugging:
Many different possible execution paths
Parallelising Applications 13 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.
Data vs Task Parallelism 14
... vs Pipeline Parallelism 15
Example 16 Worker model
Similar to the previous webserver example
Example 17 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
Single-core CPUs 18
Single-core
Concurrent thread execution
Single-core vs Multi-core CPUs 19 Single-core
Concurrent thread execution
Multi-core
Parallel and concurrent thread execution
Hyperthreading 20 Multi-threaded virtual cores
Limits of parallelisation 21 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 really going to get a 2-, 4-, or 8-fold speed increase as a result?
What are the factors that impact on parallelisation performance?
Limits of parallelisation
22
Amdahl's Law
Upper Bound on performance gains from parallelisation:
1
1−𝑃+𝑃 𝑁
P: the portion of the program that can be executed in parallel N: number of processing cores
𝑠𝑝𝑒𝑒𝑑_𝑢𝑝 =
Example: P = 0.75, N = 2. 𝑠𝑝𝑒𝑒𝑑_𝑢𝑝 = 1
= 1.6
1 −0.75 +0.75 2
Limits of parallelisation 23
Amdahl's Law Trends
Java threads 24 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
java.lang.Runnable
public interface Runnable {
public void run () ; }
Java threads 25 Thread class
Java threads 26 Implementing Runnable vs Extending Thread
java.lang.Thread implements java.lang.Runnable. Why not extend java.lang.Thread?
Java threads 27 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?
Java threads 28
Example (1)
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