Goroutines deadlock recursive

user_10873733 0
Viewed 37

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 ?

goroutine go deadlock
1 Answers

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.

user_119239990
Related