Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why happen here a deadlock

Tags:

go

I am trying to understand, how golang channel works. I read a book about the go language and found the following example.

package main

import (
    "fmt"
)

// Send the sequence 2, 3, 4, ... to returned channel 
func generate() chan int {
    ch := make(chan int)
    go func() {
        for i := 2; i <= 100 ; i++ {
            ch <- i
        }
    }()
    return ch
}

// Filter out input values divisible by 'prime', send rest to returned channel
func filter(in chan int, prime int) chan int {
    out := make(chan int)
    go func() {
        for {
            if i := <-in; i%prime != 0 {
                out <- i
            }
        }
    }()
    return out
}

func sieve() chan int {
    out := make(chan int)
    go func() {
        ch := generate()
        for {
            prime := <-ch
            ch = filter(ch, prime)
            out <- prime
        }
    }()
    return out
}

func main() {
    primes := sieve()
    for {
        fmt.Println(<-primes)
    }
}

When I run this programm, I've got a deadlock, but when I change the generate function to

// Send the sequence 2, 3, 4, ... to returned channel 
func generate() chan int {
    ch := make(chan int)
    go func() {
        for i := 2; ; i++ {
            ch <- i
        }
    }()
    return ch
}

Then the programm will run the infinite loop, but not deadlock. Why do I get deadlock, when I remove the condition in for loop?

like image 240
softshipper Avatar asked Jul 23 '14 09:07

softshipper


2 Answers

What do you mean with blocking principle?

You can see it illustrated in the blog post "The Nature Of Channels In Go "

for an unbuffered channel:

http://3.bp.blogspot.com/-vnJIWvlbP-E/UwDVICJKB9I/AAAAAAAANX0/T04V_58i8Vs/s1600/Screen+Shot+2014-02-16+at+10.10.54+AM.png

(Illustration from blog post "The Nature Of Channels In Go ", written by William Kennedy, Feb. 2014)

Unbuffered channels have no capacity and therefore require both goroutines to be ready to make any exchange.
When a goroutine attempts to write a resource to an unbuffered channel and there is no goroutine waiting to receive the resource, the channel will lock the goroutine and make it wait.
When a goroutine attempts to read from an unbuffered channel, and there is no goroutine waiting to send a resource, the channel will lock the goroutine and make it wait.

That is what happens in your case with your reader:

func main() {
    primes := sieve()
    for {
        fmt.Println(<-primes)
    }
}

since primes is never closed, main remains blocked.
It (main) is in step 3:

in step 3, the goroutine on the right places his hand into the channel or performs a read.
That goroutine is also locked in the channel until the exchange is complete.

The sender never calls close(primes).

like image 141
VonC Avatar answered Oct 02 '22 21:10

VonC


Let's consider a simpler example:

func generate() chan int {
    ch := make(chan int)
    go func() {
        for i := 2; /*i < 100*/; i++ {
            ch <- i
        }
    }()
    return ch
}

func main() {
    for i := range generate() {
        fmt.Println(i)
    }
}

With the condition i < 100 uncommented, the goroutine spawned by generate stops after sending 98 numbers. However, it does not close the channel, so main has no way of knowing that no more numbers are going to be sent, and it just keeps blocking on the channel. Since main is now the only goroutine still in existence (the other one has returned), and it's blocking, you have a deadlock.

like image 20
Fred Foo Avatar answered Oct 02 '22 21:10

Fred Foo