Chapter 4 Threads & Concurrency

Question 1

What are threads?

Answer 1

A thread is a basic unit of CPU utilization; it comprises a thread ID, a program counter (PC), a register set, and a stack.

Question 2

What do threads share with other threads?

Answer 2

It shares with other threads belonging to the same process its code section, data section, and other operating-system resources, such as open files and signals

Question 3

How many threads does a traditional process have?

Answer 3

One

Question 4

What is the use of threads?

Answer 4

Multiple threads can perform more than one task at a time.

Question 5

Examples of Threading

Answer 5

1.) An application that creates photo thumbnails from a collection of images may use a separate thread to generate a thumbnail from each separate
image.

2.) A web browser might have one thread display images or text while another thread retrieves data from the network.

3.) A word processor may have a thread for displaying graphics, another thread for responding to keystrokes from the user, and a third thread for performing spelling and grammar checking in the background.

Question 6

Why are threads used?

Answer 6

They can be used to leverage processing capabilities on multicore systems. Such applications can perform several CPU-intensive tasks in
parallel across the multiple computing cores.

Question 7

Before threads, what method was used to receive multiple requests at the same time?

Answer 7

Process-creation was the method used before threads. It involved creating a new process when a server received a new request. However, this method was deemed too confusing.

Question 8

The 4 Major Benefits of Threads

Answer 8

Responsiveness
Resource sharing
Economy
Scalability

Question 9

1st Benefit: Responsiveness

Answer 9

Multithreading an interactive application may allow a
program to continue running even if part of it is blocked or is performing a lengthy operation, thereby increasing responsiveness to the user.

A single-threaded application would be unresponsive to the user until the operation had been completed. In contrast, if the time-consuming operation is performed in a separate, asynchronous thread, the application remains responsive to the user.

Question 10

2nd Benefit: Resource Sharing

Answer 10

Processes can share resources only through techniques
such as shared memory and message passing. Such techniques must be explicitly arranged by the programmer.

However, threads share the
memory and the resources of the process to which they belong by default. The benefit of sharing code and data is that it allows an application to
have several different threads of activity within the same address space.

Question 11

3rd Benefit: Economy

Answer 11

Because threads share the resources of the process to which they belong, it is more economical to create and context-switch threads.
In general, thread creation consumes less time and memory than process
creation. Additionally, context switching is typically faster between threads than between processes.

Question 12

4th Benefit: Scalability

Answer 12

The benefits of multithreading can be even greater in a multiprocessor architecture, where threads may be running in parallel on different processing cores.

Question 13

What is a multicore system?

Answer 13

Multiple computing cores on a single processing chip, where each core appears as a separate CPU to the operating system.

Question 14

How do multithreading and multicore relate?

Answer 14

Multithreaded programming provides a mechanism for more efficient use of the multiple computing cores in the multicore system and improved concurrency.

Question 15

Concurrency in Single Threaded Programs

Answer 15

On a system with a single computing core,
concurrency merely means that the execution of the threads will be interleaved over time

Question 16

Concurrency in Multithreaded Programs

Answer 16

On a system with multiple cores, concurrency means that some threads can run in parallel because the system can assign a separate thread to each core

Question 17

Concurrent System

Answer 17

A concurrent system supports more than one task by allowing all the tasks
to make progress.

Question 18

Parallel System

Answer 18

A parallel system can perform more than one task simultaneously. Thus, it is possible to have concurrency without parallelism.

Question 19

Challenges for Programming in Multicores Systems

Answer 19

1.) Identifying Tasks
2.) Balance
3.) Data Splitting
4.) Data Dependency
5.) Testing and Debugging

Question 20

1st Problem: Identifying Tasks

Answer 20

This involves examining applications to find areas that can be divided into separate, concurrent tasks. Ideally, tasks are independent of one another and thus can run in parallel on individual
cores.

Question 21

2nd Problem: Balance

Answer 21

While identifying tasks that can run in parallel, programmers must also ensure that the tasks perform equal work of equal value. Some tasks may not contribute as much, so the cost of another core might not be worth it.

Question 22

3rd Problem: Data Splitting

Answer 22

Just as applications are divided into separate tasks, the data accessed and manipulated by the tasks must be divided to run on separate cores.

Question 23

4th Problem: Data Dependency

Answer 23

The data accessed by the tasks must be examined for dependencies between two or more tasks. When one task depends on
data from another, programmers must ensure that the execution of the
tasks is synchronized to accommodate the data dependency.

Question 24

5th Problem: Testing and Debugging

Answer 24

When a program is running in parallel on multiple cores, many different execution paths are possible, making it more difficult for testing and debugging.

Question 25

What are the two types of parallelism?

Answer 25

Data Parallelism
Task Parallelism

Question 26

Data Parallelism

Answer 26

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

Data parallelism involves the distribution of data across multiple cores

Question 27

Data Parallelism Example

Answer 27

Summing the contents of an array of size N. On a single-core system, one thread would simply sum the elements [0]…[N − 1]. On a dual-core system, however, thread A, running on core 0, could sum the
elements [0]…[N∕2 − 1] while thread B, running on core 1, could sum the
elements [N∕2]…[N − 1].

Question 28

Task Parallelism

Answer 28

Involves distributing not data but tasks (threads) across multiple computing cores. Each thread is performing a unique operation. Different threads may be operating on the same data, or they may be operating on different data.

Task parallelism involves the distribution of tasks across multiple cores

Question 29

Task Parallelism Example

Answer 29

An example of task parallelism might involve two threads, each performing
a unique statistical operation on the array of elements. The threads again are
operating in parallel on separate computing cores, but each is performing a
unique operation.

Question 30

User Threads

Answer 30

User threads are supported above the kernel and are managed without kernel support

Question 31

Kernel Threads

Answer 31

Kernel threads are supported
and managed directly by the operating system.

Question 32

Many-to-One Model

Answer 32

The many-to-one model maps many user-level threads to one
kernel thread. Thread management is done by the thread library in user space, so it is efficient

However, the entire process will block if a thread makes a blocking system call. Also, because only one thread can access the kernel at a time, multiple threads are unable to run in parallel on multicore systems.

Prevents Parallelism.

(Ex.) Green Threads (Early Java)

Question 33

One-to-One Model

Answer 33

The one-to-one model maps each user thread to a kernel thread. It provides more concurrency than the many-to-one model by allowing another thread to run when a thread makes a blocking system call.

It also allows multiple threads to run in parallel on multiprocessors. The only drawback to this model is that creating a user thread requires creating the corresponding kernel
thread, and a large number of kernel threads may burden the performance of a system

Allows greater concurrencies but too many threads can slow the system down.

(Ex.) Linux Systems

Question 34

Many-to-Many Model

Answer 34

The many-to-many model multiplexes many user-level threads to a smaller or equal number of kernel threads. The number of kernel threads may be specific to either a particular application or a particular machine.

It is difficult to implement even while being the most flexible.

Question 35

Two-Level Model

Answer 35

One variation on the many-to-many model still multiplexes many user-level threads to a smaller or equal number of kernel threads but also allows a user-level thread to be bound to a kernel thread.

Question 36

What are Thread Libraries?

Answer 36

A thread library provides the programmer with an API for creating and managing threads.

Question 37

Two ways to Create Thread Libraries

Answer 37

The first approach is to provide a library entirely in user space with no kernel support. All code and data structures for the library exist in user space.

The second approach is to implement a kernel-level library supported directly by the operating system. In this case, code and data structures for the library exist in kernel space.

Question 38

Three Main Thread Libraries

Answer 38

POSIX Pthreads: Pthreads, the threads extension of the POSIX standard, may be provided as either a user-level or a kernel-level library.

Windows: The Windows thread library
is a kernel-level library available on Windows systems.

Java: The Java thread API
allows threads to be created and managed directly in Java programs. However, because in most instances the JVM is running on top of a host operating system, the Java thread API is generally implemented using a thread library available on the host system.

Question 39

How is data shared in POSIX and Windows?

Answer 39

For POSIX and Windows threading, any data declared globally—that is,
declared outside of any function—are shared among all threads belonging to
the same process.

Question 40

Asynchronous Threading

Answer 40

With asynchronous threading, once the parent creates a child thread, the parent resumes its execution, so that the parent and child execute concurrently and independently of one another.

Because the threads are independent, there is typically little data sharing between them.

Typically used to for designing responsive user interfaces

Question 41

Synchronous threading

Answer 41

Synchronous threading occurs when the parent thread creates one or more
children and then must wait for all of its children to terminate before it resumes.

Here, the threads created by the parent perform work concurrently, but the parent cannot continue until this work has been completed. Once each thread has finished its work, it terminates and joins with its parent. Only after all of the children have joined can the parent resume execution.

Typically, synchronous
threading involves significant data sharing among threads.

Question 42

Pthreads

Answer 42

Pthreads refers to the POSIX standard (IEEE 1003.1c) defining an API for thread creation and synchronization. This is a specification for thread behavior, not an implementation.

Question 43

pthread_attr_t attr;

Answer 43

The pthread_attr_t attr
declaration represents the attributes for the thread. We set the attributes in the function call pthread_attr_init(&attr). Because we did not explicitly set any attributes, we use the default attributes provided.

Question 44

pthread_create()

Answer 44

A separate thread is created with the pthread create() function call. In addition to passing the thread identifier and the attributes for the thread, we also pass the name of the function where the new thread will begin execution—in this case, the runner() function. Last, we pass the integer parameter that was
provided on the command line, argv[1].

Question 45

runner()

Answer 45

In a Pthreads program, separate
threads begin execution in a specified function. In Figure 4.11, this is the runner() function. When this program begins, a single thread of control begins in main(). After some initialization, main() creates a second thread that begins control in the runner() function. Both threads share the global data sum

Question 46

Final Chunk of Code for 4.11

Answer 46

At this point, the program has two threads: the initial (or parent) thread in main() and the summation (or child) thread performing the summation oper-
ation in the runner() function. This program follows the thread create/join strategy, whereby after creating the summation thread, the parent thread will
wait for it to terminate by calling the pthread join() function. The summation thread will terminate when it calls the function pthread exit(). Once the summation thread has returned, the parent thread will output the value of the
shared data sum.

Question 47

Implicit Threading

Answer 47

One way to address these difficulties and better support the design of concurrent and parallel applications is to transfer the creation and management
of threading from application developers to compilers and run-time libraries.

Question 48

What are the problems of a multithreaded server?

Answer 48

The first issue concerns the amount of time required to create the thread, together with the fact that the thread will be discarded once it has completed its work. The second issue is more troublesome. If we allow each concurrent request to be serviced in a new thread, we have not placed a bound on the number of threads concurrently active in the system. Unlimited threads could
exhaust system resources, such as CPU time or memory.

Question 49

What is a thread pool?

Answer 49

The general idea behind a thread pool is to create a number of threads at start-up and place them into a pool, where they sit and wait for work

Question 50

How does a thread pool work?

Answer 50

When a server receives a request, rather than creating a thread, it instead submits the request to the thread pool and resumes waiting for additional requests. If there
is an available thread in the pool, it is awakened, and the request is serviced immediately. If the pool contains no available thread, the task is queued until one becomes free. Once a thread completes its service, it returns to the pool and awaits more work. Thread pools work well when the tasks submitted to the pool can be executed asynchronously.

Question 51

Benefits of Thread Pool

Answer 51

Servicing a request with an existing thread is often faster than waiting to create a thread.

A thread pool limits the number of threads that exist at any one point. This is particularly important on systems that cannot support a large number of concurrent threads.

Separating the task to be performed from the mechanics of creating the task allows us to use different strategies for running the task. For example, the task could be scheduled to execute after a time delay or to execute
periodically.

Question 52

How are threads in threads pool set?

Answer 52

The number of threads in the pool can be set heuristically based on factors such as the number of CPUs in the system, the amount of physical memory, and the expected number of concurrent client requests.

They can also be dynamically adjusted.

Question 53

Fork Join

Answer 53

The main parent thread creates
(forks) one or more child threads and then waits for the children to terminate and join with it, at which point it can retrieve and combine their results. This synchronous model is often characterized as explicit thread creation, but it
is also an excellent candidate for implicit threading.

Question 54

OpenMP

Answer 54

A set of compiler directives as well as an API for programs written in
C, C++, or FORTRAN that provides support for parallel programming in shared-memory environments.

OpenMP identifies parallel regions as blocks of code that may run in parallel.

Application developers insert compiler directives into their code at parallel regions, and these directives instruct the OpenMP runtime library to execute the region in parallel.

Question 55

How does code that creates a compiler directive above the parallel region work?

Answer 55

It creates as many threads as there are processing cores in the system. Thus, for a dual-core system, two threads are created; for a quad-core system, four are created; and so forth. All the threads then simultaneously execute the parallel region. As each thread exits the parallel region, it is terminated.

Question 56

Grand Central Dispatch

Answer 56

Grand Central Dispatch (GCD) is a technology developed by Apple for its macOS and iOS operating systems. It is a combination of a run-time library, an API, and language extensions that allow developers to identify sections of
code (tasks) to run in parallel.

Question 57

How does GCD schedule tasks?

Answer 57

GCD schedules tasks for run-time execution by placing them on a dispatch queue. When it removes a task from a queue, it assigns the task to an available thread from a pool of threads that it manages. GCD identifies two types of
dispatch queues: serial and concurrent.

Question 58

Concurrent Queue

Answer 58

Tasks placed on a concurrent queue are also removed in FIFO order, but several tasks may be removed at a time, thus allowing multiple tasks to execute in parallel.

Question 59

Serial Queues

Answer 59

Each process has its own serial queue (known as its main queue),
and developers can create additional serial queues that are local to a particular process.

Question 60

QOS_CLASS_USER_INTERACTIVE

Answer 60

The user-interactive class represents tasks that interact with the user, such as the user interface and event handling, to ensure a responsive user interface. Completing a task belonging to this class should require only a small amount of work.

Question 61

QOS_CLASS_USER_INITIATED

Answer 61

The user-initiated class is similar to the user-interactive class in that tasks are associated with a responsive user interface; however, user-initiated tasks may require longer processing times. Opening a file or a URL is a user-initiated task, for example. Tasks
belonging to this class must be completed for the user to continue interacting with the system, but they do not need to be serviced as quickly as tasks in the user-interactive queue.

Question 62

QOS_CLASS_UTILITY

Answer 62

The utility class represents tasks that require a longer time to complete but do not demand immediate results. This class
includes work such as importing data.

Question 63

QOS_CLASS_BACKGROUND

Answer 63

Tasks belonging to the background class are not visible to the user and are not time sensitive. Examples include indexing a mailbox system and performing backups.

Question 64

First way to express tasks submitted to dispatch queues.

Answer 64

For the C, C++, and Objective-C languages, GCD identifies a language extension known as a block, which is simply a self-contained unit of work. A block is specified by a caret ˆ inserted in front of a pair of braces { }. Code within the braces identifies the unit of work to be performed. A
simple example of a block is shown below:
^{ printf(“I am a block”); }

Question 65

Intel Thread Building Block (TBB)

Answer 65

Intel threading building blocks (TBB) is a template library that supports designing parallel applications in C++. As this is a library, it requires no special
compiler or language support. Developers specify tasks that can run in parallel, and the TBB task scheduler maps these tasks onto underlying threads.

Furthermore, the task scheduler provides load balancing and is cache aware, meaning that it will give precedence to tasks that likely have their data stored in cache memory and thus will execute more quickly. TBB provides a rich set of features, including templates for parallel loop structures, atomic operations, and mutual exclusion locking.

In addition, it provides concurrent data structures, including a hash map, queue, and vector, which can serve as equivalent thread-safe versions of the C++ standard template library data structures.

Question 66

Second way to express task submitted to dispatch queue.

Answer 66

For the Swift programming language, a task is defined using a closure, which is similar to a block in that it expresses a self-contained unit of functionality. Syntactically, a Swift closure is written in the same way as
a block, minus the leading caret.

Question 67

Parallel For Loops

Answer 67

Initially, assume there is a function named apply(float value) that performs an operation on the parameter
value. If we had an array v of size n containing float values, we could use the
following serial for loop to pass each value in v to the apply() function:

for (int i = 0; i < n; i++) {
apply(v[i]);
}

Question 68

An alternate way of using parallel for loops.

Answer 68

Alternatively, a developer could use TBB, which provides a parallel for
template that expects two values:
parallel for (range body ) where range refers to the range of elements that will be iterated (known as the iteration space) and body specifies an operation that will be performed on a subrange of elements.
We can now rewrite the above serial for loop using the TBB parallel for
template as follows:

parallel_for (size t(0), n, = {apply(v[i]);});

Question 69

fork() and exec() system calls

Answer 69

If one thread in a program calls fork(), does the new process duplicate all threads, or is the new process single-threaded? Some UNIX systems have
chosen to have two versions of fork(), one that duplicates all threads and another that duplicates only the thread that invoked the fork() system call.

The exec() system call typically works in the same way as described in Chapter 3. That is, if a thread invokes the exec() system call, the program
specified in the parameter to exec() will replace the entire process—including all threads.

Which of the two versions of fork() to use depends on the application. If exec() is called immediately after forking, then duplicating all threads is
unnecessary, as the program specified in the parameters to exec() will replace the process

Question 70

Signal

Answer 70

A signal is used in UNIX systems to notify a process that a particular event has occurred. A signal may be received either synchronously or asynchronously, depending on the source of and the reason for the event being signaled.

Question 71

Signal Patterns

Answer 71

1.) A signal is generated by the occurrence of a particular event.
2.) The signal is delivered to a process.
3.) Once delivered, the signal must be handled.

Question 72

Signal Handler Types

Answer 72

A signal may be handled by one of two possible handlers:
1. A default signal handler
2. A user-defined signal handler

Question 73

Default Signal Handler

Answer 73

Every signal has a default signal handler that the kernel runs when handling that signal.

Question 74

User-define Signal Handler

Answer 74

The default action can be overridden by a user-define
signal handler that is called to handle the signal

Question 75

Options for Signals in Multithreading

Answer 75

1. Deliver the signal to the thread to which the signal applies.
2. Deliver the signal to every thread in the process.
3. Deliver the signal to certain threads in the process.
4. Assign a specific thread to receive all signals for the process.

Question 76

Standard UNIX function for delivering a signal.

Answer 76

kill(pid_t pid, int signal)

Question 77

Standard UNIX function for delivering a signal to a specific thread

Answer 77

pthread_kill(pthread_t tid, int signal)

Question 78

Thread Cancellation

Answer 78

Thread cancellation involves terminating a thread before it has completed. For example, if multiple threads are concurrently searching through a database and one thread returns the result, the remaining threads might be canceled.

Question 79

What is the name of the thread to be canceled?

Answer 79

Target Thread

Question 80

Cancellation of a target thread may occur in two different scenarios

Answer 80

1. Asynchronous cancellation. One thread immediately terminates the target thread.
2. Deferred cancellation. The target thread periodically checks whether it should terminate, allowing it an opportunity to terminate itself in an
   orderly fashion.

Question 81

Cancellation Point

Answer 81

The default cancellation type is deferred cancellation. However, cancella-
tion occurs only when a thread reaches a cancellation point.

Question 82

Cleanup Handler

Answer 82

Additionally, Pthreads allows a function known as a cleanup handler to be invoked if a thread is canceled. This function allows
any resources a thread may have acquired to be released before the thread is terminated.

Question 83

Thread-Local Storage

Answer 83

However, in some circumstances, each thread might need its own copy of certain data. We will call such data thread-local storage (or TLS).

Question 84

Differences between TLS and local variables

Answer 84

It is easy to confuse TLS with local variables. However, local variables are visible only during a single function invocation, whereas TLS data are
visible across function invocations.

Question 85

Lightweight Process (LWP)

Answer 85

Many systems implementing either the many-to-many or the two-level model place an intermediate data structure between the user and kernel
threads. This data structure—typically known as a lightweight process

Question 86

Scheduler Activation

Answer 86

It works as follows: The kernel provides an application with a set of virtual processors (LWPs), and the application can schedule user threads onto an available virtual processor. Furthermore, the kernel must inform an application about certain events. This procedure is known as an upcall. Upcalls are handled by the thread library with an upcall handler, and upcall handlers must run on a virtual processor.

Question 87

clone()

Answer 87

Linux provides the fork() system call with the traditional functionality of duplicating a process, as described in Chapter 3. Linux also provides the ability to create threads using the clone() system call. However, Linux does not distinguish between processes and threads. In fact, Linux uses the term task—rather than process or thread— when referring to a flow of control within a program.