multithreading谜语更好的解决方案？
这是任务：我需要根据文件名锁定。 最多可以有一百万个不同的文件名。 （这用于大规模基于磁盘的缓存）。 我希望内存使用率低，查找时间短，这意味着我需要一个GC锁定字典。 （dict中只能存在使用中的锁）。
回调操作可能需要几分钟才能完成，因此全局锁定是不可接受的。 高吞吐量至关重要。
我已经在下面发布了我当前的解决方案，但我对复杂性感到不满意。
编辑：请不要发布不是100％正确的解决方案。 例如，允许在“获取锁定对象”阶段和“锁定”阶段之间从字典中删除锁定的解决方案是不正确的，无论它是否是“已接受”的设计模式。
有比这更优雅的解决方案吗？
谢谢！
[编辑：我根据RobV的建议更新了我的代码以使用循环与递归]
[编辑：再次更新代码以允许’超时’和更简单的调用模式。 这可能是我使用的最终代码。 仍然与原始post中的基本算法相同。]
[编辑：再次更新代码以处理回调内部的exception，而无需孤立锁定对象]
public delegate void LockCallback(); /// /// 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. /// public class LockProvider { /// /// The only objects in this collection should be for open files. /// protected Dictionary locks = new Dictionary(StringComparer.Ordinal); /// /// Synchronization object for modifications to the 'locks' dictionary /// protected object createLock = new object(); /// /// 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. /// /// /// /// /// 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. (ie, 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 });
根据你对文件的处理方式（你说基于磁盘的缓存，所以我假设读取和写入）然后我建议尝试基于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. (ie, 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的任何可能性。
这个解决方案肯定看起来很脆弱和复杂。 在锁内部进行公共回调是不好的做法。 为什么不让LockProvider返回某种“锁定”对象，以便消费者自己进行锁定。 这将locks字典的locks与执行分开。 它可能看起来像这样：
public class LockProvider { private readonly object globalLock = new object(); private readonly Dictionary locks = new Dictionary(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. } } }
请注意， 在我们输入try语句（using） 之前调用Monitor.Enter ，这意味着在某些主机环境（例如ASP.NET和SQL Server）中，当发生异步exception时，我们可能永远不会释放锁。 ASP.NET和SQL Server等主机在发生超时时会主动杀死线程。 使用在Monitor.Enter外部的Enter重写这一点。在try输入虽然有点棘手。
我希望这有帮助。
你能不能简单地使用一个名为Mutex的名字来自你的文件名？
虽然不是轻量级同步原语，但它比管理自己的同步字典更简单。
但是，如果你真的想这样做，我认为以下实现看起来更简单。 如果您使用的是.NET 3.5或更低版本，则需要同步字典 – .NET 4 ConcurrentDictionary或您自己的实现。
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); } } }
在.NET中似乎没有一种优雅的方法可以做到这一点，尽管我已经通过@ RobV的循环建议改进了算法。 这是我确定的最终解决方案。
它不受’孤儿参考’的影响，似乎是典型的标准模式，随后是@Steven的回答。
using System; using System.Collections.Generic; using System.Text; using System.Threading; namespace ImageResizer.Plugins.DiskCache { public delegate void LockCallback(); /// /// 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. /// public class LockProvider { /// /// The only objects in this collection should be for open files. /// protected Dictionary locks = new Dictionary(StringComparer.Ordinal); /// /// Synchronization object for modifications to the 'locks' dictionary /// protected object createLock = new object(); /// /// 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. /// /// /// /// /// 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. (ie, 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 });