无锁编程

无锁编程有两个关键点:

  • 原子操作或者cas原语
  • aba问题
inline bool CAS(pointer_t *addr, pointer_t &old_value, pointer_t &new_value)
{
    bool ret;
    __asm__ __volatile__(
    "lock cmpxchg16b %1;\n"
    "sete %0;\n"
    :"=m"(ret),"+m" (*(volatile pointer_t *) (addr))
    :"a" (old_value.ptr), "d" (old_value.tag), "b" (new_value.ptr), "c" (new_value.tag));
    return ret;
}

lock锁地址总线
aba问题:在读取v值和进行cas操作前,如果有一个线程将v值由a改成b,另外一个线程在将b改成了a,就会cas操作混乱。解决方法是用标记或版本编号与进行CAS操作的每个值相关联,并原子的更新值和标记。
 
入队列

EnQueue (x) //进队列改良版
{
    q = new record ();
    q->value = x;
    q->next = NULL;
    p = tail;
    oldp = p
    do {
        while (p->next != NULL)
            p = p->next;
    } while( CAS (p.next, NULL, q) != TRUE); //如果没有把结点链上,再试
    CAS (tail, oldp, q); //置尾结点
}

出队列

DeQueue () //出队列
{
    do{
        p = head;
        if (p->next == NULL){
            return ERR_EMPTY_QUEUE;
        }
    while( CAS (head, p, p->next);
    return p->next->value;
}

 
https://www.codeproject.com/Articles/153898/Yet-another-implementation-of-a-lock-free-circular
http://www.drdobbs.com/parallel/writing-lock-free-code-a-corrected-queue/210604448?pgno=1
https://blog.csdn.net/chenjiayi_yun/article/details/16333595
https://blog.csdn.net/mergerly/article/details/39009473 scsp无锁kfifo队列