Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Go's Runtime Scheduler

JBD
November 05, 2017

Go's Runtime Scheduler

JBD

November 05, 2017
Tweet

More Decks by JBD

Other Decks in Technology

Transcript

  1. scheduling? • Controlling the distribution of work over available resources.

    • Schedulers you might have heard of: process schedulers, network schedulers, container schedulers.
  2. go’s runtime scheduler • Distributes goroutines over multiple OS threads

    that runs on available processors. • Determine the runnable goroutines, prioritize and run them, park them, and repeat.
  3. scheduler • M:N scheduler. • M goroutines need to be

    scheduled on N OS threads that runs on available processors.
  4. T1 P1 P2 T3 T2 T4 T5 G1 G2 G3

    G10 G5 G6 G7 goroutines threads processors runnable queue G8 G4 G9 G0 not runnable goroutines
  5. challenges • Holding a global lock to manage goroutines is

    costly. • Go is often used to write I/O block heavy programs. Constant preemption of OS threads has significant overhead.
  6. work sharing or stealing? • Work sharing: After creation of

    new threads, a process attempts to migrate some of them to the other processors. • Work stealing: An underutilized processor actively looks for other processor’s threads and steal some.
  7. T1 P1 P2 T3 T2 T4 T5 G1 G9 G0

    G11 G12 G16 goroutines threads processors global queue G2 G3 G4 local queue local queue (empty) steal
  8. work stealing runtime.schedule() {
 // only 1/61 of the time,

    check the global runnable queue for a goroutine.
 // if not found, check the local queue.
 // if not found,
 // try to steal from other Ps.
 // if not found, check the global runnable queue.
 // if not found, poll network.
 }
  9. spinning • Improve perf both for high throughput and I/O

    bounded programs. • Prefer to burn some CPU cycles rather than preemption.
  10. spinning: goroutine to run T1 P1 G2 G3 G4 G6

    G7 search for runnable goroutines
  11. • Scheduler utilizes processing power by scheduling goroutines on the

    underutilized processors. • Scheduler spins threads to avoid constant preemption.