Как улучшить многопоточный доступ к Cache (пользовательская реализация)

Question

У меня есть собственная реализация Cache, которая позволяет кэшировать TCacheable<TKey> потомков, используя алгоритм замены кэша LRU (Least Недавно Использованный).

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

// a single instance is created to handle all TCacheable<T> elements
public class Cache()
{
    private TCacheable<T> oldest, newest;

    private object syncQueue = new object();
    private void topQueue(TCacheable<T> el)
    {
        lock (syncQueue)
        if (newest != el)
        {
            if (el.elder != null) el.elder.newer = el.newer;
            if (el.newer != null) el.newer.elder = el.elder;

            if (oldest == el) oldest = el.newer;
            if (oldest == null) oldest = el;

            if (newest != null) newest.newer = el;
            el.newer = null;
            el.elder = newest;
            newest = el;
        }
    }
}

Узким местом в этой функции является оператор lock(), который ограничивает доступ к кешу только одним потоком за раз.

Вопрос : Можно ли избавиться от lock(syncQueue) в этой функции при сохранении целостности очереди?

Answer 1

Хитрость в одновременном использовании LRU-кеша состоит не в том, чтобы снять блокировку - это кроличья нора - но амортизировать необходимость ее приобретения. Очередь может в конечном итоге соответствовать таблице во время чтения, но она должна быть согласована после записи, чтобы правильно выбрать жертву для выселения. Таким образом, вы можете буферизовать переупорядочения и избежать конфликтов блокировки. Я доказал правильность этого подхода в моей реализации Java: http://code.google.com/p/concurrentlinkedhashmap/

Так что, хотя я могу предложить решения для ответа «Да» на ваш вопрос, лучшим ответом будет то, что вам не нужно снимать блокировку, а понимать, когда она действительно необходима.

Answer 2

Самый простой первый шаг - переместить оператор блокировки внутри блока if (newest! = El), так как вам совсем не нужно ждать блокировки, если newest == el.

В сторонуИсходя из этого, вы делаете некоторые условные задания.Действительно ли у вас есть информация профилирования, которая заставляет вас думать, что этот раздел проблематичен с точки зрения производительности?

Если вы действительно уверены, что оптимизация этого класса - лучшее использование вашего времени, вотPDF статьи «Простые, быстрые и практичные неблокирующие и блокирующие алгоритмы параллельной очереди» . Вот отличное сообщение в блоге, которое может быть немного более простым .