OS Chapter 4: THREADS N CONCURRENCY

Page 1

Objectives

basic components of threads versus processes

benefits and challenges of multithreaded process design

implicit threading: thread pools, fork-join, Grand Central Dispatch

Windows and Linux representing threads

multithreaded app desing using Pthreads, Java and Windows API's for MT

Page 2

Overview

basic unit of "CPU utilization"

thread ID, PC, register set, stack - one thread

other threads belonging to the same process - code, data + other OS resources

single-threaded vs multi-threaded process

Motivation

app creating thumbnails from many pictures

word processor - displaying graphics, responding to keystrokes, spell-check

design for leveraging capabilities on multicore systems - CPU intensive tasks

web server example - request 1) resume listening to clients 2) service request

kernel multithreaded - boot time example

Page 3

Benefits

responsiveness - part blocked still running or performing lengthy operation, UI

resource sharing - having multiple threads/activities sharing same address space

economy - more economical creation and context-swithing threads - time and memory save

scalability - threads running in parallel on different processing cores

Page 4

Multicore Programming

more computing cores on single processin chip (CPU)

using these multiple computing cores

concurrent vs parallel execution / single-core vs multicore system

concurrency possible even without parallelism - before multipocesors n MC

Programming Challenges

Identifiying tasks - areas that can be divided in seperate independent tasks

Balance - ensuring each task performs equal work of equal value

Data splitting - dividing data accessed and manipulated to run on separate Cs

Data dependency - examine data for dependecies between 2+ tasks - sync

Testing and debugging - more difficult

Page 5

Amdahl's Law

formula for performance gains from adding additional computing cores to app

app has both serial and parallel components

speedup <= (1) / [S+((1-S)/N)] --> serial percentage of the core (S), # of cores (N)

Types of Parallelism

data and task parallelism

data - distributing subsets of the same data across computing cores

task - distributing tasks across computing cores - unique tasks - data whatever

application might be hybrid between these two

Page 6

Multithreading Models

threads support at user level or by the kernel - user vs kernel threads

kernel threads - managed and supported by OS directly

virtually all OSs support kernel threads

many-to-many, one-to-one and many-to-one model

Many-to-One

maps many user-level threads to one kernel thread

thread management is done by thread library in user space - efficient

one block syscall blocks the entire process

one thread has access to the kernel at a time - unables multitple threads running in parallel on multicore systems

Green Threads - thread library available for Solaris systems - in early Java

Page 7

One-to-one Model

each user thread mapped to kernel thread

more concurrency provided - another thread can run when blocking reached

allows multiple threads running in parallel on multiprocessors

user thread requiring a kernel thread creation - downfall

large number of kernel thread - "Boooo"

implemented by Windows and Linux + OSs

Many-to-many Model

mapping many user-level threads to smaller or equal number of kernel threads

specific to app or machine

when one thread performs blocking syscall - kernel can schedule another thread

Page 8

Models Compared

many-to-one --> no parallelism - kernel can schedule only one kernel thread at a time

one-to-one --> cannot create too many threads within an application (most popular)

many-to-many --> as many user threads ap, corresponding kernel threads run in parallel on MP

Two-level model

many-to-many that allows a user-level thread to be bound to a kernel thread

Page 9

Thread Libraries

providing API for creating and managing threads to programmers

entirely in user mode w/o kernel support (no syscalls) & kernel-level library OS supported

main libraries: POSIX Pthreads, Windows and Java

Page 10

Pthreads - POSIX standard extension - either a user-level or a kernel-level library

Windows thread library - kernel-level library

Java thread API allows threads to be created and managed directly in Java program

since JVM running on top of host OS, Java thread API generally implemented using thread library of the host system

Java Threads on Windows - implemented using Windows API;

Java Threads on UNIX, Linux and macOS - implemented using Pthreads

Posix and Windows threading

any data globally declared outside of any function are shared among all threads belonging to the same process

Java has no equivalent notion of global data so access to shared data must be explicitly arranged between threads

Page 11

Example:

Summation of a Non-negative Integer, n using a multithreaded program in a separate thread

asynchronous threading

once parent creates a child thread it resumes its execution so they execute concurrently, independent of one another

little data sharing btw independent threads

commonly used for multithreaded server or designing responsive UI

synchronous threading

parent thread creates one or more children - waits for them to terminate

child threads can execute concurrently

involves significant data sharing among threads

i.e. parent thread may combine the results calculated by its children

Page 12

Pthreads - POSIX standard (IEEE 1003.1C)

API for thread creation and synchronization

specification for thread behavior not implementation!

many systems implement Pthreads specification - most UNIX-type systems

such as Linux and macOS

Page 14

Pthreads API - constructing multithreaded C program calculating summation using it

in Pthreads program - separate threads begin execution in a specified function

runner() function is that function in example

single thread of control begins in main() - parent process

second thread created - pthread_create(%tid, &attr, runner, argv[1]);

both threads sharing global data sum

c program : #include

pthread_t tid declaring identifier

pthread_attr_t attr representing the attributes - stack size, scheduling...

pthread_attr_init initialization of these

child process - runner() function

pthread_join (tid, NULL); pthread_exit();

create/join strategy used so parent waits for child's termination

Page 15

Pthreads API - joining on ten threads by using pthread_join() function

#define NUM THREADS 10

pthread_t workers [NUM_THREADS]

for (int i=0; i < NUM_THREADS; i++)

pthread_join(workers[], NULL);

Page 16

Windows Threads

#include

DWORD WINAPI Summation (LPVOID Param) //LPVOID - pointer to void

DWORD Upper = *(DWORD*) Param;

for (DWORD i = 1; i <= Upper; i++)

DWORD ThreadId; //unsigned 32-bit integer

HANDLE ThreadHandle

ThreadHandle = CreateThread (NULL, 0, Summation, &Param, 0, &ThreadId);

security info, stack size, flag for start or suspended state

WaitForSignleObject (ThreadHandle,INFINITE); or WaitForMultipleObjects();

# of objects to wait, pointer to array of them, all objects signaled? flag, timeout duration

CloseHandle (ThreadHandle);

Page 17

Java Threads

rich set of features for the creation and management of threads

all programs at least a single thread of control (main())

2 techniques for explicitly creating threads

creating new thread derived from the Thread class

defining a class that implements Runnable interface

pulic void run() - called when we call the start() method

the code in the run() method of a class that implements Runnable is what executes in a seperate thread

class Task implements Runnable { public void run() { System.out.println ("I am a thread."); } }

creating a Thread object and passing it an instance of a class that implements Runnable followed by invoking the start() method on Thread object

Thread worker = new Thread (new Task());

worker.start(); //allocating mem, initializing new thread in JVM, call of run()

Page 18

Java Threads

waiting for summation threads to finish - join() method

try {

worker.join();

}

catch (InterruptedException ie) { }

java.util.concurrent package - thread creation organized around Executor interface:

public interface Executor {

void execute ( Runnable command);

}

Executor service = new Executor;

service.execute(new Task());

Callable interface similar to Runnable - returns a result - Future objects

Page 19

Java Threads

thread creation in Java inolves

creating a Thread object

passing it an instance of a class that implements Runnable interface

followed by invoking start() method on Thread object

Thread worker = new Thread (new Task());

worker.start();

allocating memory and initializating new thread in JVM

call of run() method - Thread eligible to be run by JVM

Page 20

Java Executor Framework

new concurrency features - java.util.concurrent package

thread creation organized around Executor interface

public interface Executor {

void execute (Runnable command);

}

Executor service = new Executor;

service.execute (new Task());

producer - consumer model

tasks implementing the Runnable interface produced by user

threads executing these tasks consume them

provides mechanism for communication between concurrent tasks

Callable interface rather than Runnable interface for return result

Return result is Fututre object --> get() method from Future interface

submit() method - as execute() method, but returns result

Page 21

Implicit Threading

JVM typically implemented on top of a host OS

specification for JVM not indicating how Java threads are mapped to OS

leaving that decision to implementation of JVM

Windows OS one-to-one model - Java thread (JVM) = kernel thread

additionally - relationship btw Java thread library and HOS thread library

JVM for Windows OS - Windows API; Unix fam OS - Pthreads API

Page 22

Implicit Threading (benefit for developers; challenge for machines)

difficulty: growth of multicore processing - apps contain 100s threads

way to address these, and support design of concurrent and parallel apps

transfering creation and management of threading from app developers to compilers and run-time libraries

4 alternative approaches to designing applications that take advantage of multicore processors through implicit threading

developers identify tasks not threads that can run in parallel

function that run-time library maps to separate thread

using many-to-many model

libraries take care of specific details you identify parallel tasks

Page 23

Thread Pools (TP) Why

issues when server creates new thread

amount of time required to create the thread

thread will be discarded once it has completed its work

no bound on the number of threads concurrently active in system

possibly exhausting system resources - CPU time or memory

solution - thread pool

Android - remote service using thread pool handles multiple concurrent requests

Page 24

Thread Pools (TP) Concept

creating number of threads at start-up and placing them into a pool

threads sit and wait for work

server receives request - submits it to the TP and waits for new request

if there is available thread in pool - it's awakened - request service imm

if no available thread - task is queued until one becomes free

completed service followed by return to pool and wait for more work

work better when tasks submitted can be executed asynchronously

Page 25

Thread Pools (TP) Benefits

faster than creating new thread

limited number of threads existing at one point

separation btw task to be performed and mehanics of creating it

different strategies could be used for running it

# of threads in TP based on # of CPUs in system, amount of physical memory, expected number of concurrent client requests...

dynamically adjusting according to usage patterns

Apple's Grand Central Dispatch

Page 26

Thread Pools

Windows API provides several functions

DWORD WINAPI PoolFunction (PVOID Param) {

/* this function runs as a separate thread. */

}

pointer to this function is passed to TP API

one thread from pool executes this function

i.e. QueueUserWorkItem(&PoolFunction, NULL-parameters, 0)

Page 27

Java Thread Pools - java.util.concurrent including API for several TP architectures

Single thread executor - newSingleThreadExecutor() - pool of size 1

Fixed thread executor - newFixedThreadPool(int n) - specified # of threads

Cached thread executor - new CachedThreadPool() - unbounded TP

Executor class methods for TP creation - static ExecutorService 1, 2 or 3

each creates and returns an object instance that implements ExecutorService interface extending Executor interface so we can invoke the execute() method on this object

shutdown() method invoked results in rejection of additional tasks from TP and shuts down once all existing tasks have completed

Page 28

Fork Join - synchronous model - explicit thread creation

main parent thread creates (forks) one or more child threads

main thread waits for childrend to terminate and join with it retrieving and combining their results

fork-join parallelism - threads not constructed during fork stage but rather parallel tasks are designated --> libraries responsibility is to have threads created and assign tasks to threads

synchronous version of TP where library determines number of threads tbc

main --> fork --> task --> join --> main

--> fork --> task --> join -->

Page 29

Fork Join in Java

introduced in API designed to be used with recursive divide-and-conquer algorthms as Quicksort and Mergesort

separate tasks are forkd during divide step & assigned smaller subsets

model: if problem small enough solve it directly; if not, fork on 2 subsets

after forks - join subtask 1, join subtask 2 and return combined results

new thrad pool - ForkJoinPool - can be assigned tasks inheriting the abstract base class ForkJoinTask - for now - SumTask class

ForkJoinPool pool = new ForkJoinPool();

SumTask task = new SumTask (0, SIZE-1, array);

int sum = pool.invok(task); --> submition of initial task to the TP

Page 30

Fork Join in Java

SumTask is class implementing D&C algorithm for sum of the array using FJ

fork() until able to compute() on subset, join() block until task completes and returns the result from compute()

SumTask extends RecursiveTask<Integer> which is derived from ForkJoinTask<V>

work stealing algorithm when thread's queue is empty

Page 31

OpenMP

set of compiler directives and API for programs written in C, C++ or FORTRAN

provides support for parallel programming in SM environments

identifies parallel regions as block of code that may run in parallel

developers insert compiler directives into their code at parallel regions so OpenMP run-time library executes the region in parallel

#pragma omp parallel - directive that creates as many threads as there are processing cores in system

#pragma omp parallel for - OpenMP divides the work contained in the for loop among the threads that it has created in response to compiler directive

# of threads can also be set manually

data private to thread or shared

Page 32

Grand Central Dispatch (GCD)

combination of run-time library, an API, and language extensions allowing developers to identify sections of code (tasks) to run in parallel

it manages most of the details of threading - as OpenMP

scheduling for run-time execution - placing tasks on dispatch queue

removing task from queue follows assigning it to available thread from TP that GCD manages

2 types of dispatch queues: serial & concurrent

serial DQ or private DQ: tasks removed in FIFO order - once removed it must complete before other's execution

main queue - each process has its own serial DQ and developers can create additional local serial queues for that process

concurrent DQ or global DQ: tasks placed on concurrent queue are removed in FIFO order, but several can be removed at a time

Page 33

GCD

4 primary quality-of-service classes of system-wide concurrent queues

user-interactive class: tasks interacting with user

user-initiated class: same as user-interactive but longer processing times

utility: tasks requiring longer time to complete

background: not visible to the user and not time sensitive

2 ways of expressing tasks submitted to DQ

for C, C++ and objective-C languages, GCD identifies a language extension - block - self contained unit of work; ^{}

for Swift programming language, GCD identifies task using a closure - similar to block - expresses a self-contained unit of functionality minus the leading caret ˇ --> dispatch_async (queue, {})

GCD TP composed of POSIC threads internally

releaed by Apple, ported to the FreeBSD OS

Page 34

Intel Thread Building Blocks (TBB)

template library that supports designing parallel applications in C++

no special compiler or language support needed

developers specify tasks that can run in parallel

TBB task scheduler maps these tasks onto underlying threads

provides load balancing - is cache aware - quicker execution

rich set of features provided by TBB

templates for parallel loop structures, hash map, queue, vector

concurrent data structures provided

thread-safe versions of the C++ std template library data structures

Page 35

TBB

parallel_for template provided by TBB

parallel_for (range body)

iteration space - size_t(0), n

an operation to be performed - [=] (size_t i) {apply(v[i]);}

creation of number of tasks that operate on chunks made by dividing the loop iterations

creation of number of threads and assigning tasks to available threads

developer can manually specify the size of the chunks too

Page 36

The fork() and exec() System Calls

some versions of UNIX - fork() duplicate all threads -- some - duplicate this

if thread invokes exec() system call - program specified in the parameter to exec() will replace the entire process - including all threads

which version of fork() to use depends on application

if exec() after forking then duplicating all is unnecessary - only calling t.

o.w. separate process should duplicate all threads

Page 37

Signal Handling

signal use in UNIX - notifying process that a particular event has occurred

signal pattern

signal generated by the occurrence of a particular event

sinal delivered to a process

signal handled by process

synchronous signals - sent to this process

illegal memory access or division by 0

signal delivered to the same process performing the operation

asynchronous signals - sent to another process

signal is generated by an event external to a running process so process receives it asynchronously

process termination with specific keystrokes (<control><C>) or timer

Page 38

Signal Handling

2 possible handlers

default signal handler (DSH)

user-defined signal handler (UDSH)

every signal has DSH that kernel runs when handling that signal

could be overriden by UDSH

signal delivering options

deliver signal to the thread to which it applies

deliver signal to every thread in process

deliver signal to certain thread in process

assign a specific thread to receive all signals for the process

standard UNIX method for delivering a signal: kill (pid_t pid, int signal)

specifies to which process (pid) to deliver a signal - first non-blocking?

Windows allows to emulate signals: asynchronous procedure calls (APC)

delivered to a particular thread rather than process - straight-forward

Page 39

Thread Cancellation

termination of thread before its completion

one finds result - all have to be canceled

target thread - has to be canceled

asynchronous cancellation - one thread imm terminates target thread

deffered cancellation - target thread periodically checks whether to terminate

deffered safer option since it has a flag giving info if thread is ready for cancellation

Pthreads - pthread_cancel(tid) function --> only a request to cancel

create, cancel, join - types of cancellation: ASYNC, DEFERRED, OFF

takes place only when thread reaches cancellation point

pthread_testcancel() function + cleanup handler

Java thread cancellation - Thread worker; worker.interrupt(); isInterrupted() ?

Page 40

Thread-Local Storage (TLS)

often in multithreaded programming threads belonging to process share data

TLS is data needed in situation where each thread needs its own copy of data

transaction-processing example - each transaction has unique identifier

TLS vs local vars - TLS are rather visible not only during function invocationbut rather across them all

similar to static data - difference being - TLS data is unique to each thread

Java providing: ThreadLocal class w set() and get() methods

Pthreads providing: pthread_key_t - key specific to each thread used for TLS

C# language: only [ThreadStatic] storage attribute is needed to declare TLS

gcc: _thread keyword for declaring TLS: static _thread int threadID;

Page 41

Scheduler Activations

communication between the kernel and thread library required by

many-to-many and two-level models

allowing number of kernel threads to be dynamically adjusted to help ensure the best performance

many systems placing intermediate data structure between user and kernel threads - lightweight process (LWP)

for user-thread library - appears to be a virtual processor on which app can schedule user thread to run

attached to Kernel thread which OS schedules to run on physical processor

kernel thread blocks - LWP blocks - user-level thread blocks

LWP is required for each concurrent blocking system call

Page 42

Scheduler Activation

scheme for communication btw user-thread library and kernel

kernel provides an app w set of virtual processors (LWPs)

app can schedule user threads on available virtual processor

kernel must inform app about certain events - upcall procedure

handled by thread library with upcall handler that must run on a virtual processor

example - app thread is about to block - allocaing new virtual processor for app running upcall handler - blocking/unblocking thread

Page 43

Windows Threads

app running as a separate process

each process may contain one or more threads

Windows API and one-to-one mapping is described earlier

general components of a thread include

thread ID uniquely identifying thread

user stack, when thread running in user mode; o.w. kernel stack

private storage area used by run-time libraries and DLLs (dynamic link)

context of the thread - stacks, register set and private storage area

primary data structures of thread include

ETHREAD - executive thread block

KTHREAD - kernel thread block

TEB - thread environment block

Page 44

Windows Threads

ETHREAD key components:

pointer to the process to which thread belongs

address of the routine in which the thread starts control

pointer to corresponding KTHREAD

...

KTHREAD includes:

scheduling and synchronization information for thread

kernel stack

pointer to corresponding TEB

...

TEB - only one user-space DS; accessed when thread is running in user mode

thread identifier

user-mode stack

array for thread-local storage (TLS)

...

Page 45

Linux Threads

fork() and clone() system calls

not distinguishing between processes and threads

Linux . uses term task - rather than process or thread - when reffering to a flow of control within a program

inoking clone() with a set of flags determining how much sharing takes place btw parent and child task

CLONE_FS, file system info shared

CLONE_VM, same memory space shared

CLONE_FILES, open files shared

using clone() equivalent to creating a thread since parent task shares most of its resources with its child task

no flags in clone() - no sharing - similar to fork() system calls

Page 46

Linux Threads

unique kernel data structure - struct task_struct - exists for each task in system

contains pointers to other data structures where data for the task are stored

i.e. data structure representing the list of open files, signal-handling info and virtual memory

fork() invoked - new task created - new copy of all associated data structures of parent process

clone() invoked - new task is created - pointing to the data structure of the parent task depending on the set of flags passed to clone()

+ flags in clone() allows it not only to create a task that behaves as a process or thread but also as a container allowing creating multiple Linux systems under a single Linux kernel run. in isolation to one another - virtualization

Content of the notes (47)

Information