Lock-Free Queue?

This is a discussion on Lock-Free Queue? within the Windows Programming forums, part of the Platform Specific Boards category; Hello, I had a go a while back at making a lock-free queue (one thread will not be held up ...

  1. #1
    Registered /usr
    Join Date
    Aug 2001
    Location
    Newport, South Wales, UK
    Posts
    1,266

    Unhappy Lock-Free Queue?

    Hello,

    I had a go a while back at making a lock-free queue (one thread will not be held up waiting for the other to finish what it's doing). This is based around the idea of one and only one thread adding items to the queue and one and only one thread removing items from it.

    It works around the idea of two lists. At any time, one list is available to each thread to add/remove items.

    When the producing thread is finished adding it manually calls QueueFlush() to swap the lists. (I couldn't work out an automatic way of doing this that was efficient. Swapping the lists every time something was added seemed inefficient)

    The consuming thread calls QueueRecv() to retrieve a pointer to its list. The pointer is removed from the queue structure, thus preventing the other thread from accidentally getting access to it.
    Code:
    typedef struct {
        t_list *plistQueue;
        t_list *plistSwap;
    } t_msgqueue;
    
    int QueueRecv(t_msgqueue *pQueue, t_list **pplistMsgs)
    {
        t_list *plist;
    
        *pplistMsgs = NULL;
        if (!pQueue)
            return -1;
    
        // plistQueue is what we want to retrieve
        plist = InterlockedExchangePointer(&pQueue->plistQueue, pQueue->plistSwap);
        InterlockedExchangePointer(&pQueue->plistSwap, plist);
        if (plist->uiCount > 0)
        {
            *pplistMsgs = plist;
            return plist->uiCount;
        }
        else
            return 0;
    
    }
    
    int QueueSend(t_msgqueue *pQueue, unsigned int uiMsgID, int iParam1, void *pParam2)
    {
        t_msg *pMsg;
    
        if (!pQueue)
            return -1;
    
        pMsg = lalloc(sizeof(*pMsg));
        if (!pMsg)
            return -1;
    
        pMsg->uiMsgID = uiMsgID;
        pMsg->iParam1 = iParam1;
        pMsg->pParam2 = pParam2;
        linsert(pQueue->plistQueue, pMsg, NULL);
        return 0;
    }
    
    void QueueFlush(t_msgqueue *pQueue)
    {
        // swap pointers
        InterlockedExchangePointer(&pQueue->plistSwap, InterlockedExchangePointer(&pQueue->plistQueue, pQueue->plistSwap));
    }
    The only problem is, it works, some of the time...
    Any ideas?

  2. #2
    Registered User
    Join Date
    Sep 2004
    Location
    California
    Posts
    3,265
    That code doesn't appear to be thread safe. I don't see anything that prevents linsert() from adding to the queue the same time that QueueRecv() is returning the same queue.

    Thread 1 calls QueueSend() and goes into linsert().
    Thread 2 calls QueueRecv() and swaps the lists. This doesn't change the fact that thread 1 still has a pointer to this list inside linsert().
    bit∙hub [bit-huhb] n. A source and destination for information.

  3. #3
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Anyone mind if I poke in a question for bithub here?

    Could this be done with a single queue and mutex (on Windows)?

    (I know the OP is talking about lock free... I hope you don't mind the sidebar...)

  4. #4
    Registered User
    Join Date
    Sep 2004
    Location
    California
    Posts
    3,265
    Quote Originally Posted by CommonTater View Post
    Anyone mind if I poke in a question for bithub here?

    Could this be done with a single queue and mutex (on Windows)?

    (I know the OP is talking about lock free... I hope you don't mind the sidebar...)
    Yeah, you just have to lock down the entire internal list for both QueueSend() and QueueRecv(). In fact, I have a feeling that the lock free implementation of a queue would still only involve one list. I've never attempted my own lock-free implementation before though, so there might be some unforseen issues with that.
    bit∙hub [bit-huhb] n. A source and destination for information.

  5. #5
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by bithub View Post
    Yeah, you just have to lock down the entire internal list for both QueueSend() and QueueRecv().
    So I would use mutexes (which I've used before) to only allow one thread access (read or write) at a time... Ok...it relates to a project in the planning stages... so I'll play with it and see what I can do. In the mean time I'll let you get back with the OP... thanks!

  6. #6
    Registered /usr
    Join Date
    Aug 2001
    Location
    Newport, South Wales, UK
    Posts
    1,266
    I haven't forgotten about this but you've given me an "oh" moment. When I get a few spare minutes I'll scribble it out on paper and come up something more correct (I'm thinking about seizing the list pointer in QueueSend as well as QueueRecv).

    Aren't threads fun?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Permenet Lock?
    By Queatrix in forum Windows Programming
    Replies: 9
    Last Post: 06-28-2007, 01:40 PM
  2. lock and unlock
    By munna_dude in forum C Programming
    Replies: 2
    Last Post: 05-18-2007, 06:52 AM
  3. lock
    By siavoshkc in forum C# Programming
    Replies: 5
    Last Post: 10-13-2006, 09:46 AM
  4. FAQ Check/Lock
    By RoD in forum A Brief History of Cprogramming.com
    Replies: 2
    Last Post: 10-15-2002, 12:21 PM
  5. Queue and Priority Queue
    By Pamela in forum C++ Programming
    Replies: 1
    Last Post: 12-07-2001, 11:09 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21