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

zsbz8rwp 于 5个月前发布在 Go

关注(0)|答案(1)|浏览(75)

我正在尝试学习更多关于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!

型
我做错了什么？

go

来源：https://stackoverflow.com/questions/77574780/getting-deadlocks-in-a-recursive-parallel-implementation-of-mergesort-in-golang

1条答案

按热度按时间

s71maibg1#

可能会有点混乱，因为你混合了两种并发模式。
当你使用无缓冲通道时，发送方goroutine会阻塞，直到接收方goroutine准备好接收值。在这种情况下，主goroutine正在等待两个goroutine使用wg.Wait()完成，而两个goroutine正在尝试将它们的结果发送到通道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)
}

字符串

赞(0）回复(0）举报 5个月前

我来回答

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

1条答案

相关问题

热门标签

最新问答