Experiments on Concurrency

This repository is focus on experimental regarding several concurrency topics including sequenced before, happens before, synchronization, concurrent object, linearizability, universal construction, wait-free, shared memory, message passing, concurrent container, ... etc. All are implemented by C11 standard.

C11 standard

[中文筆記]
C11 standard defines multi-threaded executions and data races at §5.1.2.4 which specifies the detail regarding modification order, happens before, sequenced before_(§5.1.2.3) and other concurrency related topics.

Consider a binary relation R over a set X which R is total order if R satify:

∀ a, b ∈ X, aRb and bRa ⇒ a = b
∀ a, b, c ∈ X, aRb and bRc ⇒ aRc
∀ a, b ∈ X, aRb or bRa

Consider a set X which elements are modifications of an atomic object, and a binary relation happens before over the set X, then, we can experiments the modification order defined in C11 standard, §5.1.2.4.

This section will experiments on modification order, happens before, sequenced before.

Concurrent Queue

[中文筆記]
Experiments on implements a lock-free concurrent queue based on Michael & Scott algorithm.

This section will experiments on Harris's solution for non-blocking concurrent singly-linked list using atomic_compare_exchange_strong.

Lock-free Concurrent Thread Pool

This section is experiments on how to implements a lock-free concurrent thread pool

Concurrent Object

Consider a lock-based FIFO queue, it works correct concurrently. But, enqueue and dequeue can't takes effect concurrently, they are still sequential. This section will implements a concurrent FIFO queue without lock, compared with a lock-based implementation ^[1].

Lock-based FIFO queue
It can't takes effect concurrently, still sequential, one possibility could be like that:

  thread 1:                   lock enque unlock
  thread 2: lock enque unlock
  thread 3:                                                       lock deque unlock
  thread 4:                                     lock deque unlock

FIFO queue without lock
In this simple implementation, it only works on two threads, one for enqueue ONLY, another for dequeue ONLY.
It takes effect concurrently, one possibility could be like that:
```
thread 1:   deque
thread 2:     enque  enque
```

Linearizability is a correctness condition for concurrent objects ^[2], this section will experiments it through study the paper Linearizability: A Correctness Condition for Concurrent Objects.

Wait-Free Synchronization

This paper Wait-free synchronization shows a simple universal objects from which one can construct a wait-free implementation of any sequential object ^{[3, 4]}.

Universal Construction

This paper WaitFreeHierarchy describes consensus number, consensus objects and universality of consensus, after experiments on consensus this section will implements a wait-free universal construction ^{[5, 6]}.

Concurrent Collections in Java

As mentioned above we see a lock-based FIFO queue, now we will see how BlockingQueue, ConcurrentLinkedQueue works. This section will implements a simple lock-based FIFO queue ^[7], and implements a simple concurrent FIFO queue without lock ^[8].

jeffrey-minwei/experiments-on-concurrency