[已解决]为什么下面这段代码会出现死锁呢？

御笔剑客

package main

import "fmt"
import "sync"

type Node struct {
        h, w int
}

var (
        arr   = make([]Node, 1e5)
        n, k  int
        ch    = make(chan int)
        judge = make(chan bool)
        wg    sync.WaitGroup
)

func check() {
        tot, num := 0, <-ch
        for i := 0; i < n; i++ {
                tot += (arr[i].h / num) * (arr[i].w / num)
                if tot >= k {
                        judge <- true
                        return
                }
        }
        judge <- false
}

func main() {
        fmt.Scanf("%d %d", &n, &k)
        for i := 0; i < n; i++ {
                fmt.Scanf("%d %d", &arr[i].h, &arr[i].w)
        }

        wg.Add(1)
        go check()
        go func() {
                l, r := 1, 100000
                for l < r {
                        mid := (l + r + 1) >> 1
                        ch <- mid
                        if <-judge {
                                l = mid
                        } else {
                                r = mid - 1
                        }
                }
                ch <- l
                wg.Done()
        }()
        fmt.Println(<-ch)
        wg.Wait()
}

输入：
2 10
5 6
6 5

应该输出2

最佳答案

月排行榜 / 总排行榜

Brick_Porter

2022-9-30 19:43:55

看了你的代码，我发现第52行和第19行，main和check这两个goroutine都在从通道ch取值，也就是说这两个goroutine会发生争抢。整个程序执行过程中只要check没有抢到ch发送的值，那么tot, num := 0, <-ch这行代码就会一直阻塞从而引发死锁。

我想了一会儿，可以调换52、53这两行代码，如此一来可以保证暂时只有check可以从ch中取值，从而避免了19行的阻塞从而导致死锁问题。但这样做没有从根本上解决死锁问题。第一轮迭代程序第43行从judge中取值为false，所以r的值变为50000，1<50000成立，继续第二轮迭代。当程序执行到第42行的时候由于之前的check已经返回了，所以再没有其他goroutine从ch取值，这里又会阻塞从而引发死锁。要彻底解决这个死锁问题，就需要重写check这个函数了，不能让它提前返回。

我的修改如下：

package main

import (
        "fmt"
        "sync"
)

type Node struct {
        h, w int
}

var (
        arr    = make([]Node, 3)
        n, k   int
        ch     = make(chan int)
        result = make(chan int) // 保存结果，与ch分开，避免共用
        judge  = make(chan bool)
        wg     sync.WaitGroup
)

func check() {
        tot := 0
loop:
        for num := range ch {
                for i := 0; i < n; i++ {
                        tot += (arr[i].h / num) * (arr[i].w / num)
                        if tot >= k {
                                judge <- true
                                continue loop
                        }
                }
                judge <- false
        }
}

func main() {
        fmt.Scanf("%d %d\n", &n, &k)
        for i := 0; i < n; i++ {
                fmt.Scanf("%d %d\n", &arr[i].h, &arr[i].w)
        }

        l, r := 1, 100000
        wg.Add(1)
        go check()
        go func() {
                for l < r {
                        mid := (l + r + 1) >> 1
                        ch <- mid
                        if <-judge {
                                l = mid
                        } else {
                                r = mid - 1
                        }
                        fmt.Printf("l: %v, r: %v, mid: %v\n", l, r, mid)
                }
                close(ch)
                wg.Done()
                result <- l
        }()
        wg.Wait()
        fmt.Println(<-result)
}

跳转到最佳答案楼层

Brick_Porter

看了你的代码，我发现第52行和第19行，main和check这两个goroutine都在从通道ch取值，也就是说这两个goroutine会发生争抢。整个程序执行过程中只要check没有抢到ch发送的值，那么tot, num := 0, <-ch这行代码就会一直阻塞从而引发死锁。

我想了一会儿，可以调换52、53这两行代码，如此一来可以保证暂时只有check可以从ch中取值，从而避免了19行的阻塞从而导致死锁问题。但这样做没有从根本上解决死锁问题。第一轮迭代程序第43行从judge中取值为false，所以r的值变为50000，1<50000成立，继续第二轮迭代。当程序执行到第42行的时候由于之前的check已经返回了，所以再没有其他goroutine从ch取值，这里又会阻塞从而引发死锁。要彻底解决这个死锁问题，就需要重写check这个函数了，不能让它提前返回。

我的修改如下：

package main

import (
        "fmt"
        "sync"
)

type Node struct {
        h, w int
}

var (
        arr    = make([]Node, 3)
        n, k   int
        ch     = make(chan int)
        result = make(chan int) // 保存结果，与ch分开，避免共用
        judge  = make(chan bool)
        wg     sync.WaitGroup
)

func check() {
        tot := 0
loop:
        for num := range ch {
                for i := 0; i < n; i++ {
                        tot += (arr[i].h / num) * (arr[i].w / num)
                        if tot >= k {
                                judge <- true
                                continue loop
                        }
                }
                judge <- false
        }
}

func main() {
        fmt.Scanf("%d %d\n", &n, &k)
        for i := 0; i < n; i++ {
                fmt.Scanf("%d %d\n", &arr[i].h, &arr[i].w)
        }

        l, r := 1, 100000
        wg.Add(1)
        go check()
        go func() {
                for l < r {
                        mid := (l + r + 1) >> 1
                        ch <- mid
                        if <-judge {
                                l = mid
                        } else {
                                r = mid - 1
                        }
                        fmt.Printf("l: %v, r: %v, mid: %v\n", l, r, mid)
                }
                close(ch)
                wg.Done()
                result <- l
        }()
        wg.Wait()
        fmt.Println(<-result)
}