Как избежать блокировки двойной проверки при добавлении, что объекты к Словарю <> возражают в.NET?

. Если вы хотите избежать блокировки несвязанных потоков, то потребуется дополнительная работа (и она может потребоваться только в том случае, если вы ' ve профилировал и обнаружил, что производительность неприемлема с более простым кодом). Я бы рекомендовал использовать облегченный класс-оболочку, который асинхронно создает Thingey и использовать его в вашем словаре.

Dictionary<string, ThingeyWrapper> thingeys = new Dictionary<string, ThingeyWrapper>();

private class ThingeyWrapper
{
    public Thingey Thing { get; private set; }

    private object creationLock;
    private Request request;

    public ThingeyWrapper(Request request)
    {
        creationFlag = new object();
        this.request = request;
    }

    public void WaitForCreation()
    {
        object flag = creationFlag;

        if(flag != null)
        {
            lock(flag)
            {
                if(request != null) Thing = new Thingey(request);

                creationFlag = null;

                request = null;
            }
        }
    }
}

public Thingey GetThingey(Request request)
{
    string thingeyName = request.ThingeyName;

    ThingeyWrapper output;

    lock (this.Thingeys)
    {
        if(!this.Thingeys.TryGetValue(thingeyName, out output))
        {
            output = new ThingeyWrapper(request);

            this.Thingeys.Add(thingeyName, output);
        }
    }

    output.WaitForCreation();

    return output.Thing;
}

Хотя вы все еще блокируете все вызовы, процесс создания намного проще.

Править

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

Что ж, с моей точки зрения, более простой код лучше, поэтому я бы использовал только одну блокировку:

private readonly object thingeysLock = new object();
private readonly Dictionary<string, Thingey> thingeys;

public Thingey GetThingey(Request request)
{
    string key = request.ThingeyName;
    lock (thingeysLock)
    {
        Thingey ret;
        if (!thingeys.TryGetValue(key, out ret))
        {
            ret = new Thingey(request);
            thingeys[key] = ret;
        }
        return ret;
    }
}

Блокировки действительно дешевы, когда они не оспариваются. Обратной стороной является то, что иногда вы будете блокировать всех на все время создания нового Thingey . Очевидно, чтобы избежать создания лишних элементов, вам придется как минимум заблокировать, пока несколько потоков создают Thingey для одного и того же ключа. Уменьшить его так, чтобы они только блокировали в этой ситуации, несколько сложнее.

Я бы посоветовал вам использовать приведенный выше код, но профилировать его, чтобы увидеть, достаточно ли он быстр. Если вам действительно нужно «блокировать только тогда, когда другой поток уже создает то же самое», дайте нам знать, и мы посмотрим, что мы можем сделать ...

EDIT: You ' Я прокомментировал ответ Адама, что вы «не хотите блокировать, пока создается новый Thingey» - вы же понимаете, что от этого никуда не деться, если будет конкуренция за тот же ключ, верно? Если поток 1 начинает создавать Thingey, тогда поток 2 запрашивает тот же ключ, ваши альтернативы для потока 2 либо ждут, либо создают другой экземпляр.

РЕДАКТИРОВАТЬ: Хорошо, это в целом интересно, поэтому вот первый проход в " блокировать только другие потоки, запрашивающие тот же элемент ».

private readonly object dictionaryLock = new object();
private readonly object creationLocksLock = new object();
private readonly Dictionary<string, Thingey> thingeys;
private readonly Dictionary<string, object> creationLocks;

public Thingey GetThingey(Request request)
{
    string key = request.ThingeyName;
    Thingey ret;
    bool entryExists;
    lock (dictionaryLock)
    {
       entryExists = thingeys.TryGetValue(key, out ret);
       // Atomically mark the dictionary to say we're creating this item,
       // and also set an entry for others to lock on
       if (!entryExists)
       {
           thingeys[key] = null;
           lock (creationLocksLock)
           {
               creationLocks[key] = new object();          
           }
       }
    }
    // If we found something, great!
    if (ret != null)
    {
        return ret;
    }
    // Otherwise, see if we're going to create it or whether we need to wait.
    if (entryExists)
    {
        object creationLock;
        lock (creationLocksLock)
        {
            creationLocks.TryGetValue(key, out creationLock);
        }
        // If creationLock is null, it means the creating thread has finished
        // creating it and removed the creation lock, so we don't need to wait.
        if (creationLock != null)
        {
            lock (creationLock)
            {
                Monitor.Wait(creationLock);
            }
        }
        // We *know* it's in the dictionary now - so just return it.
        lock (dictionaryLock)
        {
           return thingeys[key];
        }
    }
    else // We said we'd create it
    {
        Thingey thingey = new Thingey(request);
        // Put it in the dictionary
        lock (dictionaryLock)
        {
           thingeys[key] = thingey;
        }
        // Tell anyone waiting that they can look now
        lock (creationLocksLock)
        {
            Monitor.PulseAll(creationLocks[key]);
            creationLocks.Remove(key);
        }
        return thingey;
    }
}

Уф!

Это полностью непроверено, и, в частности, это никоим образом не устойчиво к исключениям в поток создания ... но я думаю, что это в целом правильная идея :)

право? Если поток 1 начинает создавать Thingey, тогда поток 2 запрашивает тот же ключ, ваши альтернативы для потока 2 либо ждут, либо создают другой экземпляр.

РЕДАКТИРОВАТЬ: Хорошо, это в целом интересно, поэтому вот первый проход в " блокировать только другие потоки, запрашивающие тот же элемент ".

private readonly object dictionaryLock = new object();
private readonly object creationLocksLock = new object();
private readonly Dictionary<string, Thingey> thingeys;
private readonly Dictionary<string, object> creationLocks;

public Thingey GetThingey(Request request)
{
    string key = request.ThingeyName;
    Thingey ret;
    bool entryExists;
    lock (dictionaryLock)
    {
       entryExists = thingeys.TryGetValue(key, out ret);
       // Atomically mark the dictionary to say we're creating this item,
       // and also set an entry for others to lock on
       if (!entryExists)
       {
           thingeys[key] = null;
           lock (creationLocksLock)
           {
               creationLocks[key] = new object();          
           }
       }
    }
    // If we found something, great!
    if (ret != null)
    {
        return ret;
    }
    // Otherwise, see if we're going to create it or whether we need to wait.
    if (entryExists)
    {
        object creationLock;
        lock (creationLocksLock)
        {
            creationLocks.TryGetValue(key, out creationLock);
        }
        // If creationLock is null, it means the creating thread has finished
        // creating it and removed the creation lock, so we don't need to wait.
        if (creationLock != null)
        {
            lock (creationLock)
            {
                Monitor.Wait(creationLock);
            }
        }
        // We *know* it's in the dictionary now - so just return it.
        lock (dictionaryLock)
        {
           return thingeys[key];
        }
    }
    else // We said we'd create it
    {
        Thingey thingey = new Thingey(request);
        // Put it in the dictionary
        lock (dictionaryLock)
        {
           thingeys[key] = thingey;
        }
        // Tell anyone waiting that they can look now
        lock (creationLocksLock)
        {
            Monitor.PulseAll(creationLocks[key]);
            creationLocks.Remove(key);
        }
        return thingey;
    }
}

Уф!

Это полностью непроверено, и, в частности, это никоим образом, форма или форма не является устойчивой перед лицом исключений в поток создания ... но я думаю, что это в целом правильная идея :)

право? Если поток 1 начинает создавать Thingey, тогда поток 2 запрашивает тот же ключ, ваши альтернативы для потока 2 либо ждут, либо создают другой экземпляр.

РЕДАКТИРОВАТЬ: Хорошо, это в целом интересно, поэтому вот первый проход в " блокировать только другие потоки, запрашивающие тот же элемент ».

private readonly object dictionaryLock = new object();
private readonly object creationLocksLock = new object();
private readonly Dictionary<string, Thingey> thingeys;
private readonly Dictionary<string, object> creationLocks;

public Thingey GetThingey(Request request)
{
    string key = request.ThingeyName;
    Thingey ret;
    bool entryExists;
    lock (dictionaryLock)
    {
       entryExists = thingeys.TryGetValue(key, out ret);
       // Atomically mark the dictionary to say we're creating this item,
       // and also set an entry for others to lock on
       if (!entryExists)
       {
           thingeys[key] = null;
           lock (creationLocksLock)
           {
               creationLocks[key] = new object();          
           }
       }
    }
    // If we found something, great!
    if (ret != null)
    {
        return ret;
    }
    // Otherwise, see if we're going to create it or whether we need to wait.
    if (entryExists)
    {
        object creationLock;
        lock (creationLocksLock)
        {
            creationLocks.TryGetValue(key, out creationLock);
        }
        // If creationLock is null, it means the creating thread has finished
        // creating it and removed the creation lock, so we don't need to wait.
        if (creationLock != null)
        {
            lock (creationLock)
            {
                Monitor.Wait(creationLock);
            }
        }
        // We *know* it's in the dictionary now - so just return it.
        lock (dictionaryLock)
        {
           return thingeys[key];
        }
    }
    else // We said we'd create it
    {
        Thingey thingey = new Thingey(request);
        // Put it in the dictionary
        lock (dictionaryLock)
        {
           thingeys[key] = thingey;
        }
        // Tell anyone waiting that they can look now
        lock (creationLocksLock)
        {
            Monitor.PulseAll(creationLocks[key]);
            creationLocks.Remove(key);
        }
        return thingey;
    }
}

Уф!

Это полностью непроверено, и, в частности, это никоим образом не устойчиво к исключениям в поток создания ... но я думаю, что это в целом правильная идея :)

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

private Dictionary<string, Thingey> Thingeys;
public Thingey GetThingey(Request request)
{
    string thingeyName = request.ThingeyName;
    if (!this.Thingeys.ContainsKey(thingeyName))
    {
        lock (this.Thingeys)
        {
            this.Thingeys.Add(thingeyName, null);
            if (!this.Thingeys.ContainsKey(thingeyName))
            {
                // create a new thingey on 1st reference
                Thingey newThingey = new Thingey(request);
                Thingeys[thingeyName] = newThingey;
            }
            // else - oops someone else beat us to it
            // but it doesn't mather anymore since we only created one Thingey
        }
    }

    return this.Thingeys[thingeyName];
}

Я в спешке изменил ваш код, поэтому тестирование не проводилось.
В любом случае, надеюсь, моя идея не такая наивная. : D

Это стандартная проблема с двойной проверкой блокировки . То, как это реализовано здесь, небезопасно и может вызвать различные проблемы - потенциально вплоть до сбоя при первой проверке, если внутреннее состояние словаря достаточно плохо испорчено.

Это небезопасно, потому что вы проверяете его без синхронизации, и если вам не повезло, вы можете попасть в него, пока какой-то другой поток находится в процессе обновления внутреннего состояния словаря.

Простое решение - поместить первый также проверьте под замком. Проблема в том, что это становится глобальной блокировкой, и в веб-среде при большой нагрузке это может стать серьезным узким местом.

Если мы говорим о среде .NET, есть способы обойти эту проблему, используя механизм синхронизации ASP.NET.

Вот как я это сделал в движке рендеринга NDjango : у меня есть один глобальный словарь и один словарь для каждого потока рендеринга. Когда приходит запрос, я сначала проверяю локальный словарь - эту проверку не нужно синхронизировать, и если что-то там есть, я просто беру ее

Если это не так, я синхронизирую по глобальному словарю, проверяю, есть ли он и есть ли добавляет его в мой словарь потоков и снимает блокировку. Если его нет в глобальном словаре, я сначала добавляю его туда, пока еще заблокирован.

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

Если это не так, я синхронизирую по глобальному словарю, проверяю, есть ли он и есть ли добавляет его в мой словарь потоков и снимает блокировку. Если его нет в глобальном словаре, я сначала добавляю его туда, пока еще заблокирован.

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

Если это не так, я синхронизирую по глобальному словарю, проверяю, есть ли он и есть ли добавляет его в мой словарь потоков и снимает блокировку. Если его нет в глобальном словаре, я сначала добавляю его туда, пока еще заблокирован.

NET-блокировки довольно эффективны при правильном использовании, и я считаю, что в этой ситуации вам лучше сделать это:

bool exists;
lock (thingeys) {
    exists = thingeys.TryGetValue(thingeyName, out thingey);
}
if (!exists) {
    thingey = new Thingey();
}
lock (thingeys) {
    if (!thingeys.ContainsKey(thingeyName)) {
        thingeys.Add(thingeyName, thingey);
    }
}
return thingey;

IMHO, если этот фрагмент кода вызывается из многих потоков одновременно, рекомендуется проверить его дважды.

(Но: я не уверен, что вы можете безопасно позвонить ] ContainsKey , в то время как какой-то другой поток вызывает Add . Так что, возможно, вообще невозможно избежать блокировки.)

Если вы просто хотите избежать создания Thingy, но не использования, просто создайте его в блокирующем блоке:

private Dictionary<string, Thingey> Thingeys;
public Thingey GetThingey(Request request)
{
    string thingeyName = request.ThingeyName;
    if (!this.Thingeys.ContainsKey(thingeyName))
    {
        lock (this.Thingeys)
        {
            // only one can create the same Thingy
            Thingey newThingey = new Thingey(request);
            if (!this.Thingeys.ContainsKey(thingeyName))
            {
                this.Thingeys.Add(thingeyName, newThingey);
            }

        }
    }

    return this. Thingeys[thingeyName];
}

Я думаю, вам нужно использовать MDC.Set для установки дополнительных значений контекста. Посмотрите Совет № 4 в этом блоге .

Если вы создаете неизменяемый массив, в котором перечислены все созданные Thingys и ссылаетесь на массив с помощью статической переменной, то вы можете проверить существование Thingy вне любой блокировки, поскольку неизменяемые массивы всегда потокобезопасны. Затем при добавлении нового Thingy вы можете создать новый массив с дополнительным Thingy и заменить его (в статической переменной) за одну (атомарную) операцию установки. Некоторые новые Thingys могут быть пропущены из-за условий гонки, но программа не должна давать сбой. Это просто означает, что в редких случаях будут созданы дополнительные дубликаты Thingy.

Это не заменит необходимости проверки дубликатов при создании нового Thingy, и он будет использовать много ресурсов памяти, но не потребует блокировки быть взятым или удерживаемым при создании Вещи.

Я думаю о чем-то в этом роде, вроде:

private Dictionary<string, Thingey> Thingeys;
// An immutable list of (most of) the thingeys that have been created.
private string[] existingThingeys;

public Thingey GetThingey(Request request)
{
    string thingeyName = request.ThingeyName;
    // Reference the same list throughout the method, just in case another
    // thread replaces the global reference between operations.
    string[] localThingyList = existingThingeys;
    // Check to see if we already made this Thingey. (This might miss some, 
    // but it doesn't matter.
    // This operation on an immutable array is thread-safe.
    if (localThingyList.Contains(thingeyName))
    {
        // But referencing the dictionary is not thread-safe.
        lock (this.Thingeys)
        {
            if (this.Thingeys.ContainsKey(thingeyName))
                return this.Thingeys[thingeyName];
        }
    }
    Thingey newThingey = new Thingey(request);
    Thiney ret;
    // We haven't locked anything at this point, but we have created a new 
    // Thingey that we probably needed.
    lock (this.Thingeys)
    {
        // If it turns out that the Thingey was already there, then 
        // return the old one.
        if (!Thingeys.TryGetValue(thingeyName, out ret))
        {
            // Otherwise, add the new one.
            Thingeys.Add(thingeyName, newThingey);
            ret = newThingey;
        }
    }
    // Update our existingThingeys array atomically.
    string[] newThingyList = new string[localThingyList.Length + 1];
    Array.Copy(localThingyList, newThingey, localThingyList.Length);
    newThingey[localThingyList.Length] = thingeyName;
    existingThingeys = newThingyList; // Voila!
    return ret;
}