Kebuntuan berlaku dalam pelaksanaan rekursif/selari isihan gabungan dalam golang

Editor PHP Xigua mendapati bahawa apabila menggunakan rekursi atau pelaksanaan selari bagi isihan gabungan dalam golang, masalah kebuntuan mungkin berlaku. Isih Cantum ialah algoritma pengisihan yang biasa digunakan yang boleh memecahkan tatasusunan besar kepada berbilang tatasusunan kecil dengan berkesan untuk mengisih dan kemudian menggabungkannya bersama-sama. Walau bagaimanapun, dalam pengaturcaraan serentak di Golang, jika anda tidak memberi perhatian untuk mengawal penyegerakan antara goroutine, kebuntuan mungkin berlaku. Artikel ini akan meneroka masalah ini secara terperinci dan memberikan penyelesaian.

Kandungan soalan

Saya cuba mempelajari lebih lanjut tentang concurrency di Golang, jadi saya cuba memperbaik algoritma MergeSort untuk melakukan pengisihan serentak.

Idea saya adalah untuk mencipta goroutine setiap kali saya membahagikan tatasusunan kepada dua, jadi kod saya adalah seperti berikut:

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)
}

Tetapi saya mendapat ralat maut:

fatal error: all goroutines are asleep - deadlock!

Apa salah saya?

Penyelesaian

boleh agak mengelirukan kerana anda mencampurkan dua mod konkurensi. Sekejap lagi saya akan sampai.

Apabila anda menggunakan saluran tanpa buffer, pengirim Goroutine akan menyekat sehingga penerima Goroutine bersedia untuk menerima nilai. Dalam kes ini, Goroutine utama sedang menunggu dua Goroutine untuk digunakan wg.Wait() 完成，而两个 Goroutine 正在尝试将其结果发送到通道 orderedLeft 和 orderedRight. Walau bagaimanapun, memandangkan goroutine utama tidak menerima nilai ini secara aktif daripada saluran, goroutine disekat dan tidak boleh terus disiapkan.

Anda boleh menyelesaikan masalah ini dengan mudah dengan menampan saluran: orderedRight := make(chan []int, 1).

Walau bagaimanapun, anda boleh menggunakan saluran atau waitGroups dan bukannya mencampurkannya, yang tidak diperlukan dalam kes ini:

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)
}

Atas ialah kandungan terperinci Kebuntuan berlaku dalam pelaksanaan rekursif/selari isihan gabungan dalam golang. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!