golang 中合并排序的递归/并行实现中出现死锁

php小编西瓜发现，在golang中使用递归或并行实现合并排序时，有可能出现死锁的问题。合并排序是一种常用的排序算法，可以有效地将一个大数组分解成多个小数组进行排序，然后再合并起来。然而，在golang的并发编程中，如果不注意控制goroutine之间的同步，就有可能导致死锁的情况发生。本文将详细探讨这个问题，并提供解决方案。

问题内容

我正在尝试了解有关 Golang 中并发性的更多信息，因此我正在尝试改进 MergeSort 算法以同时进行排序。

我的想法是每次将数组一分为二时创建一个 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 正在等待两个 Goroutines 使用 wg.Wait() 完成，而两个 Goroutine 正在尝试将其结果发送到通道 orderedLeft 和 orderedRight。但是，由于主 goroutine 没有主动从通道接收这些值，因此 goroutine 会被阻塞并且无法继续完成。

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

但是，您可以使用通道或 waitGroups 而不是混合使用它们，在这种情况下这并不是必需的：

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 中合并排序的递归/并行实现中出现死锁的详细内容。更多信息请关注PHP中文网其他相关文章！