Operating Systems
Phan Xuan Hieu
Data Science & Knowledge Technology Lab
Faculty of IT, VNU-UET
hieupx@vnu.edu.vn
Thread and Multithreading
Materials
§ Textbook:
• A. Silberschatz, P. B. Galvin, and G. Gagne: Operating System Concepts,
10th edition, John Wiley & Sons, 2018.
• Chapter 4
§ Futher reading:
• W. Stallings: Operating Systems: Internals and Design Principles, 9th
edition, Pearson Education Limited, 2018.
• Chapter 4
• A. S. Tanenbaum and H. Bos: Modern Operating Systems, 4th edition,
Pearson Prentice Hall, 2015.
• Chapter 2
3
Contents
§ Overview
§ Multicore programming
§ Multithreading models
§ Thread libraries
§ Implicit threading
4
Contents
§ Overview
§ Multicore programming
§ Multithreading models
§ Thread libraries
§ Implicit threading
5
Motivation
§ Most modern applications are multithreaded
§ Threads run within application
§ Mutiple tasks with the application can be implemented by
separate threads
• Update display
• Fetch data
• Spell checking
• Answer a network request
§ Process creation is heavy-weight while thread creation is light-
weight
§ Can simplify code, increase efficiency
§ Kernels are generally multithreaded
6
Single and multithreaded processes
7
Multithreaded server architecture
8
Benefits
§ Responsiveness: may allow continued execution if part of
process is blocked, especially important for user interfaces
§ Resource sharing: threads share resources of process,
easier than shared memory or message passing
§ Economy: cheaper than process creation, thread
switching lower overhead than context switching
§ Scalability: process can take advantage of multicore
architectures
9
Contents
§ Overview
§ Multicore programming
§ Multithreading models
§ Thread libraries
§ Implicit threading
10
Multicore programming
§ Multicore or multiprocessor systems putting pressure
on programmers, challenges include:
• Dividing activities
• Balance
• Data splitting
• Data dependency
• Testing and debugging
§ Parallelism implies a system can perform more than one
task simultanously
§ Concurrency supports more than one task making
progress
• Single processor/core, scheduler providing concurrency
11
Concurrency vs. parallelism
§ Concurrent execution on single-core system:
§ Parallelism on a multi-core system:
12
Types of parallelism
§ Data parallelism: distributes subsets of the same data
across multiple cores, same operation on each
§ Task parallelism: distributing threads across cores, each
thread performing unique operation
13
Data and task parallelism
14
Amdahl’s law
§ Identifies performance gains from adding additional cores to an
application that has both serial and parallel components
§ S is serial portion
§ N is number of processing cores
§ That is, if application is 75% parallel / 25% serial, moving from 1 to 2
cores results in speedup of 1.6 times
§ As N approaches infinity, speedup approaches 1/S
§ But does the law take into account contemporary multicore
systems?
15
Amdahl’s law (cont.)
16
User threads and kernel threads
§ User threads: management done by user-level thread library
§ Three primary thread libraries:
• POSIX Pthreads
• Windows threads
• Java threads
§ Kernel threads: supported by the kernel
§ Examples: virtually all general purpose OSes, including:
• Windows
• Linux
• macOS
• iOS
• Android
17
User and kernel threads
18
Contents
§ Overview
§ Multicore programming
§ Multithreading models
§ Thread libraries
§ Implicit threading
19
Mutithreading models
§ Many-to-one
§ One-to-one
§ Many-to-many
20
Many-to-one
§ Many user-level threads mapped to single kernel thread
§ One thread blocking causes all to block
§ Multiple threads may not run in parallel on multicore system
because only one may be in kernel at a time
§ Few systems currently use this model
§ Examples:
• Solaris Green Threads
• GNU Portable Threads
21
One-to-one
§ Each user-level thread maps to kernel thread
§ Creating a user-level thread creates a kernel thread
§ More concurrency than many-to-one
§ Number of threads per process sometimes restricted due to
overhead
§ Examples:
• Windows
• Linux
22
Many-to-many
§ Allows many user level threads to be mapped to many kernel
threads
§ Allows the OS to create a sufficient number of kernel threads
§ Windows with the ThreadFiber package
§ Otherwise not very common
23
Two-level model
§ Similar to many-to-many, except that it allows a user
thread to be bound to kernel thread
24
Contents
§ Overview
§ Multicore programming
§ Multithreading models
§ Thread libraries
§ Implicit threading
25
Thread libraries
§ Thread library provides programmer with API for
creating and managing threads
§ Two primary ways of implementing
• Library entirely in user space
• Kernel-level library supported by the OS
26
Pthread
§ May be provided either as user-level or kernel-level
§ A POSIX standard (IEEE 1003.1c) API for thread creation
and synchronization
§ Specification, NOT implementation
§ API specifies behavior of the thread library, implementation
is up to development of the library
§ Common in Unix operating systems (including Linux and
macOS)
27
Pthread example
28
Pthread example (cont.)
29
30
Java threads
§ Java threads are managed by the JVM
§ Typically implemented using the thread model provided by
underlying OS
§ Java threads may be created by
• Extending Thread class
• Implementing the Runnable interface
Public interface Runnable {
public abstract void run();
}
• Standard practice is to implement Runnable interface
31
Java threads (cont.)
§ Implementing Runnable interface:
§ Creating a thread:
§ Waiting on a thread:
32
Contents
§ Overview
§ Multicore programming
§ Multithreading models
§ Thread libraries
§ Implicit threading
33
Implicit threading
§ Growing in popularity as numbers of threads increase,
program correctness more difficult with explicit threads
§ Creation and management of threads done by compilers
and run-time libraries rather than programmers
§ Five methods explored:
• Thread Pools
• Fork-Join
• OpenMP
• Grand Central Dispatch
• Intel Threading Building Blocks
34
Summary
§ Multithreaded process
§ Multicore programming
• Concurrency vs. parallelism
• Types of parallelism (data vs. task)
• Speeding up by parallelism (Amdahl’s law)
§ Thread creation and management
§ Multithreading models
§ Multithreading libraries
• Pthread example
• Java thread example
35