更好地解决多线程之谜？

Question

任务如下：我需要根据文件名锁定。最多可以有一百万个不同的文件名。 （这用于大规模基于磁盘的缓存）。 我想要低内存使用率和低查找时间，这意味着我需要一个 GC 锁定字典。 （字典中只能存在正在使用的锁）。

回调操作可能需要几分钟才能完成，因此全局锁定是不可接受的。高吞吐量至关重要。

我在下面发布了我当前的解决方案，但我对其复杂性不满意。

编辑：请不要发布不是 100% 正确的解决方案。例如，允许在“获取锁对象”阶段和“锁定”阶段之间从字典中删除锁的解决方案是不正确的，无论它是否是“接受的”设计模式。

还有比这更优雅的解决方案吗？

谢谢！

[编辑：我根据 RobV 的建议更新了代码以使用循环与递归]

[编辑：再次更新代码以允许“超时”和更简单的调用模式。这可能是我使用的最终代码。仍然与原始帖子中的基本算法相同。]

[编辑：再次更新代码以处理回调内的异常，而无需孤立锁对象]

public delegate void LockCallback();
/// <summary>
/// Provides locking based on a string key. 
/// Locks are local to the LockProvider instance.
/// The class handles disposing of unused locks. Generally used for 
/// coordinating writes to files (of which there can be millions). 
/// Only keeps key/lock pairs in memory which are in use.
/// Thread-safe.
/// </summary>
public class LockProvider {

    /// <summary>
    /// The only objects in this collection should be for open files. 
    /// </summary>
    protected Dictionary<String, Object> locks = 
                    new Dictionary<string, object>(StringComparer.Ordinal);
    /// <summary>
    /// Synchronization object for modifications to the 'locks' dictionary
    /// </summary>
    protected object createLock = new object();
    /// <summary>
    /// Attempts to execute the 'success' callback inside a lock based on 'key'.  If successful, returns true.
    /// If the lock cannot be acquired within 'timoutMs', returns false
    /// In a worst-case scenario, it could take up to twice as long as 'timeoutMs' to return false.
    /// </summary>
    /// <param name="key"></param>
    /// <param name="success"></param>
    /// <param name="failure"></param>
    /// <param name="timeoutMs"></param>
    public bool TryExecute(string key, int timeoutMs, LockCallback success){
        //Record when we started. We don't want an infinite loop.
        DateTime startedAt = DateTime.UtcNow;

        // Tracks whether the lock acquired is still correct
        bool validLock = true; 
        // The lock corresponding to 'key'
        object itemLock = null;

        try {
            //We have to loop until we get a valid lock and it stays valid until we lock it.
            do {
                // 1) Creation/aquire phase
                lock (createLock) {
                    // We have to lock on dictionary writes, since otherwise 
                    // two locks for the same file could be created and assigned
                    // at the same time. (i.e, between TryGetValue and the assignment)
                    if (!locks.TryGetValue(key, out itemLock))
                        locks[key] = itemLock = new Object(); //make a new lock!

                }
                // Loophole (part 1):
                // Right here - this is where another thread (executing part 2) could remove 'itemLock'
                // from the dictionary, and potentially, yet another thread could 
                // insert a new value for 'itemLock' into the dictionary... etc, etc..

                // 2) Execute phase
                if (System.Threading.Monitor.TryEnter(itemLock, timeoutMs)) {
                    try {
                        // May take minutes to acquire this lock. 

                        // Trying to detect an occurence of loophole above
                        // Check that itemLock still exists and matches the dictionary
                        lock (createLock) {
                            object newLock = null;
                            validLock = locks.TryGetValue(key, out newLock);
                            validLock = validLock && newLock == itemLock;
                        }
                        // Only run the callback if the lock is valid
                        if (validLock) {
                            success(); // Extremely long-running callback, perhaps throwing exceptions
                            return true;
                        }

                    } finally {
                        System.Threading.Monitor.Exit(itemLock);//release lock
                    }
                } else {
                    validLock = false; //So the finally clause doesn't try to clean up the lock, someone else will do that.
                    return false; //Someone else had the lock, they can clean it up.
                }

                //Are we out of time, still having an invalid lock?
                if (!validLock && Math.Abs(DateTime.UtcNow.Subtract(startedAt).TotalMilliseconds) > timeoutMs) {
                    //We failed to get a valid lock in time. 
                    return false;
                }


                // If we had an invalid lock, we have to try everything over again.
            } while (!validLock);
        } finally {
            if (validLock) {
                // Loophole (part 2). When loophole part 1 and 2 cross paths,
                // An lock object may be removed before being used, and be orphaned

                // 3) Cleanup phase - Attempt cleanup of lock objects so we don't 
                //   have a *very* large and slow dictionary.
                lock (createLock) {
                    //  TryEnter() fails instead of waiting. 
                    //  A normal lock would cause a deadlock with phase 2. 
                    //  Specifying a timeout would add great and pointless overhead.
                    //  Whoever has the lock will clean it up also.
                    if (System.Threading.Monitor.TryEnter(itemLock)) {
                        try {
                            // It succeeds, so no-one else is working on it 
                            // (but may be preparing to, see loophole)
                            // Only remove the lock object if it 
                            // still exists in the dictionary as-is
                            object existingLock = null;
                            if (locks.TryGetValue(key, out existingLock)
                                && existingLock == itemLock)
                                locks.Remove(key);
                        } finally {
                            // Remove the lock
                            System.Threading.Monitor.Exit(itemLock);
                        }
                    }
                }
            }
        }
        // Ideally the only objects in 'locks' will be open operations now.
        return true;
    }
}

使用示例

LockProvider p = new LockProvider();
bool success = p.TryExecute("filename",1000,delegate(){
  //This code executes within the lock
});

Answer 1

根据您对文件所做的操作（您说基于磁盘的缓存，所以我假设读取和写入），然后我建议尝试基于 ReaderWriterLock，如果您可以升级到 .Net 3.5，请尝试 ReaderWriterLockSlim 相反，因为它的性能更好。

作为减少示例中潜在无限递归情况的一般步骤，请将代码的第一位更改为以下内容：

do 
{
    // 1) Creation/aquire phase
    lock (createLock){
        // We have to lock on dictionary writes, since otherwise 
        // two locks for the same file could be created and assigned
        // at the same time. (i.e, between TryGetValue and the assignment)
        if (!locks.TryGetValue(key, out itemLock)) 
            locks[key] = itemLock = new Object(); //make a new lock!

    }
    // Loophole (part 1):
    // Right here - this is where another thread could remove 'itemLock'
    // from the dictionary, and potentially, yet another thread could 
    // insert a new value for 'itemLock' into the dictionary... etc, etc..

    // 2) Execute phase
    lock(itemLock){ 
        // May take minutes to acquire this lock. 
        // Real version would specify a timeout and a failure callback.

        // Trying to detect an occurence of loophole above
        // Check that itemLock still exists and matches the dictionary
        lock(createLock){
            object newLock = null;
            validLock = locks.TryGetValue(key, out newLock);
            validLock = validLock && newLock == itemLock;
        }
        // Only run the callback if the lock is valid
        if (validLock) callback(); // Extremely long-running callback. 
    }
    // If we had an invalid lock, we have to try everything over again.
} while (!validLock);

这将用循环替换递归，从而避免无限递归导致 StackOverflow 的任何机会。

Answer 2

该解决方案看起来确实脆弱且复杂。在锁内使用公共回调是不好的做法。为什么不让 LockProvider 返回某种“锁定”对象，以便消费者自己进行锁定。这将 locks 字典的锁定与执行分开。它可能看起来像这样：

public class LockProvider
{
    private readonly object globalLock = new object();

    private readonly Dictionary<String, Locker> locks =
        new Dictionary<string, Locker>(StringComparer.Ordinal);

    public IDisposable Enter(string key)
    {
        Locker locker;

        lock (this.globalLock)
        {
            if (!this.locks.TryGetValue(key, out locker))
            {
                this.locks[key] = locker = new Locker(this, key);
            }

            // Increase wait count ínside the global lock
            locker.WaitCount++;
        }

        // Call Enter and decrease wait count óutside the 
        // global lock (to prevent deadlocks).
        locker.Enter();

        // Only one thread will be here at a time for a given locker.
        locker.WaitCount--;

        return locker;
    }

    private sealed class Locker : IDisposable
    {
        private readonly LockProvider provider;
        private readonly string key;
        private object keyLock = new object();

        public int WaitCount;

        public Locker(LockProvider provider, string key)
        {
            this.provider = provider;
            this.key = key;
        }

        public void Enter()
        {
            Monitor.Enter(this.keyLock);
        }

        public void Dispose()
        {
            if (this.keyLock != null)
            {
                this.Exit();
                this.keyLock = null;
            }
        }

        private void Exit()
        {
            lock (this.provider.globalLock)
            {
                try
                {
                    // Remove the key before releasing the lock, but
                    // only when no threads are waiting (because they
                    // will have a reference to this locker).
                    if (this.WaitCount == 0)
                    {
                        this.provider.locks.Remove(this.key);
                    }
                }
                finally
                {
                    // Release the keyLock inside the globalLock.
                    Monitor.Exit(this.keyLock);
                }
            }
        }
    }
}

LockProvider 可以按如下方式使用：

public class Consumer
{
    private LockProvider provider;

    public void DoStufOnFile(string fileName)
    {
        using (this.provider.Enter(fileName))
        {
            // Long running operation on file here.
        }
    }
}

请注意，Monitor.Enter 是在我们输入 之前调用的。 try 语句（using），这意味着在某些宿主环境（例如 ASP.NET 和 SQL Server）中，当异步异常发生时，我们有可能永远不会释放锁。发生超时时，ASP.NET 和 SQL Server 等主机会主动终止线程。不过，在 try 内的 Monitor.Enter 外部使用 Enter 重写此代码有点棘手。

我希望这有帮助。

Answer 3

难道你不能简单地使用一个命名的互斥体，其名称源自你的文件名吗？

虽然不是轻量级同步原语，但它比管理您自己的同步字典更简单。

但是，如果您确实想这样做，我认为以下实现看起来更简单。您需要一个同步字典 - .NET 4 ConcurrentDictionary 或您自己的实现（如果您使用的是 .NET 3.5 或更低版本）。

try
{
    object myLock = new object();
    lock(myLock)
    {
        object otherLock = null;
        while(otherLock != myLock)
        {
           otherLock = lockDictionary.GetOrAdd(key, myLock);
           if (otherLock != myLock)
           {
               // Another thread has a lock in the dictionary
               if (Monitor.TryEnter(otherLock, timeoutMs))
               {
                   // Another thread still has a lock after a timeout
                   failure();
                   return;
               }
               else
               {
                   Monitor.Exit(otherLock);
               }
           }
        }
        // We've successfully added myLock to the dictionary
        try
        {
           // Do our stuff
           success();
        }
        finally
        {
            lockDictionary.Remove(key);
        }
    }
}

Answer 4

尽管由于 @RobV 的循环建议我改进了算法，但在 .NET 中似乎没有一种优雅的方法来做到这一点。这是我最终确定的解决方案。

它不受“孤立引用”错误的影响，该错误似乎是 @Steven 答案所遵循的标准模式的典型特征。

using System;
using System.Collections.Generic;
using System.Text;
using System.Threading;

namespace ImageResizer.Plugins.DiskCache {

public delegate void LockCallback();
/// <summary>
/// Provides locking based on a string key. 
/// Locks are local to the LockProvider instance.
/// The class handles disposing of unused locks. Generally used for 
/// coordinating writes to files (of which there can be millions). 
/// Only keeps key/lock pairs in memory which are in use.
/// Thread-safe.
/// </summary>
public class LockProvider {

    /// <summary>
    /// The only objects in this collection should be for open files. 
    /// </summary>
    protected Dictionary<String, Object> locks = 
                    new Dictionary<string, object>(StringComparer.Ordinal);
    /// <summary>
    /// Synchronization object for modifications to the 'locks' dictionary
    /// </summary>
    protected object createLock = new object();
    /// <summary>
    /// Attempts to execute the 'success' callback inside a lock based on 'key'.  If successful, returns true.
    /// If the lock cannot be acquired within 'timoutMs', returns false
    /// In a worst-case scenario, it could take up to twice as long as 'timeoutMs' to return false.
    /// </summary>
    /// <param name="key"></param>
    /// <param name="success"></param>
    /// <param name="failure"></param>
    /// <param name="timeoutMs"></param>
    public bool TryExecute(string key, int timeoutMs, LockCallback success){
        //Record when we started. We don't want an infinite loop.
        DateTime startedAt = DateTime.UtcNow;

        // Tracks whether the lock acquired is still correct
        bool validLock = true; 
        // The lock corresponding to 'key'
        object itemLock = null;

        try {
            //We have to loop until we get a valid lock and it stays valid until we lock it.
            do {
                // 1) Creation/aquire phase
                lock (createLock) {
                    // We have to lock on dictionary writes, since otherwise 
                    // two locks for the same file could be created and assigned
                    // at the same time. (i.e, between TryGetValue and the assignment)
                    if (!locks.TryGetValue(key, out itemLock))
                        locks[key] = itemLock = new Object(); //make a new lock!

                }
                // Loophole (part 1):
                // Right here - this is where another thread (executing part 2) could remove 'itemLock'
                // from the dictionary, and potentially, yet another thread could 
                // insert a new value for 'itemLock' into the dictionary... etc, etc..

                // 2) Execute phase
                if (System.Threading.Monitor.TryEnter(itemLock, timeoutMs)) {
                    try {
                        // May take minutes to acquire this lock. 

                        // Trying to detect an occurence of loophole above
                        // Check that itemLock still exists and matches the dictionary
                        lock (createLock) {
                            object newLock = null;
                            validLock = locks.TryGetValue(key, out newLock);
                            validLock = validLock && newLock == itemLock;
                        }
                        // Only run the callback if the lock is valid
                        if (validLock) {
                            success(); // Extremely long-running callback, perhaps throwing exceptions
                            return true;
                        }

                    } finally {
                        System.Threading.Monitor.Exit(itemLock);//release lock
                    }
                } else {
                    validLock = false; //So the finally clause doesn't try to clean up the lock, someone else will do that.
                    return false; //Someone else had the lock, they can clean it up.
                }

                //Are we out of time, still having an invalid lock?
                if (!validLock && Math.Abs(DateTime.UtcNow.Subtract(startedAt).TotalMilliseconds) > timeoutMs) {
                    //We failed to get a valid lock in time. 
                    return false;
                }


                // If we had an invalid lock, we have to try everything over again.
            } while (!validLock);
        } finally {
            if (validLock) {
                // Loophole (part 2). When loophole part 1 and 2 cross paths,
                // An lock object may be removed before being used, and be orphaned

                // 3) Cleanup phase - Attempt cleanup of lock objects so we don't 
                //   have a *very* large and slow dictionary.
                lock (createLock) {
                    //  TryEnter() fails instead of waiting. 
                    //  A normal lock would cause a deadlock with phase 2. 
                    //  Specifying a timeout would add great and pointless overhead.
                    //  Whoever has the lock will clean it up also.
                    if (System.Threading.Monitor.TryEnter(itemLock)) {
                        try {
                            // It succeeds, so no-one else is working on it 
                            // (but may be preparing to, see loophole)
                            // Only remove the lock object if it 
                            // still exists in the dictionary as-is
                            object existingLock = null;
                            if (locks.TryGetValue(key, out existingLock)
                                && existingLock == itemLock)
                                locks.Remove(key);
                        } finally {
                            // Remove the lock
                            System.Threading.Monitor.Exit(itemLock);
                        }
                    }
                }
            }
        }
        // Ideally the only objects in 'locks' will be open operations now.
        return true;
    }
}
}

使用这段代码非常简单：

LockProvider p = new LockProvider();
bool success = p.TryExecute("filename",1000,delegate(){
  //This code executes within the lock
});