Multithreading in Go. Can somebody explain these answers to me?

I got two questions on a mock-exam. I was given the answers but cannot figure out the rationale behind them.

I will first post the code and then the questions and answers. Maybe somebody would be so kind to explain the answers to me?

package main

import "fmt"

func fact(n int, c chan int, d chan int) {

    k := /* code to compute factorial of n */

    z := <- d

    c <- k + z

    d <- z + 1

}

func main() {

    r := 0

    c := make(chan int)
    d := make(chan int)

    for i = 0 ; i < N ; i++ {
        go fact(i,c,d)
    }

    d <- 0

    for j = 0 ; j < N ; j++ {
        r = r + <-c
    }

    fmt.Printf("result = %d\n",r)

}

The first question is:

How does the program behave if we omit the line "d <- 0" in the main procedure, and why?

The answer from the teacher is:

The state of all the threads are blocked and also the main thread.

The second question is:

How would the efficiency of the whole program be affected if we swapped the first two lines of the fact procedure?

The answer is:

All threads are going to run sequentially. Each thread would trigger another thread only when it is finished.

It is best not to think of this as "multi-threading." Go provides direct facilities for concurrency, not for threading. It happens to implement its concurrency with threading, but that is an implementation detail. See Rob Pike's talk, Concurrency is not parallelism for a much deeper discussion.

The key to your questions is that channels are synchronous by default (if they are not made buffered during their construction). When one goroutine writes to a channel, it will block until some other goroutine reads from that channel. So when this line executes:

z := <- d

It cannot proceed until this line executes:

d <- 0

Without some value being available on the d channel, fact will never proceed. That is likely obvious to you. But the reverse is also true. Until something reads from the d channel, the main goroutine cannot proceed. In this way unbuffered channels provide a synchronization point across concurrent goroutines.

Similarly, the main loop cannot proceed until some value appears on c. I find it useful to use two fingers and point to the current line of code in each goroutine. Advance one finger until you get to a channel operation. Then advance the other until it reaches a channel operation. If your fingers are pointing to a read and a write on the same channel, then you may proceed. If they are not, then you're in deadlock.

If you think this through, you'll discover a problem. This program leaks a goroutine.

func fact(n int, c chan int, d chan int) {
    k := /* code to compute factorial of n */
    z := <- d // (1)
    c <- k + z
    d <- z + 1 // (2)
}

At (2) we try to write to d. What will allow that to proceed? Another goroutine reading from d. Remember, we started N goroutines, and all of them tried to read from d. Only one of them will be successful. The others will block at (1), waiting for something to show up on d. That happens when the first one gets to (2). Then that goroutine exits and a random goroutine will proceed.

But there will be a final goroutine that will never be able to write to d and it will leak. In order to resolve that, the following would need to be added before the final Printf:

<-d

This would allow the last goroutine to exit.

> How does the program behave if we omit the line "d <- 0" in the main procedure, and why?

Withough that line, each goroutine started by go fact(...) will be waiting for something from the channel, blocked at the statement z := <- d.

The fact() function has no net effect on the contents of the d channel -it removes something and adds something. So if there is nothing in the channel there will be no progress and the program will deadlock.

A goroutine which reads and writes from the same channel is asking for a deadlock - avoid in real life!

> How would the efficiency of the whole program be affected if we swapped the first two lines of the fact procedure?

The fact() routine will wait until it gets a token from the d channel before doing its lengthy factorial calculation.

Because there is only one token in play in the d channel at once, that means that each go routine will only do the expensive calculation when it receives the token, effectively serializing them.

As it was originally, the expensive factorial calculations are done in parallel before waiting for the token.

In practice this would work less well than you might have hoped for since goroutines aren't pre-emptively scheduled, only on blocking operations and function calls.