Concurrent

Updated: 2020-12-31

Concurrent vs Parallel

  • Parallel: two tasks run in parallel, simultaneously; doing lots of things at once
  • Concurrent: two tasks may run simultaneously, or alternatively (on a single core, not parallel), dealing with lots of things at once.

2 Ways to Improve Concurrency

  • Async, non-blocking: Node.js/V8, Nginx
  • Sync, multithreading

Source of concurrency

Processes, threads, pools, event loops, fibers, actors, etc.

Processes vs Threads vs Coroutines / Fiber

  • Processes: self-contained execution environment;
  • Threads: share the process's resources, including memory and open files; problems to take care: thread interference and memory consistency errors
  • Coroutines / Fibers: lightweight threads that are used to perform tasks asynchronously (non-blocking), also called collaborative multithreading. only suspends its execution by explicitly calling a yield function. Fibers and coroutines are conceptually the same. Coroutines are a language-level construct, while fibers are a systems-level construct. Both fibers and threads share address space.

fork() create a new process with it's own address space

Green Threads

green threads are threads that are scheduled by a runtime library or virtual machine (VM) instead of natively 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.

Async

Coroutine / Fiber

Coroutines / Fibers use cooperative multitasking, while threads use preemptive multitasking. Threads depend on the kernel's thread scheduler to preempt a busy thread and resume another thread; fibers yield themselves to run another fiber while executing.

In languages:

  • C++20, Kotlin have coroutine.
  • Fibers don't exist in Java. Project Loom is to add fibers to OpenJDK.

Future / Promise

In languages:

  • C++11: uses both future and promise and they are different

    • std::promise is used by the "producer/writer" of the asynchronous operation.
    • std::future is used by the "consumer/reader" of the asynchronous operation.
    • the reason is to hide the "write/set" functionality from the "consumer/reader", so that future provides a read-only view
    • to get a future from a promise: auto future = promise.get_future();
  • Java: uses the word Future only
  • Javascript: uses the word Promise only

Communicating Sequential Processes (CSP)

  • The idea is that there can be two processes or threads that act independently of one another but share a "channel," which one process / thread puts data into and the other process / thread consumes.
  • the channel is shared, and can be shared by multiple producers and consumers
  • limited to the current runtime and cannot be distributed, even between two runtimes on the same physical box.
  • only buffered channel is async; sender / receiver is sync, may be blocked

In languages:

  • Go: Goroutines
  • Clojure: core.async

coroutines vs goroutines

  • goroutines imply parallelism; coroutines in general do not
  • goroutines communicate via channels; coroutines communicate via yield and resume operations

Reactive Programming

Take a = b + c for example:

  • in imperative programming, a is assigned the value of b + c, after that b and c can change without affecting the value of a
  • in reactive programming, whenever b and c changes, a will be re-evaluated.

Imperative programming is the pull model, where the sum of b and c is "pulled" into a, and only the values of b and c at that time matters; and reactive programming is the push model, that over the time, the changes of b and c will be pushed into a.

One good example of "reactive" is the speadsheet: if a cell is derived from other cells by a formula, say SUM, whenever any of the other cells change, the SUM cell will change also.

The popular React framework is not really reactive, since it compares the Virtual DOM and the real DOM and update the real DOM if necessary.

In languages:

Not all languages natively support reactive programming, but there are third party libraries available. For example, ReactiveX adds Observables to different languages, including RxJava for Java; reactive-streams is another effort for Java.

Actor Model

  • Actors have their own mailbox
  • you have to have a reference (Akka) or PID (Erlang) to the other actor in order to send it a message
  • fault tolerance
  • actor can have mutable state inside of it and a guarantee of no multithreaded access to the state
  • sender is async, only receiver can be blocked
  • good for distributed system

In languages:

  • Scala: Akka
  • Erlang

Multiprocessing / Multithreading

Common problems: Memory-interference, race conditions, deadlock, live lock and starvation

Work-sharing vs Work-stealing

Source: https://rakyll.org/scheduler/

In multi-threaded computation, two scheduling paradigms: work-sharing and work-stealing.

  • Work-sharing: When a processor generates new threads, it attempts to migrate some of them to the other processors with the hopes of them being utilized by the idle / underutilized processors.
  • Work-stealing: An underutilized processor actively looks for other processor’s threads and “steal” some.

IPC

IPC: Inter Process Communication.

  • Shared Memory
  • Pipes
  • Sockets
  • RPC (Remote procedure call)

IPC is used not just for communication between processes on the same system, but processes on different systems.

Lock vs Mutex vs Semaphore vs Monitor

  • Lock: not shared with any other processes

    • Read/write lock: unlimited number of readers or 1 writer at any given time
  • Mutex (mutual exclusion): same as Lock but can be shared by multiple processes, or system wide

    • A mutex is meant to be taken and released by the task.
  • Semaphores: same as Mutex but allows X number of threads to enter (so ). Can be used as both locks and condition variables.

    • a binary semaphore is similar to a mutex, however, a semaphore is for signaling from one task to another.
  • Monitor: can wait for a certain condition, e.g. when the lock is released

Monitor

Monitors provide a mechanism for threads to temporarily give up exclusive access in order to wait for some condition to be met, before regaining exclusive access and resuming their task.

Monitor = a mutex (lock) + condition variables

Condition Variable: a container of threads that are waiting on a certain condition.

In multi-threaded programs, it is often useful for a thread to wait for some condition to become true before proceeding.

Solutions:

  • spinning until the condition becomes true (inefficient)
  • by condition variables: A condition variable is an explicit queue that threads can put themselves on when waiting for a condition

Critical Section

If one thread is in the critical section, it excludes the others from entering until it has completed the section.

Lock

Implementations: (need hardware support)

  • disable interrupts (does not work on multiprocessors)
  • test-and-set instruction (a.k.a. atomic exchange)
  • compare-and-swap (compare-and-exchange) instruction
  • fetch-and-add instruction

instead of spinning:

  • yield
  • sleep

Deadlock vs Starvation vs Livelock

  • deadlock: dining philosophers, bow
  • starvation,
  • livelock: two people attempting to pass each other in a corridor

Imagine a little dog snuck under Big Dog's cone of shame and covered the food with its own cone of shame, and it won't leave. That's deadlock. Imagine a stream of little dogs sneaking under Big Dog's cone so Big Dog nevers gets a bite. That's livelock.

By Languages

C++

  • C++11: std::promise, std::future
  • C++20: coroutine

Java

Built-in solution:

  • multi-thread. JVM natively supports multithreading running on multiple cores.
  • Future (since Java 5) and CompletableFuture (since Java 8)

Third party libs: ReactiveX, Akka.

Javascript

Javascript executes in a single-threaded event loop. async, await, and promises.

Python: GIL (Global interpreter lock)

CPython is effectively single-threaded: the interpreter doesn’t support fine-grained locking mechanism like JVM, any thread must hold the GIL to access the memory space, i.e. a Python object can be used by only one thread at a time.

Multithreaded, CPU-bound operations either need to be handled by way of C extensions or multiple instances of CPython.

Go

Use Channels and goroutines.

Kotlin

Coroutines.

PHP

PHP runs in Nginx which doesn't have a thread based architecture, so we do not use locks or spawn new threads