多资源select操作的实现模式

2016-02-24

先看这样一个需求:Go语言中,对chs []<-chan struct{}进行select操作,如果数组里所有channel都不可读,就阻塞调用的goroutine。

似乎是没有什么直接的方式,比如这样是不行的:

for _, c := range chs {
    select {
        case <-c:
            succ = true
            break
        default:
    }
}
if !succ {
    os.yield()
}

问题出在最后的yield操作只是让出了CPU,但并不是将当前goroutine设置成阻塞状态。这个不同之处在于,前者只是丢到了READY队列的队尾,下一轮还是会运行,浪费CPU,而后者丢到了阻塞队列,除非满足了某些唤醒条件,它是不会再调度的。

在看云风的ltask的时候,发现它里面也要实现类似的模式,惊讶地发现它是直接调用coroutine.yield了,不禁想比较一下它为什么能这么做。发现ltask在调用select没有可用channel的时候,其实它就已经设置task的状态为阻塞了,跟Go不同,Go中没有暴露出将goroutine状态改为阻塞的方式。

还有一处发现是ltask中select的实现是逐个地对多个channel依次加锁,判断是否可用,释放锁。

ltask.select是支持操作多个channel,理论上跟Go应该是一样的。但这里跟Go实现方式不一样,引起了我的注意。

分析以后发现,ltask里面的写channel操作是不阻塞的,这样不会出现死锁的成环条件。不知道云风是碰巧设计的还是有意为之。总之若没有这项约束,这种实现就是隐藏较深的BUG。


为什么Go语言中不这么做?记得我在一次技术分享的时候提到过这个问题。我们看一下:

select {
    case c1<-1:
    case c2<-2:
}

select {
    case <-c2:
    case <-c1:
}

假设两个goroutine分别在运行上面的两个select,如果select的实现方式是依次对每一项channel加锁,判断是否可用,解锁,这样的流程会出现什么问题呢?我们假设goroutine1判断c1,发现不可写,同时goroutine2判断c2不可读。然后,goroutin1判断c2不可写,同时goroutine2判断c1不可读,于是----死锁了。两个goroutine都进入了阻塞,并且再也没有机会唤醒!

select其实是一个整体,里面的资源不能独立对待。要么全部成功,要么失败,否则可能死锁。

所以在Go中的实现是,对select里面的资源全部加锁之后,才执行后面的操作。为了解决加锁时的死锁,Go是对channel的结构体按地址排序后,按顺序加锁的。select操作是一个比较有开销的实现。

我去网上查相关的资料,还看到有人问到select的实现,Dmitry Vyukov(Go调度器的实现者,大牛一位)回答,本来是可以把channel做成无锁的,但正是select的存在,让无锁的channel很难实现了。然后Rob Pike跟贴,说当年他还专门发过paper讲select的实现。


再推广一下,其实这并不仅仅是在Go语言中的一个模式,其实在很多其它地方都有涉及。

宽泛地说就是执行多个资源的select,如果满足其中一个,就能继续执行。如果一个都不满足,则将当前的执行单元阻塞。将来在这些资源之一就成可用时唤醒执行单元。

我猜你大概能想到的,操作系统的select/epoll调用,或者fork以后多个进行的accept操作,都具有类似的模式。

那么还不难想到另一个:惊群问题。也就是,被唤醒的执行单元做了一次无意义的唤醒,然后再做一轮抢资源,只有一个胜出。

channelselectgolangltask云风