Go消息传递并发

1.并发缺陷的类型

Go语言基于消息传递机制的并发缺陷大概分为三种：

1.1通道安全性有关的并发缺陷

当一个通道被关闭后，可以任意的向其读取数据而不会报错（当通道为空时候会返回通道数据类型对应的0值而不是错误,如List 1所示），但是向一个已关闭的通道中发送数据或者重复关闭已经关闭的通道会引发安全性错误（List 2和List 3），这部分并发错误在实际的应用程序中几乎不可能出现，也不是我们研究的重点。

package main

import "fmt"

func main() {
	ch1 := make(chan int,10)
	go func() {
		a:=1
		ch1 <- a
		close(ch1)
	}()
	fmt.Println(<-ch1)
	fmt.Println(<-ch1)
}

1
0

List 1 向已关闭的通道读取数据代码及运行结果

package main
func main() {
	ch1 := make(chan int,10)
	go func() {
		a:=1
		ch1 <- a
		close(ch1)
	}()
	ch1 <- 2
}

panic: send on closed channel

goroutine 1 [running]:
main.main()
        /home/gopath/src/migoinferDemo/demo01.go:14 +0x198

List 2 向已关闭通道中发送数据

package main

import "time"

func main() {
	ch1 := make(chan int,10)
	go func() {
		a:=1
		ch1 <- a
		close(ch1)
		close(ch1)
	}()
	time.Sleep(time.Second)
}

panic: close of closed channel

goroutine 17 [running]:
main.main.func1(0xc000128000)
        /home/gopath/src/migoinferDemo/demo01.go:11 +0x5a
created by main.main
        /home/gopath/src/migoinferDemo/demo01.go:7 +0x4e

List 3 关闭已关闭的通道

1.2全局死锁

如果一个程序在运行的过程中所有goroutine都被阻塞从而引发死锁，我们就称之为全局死锁，Go语言本身就提供了一个全局死锁检测工具以避免类似情况，然而在实际应用中，一部分Go语言的库（如net库）会暂时关闭这个检测工具从而导致全局死锁的发生。

1.3局部死锁

局部死锁（或者被称为failure of liveness，具体后面会提到）与全局死锁对应，也就是在程序中某些goroutine还能够正常工作时程序因为某些错误发生了死锁，一个简单的局部死锁实例如List 4所示：

package main

func prod(ch chan int) {
	for i := 0; i < 5; i++ {
		ch <- i // 向ch中发送数据
	}
	close(ch) // 关闭通道ch
}
func cons(ch1, ch2 chan int) {
	for {
		select {
		case x := <-ch1:
			print(x) // 读取ch1中的数据
		case x := <-ch2:
			print(x) // 读取ch2中的数据
		}
	}
}
func main() {
	ch1, ch2 := make(chan int), make(chan int)
	go prod(ch1)
	go prod(ch2)
	cons(ch1, ch1)
}

List 4 局部死锁实例

在List 4中的代码中，cons方法中select语句表示无倾向的随机选择，倒数第二行中由于笔误使得ch1在cons的参数中出现了两次，从而使得倒数第三行中"go prod(ch2)"语句中调用新goroutine向ch2中传递数据操作的结果没能与cons方法连接起来(实际运行后结果为无限增加的0值），从而破坏了程序的liveness，在这个程序运行过程中不是所有goroutine都被阻塞了，这就是局部死锁。

局部死锁就是我们研究的重点问题。

2.消息传递相关并发缺陷检测相关思路（related works）

lange等人在Go并发缺陷静态分析方面做了很多工作，他们最新的成果是Godel Checker，该工具的工作流图为：

2.1对Go语言源码进行分析

尝试使用静态分析方法对于Go语言并发相关语句进行行为分析，如下：

使用上面类型对List 4中的代码进行分析后的结果为：

第一行是对于prod方法的分析，也就是包含一个向通道发送数据的行为，然后是发送行为和通道关闭的选择（发送行为结束后关闭通道）。

第二行是对于cons方法的分析，包括一个select语句，满足某一条件就执行对应的语句。

第三行是main函数分析，包含两个创建通道操作以及三个并发的调用方法操作。

对于Go语言源码的直接分析看上去能够对于程序的Liveness进行判断，然而在实际应用中由于各种不同的输入或者条件会导致分析的结果unsound。为了解决这个问题，当前的研究大多是从Go语言中间代码入手（主要是SSA,static single assignment静态单赋值），《Fencing off Go:
Liveness and Safety for Channel-Based Programming》中使用Go标准库中的ssa包将Go源代码转换为静态单赋值（SSA)中间表示（IR),然后从SSA块中提取通信结构作为行为类型。该论文中提出了一个名为MiGo的表现形式，具体如图1所示：

图1 MiGo的主要表现形式

这里需要注意的是select语句和phi语句在转化为MiGo形式时有其额外的表现形式。

《A Static Verification Framework for Message Passing in Go using

Behavioural Types》中使用图的形式对MiGo进行分析（目前我还没找到如何自动生成这种图像，相关工具的readme文件中没有提供相关说明，不过在工具源代码中有block包，后续看看源码，这里直接用论文中的例子）：

package main

func main() {
	ch := make(chan int) // Create channel
	go sendFn(ch)        // Run as goroutine
	x := recvVal(ch)     // Ordinary func call
	for i := 0; i < x; i++ {
		print(i)
	}
	close(ch) // Close channel ch
}
func sendFn(c chan int) {
	c <- 42 // Send on channel c
}
func recvVal(c chan int) int {
	return <-c // Receive from channel c
}

对应的图像为：

图2 示例SSA图表示

2.2提取类型定义

对于图2中的每一个方法（如main,sendFn，recvVal）所表示的每一个块（block)中都添加了一个类型签名(type signature),然后使用一个自定义的getFunction算法对于每一条语句进行遍历。该算法如下：

function genFunction(fun, n, k, ρ, Γ)
	switch s ← statement at line k do
		case t =make chan T S do
			genFunction(fun, n, k+1, ρ ; (newS t), Γ[t → t])
		case t=local chan T do
			genFunction(fun, n, k+1, ρ, Γ[t → ⊥])
		case t <?v or <?t or t '= <? t do
			genFunction(fun, n, k+1, ρ ; mkPrefixΓ (s), Γ)
		case close ( t ) do
			genFunction(fun, n, k+1, ρ ; close Γ(t), Γ)
		case return do return ρ; 0
		case jump i do return ρ ; mkJumpΓ (fun, i)
		case i f _ goto i else j do
			return ρ; (mkJumpΓ (fun, i) ⊕ mkJumpΓ (fun, j))
		case select b [д1, ..., дj] do
			ρc ← mkJumpΓ (fun, n+1)
			for i in [1, ..., j] do
				ρi ← mkPrefixΓ (дi ) ρi ← mkJumpΓ (fun, n+2?i)
			if b = nonblocking then
				ρd ← mkJumpΓ (fun, n+1+2?j)
				return {ρi ; ρi ; ρc }i∈{1, . . .,j } ∪ {τ ; ρd ; ρc }
			else return {ρi ; ρi ; ρc }i∈{1, . . .,j }
		case F ( x? ) or t=F ( x? ) do
			if t is a channel then abort
			else genFunction(fun, n, k+1, ρ; mkCallΓ (F, x?), Γ)
		case go F ( x? ) do
			ρ ← genFunction(fun, n, k+1, ?, Γ)
			return ρ; (mkCallΓ (F, x?) | ρ)
		case ? t0 = t1 or t0 = ? t 1 do
			if t 1 is a channel then
				genFunction(fun, n, k+1, ρ, Γ[t0 → Γ(t1)])
			else genFunction(fun, n, k+1, ρ, Γ)
		case phi [Blki :vi ]i∈InEdges do
			if ?i ∈ InEdges : vi is a channel then abort
			else genFunction(fun, n, k+1, ρ, Γ)
			otherwise do genFunction(fun, n, k+1, ρ, Γ)

算法1 genFunction

通过使用getFunction方法就可以推导出某段SSA中间码对应的行为类型。有一个名为gospal的工具可以实现该方法对应的功能，在第三节中对这个工具会进行实例说明。

2.3 对行为类型进行模型检查（model checking）

模型检查主要分为三步。

2.3.1 LTS

LTS是labelled transition system(标记过渡系统)的缩写，模型检查的第一步就是从一组操作语义规则（operational semantics rules）中为类型生成一个标记的过渡系统。Lange等人使用了mCRL2进行检查，mCRL2中有一条规则是：我们无法识别在递归环境下的并行组合和通道创建等操作的类型。这是保证状态空间有限的必要条件。也就是说无限递归的通道创建或者方法调用等操作在我们的实验中是无法检查的。

要研究LTS，需要从类型的语义着手，还是使用类似的标签来描述各种并发行为，如表1所示。

表1 语义标签

前面提到按照mCRL2规则需要排除无限递归创建通道的情况，因此可以直接将通道创建语句放到最外层，也就是：

这样T就不包括通道创建语句了，也可以将它们都写成并行创建的形式，即

这样我们就可以得到类型的语义，也就是各种操作前后状态的变化，如图3所示，箭头左边就是操作之前的状态，箭头所指就是操作后状态，比如说第二行第二个就是一个已经创建好的缓存为n的通道经过关闭操作后状态变为关闭的状态。

图3 类型的语义

根据以上信息可以构造有限的LTS，该LTS可以代表t<>所有可能的操作，它是一个元组

S是由行为类型术语（behavior type terms)隐式标记的一组状态,t₀<>就是初始状态，A是标签的集合，箭头就代表转换的过程。

2.3.2行为类型状态的属性（这部分目前原理清楚，就是示意图还没完全搞明白）

对于前面得到的LTS，在它们的基础上定义谓词，以分析在某一状态时可以执行哪些操作。具体来说就是定义了一个谓词族，如果T准备执行族中的某一个动作，则谓词成立，谓词的示意图如4所示：

图4 谓词的定义

2.3.3 Go程序的liveness和安全性（不太懂，准备看μ-calculus相关文献）

我们在μ-calculus中对Go程序的liveness进行编码，并在2.3.2的状态标签上进行扩展。

在2.3.1中定义的LTS上对μ-calculus进行解释，如果T在LTS T中满足?，则我们可以定义

也就是说公式?对于每个T成立（而⊥永远不成立）。构造[α]?是模态运算符，如果对于T的每个α导数T'（即，通过执行动作α可以从T到达T'），公式?满足T'，则满足该条件。对偶模态是<α>?，如果存在T的α导数T^'使得?在T^'中成立，则对偶模态成立。构造νx. ?（resp.μx.?）是标准最大定点运算符（fixpoint operator)。图5是μ-calculus的公式

图5 μ-calculus的公式

根据图5中公式可以描述能够使用mCRL2进行验证的几个属性，给定一个

μ-calculus公式?，如果?对于所有可能达到的状态都满足，那么第一行的公式就总是成立。而如果?只能满足某些可达状态，那么第二行的公式就成立。下面各个公式所对应的情况都在每行末尾的方括号内说明了，也就是说μ-calculus公式可以覆盖几乎所有已知的Go语言并发情况。

Model checking这部分总的来说就是根据从Go源码中推断出的行为类型，将其转换为mCRL2语言，然后生成尽量小的（通过LTS等方式）μ-calculus公式，最后为每一个公式运行mCRL2检查器，并将结果返回给用户。

2.4 终止检查（Termination checking)

这一步就是为了解决2.1中提到的程序行为类型分析结果与程序实际之间不匹配的情况，使用了KITTeL终止分析器，该分析器原本是用于C语言的，因为Go语言结构与C语言类似所以也可以用于Go循环的终止分析，简单地说就是将Go语言中的所有循环（也就是for循环，Go语言中没有while循环）单独提取出来，忽略其他语句，然后检查循环的参数是否能使每个循环终止，如List 5所示。

func f(n int) {
	for i := 0; i < n; i++ {
		for j := 0; j < 10; j++ { ... }
    } 
}

List 5 终止检查循环实例

可以看到在这个嵌套的循环中有一个静态未知值n，它将作为各个C函数的参数生成，终止检查器KITTeL会强制检查这一类未知值所有可能的结果。

3.一部分工具

3.1 Go并发语句行为类型的分析

Lange等提出了一个名为gospal的工具包来分析Go并发语句的行为类型。List6展示了这个工具的使用情况。

package main

func main() {
	ch := make(chan int) 
	go sendFn(ch)        
	x := recvVal(ch)    
	for i := 0; i < x; i++ {
		print(i)
	}
	close(ch) 
}
func sendFn(c chan int) {
	c <- 42 
}
func recvVal(c chan int) int {
	return <-c 
}

def main.main():
    let t0 = newchan main.main0.t0_chan0, 0;
    spawn main.sendFn(t0);
    call main.recvVal(t0);
    call main.main#3(t0);
def main.sendFn(c):
    send c;
def main.recvVal(c):
    recv c;
def main.main#1(t0):
    call main.main#3(t0);
def main.main#2(t0):
    close t0;
def main.main#3(t0):
    ifFor (int t5 = 0; (t5


List 6 gospal分析Go语言语句的行为类型
3.2对于Go语言并发缺陷的检测工具
3.2.1 Gong
该工具是在《Fencing off Go:

Liveness and Safety for Channel-Based Programming》中提出的，github上的网址为https://github.com/nickng/gong 。它是本文主要描述的方法的前一步工作，该工具是对于行为类型分析的结果（.migo文件）进行程序liveness和安全性的分析。该工具是用Haskell语言写的，安装完成后在命令行中输入
Gong --help

可以看到该工具的一系列方法：
The checker program

checker [OPTIONS] FILE [INT (optional bound)]
  Go-Types liveness and safety checks

Common flags:
  -A --all       Check liveness and behavioural safety (default)
  -L --liveness  Check liveness
  -S --safety    Check behavioural safety
  -D --debug     Show liveness/safety error terms (debug)
  -N --list      Show list of k-reachable terms (debug)
  -? --help      Display help message
  -V --version   Print version information


使用一个简单的程序（List 7）验证一下该工具
package main

type S struct {
	ch chan int // nilchan
	v  int
}

func set(s *S, v int) {
	s.v = v
}

func main() {
	s := new(S)
	set(s, 10)
	set(s, 10)
	<-s.ch

	n := new(S)
	set(n, 11)
	n.ch = make(chan int)
	<-n.ch
}

List 7 Gong demo code
使用gospal分析后得到的行为类型为
def main.main():
    let t0_0 = newchan nilchan, 0;
    let t0_0 = newchan nilchan, 0;
    let t3 = newchan nilchan, 0;
    recv t3;
    let t6_0 = newchan nilchan, 0;
    let t9 = newchan main.main0.t9_chan0, 0;
    recv t9;

对其应用Gong进行分析，得到的结果如下，可知该程序是有并发错误的。


					
					
					
						相关
						
				
						
			
																
								
										Go语言核心36讲（Go语言实战与应用六）--学习笔记
									
									
								 

        
								
							
							

																
								
										Go语言之函数基础
									
									
								 

        
								
							
							

																
								
										Golang学习-CH4 Go语言流程控制
									
									
								 

        
								
							
							

																
								
										Golang学习-CH5 Go语言函数
									
									
								 

        
								
							
							

																
								
										Go语言中new和make的区别
									
									
								 

        
								
							
							

																
								
										go语言defer panic recover用法总结
									
									
								 

        
								
							
							

																
								
										Go语言程序的编译和运行
									
									
								 

        
								
							
							

																
								
										Go语言核心36讲（Go语言实战与应用十三）--学习笔记
									
									
								 

        
								
							
							

																
								
										go语言学习笔记-目录
									
									
								 

        
								
							
							

																
								
										go语言学习笔记-基础知识-3
									
									
								 

        
								
							
							

																
								
										Go语言核心36讲（Go语言实战与应用十七）--学习笔记
									
									
								 

        
								
							
							

																
								
										go语言sync.Mutex学习