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

[bwangel]

说明

前两天看到了这个帖子，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
	}
}

参考链接

• 一条经典面试题引发的思考
• Memory barrier -- Wikipedia
• 什么是 Java 中的公平锁？
• The Go Memory Model
• GoLang 内存模型
• go reentrant lock(可重入锁) 简单实现

正确答案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)
	}
}

1. hjc4869 老哥说的很好，这是一个同步问题，不是互斥问题，所以应该优先使用 semaphore/channel 去解决，而不是使用锁
2. 各位老哥都贡献了很多非常精彩的代码，有的老哥帮我支出了问题，谢谢大家。给我一点时间整理一下，到时候重新发个帖子出来。

修正版本

https://www.v2ex.com/t/555049#reply0

[richzhu]

请教一下，为什么通道要用 struct{} 类型

[bwangel]

@richzhu

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

因此，我们可以把这样的值作为占位值来使用。比如：在同一个应用场景下，map[int] [int]bool 类型的值占用更少的存储空间。

[JaguarJack]

学习了 正好看到锁这里

[exiaoxing]

好文，赞

[xylophone21]

这道题，感觉怪怪的。开 3 个线程，然后居然没有一点并行的需求

[Mark3K]

可以多开个 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]

学习了，赞一个

[mengzhuo]

还自旋锁哈哈哈哈
是个正常的 Go 程序员都会选择用 fan in channel 模式的

[bwangel]

@Mark3K 可以贴一下完整代码吗？有些没太理解？

@mengzhuo 你这样说话的态度让人很不爽，我决定把你拉黑了。

[Mark3K]

@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]

V3 -- AtomicInt 版本，把 names 再追加 “ D ”, "E", 把 3 => 5, 30 => 50, 还能正常运行吗？

[bwangel]

@Mark3K 理解了，谢谢。我补充一下。

[hjc4869]

简单问题复杂化。整层楼没人提到 Semaphore 也是惊了。

[jadeity]

并行无序，阻塞有序。
需要逻辑顺序的阻塞放在主线程保证顺序，其他不需要的阻塞放在其他线程提高性能。
不管是 channel，锁，信号还是其他什么名字，在合适的地方阻塞，把不合适的阻塞并行。

[yianing]

@hjc4869 哈哈，我看到这个问题的第一想法就是操作系统中学的信号量，read copy write

[bwangel]

@hjc4869 我刚刚上维基百科简单看了一下 Semaphore 的定义： https://zh.wikipedia.org/wiki/%E4%BF%A1%E5%8F%B7%E9%87%8F

感觉和我在文中写的 [正确答案 V2 – 公平锁] 的实现方式很像，可以详述一下 Semaphore 的解决方案吗？最好可以贴一些代码。

[bwangel]

@jadeity @jadeity 嗯，感觉这才是正确使用线程 /Goroutine 的姿势。这个题现在看来感觉有些奇怪，使用线程这种并行处理方式来做一些同步的事情。可能是面试者想要考察线程同步的方式吧。

[reus]

@Mark3K chan 读写一样有锁，而且开销更大……

[hjc4869]

@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]

我们部门面试也问这个问题，非 go, 是考信号量

[jadeity]

@bwangel 用到并行就是为了减少阻塞，并行同步就是要阻塞。如何挑选阻塞的时机，如何更优雅更有效率的阻塞，不管怎么问，都是在加上更多限制的条件下解决这个问题。

[liyunlong41]

技术贴 赞一个 之前刚好看到了 go 不满足内存一致性模型，不理解，现在稍微理解了点

[art2cat]

写的很好，但是你确定不是 fairlock 吗？

[whoisghost]

@whoisghost 楼主呀，看下我这评论呀，解法 3 是不是有问题？

[bwangel]

@art2cat 哇，谢谢老哥提醒。尴尬了，手滑打错了。

[lazyfighter]

在 go 语言入门的时候我记得有本书写的是能用锁的时候尽量用锁，因为 channel 还是依赖锁进行实现的

[reus]

@hjc4869 像你这样写的话，go 也不需要信号量。所以没人提信号量。

<script src="https://gist.github.com/reusee/57f30d177a688365e78ee9a12dac4468.js"></script>

[georgetso]

@ngn999 这就有意思了, 我怎么觉得这个问题和信号量没啥关系呢? 能详细说说为什么是考信号量吗?

[hjc4869]

@reus 这就是把 channel 当 semaphore 用……
而且 channel 本身实现用了 mutex，mutex 底层又是 semaphore，一层层包上来不如直接用 semaphore 直观。

[Coey]

归根结底是个并行无序转为串行有序的问题,遇到这种问题我一般是觉得没什么意思
当你不真正需要并行的时候,就不要用并行
另外,我认为用 FanIn/FanOut 和其他的几个解法并不是完全等价的,原因在于它对标准输出做了串行
应该有人见过多线程环境写文件导致文件混乱的吧,噗

[hjc4869]

@georgetso 这个问题本质上是在实现同步，而不是互斥。同步强调的是做事的先后顺序而不是多线程访问资源的冲突。虽然二者是包含关系并且可以互相实现，但是如果这里第一眼看到题就只是想到用 lock/mutex 而不是 semaphore/channel 去实现，那么显然是对后者的应用不熟，面试要挂的……

[Lpl]

@lazyfighter 怕是在开玩笑吧？你写一个两个 goroutine 同步的程序，channel 比 mutex 快至少一倍。

[georgetso]

@hjc4869 我同意你的分析, 这不是关于互斥的问题而是关于 happens-before 的问题. 但似乎 semaphore 是为了做资源控制而不是顺序同步吧?

[hjc4869]

@georgetso Semaphore 是一种同步的手段，可以用来做很多事情。你说的资源控制是一种用途（限制 N 个并发访问），我说的用来等待 /唤醒 thread 也是一个用途。

[georgetso]

@hjc4869 是的, 等待唤醒是这个题目的点. 我会用 condition_variable, 逻辑上更合理.

[whoisghost]

鉴于提示楼主“正确”解法 3 有问题两次被无视，为了避免其他人被楼主误导，本人只好替楼主修正所谓的“正确”解法 3：

[Lpl]

感觉我这个版本会更加简洁一点，本质上就是一个同步的问题。另外，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]

这道题目有好多种解法，我又想到了那个很“经典”的睡眠排序了，用在这里很切题。。

[29EtwXn6t5wgM3fD]

经典的使用信号量实现前驱关系的题目啊。

[gamexg]

@whoisghost #36 即使加了 gosched 面试时也够呛打及格分数。

[whoisghost]

@gamexg 嗯。至少是正确的。

[tairan2006]

这个就是并行输出串行化…用锁写很浪费 cpu 时间或者写出惊群代码呀。

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

https://gist.github.com/YiuTerran/f39064e3aa2152c64503a616725a65d9

[index90]

```
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]

补充一下，在主线程打印有点作弊，如果在子线程中打印，应该才是题目本意？

[Lpl]

没认真审题，把代码改成了单向循环链表。每个协程判断上一层的信号量 signal，接收到就打印当前节点。

https://gist.github.com/penglongli/7f8eaee1fdec19e55097bb1d041dcac3

[bwangel]

@whoisghost #35

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

你指出的这个问题非常对，我把数量改成 5/50 后。程序就会阻塞，请问这是为什么啊，有些没太理解。

[reus]

@hjc4869 你可以用“信号量”来理解，但别人未必需要。原帖 （ https://www.v2ex.com/t/547045 ）几个 go 的实现，都没人提到“信号量”。
chan 还可以传递额外的信息，如果线程间不仅仅是同步而是需要传递一些数据，那单靠 semaphore 就无能为力了。go 运行时实现的 semaphore，是没有暴露到标准库的，所以没有”直接用 semaphore ”这个可选项。

[realityone]

@bwangel

$ GOMAXPROCS=10 go run main.go

[bwangel]

@realityone 嗯，找到了一篇相关的文章，还在研读

http://www.sarathlakshman.com/2016/06/15/pitfall-of-golang-scheduler

[tonywangcn]

@bwangel 在 go version go1.10.3 darwin/amd64 状态下，你的代码是没有问题的。https://stackoverflow.com/questions/13107958/what-exactly-does-runtime-gosched-do

[index90]

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]

https://gist.github.com/myself659/8fd9af077add584ec7ba0a0f86bce3b5

一个 channel 搞定

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

https://zhuanlan.zhihu.com/p/26393117

[tairan2006]

@bwangel @tonywangcn V3 答案协程是个无阻塞的死循环啊，CPU 根本不会让渡出去…所以只能手动让出了，这个实现本身是错误的…能跑几个取决于你的 CPU 核数。

如果说同步原语的话，这题用条件变量或者信号量都可以。不过对于 golang 而言，channel 就是它的同步原语，很多时候并不一定非要用更底层的东西（过早优化是万恶之源 2333

[index90]

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

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

所以我说，在 main 中 for 10 次，或者在 main 中打印，都应该算作弊

[tairan2006]

@myself659 大哥，人家只让创建 3 个线程…你创建 30 个协程不怕被面试官打死么

[ethego]

一个读写锁竟然能说这么啰嗦。。真理往往是简洁的
```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]

@tonywangcn 哦，我刚看了一下，go 后面改了调度方式，现在实现了非协作式抢占，所以新版本应该是饿不死了。

不过，感觉还是会被面试官毙掉（

[myself659]

这个方案更好

https://gist.github.com/myself659/161e6310b485e2b08b352a9305349deb

[georgetso]

@ethego 太暴力了

[myself659]

@tairan2006 没有好好看题

看这个
https://gist.github.com/myself659/398710463292b625a62d938a85988979

[myself659]

@tairan2006
看上一楼 gist 流式处理

[tairan2006]

@myself659 Emmm …虽然思路是大体一样的，还是建议你看一下我 42 楼写的代码…因为你这个编程风格可能会让面试官感觉有点不满。。

[ethego]

@georgetso 不懂你说暴力是什么意思，用锁的正确写法就是这样。

[cokeboL]

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]

插眼

[findTheWay]

技术贴

[georgetso]

@ethego 略有异议. 该方案的确实现了既定目标, 但 cpu 空转有些过分了. 简单任务你这么写没关系, 如果是计算密集型系统, 这么写是过不了 review 的.

[Gea]

仔细看一下

[ethego]

@georgetso 什么简单不简单任务，题目的要求都清晰地摆在这里了，就不要去假设什么需求。另外这道题用原子操作并不会比上锁省多少时间，别意淫，你写出来做 benchmark 就知道了。

[ethego]

@georgetso 另外你还要再学习一个。我虽然写了 for {} 但是并没有什么 CPU 空转，mutex 没有抢到锁会阻塞等待释放，这是基础知识。

[georgetso]

@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]

@ethego 我认真学习一个后, 认为贵码能完成任务, 主要还是靠关键的三句
mu.Lock()
index++
mu.Unlock()
放在了 if 中. 这个 if 没有 else, 不过如果你把我上面回帖中的 ++ 和 print 放在这个 else 里, 就会发现 mutex 其实被抢到了 500 多次, 毕竟这是“读写锁”, 这是“基础知识”.
再请赐教!

[hheedat]

@ethego 抢到的情况不就空转了

[exonuclease]

我当时实现的 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]

@georgetso 当然我有误解你说的空转。不过对于这道题，你说的那点抢占开销比什么公平锁快多了。你自己动手 benchmark 试下就知道了，为了解决抢占的开销远比抢占本身大。

[hheedat]

楼主，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]

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]

https://golang.org/pkg/sync/#Cond.Wait
其实还有一个问题，把 sync.Wait 用 defer 这么封装是否会有问题？ wait 在阻塞的时候会先解锁，唤醒的时候会先加锁，现在唤醒之后立马就释放锁了，相当于锁的是 fl.holdCount，而不是 i，这样可能会出问题吧，i++的时候

[bwangel]

@hheedat 你好，感谢你的回复，你反馈的问题确实存在。出现`BAC`的原因是这样的（为了格式更好看一些，我把内容写在了 Gist 上，希望你拥有 跨越长城 的能力）：

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

你说的第二个问题，`i` 确实没有被 mutex 保护。但是由于每个 Goroutine 执行 `i++` 的时候都会首先获取 `holdCount` 的值，如果 holdCount 的值不为 1,那么这个 Goroutine 就会阻塞。所以可以确保同一时刻只会有一个 Goroutine 执行 `i++`

[bwangel]

@mengzhuo 老哥，默默地把你取消拉黑了。后来发现你吐槽的是对的，这个问题不能用锁解决。

[hheedat]

@bwangel
“你说的第二个问题，`i` 确实没有被 mutex 保护。但是由于每个 Goroutine 执行 `i++` 的时候都会首先获取 `holdCount` 的值，如果 holdCount 的值不为 1,那么这个 Goroutine 就会阻塞。所以可以确保同一时刻只会有一个 Goroutine 执行 `i++`”


不能，因为阻塞的 goroutine 可能会被误唤醒

[bwangel]

@hheedat 嗯，对，我的 unlock 有些问题，wait 应该放到 for 循环中

[bwangel]

@hheedat 这是修改后的代码，锁里面还是需要两个变量 holdCount 和 isHold

https://gist.github.com/bwangelme/44f0edb469733bf9bac86bbc96faf037