# 2021q1 Project (Concurrent Programming)
contributed by < `ccs100203`, `uduru0522` >
###### tags: `linux2021`
> quizzes:
> [ring buffer](https://hackmd.io/@sysprog/SyrHd-cF_)
> [QSBR](https://hackmd.io/@sysprog/linux2021-quiz17)
> [lock-free](https://hackmd.io/@sysprog/linux2021-quiz18)

## Content

### lock-free vs. wait-free
> [Lock-free vs. wait-free concurrency](https://rethinkdb.com/blog/lock-free-vs-wait-free-concurrency)
- lock-free
While a given thread might be blocked by other threads, all CPUs can continue doing other useful work without stalls.
In soft latency requirements, lock-free is a good compromise between development complexity and high concurrency. e.g. database
- wait-free
Wait-free ensure that in addition to all CPUs continuing to do useful work, no computation can ever be blocked by another computation.
In hard real-time requirements, wait-free is a good candidate to achieve the limitation. e.g. nuclear reactor

### lock-free ring-buffer with contiguous reservations
> [The design and implementation of a lock-free ring-buffer with contiguous reservations](https://ferrous-systems.com/blog/lock-free-ring-buffer/)

Focus this issue, if we have chunks of data that should remain contiguous in memory when written to the ring-buffer, but it doesn't fit in the remaining buffer space after `write`.

We aren't allowed to split it. So, we put this data at the begin in the buffer, and distinguish between valid and invalid data by `watermark` to avoid read a invalid chunk.

### Memory Ordering
> [Ordering](https://doc.rust-lang.org/std/sync/atomic/enum.Ordering.html)
> [std::memory_order](https://en.cppreference.com/w/cpp/atomic/memory_order)
#### Release-Acquire ordering
> If an atomic store in thread A is tagged memory_order_release and an atomic load in thread B from the same variable is tagged memory_order_acquire, all memory writes (non-atomic and relaxed atomic) that happened-before the atomic store from the point of view of thread A, become visible side-effects in thread B. That is, once the atomic load is completed, thread B is guaranteed to see everything thread A wrote to memory.

在 Release-Acquire ordering 中，假設 thread A 為 release 而 thread B 為 acquire，那麼當 thread B 的 atomic load 完成時，也保證 thread B 會看到所有 thread A 寫進 memory 的東西。

### quiz14 ring-buffer
WIP

## Reference
- [Lock-free vs. wait-free concurrency](https://rethinkdb.com/blog/lock-free-vs-wait-free-concurrency)
- [The design and implementation of a lock-free ring-buffer with contiguous reservations](https://ferrous-systems.com/blog/lock-free-ring-buffer/)
- [CppCon 2017: Fedor Pikus “Read, Copy, Update, then what? RCU for non-kernel programmers”](https://www.youtube.com/watch?v=rxQ5K9lo034)
- [Userspace RCU library: new APIs and data structures - Mathieu Desnoyers, EfficiOS Inc.](https://www.youtube.com/watch?v=yOoWvdBFFRs)
- [User-space RCU](https://lwn.net/Articles/573424/)

## Meeting Record
### 2021/06/25 Meeting Record
研究 quiz 14 跟 17 的 RCU 機制，解讀程式並進行評測。
研讀老師給的幾篇關於 concurreny、RCU 的文章以及影片

### 2021/05/31 Meeting Record (Sort)
#### Recap
1. Hybrid Sort: e.g. pdqsort + introsort
2. Trace corner case: uml + gdb
3. Corner case: Hybrid sort as ref.
4. Number of Comparison: send mail to author

#### Note
1. Care branch miss-prediction & cache miss
2. Create specific benchmark program for testing
3. Send the fucking email to lovely Torvald :D

#### Reference
1. [kdrag0n/allocbench](https://github.com/kdrag0n/allocbench)