Transcript Threads

Chapter 4: Threads
Chapter 4: Threads
 Overview
 Multithreading Models
 Threading Issues
 Pthreads
 Windows XP Threads
 Linux Threads
 Java Threads
Operating System Concepts – 7th edition, Jan 23, 2005
4.2
Silberschatz, Galvin and Gagne ©2005
Threads
 A thread comprises a thread ID, a program counter, a register set,
and a stack.
 It shares with other threads belonging to same process its code
section, data section and other OS resources (open files,...)
 A web browser “process” might have one thread display images or
text while another thread retrieves data from the network
 A single application may be required to perform several similar
tasks (e.g. a web server)

Server may create several processes. Process creation is time
consuming. So multiple threads are used.

Typically RPC servers are multithreaded. RMI work similarly.

Many OS kernels are now multithreaded, each thread performs
a specific task, such as interrupt handling.
Operating System Concepts – 7th edition, Jan 23, 2005
4.3
Silberschatz, Galvin and Gagne ©2005
Single and Multithreaded Processes
Operating System Concepts – 7th edition, Jan 23, 2005
4.4
Silberschatz, Galvin and Gagne ©2005
Benefits
 Responsiveness
 Resource Sharing
 Economy
 Utilization of multiprocessor architectures
Operating System Concepts – 7th edition, Jan 23, 2005
4.5
Silberschatz, Galvin and Gagne ©2005
User Threads
 Thread management done by user-level threads library
 Three primary thread libraries:

POSIX Pthreads

Win32 threads

Java threads
Operating System Concepts – 7th edition, Jan 23, 2005
4.6
Silberschatz, Galvin and Gagne ©2005
Kernel Threads
 Supported by the Kernel
 Examples

Windows XP/2000

Solaris

Linux

Tru64 UNIX

Mac OS X
Operating System Concepts – 7th edition, Jan 23, 2005
4.7
Silberschatz, Galvin and Gagne ©2005
Multithreading Models
 Many-to-One
 One-to-One
 Many-to-Many
Operating System Concepts – 7th edition, Jan 23, 2005
4.8
Silberschatz, Galvin and Gagne ©2005
Many-to-One
 Many user-level threads mapped to single kernel thread
 Thread management is done by the thread library in user space

Efficient, but the entire process will block if a thread makes a
blocking system call

True concurrency is not gained because the kernel can schedule
only one thread at a time

Because only one thread can access the kernel at a time, multiple
threads are unable to run in parallel on multiprocessors
 Examples:

Solaris Green Threads

GNU Portable Threads
Operating System Concepts – 7th edition, Jan 23, 2005
4.9
Silberschatz, Galvin and Gagne ©2005
Many-to-One Model
Operating System Concepts – 7th edition, Jan 23, 2005
4.10
Silberschatz, Galvin and Gagne ©2005
One-to-One
 Each user-level thread maps to kernel thread

More concurrency than the 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

Creating a user thread requires creating a kernel thread,...costly.

The developer has to be careful not to create too many threads
 Examples

Windows NT/XP/2000

Linux

Solaris 9 and later
Operating System Concepts – 7th edition, Jan 23, 2005
4.11
Silberschatz, Galvin and Gagne ©2005
One-to-one Model
Operating System Concepts – 7th edition, Jan 23, 2005
4.12
Silberschatz, Galvin and Gagne ©2005
Many-to-Many Model
 Allows many user level threads to be mapped to many kernel
threads
 Allows the operating system to create a sufficient number of kernel
threads
 As many user threads as necessary can be created and the
corresponding kernel threads can run in parallel on a multiprocessor
 When a thread performs a blocking system call, the kernel can
schedule another thread for execution.
 Solaris prior to version 9
 Windows NT/2000 with the ThreadFiber package
Operating System Concepts – 7th edition, Jan 23, 2005
4.13
Silberschatz, Galvin and Gagne ©2005
Many-to-Many Model
Operating System Concepts – 7th edition, Jan 23, 2005
4.14
Silberschatz, Galvin and Gagne ©2005
Two-level Model
 Similar to M:M, still multiplexes many user-level threads to
a smaller or equal number of kernel threads 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 – 7th edition, Jan 23, 2005
4.15
Silberschatz, Galvin and Gagne ©2005
Two-level Model
Operating System Concepts – 7th edition, Jan 23, 2005
4.16
Silberschatz, Galvin and Gagne ©2005
Thread Libraries
 A thread library provides the programmer an API for creating and
managing threads
 Ways of implementing a thread library:


Provide a 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 the library results in a local function call
in user space and not a system call
Implement a kernel-level library supported directly by the OS

Code and data structures exist in the kernel space

Invoking a function in the API results in a system call
Operating System Concepts – 7th edition, Jan 23, 2005
4.17
Silberschatz, Galvin and Gagne ©2005
Thread Libraries
 POSIX Pthreads library may be provided as either a user-or kernel-
level library
 The Win32 thread library is a kernel level library available on Windows
 Java thread API allows thread creation and management directly in
Java programs, but since JVM is running on top of a host OS, the Java
thread API is implemented using a thread library on the host (e.g.
Win32)
 We will examine these three thread libraries. We design a
multithreaded program that performs the summation of a non-negative
integer in a separate thread using the summation function:
N
sum =
i
i 0
Operating System Concepts – 7th edition, Jan 23, 2005
4.18
Silberschatz, Galvin and Gagne ©2005
Multithreaded C program using Pthreads API
#include <pthread.h>
#include <stdio.h>
int sum;
/* this data is shared by the thread(s) */
void *runner(void *param);
/* the thread */
int main(int argc, char *argv[])
{
pthread_t tid;
/* the thread identifier */
pthread_attr_t attr;
/* set of thread attributes */
if (argc != 2) {
fprintf(stderr, “usage: a.out < integer value>\n”);
return -1;
}
if (atoi(argv[1]) < 0) {
fprintf(stderr, “%d must be >= 0\n”, atoi(argv[1]));
return -1;
}
Operating System Concepts – 7th edition, Jan 23, 2005
4.19
Silberschatz, Galvin and Gagne ©2005
Multithreaded C program using Pthreads API
/* get the default attributes */
pthread_attr_init(&attr);
/* create the thread */
pthread_create(&tid, &attr, runner, argv[1]);
/* wait for the thread to exit */
pthread_join(tid, NULL);
printf(“sum = %d\n”, sum);
}
/* The thread will begin control in this function */
void *runner(void *param)
{
int i, upper = atoi(param);
sum = 0;
for (i = 1; i <= upper; i++)
sum += i;
pthread_exit(0);
}
Operating System Concepts – 7th edition, Jan 23, 2005
4.20
Silberschatz, Galvin and Gagne ©2005
Multithreaded
C
program
using
the
Win32
API
#include <windows.h>
#include <stdio.h>
DWORD Sum;
/* data is shared by the thread(s) */
/* the thread runs in this separate function */
DWORD WINAPI Summation(LPVOID Param)
{
DWORD Upper = *(DWORD*)Param;
for (DWORD i = 0; i <= Upper; i++)
Sum += i;
return 0;
}
int main(int argc, char * argv[])
{
DWORD ThreadId;
HANDLE ThreadHandle;
int Param;
/* perform some basic error checking */
if (argc != 2) {
fprintf(stderr, “An integer parameter is required\n”);
return -1;
}
Param = atoi(argv[1];
Operating System Concepts – 7th edition, Jan 23, 2005
4.21
Silberschatz, Galvin and Gagne ©2005
Multithreaded C program using the Win32 API
// create the thread
ThreadHandle = CreateThread(
NULL,
// default security attributes
0,
// default stack size
Summation,
// thread function
&Param,
// parameter to thread function
0,
// default creation flags
&ThreadId);
// returns the thread identifier
if (ThreadHandle != NULL) {
// now wait for the thread to finish
WaitForSingleObject(ThreadHandle, INFINITE);
// close the thread handle
CloseHandle(ThreadHandle);
printf(“Sum = %d\n”, Sum);
}
}
Operating System Concepts – 7th edition, Jan 23, 2005
4.22
Silberschatz, Galvin and Gagne ©2005
Java program for the summation example
class Sum {
private int sum;
public int getSum() {
return sum;
}
public void setSum(int sum) {
this.sum = sum;
}
}
class Summation implements Runnable {
private int upper;
private Sum sumValue;
public Summation(int upper, Sum sumValue) {
this.upper = upper;
this.sumValue = sumValue;
}
public void run() {
int sum = 0;
for (int i = 0; i <= upper; i++)
sum += i;
sumValue.setSum(sum);
}
}System Concepts – 7th edition, Jan 23, 2005
Operating
4.23
Silberschatz, Galvin and Gagne ©2005
Java program for the summation example
Public class Driver
{
public static void main(String[] args) {
if (arg.length > 0) {
if (Integer.parseInt(args[0]) < 0)
System.err.println(args[0] + “ must be >= 0.”);
else {
// create the object to be shared
Sum sumObject = new Sum();
int upper = Integer.parseInt(args[0]);
Thread thrd = new Thread(new Summation(upper, sumObject));
thrd.start();
try {
thrd.join();
System.out.println
(“The sum of “+upper+” is “+sumObject.getSum());
} catch (InterruptedException ie) { }
}
}
else
System.err.println(“Usage: Summation < integer value>”);
}
Operating System Concepts – 7th edition, Jan 23, 2005
}
4.24
Silberschatz, Galvin and Gagne ©2005
Java
 There are two techniques for creating threads in a Java program
Create a new class that is derived from the Thread class and to override
its run() method.
 Define a class that implements the Runnable interface.

public interface Runnable
{
public abstract void run();
}
The code implementing the run() method is what runs as a thread
 The specification for the JVM does not indicate how Java threads are to be
mapped to the underlying OS.
 Windows XP uses the one-to-one model.

There may be a relationship between the Java thread library and the
thread library on the host OS.
For windows Win32 API can be used when creating Java threads.
 Linux and Solaris systems might use Pthreads API.

Operating System Concepts – 7th edition, Jan 23, 2005
4.25
Silberschatz, Galvin and Gagne ©2005
Sharing of Data
 Occurs easily in Win32 and Pthreads, as shared data are simply
declared globally.
 As a pure object-oriented language, Java has no such notion of
global data; if two or more threads are to share data in a Java
program, the sharing occurs by passing reference to the shared
object to the appropriate threads.

In the example program, the main thread and the summation
thread share the object instance of the Sum class which is
referenced through the appropriate getSum() and setSum()
methods.
Operating System Concepts – 7th edition, Jan 23, 2005
4.26
Silberschatz, Galvin and Gagne ©2005
Threading Issues
 Semantics of fork() and exec() system calls
 Thread cancellation
 Signal handling
 Thread pools
 Thread specific data
 Scheduler activations
Operating System Concepts – 7th edition, Jan 23, 2005
4.27
Silberschatz, Galvin and Gagne ©2005
Semantics of fork() and exec()
 Does fork() duplicate only the calling thread or all threads?

Some UNIX systems have chosen to have two versions
 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. Duplicating
only the calling thread is appropriate.

If the separate process does not call exec() after forking, the
separate process should duplicate all threads.
Operating System Concepts – 7th edition, Jan 23, 2005
4.28
Silberschatz, Galvin and Gagne ©2005
Thread Cancellation
 Terminating a thread before it has finished

E.g. When a user presses the stop button on a web browser, all
threads loading the page are cancelled.
 Two general approaches:

Asynchronous cancellation terminates the target thread
immediately.


Troublesome. The OS will reclaim system resources from a
canceled thread but will not reclaim all resources. So,
canceling may not free a system-wide resource
Deferred cancellation allows the target thread to periodically
check if it should be cancelled

Allows a thread to check whether it should be canceled at a
point when it can be canceled safely (“cancellation points” in
Pthreads).
Operating System Concepts – 7th edition, Jan 23, 2005
4.29
Silberschatz, Galvin and Gagne ©2005
Signal Handling

Signals are used in UNIX systems to notify a process that a particular
event has occurred. May be received synchronously or asynchronously.

A signal handler is used to process signals

1.
Signal is generated by particular event
2.
Signal is delivered to a process
3.
Signal is handled
Options in multithreaded programs:

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
Operating System Concepts – 7th edition, Jan 23, 2005
4.30
Silberschatz, Galvin and Gagne ©2005
Signal Handling
 Synchronous signals are delivered to the same process that performed
the operation that caused the signal. Examples of synchronous signals
include illegal memory access, division by 0.
 When a signal is generated by an event external to a running process,
that process receives the signal asynchronously (e.g. <control><C>).
 Every signal may be handled by one of two possible handlers:

A default signal handler

A user-defined signal handler
 When signal handling, some signals may simply be ignored, others may
be handled by terminating the program.
 The standard UNIX function for delivering a signal is:

kill(aid_t aid, int signal)
 Windows does not explicitly provide support for signals. They can be
emulated using asynchronous procedure calls (APCs) which allow a
user thread to specify a function that is to be called when the user
thread receives notification of a particular event.
Operating System Concepts – 7th edition, Jan 23, 2005
4.31
Silberschatz, Galvin and Gagne ©2005
Thread Pools
 A multithreaded server has potential problems

The amount of time required to create the thread (together with the fact
that this thread will be discarded once finished)

If we allow all concurrent requests to be serviced in a new thread, we
have not placed a bound on the number of threads which may exhaust
system resources
 Create a number of threads in a pool where they await work
 Threads from the pool are awakened and when finished returned to pool.
 Advantages:

Usually slightly faster to service a request with an existing thread than
create a new thread

Allows the number of threads in the application(s) to be bound to the size
of the pool
 The number of threads in the pool

can be set heuristically based on factors such as the amount of memory

can be dynamically adjusted according to usage patterns

Consuming less memory with a small pool for low loads
Operating System Concepts – 7th edition, Jan 23, 2005
4.32
Silberschatz, Galvin and Gagne ©2005
Win32 Thread Pools
DWORD WINAPI PoolFunction(AVOID Param) {
/* This function runs as a separate thread */
}
 A pointer to PoolFunction() is passed to one of the functions in the
thread pool API, and a thread from the pool executes this function. One
such member in the thread pool API is the QueueUserWorkItem
which has three parameters
LPTHREAD_START_ROUTINE Function – a pointer to the function
that is to run as a separate thread
PVOID Param – the parameter passed to Function
ULONG Flags – flags indicating how the thread pool is to create and
manage execution of the thread.
An example call
QueueUserWorkItem(&PoolFunction, NULL, 0);
Which causes a thread from the thread pool to invoke PoolFunction()
on behalf of the programmer.
Operating System Concepts – 7th edition, Jan 23, 2005
4.33
Silberschatz, Galvin and Gagne ©2005
Thread Specific Data
 Threads belonging to a process share the data of the process
 But thread-specific data 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)
Operating System Concepts – 7th edition, Jan 23, 2005
4.34
Silberschatz, Galvin and Gagne ©2005
Scheduler Activations
 Communication between the kernel and the thread library
 Both M:M and Two-level models require communication to maintain the
appropriate number of kernel threads allocated to the application. They place
an intermediate data structure between the user and kernel threads known as
lightweight process (LWP) which appears to the user-thread library to be a
virtual processor on which the application can schedule a user thread to run.
Each LWP is attached to a kernel thread. Typically, an LWP is required for
each concurrent blocking system call for I/O intensive applications
 The kernel provides an application with a set of virtual processors (LWPs),
and the application can schedule user threads onto an available virtual
processor
 Scheduler activations provide upcalls - a communication mechanism from
the kernel to the thread library which handles them with upcall handlers.
 This communication allows an application to maintain the correct number
kernel threads
Operating System Concepts – 7th edition, Jan 23, 2005
4.35
Silberschatz, Galvin and Gagne ©2005
Scheduler Activations
 One event that triggers an upcall occurs when an application
thread is about to block.
 Kernel makes an upcall to the application informing it that a thread
is about to block.
 The kernel then allocates a new LWP to the application. The
application runs an upcall handler on this new virtual processor
which relinquishes the LWP on which the blocking thread is
running.
 The upcall handler then schedules another thread that is eligible to
run on the new LWP.
 When the event that the blocking thread was waiting occurs, the
kernel makes another upcall to the thread library informing it that
the previously blocked thread is now eligible to run. The upcall
handler for this event also requires an LWP.
Operating System Concepts – 7th edition, Jan 23, 2005
4.36
Silberschatz, Galvin and Gagne ©2005
Pthreads
 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 – 7th edition, Jan 23, 2005
4.37
Silberschatz, Galvin and Gagne ©2005
Windows XP Threads
 Win32 API
 Implements the one-to-one mapping
 Each thread contains

A thread id

Register set

Separate user and kernel stacks

Private data storage area for run-time libraries and DLLs.
 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)


Contains thread start adress, pointer to parent process, pointer to KTHREAD
Contains scheduling and synchronization info, kernel stack, pointer to TEB
TEB (thread environment block)

Contains thread identifier, user stack, thread-local storage (thread specific data)
Operating System Concepts – 7th edition, Jan 23, 2005
4.38
Silberschatz, Galvin and Gagne ©2005
Linux Threads
 Linux refers to them as tasks rather than threads
 Thread creation is done through clone() system call
 clone() allows a child task to share the address space of the parent
task (process)

File-system info may be shared

The same memory space may be shared

Signal handlers may be shared

The set of open files may be shared

Rather then copying all data structures, the new task points to
the data structures of the parent task
 A unique kernel data structure (struct task_struct) exist for
each task in the system. It contains pointers to other data structures
where these data are stored
 When fork() is invoked, a new task is created, along with a copy of
all the associated data structures of the parent process
Operating System Concepts – 7th edition, Jan 23, 2005
4.39
Silberschatz, Galvin and Gagne ©2005
Java Threads
 Java threads are managed by the JVM
 Java threads may be created by:

Extending Thread class

Implementing the Runnable interface
Operating System Concepts – 7th edition, Jan 23, 2005
4.40
Silberschatz, Galvin and Gagne ©2005
Java Thread States
Operating System Concepts – 7th edition, Jan 23, 2005
4.41
Silberschatz, Galvin and Gagne ©2005
End of Chapter 4