较好地解决了多线程谜？ [英] Better solution to multithreading riddle?

问题描述

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

回调动作可能需要几分钟来完成，因此，全局锁是不可接受的。高通量是至关重要的。

我已经张贴下面我目前的解决办法，但我不满意的复杂性。

编辑：请不要发布任何不是100％正确的解决方案。例如，可以从获取锁对象'相和锁定相之间的字典移除允许锁的溶液是不正确的，无论它是否是一个接受的设计图案或​​没有。

有没有更好的解决方案比这个？

谢谢！

 公共委托无效LockCallback（）; 
 ///<总结> 
 ///提供了基于字符串键锁定。 
 ///锁是本地的LockProvider实例。 
 ///类处理未使用的锁处置。一般用于
 ///协调写入文件（其中可能有上百万）。 
 ///仅保留在存储器键/锁对这是在使用中。 
 ///线程安全的。 
 ///< /总结> 
公共类LockProvider {
 
 ///<总结> 
 ///此集合中的唯一对象应该是打开的文件。 
 ///< /总结> 
保护字典<弦乐，对象>锁= 
新字典<字符串对象>（StringComparer.Ordinal）; 
 ///<总结> 
 ///同步对象进行修改的'锁'字典
 ///< /总结> 
保护对象createLock =新的对象（）; 
 ///<总结> 
 ///试图执行基于钥匙锁里面的'成功'回调。如果成功，返回true。 
 ///如果锁不能'timoutMs'内获得，返回false 
 ///在最坏的情况下，它可以以两倍长占用为timeoutMs'返回假。 
 ///< /总结> 
 ///< PARAM NAME =键>< /参数> 
 ///< PARAM NAME =成功>< /参数> 
 ///< PARAM NAME =失败>< /参数> 
 ///< PARAM NAME =timeoutMs>< /参数> 
公共BOOL TryExecute（字符串键，诠释timeoutMs，LockCallback成功）{
 //记录，当我们开始。我们不希望一个无限循环。 
的DateTime startedAt = DateTime.UtcNow; 
 
 //跟踪获取的锁是否仍然是正确的
布尔validLock = TRUE; 
 //相当于'键'
对象的锁itemLock = NULL; 
 
尝试{
 //我们必须循环直到我们得到了一个有效的锁，直到我们锁定它，它保持有效。 
做{
 // 1）创建/ AQUIRE阶段
锁（createLock）{
 //我们必须锁定字典写，否则
 // 2对同一文件的锁可以创建并同时分配
 //。 （即，TryGetValue和分配之间），
如果
锁[关键] = itemLock =新的对象（）（locks.TryGetValue（键，出itemLock）！）; //创建一个新的锁！ 
 
} 
 //漏洞（第1部分）：
 //就在这里 - 这是另一个线程（执行第2部分）可以删除itemLock'
 / /从字典中，并有可能，另一个线程可以
 //插入了itemLock到字典...等等，等等。
 
 // 2）执行新的价值相
如果（System.Threading.Monitor.TryEnter（itemLock，timeoutMs））{
尝试{
 //需要一段时间，获取这个锁。 
 
 //试图检测漏洞高于
的occurence //检查itemLock依然存在，字典
锁（createLock）{
对象newLock = NULL匹配; 
 validLock = locks.TryGetValue（键，出newLock）; 
 validLock = validLock&放大器;&安培; newLock == itemLock; 
} 
 //只有在锁定是有效的
如果（validLock）{
成功（）运行回调; //极长时间运行的回调，或许抛出异常
返回真; 
} 
 
} {最后
 System.Threading.Monitor.Exit（itemLock）; //释放锁
} 
}其他{
 validLock = FALSE; //所以最后子句不尝试清理锁，别人会做到这一点。 
返回FALSE; //别人了锁，他们可以清理。 
} 
 
 //我们是出来的时候，仍然有一个无效的锁？ 
如果（validLock&安培;！&安培; Math.Abs​​（DateTime.UtcNow.Subtract（startedAt）.TotalMilliseconds）GT; timeoutMs）{
 //我们没有得到及时有效的锁。 
返回FALSE; 
} 
 
 
 //如果我们有一个无效的锁，我们必须尝试重新一切。 
}，而（validLock！）; 
} {最后
如果（validLock）{
 //漏洞（部分2）。当漏洞部分1和2交叉路径，
 //一个锁定对象可以在使用前被删除，被孤立
 
 // 3）清除阶段 - 锁的尝试清理对象，因此我们不要
 //有一个非常* *大和缓慢的字典。 
锁（createLock）{
 // TryEnter（）失败，而不是等待。 
 //一个普通的锁会导致与第2阶段
 //指定超时将增加巨大的和毫无意义的开销死锁。 
 //谁拥有锁将清理也。如果
（System.Threading.Monitor.TryEnter（itemLock））{
尝试{
 //成功，所以没有其他人正在这
 //（但可能准备，看到漏洞）
 //只有解除锁定对象，如果它
 //在字典中仍然存在原样
对象existingLock = NULL; 
如果（locks.TryGetValue（键，出existingLock）
和;&安培; existingLock == itemLock）
 locks.Remove（键）; 
} {最后
 //删除锁定
 System.Threading.Monitor.Exit（itemLock）; 
} 
} 
} 
} 
} 
 //理想中的'锁'的唯一对象将是开放的操作了。 
返回真; 
} 
} 
  

使用示例

  LockProvider p =新LockProvider（）; 
 BOOL成功= p.TryExecute（文件名，1000年，委托（）{
 //此代码执行锁
内}）; 
  

解决方案

似乎没有成为一个优雅的方式来为此在.NET中，虽然我已经改进了算法，感谢@ RobV的一个循环的建议。这里是最终的解决方案，我看中了。

这是免疫，这似乎是典型的标准模式后跟@史蒂芬的回答的孤儿参考错误。

 使用系统; 
使用System.Collections.Generic; 
使用System.Text; 
使用的System.Threading; 
 
命名空间ImageResizer.Plugins.DiskCache {
 
公众委托无效LockCallback（）; 
 ///<总结> 
 ///提供了基于字符串键锁定。 
 ///锁是本地的LockProvider实例。 
 ///类处理未使用的锁处置。一般用于
 ///协调写入文件（其中可能有上百万）。 
 ///仅保留在存储器键/锁对这是在使用中。 
 ///线程安全的。 
 ///< /总结> 
公共类LockProvider {
 
 ///<总结> 
 ///此集合中的唯一对象应该是打开的文件。 
 ///< /总结> 
保护字典<弦乐，对象>锁= 
新字典<字符串对象>（StringComparer.Ordinal）; 
 ///<总结> 
 ///同步对象进行修改的'锁'字典
 ///< /总结> 
保护对象createLock =新的对象（）; 
 ///<总结> 
 ///试图执行基于钥匙锁里面的'成功'回调。如果成功，返回true。 
 ///如果锁不能'timoutMs'内获得，返回false 
 ///在最坏的情况下，它可以以两倍长占用为timeoutMs'返回假。 
 ///< /总结> 
 ///< PARAM NAME =键>< /参数> 
 ///< PARAM NAME =成功>< /参数> 
 ///< PARAM NAME =失败>< /参数> 
 ///< PARAM NAME =timeoutMs>< /参数> 
公共BOOL TryExecute（字符串键，诠释timeoutMs，LockCallback成功）{
 //记录，当我们开始。我们不希望一个无限循环。 
的DateTime startedAt = DateTime.UtcNow; 
 
 //跟踪获取的锁是否仍然是正确的
布尔validLock = TRUE; 
 //相当于'键'
对象的锁itemLock = NULL; 
 
尝试{
 //我们必须循环直到我们得到了一个有效的锁，直到我们锁定它，它保持有效。 
做{
 // 1）创建/ AQUIRE阶段
锁（createLock）{
 //我们必须锁定字典写，否则
 // 2对同一文件的锁可以创建并同时分配
 //。 （即，TryGetValue和分配之间），
如果
锁[关键] = itemLock =新的对象（）（locks.TryGetValue（键，出itemLock）！）; //创建一个新的锁！ 
 
} 
 //漏洞（第1部分）：
 //就在这里 - 这是另一个线程（执行第2部分）可以删除itemLock'
 / /从字典中，并有可能，另一个线程可以
 //插入了itemLock到字典...等等，等等。
 
 // 2）执行新的价值相
如果（System.Threading.Monitor.TryEnter（itemLock，timeoutMs））{
尝试{
 //需要一段时间，获取这个锁。 
 
 //试图检测漏洞高于
的occurence //检查itemLock依然存在，字典
锁（createLock）{
对象newLock = NULL匹配; 
 validLock = locks.TryGetValue（键，出newLock）; 
 validLock = validLock&放大器;&安培; newLock == itemLock; 
} 
 //只有在锁定是有效的
如果（validLock）{
成功（）运行回调; //极长时间运行的回调，或许抛出异常
返回真; 
} 
 
} {最后
 System.Threading.Monitor.Exit（itemLock）; //释放锁
} 
}其他{
 validLock = FALSE; //所以最后子句不尝试清理锁，别人会做到这一点。 
返回FALSE; //别人了锁，他们可以清理。 
} 
 
 //我们是出来的时候，仍然有一个无效的锁？ 
如果（validLock&安培;！&安培; Math.Abs​​（DateTime.UtcNow.Subtract（startedAt）.TotalMilliseconds）GT; timeoutMs）{
 //我们没有得到及时有效的锁。 
返回FALSE; 
} 
 
 
 //如果我们有一个无效的锁，我们必须尝试重新一切。 
}，而（validLock！）; 
} {最后
如果（validLock）{
 //漏洞（部分2）。当漏洞部分1和2交叉路径，
 //一个锁定对象可以在使用前被删除，被孤立
 
 // 3）清除阶段 - 锁的尝试清理对象，因此我们不要
 //有一个非常* *大和缓慢的字典。 
锁（createLock）{
 // TryEnter（）失败，而不是等待。 
 //一个普通的锁会导致与第2阶段
 //指定超时将增加巨大的和毫无意义的开销死锁。 
 //谁拥有锁将清理也。如果
（System.Threading.Monitor.TryEnter（itemLock））{
尝试{
 //成功，所以没有其他人正在这
 //（但可能准备，看到漏洞）
 //只有解除锁定对象，如果它
 //在字典中仍然存在原样
对象existingLock = NULL; 
如果（locks.TryGetValue（键，出existingLock）
和;&安培; existingLock == itemLock）
 locks.Remove（键）; 
} {最后
 //删除锁定
 System.Threading.Monitor.Exit（itemLock）; 
} 
} 
} 
} 
} 
 //理想中的'锁'的唯一对象将是开放的操作了。 
返回真; 
} 
} 
} 
  

消费这个代码很简单

  LockProvider p =新LockProvider（）; 
 BOOL成功= p.TryExecute（文件名，1000年，委托（）{
 //此代码执行锁
内}）; 
  

Here's the task: I need to lock based on a filename. There can be up to a million different filenames. (This is used for large-scale disk-based caching). I want low memory usage and low lookup times, which means I need a GC'd lock dictionary. (Only in-use locks can be present in the dict).

The callback action can take minutes to complete, so a global lock is unacceptable. High throughput is critical.

I've posted my current solution below, but I'm unhappy with the complexity.

EDIT: Please do not post solutions that are not 100% correct. For example, a solution which permits a lock to be removed from the dictionary between the 'get lock object' phase and the 'lock' phase is NOT correct, whether or not it is an 'accepted' design pattern or not.

Is there a more elegant solution than this?

Thanks!

[EDIT: I updated my code to use looping vs. recursion based on RobV's suggestion]

[EDIT: Updated the code again to allow 'timeouts' and a simpler calling pattern. This will probably be the final code I use. Still the same basic algorithm as in the original post.]

[EDIT: Updated code again to deal with exceptions inside callback without orphaning lock objects]

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

Usage example

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

解决方案

There doesn't seem to be an elegant way to do this in .NET, although I have improved the algorithm thanks to @RobV's suggestion of a loop. Here is the final solution I settled on.

It is immune to the 'orphaned reference' bug that seems to be typical of the standard pattern followed by @Steven's answer.

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

Consuming this code is very simple:

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

这篇关于较好地解决了多线程谜？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！