不用锁实现队列读写？

zliming

期待了解芯片组硬件的高手出来详细解析一下

daybreakcx

怎么扯上硬件实现了，囧

Solidus

这类东西我所知道的如果不用操作系统的锁的话就是CAS了，例如intel的可用lock前缀的指令，例如
lock xchg，lock前缀说白了还是个锁，只不过就是通过硬件协议把总线锁了，同时刷新所有核心的cache，但是我不认为此类东西在未来很多很多核心下性能上有什么优势可言~~

dreamice

看这个情况，肯定是没有操作系统，想自己实现一个了。主要解决的还是一个同步与互斥问题。

daybreakcx

既然是面试题，觉得扯上硬件实现就怪怪的了

Solidus

其实也不是硬件，原理解释起来得提硬件，但是编程上在WIN下就是Interlocked（自己内联汇编实现个也很easy)一族函数，俩进程或者线程做互斥也是无所谓的，因为针对的是一块共享内存，所以总线锁定同样有效，这类多进程共享内存用Interlock一族互斥在《Win核心编程》一类书上都有例子.具体实现上类似用xchg实现一个线程安全的链表类似

xhl

这个基本是使用cpu的几个特殊支持的原语来实现， 大概有4, 5中可以支持这种的原语, 但很多不通用， 要看cpu是否支持，
我以前尝试用cas cas2实现过一个. 可以做个参考。


#ifndef __LIBIGAME_LOCK_FREE_FIFO_HXX__
#define __LIBIGAME_LOCK_FREE_FIFO_HXX__

#include "Compat.hxx"

namespace IGame
{
    template <typename Type >
    class LockFreeFifo
    {
    public:
        struct Node
        {
            Type m_Data;
            Node* volatile m_Next;
            Node() : m_Data(), m_Next(NULL) {}
        };

        LockFreeFifo(Node* dummyNode) : m_Pops(0), m_Pushes(0)
        {
            m_Head = m_Tail = dummyNode;
        }

        void Insert(Node* node);
        Node* Remove();

    private:
        bool CAS(Node* volatile* _ptr, Node* oldVal, Node* newVal);
        bool CAS2(Node* volatile* _ptr, Node* oldVal1, _UInt32 oldVal2, Node* newVal1, _UInt32 newVal2);

        Node* volatile m_Head;
        volatile unsigned int m_Pops;
        Node* volatile m_Tail;
        volatile unsigned int m_Pushes;
    };
} // namespace IGame

template <typename Type >
bool LockFreeFifo<Type >::CAS(Node* volatile* _ptr, Node* oldVal, Node* newVal)
{
    register bool f;
#ifdef __GNUC__
    __asm__ __volatile__(
        "lock; cmpxchgl %%ebx, %1;"
        "setz %0;"
        : "=r"(f), "=m"(*(ptr))
        : "a"(oldVal), "b" (newVal)
        : "memory");
#else
    _asm
    {
        mov ecx, _ptr
        mov eax, oldVal
        mov ebx, newVal
        lock cmpxchg [ecx], ebx
        setz f
    }
#endif // __GNUC__

    return f;
}

template <typename Type >
bool LockFreeFifo<Type >::CAS2(Node* volatile* _ptr, Node* oldVal1, _UInt32 oldVal2,
                               Node* newVal1, _UInt32 newVal2)
{
    register bool f;
#ifdef __GNUC__
    __asm__ __volatile__(
        "lock; cmpxchg8b %1;"
        "setz %0;"
        : "=r"(f), "=m"(*(ptr))
        : "a"(oldVal1), "b" (newVal1), "c"(newVal2), "d"(oldVal2)
        : "memory");
#else
    _asm
    {
        mov esi, _ptr
        mov eax, oldVal1
        mov edx, oldVal2
        mov ebx, newVal1
        mov ecx, newVal2
        lock cmpxchg8b [esi]
        setz f
    }
#endif
    return f;
}

template <typename Type >
void LockFreeFifo<Type >::Insert(Node* node)
{
    node->m_Next = NULL;
    _UInt32 pushes;
    Node* tail;

    while (1)
    {
        pushes = m_Pushes;
        tail = m_Tail;

        // NOTE: The Queue has the same consideration as the Stack. if m_Tail is
        // freed on different thread, the this code can cause a access violation.

        // If the node that the tail points to is the last node
        // then update the last node to point at the new node.

        if (CAS(&(m_Tail->m_Next), reinterpret_cast<Node*>(NULL), node))
        {
            break;
        }
        else
        {
            // Since the tail does not point at the last node,
            // need to keep updating the tail until it does.
            CAS2(&m_Tail, tail, pushes, m_Tail->m_Next, pushes + 1);
        }
    }

    // If the tail points to what we thought was the last node
    // then update the tail to point to the new node.
    CAS2(&m_Tail, tail, pushes, node, pushes + 1);
}

template <typename Type >
Node* LockFreeFifo<Type >::Remove()
{
    Type data = Type();
    Node* head;

    while (1)
    {
        _UInt32 pops = m_Pops;
        _UInt32 pushes = m_Pushes;
        head = m_Head;
        Node* next = head->m_Next;

        // Verify that we did not get the pointers in the middle
        // of auther update.
        if (pops != m_Pops)
        {
            continue;
        }

        // Check if the queue is empty
        if (head == m_Tail)
        {
            if (next == NULL)
            {
                head = NULL; // queue is empty
                break;
            }
            // Special case if the queue has nodes but the tail
            // is just behind. Move the tail off of the head
            CAS2(&m_Tail, head, pushes, next, pushes + 1);
        }
        else if (next != NULL)
        {
            data = next->m_Data;
            // Move the head pointer, effectively removing the node
            if (CAS2(&m_Head, head, pops, next, pops + 1))
            {
                break;
            }
        }
    }

    if (head != NULL)
    {
        head->m_Data = data;
    }

    return head;
}

#endif // #ifndef __LIBIGAME_LOCK_FREE_FIFO_HXX__

zliming

这种东西在多CPU上，就是linux内核自旋锁的实现一样。锁后操作多时，不如直接用锁效率高。

用锁要线程切换，这种东西变成如果两CPU同时操作这个地址时，一个CPU要在那个禁中断死循环等那个锁开
然后 cache miss处理

zlbruce

一个线程读，一个线程写，直接用环形缓冲就行了呀，扯那么多东西干嘛
2.6的内核中就有：<linux/kfifo.h>