How can I get a least recently used algorithm to work with multiple threads?

Question

I'm using a memory pool to store image data in a ray tracer and I'm using a least-recently-used algorithm to deal with freeing blocks of memory. This works fine when there is only one thread. When I add more threads, the LRU code breaks. I'm using a linked list to store the history of which blocks have been accessed and this is the part that breaks because as blocks are accessed, I have to modify pointers in the linked list which is causing conflicts between threads. This is the only way I can think to implement memory pool so I'm not really sure how to get this to work.

This is the code I'm using to bring the accessed block to the front of the recently used list where memory read errors are occurring:

    LinkedListNode<int> *curTextureIndex = lastUsedTexture;
    LinkedListNode<int> *prevTextureIndex = NULL;
    //Find the requested texture in the recently used list
    while(curTextureIndex->data != textureBlockIndex)
    {
        prevTextureIndex = curTextureIndex;
        curTextureIndex = curTextureIndex->next;
    }

    if(curTextureIndex != lastUsedTexture)
    {
        //Bring this block to the front of the accessed list
        if(prevTextureIndex != NULL)
            prevTextureIndex->next = curTextureIndex->next;
        curTextureIndex->next = lastUsedTexture;
        lastUsedTexture = curTextureIndex;

        //Set the tail of the list if necessary
        if(lastUsedTexture_tail == curTextureIndex && prevTextureIndex != NULL)
            lastUsedTexture_tail = prevTextureIndex;
    }

Is there a good way to implement this so that it works well with multiple threads?

Answer 1

You can try using critical sections. See the wiki page here: http://en.wikipedia.org/wiki/Critical_section

If you are using ATL or MFC, they have their own classes which wrap around the low level objects which you might find easier to use.

For MFC: CCriticalSection.

For ATL: CComAutoCriticalSection.

You can just put all the linked list manipulation code within a critical section and you won't have one thread trampling the list while the other is working with it.

Also, for LRU cache, I would suggest you use a doubly linked list coupled with a hash table of pointers of the list (with key = textureBlockIndex) to make getting the entry fast, rather than walking the list and comparing, which will make it slow.

Making it fast will ensure that you spend very little time in the critical section, which is a good thing.

See: http://stackoverflow.com/questions/2504178/lru-cache-design/2504317