在.NET中将项目添加到Dictionary<>对象时,如何避免双重检查锁定?

这是标准 double check locking 问题它在这里的实现方式是不安全的,可能会导致各种问题——如果字典的内部状态搞砸了,那么在第一次检查中可能会出现崩溃。

一个简单的解决方案是将第一张支票也放在锁下。这样做的一个问题是,这会成为一个全局锁,在web环境中,在重载情况下,它会成为一个严重的瓶颈。

如果我们谈论的是.NET环境,那么可以通过借助ASP.NET同步机制来解决这个问题。

这是我在美国的做法 NDjango rendering engine :我为每个渲染线程保留一个全局字典和一个字典。当一个请求到来时,我首先检查本地字典——这个检查不需要同步,如果有东西,我就接受它

如果不是,我在全局字典上同步,检查它是否存在,如果存在,将它添加到我的线程字典并释放锁。如果它不在全局字典中,我会在仍然处于锁定状态时首先将它添加到那里。

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 东西 同一把钥匙。减少它,以便 只有 在那种情况下,封锁会有点困难。

我建议您使用上面的代码,但对其进行分析,看看它是否足够快。如果你真的需要“只有当另一个线程已经在创建相同的东西时才会阻塞”,那么请让我们知道,我们将看看我们能做些什么。。。

编辑:好的,这通常很有趣,所以这里是“仅阻止其他线程请求相同项目”的第一步。

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

呸!

那是 完全地 未经测试,尤其是在创建线程时遇到异常时,它的形状或形式都不可靠。。。但我认为这通常是正确的想法:)

如果您希望避免阻塞不相关的线程,那么就需要进行额外的工作(并且只有当您分析并发现简单代码的性能不可接受时,才需要进行额外的工作)。我建议使用异步创建 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;
}

编辑

这个问题困扰着我,超出了我的预期,所以我根据这个一般模式设计了一个更健壮的解决方案。你可以找到它 here

IMHO,如果这段代码是从多个线程同时调用的,建议检查两次。

(但是:我不确定你是否能安全地打电话给我 ContainsKey 当其他线程被调用时 Add . 因此,可能根本无法避免锁定。)

如果您只是想避免创建但未使用的东西,只需在锁定块中创建它:

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

ContainsKey 操作和吸气剂是自己的 线程安全 (并且在新版本中会保持这种方式),因为这些可能也将被调用 另一个线程已锁定词典并正在执行 Add .

如果正确使用,.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;

我希望在给出这个答案时不要太天真。但是我要做的是,因为创建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];
}

我匆忙修改了你的代码,所以没有做任何测试。

您可能会以牺牲内存为代价购买一点速度效率。如果您创建一个 不变的 数组,列出所有已创建的内容并使用静态变量引用该数组,然后可以检查任何锁之外的内容是否存在,因为不可变数组始终是线程安全的。然后,当添加新的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;
}