Deadlock occurs in recursive/parallel implementation of merge sort in golang

php editor Xigua discovered that when using recursion or parallel implementation of merge sort in golang, deadlock problems may occur. Merge sort is a commonly used sorting algorithm that can effectively break a large array into multiple small arrays for sorting and then merge them together. However, in concurrent programming in Golang, if you do not pay attention to controlling the synchronization between goroutines, deadlock may occur. This article will explore this problem in detail and provide solutions.

Question content

I'm trying to learn more about concurrency in Golang, so I'm trying to improve the MergeSort algorithm to do simultaneous sorting.

My idea is to create a goroutine every time the array is split into two, so my code is as follows:

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

But I encountered a fatal error:

fatal error: all goroutines are asleep - deadlock!

What did i do wrong?

Workaround

It can be a little confusing because you are mixing two concurrency modes. I'll be there in a moment.

When you use an unbuffered channel, the sender Goroutine will block until the receiver Goroutine is ready to receive a value. In this case, the main Goroutine is waiting for the two Goroutines to finish using wg.Wait(), while the two Goroutines are trying to send their results to channels orderedLeft and orderedRight. However, since the main goroutine is not actively receiving these values ​​from the channel, the goroutine is blocked and cannot continue to completion.

You can easily solve this problem by buffering the channel: orderedRight := make(chan []int, 1).

However, you can use channels or waitGroups instead of mixing them, which is not necessary in this case:

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

The above is the detailed content of Deadlock occurs in recursive/parallel implementation of merge sort in golang. For more information, please follow other related articles on the PHP Chinese website!