Thunderbrook commented on code in PR #136:
URL: https://github.com/apache/brpc-website/pull/136#discussion_r1159899212
##########
content/zh/docs/blogs/sourcecodes/work_stealing_queue/index.md:
##########
@@ -0,0 +1,90 @@
+---
+title: "bRPC源码解析·work_stealing_queue"
+linkTitle: "bRPC源码解析·work_stealing_queue"
+weight: 3
+date: 2023-03-27
+---
+## 背景
+每个bthread_worker都有自己的work_stealing_queue，保存着待执行的bthread，当前的bthread_worker会从queue中pop数据进行处理，如果自己的queue为空，那么会尝试去其他的bthread_worker的queue中steal，所以为了避免锁的开销，brpc设计了lock-free的WorkStealingQueue。
+
+## 实现细节
+work_stealing_queue不会发生pop和push并发的情况；可能发生并发的情况为，steal和steal，steal和push，steal和pop；
+work stealing queue的push和pop在bottom侧，steal在top侧。
+### 主要接口
+#### push
+```c++
+bool push(const T& x) {
+ const size_t b = _bottom.load(butil::memory_order_relaxed);
+ const size_t t = _top.load(butil::memory_order_acquire);
+ if (b >= t + _capacity) { // Full queue.
+ return false;
+ }
+ _buffer[b & (_capacity - 1)] = x;
+ _bottom.store(b + 1, butil::memory_order_release); // A
+ return true;
+}
+```
+首先看下push，因为steal不会修改bottom，所以bottom用relax读就好，无需同步，而top会被其他bthread_worker修改，因此通过acquire可以看到其他线程release修改top前对内存做的修改；然后判断是否超过queue的容量限制；如果没有超过容量限制，那么在bottom位置写入新数据，并更新bottom；位置A的bottom写入使用release是为了保证steal和pop能看到bottom处的数据写入。
+
+#### pop
+```c++
+bool pop(T* val) {
+ const size_t b = _bottom.load(butil::memory_order_relaxed);
+ size_t t = _top.load(butil::memory_order_relaxed);
+ if (t >= b) {
+ // fast check since we call pop() in each sched.
+ // Stale _top which is smaller should not enter this branch.
+ return false;
+ }
+ const size_t newb = b - 1;
+ _bottom.store(newb, butil::memory_order_relaxed);
+ butil::atomic_thread_fence(butil::memory_order_seq_cst); // A
+ t = _top.load(butil::memory_order_relaxed);
+ if (t > newb) {
+ _bottom.store(b, butil::memory_order_relaxed);
+ return false;
+ }
+ *val = _buffer[newb & (_capacity - 1)];
+ if (t != newb) {
+ return true;
+ }
+ // Single last element, compete with steal()
+ const bool popped = _top.compare_exchange_strong(
+ t, t + 1, butil::memory_order_seq_cst, butil::memory_order_relaxed);
+ _bottom.store(b, butil::memory_order_relaxed);
+ return popped;
+}
+```
+通过relax得到的top快速判断是否为空。然后将bottom减一，为了保证同一元素不会既被pop，又被steal，所以加了seq_cst的fence，同steal配对，具体流程后面详述；然后获取top，如果top大于newb，说明queue空，此时需将bottom修改回去；然后将val设置为newb位置的数据；如果t
!=
newb，说明队列中有不止一个数据，此时pop和steal不会竞争，因此直接返回；否则将产生竞争，如果此时top没有发生变化，即还等于t，那么说明此时没有发生steal，将top和bottom统一加一，pop的数据可用；如果top不等于t，那么说明发生了steal，此时需将bottom恢复，pop的数据不可用。
Review Comment:
done
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
