###  | # Boost.Threads ## Definitions

## Contents

Introduction
Definitions

Thread
Thread-safe
Thread State
Race Condition
Deadlock
Starvation
Priority Failure
Memory Visibility

Acknowledgments

## Introduction

The definitions are given in terms of the C++ Standard. 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.

## Definitions

### Thread

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].

### Thread-safe

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.

### Thread State

During the lifetime of a thread, it shall be in one of the following 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 for "blocked"
Terminated | Finished execution but not yet detached or joined.

Thread state transitions shall occur only as specified:

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.]

### Race Condition

A race condition is what occurs when multiple threads read 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

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.

### Starvation

The condition in which a thread is not making sufficient progress in its work during a given time interval.

### Priority Failure

A priority failure (such as priority inversion or infinite overtaking) occurs when threads executed in such a sequence that required work is not performed in time to be useful.

### Memory Visibility

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 than 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].

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.

## Acknowledgments

This document has been much improved by the incorporation of comments from William Kempf.

The visibility rules are based on [Butenhof 97].

Revised 05 November, 2001

© Copyright William E. Kempf 2001-2002. All Rights Reserved.

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.