Csc 562 - Chapter 4 - Threads

Front 1

Thread

Back 1

-This is a basic unit of CPU utilization.
-It comprises a thread ID, a program counter, a register set, and a stack.

Front 2

Multithreaded Process

Back 2

-A process that can perform more than one task at a time.
-Shares code section, data section and other OS resources among other threads belonging to the same process.

Front 3

Benefits of Multithreaded Programming

Back 3

-Responsiveness. It may allow a program to continue running even it part of it is blocked or is performing a lengthy operation.
-Resource sharing. Threads share the memory and resources of the process to which they belong, allowing an application to have several different threads of activity within the same address space.
-Economy. Because threads share resources of the process that they belong to, it's more economical to create and context-switch threads.
Scalability. Benefits can be even greater in a multiprocessor architecture, where threads may be running in parallel on different processing cores.

Front 4

Multicore/Multiprocessor System

Back 4

-Systems that contain multiple computing cores.
-Similar trend is to put multiple computing cores on a single chip.
-Each core appears as a separate processor to the OS.
-Core can appear across the CPU chips or within the CPU chips.

Front 5

Concurrency

Back 5

-Supports more than one task by allowing all the tasks to make progress.
-i.e. On a system with a single computing core, scheduler provides concurrency, meaning execution of threads will be interleaved since only one thread can be executed at a time
-You can have concurrency without parallelism

Front 6

Parallelism

Back 6

-Performs more than one task simultaneously.
-i.e. On a system with multiple cores

Front 7

Challenges When Designing Programming for Multicore Systems

Back 7

-Identifying tasks: by examining applications to find areas that can be divided into separate, concurrent tasks.
-Balance: Ensuring the tasks to run in parallel perform equal work of equal value.
-Data Splitting: Data accessed and manipulated by the tasks must be divided to run on separate cores.
-Data Dependency: Data accessed by the tasks must be examined for dependencies between 2 or more tasks. Programmers must ensure the execution of the tasks is synchronized to accommodate data dependency.
-Testing and Debugging are more difficult.

Front 8

Amdahl's Law

Back 8

-Formula that identifies potential performance gains from adding additional computing cores to an application that has both serial (nonparallel) and parallel components.
-Serial portion of an application can have a disproportionate effect on the performance we gain by adding additional computing cores.

Front 9

Data Parallelism

Back 9

-Focuses on distributing subsets of the same data across multiple computing cores and performing the same operation on each core.

Front 10

Task Parallelism

Back 10

-Involves distributing tasks (threads) across multiple computing cores, each thread performing a unique operation.
-Each thread may be operating on the same data or on different data.

Front 11

User Threads

Back 11

-Supported above the kernel and managed without kernel support.
-Support is handled by the user-level threads library
-3 primary libraries: POSIX Pthreads, Windows threads, Java threads

Front 12

Kernel Threads

Back 12

-Supported and managed directed by the OS
-Examples: virtually all contemporary OS's including Windows, Linux, Mac OS X, Solaris

Front 13

Many-To-One Model: (Relationship Between User Threads and Kernel Threads)

Back 13

-Maps many user-level threads to one kernel thread.
-If one thread blocks, it causes them all to block (the entire process).
-Multiple threads are unable to run in parallel on multicore systems since only one thread can access the kernel at a time.
-Few systems use it; Solaris Green Threads, GNU Portable Threads

Front 14

One-To-One Model: (Relationship Between User Threads and Kernel Threads)

Back 14

-Maps each user thread to a kernel thread.
-Creating a user-level thread creates a kernel thread.
-Provides more concurrency than many-to-one model by allowing another thread to run when a thread makes a blocking system call.
-Allows multiple threads to run in parallel on multiprocessors.
-Number of threads per process is sometimes restricted due to overhead.
-Examples: Windows, Linux, Solaris 9 and later

Front 15

Many-To-Many Model: (Relationship Between User Threads and Kernel Threads)

Back 15

-Maps many user-level threads to a smaller or equal number of kernel threads.
-Developer can create as many user threads as necessary, and the corresponding kernel threads can run in parallel on a multiprocessor.
-When a thread performs a block call, kernel can schedule another thread for execution.
-Examples: Solaris prior to version 9, Windows with the ThreadFiber package

Front 16

Two-Level Model: (Relationship Between User Threads and Kernel Threads)

Back 16

-Similar to Many-To-Many Model, but it allows a user thread to be bound to a kernel thread.
-Examples: Solaris 8 and earlier, IRIX, HP-UX, Tru64 UNIX

Front 17

Thread Library

Back 17

-Provides the programmer with an API for creating and managing threads.
-3 primary libraries: POSIX Pthreads, Windows, and Java

Front 18

Methods of Implementing Thread Library

Back 18

1) Provide library entirely in user space with no kernel support. All code and data structures for the library exist in user space. Invoking a function in library results in a local function call in user space.
2) Implement kernel-level library supported directly by the OS. Code and data structures for the library exist in kernel space. Invoking a function in the API for the the library results in system call to the kernel.

Front 19

POSIX Pthreads (Library)

Back 19

-May be provided as either a user-level or a kernel-level library.
-POSIX standard API for thread creation and synchronization.
This is a specification for thread behavior, not an implementation.
-Most common in UNIX-based OS's (Solaris, Linux, Mac OS X)
-Data shared by separate threads are declared globally.
-pthread_t tid declares the identifier for the thread we will create.
-pthread_attr_t attr declaration represents the attributes for the thread (stack size, scheduling info).
-pthread_create() function call creates a thread.
-pthread_join() function will cause a thread to wait on another thread to terminate.
-pthread_exit() function terminates a thread.

Front 20

Windows Threads (Library)

Back 20

-Kernel-level library; very similar to Pthreads technique.
-Data shared by separate threads are declared globally.
-Threads are created using CreateThread() function, with a set of attributes for the thread passed to the function, similar to Pthreads.
-WaitForSingleObject() function causing creating thread to block until child thread has exited.
-WaitForMulitpleObjects() function is used when multiple threads are being waited for to complete.

Front 21

Java Threads (Library)

Back 21

-Allows threads to be created and managed directly in Java programs.
-Access to shared data must be explicitly arranged between threads, unlike w/ Pthreads and Windows.
-Sharing occurs by passing references to the shared object to the appropriate thread.
-Managed by the JVM.
-Available on any system that provides a JVM, including Android applications.
-Two ways of creating threads in a Java program:
1) Create a new class derived from the Thread class and override its run() method.
2) Define a class that implements the Runnable interface, which must define the run() method.
-The code implementing the run() method in both cases is what runs as a separate thread.
-join() method is used for parent threads to wait to proceed.

Front 22

Asynchronous Threading

Back 22

-Once the parent creates a child thread, the parent resumes its execution, so that the parent and child execute concurrently.
-Each thread runs independently, and the parent thread need not know when its child terminates.
-Little data sharing between threads.

Front 23

Synchronous Threading

Back 23

-When the parent thread creates one or more children and then must wait for all of it children to terminate before it resumes.
-Threads created by the parent work concurrently, but the parent can't continue until this work has been completed.
-Involves significant data sharing among threads.
-Fork-Join Strategy

Front 24

Implicit Threading

Back 24

-The creation and management of threading is done by compilers and run-time libraries rather than application developers.
-Done to address the difficulties of applications containing hundreds or thousands of threads.
-3 approaches: Thread pools, OpenMP, and Grand Central Dispatch

Front 25

Thread Pool

Back 25

-They create a number of threads at process startup and place them in a pool to wait for work. Threads return to pool when finished with its service. If no threads are available, request must wait.
-Benefits:
1) Servicing a request with an existing thread is faster that waiting to create a thread.
2) A pool limits the # of threads that exist at any one point.
3) Separating task to be performed from mechanics of creating task allows different strategies for running the task.
-Windows API supports thread pools: PoolFunction() function runs as a separate thread.

Front 26

OpenMP

Back 26

-Set of compiler directives and an API for programs written in C, C++, or FORTRAN that provides support for parallel programming in shared-memory environments.
-Identifies parallel regions as blocks of code that may run in parallel.
-Developers insert compiler directives into their code at parallel regions, and these directives instruct the OpenMP run-time library to execute the region in parallel.
-Provides additional directives for running code regions in parallel, including parallelizing loops.
-Allows developers to choose among several levels of parallelism and whether data can be shared among threads.
-Available for several open-source and commercial compilers for Linux, Windows, and Mac OS X.

Front 27

Grand Central Dispatch (GCD)

Back 27

-A technology for Apple's Mac OS X and iOS OS's.
-A combination of extensions to the C language, an API, and a run-time library that allows application developers to identify sections of code to run in parallel.
-Manages most of the details of threading.
-Identifies extensions to the C and C++ languages, blocks - a self-contained unit of work, specified by a caret ^ inserted in front of a pair of braces {}.
-Schedules blocks for run-time execution by placing them on a dispatch queue. When it removes a block, it assigns the block to a thread from the thread pool.
-There are two types of dispatch queues: serial and concurrent.
-Internally, GCD's thread pool is composed of POSIX threads.

Front 28

Serial Queues (GCD Dispatch Queue)

Back 28

-Blocks are removed in FIFO order.
-Once a block has been removed from the queue, it must complete execution before another is removed.
-Each process has its own serial queue called the main queue.
-Developers can create additional serial queues local to processes.

Front 29

Concurrent Queues (GCD Dispatch Queue)

Back 29

-Blocks are removed in FIFO order.
-Several blocks may be removed at a time, thus allowing multiple blocks to execute in parallel.
-There are 3 system-wide concurrent dispatch queues, distinguished according to priority: low, default, high.

Front 30

fork() System Call (Threading Issues)

Back 30

-Some UNIX systems have 2 versions of fork():
1) Duplicate all threads when one thread in a program calls fork(). Appropriate when exec() is not to be called right after forking the separate process.
2)Duplicate only the thread that invoked the fork() system call. Appropriate when exec() is called immediately after forking.

Front 31

exec() System Call (Threading Issues)

Back 31

-Works the same: If a thread invokes exec(), the program specified in the parameter to exec() will replace the entire process, including all threads.

Front 32

Signals

Back 32

-Used in UNIX systems to notify a process that a particular event has occurred.
-Can be received synchronously or asynchronously.
-All signals follow the same pattern:
1) A signal is generated by the occurrence of a particular event.
2) The signal is delivered to a process.
3) Once delivered, signal must be handled.
-Signals are handled by either a default signal handler or a user-defined signal handler.

Front 33

Synchronous Signal

Back 33

-Signals are delivered to the same process that performed the operation that caused the signal.

Front 34

Asynchronous Signal

Back 34

-A signal is generated by an event external to a running process.
-The signal is sent to another process.

Front 35

Default Signal Handler

Back 35

-Every signal has one that the kernel runs when handling that signal.

Front 36

User-Defined Signal Handler

Back 36

-They can override default signal handlers.

Front 37

Signal Handling (Threading Issues)

Back 37

-For single-threaded programs, signals are delivered to process.
-For multithreaded programs, there are several options to where a signal may be delivered:
1) Deliver signal to the thread to which the signal applies.
2)Deliver signal to every thread in the process.
3) Deliver signal to certain threads in the process.
4) Assign a specific thread to receive all signals for the process.
-UNIX's standard function for delivering a signal to a process is kill(pid_t pid, int signal).
-POSIX Pthreads function to deliver a signal to a thread is pthread_kill(pthread_t tid, int signal).

Front 38

Asynchronous Procedure Calls (APCs)

Back 38

-Allows Windows to emulate signals since Windows doesn't explicitly provide support for signals.
-Enables a user thread to specify a function that is to be called when the user thread receives notification of a particular event.
-Equivalent to an asynchronous signal in UNIX.

Front 39

Thread Cancellation (Threading Issues)

Back 39

-Involves terminating a thread before it has completed.
-Thread that is to be canceled is referred to as the target thread.
-There are 2 approaches to thread cancellation: asynchronous and deferred cancellation.
-In Pthreads, thread cancellation is initiated using pthread_cancel() function.
-Invoking cancellation function is only a request to cancel target thread; actual cancellation depends on how target thread is set up to handle request.
-Pthreads supports 3 cancellation modes, defined as a state and a type.
-Pthreads allows threads to enable or disable cancellation; however cancellation requests remain pending, so threads can later enable cancellation.
-On Linux systems, thread cancellation is handled through signals.

Front 40

Asynchronous Cancellation

Back 40

-One thread immediately terminates the target thread.
-Canceling a thread asynchronously may not free a necessary system-wide resource since the OS will often reclaim system resources, but not all of them.
-Not recommended in Pthreads documentation.

Front 41

Deferred Cancellation

Back 41

-The target thread periodically checks whether it should terminate, allowing it an opportunity to terminate itself in an orderly fashion.
-One thread indicates that a target thread is to be canceled, but cancellation occurs only after the target thread has checked a flag to determine whether or not it should be canceled. Thread can perform this check at a point at which it can be canceled safely.
-In Pthreads, the default cancellation type is deferred.
-Cancellation only occurs when a thread reaches a cancellation point.
-pthread_testcancel() establishes a cancellation point.
-If a cancellation request is found pending, a cleanup handler function is invoked, which allows any resources a thread may have acquired to be released before the thread is terminated.

Front 42

Thread-Local Storage (TLS) (Threading Issues)

Back 42

-Allows each thread to have its own copy of data.
-Useful when you do not have control over the thread creation process (i.e. when using a thread pool).
-Different from local variables: Local variables are only visible during a single function invocation, but TLS are visible across function invocations.
-Similar to static data: But TLS data is unique to each thread.

Front 43

Lightweight Process (LWP)

Back 43

-An intermediate data structure between the user and kernel threads.
-Many systems implementing many-to-many or the two-level model use this.
-User-thread library sees the LWP as a virtual processor on which the application can schedule a user thread to run.
-Each LWP is attached to a kernel thread, and if a kernel thread blocks, the LWP blocks. The user-level thread attached to the LWP will also block.
-Typically, an LWP is required for each concurrent blocking system call so one LWP is not waiting for another to return.

Front 44

Scheduler Activation (Threading Issues)

Back 44

-One scheme for communication between the user-thread library and the kernel.
-Kernel provides an application with a set of virtual processors (LWPs), and the application can schedule user threads onto an available virtual processor.
-Kernel must inform an application about certain events, known as upcall.
-Upcalls are handled by the thread library with an upcall handler, which must run on a virtual processor.

Front 45

Windows Threads

Back 45

-Windows implements the Windows API - primary API for Windows 98, NT, 2000, XP, and 7.
-Implements one-to-one mapping.
-Components of a thread include:
1) Unique thread ID.
2) Register set representing the status of the process.
3) User stack when thread is running is user mode and kernel stack when thread is running in kernel mode.
4) Private storage area used by various run-time libraries and dynamic link libraries (DLLs).
-The register set, stacks, and private storage area are known as the context of the thread.
-Primary data structures of a thread include:
1) ETHREAD (executive thread block): Includes pointer to process to which the thread belongs, address of the routine in which the thread starts control, and a pointer to corresponding KTHREAD.
2) KTHREAD (kernel thread block): Includes scheduling and synchronization info for the thread, the kernel stack, and a pointer to the TEB.
3) TEB (thread environment block): Includes thread id, user-mode stack, and an array for thread-local storage. TEB is in user space.

Front 46

Linux Threads

Back 46

-Linux provides the fork() system call to duplicate processes, as well as uses the clone() system call to create threads.
-Linux doesn't distinguish between processes and threads; Linux refers to them as tasks.
-When clone() is invoked, it's passed a set of flags that determine how much sharing is to take place between the parent and child tasks.
-In the Linux kernel, a unique kernel data structure (struct task_struct) exists for each task in the system, which contains pointers to other data structures where data for the tasks are stored.