Как я могу получить наименее недавно использованный алгоритм для работы с несколькими потоками?

Question

Я использую пул памяти для хранения данных изображения в трассировщике лучей, и я использую алгоритм, который использовался реже всего для борьбы с освобождением блоков памяти. Это прекрасно работает, когда есть только один поток. Когда я добавляю больше потоков, код LRU ломается. Я использую связанный список для хранения истории доступа к блокам, и это та часть, которая разбивается, потому что при обращении к блокам мне приходится изменять указатели в связанном списке, что вызывает конфликты между потоками. Это единственный способ реализовать пул памяти, поэтому я не совсем уверен, как заставить это работать.

Это код, который я использую, чтобы перенести доступ к блоку в начало недавно использованного списка, где происходят ошибки чтения из памяти:

    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;
    }

Есть ли хороший способ реализовать это так, чтобы он хорошо работал с несколькими потоками?

Answer 1

Вы можете попробовать использовать критические разделы.См. Вики-страницу здесь: http://en.wikipedia.org/wiki/Critical_section

Если вы используете ATL или MFC, у них есть свои собственные классы, которые обертывают объекты низкого уровня, которые могут оказаться более простыми в использовании.

ДляMFC: CCriticalSection .

Для ATL: CComAutoCriticalSection .

Вы можете просто поместить весь код манипуляции со списком в критическую секцию, и вы выигралиу меня нет одного потока, попирающего список, в то время как другой работает с ним.

Кроме того, для кэша LRU я бы предложил вам использовать двусвязный список в сочетании с хеш-таблицей указателей списка (с ключом= textureBlockIndex) для быстрого получения записи, а не для обхода списка и сравнения, что сделает его медленным.

Если вы сделаете это быстро, вы потратите очень мало времени на критическую секцию, и это хорошо.

См .: Дизайн кэша LRU