Home | Libraries | People | FAQ | More |
Copyright © 2001-2003 William E. Kempf
Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose is hereby granted without fee, provided that the above copyright notice appear in all copies and that both that copyright notice and this permission notice appear in supporting documentation. William E. Kempf makes no representations about the suitability of this software for any purpose. It is provided "as is" without express or implied warranty.
Table of Contents
Boost.Threads allows C++ programs to execute as multiple, asynchronous, independent threads-of-execution. Each thread has its own machine state including program instruction counter and registers. Programs which execute as multiple threads are called multithreaded programs to distinguish them from traditional single-threaded programs. The glossary gives a more complete description of the multithreading execution environment.
Multithreading provides several advantages:
Programs which would otherwise block waiting for some external event can continue to respond if the blocking operation is placed in a separate thread. Multithreading is usually an absolute requirement for these programs.
Well-designed multithreaded programs may execute faster than single-threaded programs, particularly on multiprocessor hardware. Note, however, that poorly-designed multithreaded programs are often slower than single-threaded programs.
Some program designs may be easier to formulate using a multithreaded approach. After all, the real world is asynchronous!
Beyond the errors which can occur in single-threaded programs, multithreaded programs are subject to additional errors:
Deadlock (sometimes called "deadly embrace")
Priority failures (priority inversion, infinite overtaking, starvation, etc.)
Every multithreaded program must be designed carefully to avoid these errors. These aren't rare or exotic failures - they are virtually guaranteed to occur unless multithreaded code is designed to avoid them. Priority failures are somewhat less common, but are nonetheless serious.
The Boost.Threads design attempts to minimize these errors, but they will still occur unless the programmer proactively designs to avoid them.
Multithreaded programs are non-deterministic. In other words, the same program with the same input data may follow different execution paths each time it is invoked. That can make testing and debugging a nightmare:
Failures are often not repeatable.
Probe effect causes debuggers to produce very different results from non-debug uses.
Debuggers require special support to show thread state.
Tests on a single processor system may give no indication of serious errors which would appear on multiprocessor systems, and visa versa. Thus test cases should include a varying number of processors.
For programs which create a varying number of threads according to workload, tests which don't span the full range of possibilities may miss serious errors.
Although it might appear that multithreaded programs are inherently unreliable, many reliable multithreaded programs do exist. Multithreading techniques are known which lead to reliable programs.
Design patterns for reliable multithreaded programs, including the important monitor pattern, are presented in Pattern-Oriented Software Architecture Volume 2 - Patterns for Concurrent and Networked Objects[SchmidtStalRohnertBuschmann]. Many important multithreading programming considerations (independent of threading library) are discussed in Programming with POSIX Threads[Butenhof97].
Doing some reading before attempting multithreaded designs will give you a head start toward reliable multithreaded programs.
Warning: Multithreaded programs such as those using Boost.Threads must link to thread-safe versions of all runtime libraries used by the program, including the runtime library for the C++ Standard Library. Failure to do so will cause race conditions to occur when multiple threads simultaneously execute runtime library functions for new, delete, or other language features which imply shared state.
Certain C++ Standard Library functions inherited from C are particular problems because they hold internal state between calls:
rand
strtok
asctime
ctime
gmtime
localtime
It is possible to write thread-safe implementations of these by using thread specific storage (see boost::thread_specific_ptr), and several C++ compiler vendors do just that. The technique is well-know and is explained in [Butenhof97].
But at least one vendor (HP-UX) does not provide thread-safe implementations of the above functions in their otherwise thread-safe runtime library. Instead they provide replacement functions with different names and arguments.
Recommendation: For the most portable, yet thread-safe code, use Boost replacements for the problem functions. See the Boost Random Number Library and Boost Tokenizer Library.
Boost.Threads destructors never throw exceptions. Unless otherwise specified, other Boost.Threads functions that do not have an exception-specification may throw implementation-defined exceptions.
In particular, Boost.Threads reports failure to allocate storage by throwing an exception of type std::bad_alloc or a class derived from std::bad_alloc, failure to obtain thread resources other than memory by throwing an exception of type boost::thread_resource_error, and certain lock related failures by throwing an exception of type boost::lock_error.
Rationale: Follows the C++ Standard Library practice of allowing all functions except destructors or other specified functions to throw exceptions on errors.
Boost.Threads classes documented as meeting the NonCopyable requirement disallow copy construction and copy assignment. For the sake of exposition, the synopsis of such classes show private derivation from boost::noncopyable. Users should not depend on this derivation, however, as implementations are free to meet the NonCopyable requirement in other ways.
Definitions are given in terms of the C++ Standard [ISO98]. References to the standard are in the form [1.2.3/4], which represents the section number, with the paragraph number following the "/".
Because the definitions are written in something akin to "standardese", they can be difficult to understand. The intent isn't to confuse, but rather to clarify the additional requirements Boost.Threads places on a C++ implementation as defined by the C++ Standard.
Thread is short for "thread of execution". A thread of execution is an execution environment [1.9/7] within the execution environment of a C++ program [1.9]. The main() function [3.6.1] of the program is the initial function of the initial thread. A program in a multithreading environment always has an initial thread even if the program explicitly creates no additional threads.
Unless otherwise specified, each thread shares all aspects of its execution environment with other threads in the program. Shared aspects of the execution environment include, but are not limited to, the following:
Static storage duration (static, extern) objects [3.7.1].
Dynamic storage duration (heap) objects [3.7.3]. Thus each memory allocation will return a unique addresses, regardless of the thread making the allocation request.
Automatic storage duration (stack) objects [3.7.2] accessed via pointer or reference from another thread.
Resources provided by the operating system. For example, files.
The program itself. In other words, each thread is executing some function of the same program, not a totally different program.
Each thread has its own:
Registers and current execution sequence (program counter) [1.9/5].
Automatic storage duration (stack) objects [3.7.2].
A program is thread-safe if it has no race conditions, does not deadlock, and has no priority failures.
Note that thread-safety does not necessarily imply efficiency, and than while some thread-safety violations can be determined statically at compile time, many thread-safety errors can only only be detected at runtime.
During the lifetime of a thread, it shall be in one of the following states:
Table 10.26. Thread States
State | Description |
---|---|
Ready | Ready to run, but waiting for a processor. |
Running | Currently executing on a processor. Zero or more threads may be running at any time, with a maximum equal to the number of processors. |
Blocked | Waiting for some resource other than a processor which is not currently available, or for the completion of calls to library functions [1.9/6]. The term "waiting" is synonymous with "blocked" |
Terminated | Finished execution but not yet detached or joined. |
Thread state transitions shall occur only as specified:
Table 10.27. Thread States Transitions
From | To | Cause |
---|---|---|
[none] | Ready | Thread is created by a call to a library function. In the case of the initial thread, creation is implicit and occurs during the startup of the main() function [3.6.1]. |
Ready | Running | Processor becomes available. |
Running | Ready | Thread preempted. |
Running | Blocked | Thread calls a library function which waits for a resource or for the completion of I/O. |
Running | Terminated | Thread returns from its initial function, calls a thread termination library function, or is canceled by some other thread calling a thread termination library function. |
Blocked | Ready | The resource being waited for becomes available, or the blocking library function completes. |
Terminated | [none] | Thread is detached or joined by some other thread calling the appropriate library function, or by program termination [3.6.3]. |
[Note: if a suspend() function is added to the threading library, additional transitions to the blocked state will have to be added to the above table.]
A race condition is what occurs when multiple threads read from and write to the same memory without proper synchronization, resulting in an incorrect value being read or written. The result of a race condition may be a bit pattern which isn't even a valid value for the data type. A race condition results in undefined behavior [1.3.12].
Race conditions can be prevented by serializing memory access using the tools provided by Boost.Threads.
Deadlock is an execution state where for some set of threads, each thread in the set is blocked waiting for some action by one of the other threads in the set. Since each is waiting on the others, none will ever become ready again.
The condition in which a thread is not making sufficient progress in its work during a given time interval.
A priority failure (such as priority inversion or infinite overtaking) occurs when threads are executed in such a sequence that required work is not performed in time to be useful.
The result of certain operations in Boost.Threads is undefined; this means that those operations can invoke almost any behavior when they are executed.
An operation whose behavior is undefined can work "correctly" in some implementations (i.e., do what the programmer thought it would do), while in other implementations it may exhibit almost any "incorrect" behavior--such as returning an invalid value, throwing an exception, generating an access violation, or terminating the process.
Executing a statement whose behavior is undefined is a programming error.
An address [1.7] shall always point to the same memory byte, regardless of the thread or processor dereferencing the address.
An object [1.8, 1.9] is accessible from multiple threads if it is of static storage duration (static, extern) [3.7.1], or if a pointer or reference to it is explicitly or implicitly dereferenced in multiple threads.
For an object accessible from multiple threads, the value of the object accessed from one thread may be indeterminate or different from the value accessed from another thread, except under the conditions specified in the following table. For the same row of the table, the value of an object accessible at the indicated sequence point in thread A will be determinate and the same if accessed at or after the indicated sequence point in thread B, provided the object is not otherwise modified. In the table, the "sequence point at a call" is the sequence point after the evaluation of all function arguments [1.9/17], while the "sequence point after a call" is the sequence point after the copying of the returned value... [1.9/17].
Table 10.28. Memory Visibility
Thread A | Thread B |
---|---|
The sequence point at a call to a library thread-creation function. | The first sequence point of the initial function in the new thread created by the Thread A call. |
The sequence point at a call to a library function which locks a mutex, directly or by waiting for a condition variable. | The sequence point after a call to a library function which unlocks the same mutex. |
The last sequence point before thread termination. | The sequence point after a call to a library function which joins the terminated thread. |
The sequence point at a call to a library function which signals or broadcasts a condition variable. | The sequence point after the call to the library function which was waiting on that same condition variable or signal. |
The architecture of the execution environment and the observable behavior of the abstract machine [1.9] shall be the same on all processors.
The latitude granted by the C++ standard for an implementation to alter the definition of observable behavior of the abstract machine to include additional library I/O functions [1.9/6] is extended to include threading library functions.
When an exception is thrown and there is no matching exception handler in the same thread, behavior is undefined. The preferred behavior is the same as when there is no matching exception handler in a program [15.3/9]. That is, terminate() is called, and it is implementation-defined whether or not the stack is unwound.
[AndrewsSchnieder83] ACM Computing Surveys. No. 1. March, 1983. Concepts and Notations for Concurrent Programming”. “
Good general background reading. Includes descriptions of Path Expressions, Message Passing, and Remote Procedure Call in addition to the basics
[Boost] The Boost world wide web site. http://www.boost.org.
Boost.Threads is one of many Boost libraries. The Boost web site includes a great deal of documentation and general information which applies to all Boost libraries. Current copies of the libraries including documentation and test programs may be downloaded from the web site.
[Hansen73] ACM Computing Surveys. No. 4. December, 1983. Concurrent Programming Concepts”. “
"This paper describes the evolution of language features for multiprogramming from event queues and semaphores to critical regions and monitors." Includes analysis of why events are considered error-prone. Also noteworthy because of an introductory quotation from Christopher Alexander; Brinch Hansen was years ahead of others in recognizing pattern concepts applied to software, too.
[Butenhof97] Programming with POSIX Threads . Addison-WesleyCopyright © 1997. ISNB: 0-201-63392-2.
This is a very readable explanation of threads and how to use them. Many of the insights given apply to all multithreaded programming, not just POSIX Threads
[Hoare74] Communications of the ACM. No. 10. October, 1974. “Monitors: An Operating System Structuring Concept”. 549-557.
Hoare and Brinch Hansen's work on Monitors is the basis for reliable multithreading patterns. This is one of the most often referenced papers in all of computer science, and with good reason.
[ISO98] Programming Language C++. ISO/IEC. 14882:1998(E).
This is the official C++ Standards document. Available from the ANSI (American National Standards Institute) Electronic Standards Store.
[McDowellHelmbold89] Communications of the ACM. No. 2. December, 1989. Debugging Concurrent Programs.
Identifies many of the unique failure modes and debugging difficulties associated with concurrent programs.
[SchmidtPyarali] Strategies for Implementing POSIX Condition Variables on Win32. Department of Computer Science, Washington University, St. Louis, Missouri.
Rationale for understanding Boost.Threads condition variables. Note that Alexander Terekhov found some bugs in the implementation given in this article, so pthreads-win32 and Boost.Threads are even more complicated yet.
[SchmidtStalRohnertBuschmann] Pattern-Oriented Architecture Volume 2. Patterns for Concurrent and Networked Objects. POSA2. WileyCopyright © 2000.
This is a very good explanation of how to apply several patterns useful for concurrent programming. Among the patterns documented is the Monitor Pattern mentioned frequently in the Boost.Threads documentation.
[Stroustrup] The C++ Programming Language. Special Edition. Addison-WesleyCopyright © 2000. ISBN: 0-201-70073-5.
The first book a C++ programmer should own. Note that the 3rd edition (and subsequent editions like the Special Edition) has been rewritten to cover the ISO standard language and library.
Last revised: July 17, 2004 at 04:33:59 GMT |