Upgrade to Pro — share decks privately, control downloads, hide ads and more …

君の並行処理は実行するまでもなく間違っている #golangtokyo / golang.to...

y_taka_23
December 18, 2018

君の並行処理は実行するまでもなく間違っている #golangtokyo / golang.tokyo 20th

golang.tokyo #20 で使用した論文紹介スライドです。

Go のチャネルによる並行処理は強力で魅力的な機能ですが、同時にバグが発生しやすくかつ発見しづらい部分でもあります。この論文では、Go プログラムからその挙動を形式的に記述した振舞い型 (behavioural types) を抽出することで、並行処理に潜むバグを静的に検出する手法が提案されています。

イベント概要:https://golangtokyo.connpass.com/event/111077/
元論文:http://mrg.doc.ic.ac.uk/publications/a-static-verification-framework-for-message-passing-in-go-using-behavioural-types/

y_taka_23

December 18, 2018
Tweet

More Decks by y_taka_23

Other Decks in Technology

Transcript

  1. A Static Verification Framework for Message Passing in Go Using

    Behavioural Types J.Lange et al. (2018) #golangtokyo
  2. #golangtokyo func prod(ch chan int) { for i := 0;

    i < 5; i++ { ch <- 1 } close(ch) } func cons(ch1, ch2 chan int) { for { select { case x := <-ch1: fmt.Println(x) case x := <-ch2: fmt.Println(x) } } } func main() { ch1, ch2 := make(chan int), make(chan int) go prod(ch1) go prod(ch2) cons(ch1, ch2) } prod(ch chan int) {...} cons(ch1, ch2 chan int) {...} main(ch chan int) {...}
  3. #golangtokyo func prod(ch chan int) { for i := 0;

    i < 5; i++ { ch <- 1 } close(ch) } func cons(ch1, ch2 chan int) { for { select { case x := <-ch1: fmt.Println(x) case x := <-ch2: fmt.Println(x) } } } func main() { ch1, ch2 := make(chan int), make(chan int) go prod(ch1) go prod(ch2) cons(ch1, ch1) }
  4. #golangtokyo func prod(ch chan int) { for i := 0;

    i < 5; i++ { ch <- 1 } close(ch) } func cons(ch1, ch2 chan int) { for { select { case x := <-ch1: fmt.Println(x) case x := <-ch2: fmt.Println(x) } } } func main() { ch1, ch2 := make(chan int), make(chan int) go prod(ch1) go prod(ch2) cons(ch1, ch1) } prod(ch chan int) {...} cons(ch1, ch2 chan int) {...} main(ch chan int) {...}
  5. #golangtokyo func prod(ch chan int) { for i := 0;

    i < 5; i++ { ch <- 1 } close(ch) } func cons(ch1, ch2 chan int) { for { select { case x := <-ch1: fmt.Println(x) case x := <-ch2: fmt.Println(x) } } } func main() { ch1, ch2 := make(chan int), make(chan int) go prod(ch1) go prod(ch2) cons(ch1, ch2) }
  6. #golangtokyo func prod(ch chan int) { for i := 0;

    i < 5; i++ { ch <- 1 } close(ch) } func cons(ch1, ch2 chan int) { for { select { case x := <-ch1: fmt.Println(x) case x := <-ch2: fmt.Println(x) } } } func main() { ch1, ch2 := make(chan int), make(chan int) go prod(ch1) go prod(ch2) cons(ch1, ch2) }
  7. #golangtokyo func prod(ch chan int) { for i := 0;

    i < 5; i++ { ch <- 1 } close(ch) } func cons(ch1, ch2 chan int) { for { select { case x := <-ch1: fmt.Println(x) case x := <-ch2: fmt.Println(x) } } } func main() { ch1, ch2 := make(chan int), make(chan int) go prod(ch1) go prod(ch2) cons(ch1, ch2) }
  8. #golangtokyo func prod(ch chan int) { for i := 0;

    i < 5; i++ { ch <- 1 } close(ch) } func cons(ch1, ch2 chan int) { for { select { case x := <-ch1: fmt.Println(x) case x := <-ch2: fmt.Println(x) } } } func main() { ch1, ch2 := make(chan int), make(chan int) go prod(ch1) go prod(ch2) cons(ch1, ch2) }
  9. #golangtokyo Labeled Trans. Sys. Go Source Code Termination Safety /

    Liveness Specification Modal µ-Calculi Behavioural Types mCRL2 KITTeL This Paper This Paper (By Hand)
  10. 検査できる性質の例 • 無限ループが発生しない • デッドロックが発生しない • どの goroutine も飢餓状態にならない •

    close 済みチャネルに送信しない • チャネル内の値はいつか受信される #golangtokyo
  11. A Static Verification Framework for Message Passing in Go Using

    Behavioural Types J.Lange et al. (2018) #golangtokyo