当最简单的并发程序违背所有直觉
我在模型检查器上运行一个看似简单的并发程序时,发现了一个令人着迷且出乎意料的现象。考虑以下代码:
如果我们同时运行P和Q,且n
初始化为0,那么当这两个进程执行完它们的语句后,n
的值会是多少呢?
我原本以为n
的最终值会在10到20之间。你怎么看?猜一猜。
我在Ben-Ari关于SPIN模型检查器的书中[1]看到了这个例子。他说他惊讶地发现,n
的最终值可能低至2。我也感到震惊——这个结果完全违背了我的直觉。
为了验证这一点,我们可以在SPIN中编写一个简单的程序,并声明存在一个计算结果为2的情况。我们可以通过在程序末尾添加断言assertion (n > 2)
并运行验证来自动获得这个结果。SPIN会搜索状态空间,寻找反例。
以下是程序以及显示极端交错执行的轨迹:
当我运行这个程序时,出现了错误:
你可以在这个文件中查看完整的交错执行轨迹。
看到这个结果后,我很好奇:在实践中是否有可能观察到n
被设置为2的情况?我认为在实践中几乎不可能出现这种情况。一位Go专家向我分享了以下代码,它将执行限制在一个线程中,并显式地重新调度操作。当你运行这个Go程序时,n
的值有时是11,有时是10,但从未低于10。
package main
import "runtime"
func main() {
runtime.GOMAXPROCS(1)
n := 0
done := make(chan bool)
for range 2 {
go func() {
for range 10 {
runtime.Gosched()
t := n + 1
runtime.Gosched()
n = t
}
done <- true
}()
}
<-done
<-done
println(n)
}
无论如何,我发现这不仅反直觉,而且非常有趣,尽管我们在实践中可能不会遇到这种情况。所以,我觉得应该分享出来。
我想知道是否有可能以其他方式创建这个计算结果,或者创建一个n
的值低于10的计算结果?
这个例子让我感到惊讶。你遇到过的最简单的并发程序是什么,它让你感到最惊讶?