sheharyaar/GO-Concurrency.md

## GO-Concurrency.md

      
    Raw
  

              GO-Concurrency.md
            
          
    Go Concurrency

Contents


Goroutines

GO Waitgroups
GO Scheduler
GO States
Synchronous system calls
Netpoller
Work Stealing


GO Channels

Channels Basics
Channels Internals
Select


Sync Package

Mutex
Atomic
Condition Variables


Goroutines


Similar to OS threads but :

Lightweight and fast.
Thread stack starts from 2KB
Low CPU overhead (less syscalls)
Context switching is cheaper than threads


Total OS threads created by Go can be set by GOMAXPROCS variable.
GO runtime (present in the app binary) creates OS threads (scheduled by the Kernel) and then the runtime creates Goroutines (scheduled by the runtime) 

GO Waitgroups


Part of sync package
Used to wait on goroutines to complete execution
Syntax :

 wg sync.WaitGroup
 wg.Add(1) // Add number of threads
 
 go func(){
    defer wwg.Done()
    
    ...
    
  }()
  
  ...
  
  wg.Wait()
GO Scheduler ( > 1.14 )


Preemptive scheduler
Timeslice of 10ms

GO States


Similar to threads
States : Runnable, Executing and Waiting 

Synchronous system calls


To tackle synchronous syscalls on a thread which block the execution, Go creates a new OS thread or uses one from the thread cache and then moves logical proceess P to the new thread. The goroutine which made synchronous call is still present on the old thread.
After the blocking goroutine executes, the old thread is made to sleep or sent to the thread cache

Netpoller


Converts asynchronous calls to blocking system call
When an async system call is made and the file descriptor is not ready, then it is parked at netpoller OS threead.
netpoller uses OS interface to poll and once the fd is ready it notifies the goroutine :

kqueue (MacOS)
epoll (linux)
iocp (Windows)
io_uring (still in discussion : golang/go#31908 )


Work stealing


If a logical process runs out of goroutines, then :

It randomly picks another logical processor and steals half of it's scheduled goroutines; then
It looks at the Global Runtime Queue for goroutines; then
It looks at the netpoller queue


Helps in better distribuiton of work across threads


GO Channels


These are circular ring buffers
Used for synchronisation between multiple goroutines
Two types : buffered and unbuffered
For typesafety function arguments can be set to send only (chan<-) or recv only (<-chan) type.
As a good measure, the goroutine that creates the channel should instantiate, write and close the channel. This goroutine should be the owner. This helps in avoiding deadlocks and panics.

Deadlocks and Panics can occur:

Writing or closing a nil channel
Writing to a closed channel
Closing a channel more than once

Channels Internals

Internal structure of a channel :
type hchan struct {
   qcount   uint           // total data in the queue
   dataqsiz uint           // size of the circular queue
   buf      unsafe.Pointer // points to an array of dataqsiz elements
   elemsize uint16
   closed   uint32
   elemtype *_type // element type
   sendx    uint   // send index
   recvx    uint   // receive index
   recvq    waitq  // list of recv waiters
   sendq    waitq  // list of send waiters

   // lock protects all fields in hchan, as well as several
   // fields in sudogs blocked on this channel.
   //
   // Do not change another G's status while holding this lock
   // (in particular, do not ready a G), as this can deadlock
   // with stack shrinking.
   lock mutex
}

type waitq struct {
   first *sudog
   last  *sudog
}

// sudog represents a g in a wait list, such as for sending/receiving
// on a channel.
//
// sudog is necessary because the g ↔ synchronization object relation
// is many-to-many. A g can be on many wait lists, so there may be
// many sudogs for one g; and many gs may be waiting on the same
// synchronization object, so there may be many sudogs for one object.
//
// sudogs are allocated from a special pool. Use acquireSudog and
// releaseSudog to allocate and free them.
type sudog struct {
   // The following fields are protected by the hchan.lock of the
   // channel this sudog is blocking on. shrinkstack depends on
   // this.

   g          *g
   selectdone *uint32 // CAS to 1 to win select race (may point to stack)
   next       *sudog
   prev       *sudog
   elem       unsafe.Pointer // data element (may point to stack)

   // The following fields are never accessed concurrently.
   // waitlink is only accessed by g.

   releasetime int64
   ticket      uint32
   waitlink    *sudog // g.waiting list
   c           *hchan // channel
}
Sending data over buffered channel


Acquire Lock
Enqueue (copy) element to buf
Increase send index
Release Lock

Receiving data over buffered channel


Acquire lock
Dequeue element
Copy element to variable
Increase receive index
Release Lock


IMP : There is no memory sharing, the element is copied to and from buffer.

Buffer Full

The following happens if a buffer is full and the channel is being written to :

Sender goroutine is blocked and parked on sendQ (check hchan struct)
Data wiill be stored in the elem field of the sudog struct
When receiver deques value from buffer, enques the data from elem field to the buffer
Pops the goroutine in sendq and puts it to runnable state.

Buffer Empty


The same things as above.
The waiting receiving goroutine is parked to recvQ
The sending goroutine instead of pushing to the buffer pushes DIRECTLY to the receiving goroutine's stack which is contained in the elem field of the recQ goroutine.
Pops the recv goroutinee and sets it to running state

Send on Unbuffered channel


If a receiver is present, it directly copies to the receiver in recvQ and then pops it from there and sets it to running state
If a receiver is not present then, it gets parked to sendQ state and the value is copied to elem field in sudog struct

Receiving on Unbuffered channel


If a sender is there in sendQ then the value is copied from elem of the sudog struct and the sender is popped and set to running
Otherwise it gets parked to recQ state

Summary of communication


Blocking sender/receiver is parked to sendQ/recvQ and then the other comes in, copies the value and pops the blocking one out and sets that to running state.
The scheduler moves the blocked goroutines out of the OS thread and after channel operation is complete, goroutine is moved to local run queue.

Select

Select helps to select the available channel that is ready or until a timeout occurs to process on it.
select{
    case <-ch1:
    // block of code
    case <- ch2:
    // block of code
    case ch3 <- struct{}{}:
    // block of code
    case <- time.After(3*time.Second):
    // timeout
    default:
    // don't block and exit (cant be used with time...)
}

The cases are evaulated at the same time instead of sequentially.
Select on nil channel blocks forever

Sync Package

Mutex


Used over channels if we need to share caches and states (too large for channels).
Two types of Mutex : normal and RW Mutex
RW Mutex is for having multiple readers.
sync.Mutex

Atomic


Used for low level atomic operations and the operation is lockless.
Eg. Increasing counters

atomic.AddUint64(&counter,1)
value:= atomic.LoadUint64(&counter)
Condition Variables