使用WaitGroup后Goroutines仍提前终止？Heap排列算法并发问题求助

问题 #

在使用WaitGroup的情况下遇到了Goroutines无法正常结束的问题。以下代码是Heap排列算法的实现，为提升效率，为每个可能的首元素创建一个Goroutine，每个Goroutine处理(n-1)!个排列，理论上总排列数应为n!（n*(n-1)! = n!），但主程序似乎在子Goroutines完成前就退出了。

统计实际执行的排列数，结果并不固定：n=4时每次都能得到24个排列（即4!），所有Goroutines都能完成；但n=8时，得到的排列数约为13500，而非预期的40000（8!）。

请问该行为的原因是什么？如何确保所有Goroutines完成后主程序再退出？

package main

import (
    "fmt"
    "sync"
)

var wg sync.WaitGroup
var permutations int

func main() {

    n := 9

    wg.Add(n)

    for i := 0; i < n; i++ {

        var arr []int
        for j := 0; j < n; j++ {
            if i != j {
                arr = append(arr, j+1)
            }
        }
        go threadFunction(n-1, i+1, arr)
    }

    wg.Wait()

    fmt.Println(permutations)
}

func threadFunction(k int, suffix int, arr []int) {

    defer wg.Done()

    heapPermutation(k, suffix, arr)
}

func heapPermutation(k int, prefix int, arr []int) {

    if k == 1 {
        arr = append(arr, prefix)
        // fmt.Println(arr)
        permutations++
    } else {
        heapPermutation(k-1, prefix, arr)

        for i := 0; i < k-1; i++ {
            if k%2 == 0 {
                arr[i], arr[k-1] = arr[k-1], arr[i]
            } else {
                arr[0], arr[k-1] = arr[k-1], arr[0]
            }
            heapPermutation(k-1, prefix, arr)
        }
    }
}

原因与解决办法 #

问题根源 #

1. 竞态条件导致计数不准：全局变量permutations被多个Goroutine同时修改，permutations++不是原子操作——它实际是先读值、加1、再写回，多个Goroutine同时执行这三步时，会出现修改覆盖的情况，最终统计结果远低于预期。
2. 切片引用共享引发逻辑混乱：切片是引用类型，每个Goroutine传入的arr底层数组会被后续递归和循环修改，多个递归分支同时操作同一个数组，导致排列生成逻辑出错，部分排列根本没生成出来。

修复方案 #

1. 用原子操作保护计数：使用sync/atomic包的AddInt64方法来原子性地增加计数，避免多Goroutine修改冲突。
2. 递归时传递切片副本：每次递归调用heapPermutation前，创建当前切片的副本，让每个递归分支操作独立的底层数组，避免互相干扰。

修改后的代码：

package main

import (
    "fmt"
    "sync"
    "sync/atomic"
)

var wg sync.WaitGroup
var permutations int64

func main() {
    n := 9

    wg.Add(n)

    for i := 0; i < n; i++ {
        var arr []int
        for j := 0; j < n; j++ {
            if i != j {
                arr = append(arr, j+1)
            }
        }
        go threadFunction(n-1, i+1, arr)
    }

    wg.Wait()

    fmt.Println(permutations)
}

func threadFunction(k int, suffix int, arr []int) {
    defer wg.Done()
    heapPermutation(k, suffix, arr)
}

func heapPermutation(k int, prefix int, arr []int) {
    if k == 1 {
        // 创建副本避免修改原切片
        newArr := make([]int, len(arr))
        copy(newArr, arr)
        newArr = append(newArr, prefix)
        atomic.AddInt64(&permutations, 1)
    } else {
        // 传递切片副本进行递归
        heapPermutation(k-1, prefix, append([]int(nil), arr...))

        for i := 0; i < k-1; i++ {
            // 先复制切片再执行交换操作
            arrCopy := append([]int(nil), arr...)
            if k%2 == 0 {
                arrCopy[i], arrCopy[k-1] = arrCopy[k-1], arrCopy[i]
            } else {
                arrCopy[0], arrCopy[k-1] = arrCopy[k-1], arrCopy[0]
            }
            heapPermutation(k-1, prefix, arrCopy)
        }
    }
}

说明 #

• 原子操作atomic.AddInt64保证了多个Goroutine对计数的修改不会互相覆盖，最终统计结果准确。
• 每次递归时通过append([]int(nil), arr...)创建切片副本，让每个递归分支操作独立的数组，彻底解决了并发修改导致的排列生成错误问题，所有Goroutine都能正常完成任务。

内容的提问来源于stack exchange，提问作者Luqus