Bilkent University

Department of Computer Engineering

CS342 Operating Systems

Lecture 4
Threads

(chapter 4)
Dr. İbrahim Körpeoğlu
http://www.cs.bilkent.edu.tr/~korpe

CS342 Operating Systems - Spring 2009 1 İbrahim Körpeoğlu, Bilkent University

References

• The slides here are adapted/modified from the textbook and its slides:
Operating System Concepts, Silberschatz et al., 7th & 8th editions,
Wiley.

REFERENCES
• Operating System Concepts, 7th and 8th editions, Silberschatz et al.
Wiley.
• Modern Operating Systems, Andrew S. Tanenbaum, 3rd edition, 2009.

CS342 Operating Systems - Spring 2009 2 İbrahim Körpeoğlu, Bilkent University

1
 Outline

• Overview • Reentrency
• Multithreading Models • Thread specific data
• Thread Libraries
• Threading Issues
• Operating System Examples
• Windows XP Threads
• Linux Threads

CS342 Operating Systems - Spring 2009 3 İbrahim Körpeoğlu, Bilkent University

Objectives

• To introduce the notion of a thread — a fundamental unit of CPU

utilization that forms the basis of multithreaded computer systems
• To discuss the APIs for the Pthreads, Win32, and Java thread libraries
• To examine issues related to multithreaded programming

CS342 Operating Systems - Spring 2009 4 İbrahim Körpeoğlu, Bilkent University

2
 Threads and Thread Usage

• A process has a single thread of control (execution sequence/flow).

• If it blocks on something, no other activity (task) can be done as part
of the process during this time.
• Need for ability to concurrently run several tasks as part of the same
process.
• Every process has at least one thread (although threading is not
supported).

• A process now can have multiple threads of control. Threads run in

pseudo-parallel manner (concurrently) as part of the same process.
• All threads share the same text and data segments.

CS342 Operating Systems - Spring 2009 5 İbrahim Körpeoğlu, Bilkent University

Threads and Thread Usage

data data

CPU
blocks blocks

blocks

code blocks code

run enough

single-threaded process multi-threaded process

CS342 Operating Systems - Spring 2009 6 İbrahim Körpeoğlu, Bilkent University

3
 a multithreaded process’ execution flows:
threads
Instructions of the Program
main()
Thread0
Thread2

Thread1

time

Lifetime of the process

CS342 Operating Systems - Spring 2009 7 İbrahim Körpeoğlu, Bilkent University

Multithreading Concept

CPU

single-threaded process multi-threaded process

CS342 Operating Systems - Spring 2009 8 İbrahim Körpeoğlu, Bilkent University

4
 Multithreading Concept

Process Process

thread thread thread thread

P1.T1 P2.T1 P2.T2 P2.T3

Schedulable Entities
We can select one of them and run

CS342 Operating Systems - Spring 2009 9 İbrahim Körpeoğlu, Bilkent University

Multithreading Concept
thread1 thread2 thread3 thread4
function1(…)
{
….
{

function2(…)
{
….
{

main()
{ ….
thread_create (function1 ,…);
….
thread_create (function2, …);
….
thread_create (function1, …);
….
}
CS342 Operating Systems - Spring 2009 10 İbrahim Körpeoğlu, Bilkent University

5
 Single and Multithreaded Processes

CS342 Operating Systems - Spring 2009 11 İbrahim Körpeoğlu, Bilkent University

Benefits

• Responsiveness
– One thread blocks, another one runs.
– One thread may always wait for the user
• Resource Sharing
– Threads can easily share resources
• Economy
– Creating a thread is fast
– Context switching among threads may be faster
• Scalability
– Multiprocessors can be utilized better

CS342 Operating Systems - Spring 2009 12 İbrahim Körpeoğlu, Bilkent University

6
 Multicore Programming

• Multicore systems putting pressure on programmers, challenges

include
– Dividing activities
– Balance
– Data splitting
– Data dependency
– Testing and debugging

CS342 Operating Systems - Spring 2009 13 İbrahim Körpeoğlu, Bilkent University

Multithreaded Server Architecture

CS342 Operating Systems - Spring 2009 14 İbrahim Körpeoğlu, Bilkent University

7
 Concurrent Execution on a Single-core System

CS342 Operating Systems - Spring 2009 15 İbrahim Körpeoğlu, Bilkent University

Parallel Execution on a Multicore System

CS342 Operating Systems - Spring 2009 16 İbrahim Körpeoğlu, Bilkent University

8
 Threading Support

• Multithreading can be support by:

– User level libraries (without Kernel being aware of it)

• Library manages threads (user level implementation)
– Kernel itself
• Kernel manages threads (kernel space implementation)

• No matter which was is implemented, threads can be created, used,

and terminated via a set of functions that are part of a Thread API (a
thread library)

CS342 Operating Systems - Spring 2009 17 İbrahim Körpeoğlu, Bilkent University

Thread Library

• Three primary thread libraries:

– POSIX Pthreads
– Win32 threads
– Java threads

CS342 Operating Systems - Spring 2009 18 İbrahim Körpeoğlu, Bilkent University

9
 Kernel Support of Threads

• Kernel may implement threading and manage threads.

• Kernel is aware of threads.

• Examples
– Windows XP/2000
– Solaris
– Linux
– Tru64 UNIX
– Mac OS X

• All these kernels have threading support. They can schedule

processes and their threads (not only processes)

CS342 Operating Systems - Spring 2009 19 İbrahim Körpeoğlu, Bilkent University

Multithreading Models

• A user process wants to create one or more threads.

• Kernel can create one (or more) thread(s) for the process.

• How the threads created by the process are actually run (mapped into
kernel threads)?

• What is the relationship between user level threads and kernel level
threads?

– Many-to-One
– One-to-One
– Many-to-Many

CS342 Operating Systems - Spring 2009 20 İbrahim Körpeoğlu, Bilkent University

10
 Many-to-One Model

• Many user-level threads

mapped to a single kernel thread
• Examples:
– Solaris Green Threads
– GNU Portable Threads
• Thread management
done at user space, by a
thread library
• No need for kernel support for
multithreading (+)
• Multiple threads will run on a single
processor, not utilizing multi-
processor machines. (-)

CS342 Operating Systems - Spring 2009 21 İbrahim Körpeoğlu, Bilkent University

Many-to-One Model
Implementing Threads in User Space
• Kernel does not have to be aware
Thread
of multithreading
Process A Process B
• Library is used to create and
manage, schedule threads.

• A thread has to call a function to

voluntarily give the CPU (-)
– example: thread_yield() Run-time Thread
• Blocking systems calls defeats the system table
purpose and have to be handled (-) PCB A
• Switching between threads is fast; PCB B
Kernel process table
efficient approach (+)
• Thread creation is fast (+)

CS342 Operating Systems - Spring 2009 22 İbrahim Körpeoğlu, Bilkent University

11
 One-to-one Model

• Each user-level thread maps to a kernel thread

• Examples
– Windows NT/XP/2000
– Linux
– Solaris 9 and later
• Provides more concurrency; when a thread blocks, another can run (+).
• Multiple threads can run on several processors if available; utilizing
multiprocessor machines (+).
• Creating a user thread
requires creating a kernel
thread (-)

CS342 Operating Systems - Spring 2009 23 İbrahim Körpeoğlu, Bilkent University

One-to-one Model
Implementing Threads in Kernel
• Kernel is aware of threads. It is
managing threads, schedules
Process A Process B
threads.
• Need system calls to create threads
• Thread switching and creation is
more costly (-)
• Blocking system calls are not
problem anymore. (+)
• Kernel can stop a long running
thread and run another thread. No PCB A
need for explicit request from a PCB B
thread to be stopped. (+) Kernel process table
• Any thread function requires a
system call: (-) Thread table
– ex: thread_wait

CS342 Operating Systems - Spring 2009 24 İbrahim Körpeoğlu, Bilkent University

12
 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

• Solaris prior to version 9

• Windows NT/2000 with the
ThreadFiber package

CS342 Operating Systems - Spring 2009 25 İbrahim Körpeoğlu, Bilkent University

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

CS342 Operating Systems - Spring 2009 26 İbrahim Körpeoğlu, Bilkent University

13
 Thread Libraries

• Thread library provides programmer with API for creating and

managing threads
• Programmer just have to know the thread library interface (API).
Threads may be implemented in user space or kernel space.
– Library may be entirely in user space
– Kernel-level library supported by the OS

CS342 Operating Systems - Spring 2009 27 İbrahim Körpeoğlu, Bilkent University

Pthreads Library

• 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)

CS342 Operating Systems - Spring 2009 28 İbrahim Körpeoğlu, Bilkent University

14
 Pthreads Example

• We will show a program that creates a new thread.

– Hence a process will have two threads :
• 1 - the initial/main thread that is created to execute the main() function
(that thread is always created even there is no support for
multithreading);
• 2 - the new thread.
(both threads have equal power)

• The program will just create a new thread to do a simple computation. The
new thread will get a parameter, an integer value, and will sum all integers
from 1 up to that value. N
– sum = 1+2+…+parameter_value sum = ∑ i
i =1

• The main thread will wait until sum is computed into a global variable.

• Then the main thread will print the result.

CS342 Operating Systems - Spring 2009 29 İbrahim Körpeoğlu, Bilkent University

Pthreads Example

#include <pthread.h>
#include <stdio.h>

int sum; /* shared sum by threads – global variable */

void *runner (void *param); /* thread start function */

CS342 Operating Systems - Spring 2009 30 İbrahim Körpeoğlu, Bilkent University

15
 Pthreads Example
int main(int argc, char *argv[]){
pthread_t tid; /* id of the created thread */
pthread_attr_t attr; /* set of thread attributes */

if (argc != 2) {
fprintf (stderr, “usage: a.out <value>\n”);
return -1;
}
if (atoi(argv[1]) < 0) {
fprintf (stderr, “%d must be >= 0\n”, atoi(argv[1]);
return -1;
}

pthread_attr_init (&attr);
pthread_create (&tid, &attr, runner, argv[1]);
pthread_join (tid, NULL);
printf (“sum = %d\n”, sum);
}
CS342 Operating Systems - Spring 2009 31 İbrahim Körpeoğlu, Bilkent University

Pthreads Example

void *runner (void *param)

{
int i;

int upper;

upper = atoi(param);
sum = 0;

for (i = 1; i <= upper; ++i)

sum += i;

pthread_exit(0);
}

CS342 Operating Systems - Spring 2009 32 İbrahim Körpeoğlu, Bilkent University

16
 Pthreads Example
int main(…) thread1 thread2
{

…
….
pthread_create(&tid,…,runner,..);
wait
pthread_join(tid);

. printf (…, sum, …);

}

runner (…)
{
….
sum = …
pthread_exit();
{
CS342 Operating Systems - Spring 2009 33 İbrahim Körpeoğlu, Bilkent University

Compiling and running the program

• You can put the above code into a .c file, say mysum.c
• In order to use the Pthreads functions, we need to include pthread.h header
file in our program (as shown in previous slides)

• We also need to link with the pthread library (the Pthreads API functions are
not implemented in the standard C library). The way to do that is using the –l
option of the C compiler. After –l you can provide a library name like pthread.

• Hence we can compile+link our program as follows:

– gcc -Wall -o mysum -lpthread mysum.c

• Then we run it as (for example):

– ./mysum 6
• It will print out 21

CS342 Operating Systems - Spring 2009 34 İbrahim Körpeoğlu, Bilkent University

17
 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

CS342 Operating Systems - Spring 2009 35 İbrahim Körpeoğlu, Bilkent University

Threading Issues

• Semantics of fork() and exec() system calls

• Thread cancellation of target thread
– Asynchronous or deferred
• Signal handling
• Thread pools
• Thread-specific data
• Scheduler activations

CS342 Operating Systems - Spring 2009 36 İbrahim Körpeoğlu, Bilkent University

18
 Semantics of fork() and exec()

• Does fork() duplicate only the calling thread or all threads?

• How should we implement fork?

• logical thing to do is:

– 1) If exec() will be called after fork(), there is no need to duplicate
the threads. They will be replaced anyway.

– 2) If exec() will not be called, then it is logical to duplicate the

threads as well; so that the child will have as many threads as the
parent has.

• So we may implement two system calls: like fork1 and fork2!

CS342 Operating Systems - Spring 2009 37 İbrahim Körpeoğlu, Bilkent University

Thread Cancellation

• Terminating a thread before it has finished

• Two general approaches:
– Asynchronous cancellation terminates the target thread
immediately
– Deferred cancellation allows the target thread to periodically
check if it should be cancelled

CS342 Operating Systems - Spring 2009 38 İbrahim Körpeoğlu, Bilkent University

19
 Signal Handling

• Signals are used in UNIX systems to notify a process that a particular

event has occurred
• 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:
– 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

CS342 Operating Systems - Spring 2009 39 İbrahim Körpeoğlu, Bilkent University

a C program using signals

#include <stdio.h> • While a program is running,

#include <signal.h> if we press CTRL-C keys,
#include <stdlib.h> the program will be
terminated (killed). We are
sending a SIGINT signal to
static void sig_int_handler() {
the program
printf("I received SIGINT signal. bye... \n");
• By default, SIGINT is
fflush(stdout);
handled by kernel. By
exit(0); default, kernel terminates
} the program.
• But if we specify a handler
int main() { function as here, then our
signal (SIGINT, sig_int_handler); program can handle it.
• Kernel will notify us when
while (1) user presses the CTRL-C
; keys.
}
Program X

CS342 Operating Systems - Spring 2009 40 İbrahim Körpeoğlu, Bilkent University

20
 delivering signal (notifying)

signal handler run

Program X

SIGINT signal delived

Kernel

CTRL-C

Keyboard

CS342 Operating Systems - Spring 2009 41 İbrahim Körpeoğlu, Bilkent University

kill program

process id = 3405

signal handler run

kill -s SIGINT 3405 Program X

SIGINT signal is delivered

Kernel
SIGINT signal is stored in PCB of X

Keyboard

CS342 Operating Systems - Spring 2009 42 İbrahim Körpeoğlu, Bilkent University

21
 Some Signals

SIGABRT Process abort signal.

SIGALRM Alarm clock.
SIGBUS Access to an undefined portion of a memory object.
SIGCHLD Child process terminated, stopped, or continued.
SIGCONT Continue executing, if stopped.
SIGFPE Erroneous arithmetic operation.
SIGHUP Hangup.
SIGILL Illegal instruction.
SIGINT Terminal interrupt signal.
SIGKILL Kill (cannot be caught or ignored).
SIGPIPE Write on a pipe with no one to read it.
SIGQUIT Terminal quit signal.
SIGSEGV Invalid memory reference.
SIGSTOP Stop executing (cannot be caught or ignored).
SIGTERM Termination signal.

CS342 Operating Systems - Spring 2009 43 İbrahim Körpeoğlu, Bilkent University

Thread Pools

• Create a number of threads in a pool where they await work

• 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

CS342 Operating Systems - Spring 2009 44 İbrahim Körpeoğlu, Bilkent University

22
 Scheduler Activations

• Kernel threads are good, but they are slower if we create short threads
too frequently, or threads wait for each other too frequently.
• Is there a middle way?
– Schedule Activation

• Goal is mimic kernel threads at user level with some more kernel
support. But kernel will not create another thread for each user thread
(M:1 or M:M model).

• Avoid unnecessary transitions between user and kernel space.

CS342 Operating Systems - Spring 2009 45 İbrahim Körpeoğlu, Bilkent University

Scheduler Activations: Upcall mechanism

upcall handler can threads

re-start the 1st thread

Process
Run-time
System upcall handler
(i.e. thread library) Thread schedules
table another thread
library registers a handler makes system call
(upcall handler)
when kernel runs the upcall handler
process/thread (i.e. makes an upcall; activates
is started Kernel the user level scheduler)
kernel detects that I/O is finished
Kernel initiates I/O
and blocks the thread kernel informs the library via upcall

CS342 Operating Systems - Spring 2009 46 İbrahim Körpeoğlu, Bilkent University

23
 From Singlethread to Multithreaded

• Many programs are written as a single threaded process.

• If we try to convert a single-threaded process to multi-threaded

process, we have to be careful about

– the global variables

– the library functions

CS342 Operating Systems - Spring 2009 47 İbrahim Körpeoğlu, Bilkent University

From Singlethread to Multithreaded

int status;

func1(…) {
….
status = …
do_something_based_on(status);
}

func2(…) {
…
status = …
do_something_based_on(status);
}
main() {
….
func1 (…);
func2 (…);
}
CS342 Operating Systems - Spring 2009 48 İbrahim Körpeoğlu, Bilkent University

24
 From Singlethread to Multithreaded
int status;
• We can have problem here.
func1(…) {
…. • Just after func1 of thread 1
status = … updated status, a thread
do_something_based_on(status); switch may occur and 2nd
} thread can run and update
status.
func2(…) {
…
status = … • Then thread 1 will run
do_something_based_on(status); again, but will work with a
} different status value.
main() { Wrong result!
….
thread_create(…, func1, …);
thread_create(…, func2, …);
}
CS342 Operating Systems - Spring 2009 49 İbrahim Körpeoğlu, Bilkent University

From Singlethread to Multithreaded

• Scope of variables:
– Normally we have: global, local
– With threads we want: global, local, thread-local

• thread-local: global inside the thread (thread-wide global), but not

global for the whole process. Other threads can not access it. But all
functions of the thread can.

• But we don’t have language support to define such variables.

– C can not do that.

• Therefore thread API has special functions that can be used to create
such variables – data.
– This is called thread specific data.

CS342 Operating Systems - Spring 2009 50 İbrahim Körpeoğlu, Bilkent University

25
 Thread Specific Data

• Allows each thread to have its own copy of data

– Each thread refers to the data with the same name.

• create_global (“bufptr”); // create pointer to such a variable

• set_global (“bufptr”, &buf); // set the pointer

• bufptr = read_global (“bufptr”); // get the pointer to access

CS342 Operating Systems - Spring 2009 51 İbrahim Körpeoğlu, Bilkent University

From Singlethread to Multithreaded

• Many library procedures that are used may not be reentrant.

• They are not designed to have a second call to the same procedure
from the same process before the procedure is completed.
– We are talking about non-recursive procedures.
• They may be using global variables. Then they are not thread-safe.

• We have to be sure that we use thread-safe library routines.

CS342 Operating Systems - Spring 2009 52 İbrahim Körpeoğlu, Bilkent University

26
 Operating System Examples

• Windows XP Threads
• Linux Thread

CS342 Operating Systems - Spring 2009 53 İbrahim Körpeoğlu, Bilkent University

Windows XP Threads

CS342 Operating Systems - Spring 2009 54 İbrahim Körpeoğlu, Bilkent University

27
 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)

CS342 Operating Systems - Spring 2009 55 İbrahim Körpeoğlu, Bilkent University

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)

CS342 Operating Systems - Spring 2009 56 İbrahim Körpeoğlu, Bilkent University

28
 Clone() and fork()

user program

library sys_fork() sys_clone()

sys_fork() sys_clone(){
{ ….
… }
kernel }

CS342 Operating Systems - Spring 2009 57 İbrahim Körpeoğlu, Bilkent University

End of lecture

CS342 Operating Systems - Spring 2009 58 İbrahim Körpeoğlu, Bilkent University

29