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

御笔剑客

1. package main
   
2. 
   
3. import "fmt"
   
4. import "sync"
   
5. 
   
6. type Node struct {
   
7.         h, w int
   
8. }
   
9. 
   
10. var (
    
11.         arr   = make([]Node, 1e5)
    
12.         n, k  int
    
13.         ch    = make(chan int)
    
14.         judge = make(chan bool)
    
15.         wg    sync.WaitGroup
    
16. )
    
17. 
    
18. func check() {
    
19.         tot, num := 0, <-ch
    
20.         for i := 0; i < n; i++ {
    
21.                 tot += (arr[i].h / num) * (arr[i].w / num)
    
22.                 if tot >= k {
    
23.                         judge <- true
    
24.                         return
    
25.                 }
    
26.         }
    
27.         judge <- false
    
28. }
    
29. 
    
30. func main() {
    
31.         fmt.Scanf("%d %d", &n, &k)
    
32.         for i := 0; i < n; i++ {
    
33.                 fmt.Scanf("%d %d", &arr[i].h, &arr[i].w)
    
34.         }
    
35. 
    
36.         wg.Add(1)
    
37.         go check()
    
38.         go func() {
    
39.                 l, r := 1, 100000
    
40.                 for l < r {
    
41.                         mid := (l + r + 1) >> 1
    
42.                         ch <- mid
    
43.                         if <-judge {
    
44.                                 l = mid
    
45.                         } else {
    
46.                                 r = mid - 1
    
47.                         }
    
48.                 }
    
49.                 ch <- l
    
50.                 wg.Done()
    
51.         }()
    
52.         fmt.Println(<-ch)
    
53.         wg.Wait()
    
54. }
    

复制代码

输入：
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这个函数了，不能让它提前返回。

我的修改如下：

1. package main
   
2. 
   
3. import (
   
4.         "fmt"
   
5.         "sync"
   
6. )
   
7. 
   
8. type Node struct {
   
9.         h, w int
   
10. }
    
11. 
    
12. var (
    
13.         arr    = make([]Node, 3)
    
14.         n, k   int
    
15.         ch     = make(chan int)
    
16.         result = make(chan int) // 保存结果，与ch分开，避免共用
    
17.         judge  = make(chan bool)
    
18.         wg     sync.WaitGroup
    
19. )
    
20. 
    
21. func check() {
    
22.         tot := 0
    
23. loop:
    
24.         for num := range ch {
    
25.                 for i := 0; i < n; i++ {
    
26.                         tot += (arr[i].h / num) * (arr[i].w / num)
    
27.                         if tot >= k {
    
28.                                 judge <- true
    
29.                                 continue loop
    
30.                         }
    
31.                 }
    
32.                 judge <- false
    
33.         }
    
34. }
    
35. 
    
36. func main() {
    
37.         fmt.Scanf("%d %d\n", &n, &k)
    
38.         for i := 0; i < n; i++ {
    
39.                 fmt.Scanf("%d %d\n", &arr[i].h, &arr[i].w)
    
40.         }
    
41. 
    
42.         l, r := 1, 100000
    
43.         wg.Add(1)
    
44.         go check()
    
45.         go func() {
    
46.                 for l < r {
    
47.                         mid := (l + r + 1) >> 1
    
48.                         ch <- mid
    
49.                         if <-judge {
    
50.                                 l = mid
    
51.                         } else {
    
52.                                 r = mid - 1
    
53.                         }
    
54.                         fmt.Printf("l: %v, r: %v, mid: %v\n", l, r, mid)
    
55.                 }
    
56.                 close(ch)
    
57.                 wg.Done()
    
58.                 result <- l
    
59.         }()
    
60.         wg.Wait()
    
61.         fmt.Println(<-result)
    
62. }

复制代码

跳转到最佳答案楼层

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这个函数了，不能让它提前返回。

我的修改如下：

1. package main
   
2. 
   
3. import (
   
4.         "fmt"
   
5.         "sync"
   
6. )
   
7. 
   
8. type Node struct {
   
9.         h, w int
   
10. }
    
11. 
    
12. var (
    
13.         arr    = make([]Node, 3)
    
14.         n, k   int
    
15.         ch     = make(chan int)
    
16.         result = make(chan int) // 保存结果，与ch分开，避免共用
    
17.         judge  = make(chan bool)
    
18.         wg     sync.WaitGroup
    
19. )
    
20. 
    
21. func check() {
    
22.         tot := 0
    
23. loop:
    
24.         for num := range ch {
    
25.                 for i := 0; i < n; i++ {
    
26.                         tot += (arr[i].h / num) * (arr[i].w / num)
    
27.                         if tot >= k {
    
28.                                 judge <- true
    
29.                                 continue loop
    
30.                         }
    
31.                 }
    
32.                 judge <- false
    
33.         }
    
34. }
    
35. 
    
36. func main() {
    
37.         fmt.Scanf("%d %d\n", &n, &k)
    
38.         for i := 0; i < n; i++ {
    
39.                 fmt.Scanf("%d %d\n", &arr[i].h, &arr[i].w)
    
40.         }
    
41. 
    
42.         l, r := 1, 100000
    
43.         wg.Add(1)
    
44.         go check()
    
45.         go func() {
    
46.                 for l < r {
    
47.                         mid := (l + r + 1) >> 1
    
48.                         ch <- mid
    
49.                         if <-judge {
    
50.                                 l = mid
    
51.                         } else {
    
52.                                 r = mid - 1
    
53.                         }
    
54.                         fmt.Printf("l: %v, r: %v, mid: %v\n", l, r, mid)
    
55.                 }
    
56.                 close(ch)
    
57.                 wg.Done()
    
58.                 result <- l
    
59.         }()
    
60.         wg.Wait()
    
61.         fmt.Println(<-result)
    
62. }

复制代码