c# - 多线程谜语的更好解决方案？

Question

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

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

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

编辑:请不要发布不是 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 的任何机会。