代写 Java parallel concurrency operating system security Operating Systems Lecture 3a

Operating Systems Lecture 3a
Dr Ronald Grau School of Engineering and Informatics Spring term 2018

Previously 1  Processes
 Threads
 Distinction to processes (lightweight sub-processes)  Single- and multi-threaded processes
 Implementation
 User-level threads  Kernel-level threads  Hybrid threads

Today 2 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 3 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 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 4 Threads

Terminology 5
 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 6
 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
7
Parallelism
 N tasks execute at the same time  Requires >= N computing resources
Building a house…

Parallelism vs. Concurrency
8
Parallelism
 N tasks execute at the same time
 Requires >= N computing resources Concurrency
 N tasks progress at the same time  Competition for < N resources Building a house... Parallelism vs. Concurrency 9  Multiprogramming corresponds to concurrency  Multiprocessing corresponds to parallelism Parallelising Applications 10 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 Parallelising Applications 11 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 12 ... vs Pipeline Parallelism 13 Example 14 Worker model  Similar to the previous webserver example Example 15 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 16 Single-core  Concurrent thread execution Single-core vs Multi-core CPUs 17 Single-core  Concurrent thread execution Multi-core  Parallel and concurrent thread execution Hyperthreading 18 Multi-threaded virtual cores Limits of parallelisation 19 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? Limits of parallelisation 20 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. Limits of parallelisation 21 Amdahl's Law  Trends Java threads 22 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 23 Thread class Java threads 24 Implementing Runnable vs Extending Thread  java.lang.Thread implements java.lang.Runnable.  Why not extend java.lang.Thread? Java threads 25 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 26 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