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中文網其他相關文章！