![Concepts- Program vs](https://upload.wikimedia.org/wikipedia/commons/2/25/Concepts-_Program_vs._Process_vs._Thread.jpg)
In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, a thread of
execution
Capital punishment, also known as the death penalty, is the State (polity), state-sanctioned practice of deliberately killing a person as a punishment for an actual or supposed crime, usually following an authorized, rule-governed process to ...
is the smallest sequence of programmed instructions that can be managed independently by a
scheduler
A schedule or a timetable, as a basic time-management tool, consists of a list of times at which possible tasks, events, or actions are intended to take place, or of a sequence of events in the chronological order in which such things are i ...
, which is typically a part of the
operating system
An operating system (OS) is system software that manages computer hardware, software resources, and provides common services for computer programs.
Time-sharing operating systems schedule tasks for efficient use of the system and may also in ...
. The implementation of threads and
processes differs between operating systems. In
Modern Operating Systems
''Modern Operating Systems'' is a book written by Andrew Tanenbaum, a version (which does not target implementation) of his book '' Operating Systems: Design and Implementation''. It is now in its 4th edition, published March 2014 (), written t ...
,
Tanenbaum shows that many distinct models of process organization are possible.
[TANENBAUM, Andrew S. Modern Operating Systems. 1992. Prentice-Hall International Editions, ISBN 0-13-595752-4.] In many cases, a thread is a component of a process. The multiple threads of a given process may be executed
concurrently (via multithreading capabilities), sharing resources such as
memory
Memory is the faculty of the mind by which data or information is encoded, stored, and retrieved when needed. It is the retention of information over time for the purpose of influencing future action. If past events could not be remembered, ...
, while different processes do not share these resources. In particular, the threads of a process share its executable code and the values of its
dynamically allocated variables and non-
thread-local global variable
In computer programming, a global variable is a variable with global scope, meaning that it is visible (hence accessible) throughout the program, unless shadowed. The set of all global variables is known as the ''global environment'' or ''global s ...
s at any given time.
History
Threads made an early appearance under the name of "tasks" in
OS/360 Multiprogramming with a Variable Number of Tasks (MVT) in 1967. Saltzer (1966) credits
Victor A. Vyssotsky
Victor Alexander Vyssotsky (russian: Виктор Александрович Высотский; February 26, 1931 - December 24, 2012 in Orleans, Massachusetts) son of the astronomers Alexander N. Vyssotsky (Russian) and Emma Vyssotsky ( Americ ...
with the term "thread".
The use of threads in software applications became more common in the early 2000s as CPUs began to utilize multiple cores. Applications wishing to take advantage of multiple cores for performance advantages were required to employ concurrency to utilize the multiple cores.
Processes, kernel threads, user threads, and fibers
Scheduling can be done at the kernel level or user level, and multitasking can be done preemptively or cooperatively. This yields a variety of related concepts.
Processes
At the kernel level, a ''process'' contains one or more ''kernel threads'', which share the process's resources, such as memory and file handles – a process is a unit of resources, while a thread is a unit of scheduling and execution. Kernel scheduling is typically uniformly done preemptively or, less commonly, cooperatively. At the user level a process such as a
runtime system
In computer programming, a runtime system or runtime environment is a sub-system that exists both in the computer where a program is created, as well as in the computers where the program is intended to be run. The name comes from the compile t ...
can itself schedule multiple threads of execution. If these do not share data, as in Erlang, they are usually analogously called processes, while if they share data they are usually called ''(user) threads'', particularly if preemptively scheduled. Cooperatively scheduled user threads are known as ''
fibers
Fiber or fibre (from la, fibra, links=no) is a natural or artificial substance that is significantly longer than it is wide. Fibers are often used in the manufacture of other materials. The strongest engineering materials often incorporate ...
''; different processes may schedule user threads differently. User threads may be executed by kernel threads in various ways (one-to-one, many-to-one, many-to-many). The term "
light-weight process
In computer operating systems, a light-weight process (LWP) is a means of achieving multitasking. In the traditional meaning of the term, as used in Unix System V and Solaris, a LWP runs in user space on top of a single kernel thread and share ...
" variously refers to user threads or to kernel mechanisms for scheduling user threads onto kernel threads.
A ''process'' is a "heavyweight" unit of kernel scheduling, as creating, destroying, and switching processes is relatively expensive. Processes own
resources
Resource refers to all the materials available in our environment which are technologically accessible, economically feasible and culturally sustainable and help us to satisfy our needs and wants. Resources can broadly be classified upon their a ...
allocated by the operating system. Resources include memory (for both code and data),
file handles, sockets, device handles, windows, and a
process control block A process control block (PCB) is a data structure used by computer operating systems to store all the information about a process. It is also known as a process descriptor. When a process is created (initialized or installed), the operating system c ...
. Processes are ''isolated'' by
process isolation Process isolation is a set of different hardware and software technologies designed to protect each process from other processes on the operating system. It does so by preventing process A from writing to process B.
Process isolation can be impleme ...
, and do not share address spaces or file resources except through explicit methods such as inheriting file handles or shared memory segments, or mapping the same file in a shared way – see
interprocess communication
In computer science, inter-process communication or interprocess communication (IPC) refers specifically to the mechanisms an operating system provides to allow the processes to manage shared data. Typically, applications can use IPC, categori ...
. Creating or destroying a process is relatively expensive, as resources must be acquired or released. Processes are typically preemptively multitasked, and process switching is relatively expensive, beyond basic cost of
context switching
In computing, a context switch is the process of storing the state of a process or thread, so that it can be restored and resume execution at a later point, and then restoring a different, previously saved, state. This allows multiple processes ...
, due to issues such as cache flushing (in particular, process switching changes virtual memory addressing, causing invalidation and thus flushing of an untagged
translation lookaside buffer
A translation lookaside buffer (TLB) is a memory cache that stores the recent translations of virtual memory to physical memory. It is used to reduce the time taken to access a user memory location. It can be called an address-translation cache. ...
, notably on x86).
Kernel threads
A ''kernel thread'' is a "lightweight" unit of kernel scheduling. At least one kernel thread exists within each process. If multiple kernel threads exist within a process, then they share the same memory and file resources. Kernel threads are preemptively multitasked if the operating system's process
scheduler
A schedule or a timetable, as a basic time-management tool, consists of a list of times at which possible tasks, events, or actions are intended to take place, or of a sequence of events in the chronological order in which such things are i ...
is preemptive. Kernel threads do not own resources except for a
stack
Stack may refer to:
Places
* Stack Island, an island game reserve in Bass Strait, south-eastern Australia, in Tasmania’s Hunter Island Group
* Blue Stack Mountains, in Co. Donegal, Ireland
People
* Stack (surname) (including a list of people ...
, a copy of the
registers including the
program counter
The program counter (PC), commonly called the instruction pointer (IP) in Intel x86 and Itanium microprocessors, and sometimes called the instruction address register (IAR), the instruction counter, or just part of the instruction sequencer, is ...
, and
thread-local storage
Thread-local storage (TLS) is a computer programming method that uses static or global memory local to a thread.
While the use of global variables is generally discouraged in modern programming, legacy operating systems such as UNIX are designed ...
(if any), and are thus relatively cheap to create and destroy. Thread switching is also relatively cheap: it requires a context switch (saving and restoring registers and stack pointer), but does not change virtual memory and is thus cache-friendly (leaving TLB valid). The kernel can assign one thread to each logical core in a system (because each processor splits itself up into multiple logical cores if it supports multithreading, or only supports one logical core per physical core if it does not), and can swap out threads that get blocked. However, kernel threads take much longer than user threads to be swapped.
User threads
Threads are sometimes implemented in
userspace
A modern computer operating system usually segregates virtual memory into user space and kernel space. Primarily, this separation serves to provide memory protection and hardware protection from malicious or errant software behaviour.
Kernel ...
libraries, thus called ''user threads''. The kernel is unaware of them, so they are managed and scheduled in
userspace
A modern computer operating system usually segregates virtual memory into user space and kernel space. Primarily, this separation serves to provide memory protection and hardware protection from malicious or errant software behaviour.
Kernel ...
. Some implementations base their user threads on top of several kernel threads, to benefit from
multi-processor
Multiprocessing is the use of two or more central processing units (CPUs) within a single computer system. The term also refers to the ability of a system to support more than one processor or the ability to allocate tasks between them. There ar ...
machines (
M:N model). User threads as implemented by
virtual machine
In computing, a virtual machine (VM) is the virtualization/emulation of a computer system. Virtual machines are based on computer architectures and provide functionality of a physical computer. Their implementations may involve specialized hardw ...
s are also called
green threads
In computer programming, a green thread is a thread that is scheduled by a runtime library or virtual machine (VM) instead of natively by the underlying operating system (OS). Green threads emulate multithreaded environments without relying on an ...
.
As user thread implementations are typically entirely in
userspace
A modern computer operating system usually segregates virtual memory into user space and kernel space. Primarily, this separation serves to provide memory protection and hardware protection from malicious or errant software behaviour.
Kernel ...
, context switching between user threads within the same process is extremely efficient because it does not require any interaction with the kernel at all: a context switch can be performed by locally saving the CPU registers used by the currently executing user thread or fiber and then loading the registers required by the user thread or fiber to be executed. Since scheduling occurs in userspace, the scheduling policy can be more easily tailored to the requirements of the program's workload.
However, the use of blocking system calls in user threads (as opposed to kernel threads) can be problematic. If a user thread or a fiber performs a system call that blocks, the other user threads and fibers in the process are unable to run until the system call returns. A typical example of this problem is when performing I/O: most programs are written to perform I/O synchronously. When an I/O operation is initiated, a system call is made, and does not return until the I/O operation has been completed. In the intervening period, the entire process is "blocked" by the kernel and cannot run, which starves other user threads and fibers in the same process from executing.
A common solution to this problem (used, in particular, by many of green threads implementations) is providing an I/O API that implements an interface that blocks the calling thread, rather than the entire process, by using non-blocking I/O internally, and scheduling another user thread or fiber while the I/O operation is in progress. Similar solutions can be provided for other blocking system calls. Alternatively, the program can be written to avoid the use of synchronous I/O or other blocking system calls (in particular, using non-blocking I/O, including lambda continuations and/or async/
await
In computer programming, the async/await pattern is a syntactic feature of many programming languages that allows an Asynchrony (computer programming), asynchronous, non-blocking I/O, non-blocking Subroutine, function to be structured in a way simi ...
primitives).
Fibers
Fibers
Fiber or fibre (from la, fibra, links=no) is a natural or artificial substance that is significantly longer than it is wide. Fibers are often used in the manufacture of other materials. The strongest engineering materials often incorporate ...
are an even lighter unit of scheduling which are
cooperatively scheduled: a running fiber must explicitly "
yield" to allow another fiber to run, which makes their implementation much easier than kernel or
user threads
Ancient Egyptian roles
* User (ancient Egyptian official), an ancient Egyptian nomarch (governor) of the Eighth Dynasty
* Useramen, an ancient Egyptian vizier also called "User"
Other uses
* User (computing), a person (or software) using an ...
. A fiber can be scheduled to run in any thread in the same process. This permits applications to gain performance improvements by managing scheduling themselves, instead of relying on the kernel scheduler (which may not be tuned for the application). Parallel programming environments such as
OpenMP
OpenMP (Open Multi-Processing) is an application programming interface (API) that supports multi-platform shared-memory multiprocessing programming in C, C++, and Fortran, on many platforms, instruction-set architectures and operating syste ...
sometimes implement their tasks through fibers. Closely related to fibers are
coroutine
Coroutines are computer program components that generalize subroutines for non-preemptive multitasking, by allowing execution to be suspended and resumed. Coroutines are well-suited for implementing familiar program components such as cooperative ...
s, with the distinction being that coroutines are a language-level construct, while fibers are a system-level construct.
Threads vs processes
Threads differ from traditional
multitasking operating-system
processes in several ways:
* processes are typically independent, while threads exist as subsets of a process
* processes carry considerably more
state
State may refer to:
Arts, entertainment, and media Literature
* ''State Magazine'', a monthly magazine published by the U.S. Department of State
* ''The State'' (newspaper), a daily newspaper in Columbia, South Carolina, United States
* ''Our S ...
information than threads, whereas multiple threads within a process share process state as well as
memory
Memory is the faculty of the mind by which data or information is encoded, stored, and retrieved when needed. It is the retention of information over time for the purpose of influencing future action. If past events could not be remembered, ...
and other
resources
Resource refers to all the materials available in our environment which are technologically accessible, economically feasible and culturally sustainable and help us to satisfy our needs and wants. Resources can broadly be classified upon their a ...
* processes have separate
address space
In computing, an address space defines a range of discrete addresses, each of which may correspond to a network host, peripheral device, disk sector, a memory cell or other logical or physical entity.
For software programs to save and retrieve st ...
s, whereas threads share their address space
* processes interact only through system-provided
inter-process communication
In computer science, inter-process communication or interprocess communication (IPC) refers specifically to the mechanisms an operating system provides to allow the processes to manage shared data. Typically, applications can use IPC, categori ...
mechanisms
*
context switch
In computing, a context switch is the process of storing the state of a process or thread, so that it can be restored and resume execution at a later point, and then restoring a different, previously saved, state. This allows multiple processes ...
ing between threads in the same process typically occurs faster than context switching between processes
Systems such as
Windows NT
Windows NT is a proprietary graphical operating system
An operating system (OS) is system software that manages computer hardware, software resources, and provides common services for computer programs.
Time-sharing operating systems sc ...
and
OS/2
OS/2 (Operating System/2) is a series of computer operating systems, initially created by Microsoft and IBM under the leadership of IBM software designer Ed Iacobucci. As a result of a feud between the two companies over how to position OS/2 ...
are said to have ''cheap'' threads and ''expensive'' processes; in other operating systems there is not so great a difference except in the cost of an
address-space switch, which on some architectures (notably
x86
x86 (also known as 80x86 or the 8086 family) is a family of complex instruction set computer (CISC) instruction set architectures initially developed by Intel based on the Intel 8086 microprocessor and its 8088 variant. The 8086 was introd ...
) results in a
translation lookaside buffer
A translation lookaside buffer (TLB) is a memory cache that stores the recent translations of virtual memory to physical memory. It is used to reduce the time taken to access a user memory location. It can be called an address-translation cache. ...
(TLB) flush.
Advantages and disadvantages of threads vs processes include:
* ''Lower resource consumption'' of threads: using threads, an application can operate using fewer resources than it would need when using multiple processes.
* ''Simplified sharing and communication'' of threads: unlike processes, which require a
message passing
In computer science, message passing is a technique for invoking behavior (i.e., running a program) on a computer. The invoking program sends a message to a process (which may be an actor or object) and relies on that process and its supporting i ...
or shared memory mechanism to perform
inter-process communication
In computer science, inter-process communication or interprocess communication (IPC) refers specifically to the mechanisms an operating system provides to allow the processes to manage shared data. Typically, applications can use IPC, categori ...
(IPC), threads can communicate through data, code and files they already share.
* ''Thread crashes a process'': due to threads sharing the same address space, an illegal operation performed by a thread can crash the entire process; therefore, one misbehaving thread can disrupt the processing of all the other threads in the application.
Scheduling
Preemptive vs cooperative scheduling
Operating systems schedule threads either
preemptively or
cooperatively
Cooperation (written as co-operation in British English) is the process of groups of organisms working or acting together for common, mutual, or some underlying benefit, as opposed to working in competition for selfish benefit. Many animal a ...
.
Multi-user operating systems generally favor
preemptive multithreading
In computing, preemption is the act of temporarily interrupting an executing task, with the intention of resuming it at a later time. This interrupt is done by an external scheduler with no assistance or cooperation from the task. This preempt ...
for its finer-grained control over execution time via
context switch
In computing, a context switch is the process of storing the state of a process or thread, so that it can be restored and resume execution at a later point, and then restoring a different, previously saved, state. This allows multiple processes ...
ing. However, preemptive scheduling may context-switch threads at moments unanticipated by programmers, thus causing
lock convoy
In computer science, a lock convoy is a performance problem that can occur when using locks for concurrency control in a multithreaded application.
A lock convoy occurs when multiple threads of equal priority contend repeatedly for the same loc ...
,
priority inversion
In computer science, priority inversion is a scenario in scheduling in which a high priority task is indirectly superseded by a lower priority task effectively inverting the assigned priorities of the tasks. This violates the priority model that h ...
, or other side-effects. In contrast,
cooperative multithreading
Cooperative multitasking, also known as non-preemptive multitasking, is a style of computer multitasking in which the operating system never initiates a context switch from a running process to another process. Instead, in order to run multiple ...
relies on threads to relinquish control of execution, thus ensuring that threads
run to completion
Run-to-completion scheduling or nonpreemptive scheduling is a scheduling model in which each task runs until it either finishes, or explicitly yields control back to the scheduler. Run to completion systems typically have an event queue which is s ...
. This can cause problems if a cooperatively multitasked thread
blocks by waiting on a
resource or if it
starves other threads by not yielding control of execution during intensive computation.
Single- vs multi-processor systems
Until the early 2000s, most desktop computers had only one single-core CPU, with no support for
hardware thread
In computer architecture, multithreading is the ability of a central processing unit (CPU) (or a single core in a multi-core processor) to provide multiple threads of execution concurrently, supported by the operating system. This approach di ...
s, although threads were still used on such computers because switching between threads was generally still quicker than full-process
context switch
In computing, a context switch is the process of storing the state of a process or thread, so that it can be restored and resume execution at a later point, and then restoring a different, previously saved, state. This allows multiple processes ...
es. In 2002,
Intel
Intel Corporation is an American multinational corporation and technology company headquartered in Santa Clara, California. It is the world's largest semiconductor chip manufacturer by revenue, and is one of the developers of the x86 seri ...
added support for
simultaneous multithreading
Simultaneous multithreading (SMT) is a technique for improving the overall efficiency of superscalar CPUs with hardware multithreading. SMT permits multiple independent threads of execution to better use the resources provided by modern process ...
to the
Pentium 4
Pentium 4 is a series of single-core CPUs for desktops, laptops and entry-level servers manufactured by Intel. The processors were shipped from November 20, 2000 until August 8, 2008. The production of Netburst processors was active from 2000 u ...
processor, under the name ''
hyper-threading
Hyper-threading (officially called Hyper-Threading Technology or HT Technology and abbreviated as HTT or HT) is Intel's proprietary simultaneous multithreading (SMT) implementation used to improve parallelization of computations (doing multip ...
''; in 2005, they introduced the dual-core
Pentium D
Pentium D is a range of desktop 64-bit x86-64 processors based on the NetBurst microarchitecture, which is the dual-core variant of the Pentium 4 manufactured by Intel. Each CPU comprised two cores. The brand's first processor, codenamed ''Smith ...
processor and
AMD
Advanced Micro Devices, Inc. (AMD) is an American multinational semiconductor company based in Santa Clara, California, that develops computer processors and related technologies for business and consumer markets. While it initially manufactur ...
introduced the dual-core
Athlon 64 X2 processor.
Systems with a single processor generally implement multithreading by
time slicing: the
central processing unit
A central processing unit (CPU), also called a central processor, main processor or just processor, is the electronic circuitry that executes instructions comprising a computer program. The CPU performs basic arithmetic, logic, controlling, an ...
(CPU) switches between different ''software threads''. This
context switch
In computing, a context switch is the process of storing the state of a process or thread, so that it can be restored and resume execution at a later point, and then restoring a different, previously saved, state. This allows multiple processes ...
ing usually occurs frequently enough that users perceive the threads or tasks as running in parallel (for popular server/desktop operating systems, maximum time slice of a thread, when other threads are waiting, is often limited to 100-200ms). On a
multiprocessor
Multiprocessing is the use of two or more central processing units (CPUs) within a single computer system. The term also refers to the ability of a system to support more than one processor or the ability to allocate tasks between them. There ar ...
or
multi-core
A multi-core processor is a microprocessor on a single integrated circuit with two or more separate processing units, called cores, each of which reads and executes program instructions. The instructions are ordinary CPU instructions (such a ...
system, multiple threads can execute in
parallel
Parallel is a geometric term of location which may refer to:
Computing
* Parallel algorithm
* Parallel computing
* Parallel metaheuristic
* Parallel (software), a UNIX utility for running programs in parallel
* Parallel Sysplex, a cluster of IBM ...
, with every processor or core executing a separate thread simultaneously; on a processor or core with ''
hardware thread
In computer architecture, multithreading is the ability of a central processing unit (CPU) (or a single core in a multi-core processor) to provide multiple threads of execution concurrently, supported by the operating system. This approach di ...
s'', separate software threads can also be executed concurrently by separate hardware threads.
Threading models
1:1 (kernel-level threading)
Threads created by the user in a 1:1 correspondence with schedulable entities in the kernel
are the simplest possible threading implementation.
OS/2
OS/2 (Operating System/2) is a series of computer operating systems, initially created by Microsoft and IBM under the leadership of IBM software designer Ed Iacobucci. As a result of a feud between the two companies over how to position OS/2 ...
and
Win32
The Windows API, informally WinAPI, is Microsoft's core set of application programming interfaces (APIs) available in the Microsoft Windows operating systems. The name Windows API collectively refers to several different platform implementations th ...
used this approach from the start, while on
Linux
Linux ( or ) is a family of open-source Unix-like operating systems based on the Linux kernel, an operating system kernel first released on September 17, 1991, by Linus Torvalds. Linux is typically packaged as a Linux distribution, which ...
the
GNU C Library
The GNU C Library, commonly known as glibc, is the GNU Project's implementation of the C standard library. Despite its name, it now also directly supports C++ (and, indirectly, other programming languages). It was started in the 1980s by ...
implements this approach (via the
NPTL The Native POSIX Thread Library (NPTL) is an implementation of the POSIX Threads specification for the Linux operating system.
History
Before the 2.6 version of the Linux kernel, processes were the schedulable entities, and there were no special f ...
or older
LinuxThreads
In the Linux operating system, LinuxThreads was a partial implementation of POSIX Threads introduced in 1996. The main developer of LinuxThreads was Xavier Leroy. It has been superseded by the Native POSIX Thread Library (NPTL).
LinuxThreads had ...
). This approach is also used by
Solaris
Solaris may refer to:
Arts and entertainment Literature, television and film
* ''Solaris'' (novel), a 1961 science fiction novel by Stanisław Lem
** ''Solaris'' (1968 film), directed by Boris Nirenburg
** ''Solaris'' (1972 film), directed by ...
,
NetBSD
NetBSD is a free and open-source Unix operating system based on the Berkeley Software Distribution (BSD). It was the first open-source BSD descendant officially released after 386BSD was forked. It continues to be actively developed and is a ...
,
FreeBSD
FreeBSD is a free and open-source Unix-like operating system descended from the Berkeley Software Distribution (BSD), which was based on Research Unix. The first version of FreeBSD was released in 1993. In 2005, FreeBSD was the most popular ...
,
macOS
macOS (; previously OS X and originally Mac OS X) is a Unix operating system developed and marketed by Apple Inc. since 2001. It is the primary operating system for Apple's Mac computers. Within the market of desktop and lapt ...
, and
iOS
iOS (formerly iPhone OS) is a mobile operating system created and developed by Apple Inc. exclusively for its hardware. It is the operating system that powers many of the company's mobile devices, including the iPhone; the term also includes ...
.
''N'':1 (user-level threading)
An ''N'':1 model implies that all application-level threads map to one kernel-level scheduled entity;
the kernel has no knowledge of the application threads. With this approach, context switching can be done very quickly and, in addition, it can be implemented even on simple kernels which do not support threading. One of the major drawbacks, however, is that it cannot benefit from the hardware acceleration on
multithreaded processors or
multi-processor
Multiprocessing is the use of two or more central processing units (CPUs) within a single computer system. The term also refers to the ability of a system to support more than one processor or the ability to allocate tasks between them. There ar ...
computers: there is never more than one thread being scheduled at the same time.
For example: If one of the threads needs to execute an I/O request, the whole process is blocked and the threading advantage cannot be used. The
GNU Portable Threads
GNU Pth (Portable Threads) is a POSIX/ANSI- C based user space thread library for UNIX platforms that provides priority-based scheduling for multithreading applications. GNU Pth targets for a high degree of portability. It is part of the GNU Pr ...
uses User-level threading, as does
State Threads
The State Threads library is a small application library which provides a foundation for writing fast and highly scalable Internet applications (such as web servers, proxy servers, mail transfer agents, or any network-data-driven application) on Un ...
.
''M'':''N'' (hybrid threading)
''M'':''N'' maps some number of application threads onto some number of kernel entities,
or "virtual processors." This is a compromise between kernel-level ("1:1") and user-level ("''N'':1") threading. In general, "''M'':''N''" threading systems are more complex to implement than either kernel or user threads, because changes to both kernel and user-space code are required. In the M:N implementation, the threading library is responsible for scheduling user threads on the available schedulable entities; this makes context switching of threads very fast, as it avoids system calls. However, this increases complexity and the likelihood of
priority inversion
In computer science, priority inversion is a scenario in scheduling in which a high priority task is indirectly superseded by a lower priority task effectively inverting the assigned priorities of the tasks. This violates the priority model that h ...
, as well as suboptimal scheduling without extensive (and expensive) coordination between the userland scheduler and the kernel scheduler.
Hybrid implementation examples
*
Scheduler activations Scheduler activations are a threading mechanism that, when implemented in an operating system's process scheduler, provide kernel-level thread functionality with user-level thread flexibility and performance. This mechanism uses a so-called "N:M" ...
used by older versions of the NetBSD native POSIX threads library implementation (an ''M'':''N'' model as opposed to a 1:1 kernel or userspace implementation model)
*
Light-weight process
In computer operating systems, a light-weight process (LWP) is a means of achieving multitasking. In the traditional meaning of the term, as used in Unix System V and Solaris, a LWP runs in user space on top of a single kernel thread and share ...
es used by older versions of the
Solaris
Solaris may refer to:
Arts and entertainment Literature, television and film
* ''Solaris'' (novel), a 1961 science fiction novel by Stanisław Lem
** ''Solaris'' (1968 film), directed by Boris Nirenburg
** ''Solaris'' (1972 film), directed by ...
operating system
* Marcel from the
PM2 project.
* The OS for the Tera-
Cray MTA-2 The Cray MTA-2 is a shared-memory MIMD computer marketed by Cray Inc. It is an unusual design based on the Tera computer designed by Tera Computer Company. The original Tera computer (also known as the ''MTA'') turned out to be nearly unmanufact ...
* The
Glasgow Haskell Compiler
The Glasgow Haskell Compiler (GHC) is an open-source native code compiler for the functional programming language Haskell.
It provides a cross-platform environment for the writing and testing of Haskell code and it supports numerous extensions, ...
(GHC) for the language
Haskell
Haskell () is a general-purpose, statically-typed, purely functional programming language with type inference and lazy evaluation. Designed for teaching, research and industrial applications, Haskell has pioneered a number of programming lan ...
uses lightweight threads which are scheduled on operating system threads.
History of threading models in Unix systems
SunOS
SunOS is a Unix-branded operating system developed by Sun Microsystems for their workstation and server computer systems. The ''SunOS'' name is usually only used to refer to versions 1.0 to 4.1.4, which were based on BSD, while versions 5.0 and l ...
4.x implemented ''
light-weight process
In computer operating systems, a light-weight process (LWP) is a means of achieving multitasking. In the traditional meaning of the term, as used in Unix System V and Solaris, a LWP runs in user space on top of a single kernel thread and share ...
es'' or LWPs.
NetBSD
NetBSD is a free and open-source Unix operating system based on the Berkeley Software Distribution (BSD). It was the first open-source BSD descendant officially released after 386BSD was forked. It continues to be actively developed and is a ...
2.x+, and
DragonFly BSD
DragonFly BSD is a free and open-source Unix-like operating system forked from FreeBSD 4.8. Matthew Dillon, an Amiga developer in the late 1980s and early 1990s and FreeBSD developer between 1994 and 2003, began working on DragonFly BSD in Ju ...
implement LWPs as kernel threads (1:1 model). SunOS 5.2 through SunOS 5.8 as well as NetBSD 2 to NetBSD 4 implemented a two level model, multiplexing one or more user level threads on each kernel thread (M:N model). SunOS 5.9 and later, as well as NetBSD 5 eliminated user threads support, returning to a 1:1 model. FreeBSD 5 implemented M:N model. FreeBSD 6 supported both 1:1 and M:N, users could choose which one should be used with a given program using /etc/libmap.conf. Starting with FreeBSD 7, the 1:1 became the default. FreeBSD 8 no longer supports the M:N model.
Single-threaded vs multithreaded programs
In
computer programming
Computer programming is the process of performing a particular computation (or more generally, accomplishing a specific computing result), usually by designing and building an executable computer program. Programming involves tasks such as ana ...
, ''single-threading'' is the processing of one
command
Command may refer to:
Computing
* Command (computing), a statement in a computer language
* COMMAND.COM, the default operating system shell and command-line interpreter for DOS
* Command key, a modifier key on Apple Macintosh computer keyboards
* ...
at a time. In the formal analysis of the variables'
semantics
Semantics (from grc, σημαντικός ''sēmantikós'', "significant") is the study of reference, meaning, or truth. The term can be used to refer to subfields of several distinct disciplines, including philosophy
Philosophy (f ...
and process state, the term ''single threading'' can be used differently to mean "backtracking within a single thread", which is common in the
functional programming
In computer science, functional programming is a programming paradigm where programs are constructed by Function application, applying and Function composition (computer science), composing Function (computer science), functions. It is a declar ...
community.
Multithreading is mainly found in multitasking operating systems. Multithreading is a widespread programming and execution model that allows multiple threads to exist within the context of one process. These threads share the process's resources, but are able to execute independently. The threaded programming model provides developers with a useful abstraction of concurrent execution. Multithreading can also be applied to one process to enable
parallel execution on a
multiprocessing
Multiprocessing is the use of two or more central processing units (CPUs) within a single computer system. The term also refers to the ability of a system to support more than one processor or the ability to allocate tasks between them. There ar ...
system.
Multithreading libraries tend to provide a function call to create a new thread, which takes a function as a parameter. A concurrent thread is then created which starts running the passed function and ends when the function returns. The thread libraries also offer data synchronization functions.
Threads and data synchronization
Threads in the same process share the same address space. This allows concurrently running code to
couple
Couple or couples may refer to :
Basic meaning
*Couple (app), a mobile app which provides a mobile messaging service for two people
*Couple (mechanics), a system of forces with a resultant moment but no resultant force
*Couple (relationship), tw ...
tightly and conveniently exchange data without the overhead or complexity of an
IPC. When shared between threads, however, even simple data structures become prone to
race conditions
A race condition or race hazard is the condition of an electronics, software, or other system where the system's substantive behavior is dependent on the sequence or timing of other uncontrollable events. It becomes a bug when one or more of t ...
if they require more than one CPU instruction to update: two threads may end up attempting to update the data structure at the same time and find it unexpectedly changing underfoot. Bugs caused by race conditions can be very difficult to reproduce and isolate.
To prevent this, threading
application programming interface
An application programming interface (API) is a way for two or more computer programs to communicate with each other. It is a type of software interface, offering a service to other pieces of software. A document or standard that describes how t ...
s (APIs) offer
synchronization primitives such as
mutex
In computer science, a lock or mutex (from mutual exclusion) is a synchronization primitive: a mechanism that enforces limits on access to a resource when there are many threads of execution. A lock is designed to enforce a mutual exclusion concu ...
es to
lock
Lock(s) may refer to:
Common meanings
*Lock and key, a mechanical device used to secure items of importance
*Lock (water navigation), a device for boats to transit between different levels of water, as in a canal
Arts and entertainment
* ''Lock ...
data structures against concurrent access. On uniprocessor systems, a thread running into a locked mutex must sleep and hence trigger a context switch. On multi-processor systems, the thread may instead poll the mutex in a
spinlock
In software engineering, a spinlock is a lock that causes a thread trying to acquire it to simply wait in a loop ("spin") while repeatedly checking whether the lock is available. Since the thread remains active but is not performing a useful task, ...
. Both of these may sap performance and force processors in
symmetric multiprocessing
Symmetric multiprocessing or shared-memory multiprocessing (SMP) involves a multiprocessor computer hardware and software architecture where two or more identical processors are connected to a single, shared main memory, have full access to all ...
(SMP) systems to contend for the memory bus, especially if the
granularity
Granularity (also called graininess), the condition of existing in granules or grains, refers to the extent to which a material or system is composed of distinguishable pieces. It can either refer to the extent to which a larger entity is subd ...
of the locking is too fine.
Other synchronization APIs include
condition variables
In concurrent programming, a monitor is a synchronization construct that allows threads to have both mutual exclusion and the ability to wait (block) for a certain condition to become false. Monitors also have a mechanism for signaling other th ...
,
critical section
In concurrent programming, concurrent accesses to shared resources can lead to unexpected or erroneous behavior, so parts of the program where the shared resource is accessed need to be protected in ways that avoid the concurrent access. One way to ...
s,
semaphores, and
monitors
Monitor or monitor may refer to:
Places
* Monitor, Alberta
* Monitor, Indiana, town in the United States
* Monitor, Kentucky
* Monitor, Oregon, unincorporated community in the United States
* Monitor, Washington
* Monitor, Logan County, West Vir ...
.
Thread pools
A popular programming pattern involving threads is that of
thread pools where a set number of threads are created at startup that then wait for a task to be assigned. When a new task arrives, it wakes up, completes the task and goes back to waiting. This avoids the relatively expensive thread creation and destruction functions for every task performed and takes thread management out of the application developer's hand and leaves it to a library or the operating system that is better suited to optimize thread management.
Multithreaded programs vs single-threaded programs pros and cons
Multithreaded applications have the following advantages vs single-threaded ones:
* ''Responsiveness'': multithreading can allow an application to remain responsive to input. In a one-thread program, if the main execution thread blocks on a long-running task, the entire application can appear to freeze. By moving such long-running tasks to a ''worker thread'' that runs concurrently with the main execution thread, it is possible for the application to remain responsive to user input while executing tasks in the background. On the other hand, in most cases multithreading is not the only way to keep a program responsive, with
non-blocking I/O
In computer science, asynchronous I/O (also non-sequential I/O) is a form of input/output processing that permits other processing to continue before the transmission has finished. A name used for asynchronous I/O in the Windows API is overlappe ...
and/or
Unix signals
Signals are standardized messages sent to a running program to trigger specific behavior, such as quitting or error handling. They are a limited form of inter-process communication (IPC), typically used in Unix, Unix-like, and other POSIX-compli ...
being available for obtaining similar results.
* ''Parallelization'': applications looking to use multicore or multi-CPU systems can use multithreading to split data and tasks into parallel subtasks and let the underlying architecture manage how the threads run, either concurrently on one core or in parallel on multiple cores. GPU computing environments like
CUDA
CUDA (or Compute Unified Device Architecture) is a parallel computing platform and application programming interface (API) that allows software to use certain types of graphics processing units (GPUs) for general purpose processing, an approach ca ...
and
OpenCL
OpenCL (Open Computing Language) is a framework for writing programs that execute across heterogeneous platforms consisting of central processing units (CPUs), graphics processing units (GPUs), digital signal processors (DSPs), field-progra ...
use the multithreading model where dozens to hundreds of threads run in
parallel across data on a
large number of cores. This, in turn, enables better system utilization, and (provided that synchronization costs don't eat the benefits up), can provide faster program execution.
Multithreaded applications have the following drawbacks:
* ''
Synchronization
Synchronization is the coordination of events to operate a system in unison. For example, the conductor of an orchestra keeps the orchestra synchronized or ''in time''. Systems that operate with all parts in synchrony are said to be synchronou ...
'' complexity and related bugs: when using shared resources typical for threaded programs, the
programmer
A computer programmer, sometimes referred to as a software developer, a software engineer, a programmer or a coder, is a person who creates computer programs — often for larger computer software.
A programmer is someone who writes/creates ...
must be careful to avoid
race conditions
A race condition or race hazard is the condition of an electronics, software, or other system where the system's substantive behavior is dependent on the sequence or timing of other uncontrollable events. It becomes a bug when one or more of t ...
and other non-intuitive behaviors. In order for data to be correctly manipulated, threads will often need to
rendezvous in time in order to process the data in the correct order. Threads may also require
mutually exclusive
In logic and probability theory, two events (or propositions) are mutually exclusive or disjoint if they cannot both occur at the same time. A clear example is the set of outcomes of a single coin toss, which can result in either heads or tails ...
operations (often implemented using
mutexes) to prevent common data from being read or overwritten in one thread while being modified by another. Careless use of such primitives can lead to
deadlock
In concurrent computing, deadlock is any situation in which no member of some group of entities can proceed because each waits for another member, including itself, to take action, such as sending a message or, more commonly, releasing a lo ...
s, livelocks or
races over resources. As
Edward A. Lee
Edward Ashford Lee (born October 3, 1957 in Puerto Rico) is an American computer scientist,
electrical engineer, and author.
He is Professor of the Graduate School and Robert S. Pepper Distinguished Professor Emeritus in the Electrical Engineeri ...
has written: "Although threads seem to be a small step from sequential computation, in fact, they represent a huge step. They discard the most essential and appealing properties of sequential computation: understandability, predictability, and determinism. Threads, as a model of computation, are wildly non-deterministic, and the job of the programmer becomes one of pruning that nondeterminism."
* ''Being untestable''. In general, multithreaded programs are non-deterministic, and as a result, are untestable. In other words, a multithreaded program can easily have bugs which never manifest on a test system, manifesting only in production.
This can be alleviated by restricting inter-thread communications to certain well-defined patterns (such as message-passing).
* ''Synchronization costs''. As thread context switch on modern CPUs can cost up to 1 million CPU cycles,
it makes writing efficient multithreading programs difficult. In particular, special attention has to be paid to avoid inter-thread synchronization from being too frequent.
Programming language support
Many programming languages support threading in some capacity.
* IBM
PL/I
PL/I (Programming Language One, pronounced and sometimes written PL/1) is a procedural, imperative computer programming language developed and published by IBM. It is designed for scientific, engineering, business and system programming. I ...
(F) included support for multithreading (called ''multitasking'') as early as in the late 1960s, and this was continued in the Optimizing Compiler and later versions. The IBM Enterprise PL/I compiler introduced a new model "thread" API. Neither version was part of the PL/I standard.
* Many implementations of
C and
C++
C++ (pronounced "C plus plus") is a high-level general-purpose programming language created by Danish computer scientist Bjarne Stroustrup as an extension of the C programming language, or "C with Classes". The language has expanded significan ...
support threading, and provide access to the native threading APIs of the operating system. A standardized interface for thread implementation is
POSIX Threads
POSIX Threads, commonly known as pthreads, is an execution model that exists independently from a language, as well as a parallel execution model. It allows a program to control multiple different flows of work that overlap in time. Each flow of ...
(Pthreads), which is a set of C-function library calls. OS vendors are free to implement the interface as desired, but the application developer should be able to use the same interface across multiple platforms. Most
Unix
Unix (; trademarked as UNIX) is a family of multitasking, multiuser computer operating systems that derive from the original AT&T Unix, whose development started in 1969 at the Bell Labs research center by Ken Thompson, Dennis Ritchie, and ot ...
platforms, including Linux, support Pthreads. Microsoft Windows has its own set of thread functions in the
process.h
process.h is a C header file which contains function declarations and macros used in working with threads and processes. Most C compilers that target DOS, Windows 3.1x, Win32, OS/2, Novell NetWare or DOS extenders supply this header and the librar ...
interface for multithreading, like
beginthread The beginthread function creates a new thread of execution within the current process. It is part of the Microsoft Windows runtime library and is declared in the process.h header file.
Prototype
unsigned long _beginthread(void(* Func)(void*), ...
.
* Some
higher level
In the Scottish secondary education system, the Higher () is one of the national school-leaving certificate exams and university entrance qualifications of the Scottish Qualifications Certificate (SQC) offered by the Scottish Qualifications ...
(and usually
cross-platform
In computing, cross-platform software (also called multi-platform software, platform-agnostic software, or platform-independent software) is computer software that is designed to work in several computing platforms. Some cross-platform software r ...
) programming languages, such as
Java
Java (; id, Jawa, ; jv, ꦗꦮ; su, ) is one of the Greater Sunda Islands in Indonesia. It is bordered by the Indian Ocean to the south and the Java Sea to the north. With a population of 151.6 million people, Java is the world's List ...
,
Python
Python may refer to:
Snakes
* Pythonidae, a family of nonvenomous snakes found in Africa, Asia, and Australia
** ''Python'' (genus), a genus of Pythonidae found in Africa and Asia
* Python (mythology), a mythical serpent
Computing
* Python (pro ...
, and
.NET Framework
The .NET Framework (pronounced as "''dot net"'') is a proprietary software framework developed by Microsoft that runs primarily on Microsoft Windows. It was the predominant implementation of the Common Language Infrastructure (CLI) until bein ...
languages, expose threading to developers while abstracting the platform specific differences in threading implementations in the runtime. Several other programming languages and language extensions also try to abstract the concept of concurrency and threading from the developer fully (
Cilk
Cilk, Cilk++, Cilk Plus and OpenCilk are general-purpose programming languages designed for multithreaded parallel computing. They are based on the C and C++ programming languages, which they extend with constructs to express parallel loops ...
,
OpenMP
OpenMP (Open Multi-Processing) is an application programming interface (API) that supports multi-platform shared-memory multiprocessing programming in C, C++, and Fortran, on many platforms, instruction-set architectures and operating syste ...
,
Message Passing Interface (MPI)). Some languages are designed for sequential parallelism instead (especially using GPUs), without requiring concurrency or threads (
Ateji PX,
CUDA
CUDA (or Compute Unified Device Architecture) is a parallel computing platform and application programming interface (API) that allows software to use certain types of graphics processing units (GPUs) for general purpose processing, an approach ca ...
).
* A few interpreted programming languages have implementations (e.g.,
Ruby MRI
Matz's Ruby Interpreter or Ruby MRI (also called CRuby) was the reference implementation of the Ruby programming language named after Ruby creator Yukihiro Matsumoto ("Matz"). Until the specification of the Ruby language in 2011, the MRI impleme ...
for Ruby,
CPython
CPython is the reference implementation of the Python (programming language), Python programming language. Written in C (programming language), C and Python, CPython is the default and most widely used implementation of the Python language.
CP ...
for Python) which support threading and concurrency but not parallel execution of threads, due to a
global interpreter lock
A global interpreter lock (GIL) is a mechanism used in computer-language interpreters to synchronize the execution of threads so that only one native thread (per process) can execute at a time. An interpreter that uses GIL always allows exactly o ...
(GIL). The GIL is a mutual exclusion lock held by the interpreter that can prevent the interpreter from simultaneously interpreting the applications code on two or more threads at once, which effectively limits the parallelism on multiple core systems. This limits performance mostly for processor-bound threads, which require the processor, and not much for I/O-bound or network-bound ones. Other implementations of interpreted programming languages, such as
Tcl
TCL or Tcl or TCLs may refer to:
Business
* TCL Technology, a Chinese consumer electronics and appliance company
**TCL Electronics, a subsidiary of TCL Technology
* Texas Collegiate League, a collegiate baseball league
* Trade Centre Limited ...
using the Thread extension, avoid the GIL limit by using an Apartment model where data and code must be explicitly "shared" between threads. In Tcl each thread has one or more interpreters.
* In programming models such as
CUDA
CUDA (or Compute Unified Device Architecture) is a parallel computing platform and application programming interface (API) that allows software to use certain types of graphics processing units (GPUs) for general purpose processing, an approach ca ...
designed for
data parallel computation
Data parallelism is parallelization across multiple processors in parallel computing environments. It focuses on distributing the data across different nodes, which operate on the data in parallel. It can be applied on regular data structures like ...
, an array of threads run
the same code in parallel using only its ID to find its data in memory. In essence, the application must be designed so that each thread performs the same operation on different segments of memory so that they can operate in parallel and use the GPU architecture.
*
Hardware description language
In computer engineering, a hardware description language (HDL) is a specialized computer language used to describe the structure and behavior of electronic circuits, and most commonly, digital logic circuits.
A hardware description language e ...
s such as
Verilog
Verilog, standardized as IEEE 1364, is a hardware description language (HDL) used to model electronic systems. It is most commonly used in the design and verification of digital circuits at the register-transfer level of abstraction. It is also ...
have a different threading model that supports extremely large numbers of threads (for modeling hardware).
See also
*
Clone (Linux system call)
In computing, particularly in the context of the Unix operating system and its workalikes, fork is an operation whereby a process creates a copy of itself. It is an interface which is required for compliance with the POSIX and Single UNIX Speci ...
*
Communicating sequential processes
In computer science, communicating sequential processes (CSP) is a formal language for describing patterns of interaction in concurrent systems. It is a member of the family of mathematical theories of concurrency known as process algebras, or pro ...
*
Computer multitasking
In computing, multitasking is the concurrent execution of multiple tasks (also known as processes) over a certain period of time. New tasks can interrupt already started ones before they finish, instead of waiting for them to end. As a result ...
*
Multi-core (computing)
A multi-core processor is a microprocessor on a single integrated circuit with two or more separate processing units, called cores, each of which reads and executes program instructions. The instructions are ordinary CPU instructions (such a ...
*
Multithreading (computer hardware)
In computer architecture, multithreading is the ability of a central processing unit (CPU) (or a single core in a multi-core processor) to provide multiple threads of execution concurrently, supported by the operating system. This approach d ...
*
Non-blocking algorithm
In computer science, an algorithm is called non-blocking if failure or suspension of any thread cannot cause failure or suspension of another thread; for some operations, these algorithms provide a useful alternative to traditional blocking im ...
*
Priority inversion
In computer science, priority inversion is a scenario in scheduling in which a high priority task is indirectly superseded by a lower priority task effectively inverting the assigned priorities of the tasks. This violates the priority model that h ...
*
Protothreads A protothread is a low-overhead mechanism for concurrent programming.
Protothreads function as stackless, lightweight threads, or coroutines, providing a blocking context cheaply using minimal memory per protothread (on the order of single bytes) ...
*
Simultaneous multithreading
Simultaneous multithreading (SMT) is a technique for improving the overall efficiency of superscalar CPUs with hardware multithreading. SMT permits multiple independent threads of execution to better use the resources provided by modern process ...
*
Thread pool pattern
In computer programming, a thread pool is a software design pattern for achieving concurrency of execution in a computer program. Often also called a replicated workers or worker-crew model, a thread pool maintains multiple threads waiting for ...
*
Thread safety Thread safety is a computer programming concept applicable to multi-threaded code. Thread-safe code only manipulates shared data structures in a manner that ensures that all threads behave properly and fulfill their design specifications without uni ...
*
Win32 Thread Information Block
In computing, the Win32 Thread Information Block (TIB) is a data structure in Win32 on x86 that stores information about the currently running thread. It is also known as the Thread Environment Block (TEB) for Win32. It descended from, and is ba ...
References
Further reading
* David R. Butenhof: ''Programming with POSIX Threads'', Addison-Wesley,
* Bradford Nichols, Dick Buttlar, Jacqueline Proulx Farell: ''Pthreads Programming'', O'Reilly & Associates,
* Paul Hyde: ''Java Thread Programming'', Sams,
* Jim Beveridge, Robert Wiener: ''Multithreading Applications in Win32'', Addison-Wesley,
* Uresh Vahalia: ''Unix Internals: the New Frontiers'', Prentice Hall,
{{DEFAULTSORT:Thread (computer science)
Concurrent computing