Chapter 4: Threads
Operating System Concepts Essentials – 8th Edition Silberschatz, Galvin and Gagne ©2011
Thread
A thread sometimes called a lightweight process (LWP), is a basic unit of CPU
utilization.
It consists of a thread ID, PC, a register set and a stack.
It shares its code section, data section and other OS resources such as open
files and signals with other threads belonging to same process (Threads run
within application).
A traditional process has a single thread of control. If a process has multiple
threads of control, it can perform more than one task at a time.
Most applications that run on modern computers are multithreaded nowadays.
An application typically implemented as a separate process with several
threads of control. For example, a web browser might have on thread to
displace text or images while another thread retrieves data from the network.
Similarly, a word processor may have a thread for displaying graphics, another
thread for responding to key strokes from user and a thread for performing
spelling and grammar checker in the background.
Operating System Concepts Essentials – 8th Edition 4.2 Silberschatz, Galvin and Gagne ©2011
1
Single and Multithreaded Processes
Applications can also be designed to leverage processing capabilities on
multicore systems.
Such applications can perform several CPU-intensive tasks in parallel
across the multiple computing cores.
In certain situations, a single application may be required to perform several
similar tasks. For example, a web server accepts client requests for web
pages, images, sound and so forth. If the web server ran as traditional
single-threaded process, it would be able to serve only one client at a time.
One solution is to have the server run as a single process that accepts
requests. When the server receives a request, it creates a separate process
to service that request.
In fact this process creation method was common in use, before threads
become popular.
Process creation is heavy-weight, time consuming and resource intensive
while thread creation is light-weight.
It is generally more efficient to use one process that contains multiple
threads.
Operating System Concepts Essentials – 8th Edition 4.3 Silberschatz, Galvin and Gagne ©2011
Single and Multithreaded Processes
Most OS kernels are now multithreaded. Several threads operate in Kernel
and each performs a specific task, such as managing devices, managing
memory or interrupt handling.
For example, Linux uses a Kernel thread for managing the amount of free
Memory.
Operating System Concepts Essentials – 8th Edition 4.4 Silberschatz, Galvin and Gagne ©2011
2
Benefits of Multithreaded Programming
Responsiveness: Multithreading application may allow program to continue
running even, if part of it is blocked or performing lengthy operation, thereby,
increasing responsiveness to the user.
For example, a multithreaded web browser could still allow user interaction in
one thread, while an image is being loaded in another thread.
Resource Sharing: By default, threads share the memory and resources of the
process to which they belong. The benefit of code and data sharing is that it allows
an application to have several different threads of activity all with in the same
address space.
Economy: Allocating memory and resources for process creation is costly.
However, it is more economical to create and context switch threads.
Scalability: The benefit of multithreading can greatly increased in multiprocessor
architecture, where each thread may be running in parallel on different processor.
Multithreading on multiprocessor increases concurrency. In single processor
architecture, the CPU generally moves between each thread so quickly as to
create an illusion of parallelism, but in reality only one thread is running at a time.
Operating System Concepts Essentials – 8th Edition 4.5 Silberschatz, Galvin and Gagne ©2011
Multithreaded Server Architecture
When a multithreaded server receives a request for service, it creates
new thread to service the request as shown above. This allow the
server to service several concurrent requests.
Operating System Concepts Essentials – 8th Edition 4.6 Silberschatz, Galvin and Gagne ©2011
3
Multicore Programming
Now in response to the need of more computing performance, single CPU systems evolved into
multi-CPU systems. A more recent trend in system design is to place multiple computing cores
on a single chip.
Multiprogramming provides a mechanism for more efficient use of these multicore systems and
improves concurrency.
Consider a system with single computing facility having an application with 4 threads. On this
system, concurrency means the execution of threads will be interleaved overtime as shown
below:
Because processor core is capable of execution of one thread at a time.
On a system with multiple cores, concurrency means that threads can run in parallel, because
system can assign a separate threads to each core.
Operating System Concepts Essentials – 8th Edition 4.7 Silberschatz, Galvin and Gagne ©2011
Amdahl’s Law
Operating System Concepts Essentials – 8th Edition 4.8 Silberschatz, Galvin and Gagne ©2011
4
Programming Challenges in Multicore Programming
The trend towards multicore systems continues to place pressure on programmers/system
designers to make better use of multiple computing cores. In general, there are 5 areas present
challenges in programming for multicore systems:
Dividing activities/Identifying tasks: In this challenge, task is to identify the processes that
can be divided into separate, concurrent tasks. Ideally tasks are independent of one another
and thus run in parallel on individual cores.
Balance: While identifying tasks that can run in parallel, developers must also ensure that
tasks perform equal work of equal value. In some instances, a certain task may not contribute
as much value to overall process as other tasks. Using a separate execution core to run these
tasks may not be worth the cost.
Data splitting: Just as applications are divided into separate tasks that data accessed and
manipulated by tasks must be divided to run on separate cores.
Data dependency: The data accessed by tasks must be examined for dependencies between
two or more tasks. When one tasks depends on data from another, programmers must ensure
that the execution of task is synchronized to accommodate that data dependency.
Testing and debugging: When a program is running in parallel on multiple cores, many
different execution paths are possible. Testing and debugging of such concurrent programs is
more difficult than single threaded application.
Because of these challenges, many software developers now argue that the advent of multicore
systems will require an entirely new approach to design system in future.
Operating System Concepts Essentials – 8th Edition 4.9 Silberschatz, Galvin and Gagne ©2011
OS Support Threads
The OS supports the threads at two levels:
User Level Support: User level threads implement in user-level threads library rather than system calls, therefore, thread
switching does not need to call OS and interrupt to Kernel.
In fact Kernel knows nothing about user level threads and manages them as single threaded processes.
Advantages of user-level threads:
User-level threads do not require modification to OS.
Each thread is simply represented by a PC, registers, stack and a small control block, all stored in user process address
space.
Creating, switching and synchronization between threads can not be done without intervention of kernel.
Thread switching is not much expensive than Remote Procedure Call (RPC).
Drawbacks of user-level threads:
There is a lack of coordination between thread and OS Kernel.
User-level threads require non-blocking system calls.
Kernel Level Threads: In this, kernel knows about all threads. The kernel has a thread table that keeps track of all threads in the
system. OS kernel provides system call to create and manage threads.
Advantages of Kernel-level threads:
Because kernel has full knowledge of all threads, scheduler may decide to give time to a process having large number
of threads than process having small number of threads.
Kernel level threads are good for applications that require frequently blocking.
Disadvantages of Kernel-level threads:
The Kernel threads are slow and inefficient.
Kernel manages and schedule threads as well as processes. Therefore, it requires full PCB/TCB for each thread to
maintain information about threads. As a result, there is a significant overhead and increased in kernel complexity.
Operating System Concepts Essentials – 8th Edition 4.10 Silberschatz, Galvin and Gagne ©2011
5
Example of OS Threads
Three primary User thread libraries:
POSIX Pthreads
Win32 threads
Java threads
Examples of Kernel Threads
Windows XP/2000
Solaris
Linux
Tru64 UNIX
Mac OS X
Virtually, all contemporary OSs (Windows, Linux, Mac OS and Solaris
support Kernel-Threads.
Operating System Concepts Essentials – 8th Edition 4.11 Silberschatz, Galvin and Gagne ©2011
Multithreading Models
A relationship must exist between user
threads and Kernel threads. There are three
common ways of establishing such a
relationship:
Many-to-One
One-to-One
Many-to-Many
Operating System Concepts Essentials – 8th Edition 4.12 Silberschatz, Galvin and Gagne ©2011
6
Many-to-One
This model maps many user level threads to one Kernel thread as shown in figure below:S
Thread management is done in user space, so, it is efficient. However, the entire process will
block if a thread makes a blocking system calls.
Also one thread can access the kernel at a time, multiple threads are unable to run in parallel
on multicore systems.
Therefore, very few systems use this model, because of its inability to take the advantage of
multiple processing cores.
Examples:
Solaris Green Threads
GNU Portable Threads
Operating System Concepts Essentials – 8th Edition 4.13 Silberschatz, Galvin and Gagne ©2011
One-to-One
Each user-level thread maps to kernel thread
This model provides more concurrency than many-to-one model by allowing another thread to run
when a thread makes a blocking system call.
It also allow multiple threads to run in parallel on multiple processors.
The only drawback of this model is that creating a user thread requires creating the corresponding
kernel thread. Consequently, it creates overhead on the performance of an application.
Examples
Windows NT/XP/2000
Linux
Solaris 9 and later
Operating System Concepts Essentials – 8th Edition 4.14 Silberschatz, Galvin and Gagne ©2011
7
Many-to-Many Model
This model multiplexes many user-level threads to a smaller or equal number of kernel threads
as shown below:
The number of Kernel threads may be specific to either a particular application or machine.
This model is not suffered from shortcomings as mentioned in previous model.
In this model, developers can create many users threads as necessary and corresponding
kernel threads run in parallel on a multiprocessor.
Also when a thread performs a blocking call, the kernel can schedule another thread for
execution.
Example:
Solaris prior to version 9
Windows NT/2000 with the ThreadFiber package
Operating System Concepts Essentials – 8th Edition 4.15 Silberschatz, Galvin and Gagne ©2011
Two-level Model
Similar to M:M, except that it allows a user thread to be bound to kernel thread
Examples
IRIX
HP-UX
Tru64 UNIX
Solaris 8 and earlier
Operating System Concepts Essentials – 8th Edition 4.16 Silberschatz, Galvin and Gagne ©2011
8
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
Operating System Concepts Essentials – 8th Edition 4.17 Silberschatz, Galvin and Gagne ©2011
Pthreads
May be provided either as user-level or kernel-level
A POSIX standard (IEEE 1003.1c) API for thread creation and synchronization
API specifies behavior of the thread library, implementation is up to development of the library
Common in UNIX operating systems (Solaris, Linux, Mac OS X)
Operating System Concepts Essentials – 8th Edition 4.18 Silberschatz, Galvin and Gagne ©2011
9
Pthreads Example
Operating System Concepts Essentials – 8th Edition 4.19 Silberschatz, Galvin and Gagne ©2011
Pthreads Example (Cont.)
Operating System Concepts Essentials – 8th Edition 4.20 Silberschatz, Galvin and Gagne ©2011
10
Win32 API Multithreaded C Program
Operating System Concepts Essentials – 8th Edition 4.21 Silberschatz, Galvin and Gagne ©2011
Win32 API Multithreaded C Program (Cont.)
Operating System Concepts Essentials – 8th Edition 4.22 Silberschatz, Galvin and Gagne ©2011
11
Java Threads
Java threads are managed by the JVM
Typically implemented using the threads model provided by underlying OS
Java threads may be created by:
Extending Thread class
Implementing the Runnable interface
Operating System Concepts Essentials – 8th Edition 4.23 Silberschatz, Galvin and Gagne ©2011
Java Multithreaded Program
Operating System Concepts Essentials – 8th Edition 4.24 Silberschatz, Galvin and Gagne ©2011
12
Java Multithreaded Program (Cont.)
Operating System Concepts Essentials – 8th Edition 4.25 Silberschatz, Galvin and Gagne ©2011
Threading Issues
Fork() system call is used to create separate duplicate process. Semantics of fork() and
exec() system calls change in multithreaded programming.
If one thread in a program call fork(), does the new process duplicate all threads or is a 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 will replace the entire process-including all threads.
Which of two versions of fork() to use depends on the application.
If exec() is called immediately after forking, then duplicating all threads is unnecessary,
because program specified in parameters to exec() will replace the process.
Signal handling
A signal is used in UNIX systems to notify a process that a particular event has been
occurred.
A signal may be Synchronous or asynchronous, depending on the source of and
reason for which event being signaled.
All signals follow the same pattern
A signal is generated by the occurrence of a particular event.
The signal is delivered to a process.
Once delivered, the signal must be handled.
Operating System Concepts Essentials – 8th Edition 4.26 Silberschatz, Galvin and Gagne ©2011
13
Threading Issues (Cont.)
Example of synchronous signal include illegal memory access and division by 0.
If a running program performs either of these actions, a signal is generated.
Synchronous signals are delivered to the same process that performed the operation
and caused the signal.
When a signal is generated by an event external to running program that process
receives the signal asynchronously.
Example of asynchronous signals includes terminating a process with keystrokes (such
as <control> <C>).
A signal may be handled by one of two possible handlers:
A default signal handler
A user-defined signal handler
Every signal has default signal handler that Kernel runs when handling that signal.
The default action can be overridden by a user-defined signal handler.
Handling signals in single threaded programs is straight forwarded-signals are always
delivered on a process.
However, delivering signals is more complex in multithreaded programs, where a
process may have several threads.
Where, then, should a signal be delivered?
Operating System Concepts Essentials – 8th Edition 4.27 Silberschatz, Galvin and Gagne ©2011
Threading Issues (Cont.)
In general, the following options exist:
Deliver the signal to the thread to which the signal applies.
Deliver the signal to every thread in the process.
Deliver the signal to certain threads in the process.
Assign a specific thread to receive all signals for the process.
The standard UNIX function for delivering a signal is
Kill(pid_t pid, int signal)
This function specifies the process (pid) to which a particular
signal (signal) is to be delivered.
Although Windows does not explicitly provide support for
signals, it allows us to emulate them using asynchronous
procedure calls (APCs). The APC facility enables a user thread
to specify a function that is to be called when user thread
receives notification of a particular event.
Operating System Concepts Essentials – 8th Edition 4.28 Silberschatz, Galvin and Gagne ©2011
14
Threading Issues (Cont.)
Thread cancellation: It 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.
Another situation might occur when a user presses a button on a web
browser that stops a web page from loading any further means all threads
loading the page are cancelled.
A thread that is to be canceled is referred to be as target thread.
Cancellation of a target thread may occur in two different scenarios:
Asynchronous cancellation: One thread immediately terminates the
target thread.
Deferred cancellation: The target thread periodically checks whether it
should terminate, allowing it an opportunity to terminate itself in an
orderly fashion.
Operating System Concepts Essentials – 8th Edition 4.29 Silberschatz, Galvin and Gagne ©2011
Threading Issues (Cont.)
The difficulty with cancellation occurs in situations where resources have
been allocated to a canceled thread or where a thread is canceled while in
the midst of the updating data it is sharing with other threads.
This become troublesome with asynchronous cancellation, because
canceling a thread asynchronously may not free a necessary system-wide
resources.
With deferred cancellation, 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.
The thread can perform this check at a point at which it can be canceled
safely.
In Pthread, thread cancellation is initiated using pthread_cancel() function.
The default cancellation type is deferred cancellation. Here, cancellation
occurs only when a thread reaches a cancellation point.
One technique for establishing a cancellation point is to invoke the
pthread_testcancel() function.
Operating System Concepts Essentials – 8th Edition 4.30 Silberschatz, Galvin and Gagne ©2011
15
Threading Issues (Cont.)
Threads belonging to a process share the data of the process. Indeed, this
data sharing provides one of the benefits of multithreading.
In some circumstances, each thread might need its own copy of certain
data. We call such data thread local storage (TLS)
For example, in a transaction processing system, we might service each
transaction in a separate thread. Each transaction might be assigned a
unique identifier. To associate each thread with its unique identifier, we
could use thread local storage.
It is easy to confuse TLS with local variables. However, local variables are
visible only during a single function invocation, whereas TLS data visible
across function invocations.
Operating System Concepts Essentials – 8th Edition 4.31 Silberschatz, Galvin and Gagne ©2011
Scheduler Activations
Scheduler activations: A final issue to be considered with multithreaded
programs concerns communication between Kernel and thread library which
many require M:M and Two-level model.
Both M:M and Two-level models require communication to maintain the
appropriate number of kernel threads allocated to the application.
Scheduler activations provide upcalls - a communication mechanism from
the kernel to the thread library.
This communication allows an application to maintain the correct number
kernel threads.
Operating System Concepts Essentials – 8th Edition 4.32 Silberschatz, Galvin and Gagne ©2011
16
Lightweight Processes
Many systems implementation either M:M or Two-level model place an intermediate
data structure between user and Kernel threads. This data structure known as
lightweight process or LWP as shown below:
• Each LWP is attached to a Kernel thread and it is the Kernel threads that OS
schedules to run on physical processors. If Kernel thread blocks (such as while
waiting for an I/O operation to complete), the LWP blocks as well.
Operating System Concepts Essentials – 8th Edition 4.33 Silberschatz, Galvin and Gagne ©2011
Scheduler Activations
As discussed earlier, One scheme for communication
between user-thread library and Kernel is known as
scheduler activation.
It works as follows: The Kernel provides an application
with a set of virtual processors (LWPs) and application
can schedule user threads onto available virtual
processor.
Furthermore, Kernel must inform an application about
certain events. This procedure is known as upcall. Upcalls
are handled by thread library with an upcall handler.
Upcall handlers must run on a virtual processor.
Operating System Concepts Essentials – 8th Edition 4.34 Silberschatz, Galvin and Gagne ©2011
17
Operating System Examples
Windows implements the Windows API of Microsoft OSs( Window
98, NT, 2000 and XP)
The general components of thread include:
A thread ID uniquely identifying thread.
A register set representing the status of processor
A user stack, employed when thread is running in user mode ,
and a Kernel stack, employed when the thread is running in
Kernel mode.
A private storage area used by various run-time libraries and
dynamic link libraries (DLL).
The register set, stack and private storage area are known as
context of the thread.
Operating System Concepts Essentials – 8th Edition 4.35 Silberschatz, Galvin and Gagne ©2011
Operating System Examples
The primary data structures of a thread include:
ETHREAD: Executive thread block
KTHREAD: Kernel thread block
TEB: thread environment block
The key components of ETHREAD include a pointer to the process to which
the thread belongs and the address of the routine in which the thread starts
control. The ETHREAD also contains a pointer to the corresponding
KTHREAD.
The KTHREAD includes scheduling and synchronization information for the
thread. It also includes Kernel stack (used when the thread is running in
Kernel mode) and a pointer to TEB.
Both ETHREAD and KTHREAD exist entirely in Kernel space, this means
only Kernel can access them.
The TEB is a user-space data structure that is accessed when thread is
running in user mode. Along with other fields, TEB contains thread identifier,
user-mode stack and an array for thread-local storage.
Operating System Concepts Essentials – 8th Edition 4.36 Silberschatz, Galvin and Gagne ©2011
18
Windows XP Threads Data Structures
Operating System Concepts Essentials – 8th Edition 4.37 Silberschatz, Galvin and Gagne ©2011
Windows XP Threads
Implements the one-to-one mapping, kernel-level
Each thread contains
A thread id
Register set
Separate user and kernel stacks
Private data storage area
The register set, stacks, and private storage area are known as the context of
the threads
The primary data structures of a thread include:
ETHREAD (executive thread block)
KTHREAD (kernel thread block)
TEB (thread environment block)
Operating System Concepts Essentials – 8th Edition 4.38 Silberschatz, Galvin and Gagne ©2011
19
Linux Threads
Linux provides the fork() system call for duplicating a process.
Thread creation is done through clone() system call.
Linux does not distinguish between processes and threads.
Linux refers to them as tasks rather than threads.
clone() allows a child task to share the address space of the parent task
(process)
When clone() is invoked, it is passed a set of flags that determine how
sharing is to take place between the parent and child tasks. Some flags
are shown below:
For example suppose that clone() is passed the flags CLONE_FS,
CLONE_VM, CLONE_SIGHAND and CLONE_FILES. The parent and
child tasks will then share memory space, same signal handlers and
same set of open files.
struct task_struct points to process data structures (shared or unique)
Operating System Concepts Essentials – 8th Edition 4.39 Silberschatz, Galvin and Gagne ©2011
Linux Threads
fork() and clone() system calls
Doesn’t distinguish between process and thread
Uses term task rather than thread
clone() takes options to determine sharing on process create
struct task_struct points to process data structures (shared or
unique)
Operating System Concepts Essentials – 8th Edition 4.40 Silberschatz, Galvin and Gagne ©2011
20
End of Chapter 4
Operating System Concepts Essentials – 8th Edition Silberschatz, Galvin and Gagne ©2011
21
