英文:
Goroutines deadlock recursive
问题
我有一个深度优先搜索（DFS）递归函数，它可以给我在有向图中的所有可能路径。
但是我无法准确知道它何时完成。
func dfs(data map[int][]int, path []int) {
datum := path[len(path)-1]
value := data[datum]
for i := 0; i < len(value); i++ {
if !contains(path, value[i]) {
new_path := append(path, []int{value[i]}...)
if len(new_path) > len(max_path) {
max_path = new_path
}
dfs(data, new_path)
}
}
}
我尝试在不同情况下使用goroutines来执行这个函数，以减少时间。通过使用goroutines，我可以大大提高速度（大约是10倍）。
for _, node := range nodes {
if is_touching_wall(node) {
wg.Add(1)
go dfs(graph, []int{node})
}
}
wg.Wait()
正如你所理解的，我调用了wg.Add(1)，但是没有调用wg.Done()。这会导致"fatal error: all goroutines are asleep - deadlock!"的错误。
我试图找到DFS完成的时间，以便调用Done()，但是无法成功。
是否有其他方法可以在goroutines即将发生死锁时取消它们，或者我应该尝试另一种方法？
英文:
I have a DFS recursive function which gives me all possible routes in a directed graph.
And I can't precisely know when it finishes.
func dfs(data map[int][]int, path []int) {
datum := path[len(path)-1]
value := data[datum]
for i := 0; i < len(value); i++ {
if !contains(path, value[i]) {
new_path := append(path, []int{value[i]}...)
if len(new_path) > len(max_path) {
max_path = new_path
}
dfs(data, new_path)
}
}
}
I try to execute this function on goroutines for different cases. In order to reduce time I use goroutines. (By the way it really speeds things up like 10x or much)
for _, node := range nodes {
if is_touching_wall(node) {
wg.Add(1)
go dfs(graph, []int{node})
}
}
wg.Wait()
As you can understand here, I call wg.add(1) but i don't call wg.Done() later. So it creates "fatal error: all goroutines are asleep - deadlock!".
I tried to find the time when DFS finishes, in order to call Done() but couldn't manage it.
Is there any other way to cancel goroutines if they are going to be deadlocked or should i try another approach here ?
答案1
得分: 1
你使用goroutines的方式来进行这种方法，可能不会获得太多的收益。如果DFS在一棵树上运行，那么你可以将其分割成不相交的部分，并在每个部分上使用goroutines。但是对于有向图，你无法确定一个goroutine遍历的节点是否也被其他goroutine遍历。
然而，为了解决死锁问题，你必须在goroutine结束时调用wg.Done。一种简单的方法是：
wg.Add(1)
go func() {
defer wg.Done()
dfs(graph, []int{node})
}()
这只能解决死锁问题，而不能解决你的实际问题。
英文:
It is unlikely that you will gain much, if any, using goroutines the way you do for this approach. If the DFS is running on a tree, then you can potentially split it into disjoint sections and use goroutines on each. With a directed graph, you have no idea if nodes traversed by one goroutine are also being traversed by others.
Nevertheless, in order to deal with the deadlock, you must call wg.Done when a goroutine ends. A simple way of doing it is:
wg.Add(1)
go func() {
defer wg.Done()
dfs(graph, []int{node})
}()
This will not solve your real problem though, only the deadlocks.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论