%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%	threads.tex
%
%		An Introduction to Multi Threaded Programming with POSIX 
%		Threads and Linux
%
%
%							Liam Widdowson
%							lbw@telstra.com
%							2001/01/11
%							Version 1.0
%	
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[a4paper, titlepage, 12pt, landscape, final]{threads}
% \usepackage{draftcopy}
\usepackage[dvips]{graphicx}
\usepackage{fancyvrb}
\author{Liam Widdowson [lbw@telstra.com]\\Hewlett-Packard Consulting}
\title{An Introduction to Multi Threaded Programming with POSIX Threads and Linux}
\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%	Title page
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\titlepage
\maketitle
\newpage
\tableofcontents
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%	Portability - General Portability
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Preface}
\subsection{General Portability}
New open source applications are being released each day. Many of the 
programmers who develop open source software may do so on a single platform 
such as Linux. Far too much open source software is not portable out of 
the box. Such software typically requires non-trivial changes to compile
or work reliably on other operating systems.
\newline
\newline
Portability is a key component to producing good quality, reliable software. 
Developing and testing software on multiple platforms helps iron out 
obscure bugs that many seldom be seen on a single hardware architecture or 
operating system.
\newline
\newline
It is a disservice to the developer's efforts if no attempt is made 
to make software portable. Wherever possible, a developer should use
what is available in the POSIX APIs and not unnecessarily use operating 
system specific system calls or third party libraries. If system specific 
functions must be used, they should be placed in pre-processor condition 
statements. When designing software, thought should be given to how the
software may behave on other software and hardware platforms (e.g different 
byte order). 
\newpage
Our great and fearless leader Linus Torvalds one said:
\begin{quote}
\emph{Porting this new operating systems to other platforms was really 
not on my mind at the beginning. At first I just wanted something that would run
on my 386} \cite{O-A:DIB99}
\end{quote}
It is important that developers do not fall into the same trap as Linus 
did. This oversight meant that a great deal of internal re-development was
required to get Linux to a state where it could be ported in a straight forward
manner. Most of the popular open source software has been extensively ported 
to other platforms (e.g Sendmail, BIND, NetBSD). It could indeed be argued that 
portability is a key component to the success of a particular piece of software. 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%	Portability - Pthreads Portability
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{POSIX Threads Portability}
Portability is imperative when developing with POSIX threads. The POSIX
thread API abstracts its data types from the underlying data 
storage structures. 
Developers should never make any assumptions in regards to how 
POSIX thread data types, the scheduler or the threading model are implemented
by the vendor.
All POSIX thread data types should be considered \emph{opaque} \cite{A-W:BUT97}.
\newline
\newline
The importance of portability will become more apparent as we delve further
into POSIX threads.
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%	Introduction
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
\subsection{Definition}
In a general sense a thread can be considered as a scheduling entity. 
More specifically consider a thread as an independent flow of control within 
a scheduling entity. In a typical Unix implementation, a thread will share 
the same address space, file descriptors, text and data segments of its 
parent process. Each thread has its own private stack, register context and 
program counter.  

\subsection{Brief History}
The concept of a thread (as an independent flow of control) dates back to 1965
with the Berkeley Timesharing System. However, at that time they were known
as processes, not threads \cite{A-P:DIJ65}. Processes interacted with
what would now be considered traditional Inter-Process Communication (IPC)
means such as semaphores and message passing.
One of the first thread implementations was developed on Multics at 
Bell Laboratories during early 1970.
It used multiple stacks in a single process to support multiple background
compilations \cite{I-N:OSU96}.
In the early 1980s, micro-kernel based operating systems such as Amoeba and
Chorus provided \emph{lightweight processes} that shared the address space 
of a single standard process \cite{I-N:OSU96}. 
\newpage
Threads as we have come to know them today were created as a part of the 
Open Software Foundation's Distributed Computing Environment. 
OSF's DCE threads is a complete user space implementation 
based on an early POSIX threads draft. It has been ported extensively to 
many operating systems thanks to its modular design. DCE could typically be 
ported to a new operating system in a matter of days with 
\emph{some assembly required} for context switch routines \cite{A-W:BUT97}. 
Today, threads are defined by the POSIX 1003.1c-1995 standard. Extensions 
to the standard have been defined by The Open Group as part of the Single 
UNIX Specification V2. Additionally, many vendors have added non-portable
system specific extensions.

\subsection{Motivation}
Most non-trivial applications must perform several tasks at once. Of
those applications some or all of those tasks may be independent of each 
other and may lend themselves to parallel execution. A mail transport agent 
provides an excellent example - a traditional implementation uses a listener 
process that waits for requests and \emph{forks} a new process to 
service each new client. Such an architecture has some disadvantages - forking 
each process adds significant overhead as \emph{fork(2)} is an expensive 
system call (even if copy-on-write functionality is provided within the kernel)
\cite{P-H:VAH96}.
As each process has it's own address space it must use standard IPC 
facilities such as semaphores or shared memory to communicate. Some of these 
calls are relatively expensive and retard the application's performance.
\newpage
Threads address many of the aforementioned issues. Threads have a common
address space which provides simplified data sharing and lightweight 
process creation. 
Additionally, threading environments provide advanced data types which
assist in providing a more natural style of parallel programming.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%	Thread Models
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Thread Models}
There are three generally accepted models used in the implementation of 
threads on Unix variant operating systems. Each model has its own set 
of advantages and disadvantages. The following section examines the
three models.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%	Thread Models - User Land Threads
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{User Space Threads}
\subsubsection{Overview}
A multi-threading sub system may be implemented entirely in user space. This
model is typically referred to as M x 1 threads (i.e M user space threads are 
contained within one kernel space scheduling entity). Typically, 
implementations of this model are based on the POSIX threads draft 4. 
OSF's DCE is one such implementation.  A user space library creates, 
terminates, schedules and synchronises threads.  These threads are not 
directly visible to the kernel, in fact, the kernel is unaware that 
the single process which holds the threads is any different from other processes.
\newline
\newline
This model provides a performance benefit as each thread context switch 
does not traverse the user/kernel space boundary. However, there are also 
disadvantages associated with this model - All threads reside within a single 
kernel space scheduling entity (typically a Unix process). This means 
that a only single processor may be utilised to schedule all threads. 
Within uni-processor environments this may not represent a significant 
issue, however in multi-processor environments this model may be
unacceptable.
\newline
\newline
Further, if a single thread blocks on a system call such as \emph{read(2)}, 
the entire process and all associated threads block. Many user space 
libraries help alleviate this problem by using non-blocking I/O. However, 
there are still performance and compatibility issues associated 
with this work-around (e.g not all interfaces support non-blocking I/O).
\newline
\newline
Essentially, a user-space thread library can provide 
\emph{concurrency} (i.e the appearance of multiple tasks being performed at
once) but can never provide \emph{parallelism} (i.e multiple tasks performed
at the same instance in time on separate processors). 
\newline
\newline
Operating systems which implement this threading model include: 
\newline
FreeBSD and OpenBSD
\newpage
\subsubsection{Architecture}
\lineskip .75em%
\begin{center}
\includegraphics[angle=0, width=13.5cm]{user-space-threads.eps}%
\end{center}
%%%% table
\begin{center}
\begin{tabular}{|p{6.25cm}|p{6.25cm}|} 
\hline
\emph{Advantages} & \emph{Disadvantages} \\
\hline
Context-switches performed entirely in user mode &
Poor performance due to blocking system calls and/or associated code complexity to 
avoid them \\
\hline
Straight forward implementation &
Unable to use multiple processors \\
\hline
\end{tabular}
\end{center}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%	Thread Models - Kernel Land Threads
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\subsection{Kernel Space Threads}
\subsubsection{Overview}
Unlike user space threads which do not involve any thread specific kernel
interaction, kernel space threads rely on it. The kernel space
thread model is often referred to as the 1 x 1 thread model (i.e one thread 
maps to one kernel space entity). Typically, implementations may map
each single thread to a single kernel entity such as a standard Unix 
process or a more lightweight \emph{kernel thread}.
\newline
\newline
Each thread is scheduled independently by the kernel scheduler so if a
thread blocks it will not effect any other thread. However, creation,
synchronisation and termination of kernel threads may suffer some performance
problems when compared to user space threads. The kernel must be 
involved in operations such as requesting a memory lock or thread
scheduling. Further, each kernel thread
or process takes up valuable kernel resources which inhibits the creation
of a large number of threads (most operating systems will only
allow an arbitrary number of threads to be created system wide).
Whilst the overhead may be greater, kernel threads do offer true 
\emph{parallelism} as each thread may run independently on separate 
physical processors.
\newline
\newline
Operating systems which implement this threading model include: 
\newline
HP-UX 11 and Linux
\newpage
\subsubsection{Architecture}
\begin{center}
\includegraphics[angle=0, width=13cm]{kernel-space-threads.eps}%

%%%% table
\begin{tabular}{|p{6.25cm}|p{6.25cm}|} 
\hline
\emph{Advantages} & \emph{Disadvantages} \\
\hline
Able to use multiple processors &
Context switches performed entirely in kernel mode \\
\hline
Improved performance when coping with blocked system calls, etc &
Decreased performance with large number of threads \\
\hline
\end{tabular}
\end{center}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%	Thread Models - T x N Threads
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\subsection{Kernel and User Space Threads}
\subsubsection{Overview}
Kernel and user space threads are often referred to as M x N threads 
(i.e M user space threads within N kernel entities). The kernel and user space 
threading model provides a ``best of both worlds'' approach. 
\newline
\newline
This model requires co-operation between the kernel scheduler and a user space
thread library/scheduler. Essentially, sets of threads are 
\emph{bound} to individual kernel entities. This allows the majority of 
context-switches to occur in user mode whilst still using multiple 
kernel entities to provide \emph{parallelism}. For example, an application 
may have
nine threads which are spread across four kernel entities. This would allow
the application to take advantage of multi-processor hardware whilst still
traversing the user-kernel boundary as little as possible. In situations
where a thread blocks in a system call, another thread is immediately 
scheduled thus not halting the execution of threads that are bound to 
the same kernel entity. 
\newline
\newline
Operating systems which implement this threading model include: 
\newline
IRIX, Solaris and Tru64
\newpage

\subsubsection{Architecture}
\begin{center}
\includegraphics[angle=0, width=11.75cm]{kernel-and-user-space-threads.eps}%
%%%% table
\newline
\begin{tabular}{|p{6.25cm}|p{6.25cm}|} 
\hline
\emph{Advantages} & \emph{Disadvantages} \\
\hline
Able to use multiple processors &
Complex system implementation \\
\hline
Improved performance with blocked system calls, etc &
\\
\hline
Most context switches in user mode &
\\
\hline
\end{tabular}
\end{center}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%	Linux thread model
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\section{LinuxThreads}
\subsection{Overview}
Linux implements the 1 x 1 kernel space threading model. Thread creation at 
a kernel level is performed with \emph{clone(2)} system call. Under
Linux, the \emph{clone(2)} system call is a generalisation of
\emph{fork(2)}. Thus a thread under Linux is
not significantly different from a standard heavy-weight Unix process. 
When a process creates its first thread, a total of  
three threads will be active. The initial or \emph{main()} thread (process), 
the newly created thread and a manager thread which helps performs scheduling 
activities. This is significantly different from implementations such as Solaris 
and Tru64 which have separate kernel and user space entities to represent 
threads.
\newline
\newline
Linux's kernel developers have made a specific decision to support this model as
they believe it removes the complexity associated with
implementing another entity and scheduler within the kernel. Threads are
created, terminated and scheduled by the same code that does so for 
processes. Apart from providing simplicity, the rationale behind this
architecture choice is that Linux has exceptionally fast context-switch code 
and this negates what is one of the biggest problems associated with 1 x 1 
implementations - context switch performance.
However, this simplicity comes with an inherent problem - Linux
will never truly be POSIX 1003.1c-1995 compliant without specific
support within the kernel for threads.
\newline
\newline
It is for this reason that threads under Linux do not provide a significant
performance benefit as they do on other platforms. Nonetheless, threads
provide a more natural parallel style suitable for parallel programming. However, 
keep in mind portability - a threaded application will perform significantly
better than a forking application on most other operating systems. 

\subsection{Simple Kernel Threads Example}
The following source code was posted by Linus Torvalds to the Linux
kernel mailing list in 1996. It provides a basic example of how the
\emph{clone(2)} system call may be used to implement kernel threads. 
\VerbatimInput[fontsize=\footnotesize, frame=lines, numbers=left,
		label={[linux-clone.c - Linus Torvalds]linux-clone.c},
		resetmargins=true]{code/linux-clone.c}
The output from Linus' threading example is as follows:

\begin{Verbatim}[fontsize=\footnotesize]
mother:  fd = 3
mother:  vm = 10
child:   got argument 3 as fd
child:   vm = 5
mother:  vm = 5
mother:  child closed our file descriptor
\end{Verbatim}


\subsection{Developing with LinuxThreads}
A variety of threading libraries (including user space implementations)
have been developed for Linux. However, the defacto 
standard library is now LinuxThreads. LinuxThreads 0.8 provides a mostly
compliant POSIX 1003.1c implementation and forms part of glibc 2.x.
Linux initially diverges from the POSIX standard with one fundamental 
difference - each thread has an independent PID. This occurs because each
thread is essentially a standard Unix process pretending to be a 
thread. POSIX requires that all threads in a process share a single PID. 
In turn, this violation effects the behavior of \emph{fork(2)} and signals,
none of which are entirely POSIX compliant.  
\newline
\newline
The following are minimum requirements for developing threaded software with Linux:
gcc 2.8, gdb 4.18, LinuxThreads 0.8, glibc 2.0.1 and kernel 2.x
\newline
\newline
The following table provides examples of common linker and 
compiler flags required when compiling POSIX threaded software:
\begin{center}
\begin{tabular}{|p{2cm}|p{7cm}|p{3cm}|}
\hline
\emph{Utility} & \emph{Parameter} & \emph{Platform} \\ 
\hline
ld & -lpthread & All platforms \\ 
\hline
gcc/cc & -D\_REENTRANT & All platforms \\
& -pthread & Free/OpenBSD \\ 
& -D\_POSIX\_C\_SOURCE=199506L & HP-UX \\ 
& -mt (SunSoft CC only) & Solaris \\ 
\hline
\end{tabular}
\end{center}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%	Programming with POSIX threads
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\section{Programming with POSIX threads}
This Section outlines how POSIX threads functions and data types
may be used to create multi threaded applications. Within Section
\ref{Sec:threadcreation}
performance comparisons will be made between a forking
and threaded example application on Linux, Solaris and FreeBSD. This 
comparison is by no means a definitive benchmark, however, it does provide
some insight into the performance benefits of threaded applications.
The following systems were used to test each piece of code. 
\newline
\newline
%%%% table
\begin{tabular}{|p{2.2cm}|p{3.3cm}|p{4.8cm}|p{1.4cm}|} 
\hline
\emph{Hostname} & \emph{Operating System} & \emph{Processor(s)} & \emph{Memory} \\
\hline
athena & Linux 2.2.17 & AMD K6-2/300MHz & 64MB \\
fatso & FreeBSD 4.2 & Intel 100MHz Pentium & 32MB \\
helios & Solaris 8 & 160MHz TuroboSPARC & 96MB \\
prometheus & Solaris 8 & 2 x 150MHz HyperSPARC & 256MB \\
\hline
\end{tabular}
\subsection{POSIX thread facilities}
In addition to providing facilities to create, terminate and synchronise
threads and shared data, POSIX threads implementations should provide 
features such as:
\begin{quote}
- A per-thread \emph{errno} global variable;
\newline
- Thread safe versions of functions such as \emph{malloc(3)} and
\emph{free(3)}.
\end{quote}
%%%%%% simple thread creation
\newpage
\subsection{POSIX thread creation}
\label{Sec:threadcreation}
A POSIX thread is created using the \emph{pthread\_create()} function.
This function is defined as:
\begin{Verbatim}[fontsize=\footnotesize]
	int pthread_create(pthread_t *thread_id, pthread_attr_t *attr, 
			void *(*startroutine)(void *), void *arg)
\end{Verbatim}
The \emph{pthread\_create()} function returns 0 upon success, ENOMEM if there are insufficient
resources to create the thread, EINVAL if the attributes are invalid
or EPERM if there are insufficient priviladges to create the thread.
\newline
\newline
The \emph{thread\_id} pointer stores the thread's unique identifier 
(analogous to a process PID), \emph{attr} stores the attributes that the new 
thread should possess upon creation and \emph{startroutine} points to the 
function that 
should be called upon thread creation. Finally, \emph{arg} is a pointer to 
data which 
should be supplied as an argument to \emph{startroutine}.  Note, only one 
argument is allowed so multiple data objects may be placed within a struct.
\newline
\newline
Functions which are called by \emph{pthread\_create()} should be of the
form:
\begin{Verbatim}[fontsize=\footnotesize]
	void *function(void *argument);
\end{Verbatim}
The argument may then be re-cast at a later date to the desired type.
When a thread wishes to exit, it may do so in a variety of ways - 
either via a \emph{return} statement or by calling
the following function:
\begin{Verbatim}[fontsize=\footnotesize]
	void pthread_exit(void *value_ptr);
\end{Verbatim}
\newpage
The value of the exiting thread is lost unless the caller waits for it with the 
following function:
\begin{Verbatim}[fontsize=\footnotesize]
	void pthread_join(pthread_t thread_id, void *value_ptr);
\end{Verbatim}
The \emph{pthread\_join()} function is analogous to \emph{waitpid(2)} for processes.
\newline
\newline
Thread attributes are set by the \emph{pthread\_attr\_*()} routines and 
define details such as what state the thread should begin execution in, 
scheduling information, etc. If NULL is specified as an argument to 
\emph{pthread\_create()}, the thread 
will be created with a default set of attributes.
An examination of all pthread attributes is beyond the scope of this 
paper, but one noteworthy attribute must be mentioned. 
When a thread exits, its resources are not automatically
\emph{recycled}. The thread will continue to exist in a 
zombie state until it is joined with \emph{pthread\_join()}. 
\newline
\newline
However, in some situations it may not be convenient to use 
\emph{pthread\_join()}.
The thread's id may be lost, the caller may not wish to collect the
thread's return value or suspend its execution while it waits
for the thread to finish. In such a case, the thread may be created with 
the PTHREAD\_CREATE\_DETACHED attribute set. This will create the thread in
a detached state. When the thread exits all resources will be automatically
\emph{recycled}. 
\newpage
The attribute may be set with code such as the following
or by calling the \emph{pthread\_detach(pthread\_t *thread\_id)} function 
at any time:
\begin{Verbatim}[fontsize=\footnotesize]
	pthread_attr_t  attr;
	pthread_t       t;

	pthread_attr_init(&attr);
	pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_DETACHED);
	pthread_create(&t, &attr, some_function(), (void *) some_arg);
	.. 
	or
	.. 
	pthread_detach(&t1)

\end{Verbatim}
A thread that is detached can never be joined again with \emph{pthread\_join()}.
It is also worth mentioning again, that all pthread data types are 
\emph{opaque}. One should never make any assumptions about the underlying 
data types. Further, the result of copying pthread data variables is
undefined as is performing arithmetic (e.g equality) operations upon them.
In order to check if two \emph{pthread\_t} thread IDs are the same, 
the following function should be used:
\begin{Verbatim}[fontsize=\footnotesize]
	int pthread_equal(pthread_t thread0, pthread_t thread1);
\end{Verbatim}
The \emph{pthread\_equal()} function returns a non-zero value if the thread IDs
are equal, otherwise zero is returned.
\newline
\newline
A thread's thread identifier may be retrieved at any time by using the 
following function:
\begin{Verbatim}[fontsize=\footnotesize]
	pthread_t pthread_self(void);
\end{Verbatim}


The following code demonstrates thread creation by creating a 
pre-defined number of threads and prints a message from each. To contrast,
a forking version is provided.  
\subsubsection{Threaded version}
\VerbatimInput[fontsize=\footnotesize, frame=lines, numbers=left,
		label={[test2-thread.c]test2-thread.c},
		resetmargins=true]{code/test2-thread.c}
\subsubsection{Forking version}
\VerbatimInput[fontsize=\footnotesize, frame=lines, numbers=left,
		label={[test2-process.c]test2-process.c},
		resetmargins=true]{code/test2-process.c}
\newpage
\subsubsection{Performance Comparison Graph}
\label{Sec:performance+comparison+graph}
The following graph displays the time taken by the threaded and forking 
test code. Note that the Y axis represents time using a logarithmic scale.
\includegraphics[angle=0]{test2-combined.eps}%
\newpage
\subsubsection{Performance Comparison Analysis}
It is evident from the data provided that threaded applications perform
significantly better.  On Solaris, the threaded application performed 
its tasks almost twenty times faster than the forking version. It spent
almost half as much time in user mode and sixteen times less 
time in kernel mode. Attention should be paid to the difference in
results between the single and multi-processor Solaris machines. The
multi-processor machine spent slightly more time in kernel mode and
slightly less in user mode. This is because some of the threads could
run on different processors thus slightly more kernel intervention was 
required for context switching and thread creation.
\newline
\newline
On Linux, the gap was much smaller, but threads still provide a performance 
advantage finishing their tasks three times faster whilst spending five times 
less time in user mode and about the same time in kernel mode.
\newline
\newline
FreeBSD's user space threads implementation also provided 
excellent results. The threaded application performed almost ten times 
faster and spent significantly less time in both user and kernel mode.
\newline
\newline
The code used in this simple experiment does not mimic the behavior of a 
typical application
(which would be both computational and I/O bound). In such a 
situation a threading model which includes a kernel and user space 
scheduler (such as Solaris or Tru64) would most likely perform best.
\newpage
%%%%%% mutex locking
\subsection{Mutual Exclusion}
As threads share the same address space, they must possess a 
synchronisation method to ensure that shared resources are not corrupted by 
concurrent reading and writing.
POSIX threads provide a synchronisation type called a mutex. A mutex (short for
mutual exclusion) may be used to protect access to any resource.
A mutex locked within a single thread may not be unlocked by any other thread.
A thread which attempts to acquire a locked mutex will block until it is 
released. 
\newline
\newline
The mutex type within POSIX threads is \emph{pthread\_mutex\_t} and may be 
initialized at deceleration with the PTHREAD\_MUTEX\_INITIALIZER value 
or with the following function:
\begin{Verbatim}[fontsize=\footnotesize]
	int pthread_mutex_init( pthread_mutex_t *mutex,
				pthread_mutexattr_t *attr);
\end{Verbatim}
The mutex initialization returns 0 if successful, EBUSY if it
has already been initialised or EINVAL if the mutex or attributes are invalid.
\newline
\newline
A mutex may have a variety of attributes accrued to it at initialisation. 
Discussion of these attributes is beyond the scope of this paper. 
\newline
\newline
Mutexes should be used to protect multiple threads from reading \emph{or} 
writing shared data at once. In addition, a mutex should be used to protect
a non-thread safe function from multiple invocations across threads. 
\newline
\newline
The following code provides an example of how a mutex is used to 
protect stdout. When a program is linked with the pthread library, the 
library will transparently perform internal mutex locking for
functions such as \emph{malloc(3)} and buffering/locking of stdout. 
In the following code explicit mutex locking of stdout is required as 
characters are being written to stdout individually.
\newline
\VerbatimInput[fontsize=\footnotesize, frame=lines, numbers=left,
		label={[file-mutex.c]file-mutex.c},
		resetmargins=true]{code/file-mutex.c}
\newpage
The following was output from the aforementioned program:
\begin{Verbatim}[fontsize=\footnotesize]
[thread 4] http://www.linux.conf.au/
[thread 5] http://www.linux.conf.au/
[thread 4] http://www.linux.conf.au/
[thread 5] http://www.linux.conf.au/
[thread 4] http://www.linux.conf.au/
[thread 4] http://www.linux.conf.au/
[thread 5] http://www.linux.conf.au/
[thread 4] http://www.linux.conf.au/
[thread 5] http://www.linux.conf.au/
[thread 5] http://www.linux.conf.au/
\end{Verbatim}
The following was output from the aforementioned program with mutex
locking removed at lines 16 and 20. Observe that how without correct
synchronisation the data is corrupted.
\begin{Verbatim}[fontsize=\footnotesize]
[thread 5] [thread 4] http:ht//wwtp://www.w.linux.conflinu.au/x.c
onf.au/
[thread 5] http://www.linux.conf.au/
[thread 4] http://www[thread 5] http://www.linux.conf..linuxau/
.conf.au/
[thread 5] http://w[thread 4] hww.littnux.conf.au/
p://www.linux.conf.au/
[thread 4] http://www.linux.conf.au/
[thread 5] http://www.linux.conf.au/
[thread 4] http://www.linux.conf.au/
\end{Verbatim}

%%%%%% condition variables
\subsection{Signaling and Synchronisation}
Within an application, there may be times where the need arises
to signal another process or thread to begin doing some work. There may
be a queue of data that needs to be processed or a thread pool waiting to 
service a newly established connection. 
POSIX threads offers \emph{condition variables} to perform this function. 
A thread or many threads 
may wait on a particular condition and once the condition is met, one or all of 
the threads will return from their blocked state and begin their work.
\newline
\newline
Within POSIX threads, a condition variable is always associated with a mutex and
indirectly, associated with the data it is waiting upon. A condition
variable is defined by the \emph{pthread\_cond\_t} type. Like a mutex,
a \emph{pthread\_cond\_t} can be initialized either with the constant
PTHREAD\_COND\_INITIALIZER or the following function:
\begin{Verbatim}[fontsize=\footnotesize]
	pthread_cond_init(pthread_cond_t *cond, pthread_condattr_t *attr);
\end{Verbatim}
The function \emph{pthread\_cond\_init()} returns 0 if successful, EAGAIN if
insufficient resources are available or ENOMEM if insufficient memory is
available. 
\newline
\newline
Like most of the POSIX thread functions, condition variables have attributes
which may be set upon initialisation. Discussion of these attributes are 
beyond the scope of this paper.
\newline
\newline
Once initialised, a condition variable may be waited upon by using either of
the following functions:
\begin{Verbatim}[fontsize=\footnotesize]
	int pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex);

	int pthread_cond_timedwait(pthread_cond_t *cond, 
                                   pthread_mutex_t *mutex,
                                   struct timespec *wait_time);
\end{Verbatim}
The above functions will return 0 upon success, EINVAL if either the mutex
or condition variable are invalid or ETIMEOUT if 
\emph{pthread\_cond\_timedwait()} returns from the timed wait without the
condition variable changing state.
\newline
\newline
Before calling either of the above functions, a thread must have the 
associated data mutex locked. The function will internally unlock the mutex
to allow other operations to occur, but once the condition has been signaled
the function will return with the mutex locked. 
\newline
\newline
In order to wake a thread or threads waiting upon a condition variable,
one of the following functions may be used:
\begin{Verbatim}[fontsize=\footnotesize]
	int pthread_cond_signal(pthread_cond_t *cond);

	int pthread_cond_broadcast(pthread_cond_t *cond);
\end{Verbatim}
The \emph{pthread\_cond\_signal()} function will only wake a single thread 
whilst \emph{pthread\_cond\_broadcast()} will wake all waiting threads. The
above functions return 0 upon success or EINVAL if the condition variable
has not been initialised. The following code demonstrates how a condition 
variable may be used:
\VerbatimInput[fontsize=\footnotesize, frame=lines, numbers=left,
		label={[cond-wait.c]cond-wait.c},
		resetmargins=true]{code/cond-wait.c}
The following was output from the aforementioned program:
\begin{Verbatim}[fontsize=\footnotesize]
[thread 5] enter string: hello
[thread 4] user said: hello
[thread 5] enter string: world
[thread 4] user said: world
[thread 5] enter string: q
[thread 4] goodbye!
\end{Verbatim}

%%%%%% signal handling 
\subsection{UNIX Signal handling}
Signal handling can become complex within a multi-threaded application and
should, where possible, be avoided.
The POSIX thread standard states that application generated signals are 
sent to any thread within that application. This means that if a SIGCHLD 
is raised by a child process, it may not be delivered to the thread 
that originally created that child. However, the signals SIGFPE, SIGSEGV, 
SIGPIPE and SIGTRAP are always delivered to the thread that caused them
\cite{A-W:BUT97}.
\newline
\newline
Despite signals being sent to individual threads, they do effect the process 
as a whole. Unless the relevant signal handler is installed, a signal such as 
SIGSEGV (whether sent to an individual thread or the process) results in the 
entire process being killed and a core file generated.
\newline
\newline
As mentioned previously, LinuxThreads signal handling differs 
significantly from the POSIX standard. According to the POSIX standard, 
external signals generated from a command such as \emph{kill} should be 
sent to the process which in turn delivers it to any thread that does 
not block the signal. Since a thread within Linux is in fact a process, 
the external signal will be delivered to that particular process. 
If another thread is blocked in \emph{sigwait(2)} waiting for that external 
signal, it will remain blocked. Additionally, SIGUSR1 and SIGUSR2 
may not be used within a threaded application under Linux as they are used 
internally by LinuxThreads.
\newline
\newline
On POSIX compliant systems the preferred signal handling method is to 
create a thread specifically for signal handling. The required signals
should be masked in all other threads by using the following function:
\begin{Verbatim}[fontsize=\footnotesize]
	int pthread_sigmask(int how, sigset_t *set, sigset_t *oset);
\end{Verbatim}
The \emph{pthread\_sigmask()} function returns 0 upon success and a non-zero
value upon error. A thread inherits the signal masks of its creator. It is 
therefore possible to set signal masks of all threads by specifying them 
in \emph{main()} before creating any threads.
\newline
\newline
Once all threads other than the signal handling thread have the signal 
masked, the handler thread may wait for the signal with \emph{sigwait()} 
and perform the appropriate processing when necessary.
\newline
\newline
However, in order to process external signals in a portable fashion on Linux, 
a signal handler should be installed process wide with either \emph{signal(2)}
or \emph{sigaction(2)}. The code executed within a signal handler is not 
async-safe so it is generally necessary to wake a thread (using Sys V IPC) 
to perform the required operations once a signal has been received.
\newline
\newline
The following code outlines how a portable external signal handler may be 
implemented:
\newpage
\VerbatimInput[fontsize=\footnotesize, frame=lines, numbers=left,
		label={[signals.c]signals.c},
		resetmargins=true]{code/signals.c}
%%%%%% One time operations
\subsection{One time operations}
Sometimes within a threaded program, it is useful to execute an operation
only once within a thread, no matter how many times it is invoked. This
may include operations such as initialising a mutex with the 
\emph{pthread\_mutex\_init()} function. This may be performed by 
declaring a variable of type \emph{pthread\_once\_t} which must be initialized 
with the value PTHREAD\_ONCE\_INIT. It is then possible to perform an 
operation a guaranteed single time by using the following function:
\begin{Verbatim}[fontsize=\footnotesize]
	int pthread_once(pthread_once_t *once, void (*once_routine,  void)););
\end{Verbatim}
\emph{once\_routine} is the pointer of the function to be called. Note, no 
argument can be given to the function unlike with 
\emph{pthread\_create\_thread()}. The function \emph{pthread\_once()} returns 
0 if successful or EINVAL if either the supplied routine or 
\emph{pthread\_once\_t} are invalid. 
\newline
\newline
The following code illustrates how 
\emph{pthread\_once()} may be used:
\VerbatimInput[fontsize=\footnotesize, frame=lines, numbers=left,
		label={[do-once.c]do-once.c},
		resetmargins=true]{code/do-once.c}

%%%%%%% Cancellation
\subsection{Thread Cancellation}
In many situations, a programmer may wish to stop a thread's 
operation and ensure that it shuts down cleanly. An example would be ensuring
a dbm database is closed correctly with \emph{dbm\_close(3)} before an
application is shut down or unlocking shared mutexes when the thread is 
shutdown or restarted. It would be possible, but messy to implement
such a signaling method using UNIX signals or condition variables. Fortunately, 
POSIX threads provides a set of cancellation functions which many be used to 
shutdown a thread cleanly.
\newline
\newline
In order for a thread to be canceled, it must first declare that it is
able to be canceled by calling the following functions:
\begin{Verbatim}[fontsize=\footnotesize]
	int pthread_setcancelstate(int state, int *oldstate);

	int pthread_setcanceltype(int type, int *oldtype);
\end{Verbatim}
POSIX threads provides two types of cancellation - deferred and asynchronous.
A thread using deferred cancellation will only allow cancellation at
specific cancellation points. Cancellation points include various system
and function calls including \emph{read(2), pthread\_cond\_wait()}, etc. 
Consult the relevant vendor's operating system documentation for all supported 
cancellation points. Additionally, POSIX threads defines the following
function:
\begin{Verbatim}[fontsize=\footnotesize]
	void pthread_testcancel();
\end{Verbatim}
This function may be used to test whether cancellation is required at 
any point within an application. It is particularly useful for allowing
cancellation from a hard loop without any system cancellation points.
\newline
\newline
Asynchronous cancellation allows the thread to be canceled
at any time without encountering a cancellation point. Use of asynchronous 
cancellation is not encouraged as it may potentially leave resources
in an unknown state.
\newline
\newline
Once cancellation has been enabled within a thread, the following 
functions may be used to define and place a ``clean up function'' on the
cancellation stack:
\begin{Verbatim}[fontsize=\footnotesize]
	void pthread_cleanup_push(void (*handler, void *), void *arg);

	void pthread_cleanup_pop(int execute);
\end{Verbatim}
Note, in order for the application to compile, use of 
\emph{pthread\_cleanup\_push()} requires that a matching 
\emph{pthread\_cleanup\_pop()} is placed within the same caller function. 
\newline
\newline
If multiple cleanup handlers are placed upon the cleanup stack, they will
be called in LIFO order once a cancellation request is received.
In order to send a cancellation request, the following function is defined:
\begin{Verbatim}[fontsize=\footnotesize]
	int pthread_cancel(pthread_t thread);
\end{Verbatim}
The \emph{pthread\_cancel()} function returns 0 upon success or ESRCH if
no such thread exists. The following code provides an example of deferred
cancellation:
\VerbatimInput[fontsize=\footnotesize, frame=lines, numbers=left,
		label={[cancel.c]cancel.c},
		resetmargins=true]{code/cancel.c}

%%%%%% Forking and threads
\subsection{Forking and Threads}
The use of \emph{fork(2)} within a threaded application should be avoided
unless it is used only to invoke another program with \emph{exec(2)}. The
POSIX standard states that only the thread which calls \emph{fork(2)} will
exist in the child. Additionally, it will own all the mutexes and have the
same values for thread specific data as it did before the \emph{fork(2)}.
Additionally, to assist in performing cleanup operations before a fork, 
POSIX threads provide the following function (which is analogous to 
\emph{atexit(2)}):
\begin{Verbatim}[fontsize=\footnotesize]
	int pthread_atfork(void (*prepare)(void),  void  (*parent)(void), 
                           void (*child) (void));
\end{Verbatim}
The function returns 0 if successful or ENOMEM if insufficient memory is
available. The \emph{pthread\_atfork()} function allows a specified 
function to be called within a thread prior to \emph{fork(2)} being called.
This allows a thread to unlock any required mutexes and protect itself
from a deadlock situation in the child. All threaded software which 
executes non-trivial code within a child process should use 
\emph{pthread\_atfork()}.
\newline
\newline
Linux diverges from the POSIX standard in regards to the behavior of 
\emph{fork(2)} within a threaded program. A portable method to use
\emph{fork(2)} safely on Linux and other operating systems is to create a 
``fork thread'' which listens for requests and calls \emph{fork(2)} 
and \emph{wait(2)} on behalf of other threads. 
%%%%%% Making existing libraries thread safe
\subsection{Using Non-thread Safe Functions}
Whilst thread safe versions of many standard POSIX functions 
(such as \emph{strtok\_r()} have been added with the advent of threads, 
many non-thread safe functions still exist either in third party libraries
or within libc. Functions such as \emph{bufsplit()} can still be used
within a threaded program but must be protected by a mutex. The following
code provides an example of how such a function may be used:
\begin{Verbatim}[fontsize=\footnotesize]

	... 
	pthread_mutex_t bufsplit_mutex = PTHREAD_MUTEX_INITIALIZER;
	char **st[3];
	char *buf;

	buf = strdup("root:x:0:0::/:/sbin/sh");

	pthread_mutex_lock(&bufsplit_mutex);
	bufsplit(":", 0, NULL);
	bufsplit(buf, (size_t) 2, st);
	pthread_mutex_unlock(&bufsplit_mutex);
	... 
\end{Verbatim}

Third-party libraries should have their function interfaces modified 
accordingly to follow the standard of functions such as 
\emph{strtok\_r()} where any persistent data is passed as an argument
to the function. However, in many cases it may not be possible to alter
the interface a function presents to the outside world. In such a situation
POSIX thread specific data may be of assistance. Essentially, thread specific
data allows the same data structure to be used by multiple 
threads but each thread has it's own instance of the data and its own
associated value. However, due to it's complex nature, detailed
discussion of thread specific data is beyond the scope of this paper.

\subsection{Advanced Threading Topics Not Covered}
%%%%% Advanced threading subjects not covered
Much of the advanced multi-threading functionality provided within
the POSIX standard has not been discussed within this paper. Specifically, 
thread, mutex and condition variable attributes provide the ability to 
control how such data types 
behave and what functionality they provide (e.g mutexes shared across
multiple processes, etc). The standard also provides real time
extensions that provide functionality to alter scheduling characteristics 
of an application and its threads.  Further information can be sought from 
threading texts, vendor documentation or the standard itself.
\newline
\newline
Additionally, The X/Open Group have provided extensions to the POSIX thread
standard as part of their UNIX98 specification. The most noteworthy 
extension is the inclusion of read/write locks with the 
\emph{pthread\_rwlock\_*()} set of functions. These provide mutex like
functionality whilst allowing a distinction between reader and
writer threads thus allowing many threads to concurrently access a resource 
whilst allowing only a single thread to perform updates.
\newpage
\section{Acknowledgments}
The author would like to thank the following people for reviewing and 
providing amendments to this paper:
\newline
\newline
David Luyer
\newline
\emph{Pacific Internet, Australia}
\newline
\newline
John Ferlito
\newline
\emph{Bulletproof Networks, Australia}
\newline
\newline
Nic Grant
\newline
\emph{Tripfinder Limited, Ireland}
\newline
\newline
Philip Dell
\newline
\emph{Hewlett-Packard Consulting, Australia}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%	Bibliography
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\begin{thebibliography}{1}

\bibitem{O-A:DIB99}
Chris DiBona, Sam Ockman and Mark Stone (editors)
\newline Open Sources - Voices from the Open Source Revolution
\newline O'Reilly and Associates, 1999

\bibitem{A-W:BUT97}
David R. Butenhof
\newline Programming with POSIX Threads
\newline Addison-Wesley, 1999

\bibitem{A-P:DIJ65}
E. W. Dijkstra, F. Genuys (editor)
\newline Cooperating sequential processes, Programming languages
\newline Academic Press, 1968

\bibitem{I-N:OSU96}
Brian O'Sullivan
\newline comp.os.research FAQ
\newline http://www.serpentine.com/~bos/os-faq/, 1996

\bibitem{P-H:VAH96}
Uresh Vahalia
\newline UNIX Internals - The New Frontiers
\newline Prentice Hall, 1996

\end{thebibliography}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}
