Un blocage se produit lors de l'implémentation récursive/parallèle du tri par fusion dans Golang

L'éditeur PHP Xigua a découvert que lors de l'utilisation de la récursion ou de l'implémentation parallèle du tri par fusion dans Golang, des problèmes de blocage peuvent survenir. Le tri par fusion est un algorithme de tri couramment utilisé qui peut efficacement diviser un grand tableau en plusieurs petits tableaux pour le tri, puis les fusionner. Cependant, dans la programmation simultanée dans Golang, si vous ne faites pas attention au contrôle de la synchronisation entre les goroutines, un blocage peut survenir. Cet article explorera ce problème en détail et proposera des solutions.

Contenu de la question

J'essaie d'en savoir plus sur la concurrence dans Golang, j'essaie donc d'améliorer l'algorithme MergeSort pour effectuer un tri simultané.

Mon idée est de créer une goroutine à chaque fois que je divise le tableau en deux, donc mon code est le suivant :

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

Mais j'ai eu une erreur fatale :

fatal error: all goroutines are asleep - deadlock!

Qu'est-ce que j'ai fait de mal ?

Workaround

peut être un peu déroutante car vous mélangez deux modes de concurrence. J'y serai dans un instant.

Lorsque vous utilisez un canal sans tampon, le Goroutine émetteur se bloquera jusqu'à ce que le Goroutine récepteur soit prêt à recevoir la valeur. Dans ce cas, la Goroutine principale attend que deux Goroutines l'utilisent wg.Wait() 完成，而两个 Goroutine 正在尝试将其结果发送到通道 orderedLeft 和 orderedRight. Cependant, comme la goroutine principale ne reçoit pas activement ces valeurs du canal, la goroutine est bloquée et ne peut pas continuer jusqu'à son achèvement.

Vous pouvez facilement résoudre ce problème en mettant en mémoire tampon le canal : orderedRight := make(chan []int, 1).

Cependant, vous pouvez utiliser des canaux ou des waitGroups au lieu de les mélanger, ce qui n'est pas nécessaire dans ce cas :

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!