butex

Butex就是可以在pthread和bthread中通用的futex-link primitive

可以看到比较熟悉的API。创建，删除，wake，wait。

还有两个不是那么熟悉的，就是wake except，以及requeue

最开始的两个例子。对应了wait和wake的顺序。要么wait可以看到新的value，然后停止wait。要么wait被wake唤醒。

一个butex有一个原子量，也就是对应的futex-word。若干个等待者，还有一个lock

这里可以看出来和我们之前看的brpc内部的futex是非常类似的。只不过他用的是unordered map。这里是一个linked list

侵入式的链表，通过继承来把prev和next这两个值注入到节点中。

记录了当前的tid，以及指向butex的指针

还有两种子类，分别是bthread waiter和pthread waiter

create和destory就是从资源池中申请和释放。注意到用户拿到的是butex-word，而非butex这个对象。所以在释放的时候，我们计算value对应Butex的偏移量来拿到原始的指针。注意这里我们没有虚继承或者虚函数，所以是标准的C语言内存分布。

wake会首先锁住butex，然后取出第一个节点。

根据他是pthread还是bthread唤醒睡眠的线程。

对于pthread来说，他内部的实现就是一个futex。所以pthread睡眠就会睡在这个futex上。我们唤醒这个futex即可。

对于bthread来说，这里和timer thread相关。简单来说就是把它从timer thread中拿出来。即不再睡眠。

exchange会调用sched_to，即开始执行这个唤醒的bthread。类似yield

wake all的作用类似。只不过是唤醒了所有的等待者。同时我们yield出的worker会给第一个等待者使用

requeue中有个有意思的实现就是由于我们需要把当前butex的waiter转移到另一个butex，所以需要同时锁住两个butex。这里他用了double lock

即通过地址来保证锁的顺序。从而防止死锁。

butex的wait。最开始判断如果值不同直接结束等待

如果是pthread的话调用wait from pthread。最终还是会通过futex来等待。

否则的话他会设置超时机制。通过在timer thread中注册erase from butex and wakeup来保证我们可以在超时后被唤醒。

最后通过sched让出worker即可

erase from butex就是把结点从链表中移除。然后调用对应的wakeup

由于有可能出现竞争，即我们同时调用了wakeup和erase from butex。这时候我们需要保证只有一个人能够成功。当一个人成功的时候，他会把container设为null，从而让另一个人失败。

对于当前的bthread。我们需要在他挂起后才能把它放到等待队列中

这里wait for butex的作用就是把这个结点插入到butex中

这里的原因是只有我们调用了sched后才能说明当前的bthread睡眠了。所以如果我们先判断，再调度sched，就要求我们跨越上下文持锁，这是相当容易出错的操作。

为了保证睡眠和判断的原子性，我们先通过sched让bthread睡眠，再去判断。

上面有一个点说错了，就是unsleep if necessary的作用不是唤醒，而是根据sleep id取消对应的任务。

总的来说大概的原理比较清晰。但是可以看到他有很多很细节的处理，比如处理各个地方的race condition。比如我们还需要处理被中断的阻塞操作。

他这里描述了一个竞争的场景。本质上是一个线程拥有对象的可变引用，另一个线程拥有只读引用。当一个线程销毁对象的时候，另一个线程对该对象的访问就会崩溃。

在bthread中的解决方法就是不去释放butex，但是代价就是可能导致虚假的唤醒，因为可能一边通过butex destroy归还资源，然后由申请了新的butex，另一边才调用wakeup，从而导致虚假唤醒。这种情况很少见，并且是可接受的。

这里butex的实现细节还是相当复杂的，需要我们仔细思考。