Deadlock tritt bei der rekursiven/parallelen Implementierung der Zusammenführungssortierung in Golang auf

Der PHP-Editor Xigua hat festgestellt, dass bei Verwendung von Rekursion oder paralleler Implementierung der Zusammenführungssortierung in Golang Deadlock-Probleme auftreten können. Merge Sort ist ein häufig verwendeter Sortieralgorithmus, der ein großes Array zum Sortieren effektiv in mehrere kleine Arrays aufteilen und diese dann zusammenführen kann. Wenn Sie jedoch bei der gleichzeitigen Programmierung in Golang nicht auf die Steuerung der Synchronisation zwischen Goroutinen achten, kann es zu einem Deadlock kommen. In diesem Artikel wird dieses Problem im Detail untersucht und Lösungen bereitgestellt.

Frageninhalt

Ich versuche, mehr über Parallelität in Golang zu erfahren, also versuche ich, den MergeSort-Algorithmus zu verbessern, um eine gleichzeitige Sortierung durchzuführen.

Meine Idee ist es, jedes Mal, wenn ich das Array in zwei teile, eine Goroutine zu erstellen, daher lautet mein Code wie folgt:

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

Aber ich habe einen schwerwiegenden Fehler gemacht:

fatal error: all goroutines are asleep - deadlock!

Was habe ich falsch gemacht?

Workaround

kann etwas verwirrend sein, da Sie zwei Parallelitätsmodi mischen. Ich bin gleich da.

Wenn Sie einen ungepufferten Kanal verwenden, blockiert die Sender-Goroutine, bis die Empfänger-Goroutine bereit ist, den Wert zu empfangen. In diesem Fall wartet die Haupt-Goroutine auf die Verwendung durch zwei Goroutinen wg.Wait() 完成，而两个 Goroutine 正在尝试将其结果发送到通道 orderedLeft 和 orderedRight. Da die Haupt-Goroutine diese Werte jedoch nicht aktiv vom Kanal empfängt, ist die Goroutine blockiert und kann nicht bis zum Abschluss fortgesetzt werden.

Sie können dieses Problem leicht lösen, indem Sie den Kanal puffern: orderedRight := make(chan []int, 1).

Sie können jedoch Kanäle oder WaitGroups verwenden, anstatt sie zu mischen, was in diesem Fall nicht erforderlich ist:

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

Das obige ist der detaillierte Inhalt vonDeadlock tritt bei der rekursiven/parallelen Implementierung der Zusammenführungssortierung in Golang auf. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!