首頁 > 後端開發 > Golang > golang 中合併排序的遞歸/並行實作中出現死鎖

golang 中合併排序的遞歸/並行實作中出現死鎖

WBOY
發布: 2024-02-10 13:15:08
轉載
500 人瀏覽過

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

來源:stackoverflow.com
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板