Processes - Part II
Amir H. Payberah
payberah@kth.se
Nov. 7, 2023
Threads
1 / 42
Thread
A basic unit of CPU utilization.
https://tinyurl.com/e8crhtne
2 / 42
Threads (1/2)
I A traditional process: has a single thread.
3 / 42
Threads (1/2)
I A traditional process: has a single thread.
I Multiple threads in a process: performing more than one task at a time.
3 / 42
Threads (1/2)
I A traditional process: has a single thread.
I Multiple threads in a process: performing more than one task at a time.
I Threads in a process share code section, data section, and other OS
resources, e.g., open files.
3 / 42
Threads (2/2)
I Multiple tasks of an application can be implemented by separate threads.
• Update display
• Fetch data
• Spell checking
• Answer a network request
4 / 42
Threads - Example
I Multi-threaded web-server architecture
5 / 42
Threads Benefits
I Responsiveness: allow continued execution if part of process is blocked.
6 / 42
Threads Benefits
I Responsiveness: allow continued execution if part of process is blocked.
I Resource Sharing: threads share resources of process, easier than shared
memory or message passing.
6 / 42
Threads Benefits
I Responsiveness: allow continued execution if part of process is blocked.
I Resource Sharing: threads share resources of process, easier than shared
memory or message passing.
I Economy: thread switching has lower overhead than context switching.
6 / 42
Threads Benefits
I Responsiveness: allow continued execution if part of process is blocked.
I Resource Sharing: threads share resources of process, easier than shared
memory or message passing.
I Economy: thread switching has lower overhead than context switching.
I Scalability: process can take advantage of multiprocessor architectures.
6 / 42
Multi-core Programming
7 / 42
Multi-core Systems
I Users need more computing performance: single-CPU → multi-CPU
8 / 42
Multi-core Systems
I Users need more computing performance: single-CPU → multi-CPU
I A similar trend in system design: multi-core systems
• Each core appears as a separate processor.
8 / 42
Multi-core Systems
I Users need more computing performance: single-CPU → multi-CPU
I A similar trend in system design: multi-core systems
• Each core appears as a separate processor.
I Multi-threaded programming
• Improves concurrency and more efficient use of multiple cores.
8 / 42
Concurrency vs. Parallelism (1/2)
I Concurrency: supporting more than one task by allowing all the tasks to
make progress.
9 / 42
Concurrency vs. Parallelism (1/2)
I Concurrency: supporting more than one task by allowing all the tasks to
make progress.
• A scheduler providing concurrency.
9 / 42
Concurrency vs. Parallelism (1/2)
I Concurrency: supporting more than one task by allowing all the tasks to
make progress.
• A scheduler providing concurrency.
I Concurrent execution on a single-core system.
9 / 42
Concurrency vs. Parallelism (2/2)
I Parallelism: performing more than one task simultaneously.
10 / 42
Concurrency vs. Parallelism (2/2)
I Parallelism: performing more than one task simultaneously.
I Parallelism on a multi-core system.
10 / 42
Types of Parallelism
I Data parallelism
• Distributes subsets of the same data across multiple cores, same operation
on each.
11 / 42
Types of Parallelism
I Data parallelism
• Distributes subsets of the same data across multiple cores, same operation
on each.
I Task parallelism
• Distributes threads across cores, each thread performing unique operation.
11 / 42
Multi-threading Models
12 / 42
User Threads and Kernel Threads
I User threads: managed by user-level threads library.
I Kernel threads: supported by the Kernel.
13 / 42
User Threads and Kernel Threads
I User threads: managed by user-level threads library.
• Three primary thread libraries:
• POSIX pthreads
• Windows threads
• Java threads
I Kernel threads: supported by the Kernel.
13 / 42
Multi-Threading Models
I Many-to-One
I One-to-One
I Many-to-Many
14 / 42
Many-to-One Model
I Many user-level threads mapped to single kernel thread.
15 / 42
Many-to-One Model
I Many user-level threads mapped to single kernel thread.
I One thread blocking causes all to block.
15 / 42
Many-to-One Model
I Many user-level threads mapped to single kernel thread.
I One thread blocking causes all to block.
I Multiple threads may not run in parallel on multi-core system because
only one may be in kernel at a time.
15 / 42
Many-to-One Model
I Many user-level threads mapped to single kernel thread.
I One thread blocking causes all to block.
I Multiple threads may not run in parallel on multi-core system because
only one may be in kernel at a time.
I Few systems currently use this model.
• Solaris green threads
• GNU portable threads
15 / 42
One-to-One Model
I Each user-level thread maps to one kernel thread.
16 / 42
One-to-One Model
I Each user-level thread maps to one kernel thread.
I Creating a user-level thread creates a kernel thread.
16 / 42
One-to-One Model
I Each user-level thread maps to one kernel thread.
I Creating a user-level thread creates a kernel thread.
I More concurrency than many-to-one.
16 / 42
One-to-One Model
I Each user-level thread maps to one kernel thread.
I Creating a user-level thread creates a kernel thread.
I More concurrency than many-to-one.
I Number of threads per process sometimes restricted due to overhead.
16 / 42
One-to-One Model
I Each user-level thread maps to one kernel thread.
I Creating a user-level thread creates a kernel thread.
I More concurrency than many-to-one.
I Number of threads per process sometimes restricted due to overhead.
I Examples:
• Windows
• Linux
16 / 42
Many-to-Many Model
I Allows many user-level threads to be mapped to many kernel threads.
17 / 42
Many-to-Many Model
I Allows many user-level threads to be mapped to many kernel threads.
I Allows the OS to create a sufficient number of kernel threads.
17 / 42
Many-to-Many Model
I Allows many user-level threads to be mapped to many kernel threads.
I Allows the OS to create a sufficient number of kernel threads.
I Examples:
• Windows with the ThreadFiber package
• Otherwise not very common
17 / 42
Thread Libraries
18 / 42
Thread Libraries (1/2)
I Thread library provides programmer with API for creating and managing
threads.
19 / 42
Thread Libraries (1/2)
I Thread library provides programmer with API for creating and managing
threads.
I Two primary ways of implementing:
• Library entirely in user-space.
• Kernel-level library supported by the OS.
19 / 42
Thread Libraries (2/2)
I Pthread
• Either a user-level or a kernel-level library.
20 / 42
Thread Libraries (2/2)
I Pthread
• Either a user-level or a kernel-level library.
I Windows thread
• Kernel-level library.
20 / 42
Thread Libraries (2/2)
I Pthread
• Either a user-level or a kernel-level library.
I Windows thread
• Kernel-level library.
I Java thread
• Uses a thread library available on the host system.
20 / 42
21 / 42
Pthreads
I A POSIX API for thread creation and synchronization.
22 / 42
Pthreads
I A POSIX API for thread creation and synchronization.
I Specification, not implementation.
22 / 42
Pthreads
I A POSIX API for thread creation and synchronization.
I Specification, not implementation.
I API specifies behavior of the thread library, implementation is up
to development of the library.
22 / 42
Pthreads
I A POSIX API for thread creation and synchronization.
I Specification, not implementation.
I API specifies behavior of the thread library, implementation is up
to development of the library.
I Common in UNIX OSs, e.g., Solaris, Linux, Mac OS X
22 / 42
Thread ID
I The thread ID (TID) is the thread analogue to the process ID (PID).
23 / 42
Thread ID
I The thread ID (TID) is the thread analogue to the process ID (PID).
I The PID is assigned by the Linux kernel, and TID is assigned in the
Pthread library.
23 / 42
Thread ID
I The thread ID (TID) is the thread analogue to the process ID (PID).
I The PID is assigned by the Linux kernel, and TID is assigned in the
Pthread library.
I Represented by pthread t.
23 / 42
Thread ID
I The thread ID (TID) is the thread analogue to the process ID (PID).
I The PID is assigned by the Linux kernel, and TID is assigned in the
Pthread library.
I Represented by pthread t.
I Obtaining a TID at runtime:
#include <pthread.h>
pthread_t pthread_self(void);
23 / 42
Creating Threads
I pthread create() defines and launches a new thread.
#include <pthread.h>
int pthread_create(pthread_t *thread, const pthread_attr_t *attr,
void *(*thread_func)(void *), void *arg);
24 / 42
Creating Threads
I pthread create() defines and launches a new thread.
#include <pthread.h>
int pthread_create(pthread_t *thread, const pthread_attr_t *attr,
void *(*thread_func)(void *), void *arg);
I thread func has the following signature:
void *thread_func(void *arg);
24 / 42
Terminating Threads
I Terminating yourself by calling pthread exit().
#include <pthread.h>
void pthread_exit(void *retval);
25 / 42
Terminating Threads
I Terminating yourself by calling pthread exit().
#include <pthread.h>
void pthread_exit(void *retval);
I Terminating others by calling pthread cancel().
#include <pthread.h>
int pthread_cancel(pthread_t thread);
25 / 42
Joining and Detaching Threads
I Joining allows one thread to block while waiting for the termination
of another.
#include <pthread.h>
int pthread_join(pthread_t thread, void **retval);
int pthread_detach(pthread_t thread);
[https://computing.llnl.gov/tutorials/pthreads/#Joining]
26 / 42
Joining and Detaching Threads
I Joining allows one thread to block while waiting for the termination
of another.
I You use join if you care about what value the thread returns when
it is done, and use detach if you do not.
#include <pthread.h>
int pthread_join(pthread_t thread, void **retval);
int pthread_detach(pthread_t thread);
[https://computing.llnl.gov/tutorials/pthreads/#Joining]
26 / 42
A Threading Example
void *thread_func(void *message) {
printf("%s\n", (const char *)message);
return message;
}
int main(void) {
pthread_t thread1, thread2;
const char *message1 = "Thread 1";
const char *message2 = "Thread 2";
// Create two threads, each with a different message.
pthread_create(&thread1, NULL, thread_func, (void *)message1);
pthread_create(&thread2, NULL, thread_func, (void *)message2);
// Wait for the threads to exit.
pthread_join(thread1, NULL);
pthread_join(thread2, NULL);
return 0;
}
27 / 42
Implicit Threading
28 / 42
Implicit Threading
I Increasing the number of threads: program correctness more difficult
with explicit threads.
29 / 42
Implicit Threading
I Increasing the number of threads: program correctness more difficult
with explicit threads.
I Implicit threading: creation and management of threads done by
compilers and run-time libraries rather than programmers.
29 / 42
Implicit Threading
I Increasing the number of threads: program correctness more difficult
with explicit threads.
I Implicit threading: creation and management of threads done by
compilers and run-time libraries rather than programmers.
I Four methods explored:
• Thread Pools
• Fork-Join
• OpenMP
29 / 42
Thread Pools
I Create a number of threads in a pool where they await work.
30 / 42
Thread Pools
I Create a number of threads in a pool where they await work.
I Usually slightly faster to service a request with an existing thread
than create a new thread.
30 / 42
Thread Pools
I Create a number of threads in a pool where they await work.
I Usually slightly faster to service a request with an existing thread
than create a new thread.
I Allows the number of threads in the application(s) to be bound to
the size of the pool.
30 / 42
Fork-Join (1/2)
I Multiple threads (tasks) are forked, and then joined.
31 / 42
Fork-Join (2/2)
32 / 42
Fork-Join (2/2)
32 / 42
OpenMP (1/2)
I Set of compiler directives and APIs for C, C++, FORTRAN.
33 / 42
OpenMP (1/2)
I Set of compiler directives and APIs for C, C++, FORTRAN.
I Identifies parallel regions: blocks of code that can run in parallel.
33 / 42
OpenMP (1/2)
I Set of compiler directives and APIs for C, C++, FORTRAN.
I Identifies parallel regions: blocks of code that can run in parallel.
I #pragma omp parallel: create as many threads as there are cores.
I #pragma omp parallel for: run for loop in parallel.
33 / 42
OpenMP (2/2)
#include <omp.h>
#include <stdio.h>
int main(int argc, char *argv[]) {
/* sequential code */
#pragma omp parallel
{
printf("I am a parallel region.");
}
/* sequential code */
return 0;
}
34 / 42
Thread Cancellation
35 / 42
Thread Cancellation (1/4)
I Terminating a thread before it has finished.
36 / 42
Thread Cancellation (1/4)
I Terminating a thread before it has finished.
I Thread to be canceled is target thread.
36 / 42
Thread Cancellation (1/4)
I Terminating a thread before it has finished.
I Thread to be canceled is target thread.
I Two general approaches:
36 / 42
Thread Cancellation (1/4)
I Terminating a thread before it has finished.
I Thread to be canceled is target thread.
I Two general approaches:
• Asynchronous cancellation terminates the target thread immediately.
36 / 42
Thread Cancellation (1/4)
I Terminating a thread before it has finished.
I Thread to be canceled is target thread.
I Two general approaches:
• Asynchronous cancellation terminates the target thread immediately.
• Deferred cancellation allows the target thread to periodically check if it should
be cancelled.
36 / 42
Thread Cancellation (2/4)
int counter = 0;
pthread_t tmp_thread;
int main() {
pthread_t thread1, thread2;
pthread_create(&thread1, NULL, thread_func1, NULL);
pthread_create(&thread2, NULL, thread_func2, NULL);
pthread_join(thread1, NULL);
pthread_join(thread2, NULL);
}
37 / 42
Thread Cancellation (3/4)
void* thread_func2(void* args) {
tmp_thread = pthread_self();
while (1) {
printf("thread number two\n");
sleep(1); // sleep 1 second
}
}
38 / 42
Thread Cancellation (4/4)
void* thread_func1(void* args) {
while (1) {
printf("thread number one\n");
sleep(1);
counter++;
if (counter == 2) {
pthread_cancel(tmp_thread);
pthread_exit(NULL);
}
}
}
39 / 42
Summary
40 / 42
Summary
I Single-thread vs. Multi-thread
41 / 42
Summary
I Single-thread vs. Multi-thread
I Concurrency vs. parallelism
41 / 42
Summary
I Single-thread vs. Multi-thread
I Concurrency vs. parallelism
I Multi-threading models: many-to-one, one-to-one, many-to-many
41 / 42
Summary
I Single-thread vs. Multi-thread
I Concurrency vs. parallelism
I Multi-threading models: many-to-one, one-to-one, many-to-many
I Multi-thread libraries: pthread
41 / 42
Summary
I Single-thread vs. Multi-thread
I Concurrency vs. parallelism
I Multi-threading models: many-to-one, one-to-one, many-to-many
I Multi-thread libraries: pthread
I Implicit threading
41 / 42
Summary
I Single-thread vs. Multi-thread
I Concurrency vs. parallelism
I Multi-threading models: many-to-one, one-to-one, many-to-many
I Multi-thread libraries: pthread
I Implicit threading
I Thread cancellation
41 / 42
Questions?
Acknowledgements
Some slides were derived from Avi Silberschatz slides.
42 / 42
