Go coroutine management

The biggest characteristic of GO language is high concurrency, and the implementation method is coroutine. Let’s talk about go coroutines today.

What is a coroutine

In short, a coroutine is a lightweight, stand-alone block of code defined by the GO language itself. Analogous to threads at the operating system level, we can think of a coroutine as a thread. How do we normally start a thread? A method is passed in, and its internal implementation is to call the system interface to execute the method (code block). Similarly, a coroutine executes a method (code block), so it can be understood that a coroutine is a thread, no difference.

Why coroutines

Why have a coroutine when a coroutine is a thread? Aren’t threads enough?

Let’s look at the disadvantages of threads first. Suppose you have a machine with four cpus that, when running a program on it, can run up to four threads at the same time. When all four threads reach a choke point, they are suspended, and the suspension requires operating system access. The operating system suspends the blocked thread and then runs other threads that have not yet started executing or that have not blocked. This involves switching between kernel and user mode, which is very time consuming, and because the CPU schedules threads in a polling time slice, when a thread is blocked but its time slice has not expired, that time is blocked and wasted. There are two problems: 1. It is very time-consuming for the operating system to switch threads; 2. CPU time slices are wasted before the blocked thread runs out of time. Problem 2 May not be solved. When a coroutine is blocked, the corresponding P will be unlocked with G and M, and P will choose other M to continue to execute other G in the corresponding queue, so as to achieve high concurrency. To discuss)

To solve these two problems, Go designers proposed the concept of coroutines. Like threads, coroutines execute a block of code, but they are implemented at the go language level and the underlying operating system is unaware of them. That is, coroutines are all user-mode. It can be understood that a thread contains multiple coroutines. The coroutine is that go defines a structure at the language level, corresponding to a code block, which contains a small amount of information such as the PC pointer and stack of the code block, less information than the thread. Problem 1 solved: The coroutine is defined by the GO language itself, so it is user-mode. All coroutines run in user-mode. To the operating system, only one thread is aware of what is going on inside the thread. The management and switching of coroutines are controlled by GO itself with the code, independent of the operating system, so the switching speed between coroutines is very fast, and does not involve the CPU, memory and other resources of the operating system. Problem 2: when a collaborators cheng is blocked, the go coroutines manager will take collaborators that hang cheng, continue to carry out the other has not yet run coroutines or coroutines, not blocked, for the operating system has always been a thread running, the language of the SAO operation make full use of the thread is blocked and time slice before maturity of this period of time.

How do I manage coroutines

The go language defines its own structure, called a coroutine. It controls the scheduling and execution of multiple coroutines (constructs) in user mode. How does it work?

Go introduces the concept of Processor (P). A P represents a logical processor for scheduling G. This is called a logical processor and generally corresponds to a physical processor

M(Machine), can be understood as a thread, the thread that actually executes P.

The relationship between G, P and M is shown as follows:

Each P has a corresponding G queue. P binds thread M0 to execute the coroutine G0. When a blocking event occurs, the Runtime binds a new thread M1 to P to execute the new thread

The data structure

The structure of G

Important members

  • Stack: the stack space currently used by G, with lo and HI members
  • Stackguard0: a value that checks if the stack space is sufficient, below which the stack expands, and 0 is used by the GO code
  • Stackguard1: checks if the stack space is sufficient, below which the stack expands, 1 is used by native code
  • M: m of the current g
  • Sched: scheduling data of G. When G is interrupted, the current PC and RSP will be saved to this value, and the value will be used when g is restored
  • Atomicstatus: indicates the current status of g
  • Schedlink: The next G, which is used when in a linked list structure
  • Preempt: indicates whether g is preempted
  • Lockedm: does G require the execution to return to M? Sometimes if G breaks the recovery will require the execution to use the original M

state

  • Idle (_Gidle): G is newly created and not initialized
  • To run (_Grunnable): G is in the run queue waiting for M to run
  • Running (_Grunning): indicates that M is running G, and M will have a P
  • System call (_Gsyscall): M is running the system call from G, and M does not own P
  • Waiting (_Gwaiting): G is waiting for some condition to complete. G is not running or in a run queue (possibly in a channel’s wait queue).
  • Aborted (_Gdead): indicates that G is not in use and may have completed execution (and is waiting for reuse in freelist)
  • Stack replication (_Gcopystack): indicates that G is taking a new stack space and copying the old contents over (to prevent GC scanning)

The structure of the P

Important members

  • Status: indicates the current status of P
  • Link: Next p, when p is used in the list structure
  • M: m with this P
  • McAche: local allocator used to allocate memory
  • Runqhead: indicates the outgoing queue number of the local run queue
  • Runqtail: indicates the queue entry number of the local run queue
  • Runq: An array of local runqueues that can hold 256 gigabytes
  • Gfree: a free list of G instances that can be reused after changing to _Gdead
  • GcBgMarkWorker: The worker function of the background GC, which M will execute first if it exists
  • GCW: The local work queue for GC, which will be examined in the next GC article

state

  • Idle (_Pidle): when M finds that there is no G waiting to be run, it will sleep, and the P owned by M will become idle and be added to the idle P linked list
  • Running (_Prunning): When M has a P, the state of P changes to running. When M runs, G uses the resources in P
  • In system calls (_Psyscall): When GO calls native code, which in turn calls GO code, the P used changes to this state
  • GC stopping (_Pgcstop): P changes to this state when GC stops the entire world (STW)
  • Aborted (_Pdead): When the number of P changes at run time, and the number decreases, the excess P becomes this state

The structure of the M

Important members

  • G0: Special G for scheduling, to which system calls are switched when scheduled and executed
  • Curg: the currently running G
  • P: indicates the current p
  • Nextp: when M is awakened, M will have this P
  • Park: Semaphore used by M when it sleeps, which is used to wake M up
  • Schedlink: The next M, used when m is in a linked list structure
  • McAche: local allocator used to allocate memory, same as p.mcache (copied over if you have P)
  • Lockedg: indicates the value of lockedm

state

  • Spinning: M is fetching G from the run queue, and M will have a P
  • In executing go code: M is executing go code, and M has a P
  • In executing native code: M is executing native code or blocking syscall, and M does not have P
  • Hibernating: when M finds no G to run, it goes to sleep and adds it to the free M list. At this time, M does not own P

Spinning is an important state, and whether you need to wake up or create a new M depends on the number of M’s in the current spin.

Local run queue

There are multiple runqueues in GO that hold G ready to run (_Grunnable), local and global runqueues in each P. When G is enqueued to be run, it will be added to the local run queue of current P preferentially. When M obtains G to be run, it will also obtain G from the local run queue of P preferentially. Thread locks are not required for enqueueing and dequeuing of the local run queue.

The number of local runqueues is limited. When the number of local runqueues reaches 256, the local runqueues are queued to the global runqueues. The data structure of the local run queue is the ring queue, consisting of a 256-length array and two ordinals (head, tail).

When M fetches G from the local run queue of P, it will attempt to steal half of G from another P if it finds that the local run queue is empty. This mechanism is called Work Stealing

Global run queue

The global run queue is stored in the global variable sched, and thread locks are required to enqueue and dequeue global runs. The data structure of the global run queue is a linked list, consisting of two Pointers (head, tail).

Free M linked list

When M finds no G to run, it goes to sleep and is added to the free M list, which is stored in the global variable sched. Dormant M waits for a semaphore (M. Park), which is used by awakened M.

Go needs to ensure that there are enough M to run G through the following mechanism:

  • After joining G to run, if there is currently no spin M but there is a free P, wake up or create a new M
  • When M leaves the spin state and is ready to run out of the queue G, if there is currently no spin M but there is a free P, wake up or create a new M
  • When M leaves the spin state and is ready to sleep, all runqueues are checked again after leaving the spin state, and G re-enters the spin state if it is waiting to run

Because the “enqueued ready to run G” and “M out of spin state” are performed at the same time, go uses this check order:

Enqueue G to run => Memory barrier => Check the M number of current spins => Wake up or create an M to reduce the M number of current spins => Memory barrier => Check whether all run queues have G to run => sleep

This ensures that G will not be queued, and there will be idle resource P, but no M to execute.

Free P linked list

All local operation in the queue when P G after operation, and can’t get G from other places, have P M will release P and enter a dormant state, the release of P becomes idle and added to the free list, P free P list stored in global variables sched to run next time P G team if it is found that there are free, But if you don’t have M in the spin, you wake up or you create a new M, and M will have this P, and P will go back to the running state.

How do coroutines communicate with each other

Communication between coroutines is realized through channel

Channel data structure

  • Qcount: the number of elements in the current queue
  • Dataqsiz: The number of elements that a queue can hold. A value of 0 indicates that this channel has no buffer
  • Buf: Buffer of a queue, structured as a ring queue
  • Elemsize: indicates the size of the element
  • Closed: Indicates whether the system is closed
  • Elemtype: specifies the type of the element, which is used to determine whether to invoke write barriers
  • Sendx: Serial number of the sending element
  • Recvx: Serial number of the received element
  • Recvq: The list of Gs currently waiting to receive data from a channel (the actual type is a list of Sudog)
  • Sendq: list of G currently waiting to send data to channel (actual type is sudog list)
  • Lock: Thread lock used to operate channels

Process of writing data to a channel

Chansend1 calls the runtime.chansend1 function, which calls the chansend function.

  • Check if channel.recvq has G for the waiting receiver
    • If yes, the channel has no buffer or the buffer is empty
    • Call send
      • If sudog.elem is not nil, call the sendDirect function to copy the element directly from the sender
      • The sudog.elem waiting to receive is a pointer to the memory of the receive target, if the receive target is _ then elem is nil and copy can be omitted
      • The sudog.elem waiting to be sent is a pointer to the memory of the source target
      • After copying, call goReady to restore the sender’s G
        • Switch to G0 and call ready, and then switch back
          • Change the state of G from waiting to waiting (_Grunnable)
          • Put G on the local run queue of P
          • If there is currently a free P, but no spinning M(nmspinning is equal to 0), wake up or create a new M
    • After getting the data from the sender and waking up G, you can return from Chansend
  • Determines whether elements can be put into a buffer
    • If the buffer has free space, the element is put into the buffer and returned from chansend
  • There is no buffer or the buffer is full and the sender’s G needs to wait
    • Gets the current g
    • Create a new sudog
    • Set sudog.elem = to a pointer to sending memory
    • Set sudog.g = g
    • Set sudog.c = channel
    • Set g.waiting = sudog
    • Put sudog in channel.sendq
    • Call the goparkunlock function
      • Call the gopark function
        • The park_m function is called through the McAll function
          • The McAll function, as described above, saves the current state to g.ched, then switches to g0 and g0 stack space and executes the specified function
          • The park_m function first changes the state of G from running (_Grunning) to waiting (_Gwaiting)
          • The dropg function is then called to disassociate M from G
          • Call the pass-by unlock function, which unlocks channel.lock
          • Finally, the schedule function is called to resume scheduling
  • Resuming from here indicates either that the message was sent successfully or that the channel is closed
    • Check if sudog.param is nil, if nil means the channel is closed, and panic is thrown
    • Otherwise, release sudog and return

The process of receiving data from a channel

The runtime.chanrecv1 function calls the runtime.chanrecv1 function.

  • Check for waiting sender G in channel.sendq
    • If yes, the channel has no buffer or the buffer is full. These two cases need to be handled separately (to ensure the same order of incoming and outgoing queues).
    • Call the recv function
      • If there is no buffer, the recvDirect function is called to copy the element directly to the receiver
      • If there are buffers, the buffer is full
        • Copies the next element in the queue to be dequeued directly to the receiver
        • Copies the sent element to the position in the queue where it was just unqueued
        • The buffer is still full, but both the send and receive numbers increase by one
      • After copying, call goReady to restore G of the receiver, same as above
    • After handing the data to the receiver and waking up G, you can return from Chanrecv
  • Determines whether elements can be retrieved from the buffer
    • If the buffer has an element, it is fetched directly and returned from chanrecv
  • No buffer or no element in the buffer, G of the receiver needs to wait
    • Gets the current g
    • Create a new sudog
    • Set sudog.elem = to a pointer to receive memory
    • Set sudog.g = g
    • Set sudog.c = channel
    • Set g.waiting = sudog
    • Put sudog into channel.recvq
    • Call goparkunlock and do the same
  • Resuming from here indicates that the channel has been successfully received or closed
    • Check if sudog.param is nil, which means the channel is closed
    • Unlike sending, receiving does not discard panic, but sends a return value to inform a channel that it has closed
    • Release sudog and return

Close the Channel process

  • Closing a channel actually calls the Closechan function, and the flow is as follows:
  • Set channel.closed = 1
  • Enumeratechannel. recvq, clear them sudog.elem, set sudog.param = nil
  • Enumerating channel.sendq, set sudog.elem = nil, set sudog.param = nil
  • Call the goReady function to restore G for all receivers and senders

If G ched needs to wait for resources, the running state of G is recorded in G ched, then the state is changed to _Gwaiting, and then M can continue to run other G. Where G in wait is stored and when to resume is determined by the waiting resource. The above wait for a channel will put G in the linked list of the channel.

Waiting for network resources can be seen in netpoll related processing, netpoll processing is different in different systems, you can see for yourself.

This paper mainly refers to the document [1], thanks to the author

reference

[1] Golang source code exploration (two) coroutine implementation principle [2] Golang coroutine scheduling two: coroutine switching principle [3] What is coroutine (Goroutine), how do they work? [4] Introduction to Go coroutine