在Golang中Mergesort的递归并行实现中出现死锁

发布于11月30日

我正在try 学习更多关于Golang中的并发性的知识，所以我正在try 改进MergeSort算法来进行并发排序.

我的 idea 是每次将数组一分为二时创建一个goroutine，所以我的代码是这样的:

func mergeSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }

    mid := len(arr) / 2
    left := arr[:mid]
    right := arr[mid:]

    orderedLeft := make(chan []int)
    orderedRight := make(chan []int)

    var wg sync.WaitGroup

    wg.Add(2)
    go func() {
        defer wg.Done()

        left = mergeSort(left)
        orderedLeft <- left
    }()

    go func() {
        defer wg.Done()
        right = mergeSort(right)
        orderedRight <- right
    }()

    wg.Wait()

    close(orderedLeft)
    close(orderedRight)

    left = <-orderedLeft
    fmt.Println(left)
    right = <-orderedRight
    fmt.Println(right)

    return merge(left, right)
}

但我得到了一个致命的错误:

fatal error: all goroutines are asleep - deadlock!

我做错了什么？

推荐答案

可能会有点混乱，因为您混合了两种并发模式.我马上就到.

当您使用无缓冲通道时，发送方Goroutine将被阻止，直到接收方Goroutine准备好接收该值. 在本例中，主Goroutine正在等待两个Goroutine使用wg.Wait()完成，而两个Goroutine正在try 将其结果发送到通道orderedLeft和orderedRight.然而，由于主Goroutine没有主动地从通道接收这些值，Goroutine被阻塞并且无法继续进行完成.

您可以通过将通道设置为缓冲:orderedRight := make(chan []int, 1)来轻松解决此问题.

但是，您可以使用channels或waitGroup，而不是混合使用它们，在这种情况下，这并不是真正必要的:

func mergeSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }

    mid := len(arr) / 2
    left := arr[:mid]
    right := arr[mid:]

    var wg sync.WaitGroup

    wg.Add(2)
    go func() {
        defer wg.Done()
        left = mergeSortWg(left)
    }()

    go func() {
        defer wg.Done()
        right = mergeSortWg(right)
    }()

    wg.Wait()

    return merge(left, right)
}

在Golang中Mergesort的递归并行实现中出现死锁

推荐答案

Go相关问答推荐

在Golang中，@LATEST和@UPGRADE特殊查询有什么不同？

创建使用逗号而不是加号分隔OU的CSR

如何防止程序B存档/删除围棋中程序A当前打开的文件？

JWT 如何解析声明有效性和错误？

Go 中将 int 切片转换为自定义 int 切片指针类型的函数

无法读取postman 中的表单数据

在 Windows 11 上运行 go mod tidy 时的 gitlab 权限问题

为什么我只收到部分错误而不是我启动的 goroutines 的所有错误？

如何在 Go 中将 int 转换为包含 complex128 的泛型类型？

如何解决我的 Go 聊天应用程序中 cookie 未在本地主机端口之间传输的问题？

如何从 Go 中的 `HijackedResponse` 中删除 Cursor Position ANSI 转义码？

将值发送到 Channel 并在就绪时读取输出

如何使用带有方法的字符串枚举作为通用参数？

Golang Echo Labstack 如何在模板视图中调用函数/方法

如何在golang中使用ozzo验证进行时间最大验证

在 Go 中将十六进制转换为带符号的 Int

go routine 和接收错误或成功的通道

(如何)我可以基于接口抽象地实现Stringer吗？

手动下载并放置一个 golang mod 文件

为什么 Go 不允许将一个泛型分配给另一个泛型？