golang select-case 实现机制

Posted 2018-05-19 19:21 +0800 by ZhangJie ‐ 2 min read

1 chan操作规则 #

在介绍select-case实现机制之前，最好先了解下chan操作规则，明白goroutine何时阻塞，又在什么时机被唤醒，这对后续理解select-case实现有帮助。所以接下来先介绍chan操作规则，然后再介绍select-case的实现。

1.1 chan操作规则1 ##

当一个goroutine要从一个non-nil & non-closed chan上接收数据时，goroutine首先会去获取chan上的锁，然后执行如下操作直到某个条件被满足：

1）如果chan上的value buffer不空，这也意味着chan上的recv goroutine queue也一定是空的，该接收goroutine将从value buffer中unshift出一个value。这个时候，如果send goroutine队列不空的情况下，因为刚才value buffer中空出了一个位置，有位置可写，所以这个时候会从send goroutine queue中unshift出一个发送goroutine并让其恢复执行，让其执行把数据写入chan的操作，实际上是恢复该发送该goroutine执行，并把该发送goroutine要发送的数据push到value buffer中。然后呢，该接收goroutine也拿到了数据了，就继续执行。这种情景，channel的接收操作称为non-blocking操作。

2）另一种情况，如果value buffer是空的，但是send goroutine queue不空，这种情况下，该chan一定是unbufferred chan，不然value buffer肯定有数据嘛，这个时候接收goroutine将从send goroutine queue中unshift出一个发送goroutine，并将该发送goroutine要发送的数据接收过来（两个goroutine一个有发送数据地址，一个有接收数据地址，拷贝过来就ok），然后这个取出的发送goroutine将恢复执行，这个接收goroutine也可以继续执行。这种情况下，chan接收操作也是non-blocking操作。

3）另一种情况，如果value buffer和send goroutine queue都是空的，没有数据可接收，将把该接收goroutine push到chan的recv goroutine queue，该接收goroutine将转入blocking状态，什么时候恢复期执行呢，要等到有一个goroutine尝试向chan发送数据的时候了。这种场景下，chan接收操作是blocking操作。

1.2 chan操作规则2 ##

当一个goroutine常识向一个non-nil & non-closed chan发送数据的时候，该goroutine将先尝试获取chan上的锁，然后执行如下操作直到满足其中一种情况。

1）如果chan的recv goroutine queue不空，这种情况下，value buffer一定是空的。发送goroutine将从recv goroutine queue中unshift出一个recv goroutine，然后直接将自己要发送的数据拷贝到该recv goroutine的接收地址处，然后恢复该recv goroutine的运行，当前发送goroutine也继续执行。这种情况下，chan send操作是non-blocking操作。

2）如果chan的recv goroutine queue是空的，并且value buffer不满，这种情况下，send goroutine queue一定是空的，因为value buffer不满发送goroutine可以发送完成不可能会阻塞。该发送goroutine将要发送的数据push到value buffer中然后继续执行。这种情况下，chan send操作是non-blocking操作。

3）如果chan的recv goroutine queue是空的，并且value buffer是满的，发送goroutine将被push到send goroutine queue中进入阻塞状态。等到有其他goroutine尝试从chan接收数据的时候才能将其唤醒恢复执行。这种情况下，chan send操作是blocking操作。

1.3 chan操作规则3 ##

当一个goroutine尝试close一个non-nil & non-closed chan的时候，close操作将依次执行如下操作。

1）如果chan的recv goroutine queue不空，这种情况下value buffer一定是空的，因为如果value buffer如果不空，一定会继续unshift recv goroutine queue中的goroutine接收数据，直到value buffer为空（这里可以看下chan send操作，chan send写入数据之前，一定会从recv goroutine queue中unshift出一个recv goroutine）。recv goroutine queue里面所有的goroutine将一个个unshift出来并返回一个val=0值和sentBeforeClosed=false。

2）如果chan的send goroutine queue不空，所有的goroutine将被依次取出并生成一个panic for closing a close chan。在这close之前发送到chan的数据仍然在chan的value buffer中存着。

1.4 chan操作规则4 ##

一旦chan被关闭了，chan recv操作就永远也不会阻塞，chan的value buffer中在close之前写入的数据仍然存在。一旦value buffer中close之前写入的数据都被取出之后，后续的接收操作将会返回val=0和sentBeforeClosed=true。

1.5 小结 #

理解这里的goroutine的blocking、non-blocking操作对于理解针对chan的select-case操作是很有帮助的。下面介绍select-case实现机制。

2 select-case实现 #

2.1 select-case原理简述 #

select-case中假如没有default分支的话，一定要等到某个case分支满足条件然后将对应的goroutine唤醒恢复执行才可以继续执行，否则代码就会阻塞在这里，即将当前goroutine push到各个case分支对应的ch的recv或者send goroutine queue中，对同一个chan也可能将当前goroutine同时push到recv、send goroutine queue这两个队列中。

不管是普通的chan send、recv操作，还是select chan send、recv操作，因为chan操作阻塞的goroutine都是依靠其他goroutine对chan的send、recv操作来唤醒的。前面我们已经讲过了goroutine被唤醒的时机，这里还要再细分一下。

chan的send、recv goroutine queue中存储的其实是一个结构体指针*sudog，成员gp *g指向对应的goroutine，elem unsafe.Pointer指向待读写的变量地址，c *hchan指向goroutine阻塞在哪个chan上，isSelect为true表示select chan send、recv，反之表示chan send、recv。g.selectDone表示select操作是否处理完成，即是否有某个case分支已经成立。

2 select-case执行流程 #

2.1 chan操作阻塞的goroutine唤醒时执行逻辑 ##

下面我们先描述下chan上某个goroutine被唤醒时的处理逻辑，假如现在有个goroutine因为select chan 操作阻塞在了ch1、ch2上，那么会创建对应的sudog对象，并将对应的指针*sudog push到各个case分支对应的ch1、ch2上的send、recv goroutine queue中，等待其他协程执行(select) chan send、recv操作时将其唤醒： 1）源码文件chan.go，假如现在有另外一个goroutine对ch1进行了操作，然后对ch1的goroutine执行unshift操作取出一个阻塞的goroutine，在unshift时要执行方法 **func (q waitq) dequeue() sudog，这个方法从ch1的等待队列中返回一个阻塞的goroutine。

func (q *waitq) dequeue() *sudog {
	for {
		sgp := q.first
		if sgp == nil {
			return nil
		}
		y := sgp.next
		if y == nil {
			q.first = nil
			q.last = nil
		} else {
			y.prev = nil
			q.first = y
			sgp.next = nil // mark as removed (see dequeueSudog)
		}

		// if a goroutine was put on this queue because of a
		// select, there is a small window between the goroutine
		// being woken up by a different case and it grabbing the
		// channel locks. Once it has the lock
		// it removes itself from the queue, so we won't see it after that.
		// We use a flag in the G struct to tell us when someone
		// else has won the race to signal this goroutine but the goroutine
		// hasn't removed itself from the queue yet.
		if sgp.isSelect {
			if !atomic.Cas(&sgp.g.selectDone, 0, 1) {
				continue
			}
		}

		return sgp
	}
}

假如队首元素就是之前阻塞的goroutine，那么检测到其sgp.isSelect=true，就知道这是一个因为select chan send、recv阻塞的goroutine，然后通过CAS操作将sgp.g.selectDone设为true标识当前goroutine的select操作已经处理完成，之后就可以将该goroutine返回用于从value buffer读或者向value buffer写数据了，或者直接与唤醒它的goroutine交换数据，然后该阻塞的goroutine就可以恢复执行了。

这里将sgp.g.selectDone设为true，相当于传达了该sgp.g已经从刚才阻塞它的select-case块中退出了，对应的select-case块可以作废了。有必要提提一下为什么要把这里的sgp.g.selectDone设为true呢？直接将该goroutine出队不就完了吗？不行！考虑以下对chan的操作dequeue是需要先拿到chan上的lock的，但是在尝试lock chan之前有可能同时有多个case分支对应的chan准备就绪。看个示例代码：

// g1
go func() {
  ch1 <- 1
}()

// g2
go func() {
  ch2 <- 2
}

select {
  case <- ch1:
    doSomething()
  case <- ch2:
    doSomething()
}

协程g1在 chan.chansend方法中执行了一般，准备lock ch1，协程g2也执行了一半，也准备lock ch2; 协程g1成功lock ch1执行dequeue操作，协程g2页成功lock ch2执行deq ueue操作； 因为同一个select-case块中只能有一个case分支允许激活，所以在协程g里面加了个成员g.selectDone来标识该协程对应的select-case是否已经成功执行结束（一个协程在某个时刻只可能有一个select-case块在处理，要么阻塞没执行完，要么立即执行完），因此dequeue时要通过CAS操作来更新g.selectDone的值，更新成功者完成出队操作激活case分支，CAS失败的则认为该select-case已经有其他分支被激活，当前case分支作废，select-case结束。

这里的CAS操作也就是说的多个分支满足条件时，golang会随机选择一个分支执行的道理。

2.2 select-case块golang是如何执行处理的 ##

源文件select.go中方法 *selectgo(sel hselect) ，实现了对select-case块的处理逻辑，但是由于代码篇幅较长，这里不再复制粘贴代码，感兴趣的可以自己查看，这里只简要描述下其执行流程。

selectgo逻辑处理简述：

• 预处理部分 对各个case分支按照ch地址排序，保证后续按序加锁，避免产生死锁问题；
• pass 1 部分处理各个case分支的判断逻辑，依次检查各个case分支是否有立即可满足ch读写操作的。如果当前分支有则立即执行ch读写并回，select处理结束；没有则继续处理下一分支；如果所有分支均不满足继续执行以下流程。
• pass 2 没有一个case分支上chan操作立即可就绪，当前goroutine需要阻塞，遍历所有的case分支，分别构建goroutine对应的sudog并push到case分支对应chan的对应goroutine queue中。然后gopark挂起当前goroutine，等待某个分支上chan操作完成来唤醒当前goroutine。怎么被唤醒呢？前面提到了chan.waitq.dequeue()方法中通过CAS将sudog.g.selectDone设为1之后将该sudog返回并恢复执行，其实也就是借助这个操作来唤醒。
• pass 3 整个select-case块已经结束使命，之前阻塞的goroutine已被唤醒，其他case分支没什么作用了，需要废弃掉，pass 3部分会将该goroutine从之前阻塞它的select-case块中各case分支对应的chan recv、send goroutine queue中移除，通过方法chan.waitq.dequeueSudog(sgp *sudog)来从队列中移除，队列是双向链表，通过sudog.prev和sudog.next删除sudog时间复杂度为O(1)。

3 总结 #

本文简要描述了golang中select-case的实现逻辑，介绍了goroutine与chan操作之间的协作关系。之前ZMQ作者Martin Sustrik仿着golang写过一个面向c的库，libmill，实际实现思路差不多，感兴趣的也可以翻翻看，libmill源码分析。