不用鎖實現(xiàn)隊列讀寫？

zliming

期待了解芯片組硬件的高手出來詳細解析一下

daybreakcx

怎么扯上硬件實現(xiàn)了，囧

Solidus

這類東西我所知道的如果不用操作系統(tǒng)的鎖的話就是CAS了，例如intel的可用lock前綴的指令，例如
lock xchg，lock前綴說白了還是個鎖，只不過就是通過硬件協(xié)議把總線鎖了，同時刷新所有核心的cache，但是我不認為此類東西在未來很多很多核心下性能上有什么優(yōu)勢可言~~

dreamice

看這個情況，肯定是沒有操作系統(tǒng)，想自己實現(xiàn)一個了。主要解決的還是一個同步與互斥問題。

daybreakcx

既然是面試題，覺得扯上硬件實現(xiàn)就怪怪的了

Solidus

其實也不是硬件，原理解釋起來得提硬件，但是編程上在WIN下就是Interlocked（自己內(nèi)聯(lián)匯編實現(xiàn)個也很easy)一族函數(shù)，倆進程或者線程做互斥也是無所謂的，因為針對的是一塊共享內(nèi)存，所以總線鎖定同樣有效，這類多進程共享內(nèi)存用Interlock一族互斥在《Win核心編程》一類書上都有例子.具體實現(xiàn)上類似用xchg實現(xiàn)一個線程安全的鏈表類似

xhl

這個基本是使用cpu的幾個特殊支持的原語來實現(xiàn)， 大概有4, 5中可以支持這種的原語, 但很多不通用， 要看cpu是否支持，
我以前嘗試用cas cas2實現(xiàn)過一個. 可以做個參考。


#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內(nèi)核自旋鎖的實現(xiàn)一樣。鎖后操作多時，不如直接用鎖效率高。

用鎖要線程切換，這種東西變成如果兩CPU同時操作這個地址時，一個CPU要在那個禁中斷死循環(huán)等那個鎖開
然后 cache miss處理

zlbruce

一個線程讀，一個線程寫，直接用環(huán)形緩沖就行了呀，扯那么多東西干嘛
2.6的內(nèi)核中就有：<linux/kfifo.h>