[concurrent] notes from Leslie Lamport

Leslie Lamport’s "How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs" defines sequential consistency:

The customary approach to designing and proving the correctness of

multiprocess algorithms for such a computer assumes that the following

condition is satisfied: the result of any execution is the same as if

the operations of all the processors were executed in some sequential

order, and the operations of each individual processor appear in this

sequence in the order specified by its program. A multiprocessor

satisfying this condition will be called sequentially consistent.

Even on ARM/POWER: threads in the system must agree about a total order for the writes to a single memory location.

“weakly ordered” defined as follows:

Let a synchronization model be a set of constraints on memory accesses

that specify how and when synchronization needs to be done.

Hardware is weakly ordered with respect to a synchronization model

iff it appears sequentially consistent to all software that

obey the synchronization model.

[C++] note about std::shared_mutex and pthread_rwlock_t

Reference:
std::shared_mutex
pthread_rwlock_init
stackoverflow response:
https://stackoverflow.com/a/57709957
https://stackoverflow.com/a/2190271

Take away:

C++17's std::shared_mutex on linux might using pthread_rwlock_t underneath, thus in order to tweak

the behavior of write starvation, set PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP in the pthread_rwlock_init call's pthread_rwlockattr_t is necessary.

For those not using pthread_rwlock_t, std::shared_mutex should rely on linux kernel's scheduler, which is fair, avoid either write/read starvation.

Here's how Go handles stavation:

http://vsdmars.blogspot.com/2021/03/go-methods-for-lock-starvation-barging.html

[kernel] Thread Control Block (TCB) and Process control block(PCB)

Reference:

https://en.wikipedia.org/wiki/Process_control_block

https://en.wikipedia.org/wiki/Thread_control_block

https://en.wikipedia.org/wiki/X86_memory_segmentation

https://en.wikipedia.org/wiki/Protection_ring

A Deep dive into (implicit) Thread Local Storage: https://chao-tic.github.io/blog/2018/12/25/tls

[split stack] reading notes and references: https://vsdmars.blogspot.com/2019/01/split-stack-reading-notes-and-references.html

TCB(Thread control block) or TLS(Thread Local Storage) setup is done somewhat differently for statically linked executables and dynamically linked executables.

dynamically linked executables

TLS is initialised differently for the main thread and the other threads that begin later in the execution.

When it comes to dynamically linked ELF programs, it’s useful to know that once they are loaded and mapped into memory, the kernel would then take its hands off and pass the execution baton to the dynamic linker (ld.so on Linux).

The main thread’s TLS is setup in the function init_tls, which calls _dl_allocate_tls_storage to allocate the TCB or struct pthread, eventually invokes the aforementioned macro TLS_INIT_TP to bind the pthread TCB to the main thread.

A module in glibc can refer to either an executable or a dynamically shared object, a module ID therefore is an index number for a loaded ELF object in a process.

Note that for a given running process the module ID for the main executable will always be 1, whereas the shared objects don’t know their module IDs until they are loaded and assigned by the linker.

Dynamically-loaded modules here don’t mean any dynamic shared objects, they only refer to the shared objects that are loaded by explicitly calling dlopen.

[Go][ticket][trick] make 64-bit fields 64-bit aligned on 32-bit systems

Ticket:

cmd/compile: make 64-bit fields 64-bit aligned on 32-bit systems
https://github.com/golang/go/issues/599

Reference:

https://stackoverflow.com/questions/5061392/aligned-memory-management

The idea below is to avoid any padding, thus using 15 bytes, which if using 14 bytes will be used by later 2 bytes short type.

package mylib

import (
	"unsafe"
	"sync/atomic"
)

type Counter struct {
	x [15]byte // instead of "x uint64"
}

func (c *Counter) xAddr() *uint64 {
	// The return must be 8-byte aligned.
	return (*uint64)(unsafe.Pointer(
		uintptr(unsafe.Pointer(&c.x)) + 8 -
		uintptr(unsafe.Pointer(&c.x))%8))
}

func (c *Counter) Add(delta uint64) {
	p := c.xAddr()
	atomic.AddUint64(p, delta)
}

func (c *Counter) Value() uint64 {
	return atomic.LoadUint64(c.xAddr())
}

[Go] methods for lock starvation: Barging / Handoff / Spinning

Before Go v1.9.0, methods for thread starvation:

• Barging
• Spinning

After Go v.1.9.0 includes:

• Handoff

Goroutines wait for the lock for more than one millisecond, aka. bounded waiting, will be flagged as starving.

If there are Goroutines flagged as starving, the unlock method will hand off the lock to the first waiter directly.

[reference: Bounded waiting]

If there are Goroutines flagged as starving, the spinning method is deactivated.

[Go] posix thread TLS(slow) call by Go

Thread Local Storage(TLS)  is slow. (TLPI Ch.31.3.1, Ch.31.4)

Discussion thread:
https://groups.google.com/forum/?utm_medium=email&utm_source=footer#!msg/golang-nuts/tGamryo50BY/gKxPGwBdAwAJ


Steps:

1. Using runtime.LockOSThread to lock this go-routine to the underlying P
2. Call cgo/c SO.
3. Use channel to pass down messages, other go-routine might be scheduled out of this P(most likely won't if listen to same channel)

[Go] use sync.Pool with sense

https://github.com/golang/go/issues/23199

tl;dr
It's caller's responsibility to put back normalized size of instance back into
sync.Pool

Intermingling small and large size of instance put into the sync.Pool will
eventually getting all the instance inside the pool with large size.
(Read Reference 1)

thus either create a bunch of sync.Pool bucketize the items by size (aka. slab memory allocation) or only put back certain size of instance back to the pool.

Same idea as goroutin instance recycling.
Go runtime will not recycle any goroutin size > 2k.


Reference:
https://github.com/golang/go/issues/23199
http://vsdmars.blogspot.com/2019/01/split-stack-reading-notes-and-references.html

Reason:
the buffer inside the sync.Pool will remain LARGE and never shrink even serving small objects
code:

pool := sync.Pool{New: func() interface{} { return new(bytes.Buffer) }}

processRequest := func(size int) {
	b := pool.Get().(*bytes.Buffer)
	time.Sleep(500 * time.Millisecond) // Simulate processing time
	b.Grow(size)
	pool.Put(b)
	time.Sleep(1 * time.Millisecond) // Simulate idle time
}

// Simulate a set of initial large writes.
for i := 0; i < 10; i++ {
	go func() {
		processRequest(1 << 28) // 256MiB
	}()
}

time.Sleep(time.Second) // Let the initial set finish

// Simulate an un-ending series of small writes.
for i := 0; i < 10; i++ {
	go func() {
		for {
			processRequest(1 << 10) // 1KiB
		}
	}()
}

// Continually run a GC and track the allocated bytes.
var stats runtime.MemStats
for i := 0; ; i++ {
	runtime.ReadMemStats(&stats)
	fmt.Printf("Cycle %d: %dB\n", i, stats.Alloc)
	time.Sleep(time.Second)
	runtime.GC()
}

[Go] race detector

Reference:
https://golang.org/doc/articles/race_detector.html



Usage:
$ go test -race mypkg // to test the package

$ go run -race mysrc.go // to run the source file

$ go build -race mycmd // to build the command

$ go install -race mypkg // to install the package

Options:

The GORACE environment variable sets race detector options.

The format is:

$ GORACE="option1=val1 option2=val2"

The options are:

• log_path (default stderr):
  The race detector writes its report to a file named log_path.pid. The special names stdout and stderr cause reports to be written to standard output and standard error, respectively.
• exitcode (default 66):
  The exit status to use when exiting after a detected race.
• strip_path_prefix (default ""):
  Strip this prefix from all reported file paths, to make reports more concise.
• history_size (default 1):
  The per-goroutine memory access history is 32K * 2**history_size elements.
  Increasing this value can avoid a "failed to restore the stack" error in reports, at the cost of increased memory usage.
• halt_on_error (default 0):
  Controls whether the program exits after reporting first data race.

e.g

$ GORACE="log_path=/tmp/race/report strip_path_prefix=/my/go/sources/" go test -race

Excluding Tests with build tag:

// +build !race

package foo

// The test contains a data race. See issue 123.
func TestFoo(t *testing.T) {
 // ...
}

// The test fails under the race detector due to timeouts.
func TestBar(t *testing.T) {
 // ...
}

// The test takes too long under the race detector.
func TestBaz(t *testing.T) {
 // ...
}

[Go] channel vs. mutex

Channel

passing ownership of data, distributing units of work, communicating async results

Mutex:

caches, state

Go's WaitGroup as imperative language's thead join.

[Go] LockOsThread

Reference:
https://github.com/golang/go/wiki/LockOSThread

package sdl

// Arrange that main.main runs on main thread.
func init() {
 runtime.LockOSThread()
}

// Main runs the main SDL service loop.
// The binary's main.main must call sdl.Main() to run this loop.
// Main does not return. If the binary needs to do other work, it
// must do it in separate goroutines.
func Main() {
 for f := range mainfunc {
  f()
 }
}

// queue of work to run in main thread.
var mainfunc = make(chan func())

// do runs f on the main thread.
func do(f func()) {
 done := make(chan bool, 1)
 mainfunc <- func() {
  f()
  done <- true
 }
 <-done
}

func Beep() {
 do(func() {
  // whatever must run in main thread
 })
}

[futex] futex skim through

Notes from reading Eli Bendersky's blog post:
Basics of Futexes

Background:

System calls are expensive.
Context switch happens between userspace and kernel space.
Thus, we have VDSO ( http://vsdmars.blogspot.com/search/label/linux_vdso ) to relax some system calls' burden, as for locks, we have futex.
The difference here is that futex doesn't involve any business logic but simply to acquire the lock to access memory concurrently safe.


It is likely that when a thread acquires a lock, the lock hasn't been locked yet.
In this case, no system call involved, a compare_and_swap atomic instruction would be enough. ( cmpxhg , which is cheaper than a system call )
Reference:
https://stackoverflow.com/a/27856649
The high-level locks that lock-free algorithms try to avoid can guard arbitrary code fragments whose execution may take arbitrary time and thus, these locks will have to put threads into wait state until the lock is available which is a costly operation, e.g. implies maintaining a queue of waiting threads.

This is an entirely different thing than the CPU LOCK prefix feature which guards a single instruction only and thus might hold other threads for the duration of that single instruction only. Since this is implemented by the CPU itself, it doesn’t require additional software efforts.

Therefore the challenge of developing lock-free algorithms is not the removal of synchronization entirely, it boils down to reduce the critical section of the code to a single atomic operation which will be provided by the CPU itself.



However; if there's lock needed, the atomic CAS would fail.

2 choices here:

1. busy 'for loop CAS' (spinlock), which consumes CPU core power. Although it's in userspace, still a very bad idea.
   Reference:
   https://vsdmars.blogspot.com/2018/09/c-something-about-spinlock.html
2. "sleep" (i.e pause) until the lock free.
   Reference:https://vsdmars.blogspot.com/2018/09/c-something-about-spinlock.html
   As for 'pause':
   Pause Intrinsic can help prevent a busy wait from completely overwhelming the system, by inserting pauses in the instruction stream that prevent the busy loop from overwhelming the processor.
   This is particularly important on hyperthreaded systems since it gives the other logical core time to run.
   If must busy wait then be sure to use pause. 

Reference:
http://man7.org/linux/man-pages/man2/futex.2.html
The futex() system call provides a method for waiting until a certain condition becomes true.  It is typically used as a blocking construct in the context of shared-memory synchronization.  When using futexes, the majority of the synchronization operations are performed in user space.  A user-space program employs the futex() system call only when it is likely that the program has to block for a longer time until the condition becomes true.  Other futex() operations can be used to wake any processes or threads waiting for a particular condition.

Focus on 2 futex system calls:

• FUTEX_WAIT (mutex.Lock)
  waits on an event.
  Caller is suspended by the kernel and will only be scheduled awake when there's a wake-up signal.
• FUTEX_WAKE (mutex.Unlock)
  signals an event.

Go by example code from Eli Bendersky


Child process:

1. Waits for 0xA to be written into a shared memory slot.
2. Writes 0xB into the same memory slot.

Parent process:

1. Writes 0xA into the shared memory slot.
2. Waits for 0xB to be written into the slot.

wait_on_futex_value:
loop that waits
pause if the val is the expected value, but not yet being waked yet.
If val is not the expected value, continue looping.
Then another process sent out wake event, stop pausing, check if the val is the expected value, i.e not a spurious wake up call, if is, returns.
FUTEX_WAIT (since Linux 2.6.0)
This operation tests that the value at the futex word pointed to by the address uaddr still contains the expected value val,and if so, then sleeps waiting for a FUTEX_WAKE operation on the futex word.  The load of the value of the futex word is an atomic memory access (i.e., using atomic machine instructions of the respective architecture).  This load, the comparison with the expected value, and starting to sleep are performed atomically and totally ordered with respect to other futex operations on the same futex word.  If the thread starts to sleep, it is considered a waiter on this futex word.  If the futex value does not match val, then the call fails immediately with the error EAGAIN.

The purpose of the comparison with the expected value is to prevent lost wake-ups.  If another thread changed the value of the futex word after the calling thread decided to block based on the prior value, and if the other thread executed a FUTEX_WAKE operation (or similar wake-up) after the value change and before this FUTEX_WAIT operation, then the calling thread will observe the value change and will not start to sleep.

If the timeout is not NULL, the structure it points to specifies a timeout for the wait.  (This interval will be rounded up to the system clock granularity, and is guaranteed not to expire early.)  The timeout is by default measured according to the CLOCK_MONOTONIC clock, but, since Linux 4.5, the CLOCK_REALTIME clock can be selected by specifying FUTEX_CLOCK_REALTIME in futex_op.  If timeout is NULL, the call blocks indefinitely.
           

wake_futex_blocking:
send wake up event.
FUTEX_WAKE (since Linux 2.6.0)
This operation wakes at most val of the waiters that are waiting (e.g., inside FUTEX_WAIT) on the futex word at the address uaddr.  Most commonly, val is specified as either 1 (wake up a single waiter) or INT_MAX (wake up all waiters). No guarantee is provided about which waiters are awoken (e.g., a waiter with a higher scheduling priority is not guaranteed to be awoken in preference to a waiter with a lower priority).

• Futexes are kernel queues for userspace code.
• A futex is a queue the kernel manages for userspace convenience.
• Futex allows userspace code asking the kernel to suspend until a certain condition is meet, and allows other userspace code signal that condition and wake up the waiting processes.
• Futexes are implemented in kernel/futex.c
• Kernel keeps a hash table keyed by the address to quickly find the proper queue data structure and adds the calling process to the wait queue.

figure: https://lwn.net/Articles/360699/

Timed blocking with FUTEX_WAIT


Ok, isn't this familiar?
Golang's channel + context timeout.
And yet we could use Golang channel to implement a mutex lock.


Reference:
https://eli.thegreenplace.net/2018/basics-of-futexes/
http://man7.org/linux/man-pages/man2/futex.2.html
A futex overview and update
[C++] something about spinlock
Futexes are tricky [PDF]

[Go] channel in detail

Channel traits:

• goroutine is safe
• store and pass values between goroutines, Golang is a value based language same as C and C++
• provides FIFO semantic
• can cause goroutines to block and unblock

How would you design a channel?

Ring buffer!

With ring buffer, we need:

• the type that this ring buffer holds, thus compiler knows the size of the ring buffer which could allocate it's memory.
• start idx(hchan.recvx), end idx(hchan.sendx) (thus we know the current data size)
  while hchan.recvx == hchan.sendx means either 0 data or ring is full.
• ring buffer size
• how many senders/receivers are consuming the ring
  thus we need mutex lock

Let's take a look at hchan struct in golang chan.go implement:
https://github.com/golang/go/blob/master/src/runtime/chan.go#L32


hchan instance usually allocated on the heap, unless this channel is only been used in one single thread(stack, to be precise).


ch <- 42 will copy data into the ring buffer with mutex locks hchan, increase the hchan.sendx.
<- ch will copy the value from ring buffer with mutex locks hchan, increase the hchan.recvx.


If the ring buffer is full, send blocks, and golang scheduler suspends the send goroutine (aka. user space thread, not the OS thread) until there's room in the ring buffer.

Please refer to previous post about scheduler:
http://vsdmars.blogspot.com/2018/06/golang-go-scheduler.html
Golang scheduler design doc:
https://docs.google.com/document/d/1TTj4T2JO42uD5ID9e89oa0sLKhJYD0Y_kqxDv3I3XMw


Each (G)oroutine is managed by (P)rocessor, and each (P)rocessor can only be run by one (M)thread.
(P)rocessor has the runQ (list) holds (G)oroutines.

If the ring buffer is full, the sender pauses, scheduler calls 'gopark' to remove the caller (G)oroutine from (M)thread into (P)rocessor's runQ(of (G)oroutines).
https://github.com/golang/go/blob/master/src/runtime/proc.go#L284:6


hchan has the information of senders and receivers.
https://github.com/golang/go/blob/master/src/runtime/chan.go#L53:6

hchan.sendq // waitq
hchan.recvq  // waitq

type waitq struct {
    first *sudog
    last  *sudog
}

sudog:
https://github.com/golang/go/blob/master/src/runtime/runtime2.go#L276

sudog.elem represends the data which is about to send(copy)/receive(copy) to/from the ring buffer.



Here's the interesting part, the implementation optimized sending/receiving data by skip copy data into/out from ring buffer iff there's a waiting (G)oroutine, which directly store the sending/receiving pointer to data into the waiting (G)oroutine's sudog.elem
Receive optimized:
https://github.com/golang/go/blob/master/src/runtime/chan.go#L190
Send optimized:
https://github.com/golang/go/blob/master/src/runtime/chan.go#L473



Fast path implement:
Sender:
https://github.com/golang/go/blob/master/src/runtime/chan.go#L159
Receiver: (atomic.Load involved)
https://github.com/golang/go/blob/master/src/runtime/chan.go#L437


Quote from Ian Lance Taylor:
https://groups.google.com/forum/#!topic/golang-nuts/L-bGvB52UrU
The runtime package is always compiled by a known compiler, and is permitted to know how that specific compiler behaves. If the compiler changes, while still staying within spec, the runtime package will change too. You can't argue about the language's memory model based on the code in the runtime package.


Reference:
Ring buffer in C:
https://embeddedartistry.com/blog/2017/4/6/circular-buffers-in-cc
chan.go:
https://github.com/golang/go/blob/master/src/runtime/chan.go
gopark:
https://github.com/golang/go/blob/master/src/runtime/proc.go#L284:6
goready:
https://github.com/golang/go/blob/master/src/runtime/proc.go#L310:6
Benign Data Races: What Could Possibly Go Wrong?
https://software.intel.com/en-us/blogs/2013/01/06/benign-data-races-what-could-possibly-go-wrong
The Go Memory Model:
https://golang.org/ref/mem

[structure concurrency][Go][design] Graceful Shutdown

Recently I'm working on Actor design utilizing with Golang's channel.

Link: https://github.com/vsdmars/actor

While bumped into Martin Sústrik's blog post:
Graceful Shutdown: http://250bpm.com/blog:146
Along with the discussion: https://trio.discourse.group/t/graceful-shutdown/93
Structured concurrency resources: https://trio.discourse.group/t/structured-concurrency-resources/21

It's a nice summary, touched the well known concept of pthread cancellation point as well as Golang's context.Done()/Cancel() pattern.

Notes:
In-band cancel:
through application level channel

out-of-band cancel:
through language run-time

Sending a graceful shutdown request cannot possibly be a feature of the language. It must be done manually by the application.


POSIX C thread:
Reference:
https://stackoverflow.com/a/27374983
http://man7.org/linux/man-pages/man7/pthreads.7.html (Cancellation points)

The rules of hard cancellation are strict:
Once a coroutine has been hard-canceled the very next blocking call will immediately return ECANCELED.
In other words, every single blocking call is a cancellation point.

As an additional note, if looking at the POSIX requirement for cancel points, virtually all blocking interfaces are required to be cancel points.
Otherwise, on any completely blocked thread (in such call), there would be no safe way to terminate that thread.

Graceful shutdown can terminate the coroutine only when it is idling and waiting for a new request.

Reasoning:

If we allowed graceful shutdown to terminate the coroutine while it is trying to send the reply, it would mean that a request could go unanswered.

And that doesn't deserve to be called "graceful shutdown".
(e.g. Golang, context.Done() pattern)

Definition summarize:

Hard cancellation:

- Is triggered via an invisible communication channel created by the language runtime.

- It manifests itself inside the target coroutine as an error code (ECANCELED in libdill) or an exception (Cancelled in Trio).

- The error (or the exception) can be returned from any blocking call.

- In response to it, the coroutine is not expected to do any application-specific work. It should just exit.

Graceful shutdown:

- Is triggered via an application-specific channel.

- Manifests itself inside the target coroutine as a plain old message.

- The message may only be received at specific, application-defined points in the coroutine.

- In response to it, the coroutine can do arbitrary amount of application-specific work.

Hard cancellation is fully managed by the language.

Graceful shutdown is fully managed by the application.

Golang library reference:

go-resiliency/deadline: https://github.com/eapache/go-resiliency/tree/master/deadline

Godoc: https://godoc.org/github.com/eapache/go-resiliency/deadline#example-Deadline

[Actor model] Some real-world implementation details from AKKA

Found this talk on YT recently, my comments + notes below:

Introduction to the Actor Model for Concurrent Computation - John Murray

Actor is:

• persistent
• has internal state
• asyc
• Independent event-loop + memory
• Mailbox (receive message)
• React in FIFO order

Well,
actor model is concurrent with regard to a system of actions.
actor model is Not concurrent with regard to data.
(surely we can do implement concurrent thread inside one actor.)

Using channel as mutex to single variable

So, how to make a mutable variable access by multiple threads?

In Golang, we have channel.

• Create a channel with the length of 1.
• Put the mutable variable in, and mutiple goroutines have access to that channel.
• However, only one goroutine can successful retrieve the mutable varible inside the length of 1 channel, other goroutines since the channel has no value, it will block.
• This acts as a MUTEX for goroutines.
• Once the goroutine which having the mutable variable changed,
  it puts it back to the channel thus other goroutines can access.

Actor can:

• create more Actors
• receive messages and response
• make local decisions
• perform arbitrary, side-effecting action
• send messages
• respond to the sender 0 or more times
  (to clearfy here, by "respond" means
  send message to the sender Actor
  Not duplex channel respond)
• Process exactly one message at a time

Actor communication is:

• No channels or internediaries (such as in CSP, e.g. golang)
• "best effor" delivery
• at-most-once delivery
• Messages can take arbitrary long to be delivered (has no concept of time)
• No message ordering guarantees

Actor address:

• identify the actor
• may also represent a proxy / forwarder to an Actor
• contains location and transport information
• don't care where the Actor lives
  (can be inside the same process, different nodes, different containers, etc)
• one address may represent many Actors(pool)

Error handling:

• Supervision
• the running state of an Actor is monitored and managed by another Actor(the Supervisor)
• Supervision has:
• constantly monitors running state of actor
• can perform actions based on the state of the Actor( e.g unhandled error, restart Actor)
  (In Golang, we take advantage of context.Context)
• transparent life-cycle management
• addresses do not change during restarts
  (we implemented with Actor's hash(name + uuid + hostname) as 'address')
  BE WARE.
  This only has meaning iff Actor is not pure, which is STATEFUL.
• Persist state into local sqlite, loaded with (name + uuid)
• mailboxes are persisted outside the Actor instances (Auh, K.I.S.S)
  I doubt the use of Supervisor idea.
  Think about this, does the Sender care how the Receiver act when it receives the message? ;-P

 

Implement Address contains these as a group:

• mailbox
• Actor

Anti use-case:

• Working on a non-concurrent system
• performance critical applications
• non-concurrent communication is involved
• no mutable state

Draw backs:

• too many Actors
• testing
• debugging

Extra material:
Don't use Actors for concurrency


CRDT:
https://medium.com/@istanbul_techie/a-look-at-conflict-free-replicated-data-types-crdt-221a5f629e7e

[Go][book] Concurrency in Go - Katherine Cox-Buday

Summary of reading:
Concurrency in Go - Katherine Cox-Buday

I agree with Eli Bendersky's point of view about this book i.e
if coming from the arena of C++, which is that, the book is relatively
can be considered as a 'reference book' for some golang tricks.

Before delve into golang concurrency, the understanding of
golang scheduler is a must.
Reference:
http://vsdmars.blogspot.com/2018/06/golang-go-scheduler.html
http://vsdmars.blogspot.com/2018/07/golangnote-analysis-of-go-runtime.html
HPX lib (C++)
Intel TBB (C++)

Understanding memory model is also essential to concurrency, although in golang, this is mostly hidden by it's run-time and channel.
Reference:
http://vsdmars.blogspot.com/2018/09/concurrency-c-wrap-up-2018.html


For advanced concurrency programming, take a look at
The Art of Multiprocessor Programming - Maurice Herlihy & Nir Shavit
Reference:
http://vsdmars.blogspot.com/2016/01/multiprocessor-programming-types-of.html

Jotting down reading notes for those are fun/useful :-)

RWLock:
[C++]
std::shared_mutex

[Golang]
sync.RWMutex

[Python]
None, and i coined one for fun:
https://github.com/verbalsaintmars/python_util/tree/master/rwlock

Cond Variable:
[C++]
std::condition_variable

[Golang]
sync.NewCond

sync.Once dead lock example:

var onceA, onceB sync.Once
var initB func()
initA := func() { onceB.Do(initB) }
initB = func() { onceA.Do(initA) }
onceA.Do(initA)

sync.Pool
sync.Pool can be the panacea for creating new type instance
inside a 'loop', i.e for loop.

Experienced engineer could spot the performance hit 'bad design'
by seeing new/make_shared/NewXXX etc. inside a for/while loop.

Reusing the type instance from being GCed boosts the performance;
however, just that, the pool stored type instance should be stateless
to avoid side-effect.

GC can still drain the Pool, thus a .Get() with drained Pool will create a new type's instance.

Further intriguing read:
Purpose of sync.Pool 
Learn High Performance Go 

Close(Channel):
close(channel)  acts as a signal for those blocking channels to continue.
e.g
https://play.golang.org/p/k3143TbiqO4

package main

import (
 "fmt"
 "time"
)

var ch = make(chan struct{})

func run(cnt int) {
 <-ch
 fmt.Println(cnt)
}

func main() {
 go run(1)
 go run(2)
 go run(3)
 go run(4)

 time.Sleep(10 * time.Second)
 close(ch)
 time.Sleep(10 * time.Second)
}

Select as normalized distribution seed:
Using select to act as a normalized distribution seed.
e.g:
https://play.golang.org/p/2m4VB9rhfcU

package main
import "fmt"

func main() {
 c1 := make(chan interface{})
 close(c1)
 c2 := make(chan interface{})
 close(c2)

 var c1Count, c2Count int

 for i := 1000; i >= 0; i-- {
  select {
  case <-c1:
   c1Count++
  case <-c2:
   c2Count++
  }
 }
 fmt.Println(c1Count)
 fmt.Println(c2Count)
}

Daisy-chain (it's simply elegant):
from slide:https://talks.golang.org/2012/concurrency.slide

func f(left, right chan int) {
    left <- 1 + <-right
}

func main() {
    const n = 10000
    leftmost := make(chan int)
    right := leftmost
    left := leftmost
    for i := 0; i < n; i++ {
        right = make(chan int)
        go f(left, right)
        left = right
    }
    go func(c chan int) { c <- 1 }(right)
    fmt.Println(<-leftmost)
}

Legacy golang code alert (prior Go1.5):

runtime.GOMAXPROCS(runtime.NumCPU())

i.e Go 1.5 is set to make the default value of GOMAXPROCS
the same as the number of CPUs on your machine,
so above code isn't necessary anymore.


Channel error/result back to caller:
https://play.golang.org/p/aCowW5mNEp1

package main

import "fmt"

func main() {
 type result struct {
  stat int
 }

 CheckErr := func(input chan int) <-chan result {
  r := make(chan result)

  go func() {
   defer close(r)
   for i := range input {
    r <- result{i}
   }
  }()

  return r
 }

 input := make(chan int)

 go func() {
  defer close(input)
  for i := range [10]struct{}{} {
   input <- i
  }
 }()

 for result := range CheckErr(input) {
  fmt.Println(result)
 }

}

The or-channel: 
https://play.golang.org/p/XsDYdU8ks5D

package main

import (
 "time"
)

func main() {

 var or func(channels ...chan interface{}) <-chan interface{}

 or = func(channels ...chan interface{}) <-chan interface{} {
  switch len(channels) {
  case 0:
   return nil
  case 1:
   return channels[0]
  }

  orDone := make(chan interface{})

  go func() {
   defer close(orDone) // Trick is here :-)

   switch len(channels) {
   case 2:
    select {
    case <-channels[0]:
    case <-channels[1]:
    }
   default:
    select {
    case <-channels[0]:
    case <-channels[1]:
    case <-channels[2]:
    case <-or(append(channels[3:], orDone)...):
    }
   }
  }()
  return orDone
 }

 chs := make([]chan interface{}, 7)
 for i, _ := range chs {
  chs[i] = make(chan interface{}, 1)
 }

 done := make(chan struct{})

 go func() {
  <-or(chs...)
  done <- struct{}{}
 }()
 time.Sleep(3 * time.Second)
 chs[0] <- struct{}{}
 <-done
}

Best Practices for Constructing Pipelines:
https://play.golang.org/p/4efPkGXUSoM

package main

import "fmt"

func main() {
 pipe := func(done chan struct{}, i ...int) chan int {
  retch := make(chan int)

  go func() {
   defer close(retch)
   for fi := range i {
    select {
    case <-done:
    case retch <- fi:
    }
   }
  }()

  return retch
 }

 done := make(chan struct{})
 for c := range pipe(done, 47, 38, 29) {
  fmt.Println(c)
 }
}

Fan-Out, Fan-In (auh, map-reduce):
https://play.golang.org/p/fmGAGFCuzDy
Fan-out:
Use for-range as pipeline channel to fan-out.

Take advantage of
var wg sync.WaitGroup
defer wg.done()
wg.Wait()
to fan-in.

package main

import "sync"

func main() {

 fanIn := func(done <-chan interface{}, channels ...<-chan interface{},
 ) <-chan interface{} {

  var wg sync.WaitGroup

  multiplexedStream := make(chan interface{})

  multiplex := func(c <-chan interface{}) {
   defer wg.Done()
   for i := range c {
    select {
    case <-done:
     return
    case multiplexedStream <- i:
    }
   }
  }

  wg.Add(len(channels))

  for _, c := range channels {
   go multiplex(c)
  }

  go func() {
   wg.Wait()
   close(multiplexedStream)
  }()

  return multiplexedStream
 }
 done := make(chan interface{})
 chan1 := make(chan interface{}, 1)
 chan2 := make(chan interface{}, 1)
 chan1 <- struct{}{}
 chan2 <- struct{}{}
 <-fanIn(done, chan1, chan2)
}

The or-done-channel:
https://play.golang.org/p/HsgZe8Ke9xU
Acted as a building block for other services.

package main

import (
 "fmt"
 "time"
)

func main() {

 orDone := func(done, c <-chan interface{}) <-chan interface{} {
  valStream := make(chan interface{})
  go func() {
   defer close(valStream)
   for {
    select {
    case <-done:
     return
    case v, ok := <-c:
     if ok == false {
      return
     }
     select {
     case valStream <- v:
     case <-done:
     }
    }
   }
  }()
  return valStream
 }
 ch := make(chan interface{}, 3)
 ch <- 1
 ch <- 2
 ch <- 3

 go func() {
  time.Sleep(3 * time.Second)
  close(ch)
 }()

 for v := range orDone(make(chan interface{}), ch) {
  fmt.Println(v)
 }
}

The tee-channel:
https://play.golang.org/p/bcbVnfmUdBT
interleave output.

package main

import (
 "fmt"
 "time"
)

func main() {

 orDone := func(done, c <-chan interface{}) <-chan interface{} {
  valStream := make(chan interface{})
  go func() {
   defer close(valStream)
   for {
    select {
    case <-done:
     return
    case v, ok := <-c:
     if ok == false {
      return
     }
     select {
     case valStream <- v:
     case <-done:
     }
    }
   }
  }()
  return valStream
 }

 done := make(chan interface{})
 ch := make(chan interface{}, 3)
 ch <- 1
 ch <- 2
 ch <- 3

 tee := func(done <-chan interface{}, in <-chan interface{}) (_, _ <-chan interface{}) {
  out1 := make(chan interface{})
  out2 := make(chan interface{})

  go func() {
   defer close(out1)
   defer close(out2)

   for val := range orDone(done, in) {
    var out1, out2 = out1, out2
    for i := 0; i < 2; i++ {
     select {
     case <-done:
      return
     case out1 <- val:
      out1 = nil // next loop out1 will be ignored.
     case out2 <- val:
      out2 = nil // ditto
     }
    }
   }
  }()
  return out1, out2
 }

 go func() {
  time.Sleep(3 * time.Second)
  done <- struct{}{}
 }()

 a, b := tee(done, ch)
 for v := range a {
  fmt.Printf("a val: %v\n", v)
  fmt.Printf("b val: %v\n", <-b)
 }
}

The bridge-channel:
https://play.golang.org/p/jvTDGZbFeZO
Channel contains channels.
Fan-out by assigning each sub-channels into
fan-in channel for caller to consume.

Till now you can see most of the implements from the book
use 0 buffer channel.

It's the lazy-binding technique which only processes data until
the caller consumes the processed data.

Like 'yield' (i.e coroutine, light weight thread/green thread)
in major languages, e.g C#, Python
Reference:
[C++]
http://c9x.me/articles/gthreads/intro.html

package main

import (
 "fmt"
 "time"
)

func main() {
 orDone := func(done, c <-chan interface{}) <-chan interface{} {
  valStream := make(chan interface{})
  go func() {
   defer close(valStream)
   for {
    select {
    case <-done:
     return
    case v, ok := <-c:
     if ok == false {
      return
     }
     select {
     case valStream <- v:
     case <-done:
     }
    }
   }
  }()
  return valStream
 }

 bridge := func(
  done <-chan interface{},
  chanStream <-chan <-chan interface{},
 ) <-chan interface{} {

  valStream := make(chan interface{})

  go func() {
   defer close(valStream)

   for {
    var stream <-chan interface{}

    select {
    case maybeStream, ok := <-chanStream:
     if ok == false {
      return
     }
     stream = maybeStream
    case <-done:
     return
    }

    for val := range orDone(done, stream) {
     select {
     case valStream <- val:
     case <-done:
     }
    }
   }
  }()
  return valStream
 }

 done := make(chan interface{})
 base := make(chan interface{}, 1)
 next := make(chan (<-chan interface{}), 1)
 base <- 42
 next <- base

 go func() {
  time.Sleep(3 * time.Second)
  close(base)
  close(next)
 }()

 result := bridge(done, next)
 for i := range result {
  fmt.Println(i)
 }
}

Queuing:
Buffered channels piped together then run in sequence.
The receiving type and returning type could be the same thus forms a Monad..
Reference:
http://vsdmars.blogspot.com/2017/09/fp-functor-applicative-monoid-monad.html
http://vsdmars.blogspot.com/2016/08/fp-related-readstudy-links.html



The context Package:
Familiar with the usage, skim over this section.

Timeouts and Cancellation:
Use context timeout mechanism, passing down context instance
through the calling stack.


Heartbeat:
https://play.golang.org/p/4RHoiIjnLLL
Use time.Tick(interval) https://golang.org/pkg/time/#Tick  as returning channel.
Can be used as interval probing check.

time.After can be used to check if a select statement is in healthy state within the timeout.

package main

import (
 "fmt"
 "time"
)

func main() {
 doWork := func(done <-chan interface{},
  pulseInterval time.Duration) (<-chan interface{}, <-chan 
time.Time) {

  heartbeat := make(chan interface{})
  results := make(chan time.Time)

  go func() {
   defer close(heartbeat)
   defer close(results)

   pulse := time.Tick(pulseInterval)
   workGen := time.Tick(2 * pulseInterval)

   sendPulse := func() {
    select {
    case heartbeat <- struct{}{}:
    default:
    }
   }

   sendResult := func(r time.Time) {
    for {
     select {
     case <-done:
      return
     case <-pulse:
      sendPulse()
     case results <- r:
      return
     }
    }
   }

   for {
    select {
    case <-done:
     return
    case <-pulse:
     sendPulse()
    case r := <-workGen:
     sendResult(r)
    }
   }
  }()

  return heartbeat, results
 }

 done := make(chan interface{})

 go func() {
  defer close(done)
  time.Sleep(3 * time.Second)
 }()

 h, r := doWork(done, 120*time.Second)

 for {
  select {
  case _, ok := <-h:
   if ok == false {
    return
   }
  case _, ok := <-r:
   if ok == false {
    return
   }
  case <-time.After(1 * time.Second):
   fmt.Println("worker goroutine is not healthy!")
   return
  }
 }
}

Purpose of nil channel:
Avoid busy loop.

func merge(a, b <-chan int) <-chan int {
 c := make(chan int)
 go func() {
  defer close(c)
  for a != nil || b != nil {
   select {
   case v, ok := <-a:
    if !ok {
     fmt.Println("a is done")
     a = nil
     continue
    }
    c <- v
   case v, ok := <-b:
    if !ok {
     fmt.Println("b is done")
     b = nil
     continue
    }
    c <- v
   }
  }
 }()
 return c
}

[Concurrency] [C++][Go] Wrap up - 2018

Modified

• Thie Core's cache line has the modified data.
• Data in memory won't be in other Core's cache line.

Exclusive

• Data aren't modified.
• Data in memory is the latest.
• If the Core has to evict the data inside the cache line,
  nothing need to be write back to memory.

Shared

• Data are shared between Cores' cache line.
• If this core has to modify the data, it needs to ask for data from other cores first.

Invalid

• The data in the cache line is null.

Operations:

Read

• read data from cache lines. Ask for other cores' for data.  

Read response

• Data for read request. Either from Memory or from Cores' cache.

Invalidate

• Invalidate the particular data inside Cores' cache lines.

Invalidate ack

• Response to invalidate request that the request is in the queue.      

Read invalidate

• Read + Invalidate.
• Will get read's data response and invalidate ack.

Writeback

• Write the data from cache line to memory.

Store buffer:

• Read invalidate request to other Cores' cache line for the to be modified data  is not necessary since the data response isn't needed because this Core is going to modify the data anyway.
• Thus, this core will write data to Store buffer first.
• Thus, Core will read data inside the Store Buffer with highest priority if the data exist in Store buffer and Cache line.
• However, there's an issue for Read invalidate request to other cores.
  Consider that data A in Core 1 cache, data B in Core 2 cache.
  And data A, data B has this happen before relationship.
  i.e
  In Core 1, update data A(Core 1), then update data B(Core 2).
  In Core 2, read data A(Core 1), verify data B(Core 2).

 
You see the problem. Between operation on A/B there's interleaves.
 
Core 1 updates data B, write into store buffer, send read invalidate to Core 2 on data B, at the same time, Core 2 reads data A, receives data A from Core 1, and verify data B as well, at the time, data B isn't invalidated yet.

Thus we need some wait mechanism.
i.e memory barrier.

In the above case, we need

• WMB(write memory barrier) on Core 1,
• RMB(read memory barrier) on Core 2. 

For Core 1, we do:
Update B, then WMB, then update data A.

For Core 2, we do:
Read data A, if A is old data, verify B won't happen, and if A is new data.
i.e
Core 1 updated data A, data B in Core 2 SHOULD use new one from Core 1, since it's invalidate queued.
But how to trigger Core 2 to verify invalidate queue? Before verify data B in Core 2, call RMB.
So the sequence for Core 2 will become:
Read Data A, RMB, verify data B.
     
 
WMB:

• Send read invalidate to Core 2 and till Core 2 send back invalidate ack will Core 1 flush data A from store buffer to it's cache line.

RMW:

• Verify invalidate queue, make data that is in the invalidate queue invalid the Core 2's cache line.
• While Core 2 tries to read the data, it will send a 'read' request to Core 1 for data B.

Take away:

• WMB should be issued AFTER a write to the shared data.
• RMW should be issued BEFORE a read to the shared data.

     
Reference:

1. Memory Barriers: a Hardware View for Software Hackers
2. https://en.cppreference.com/w/cpp/atomic/memory_order
3. https://en.cppreference.com/w/cpp/atomic/atomic_thread_fence

Code:

#include <atomic>
#include <iostream>
#include <thread>

using namespace std;
atomic<int> A{0};
atomic<int> B{0};

void t1()
{
    this_thread::sleep_for(1s);
    B.store(38, memory_order_relaxed);

    int a = 42;
    // WMB, prevents 'a' passing A.store.
    A.store(a, memory_order_release);
}

void t2()
{
    // RMB
    while (A.load(memory_order_acquire) != 42) {
        cout << "in while" << endl;
        // Prints 0 or 38 if B.store hasn't process yet.
        cout << B.load(memory_order_relaxed) << endl;
    }
    cout << "out while" << endl;
    // Always print 38.
    cout << B << endl;
}
int main()
{
    thread T1{t1};
    thread T2{t2};
    T1.join();
    T2.join();
}

Fence:

#include <atomic>
#include <iostream>
#include <thread>
using namespace std;
atomic<int> A{0};
atomic<int> B{0};

void t1()
{
    A.store(42, memory_order_relaxed);
    atomic_thread_fence(memory_order_release);
    // B.store can NEVER before A.store.
    B.store(38, memory_order_relaxed);
}

void t2()
{
    while (B.load(memory_order_relaxed) == 38) {
        cout << "in while loop\n";
        cout << A << endl; // Must be 42
        break;
    }
    cout << "out while loop\n";
}

int main()
{
    thread T1{t1};
    thread T2{t2};
    T1.join();
    T2.join();
}

Fence:

Release/Store

• Prevents all preceding memory operations from being reordered past subsequent writes.
• Prevents all following memory operations from being memory reordered before the write.

Acquire/Load

• Prevents all following memory operations from being reordered before this fence.
• Prevents all preceding memory operations from being reordered pass this fence.

Memory fences are NOT an acquire or release operation.

Operation:

Release operation:  store

• Cannot be reordered by compiler.
• Prevents preceding memory operations from being reordered past itself.
  i.e Any operations after a store can be reordered before the store operation.
• Any read or write operation that precedes it in program order.
  i.e those in memory_order_relaxed mode can't be reordered.

     
Acquire operation:  load

• https://en.cppreference.com/w/cpp/atomic/atomic_load
• Cannot be reordered by compiler.
• Any read or write operation that follows it in program order.
  i.e those in memory_order_relaxed mode can't be reordered.
• Those before the load can be memory ordered pass the load. Not as strong as fence.

BUT with different variable(object):
A release operation followed by a acquire operation CAN be reordered.
A acquire operation followed by a release operation CAN be reordered.
i.e
    A.store(1, std::memory_order_release);
    int b = B.load(std::memory_order_acquire);
=>
    int b = B.load(std::memory_order_acquire);
    A.store(1, std::memory_order_release);

However, keep in mind that (different variable/object) even reorder is OK for release/acquire operation, standard also depicts:
http://eel.is/c++draft/intro.multithread#intro.progress-18
An implementation should ensure that the last value (in modification order) assigned by an atomic or synchronization operation will become visible to all other threads in a finite period of time.

Reference:

https://stackoverflow.com/questions/14687703/what-c11-atomic-operations-memory-orders-guarantees-freshness

https://stackoverflow.com/questions/8819095/concurrency-atomic-and-volatile-in-c11-memory-model/8833218#8833218

i.e
If an store operation follows a for/while loop and a load operation,
the compiler shouldn't reorder load before store due to it can't
reasoning that the for/while loop is finite thus other thread can see thread store result in a finite time.
   
Reference:

1. [Preshing] Can Reordering of Release/Acquire Operations Introduce Deadlock?
2. [Bruce Dawson] In Praise of Idleness
3. [Golang bug list] cmd/compile: go1.8 regression: sync/atomic loop elided #19182

Hardware Memory Model:

Weak memory model

• ARM/Power PC

Strong memory model

• x86/64
• Sequential Consistence (software)

Reordering:

Sequentially Consistent types:

• Java: volatile variables
• C++11: atomic (default)

Explicit Compiler Barriers:
gcc:
    asm volatile("" ::: "memory");
Macro:
    #define COMPILER_BARRIER() asm volatile("" ::: "memory")

source:
https://elixir.bootlin.com/linux/latest/source/arch/x86/include/asm/barrier.h#L22

figure source: (https://www.youtube.com/watch?v=ZQFzMfHIxng)

Don't consider Sequential Consistency is SLOW; correctness is the highest priority.

Implied Compiler Barriers:
C++11:

• Every non­-relaxed atomic operation acts as a compiler barrier.
  這裡是compiler reordering, 不是memory reordering.
• Every function containing a compiler barrier must act as a compiler barrier itself, even the function is inlined.
• The majority of function calls act as compiler barriers, whether they contain their own compiler barrier or not due to it's coming from different TU. 
• But does not include inline functions, functions declared with the pure attribute, and cases where link ­time code generation is used.          

Reference:

1. [Implications of pure and constant functions] https://lwn.net/Articles/285332/

What about Golang?

goroutine act as 'user space thread', 

i.e it's runtime memory location is allocated on the heap.

Inside a single goroutine, the compiler is allowed to re-arrange

expressions as long as the reordering does not change the behavior within that goroutine as defined by the language specification. 

Within a single goroutine, the happens-before order is the order expressed by the program.

i.e

a := 42
if a == 42 {
    // always true.
}

// b will always be 42
b := a
// within other goroutines, the observe of a == 42 and c == 38 sequence is not guaranteed.
c := 38  

Reads and writes of values larger than a single machine word behave as multiple machine-word-sized operations in an unspecified order.

Initialization:

• If a package p imports package q, the completion of q's init functions happens before the start of any of p's.
• The start of the function main.main happens after all init functions have finished.

Goroutine creation:

• The go statement that starts a new goroutine happens before the goroutine's execution begins.
• i.e go statement act as a barrier function call in C/C++ which won't be reordered.

Goroutine destruction:

• Can happen any time.
• Be ware that if a goroutine that updates a global value and do nothing (i.e using channel etc.), an aggressive compiler could delete the goroutine entirely for optimization.
  i.e just modify the global variable without creating a goroutine.
  https://github.com/golang/go/issues/19182

Channel communication:

• A send on a channel happens before the corresponding receive from that channel completes.
• The closing of a channel happens before a receive that returns a zero value because the channel is closed.
• A receive from an un-buffered channel happens before the send on that channel completes.
• The kth receive on a channel with capacity C happens before the k+Cth send from that channel completes.

i.e the famous:
Do not communicate by sharing memory; instead, share memory by communicating.

No more memory store/load operation from programmer's point of view.

The Channel acted as the sequential consistence/memory fence contract.

Reference:

https://golang.org/ref/mem

https://blog.golang.org/share-memory-by-communicating

https://github.com/8l/go-learn

https://dougrichardson.org/2016/01/23/go-memory-allocations.html

[Preventing stack guard-page hopping] https://lwn.net/Articles/725832/

[Go] The Go scheduler

Reference:
Morsing's The Go Scheduler article
Dmitry Vyukov's Scalable Go Scheduler Design doc
MIT Paper: Scheduling Multithreaded Computations by Work Stealing
Intel TBB Task Scheduler
Go's work-stealing scheduler
Command trace

Why a userspace scheduler for go?
Because of garbage collector.

The Go garbage collector requires that all threads are stopped when running a collection and that memory must be in a consistent state.
This involves waiting for running threads to reach a point where we know that the memory is consistent.

Golang is using M:N thread model, i.e M as gorotines, N as OS threads.

layout:

G: goroutine (aka. Task, can be stolen)
M: OS thread (machine, aka. OS thread)
P: processor, NOT CPU processor, but a logical one (aka. context, can steal, own 1 M)
The number of P is set to GOMAXPROCS/runtime function GOMAXPROCS()
Each P has it's own local runqueue, which contains Gs. 
This design relieve mutex contention on single thread. 
Why? Because there's no mutex variable crossing CPU cores , which there's no WB/RB barriers involves.

Why P(context)? Because P can be moving around the threads.
If 1 P is blocked due to it's goroutine called a syscall, we could have that goroutin + M stay and moving the P with it's runqueue to other thread to run, consider P as a package can be move around to other threads.

The scheduler makes sure there are enough threads to run all contexts.

When the syscall returns, the (blocking) thread must try and get a context(P) in order to run the returning goroutine.
The normal mode of operation is to steal a context(P) from one of the other threads. If it can't steal one, it will put the goroutine on a global runqueue, put itself(i.e the 'was' blocking thread) on the thread cache and go to sleep.

Global runqueue:

• Global queue: G's can be put into here if original P is blocked and resumed(awake) but can't grab a M.
• The global runqueue is a runqueue that contexts(P) pull from when they run out of their local runqueue.
• Contexts(P) also periodically check the global runqueue for goroutines. Otherwise the goroutines on global runqueue could end up never running because of starvation.

Logic sequence:
runtime.schedule() {
    // only 1/61 of the time, check the global runnable queue for a G.
    // if not found, check the local queue.
    // if not found,
    //     try to steal from other Ps.
    //     if not, check the global runnable queue.
    //     if not found, poll network.
}

Task Stealing:

• If local runqueue is drained, look into global runqueue.
• If the global runqueue is empty, the P will steal from other P's local runquene, half of them.

Spinning threads(M):

A thread is spinning if:

• An M with a P assignment is looking for a runnable goroutine.
• An M without a P assignment is looking for available Ps.
• Scheduler also unparks an additional thread and spins it when it is readying a goroutine if there is an idle P and there are no other spinning threads.

Logical Processor: (This is the essential of Go)

https://groups.google.com/forum/?utm_medium=email&utm_source=footer#!msg/golang-nuts/5Zo403s3LC0/P4JwsHsKAQAJ

The purpose of a P is to limit the amount of total concurrency running Go code. 

By default set the number of P's to the number of CPU cores on the system (including hyperthreading).  

The user can control it by setting the GOMAXPROCS environment variable, and the program can control it by calling runtime.GOMAXPROCS

M's, on the other hand, which are operating system threads, are started as needed, so the user and program have no control over them.  

G's, which are goroutines, are started by the program but there is no way to limit the total number of goroutines. 

So using P's is how the Go runtime tries to keep the program running efficiently without thrashing.

Design Doc:

https://docs.google.com/document/d/1TTj4T2JO42uD5ID9e89oa0sLKhJYD0Y_kqxDv3I3XMw/edit