# Concurrency, multi-threading and parallel programming concepts
This document describes various concurrency, multi-threading, parallel programming methods and concepts. The purpose is to write a single document/wiki that contains everything you need to know about concurrency. Things should be explained clearly yet in as great detail as possible. **You are welcome to contribute to this document.**
*If you are interested in contributing to this document, you can ask me to add you as a contributor or you can just fork this.*
*Note 1: This document mainly discusses modern OS and hardware.*
*Note 2: While attention is paid to what is written here, there is no guarantee that this document is correct at its entirety.*
# Table of Contents
#### Approaches to concurrency
* [Processes](https://github.com/kaisellgren/Concurrency-concepts/blob/master/#Processes)
* [Threads](https://github.com/kaisellgren/Concurrency-concepts/blob/master/#Threads)
* [Green Threads](https://github.com/kaisellgren/Concurrency-concepts/blob/master/#GreenThreads)
* [Green Processes](https://github.com/kaisellgren/Concurrency-concepts/blob/master/#GreenProcesses)
* [Isolates](https://github.com/kaisellgren/Concurrency-concepts/blob/master/#Isolates)
#### Synchronization primitives
* [Locks](https://github.com/kaisellgren/Concurrency-concepts/blob/master/#Locks)
* [Mutex](https://github.com/kaisellgren/Concurrency-concepts/blob/master/#Mutex)
* [Semaphores](https://github.com/kaisellgren/Concurrency-concepts/blob/master/#Semaphores)
* [Monitors](https://github.com/kaisellgren/Concurrency-concepts/blob/master/#Monitors)
* [Message Passing](https://github.com/kaisellgren/Concurrency-concepts/blob/master/#MessagePassing)
#### Higher-Level Frameworks and Languages
* [Microsoft's TPL and other asynchronous features] (#TPL)
* [Apple's GCD and blocks] (#GCD)
* [Clojure] (#Clojure)
* [Erlang] (#Erlang)
* [Node.js] (#Node.js)
* [Python gevent] (#gevent)
* [HTML5 Web Workers] (#WebWorkers)
## Processes
Processes are [operating system](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://en.wikipedia.org/wiki/Operating_system) (OS) managed and in case of a modern OS they are truly concurrent in the presence of suitable hardware support ([multiprocessor](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://en.wikipedia.org/wiki/Multiprocessor) and [multicore](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://en.wikipedia.org/wiki/Multi-core_processor) systems).
Processes are scheduled by the operating system's [scheduler](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://en.wikipedia.org/wiki/Scheduling_(computing\)). They may be made up of multiple [threads of execution](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://en.wikipedia.org/wiki/Thread_(computer_science\)) that execute instructions concurrently.
Processes exist within their own [address space](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://en.wikipedia.org/wiki/Address_space). No other process can read or write to another one's memory, because the OS secures this with [process isolation](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://en.wikipedia.org/wiki/Process_isolation) as the OS is the one who manages the processes.
Processes are heavy and spawning many of them (in contrast to other concurrency models) is not recommended. Creating a process requires creating an entirely new [virtual address space](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://en.wikipedia.org/wiki/Virtual_address_space).
[Context switching](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://en.wikipedia.org/wiki/Context_switch) between processes requires a lot of work. This means saving of the entire CPU state (all [processor registers](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://en.wikipedia.org/wiki/Processor_register) that were in use, [program counter](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://en.wikipedia.org/wiki/Program_counter), etc.) into [PCB](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://en.wikipedia.org/wiki/Process_control_block) (usually). Context switching also involves switching the [MMU](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://en.wikipedia.org/wiki/Memory_management_unit) context and keeping OS related data.
Processes can't talk to each other directly (in modern OS). Instead the OS provides facilities for [inter-process communication](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://en.wikipedia.org/wiki/Inter-process_communication).
Typical ways of inter-process communication involve [files](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://en.wikipedia.org/wiki/Computer_file), [signals](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://en.wikipedia.org/wiki/Signal_(computing\)), [sockets](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://en.wikipedia.org/wiki/Berkeley_sockets), [message queues](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://en.wikipedia.org/wiki/Message_queue), ([named](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://en.wikipedia.org/wiki/Named_pipe)) [pipes](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://en.wikipedia.org/wiki/Pipeline_(Unix\)), [semaphores](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://en.wikipedia.org/wiki/Semaphore_(programming\)), [shared memory](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://en.wikipedia.org/wiki/Shared_memory) and even [memory-mapped files](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://en.wikipedia.org/wiki/Memory-mapped_file).
Processes are all about [preemptive multitasking](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://en.wikipedia.org/wiki/Computer_multitasking#Preemptive_multitasking.2Ftime-sharing) (today) meaning that the OS decides when a process is preempted ("goes to sleep") and which process goes "alive" next.
## Threads
Threads, like processes, are also OS managed. Threads share the same address space of their [parent process](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://en.wikipedia.org/wiki/Parent_process). This means that processes can spawn threads indirectly using OS provided functionality (e.g. [CreateThread](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://msdn.microsoft.com/en-us/library/ms885186.aspx) or [pthread_create](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://www.kernel.org/doc/man-pages/online/pages/man3/pthread_create.3.html)).
On a single processor, multithreading generally occurs by [time-division multiplexing](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://en.wikipedia.org/wiki/Time-division_multiplexing) (as in [multitasking](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://en.wikipedia.org/wiki/Computer_multitasking)): the processor switches between different threads. This [context switching](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://en.wikipedia.org/wiki/Context_switch) generally happens frequently enough that the user perceives the threads or tasks as running at the same time. On a [multiprocessor](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://en.wikipedia.org/wiki/Multiprocessor) (including [multi-core](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://en.wikipedia.org/wiki/Multi-core) system), the threads or tasks will actually run at the same time, with each processor or core running a particular thread or task.
Many modern operating systems directly support both [time-sliced](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://en.wikipedia.org/wiki/Preemption_(computing\)#Time_slice) and multiprocessor threading with a [process scheduler](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://en.wikipedia.org/wiki/Scheduling_(computing\)).
Like processes, threads are about [preemptive multitasking](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://en.wikipedia.org/wiki/Computer_multitasking#Preemptive_multitasking.2Ftime-sharing) and the OS decides when they are preempted. To avoid preemption with threads, [mutex](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://en.wikipedia.org/wiki/Mutual_exclusion) can be used. Windows also offers support for [Critical Sections](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://en.wikipedia.org/wiki/Critical_section) with two functions [EnterCriticalSection](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://msdn.microsoft.com/en-us/library/ms885212.aspx) and [LeaveCriticalSection](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://msdn.microsoft.com/en-us/library/bb202768.aspx).
Communication between threads is far simpler than [inter-process communication](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://en.wikipedia.org/wiki/Inter-process_communication) between processes. This is mainly due to the shared memory, but also due to the fact that the [strict security constraints](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://en.wikipedia.org/wiki/Process_isolation) the OS puts on processes do not exist with threads.
#### Memory usage
Threads are generally said to be "lightweight", but that is relative. Threads have to support the execution of [native code](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://en.wikipedia.org/wiki/Machine_code) so the OS has to provide a decent-sized [stack](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://en.wikipedia.org/wiki/Stack-based_memory_allocation), usually measured in megabytes. In Windows, the [default stack reservation size](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://msdn.microsoft.com/en-us/library/windows/desktop/ms686774(v=vs.85\).aspx) used by the linker is 1 MB. In Linux, the typical [thread stack size](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://www.kernel.org/doc/man-pages/online/pages/man3/pthread_create.3.html) is between 2 MB and 10 MB. This means that in Linux, creating 1000 threads would equal to memory usage from ~2 GB to ~10 GB, without even beginning to do any actual work with the threads.
##### Determining stack size on Linux
You can rather easily determine the default stack size for Linux OS by running the following:
```
$ ulimit -a | grep stack
stack size (kbytes, -s) 8192
```
The above output was from Ubuntu 11 x86. We can also test this with some code:
```c
void makeTenThreads()
{
std::vector
threads;
for (int i = 0; i < 10; i++)
{
threads.push_back(pthread_t(0));
pthread_create(&threads.back(), 0, &doNothing2, 0);
}
std::vector::iterator itr = threads.begin();
while (itr != threads.end())
{
pthread_join(*itr, 0);
++itr;
}
sleep(11);
threads.clear();
}
int main()
{
makeTenThreads();
sleep(10);
}
```
Running `pmap -x 1234` where `1234` is the PID will give us 10 x 8192K blocks allocated, because we created 10 threads and each of them got 8 MB allocated.
##### Setting the stack size
Thread default stack size varies depending on the OS and you can actually set it on your own. On Linux, you call [pthread_attr_setstacksize](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://www.kernel.org/doc/man-pages/online/pages/man3/pthread_attr_setstacksize.3.html) and on Windows it can be specified as a parameter to [CreateThread](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://msdn.microsoft.com/en-us/library/ms885186.aspx).
The number of threads a process can create is limited by the available virtual memory and depends on the default stack size. On Windows, if every thread has 1 MB of stack space, you can create a maximum of 32 threads. If you reduce the default stack size, you can create more threads. These details vary greatly depending on the platform and libraries.
Reducing the thread stack size will not reduce overhead in terms of CPU or performance. Your only limit in this respect is the total available virtual address space given to threads on your platform. Generally you should not change the stack size, because you can't really compute how much you need for an arbitrary thread, as it totally depends on the code run. You would have to analyze the entire code and the resulting disassembly executed by the thread to know how much stack size to use. This is non-trivial.
#### "Threads are lightweight"
Threads are "lightweight processes", not "lightweight" themselves as some may claim. They require less resources to create and to do context switching as opposed to processes, but it still is not cheap to have many of them running at the same time.
While thread context switching still involves restoring of [the program counter](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://en.wikipedia.org/wiki/Program_counter), CPU [registers](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://en.wikipedia.org/wiki/Processor_register), and other potential OS data, they do not need the context switch of an [MMU](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://en.wikipedia.org/wiki/Memory_management_unit) unlike processes do, because threads share the same memory. Context switching with threads is less of a problem unless you have many threads.
#### Race conditions
Since memory/data is shared among threads in the same process, applications frequently need to deal with [race conditions](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://en.wikipedia.org/wiki/Race_conditions). [Thread Synchronization](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://en.wikipedia.org/wiki/Synchronization_(computer_science\)#Thread_or_process_synchronization) is needed. Typical synchronization mechanisms include [Locks](https://github.com/kaisellgren/Concurrency-concepts/blob/master/Locks), [Mutex](https://github.com/kaisellgren/Concurrency-concepts/blob/master/Mutex), [Monitors](https://github.com/kaisellgren/Concurrency-concepts/blob/master/Monitors) and [Semaphores](https://github.com/kaisellgren/Concurrency-concepts/blob/master/Semaphores). These are concurrency constructs used to ensure two threads won't access the same shared data at the same time, thus achieving correctness.
Programming with threads involve hazardous race conditions, deadlocks and livelocks. This is often said to be one of the bad things about threads along with the overhead they bring.
#### Summary
Threads are good for concurrent CPU heavy work across 1-n processors and cores within a single application/process. This is, because they scale to cores and CPUs thanks to the OS scheduler. For IO heavy work, threads are a nightmare, because that usually involves spawning of multiple threads for shorter periods of time.
##### When to use
* You need plenty of CPU.
* You keep the threads running for a longer time.
* You do not spawn and kill and spawn and kill threads too often.
* You do not need many threads.
An example of a good use for a thread could be a game. Running e.g. AI logic on a separate thread makes sense, because the thread is spawned once and kept alive for a long time. AI logic also requires plenty of CPU making threads very good for such purposes.
Short-lived, frequently spawned threads make little sense. Building a chat web application that involves 1000 concurrent active chatters are an example when not to use threads. Memory usage would be high, context switching would take too much time relative to the actual application. Creating threads and killing them that often has an unacceptable high overhead. A chat requires more IO than CPU work, thus, threads do not suit that situation.
## Green Threads
Green threads are [threads](https://github.com/kaisellgren/Concurrency-concepts/blob/master/Threads) that are scheduled by a virtual machine (VM). In contrast, typical threads are scheduled by the underlying operating system. Green threads emulate multithreaded environments without relying on any native OS capabilities, and they are managed in user space instead of kernel space, enabling them to work in environments that do not have native thread support.
Native threads can switch between threads pre-emptively, switching control from a running thread to a non-running thread at any time. Green threads only switch when control is explicitly given up by a thread (Thread.yield(), Object.wait(), etc.) or a thread performs a blocking operation (read(), etc.). Whether a blocking call causes yielding depends on the virtual machine implementation.
On multi-CPU machines, native threads can run more than one thread simultaneously by assigning different threads to different CPUs. Green threads run on only one CPU, because every green thread runs on the same operating system thread. This means that a green thread that blocks will block every other green thread as well.
Green threads can be started much faster on some VMs. They significantly outperform Linux native threads on thread activation and synchronization. Native threads have better performance on I/O and context switching operations, however.
Green threads are a good choice over native threads if the platform does not provide support for threading. Another reason is that if your code is not thread-safe or if you need to spawn many threads and often since this is cheaper with green threads.
The Erlang virtual machine has what might be called ['green processes'](https://github.com/kaisellgren/Concurrency-concepts/blob/master/Green Processes) - they are like operating system processes (they do not share state like threads do) but are implemented within the Erlang Run Time System (erts). These are sometimes erroneously cited as green threads.
#### Summary
Green threads are rarely used nowadays. They provide little use and have their drawbacks.
##### When to use
* The underlying platform does not provide support for threads.
* We need to spawn many threads or often.
* Our code is not thread-safe.
## Green Processes
Green processes are like operating system processes except that they are implemented in a virtual machine on the user space. This means that green processes do not share state like threads do, freeing us from the race condition hazards that threads pose.
The Erlang Run Time System (erts) implements green processes. These are sometimes erroneously cited as green threads.
Green processes are neither operating system processes nor threads, but lightweight processes. It has been estimated that [Erlang's green processes take around 300 WORDs](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://www.erlang.org/doc/efficiency_guide/processes.html) to create, thus many of them can be created without degrading the performance. It has also been proven to be possible to create even [20 million processes](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://groups.google.com/group/comp.lang.functional/msg/33b7a62afb727a4f?dmode=source). These figures are highly implementation dependent, but they show the potential of green processes.
One reason why green processes can be so lightweight as opposed to operating system processes is that green processes totally lack of any type of security restrictions or other unnecessary overhead that the OS has to put on its processes. Another reason for their lightness is that the virtual machine is fully aware of the application that uses these processes, unlike in case of an OS that has less of an idea of what an application might do.
Inter-process communication works via shared-nothing asynchronous message passing style. The use of message passing eliminates hazards such as deadlocks and livelocks that threads have and allow for clean communication.
## Isolates
Isolates are a concurrency mechanism used in [Google Dart](https://github.com/kaisellgren/Concurrency-concepts/blob/master/http://dartlang.org). Isolates are spawned and use [message passing](https://github.com/kaisellgren/Concurrency-concepts/blob/master/Message Passing). They are inspired by Erlang's [green processes](https://github.com/kaisellgren/Concurrency-concepts/blob/master/Green Processes).
There are two types of isolates, heavy and light. These two differ dramatically, and the programmer has to know which one to use in which scenario. Luckily isolates offer an intuitive API that works the same way for both light and heavy isolates so it is easy to change the type of an isolate at any time.
Isolates are independent of each other. This means they do not share state as one might guess from the use of [message passing](https://github.com/kaisellgren/Concurrency-concepts/blob/master/Message Passing).
#### Heavy isolates
Heavy isolates use [threads](https://github.com/kaisellgren/Concurrency-concepts/blob/master/Threads) behind the scenes. Typical synchronization mechanisms such as [locks](https://github.com/kaisellgren/Concurrency-concepts/blob/master/Locks) and [monitors](https://github.com/kaisellgren/Concurrency-concepts/blob/master/Monitors) are not needed nor do they exist in the programmers eyes. Heavy isolates use [message passing](https://github.com/kaisellgren/Concurrency-concepts/blob/master/Message Passing) and internally rely on operating system threads. It's up to the implementation to decide what kind of synchronization mechanism to use (e.g. [monitors](https://github.com/kaisellgren/Concurrency-concepts/blob/master/Monitors)) and that mechanism may even vary depending on scenarios.
Due to use of [message passing](https://github.com/kaisellgren/Concurrency-concepts/blob/master/Message Passing) you are free from [thread related problems](https://github.com/kaisellgren/Concurrency-concepts/blob/master/Threads) such as deadlocks and spinlocks. Heavy isolates are essentially a nice implementation on top of native [threads](https://github.com/kaisellgren/Concurrency-concepts/blob/master/Threads).
#### Light isolates
Light isolates are different from heavy isolates in the sense that the underlying implementation does not use [threads](https://github.com/kaisellgren/Concurrency-concepts/blob/master/Threads). Light isolates are single-threaded, they live on the thread that spawned the light isolate. For example, one may spawn two heavy isolates which both spawn a light isolate and in this case, you would have two native [threads](https://github.com/kaisellgren/Concurrency-concepts/blob/master/Threads) both running one light isolate.
Light isolates are very efficient in context switching and to create/kill. And in fact, it is very well possible to create millions of light isolates. This allows for concurrent, real-time, web applications for instance.
Beware that blocking in a light isolate blocks the rest of the isolates on that thread.
##### Heavy vs light isolates
Heavy isolates come with some of the benefits and drawbacks of threads. The same applies to light isolates, they come with the problems and benefits of single-threaded evented systems.
##### When to use heavy isolates
* You need CPU heavy work.
* You do not need multiple isolates.
* You are not spawning and killing isolates too often.
##### When to use light isolates
* You are IO bound rather than CPU bound.
* You need several isolates or you spawn/kill them frequently.
If you were to program a game, you should use heavy isolates for the AI. If you were programming a web server, you would use light isolates for handling requests.
There is no reason not to use both and in fact, using both at times makes sense.
#### Communication
As said earlier, isolates rely on [message passing](https://github.com/kaisellgren/Concurrency-concepts/blob/master/Message Passing). There is no shared data and communication is done through ports. This communication allows you to also restart parts of the program if something goes wrong and an isolate lives as long as its port(s) are open. The [message passing](https://github.com/kaisellgren/Concurrency-concepts/blob/master/Message Passing) is asynchronous.
Here's an example code sample written in Dart:
```java
class Worker extends Isolate {
Worker() : super.heavy();
main() {
this.port.receive(
void _(var message, SendPort replyTo) {
print("Message received: ${message}");
replyTo.send("sup");
this.port.close();
}
);
}
}
```
The Worker class extends the Isolate class, and when it's instantiated, it calls th ... ...