V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
The Go Programming Language
http://golang.org/
Go Playground
Go Projects
Revel Web Framework
bwangel
V2EX  ›  Go 编程语言

一条面试题引发的思考 Go 版本

  •  1
     
  •   bwangel ·
    bwangelme · 2019-04-07 09:42:15 +08:00 · 9289 次点击
    这是一个创建于 2056 天前的主题,其中的信息可能已经有所发展或是发生改变。

    说明

    前两天看到了这个帖子,https://www.v2ex.com/t/547045#reply53 感觉其中描述的问题很有意思,我就用 Go 把它提到的解决方案都实现了一遍,文章链接:一条面试题引发的关于 Go 语言中锁的思考,还请大家多多指教!

    ~~~正文分割线~~~

    一条面试题引发的关于 Go 语言中锁的思考

    前言

    前两天在 V2EX 上看到了一篇博文,《一条经典面试题引发的思考》,感觉很有意思,我就用 Go 把它的答案实现了一遍。

    问题描述及一个错误解法

    问题如下:

    编写一个程序,开启 3 个线程 A,B,C,这三个线程的输出分别为 A、B、C,每个线程将自己的 输出在屏幕上打印 10 遍,要求输出的结果必须按顺序显示。如:ABCABCABC....

    一个错误解法如下:

         1	package main
         2	
         3	import (
         4		"fmt"
         5		"sync"
         6	)
         7	
         8	var mu sync.Mutex
         9	var index int
        10	var endSignal = make(chan struct{})
        11	
        12	func echoRoutine(routineIndex int, routineName string) {
        13		for index < 30 {
        14			mu.Lock()
        15			if index%3 == routineIndex {
        16				fmt.Println(index, routineName)
        17				index++
        18			}
        19			mu.Unlock()
        20		}
        21	
        22		endSignal <- struct{}{}
        23	}
        24	
        25	func main() {
        26		routineNames := []string{"A", "B", "C"}
        27	
        28		for idx, name := range routineNames {
        29			go echoRoutine(idx, name)
        30		}
        31	
        32		for _ = range routineNames {
        33			<-endSignal
        34		}
        35		//Output:
        36		//0 A
        37		//1 B
        38		//2 C
        39		//3 A
        40		//4 B
        41		//5 C
        42		//6 A
        43		//7 B
        44		//8 C
        45		//9 A
        46		//10 B
        47		//11 C
        48		//12 A
        49		//13 B
        50		//14 C
        51		//15 A
        52		//16 B
        53		//17 C
        54		//18 A
        55		//19 B
        56		//20 C
        57		//21 A
        58		//22 B
        59		//23 C
        60		//24 A
        61		//25 B
        62		//26 C
        63		//27 A
        64		//28 B
        65		//29 C
        66		//30 A
        67		//31 B
        68	}
    

    从上面的输出可以看到,程序还额外输出了两次 A 和 B。首先说结论,这是因为检查条件index < 30 没有加锁。为了理解这个错误,首先我们需要了解一下 Go 的内存模型。

    Go 语言的内存模型

    首先说什么是 Go 的内存模型,在官方文档中是这样定义的:

    The Go memory model specifies the conditions under which reads of a variable in one goroutine can be guaranteed to observe values produced by writes to the same variable in a different goroutine.

    Go 语言的内存模型规定了一个 Goroutine 可以看见另外一个 Goroutine 修改同一个变量的值的条件,这类似于 Java 内存模型中 内存可见性 问题。

    Happens Before 原则

    在 Go 语言中,编译器和处理器会对执行的指令进行重排序。Go 语言会保证的是,在单个 Goroutine 内,重排序后的执行效果和未进行重排序(即在代码中定义的执行顺序)的执行效果是一样。但是在多个 Goroutine 的运行环境下,由于重排序的原因,一个 Goroutine 观察到的执行顺序可能和另外一个 Goroutine 观察到的不一样。例如一个 Goroutine 执行a = 1; b = 2,另一个 Goroutine 可能会在a被赋值之前先观察到b被赋值了。

    为了规范读和写的操作,Go 定义了 happens before 原则。对于变量读写操作,我们可以将其称作是事件。事件之间的顺序可以定义为三种,E1 发生在 E2 之前,E1 发生在 E2 之后,E1 和 E2 同时发生。

    在单个 Goroutine 内,happens before 顺序就是程序执行的顺序,如果下面两个条件都被满足的话,变量v的读取事件r,可以观察到变量v的写入事件w

    1. r没有在w之前发生。
    2. w之后,r之前,没有另外一个变量v的写入事件w'发生。

    总的来说,在单个 Goroutine 的环境下,读事件r会观察到最近的一个写事件w

    在多个 Goroutine 的运行环境下,如果需要让v的读取事件r观察到其写入事件w。需要满足更严格的条件:

    1. w发生在r之前
    2. 任何针对共享变量v的写入事件都发生在w之前或者r之后。

    因为在多个 Goroutine 的运行环境下,读写事件可能并行地发生,所以第一点更严格了一些,要求w必须在r之前发生,两者不能同时发生,且它们之间没有其他的写事件w'。 因此在多个 Goroutine 访问一个共享变量v的时候,我们必须使用同步事件去建立一个 happens before 条件来让读事件观察到目标写事件。

    此外,还需要注意的是:

    1. 在变量v发生写事件之前,它被初始化成对应类型的零值。
    2. 大于一个机器字的变量的读写事件,会表现成 未指定顺序 的多次机器字大小的读写操作。

    正确答案 V1

    了解了 Go 内存模型中的 Happens Before 原则之后,我们接着再来分析上述的错误代码。

    • 在 B Goroutine 输出完 28 之后,A, B, C 都会再循环了一次。
    • 接着会由 C 先来执行输出操作。由于 C 执行第 17 行i++的写操作和 A 和 B 执行第 13 行index < 30读操作是并行发生的,所以 A 和 B 可能读取到的值是 29 并进入循环。
    • 因为此时 A 和 B 都已经进入循环了,所以会出现多输出一次的情况。
    • A 和 B 进入循环后,由于锁的存在,它们能够获取到正确的index的值,所以最后多输出的结果是 30 和 31。

    理解了这个错误之后,我们可以把代码稍微改一下,将index < 30这个比较操作也置于锁的保护中,就能够得到正确的结果了。

    package main
    
    import (
    	"fmt"
    	"sync"
    )
    
    var i int
    var mu sync.Mutex
    var endSignal = make(chan struct{})
    
    func threadPrint(threadNum int, threadName string) {
    	for {
    		mu.Lock()
    		if i >= 30 {
    			mu.Unlock()
    			break
    		}
    
    		if i%3 == threadNum {
    			fmt.Printf("%d: %s\n", i, threadName)
    			i++
    		}
    		mu.Unlock()
    	}
    
    	endSignal <- struct{}{}
    }
    
    func main() {
    	names := []string{"A", "B", "C"}
    
    	for idx, name := range names {
    		go threadPrint(idx, name)
    	}
    
    	for _ = range names {
    		<-endSignal
    	}
    }
    

    正确答案 V2 -- 公平锁

    上述代码是得到的结果是正确的,但是还存在一些问题。我们想要的执行顺讯是有序的, 但每次解锁的时候,都是 A, B, C 三个 Goroutine 上去抢锁资源。有时候某个 Goroutine 抢到了锁资源,但是其并不符合执行要求(i%3 != threadNum)。它就会将锁释放,然后让大家重新再来抢。

    这样的争抢索锁资源造成了时间上的浪费,执行了一些不必要的操作。

    为了避免这些浪费,我们可以参考 Java 中的公平锁,让解锁的顺序和上锁的顺序匹配,每次只有一个 Goroutine 获得锁资源,大家不必每次都去争抢锁资源。

    package main
    
    import (
    	"fmt"
    	"log"
    	"sync"
    )
    
    type FailLock struct {
    	mu        *sync.Mutex
    	cond      *sync.Cond
    	holdCount int
    }
    
    func NewFailLock() sync.Locker {
    	mu := new(sync.Mutex)
    	cond := sync.NewCond(mu)
    
    	return &FailLock{
    		holdCount: 0,
    		mu:        mu,
    		cond:      cond,
    	}
    }
    
    func (fl *FailLock) Lock() {
    	fl.mu.Lock()
    	defer fl.mu.Unlock()
    
    	fl.holdCount++
    	if fl.holdCount == 1 {
    		return
    	}
    
    	fl.cond.Wait()
    }
    
    func (fl *FailLock) Unlock() {
    	fl.mu.Lock()
    	defer fl.mu.Unlock()
    
    	if fl.holdCount == 0 {
    		log.Fatal("unlock of UnLocked mutex")
    	}
    
    	fl.holdCount--
    	if fl.holdCount != 0 {
    		fl.cond.Signal()
    	}
    }
    
    var (
    	end = make(chan struct{})
    	i   int
    )
    
    func threadPrint(threadNum int, threadName string, mu sync.Locker) {
    	for i < 30 {
    		mu.Lock()
    		if i >= 30 {
    			mu.Unlock()
    			continue
    		}
    		if i < 3 && i%3 != threadNum {
    			mu.Unlock()
    			continue
    		}
    
    		fmt.Printf("%d: %s\n", i, threadName)
    		i += 1
    		mu.Unlock()
    	}
    	end <- struct{}{}
    }
    
    func main() {
    	mu := NewFailLock()
    	names := []string{"A", "B", "C"}
    
    	for idx, name := range names {
    		go threadPrint(idx, name, mu)
    	}
    
    	for _ = range names {
    		<-end
    	}
    }
    

    上述代码中需要注意两点:

    1. 由于 Goroutine 无法保证启动顺序,即我们无法保证最开始上锁的顺序是A,B,C这样的顺序,所以需要在64~67行加一个判断,程序刚开始执行时如果获得的锁不对,就不执行任何操作,重新获得锁。
    2. 由于可见性的原因,需要在60~63行上锁之后加一个判断,保证i的值是最新的值。

    正确答案 V3 -- AtomicInt

    除了自己手动加锁外,我们也可以使用 Go 的 atomic 包中提供的原子操作来完成上述功能。 每个 Goroutine 原子性地获得i的值,如果符合i % 3 == threadNum的条件,则执行操作,否则作自旋。代码如下:

    package main
    
    import (
    	"fmt"
    	"sync/atomic"
    )
    
    var (
    	end = make(chan struct{})
    	i   int32
    )
    
    func threadPrint(threadNum int32, threadName string) {
    
    	for {
    		v := atomic.LoadInt32((*int32)(&i))
    		if v >= 30 {
    			break
    		}
    
    		if v%3 == threadNum {
    			fmt.Printf("%d: %s\n", i, threadName)
    			atomic.AddInt32((*int32)(&i), int32(1))
    		} else {
    			continue
    		}
    	}
    	end <- struct{}{}
    }
    
    func main() {
    	names := []string{"A", "B", "C"}
    
    	for idx, name := range names {
    		go threadPrint(int32(idx), name)
    	}
    
    	for _ = range names {
    		<-end
    	}
    }
    

    参考链接

    第 1 条附言  ·  2019-04-07 12:28:15 +08:00

    正确答案V4 - FanIn

    经V友 @Mark3K 的补充,还可以使用多个 channel 执行扇入(Fan In)操作,避免使用锁。

    首先说一下扇入的定义,Go blog 中是这样描述的:

    A function can read from multiple inputs and proceed until all are closed by multiplexing the input channels onto a single channel that's closed when all the inputs are closed. This is called fan-in.

    通过将多个输入 channel 多路复用到单个处理 channel 的方式,一个函数能够从多个输入 channel 中读取数据并处理。当所有的输出 channel 都关闭的时候,单个处理 channel 也会关闭。这就叫做扇入。

    在维基百科中描述的逻辑门的扇入如下(大家也可以参考这个来理解 Go 中的扇入):

    Fan-in is the number of inputs a logic gate can handle. For instance the fan-in for the AND gate shown in the figure is 3. Physical logic gates with a large fan-in tend to be slower than those with a small fan-in. This is because the complexity of the input circuitry increases the input capacitance of the device. Using logic gates with higher fan-in will help reducing the depth of a logic circuit.

    一个逻辑门将多个输入处理成一个输出,它能够处理的输入数量就叫做扇入。

    理解了扇入的概念后,上述问题的答案也呼之欲出了。我们可以为A,B,C三个 Goroutine 创建三个 channel。然后通过一个 FanIn 函数将三个 channel 的输出输入到一个 channel 中。具体代码如下:

    package main
    
    import "fmt"
    
    func gen(v string, times int) <-chan string {
    	ch := make(chan string)
    	go func() {
    		defer close(ch)
    		for i := 0; i < times; i++ {
    			ch <- v
    		}
    	}()
    	return ch
    }
    
    func fanIn(times int, inputs []<-chan string) <-chan string {
    	ch := make(chan string)
    	go func() {
    		defer close(ch)
    		for i := 0; i < times; i++ {
    			for _, input := range inputs {
    				v := <-input
    				ch <- v
    			}
    		}
    	}()
    	return ch
    }
    
    func main() {
    	times := 10
    	inputs := make([]<-chan string, 0, 3)
    	for _, K := range []string{"A", "B", "C"} {
    		inputs = append(inputs, gen(K, times))
    	}
    	for char := range fanIn(times, inputs) {
    		fmt.Println(char)
    	}
    }
    
    第 2 条附言  ·  2019-04-07 21:33:56 +08:00
    1. hjc4869 老哥说的很好,这是一个同步问题,不是互斥问题,所以应该优先使用 semaphore/channel 去解决,而不是使用锁
    2. 各位老哥都贡献了很多非常精彩的代码,有的老哥帮我支出了问题,谢谢大家。给我一点时间整理一下,到时候重新发个帖子出来。
    第 3 条附言  ·  2019-04-14 18:11:58 +08:00
    83 条回复    2019-04-16 23:22:01 +08:00
    richzhu
        1
    richzhu  
       2019-04-07 10:15:21 +08:00 via iPhone
    请教一下,为什么通道要用 struct{} 类型
    bwangel
        2
    bwangel  
    OP
       2019-04-07 10:27:55 +08:00 via Android
    @richzhu

    字面量 struct{}代表了空的结构体类型。这样的类型既不包含任何字段也没有任何方法。该类型的值所需的存储空间几乎可以忽略不计。

    因此,我们可以把这样的值作为占位值来使用。比如:在同一个应用场景下,map[int] [int]bool 类型的值占用更少的存储空间。
    JaguarJack
        3
    JaguarJack  
       2019-04-07 10:39:09 +08:00 via iPhone
    学习了 正好看到锁这里
    exiaoxing
        4
    exiaoxing  
       2019-04-07 10:44:39 +08:00 via iPhone
    好文,赞
    xylophone21
        5
    xylophone21  
       2019-04-07 10:51:02 +08:00
    这道题,感觉怪怪的。开 3 个线程,然后居然没有一点并行的需求
    Mark3K
        6
    Mark3K  
       2019-04-07 10:54:50 +08:00   ❤️ 1
    可以多开个 channel,避免加锁
    func fanIn() <-chan string{
    inCh := make(chan string)
    go func() {
    defer close(inCh)
    for i := 0; i < 10; i++{
    inCh <- aCh
    inCh <- bCh
    inCh <- cCh
    }
    }()
    return inCh
    }
    deepdark
        7
    deepdark  
       2019-04-07 10:55:46 +08:00 via Android
    学习了,赞一个
    mengzhuo
        8
    mengzhuo  
       2019-04-07 11:02:59 +08:00
    还自旋锁哈哈哈哈
    是个正常的 Go 程序员都会选择用 fan in channel 模式的
    bwangel
        9
    bwangel  
    OP
       2019-04-07 11:11:55 +08:00
    @Mark3K 可以贴一下完整代码吗?有些没太理解?

    @mengzhuo 你这样说话的态度让人很不爽,我决定把你拉黑了。
    Mark3K
        10
    Mark3K  
       2019-04-07 11:13:11 +08:00   ❤️ 1
    @bwangel
    ```go
    package main

    import "fmt"

    func gen(v string, times int) <-chan string {
    ch := make(chan string)
    go func() {
    defer close(ch)
    for i := 0; i < times; i++ {
    ch <- v
    }
    }()
    return ch
    }

    func fanIn(times int, inputs []<-chan string) <-chan string {
    ch := make(chan string)
    go func() {
    defer close(ch)
    for i := 0; i < times; i++ {
    for _, input := range inputs {
    v := <-input
    ch <- v
    }
    }
    }()
    return ch
    }

    func main() {
    times := 10
    inputs := make([]<-chan string, 0, 3)
    for _, K := range []string{"A", "B", "C"} {
    inputs = append(inputs, gen(K, times))
    }
    for i := range fanIn(times, inputs) {
    fmt.Println(i)
    }
    }

    ```
    whoisghost
        11
    whoisghost  
       2019-04-07 11:20:14 +08:00   ❤️ 1
    V3 -- AtomicInt 版本,把 names 再追加 “ D ”, "E", 把 3 => 5, 30 => 50, 还能正常运行吗?
    bwangel
        12
    bwangel  
    OP
       2019-04-07 11:24:10 +08:00
    @Mark3K 理解了,谢谢。我补充一下。
    hjc4869
        13
    hjc4869  
       2019-04-07 11:46:51 +08:00   ❤️ 1
    简单问题复杂化。整层楼没人提到 Semaphore 也是惊了。
    jadeity
        14
    jadeity  
       2019-04-07 12:06:28 +08:00
    并行无序,阻塞有序。
    需要逻辑顺序的阻塞放在主线程保证顺序,其他不需要的阻塞放在其他线程提高性能。
    不管是 channel,锁,信号还是其他什么名字,在合适的地方阻塞,把不合适的阻塞并行。
    yianing
        15
    yianing  
       2019-04-07 12:10:19 +08:00 via Android
    @hjc4869 哈哈,我看到这个问题的第一想法就是操作系统中学的信号量,read copy write
    bwangel
        16
    bwangel  
    OP
       2019-04-07 12:35:40 +08:00
    @hjc4869 我刚刚上维基百科简单看了一下 Semaphore 的定义: https://zh.wikipedia.org/wiki/%E4%BF%A1%E5%8F%B7%E9%87%8F

    感觉和我在文中写的 [正确答案 V2 – 公平锁] 的实现方式很像,可以详述一下 Semaphore 的解决方案吗?最好可以贴一些代码。
    bwangel
        17
    bwangel  
    OP
       2019-04-07 12:37:35 +08:00
    @jadeity @jadeity 嗯,感觉这才是正确使用线程 /Goroutine 的姿势。这个题现在看来感觉有些奇怪,使用线程这种并行处理方式来做一些同步的事情。可能是面试者想要考察线程同步的方式吧。
    reus
        18
    reus  
       2019-04-07 12:39:53 +08:00
    @Mark3K chan 读写一样有锁,而且开销更大……
    hjc4869
        19
    hjc4869  
       2019-04-07 12:58:39 +08:00
    @bwangel

    static void Worker(char c, int o, SemaphoreSlim wait, SemaphoreSlim signal, SemaphoreSlim finish)
    {
    for (int i = 0; i < 10; i++)
    {
    wait.Wait();
    Console.WriteLine($"{i*3+o}: {c}");
    signal.Release();
    }

    if (finish != null) finish.Release();
    }

    static void Main(string[] args)
    {
    SemaphoreSlim s1 = new SemaphoreSlim(0), s2 = new SemaphoreSlim(0), s3 = new SemaphoreSlim(0);
    SemaphoreSlim sTerm = new SemaphoreSlim(0);
    Task.Run(() => Worker('A', 0, s1, s2, null));
    Task.Run(() => Worker('B', 1, s2, s3, null));
    Task.Run(() => Worker('C', 2, s3, s1, sTerm));
    s1.Release();
    sTerm.Wait();
    }
    ngn999
        20
    ngn999  
       2019-04-07 13:02:05 +08:00
    我们部门面试也问这个问题,非 go, 是考信号量
    jadeity
        21
    jadeity  
       2019-04-07 13:38:21 +08:00
    @bwangel 用到并行就是为了减少阻塞,并行同步就是要阻塞。如何挑选阻塞的时机,如何更优雅更有效率的阻塞,不管怎么问,都是在加上更多限制的条件下解决这个问题。
    liyunlong41
        22
    liyunlong41  
       2019-04-07 13:43:06 +08:00 via iPhone
    技术贴 赞一个 之前刚好看到了 go 不满足内存一致性模型,不理解,现在稍微理解了点
    art2cat
        23
    art2cat  
       2019-04-07 13:48:48 +08:00
    写的很好,但是你确定不是 fairlock 吗?
    whoisghost
        24
    whoisghost  
       2019-04-07 14:03:55 +08:00
    @whoisghost 楼主呀,看下我这评论呀,解法 3 是不是有问题?
    bwangel
        25
    bwangel  
    OP
       2019-04-07 14:31:11 +08:00
    @art2cat 哇,谢谢老哥提醒。尴尬了,手滑打错了。
    lazyfighter
        26
    lazyfighter  
       2019-04-07 14:52:17 +08:00
    在 go 语言入门的时候我记得有本书写的是能用锁的时候尽量用锁,因为 channel 还是依赖锁进行实现的
    reus
        27
    reus  
       2019-04-07 15:01:13 +08:00
    @hjc4869 像你这样写的话,go 也不需要信号量。所以没人提信号量。

    <script src="https://gist.github.com/reusee/57f30d177a688365e78ee9a12dac4468.js"></script>
    georgetso
        28
    georgetso  
       2019-04-07 15:34:31 +08:00
    @ngn999 这就有意思了, 我怎么觉得这个问题和信号量没啥关系呢? 能详细说说为什么是考信号量吗?
    hjc4869
        29
    hjc4869  
       2019-04-07 16:21:46 +08:00   ❤️ 1
    @reus 这就是把 channel 当 semaphore 用……
    而且 channel 本身实现用了 mutex,mutex 底层又是 semaphore,一层层包上来不如直接用 semaphore 直观。
    Coey
        30
    Coey  
       2019-04-07 16:22:56 +08:00 via Android
    归根结底是个并行无序转为串行有序的问题,遇到这种问题我一般是觉得没什么意思
    当你不真正需要并行的时候,就不要用并行
    另外,我认为用 FanIn/FanOut 和其他的几个解法并不是完全等价的,原因在于它对标准输出做了串行
    应该有人见过多线程环境写文件导致文件混乱的吧,噗
    hjc4869
        31
    hjc4869  
       2019-04-07 16:39:30 +08:00   ❤️ 1
    @georgetso 这个问题本质上是在实现同步,而不是互斥。同步强调的是做事的先后顺序而不是多线程访问资源的冲突。虽然二者是包含关系并且可以互相实现,但是如果这里第一眼看到题就只是想到用 lock/mutex 而不是 semaphore/channel 去实现,那么显然是对后者的应用不熟,面试要挂的……
    Lpl
        32
    Lpl  
       2019-04-07 16:56:11 +08:00
    @lazyfighter 怕是在开玩笑吧?你写一个两个 goroutine 同步的程序,channel 比 mutex 快至少一倍。
    georgetso
        33
    georgetso  
       2019-04-07 17:00:04 +08:00
    @hjc4869 我同意你的分析, 这不是关于互斥的问题而是关于 happens-before 的问题. 但似乎 semaphore 是为了做资源控制而不是顺序同步吧?
    hjc4869
        34
    hjc4869  
       2019-04-07 17:13:34 +08:00
    @georgetso Semaphore 是一种同步的手段,可以用来做很多事情。你说的资源控制是一种用途(限制 N 个并发访问),我说的用来等待 /唤醒 thread 也是一个用途。
    georgetso
        35
    georgetso  
       2019-04-07 17:18:58 +08:00
    @hjc4869 是的, 等待唤醒是这个题目的点. 我会用 condition_variable, 逻辑上更合理.
    whoisghost
        36
    whoisghost  
       2019-04-07 17:31:05 +08:00   ❤️ 1
    鉴于提示楼主“正确”解法 3 有问题两次被无视,为了避免其他人被楼主误导,本人只好替楼主修正所谓的“正确”解法 3:
    Lpl
        37
    Lpl  
       2019-04-07 17:59:23 +08:00
    感觉我这个版本会更加简洁一点,本质上就是一个同步的问题。另外,mutex 和 channel 之间性能其实是有很大差别的,golang 的并发通信模型是“通信同步”( CSP )。mutex 就是单纯的一个互斥锁。

    https://gist.github.com/penglongli/47395e7e75472a7da92787f3eb8e947d

    ```
    var (
    num = 10
    )

    func main() {
    sig := make(chan int)
    c1 := make(chan string)
    c2 := make(chan string)
    c3 := make(chan string)

    var wg sync.WaitGroup
    wg.Add(3)

    go print(&wg, c1, "A")
    go print(&wg, c2, "B")
    go print(&wg, c3, "C")
    go func() {
    for {
    select {
    case <-sig:
    // 检测到 sig 信号后退出 goroutine,避免出现 Deadlock
    return
    case str := <- c1: {
    fmt.Println(str)
    str = <- c2
    fmt.Println(str)
    str = <- c3
    fmt.Println(str)
    }
    }
    }
    }()
    wg.Wait()
    sig <- 1
    }

    func print(wg *sync.WaitGroup, c chan string, str string) {
    defer wg.Done()

    for i := 0; i < num; i++ {
    c <- str
    }
    }
    ```
    Lpl
        38
    Lpl  
       2019-04-07 18:02:26 +08:00
    这道题目有好多种解法,我又想到了那个很“经典”的睡眠排序了,用在这里很切题。。
    29EtwXn6t5wgM3fD
        39
    29EtwXn6t5wgM3fD  
       2019-04-07 18:15:32 +08:00
    经典的使用信号量实现前驱关系的题目啊。
    gamexg
        40
    gamexg  
       2019-04-07 18:19:11 +08:00
    @whoisghost #36 即使加了 gosched 面试时也够呛打及格分数。
    whoisghost
        41
    whoisghost  
       2019-04-07 19:03:41 +08:00
    @gamexg 嗯。至少是正确的。
    tairan2006
        42
    tairan2006  
       2019-04-07 19:16:44 +08:00   ❤️ 2
    这个就是并行输出串行化…用锁写很浪费 cpu 时间或者写出惊群代码呀。

    这个扇出的代码也有问题,题目要求是在各自线程里面输出,你要是这么写,不如直接从主协程里面按顺序从管道里面拿数据,更省事。我也手痒写了个玩。

    https://gist.github.com/YiuTerran/f39064e3aa2152c64503a616725a65d9
    index90
        43
    index90  
       2019-04-07 19:28:57 +08:00
    ```
    package main

    import "fmt"

    type Message struct {
    msg string
    ch chan bool
    }

    func T(msg string) chan Message {
    w := make(chan bool)
    c := make(chan Message)
    go func(){
    defer close(c)
    for i:=0;i<10;i++ {
    c <- Message{msg:msg, ch:w}
    <-w
    }
    }()
    return c
    }

    func main() {
    A := T("A")
    B := T("B")
    C := T("C")
    for i:=0;i<10;i++ {
    a := <-A;fmt.Println(a.msg)
    b := <-B;fmt.Println(b.msg)
    c := <-C;fmt.Println(c.msg)
    a.ch <- true
    b.ch <- true
    c.ch <- true
    }
    }
    ```
    出自油管[19:21] :
    index90
        44
    index90  
       2019-04-07 19:31:01 +08:00
    补充一下,在主线程打印有点作弊,如果在子线程中打印,应该才是题目本意?
    Lpl
        45
    Lpl  
       2019-04-07 20:25:47 +08:00
    没认真审题,把代码改成了单向循环链表。每个协程判断上一层的信号量 signal,接收到就打印当前节点。

    https://gist.github.com/penglongli/7f8eaee1fdec19e55097bb1d041dcac3
    bwangel
        46
    bwangel  
    OP
       2019-04-07 20:51:28 +08:00
    @whoisghost #35

    老哥抱歉,不知道啥时候把你 block 了。所以一直没看到你的评论。

    你指出的这个问题非常对,我把数量改成 5/50 后。程序就会阻塞,请问这是为什么啊,有些没太理解。
    reus
        47
    reus  
       2019-04-07 20:58:11 +08:00
    @hjc4869 你可以用“信号量”来理解,但别人未必需要。原帖 ( https://www.v2ex.com/t/547045 )几个 go 的实现,都没人提到“信号量”。
    chan 还可以传递额外的信息,如果线程间不仅仅是同步而是需要传递一些数据,那单靠 semaphore 就无能为力了。go 运行时实现的 semaphore,是没有暴露到标准库的,所以没有”直接用 semaphore ”这个可选项。
    realityone
        48
    realityone  
       2019-04-07 21:41:46 +08:00
    @bwangel

    $ GOMAXPROCS=10 go run main.go
    bwangel
        49
    bwangel  
    OP
       2019-04-07 21:47:55 +08:00
    @realityone 嗯,找到了一篇相关的文章,还在研读

    http://www.sarathlakshman.com/2016/06/15/pitfall-of-golang-scheduler
    tonywangcn
        50
    tonywangcn  
       2019-04-07 21:58:56 +08:00
    @bwangel 在 go version go1.10.3 darwin/amd64 状态下,你的代码是没有问题的。https://stackoverflow.com/questions/13107958/what-exactly-does-runtime-gosched-do
    index90
        51
    index90  
       2019-04-07 22:04:57 +08:00
    package main

    import "fmt"

    func T(msg string) chan struct{} {
    ch := make(chan struct{})
    go func() {
    defer close(ch)
    for i:=0;i<10;i++ {
    <-ch
    fmt.Println(msg)
    ch<- struct{}{}
    }
    }()
    return ch
    }

    func main() {
    A := T("A")
    B := T("B")
    C := T("C")
    t := struct{}{}
    for ; ; {
    A <- t
    B <- <- A
    C <- <- B
    t = <- C
    }
    }
    myself659
        52
    myself659  
       2019-04-07 22:24:25 +08:00
    https://gist.github.com/myself659/8fd9af077add584ec7ba0a0f86bce3b5

    一个 channel 搞定

    更多 channel 特性 参考一下这篇文章

    https://zhuanlan.zhihu.com/p/26393117
    tairan2006
        53
    tairan2006  
       2019-04-07 22:33:30 +08:00
    @bwangel @tonywangcn V3 答案协程是个无阻塞的死循环啊,CPU 根本不会让渡出去…所以只能手动让出了,这个实现本身是错误的…能跑几个取决于你的 CPU 核数。

    如果说同步原语的话,这题用条件变量或者信号量都可以。不过对于 golang 而言,channel 就是它的同步原语,很多时候并不一定非要用更底层的东西(过早优化是万恶之源 2333
    index90
        54
    index90  
       2019-04-07 22:34:27 +08:00
    @myself659
    编写一个程序,开启 3 个线程 A,B,C,这三个线程的输出分别为 A、B、C,每个线程将自己的 输出在屏幕上打印 10 遍,要求输出的结果必须按顺序显示。如:ABCABCABC....

    关键点:
    1. 3 个线程
    2. 每个线程将自己的输出打印
    3. 每个线程都打印 10 遍

    所以我说,在 main 中 for 10 次,或者在 main 中打印,都应该算作弊
    tairan2006
        55
    tairan2006  
       2019-04-07 22:38:24 +08:00
    @myself659 大哥,人家只让创建 3 个线程…你创建 30 个协程不怕被面试官打死么
    ethego
        56
    ethego  
       2019-04-07 22:45:40 +08:00
    一个读写锁竟然能说这么啰嗦。。真理往往是简洁的
    ```go
    package main

    import (
    "fmt"
    "sync"
    )

    var mu sync.RWMutex
    var index int
    var endSignal = make(chan struct{})

    func echoRoutine(routineIndex int, routineName string) {
    for {
    mu.RLock()
    i := index
    mu.RUnlock()

    if i >= 30 {
    break
    }

    if i % 3 == routineIndex {
    fmt.Println(i, routineName)
    mu.Lock()
    index++
    mu.Unlock()
    }
    }

    endSignal <- struct{}{}
    }

    func main() {
    routineNames := []string{"A", "B", "C"}

    for idx, name := range routineNames {
    go echoRoutine(idx, name)
    }

    for _ = range routineNames {
    <-endSignal
    }
    }
    ```
    tairan2006
        57
    tairan2006  
       2019-04-07 22:53:45 +08:00
    @tonywangcn 哦,我刚看了一下,go 后面改了调度方式,现在实现了非协作式抢占,所以新版本应该是饿不死了。

    不过,感觉还是会被面试官毙掉(
    myself659
        58
    myself659  
       2019-04-07 23:05:28 +08:00
    georgetso
        59
    georgetso  
       2019-04-07 23:10:35 +08:00
    @ethego 太暴力了
    myself659
        60
    myself659  
       2019-04-07 23:35:14 +08:00
    myself659
        61
    myself659  
       2019-04-07 23:36:52 +08:00
    @tairan2006
    看上一楼 gist 流式处理
    tairan2006
        62
    tairan2006  
       2019-04-07 23:48:31 +08:00
    @myself659 Emmm …虽然思路是大体一样的,还是建议你看一下我 42 楼写的代码…因为你这个编程风格可能会让面试官感觉有点不满。。
    ethego
        63
    ethego  
       2019-04-08 00:38:56 +08:00
    @georgetso 不懂你说暴力是什么意思,用锁的正确写法就是这样。
    cokeboL
        64
    cokeboL  
       2019-04-08 02:06:47 +08:00
    package main

    import (
    "fmt"
    "github.com/temprory/util"
    "sync"
    )

    func main() {
    wg := sync.WaitGroup{}
    cl := util.NewCorsLink("test", 10, 3)
    for i := 0; i < 30; i++ {
    idx := i
    wg.Add(1)
    cl.Go(func(task *util.LinkTask) {
    defer wg.Done()

    task.WaitPre()
    if idx%3 == 0 {
    fmt.Println("A")
    } else if idx%3 == 1 {
    fmt.Println("B")
    } else {
    fmt.Println("C")
    }

    task.Done(nil)
    })
    }
    wg.Wait()
    cl.Stop()
    }
    ShayneWang
        65
    ShayneWang  
       2019-04-08 09:21:58 +08:00
    插眼
    findTheWay
        66
    findTheWay  
       2019-04-08 09:43:54 +08:00
    技术贴
    georgetso
        67
    georgetso  
       2019-04-08 11:02:59 +08:00
    @ethego 略有异议. 该方案的确实现了既定目标, 但 cpu 空转有些过分了. 简单任务你这么写没关系, 如果是计算密集型系统, 这么写是过不了 review 的.
    Gea
        68
    Gea  
       2019-04-08 11:23:39 +08:00
    仔细看一下
    ethego
        69
    ethego  
       2019-04-08 14:25:52 +08:00
    @georgetso 什么简单不简单任务,题目的要求都清晰地摆在这里了,就不要去假设什么需求。另外这道题用原子操作并不会比上锁省多少时间,别意淫,你写出来做 benchmark 就知道了。
    ethego
        70
    ethego  
       2019-04-08 14:33:05 +08:00
    @georgetso 另外你还要再学习一个。我虽然写了 for {} 但是并没有什么 CPU 空转,mutex 没有抢到锁会阻塞等待释放,这是基础知识。
    georgetso
        71
    georgetso  
       2019-04-08 16:17:48 +08:00
    @ethego 这倒是有趣了. 该学习的我虚心学习, 不过我尝试在
    mu.RLock()
    这一句上面添加
    counter++ // (先定义一个全局变量 var counter = 0)
    fmt.Println(counter)
    然后发现打印了 500 多行. 最后几行是:
    521
    522
    523
    524
    486
    29 C
    526
    525
    518

    如果 cpu 没有空转, 那不应该跑 500 多句 println 吧?
    请赐教!
    georgetso
        72
    georgetso  
       2019-04-08 16:21:38 +08:00
    @ethego 我认真学习一个后, 认为贵码能完成任务, 主要还是靠关键的三句
    mu.Lock()
    index++
    mu.Unlock()
    放在了 if 中. 这个 if 没有 else, 不过如果你把我上面回帖中的 ++ 和 print 放在这个 else 里, 就会发现 mutex 其实被抢到了 500 多次, 毕竟这是“读写锁”, 这是“基础知识”.
    再请赐教!
    hheedat
        73
    hheedat  
       2019-04-08 16:27:38 +08:00
    @ethego 抢到的情况不就空转了
    exonuclease
        74
    exonuclease  
       2019-04-08 17:46:38 +08:00
    我当时实现的 c++版本是每个线程用自己的计数器来判断是否退出的
    atomic_int counter = 0;
    const vector<char> letters = { 'A','B','C' };
    void worker(int target) {
    int local_counter = 0;
    while (local_counter < 10)
    {
    if (counter.load() % 3 == target) {
    cout << letters[target] << endl;
    ++counter;
    ++local_counter;
    }
    }
    }

    int main()
    {
    thread a(worker, 0);
    thread b(worker, 1);
    thread c(worker, 2);
    a.join();
    b.join();
    c.join();
    return 0;
    }
    ethego
        75
    ethego  
       2019-04-08 18:52:29 +08:00
    @georgetso 当然我有误解你说的空转。不过对于这道题,你说的那点抢占开销比什么公平锁快多了。你自己动手 benchmark 试下就知道了,为了解决抢占的开销远比抢占本身大。
    hheedat
        76
    hheedat  
       2019-04-12 15:59:46 +08:00
    楼主,V2 公平锁这里有个错误,贴出我的一次执行结果


    ```
    0: A
    1: B
    2: C
    3: B
    4: A
    5: C
    6: B
    7: A
    8: C
    9: B
    10: A
    11: C
    12: B
    13: A
    14: C
    15: B
    16: A
    17: C
    18: B
    19: A
    20: C
    21: B
    22: A
    23: C
    24: B
    25: A
    26: C
    27: B
    28: A
    29: C
    ```


    原因在于 ```if i < 3 && i%3 != threadNum {``` 这里



    应该把 i<3 这个条件去掉,你这里加这个是为了保证第一轮按照 ABC 输出,所以只在 i<3 的时候校验了,但是后面的也应该全部校验。因为即使没有收到条件变量的通知,调用其方法的 goroutine 也是有可能被唤醒的。
    hheedat
        77
    hheedat  
       2019-04-12 16:53:48 +08:00
    func threadPrint(threadNum int, threadName string, mu sync.Locker) {
    for i < 9 {
    fmt.Println("......", threadNum, threadName, "S-1")
    mu.Lock()
    if i >= 9 {
    mu.Unlock()
    continue
    }
    if i < 3 && i%3 != threadNum {
    fmt.Println("......", threadNum, threadName, "S-2")
    mu.Unlock()
    continue
    }

    fmt.Printf("%d: %s\n", i, threadName)
    i += 1
    fmt.Println("......", threadNum, threadName, "S-3")
    mu.Unlock()
    }
    end <- struct{}{}
    }

    ...... 0 A S-1
    0: A
    ...... 0 A S-3
    ...... 0 A S-1
    ...... 0 A S-2
    ...... 0 A S-1
    ...... 0 A S-2
    ...... 2 C S-1
    ...... 1 B S-1
    ...... 2 C S-2
    ...... 2 C S-1
    1: B
    ...... 1 B S-3
    ...... 1 B S-1
    2: C
    ...... 2 C S-3
    ...... 2 C S-1
    ...... 0 A S-1
    3: B
    ...... 1 B S-3
    ...... 1 B S-1
    4: C
    ...... 2 C S-3
    ...... 2 C S-1
    5: A
    ...... 0 A S-3
    ...... 0 A S-1
    6: B
    ...... 1 B S-3
    ...... 1 B S-1
    7: C
    ...... 2 C S-3
    ...... 2 C S-1
    8: A
    ...... 0 A S-3


    打印一些状态可以看出一些端倪
    hheedat
        78
    hheedat  
       2019-04-12 17:15:29 +08:00
    https://golang.org/pkg/sync/#Cond.Wait
    其实还有一个问题,把 sync.Wait 用 defer 这么封装是否会有问题? wait 在阻塞的时候会先解锁,唤醒的时候会先加锁,现在唤醒之后立马就释放锁了,相当于锁的是 fl.holdCount,而不是 i,这样可能会出问题吧,i++的时候
    bwangel
        79
    bwangel  
    OP
       2019-04-14 17:23:21 +08:00
    @hheedat 你好,感谢你的回复,你反馈的问题确实存在。出现`BAC`的原因是这样的(为了格式更好看一些,我把内容写在了 Gist 上,希望你拥有 跨越长城 的能力):

    https://gist.github.com/bwangelme/1d204647f4658007043f348a61f37936

    你说的第二个问题,`i` 确实没有被 mutex 保护。但是由于每个 Goroutine 执行 `i++` 的时候都会首先获取 `holdCount` 的值,如果 holdCount 的值不为 1,那么这个 Goroutine 就会阻塞。所以可以确保同一时刻只会有一个 Goroutine 执行 `i++`
    bwangel
        80
    bwangel  
    OP
       2019-04-14 18:11:37 +08:00
    @mengzhuo 老哥,默默地把你取消拉黑了。后来发现你吐槽的是对的,这个问题不能用锁解决。
    hheedat
        81
    hheedat  
       2019-04-15 09:54:26 +08:00   ❤️ 1
    @bwangel
    “你说的第二个问题,`i` 确实没有被 mutex 保护。但是由于每个 Goroutine 执行 `i++` 的时候都会首先获取 `holdCount` 的值,如果 holdCount 的值不为 1,那么这个 Goroutine 就会阻塞。所以可以确保同一时刻只会有一个 Goroutine 执行 `i++`”


    不能,因为阻塞的 goroutine 可能会被误唤醒
    bwangel
        82
    bwangel  
    OP
       2019-04-15 10:51:00 +08:00 via Android
    @hheedat 嗯,对,我的 unlock 有些问题,wait 应该放到 for 循环中
    bwangel
        83
    bwangel  
    OP
       2019-04-16 23:22:01 +08:00
    @hheedat 这是修改后的代码,锁里面还是需要两个变量 holdCount 和 isHold

    https://gist.github.com/bwangelme/44f0edb469733bf9bac86bbc96faf037
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3503 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 36ms · UTC 10:26 · PVG 18:26 · LAX 02:26 · JFK 05:26
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.