Why use concurrency

Why Use parallel execution

More efficient
Some tasks must be performed sequentially
Not all tasks can be run parallelly

Parallel Execution

2 Programs execute in parallel if they execute at the exactly the same time
At time t, an instruction is being performed for both P1 and P2
Need replicated hardware

Von Neumann Bottleneck

Design processors with more memory:
- Reduce the bottlenech
- Cache access time = 1 clock cycle
- Main memory access time = ~100 clock cycles
- Increasing on-chip cache improves performance

Moore’s Law

Predicted that transistor density would double every 2 years
Smaller transistors switch faster
Exponential increase in density would lead to exponential increase in speed

Power wall

Transistors consume power when they switch
Increasing transistor density leads to increased power consumption
High power leads to high temperature
Air cooling has limit

Multi-core system

Cannot increase frequency
Can add processor cores, without increasing frequency
Parallel execution is needed to exploit multi-core systems
Different programs on different cores

Concurrent vs Parallel

Concurrent Execution

Concurrent execution is not necessarily the same as parallel execution
Concurrent: Start and end times overlap
Parallel: execute at exactly the same time
Parallel tasks must be executed on different hardware
Concurrent tasks may be executed on the same hardware, only 1 task actually executed at a time
Mapping from tasks to hardware is not directly controlled by the programmer: OS, Go runtime scheduler

Hiding Latency

Concurrency improves performances, even without parallelism
Tasks must periodically wait for something (i.e. Wait for memory)
Other concurrent tasks can operate while one is waiting

Concurrency Basics
Processes
Processes: an instance of a running program
- Memory: virtual address space stores code, stack, heap, shared libraries
- Registers: program counter, data regs, stack ptr…
Operating system allows many processes to execute concurrently, processes are switched quickly (20ms), user has the impression of parallelism
Operating system must give processes fair access to resources

Scheduling

Context switch: control flow changes from one process too another
State: all context related to a context, when doing context switch, the process state is saved in memory
Context switching can be slow

Thread & Goroutines

Thread has less contexts, shares some context with each other, many threads can exist in one process
OS schedules threads rather than processes
Goroutine is like a thread in Go. Many goroutines execute within a single OS thread.
Go runtime scheduler: schedules goroutines inside an OS thread. Like a little OS inside a single OS thread. Logical processor is mapped to a thread. Multiple Core CPU can have multiple logical processors.

Interleavings

The order of execution within a task is known
The order of execution between concurrent tasks is unknown
Interleaving of instructions between tasks is unknown. Many interleavings are possible, must consider all possibilities.

Race conditions

Outcome depends on non-deterministic ordering
race occurs due to communication

Goroutines

One goroutine is created automatically to execute the main()
A goroutine is a function that is capable of running concurrently with other functions.

func f(n int) {
  for i := 0; i < 10; i++ {
    fmt.Println(n, ":", i)
  }
}

func main() {
  go f(0)
  var input string
  fmt.Scanln(&input)
}

Channels

Channels provide a way for two goroutines to communicate with one another and synchronize their execution.

func pinger(c chan string) {
  for i := 0; ; i++ {
    c <- "ping"
  }
}

func printer(c chan string) {
  for {
    msg := <- c
    fmt.Println(msg)
    time.Sleep(time.Second * 1)
  }
}

func main() {
  var c chan string = make(chan string)

  go pinger(c)
  go printer(c)

  var input string
  fmt.Scanln(&input)
}

Using a channel like this synchronizes the two goroutines. When pinger attempts to send a message on the channel it will wait until printer is ready to receive the message. (this is known as blocking)

Select statement

Go has a special statement called select which works like a switch but for channels:

func main() {
  c1 := make(chan string)
  c2 := make(chan string)

  go func() {
    for {
      c1 <- "from 1"
      time.Sleep(time.Second * 2)
    }
  }()

  go func() {
    for {
      c2 <- "from 2"
      time.Sleep(time.Second * 3)
    }
  }()

  go func() {
    for {
      select {
      case msg1 := <- c1:
        fmt.Println(msg1)
      case msg2 := <- c2:
        fmt.Println(msg2)
      }
    }
  }()

  var input string
  fmt.Scanln(&input)
}

This program prints “from 1” every 2 seconds and “from 2” every 3 seconds. select picks the first channel that is ready and receives from it (or sends to it). If more than one of the channels are ready then it randomly picks which one to receive from. If none of the channels are ready, the statement blocks until one becomes available.

The select statement is often used to implement a timeout:

select {
case msg1 := <- c1:
  fmt.Println("Message 1", msg1)
case msg2 := <- c2:
  fmt.Println("Message 2", msg2)
case <- time.After(time.Second):
  fmt.Println("timeout")
}

time.After creates a channel and after the given duration will send the current time on it. (we weren’t interested in the time so we didn’t store it in a variable) We can also specify a default case:

select {
case msg1 := <- c1:
  fmt.Println("Message 1", msg1)
case msg2 := <- c2:
  fmt.Println("Message 2", msg2)
case <- time.After(time.Second):
  fmt.Println("timeout")
default:
  fmt.Println("nothing ready")
}

Buffered Channels

It’s also possible to pass a second parameter to the make function when creating a channel:

1	c := make(chan int, 1)

This creates a buffered channel with a capacity of 1. Normally channels are synchronous; both sides of the channel will wait until the other side is ready. A buffered channel is asynchronous; sending or receiving a message will not wait unless the channel is already full.

Close the channel

func fibonacci(n int, c chan int) {
	x, y := 0, 1
	for i := 0; i < n; i++ {
		c <- x
		x, y = y, x+y
	}
	close(c)
}

func main() {
	c := make(chan int, 10)
	go fibonacci(cap(c), c)
	for i := range c { // receives values from the channel repeatedly until it is closed.
		fmt.Println(i)
	}
}

Only the sender should close a channel, never the receiver. Sending on a closed channel will cause a panic.

sync.Mutex

mutual exclusion To make sure only one goroutine can access a variable at a time to avoid conflicts.

Go’s standard library provides mutual exclusion with sync.Mutex and its two methods: Lock, Unlock.

We can define a block of code to be executed in mutual exclusion by surrounding it with a call to Lock and Unlock.

We can also use defer to ensure the mutex will be unlocked.

import (
	"fmt"
	"sync"
	"time"
)

// SafeCounter is safe to use concurrently.
type SafeCounter struct {
	mu sync.Mutex
	v  map[string]int
}

// Inc increments the counter for the given key.
func (c *SafeCounter) Inc(key string) {
	c.mu.Lock()
	// Lock so only one goroutine at a time can access the map c.v.
	c.v[key]++
	c.mu.Unlock()
}

// Value returns the current value of the counter for the given key.
func (c *SafeCounter) Value(key string) int {
	c.mu.Lock()
	// Lock so only one goroutine at a time can access the map c.v.
	defer c.mu.Unlock()
	return c.v[key]
}

func main() {
	c := SafeCounter{v: make(map[string]int)}
	for i := 0; i < 1000; i++ {
		go c.Inc("somekey")
	}

	time.Sleep(time.Second)
	fmt.Println(c.Value("somekey"))
}