History of Concurrency

OSBridge | 21 Jun 2014

​

Michael Schurter

Developer @ Lytics.io

michael.schurter@gmail.com

@schmichael

What is concurrency?

...and why is it important?

Concurrency is...

...the composition of independently executing tasks.

Dependent Tasks

import redis��client = redis.Redis('localhost')�counter_key = client.get('foreign_key1')�client.incr(counter_key)

Independent Tasks

import redis��client = redis.Redis('localhost')�client.incr('counter1')�client.incr('counter2')

Concurrent Tasks

package main��import "net/http"��func main() {� go http.Get("http://google.com/?q=independent")� go http.Get("http://google.com/?q=tasks")�}

Parallelism is...

...the simultaneous execution of multiple tasks.

Concurrency vs Parallelism

• Structural
• A static property of code.
• Concurrent tasks may be executed in parallel.

• Runtime Property
• Depends on many factors:
• Hardware
• Environment
• Platform
• Configuration
• Code

Why does concurrency matter?

You cannot execute code in parallel if it is not written to be concurrent.

​

Concurrency:

Easy for computers; hard for humans.

Why should you learn about it?

• “Thousands of cores by…”
• Computers are good at concurrency.
• Humans are bad at it.
• Learn from those who have come before.

Hardware

not included

(in this talk)

Not a distributed systems talk

Xxxxx

The History of Concurrency

...everything was invented in the 60s and 70s...

• 1960 - Continuations in Algol 60
• 1962 - LEO III is the first time slicing computer; multitasking is born
• 1963 - Coroutines (implemented in Simula 67)
• 1964 - First(?) Preemptive multitasking OS: MULTICS
• 1965 - Mutexes, Semaphores (both by Dijkstra)
• 1968 - Algol 68 builds in parallelism (sema & par keywords)
• 1970 - Compare-and-Swap in IBM 370 (hardware)
• 1973 - Unix Pipes (coprocesses)
• 1973 - Actor model
• 1974 - Monitors (in Concurrent Pascal by Hoare and Hansen)
• 1975 - Continuation-passing style (for Scheme)
• 1976 - Promises (followed by implicit Futures in 1977)
• 1978 - Concurrent Sequential Processes (Transputer in the 80s)

​

All the wars have been won

1979 - The Duality Argument asserts threaded and evented systems are logically equivalent.

​

Even the performance is equivalent.

When were threads invented?

Depends on what we mean by “thread”

​

What are threads?

(Worst diagram ever.)

3 concepts to know before understanding threads...

#1 - Primitives vs. Models

Models

Design Patterns

Primitives

Primitives

Primitives

Primitives

• Processes
• Threads
• Semaphores
• Mutexes
• Monitors
• Coroutines
• Continuations

#1 Primitives, Patterns, and Models

Patterns

• Event loop dispatching
• Thread pools
• Queues
• Continuation passing
• Callbacks

​

Models

• Actor
• CSP
• SEDA

#1 Primitives, Patterns, and Models

Models evolve into Primitives

Models

Design Patterns

Primitives

Primitives

Primitives

#1 Primitives, Patterns, and Models

Evolution Example: Monitors

​

mutex + condition + object = monitor

#1 Primitives, Patterns, and Models

Modern examples of primitive evolution:

• Go exposes CSP via primitives
• Dart and Rust expose message passing primitives
• Julia provides primitives for local and distributed parallel computing

Erlang did it all in the 80s but we’ll come back to it...

#2 Task Scheduling

#1 Primitives, Patterns, and Models

If there are multiple tasks, who decides when each one executes and how?

​

The Two Scheduling Modes

Preemptive

​

Modern OS Threads

Modern OS Processes

Goroutines

Erlang Processes

UNIX Signals

Cooperative

​

Callbacks

Coroutines

Continuations

Fibers

Greenthreads

Cooperative Concurrency

• Continuations
• The ability to save and resume execution state
• Can be implemented with closures or classes less easily/fully
• Coroutines
• Subroutines that yield & resume control using continuations
• Generators (yield) are a type of coroutine
• Implicit vs. Explicit
• Issues:
• One uncooperative thread causes a deadlock
• CPU bounded tasks are awkward to handle
• Language support varies; tough to fully hack in later

Preemptive Concurrency

• Preemptive Processes
• Core feature of UNIX from the beginning (via MULTICS)
• Windows 95 & NT
• Mac OS didn’t gain it until OSX (2001)
• Core feature in AmigaOS (1985)
• Preemptive Threads
• Solaris (1993)
• Linux 2.6 (2004)
• Earlier kernels kind of had threads

#2 Task Scheduling

Modern language examples:

• Go and Erlang’s M:N threads
• Rust has configurable scheduling with M:N threads provided by a library
• Javascript and Dart are cooperative only
• Most modern languages are preemptive with libraries for cooperative

#3 Methods of Interaction

#1 Primitives, Patterns, and Models

#2 Task Scheduling

If tasks are independent, how do they communicate?

​

Shared Memory

Message Passing

Synchronization

​

Coordinate via:

• Semaphores
• Mutexes
• Monitors

Communication

​

Communicate via:

• Channels
• Signals
• Queues

Message Passing Models: Actors

#3 Methods of Interaction

• Actors are the concurrency primitive
• No shared state between Actors
• Messages are delivered asynchronously
• Often built upon threads, locks, etc.
• Inspired by Simula (1967) & Smalltalk (1969)

Erlang (1986)

#3 Methods of Interaction

Actor model in core language & runtime

Erlang’s Philosophy

#3 Methods of Interaction

“The world is concurrent

Things in the world don’t share data

Things communicate with messages

Things fail

Model this in a language” — Joe Armstrong

Message Passing Models: CSP

#3 Methods of Interaction

Communicating Sequential Processes

• Similar to Actors except:
• Processes are anonymous, channels are explicit
• Communication is synchronous (Actors are async)
• Invented by C. A. R. Hoare in 1978
• Implemented in hardware by Transputers!
• Influenced Limbo which influenced Go

#3 Methods of Interaction

Threads share memory (and therefore require synchronization which is tricky to get right).

​

"Threads, as a model of computation, are wildly non-deterministic, and the job of the programmer becomes one of pruning that nondeterminism."

#3 Methods of Interaction

— The Problem with Threads, Edward A. Lee, UC Berkeley, 2006

Threading is not a model

#3 Methods of Interaction

Threading is an important primitive

​

Build concurrency models on top of threads

Modern Frameworks: Akka (2009)

• Event driven
• Actor model with lightweight processes
• Run on threads
• Software Transactional Memory
• Update: Not anymore! Thanks @tlockney
• Distributed
• All on the JVM

3 Concurrency Concepts

1. Primitives, Patterns, and Models
2. Preemption vs. Cooperation
3. Shared Memory vs. Message Passing

Concurrency Today

C++0x, Java, Python, and Ruby

• Preemption/sharing with threads and coordination builtin.
• Global lock for Python and Ruby.
• Lots of higher level models for Java.
• Lots of cooperative libraries for all.

C#

• At first glance appears the same as Java.
• Added async/await in 2013 (C# 5.0)
• Adds native cooperation to a previously preemptive runtime.

D

• Similar to Java at first glance.
• Standard library has fibers, tasks, and message passing.

Javascript and Dart

• Only cooperative, no preemption.
• Dart has tasks and message passing.
• Javascript has callbacks & soon generators.

Go

• CSP inspired primitives.
• M:N threading.
• Single OS thread by default.
• Might change once the scheduler improves.

Rust

• Pluggable concurrency libraries.
• Safe memory sharing through ownership tracking.

​

https://air.mozilla.org/guaranteeing-memory-safety-in-rust/

​

Julia and Erlang

• Radically different languages.
• Provide high level abstractions for parallelism and distributed computing.

Haskell and Clojure

• Haskell can do whatever you want.
• STM, cooperative, preemptive, whatever.
• Clojure likewise has lots of concurrency features (and STM too!).

“New” Concurrency Primitive: STM

Software Transactional Memory

• Hardware theory in 1986; Software in 1995
• Aims to make sharing memory safe
• Thread writes a log, validates it, commits it
• Suffers a performance penalty
• Clojure, Scala, Haskell today (PyPy soon?)

The Future of Concurrency

• Primitives will continue to evolve to make abstract models easier.
• STM might make sharing OK

• New languages mean you have to care less.
• New thread scheduling syscalls in Linux?

Thanks!

Michael Schurter

michael.schurter@gmail.com

@schmichael

schmichael on Freenode

License

The text and slides are CC0 1.0 Universal (CC0 1.0) licensed.

​

The images are copyright their respective owners.