2021q1 Project (Concurrent Programming)

contributed by < ccs100203, uduru0522 >

tags: linux2021

quizzes:
ring buffer
QSBR
lock-free

Content

lock-free vs. wait-free

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

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
std::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
• The design and implementation of a lock-free ring-buffer with contiguous reservations
• CppCon 2017: Fedor Pikus “Read, Copy, Update, then what? RCU for non-kernel programmers”
• Userspace RCU library: new APIs and data structures - Mathieu Desnoyers, EfficiOS Inc.
• User-space RCU

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