如何判断一个 goroutine 是否成功或所有 goroutines 都已完成？

Question

我正在尝试使用 DFS 通过检查图中每个节点的循环来检查图的循环。

我想运行为每个节点创建一个 goroutine，并在检测到第一个循环或没有循环时终止。

在检测到第一个循环时终止似乎没问题，但我无法将其与不再有节点的情况混合使用。

下面是一个似乎可以工作的实现，但对我来说看起来很糟糕，我一直在寻找更好的实现。我基本上使用缓冲通道并在每次我没有得到一个循环时增加一个计数器并在计数器达到底层图形的大小时终止。

使用计数器来确定我们何时完成对我来说似乎不合时宜。或者，更确切地说，很高兴知道在 Go 中是否有更惯用的方法来执行此操作。

func (c *cycleDet) hasCycle() bool {
    adj := c.b // adjacency list representation of the unerlying graph
    hasCycles := make(chan bool, len(adj))

    for node := range adj {
        go func(no nodeID, co chan<- bool) {
            visited := make(map[nodeID]struct{})
            // c.nodeHasCycle will use a recursive implementation of DFS to
            // find out if the node no leads to a cycle.
            if c.nodeHasCycle(no, visited) {
                co <- true
                return
            }
            co <- false
        }(node, hasCycles)
    }

    var i int
    for {
        select {
        case v := <-hasCycles:
            if v {
                fmt.Println("got cycle")
                return true
            }
            if i == len(c.b) {
                return false
            }
            i++
        }
    }
}

我还遇到了另一个推荐使用“观察者”goroutine 的 SO post（尽管我找不到 SO post）。我不确定那会是什么样子，但想象一下它会像这样与 WaitGroups 混合：

func (c *cycleDet) hasCycle() bool {
    hasCycle := make(chan bool)
    done := make(chan struct{})
    var wg sync.WaitGroup

    adj := c.b // adjacency list representation of the unerlying graph
    for node := range adj {
        go func(no nodeID, co chan<- bool) {
            // Use wg to synchronize termination of read-only goroutines.
            wg.Add(1)
            defer wg.Done()

            visited := make(map[nodeID]struct{})
            // c.nodeHasCycle will use a recursive implementation of DFS to
            // find out if the node no leads to a cycle.
            if c.nodeHasCycle(no, visited) {
                co <- true
                return
            }
        }(node, hasCycle)
    }

    // Observer goroutine to notify when wg is done waiting.
    time.Sleep(100 * time.Millisecond)
    go func() {
        wg.Wait()
        done <- struct{}{}
    }()

    select {
    case <-hasCycle:
        fmt.Println("got a cycle")
        return true
    case <-done:
        fmt.Println("no cycle detected")
        return false
    }
}

但是这种方法让我担心，因为我需要睡觉让观察者仅在第一个 WaitGroup 计数器递增后才开始等待，这似乎比第一个解决方案脆弱得多。

Answer 1

您说得对，WaitGroup 可能就是您想要的。但是，您没有正确使用它。首先，您需要在调用 wg.Done() 的 go 例程之外调用 wg.Add(1)。其次，调用 wg.Wait() 块，直到等待组中的所有 go 例程执行完毕，所以你不希望它并发执行。

至于 short-circuiting，确实没有什么好办法。我的建议是使用上下文。在这种情况下，您必须做的一件事是，如果您想要真正的 short-circuiting 行为，则将上下文连接到 nodeHasCycle 的调用中。

正在修复您的代码，我们有：

func (c *cycleDet) hasCycle() bool {
    ctx, cancel := context.WithCancel(context.Background())
    hasCycle := make(chan bool)
    var wg sync.WaitGroup

    adj := c.b // adjacency list representation of the unerlying graph
    for node := range adj {
        wg.Add(1)
        go func(ctx context.Context, no nodeID, co chan<- bool, cancel context.CancelFunc) {
            // Use wg to synchronize termination of read-only goroutines.
            defer wg.Done()

            select {
                case <-ctx.Done():
                    return
                default:
            }

            visited := make(map[nodeID]struct{})
            // c.nodeHasCycle will use a recursive implementation of DFS to
            // find out if the node no leads to a cycle.
            if c.nodeHasCycle(ctx, no, visited) {
                co <- true
                cancel()
                return
            }
        }(ctx, node, hasCycle, cancel)
    }

    // Observer goroutine to notify when wg is done waiting.
    time.Sleep(100 * time.Millisecond)
    wg.Wait()
    defer cancel()

    select {
    case <-hasCycle:
        fmt.Println("got a cycle")
        return true
    default:
        fmt.Println("no cycle detected")
        return false
    }
}

以这种方式设置后，您可以确保对 go-routine 的所有调用都将运行，除非找到循环，在这种情况下不会调用其他 go-routes，并且如果您在 nodeHasSycle 中添加检查取消的逻辑，然后您也可以停止执行对它的任何运行调用。

如何判断一个 goroutine 是否成功或所有 goroutines 都已完成？

How to tell if one goroutine succeeded or all goroutines are done?

go

depth-first-search

goroutine