Go's Scheduler Steals Half-Idle Cores: Work Stealing, Spinning and the Global Run Queue

TL;DR: Go does not hand goroutines to threads and hope for the best. Every processor (P) owns a private 256-slot run queue plus one extra “run next” slot. When a P runs dry, its M turns into a spinning thief: it picks a victim P at random, grabs half that queue in one atomic batch, and keeps going until it finds work or gives up and parks on a futex.

Read the Go source (the 1.28 development tree) and the first thing you notice about src/runtime/proc.go is that it opens with a design essay, not code. That essay is the whole scheduler in English, and it is worth reading before anything else.

The G/M/P model

go
// src/runtime/proc.go:24
// Goroutine scheduler
// The scheduler's job is to distribute ready-to-run goroutines over worker threads.
//
// The main concepts are:
// G - goroutine.
// M - worker thread, or machine.
// P - processor, a resource that is required to execute Go code.
//     M must have an associated P to execute Go code, however it can be
//     blocked or in a syscall w/o an associated P.
//
// Design doc at https://golang.org/s/go11sched.

Three nouns, one rule: a P is the licence to run Go code. An M (an OS thread) can exist without a P — blocked in a syscall, parked, inside cgo — but a goroutine only makes progress while some M holds a P. GOMAXPROCS is the number of Ps, which is the real parallelism limit.

The scheduler’s job is to distribute ready-to-run goroutines over worker threads. The interesting part is what happens when the distribution is uneven: one P with a deep queue, its neighbour with nothing at all.

The local run queue: a 256-slot ring

Each P owns a fixed-size ring buffer of goroutine pointers. Not a slice, not a linked list: a fixed array with a head and a tail index.

go
// src/runtime/runtime2.go:804
	// Queue of runnable goroutines. Accessed without lock.
	runqhead uint32
	runqtail uint32
	runq     [256]guintptr
	// runnext, if non-nil, is a runnable G that was ready'd by
	// the current G and should be run next instead of what's in
	// runq if there's time remaining in the running G's time
	// slice. It will inherit the time left in the current time
	// slice. If a set of goroutines is locked in a
	// communicate-and-wait pattern, this schedules that set as a
	// unit and eliminates the (potentially large) scheduling
	// latency that otherwise arises from adding the ready'd
	// goroutines to the end of the run queue.
	//
	// Note that while other P's may atomically CAS this to zero,
	// only the owner P can CAS it to a valid G.
	runnext guintptr

text
   P0                                   P1
   +-----------------------------+       +-----------------------------+
   | runnext : *g   (one slot)   |       | runnext : *g                |
   +-----------------------------+       +-----------------------------+
   | runq[0..255]  (ring)        |       | runq[0..255]                |
   |  head=12  tail=19           |       |  head=3   tail=3  (empty)  |
   |  G12 G13 G14 G15 G16 G17 G18 |       |                             |
   +-----------------------------+       +-----------------------------+
            ^                                        ^
            |                                        |
     owner P writes here              a thief P may steal half of this

The fixed 256-entry size is deliberate: the owner P can put and take goroutines without taking any lock, because the queue is private and only the owner writes to it. Everything else uses atomics.

go
// src/runtime/proc.go:7565
	if next {
	retryNext:
		oldnext := pp.runnext
		if !pp.runnext.cas(oldnext, guintptr(unsafe.Pointer(gp))) {
			goto retryNext
		}
		if oldnext == 0 {
			return
		}
		// Kick the old runnext out to the regular run queue.
		gp = oldnext.ptr()
	}

retry:
	h := atomic.LoadAcq(&pp.runqhead) // load-acquire, synchronize with consumers
	t := pp.runqtail
	if t-h < uint32(len(pp.runq)) {
		pp.runq[t%uint32(len(pp.runq))].set(gp)
		atomic.StoreRel(&pp.runqtail, t+1) // store-release, makes the item available for consumption
		return
	}
	if runqputslow(pp, gp, h, t) {
		return
	}
	// the queue is not full, now the put above must succeed
	goto retry

Note runnext: when a goroutine readies another one (an unbuffered channel handoff, say), the new goroutine goes into the runnext slot and inherits the remaining time slice of the current goroutine. That is how a communicate-and-wait pattern between two goroutines runs as a unit instead of paying a scheduling round trip.

Note also that the ring is a FIFO of readiness, not of goroutine creation, and runnext deliberately jumps the queue.

When the local queue is full, the P spills half of it plus the new goroutine onto the global queue (runqputslow), because moving 129 goroutines to the global queue under a lock is cheaper than moving them one at a time.

The global run queue

The global queue is a linked list of goroutines guarded by sched.lock. It exists for two reasons: overflow from a local queue, and goroutines made runnable by something that is not a P (a timer, the netpoller, a signal handler).

go
// src/runtime/proc.go:7320
func globrunqput(gp *g) {
	assertLockHeld(&sched.lock)

	sched.runq.pushBack(gp)
}

A P takes from the global queue in batches, not one goroutine at a time, and dumps the rest into its own local queue:

go
// src/runtime/proc.go:7364
func globrunqgetbatch(n int32) (gp *g, q gQueue) {
	assertLockHeld(&sched.lock)

	if sched.runq.size == 0 {
		return
	}

	n = min(n, sched.runq.size, sched.runq.size/gomaxprocs+1)

	gp = sched.runq.pop()
	n--

	for ; n > 0; n-- {
		gp1 := sched.runq.pop()
		q.pushBack(gp1)
	}
	return
}

The batch size is capped at size/gomaxprocs+1: with many Ps, each P takes only a small slice, so one P cannot hoard work while the others starve. One lock acquisition is amortised over many goroutines.

The global queue is not consulted on every scheduling decision — that would serialise everything on one mutex. It is checked once every 61 ticks:

go
// src/runtime/proc.go:3459
	// Check the global runnable queue once in a while to ensure fairness.
	// Otherwise two goroutines can completely occupy the local runqueue
	// by constantly respawning each other.
	if pp.schedtick%61 == 0 && !sched.runq.empty() {
		lock(&sched.lock)
		gp := globrunqget()
		unlock(&sched.lock)
		if gp != nil {
			return gp, false, false
		}
	}

61 is a prime, so it does not line up with any common periodic pattern.

Stealing: half a queue at a time

Here is the core of the thing. A thief does not take one goroutine at a time from a victim — that would require the victim to release its queue slot by slot while the thief grabs them. Instead the thief grabs a batch with a single CAS on the victim’s head pointer, taking half of the queue.

go
// src/runtime/proc.go:7733
func runqgrab(pp *p, batch *[256]guintptr, batchHead uint32, stealRunNextG bool) uint32 {
	for {
		h := atomic.LoadAcq(&pp.runqhead) // load-acquire, synchronize with other consumers
		t := atomic.LoadAcq(&pp.runqtail) // load-acquire, synchronize with the producer
		n := t - h
		n = n - n/2
		if n == 0 {
			if stealRunNextG {
				// Try to steal from pp.runnext.
				if next := pp.runnext; next != 0 {
					if pp.status == _Prunning {
						if mp := pp.m.ptr(); mp != nil {
							if gp := mp.curg; gp == nil || readgstatus(gp)&^_Gscan != _Gsyscall {
								// Sleep to ensure that pp isn't about to run the g
								// we are about to steal.

The n = n - n/2 line is the whole trick: half the victim’s queue, rounded down. The thief copies the entries into its own ring buffer and commits the theft with one CAS; if the CAS fails, the victim was concurrently taking work and the thief simply retries. No locks, no waiting, no corruption.

The steal takes only half so the victim keeps a share. A thief that took everything could ping-pong work back and forth with the owner and starve it. Half is a compromise: enough to be worth the trip, not enough to starve the victim.

go
// src/runtime/proc.go:7806
func runqsteal(pp, p2 *p, stealRunNextG bool) *g {
	t := pp.runqtail
	n := runqgrab(p2, &pp.runq, t, stealRunNextG)
	if n == 0 {
		return nil
	}
	n--
	gp := pp.runq[(t+n)%uint32(len(pp.runq))].ptr()
	if n == 0 {
		return gp
	}
	h := atomic.LoadAcq(&pp.runqhead) // load-acquire, synchronize with consumers
	if t-h+n >= uint32(len(pp.runq)) {
		throw("runqsteal: runq overflow")
	}
	atomic.StoreRel(&pp.runqtail, t+n) // store-release, makes the item available for consumption
	return gp
}

One goroutine from the stolen batch is returned to run immediately; the rest stay in the thief’s local queue as warm work. Note that the stolen goroutines are copied into the thief’s own ring at its runqtail, and the new tail is published with a single store-release.

Picking a victim at random

Stealing from the same P every time would hammer one contended cache line, so the victim is chosen from a pseudo-random permutation of all Ps.

go
// src/runtime/proc.go:3847
func stealWork(now int64) (gp *g, inheritTime bool, rnow, pollUntil int64, newWork bool) {
	pp := getg().m.p.ptr()

	ranTimer := false

	const stealTries = 4
	for i := 0; i < stealTries; i++ {
		stealTimersOrRunNextG := i == stealTries-1

		for enum := stealOrder.start(cheaprand()); !enum.done(); enum.next() {
			p2 := allp[enum.position()]
			if pp == p2 {
				continue
			}

Four rounds, each round walking a different permutation of all Ps. The permutation is not a shuffle; it is a walk with a stride coprime to the number of Ps, so every P is visited exactly once per round:

go
// src/runtime/proc.go:8087
func (ord *randomOrder) reset(count uint32) {
	ord.count = count
	ord.coprimes = ord.coprimes[:0]
	for i := uint32(1); i <= count; i++ {
		if gcd(i, count) == 1 {
			ord.coprimes = append(ord.coprimes, i)
		}
	}
}

func (ord *randomOrder) start(i uint32) randomEnum {
	return randomEnum{
		count: ord.count,
		pos:   i % ord.count,
		inc:   ord.coprimes[i/ord.count%uint32(len(ord.coprimes))],
	}
}

Start at a random offset, walk with a random coprime stride. Every P gets visited, in a different order each time, without shuffling an array.

Spinning: the scheduler’s most unusual idea

When a P finds nothing in its own queue, it does not immediately park its thread. It first steals. And stealing means the M is “spinning” — burning CPU looking for work.

go
// src/runtime/proc.go:3531
	// Spinning Ms: steal work from other Ps.
	//
	// Limit the number of spinning Ms to half the number of busy Ps.
	// This is necessary to prevent excessive CPU consumption when
	// GOMAXPROCS>>1 but the program parallelism is low.
	if mp.spinning || 2*sched.nmspinning.Load() < gomaxprocs-sched.npidle.Load() {
		if !mp.spinning {
			mp.becomeSpinning()
		}

		gp, inheritTime, tnow, w, newWork := stealWork(now)
		if gp != nil {
			// Successfully stole.
			return gp, inheritTime, false
		}

Note the limit: at most half as many spinning Ms as there are busy Ps. If your program is single-threaded but GOMAXPROCS is 64, the runtime will not let 64 threads burn CPU hunting for work that does not exist. It will let a couple.

Becoming a spinner is a counter increment, and leaving that state is a counter decrement plus a possible wake-up:

go
// src/runtime/proc.go:4042
func resetspinning() {
	gp := getg()
	if !gp.m.spinning {
		throw("resetspinning: not a spinning m")
	}
	gp.m.spinning = false
	nmspinning := sched.nmspinning.Add(-1)
	if nmspinning < 0 {
		throw("findRunnable: negative nmspinning")
	}
	// M wakeup policy is deliberately somewhat conservative, so check if we
	// need to wakeup another P here. See "Worker thread parking/unparking"
	// comment at the top of the file for details.
	wakep()
}

So a thread that finds work stops spinning and, in doing so, may start a different thread spinning in its place. The invariant the runtime wants is roughly: if there is runnable work and an idle P, some thread should be looking for it.

The delicate dance before parking

Before a thread gives up and parks, it must release its P, and the moment it releases the P is a race: work could be submitted at the same instant. The runtime’s comment on this is the best piece of prose in the file.

go
// src/runtime/proc.go:3641
	// Delicate dance: thread transitions from spinning to non-spinning
	// state, potentially concurrently with submission of new work. We must
	// drop nmspinning first and then check all sources again (with
	// #StoreLoad memory barrier in between). If we do it the other way
	// around, another thread can submit work after we've checked all
	// sources but before we drop nmspinning; as a result nobody will
	// unpark a thread to run the work.

The protocol: drop nmspinning, then re-check every source of work (global queue, all local queues, GC work, timers). If you find work, restore the spinning state and go around again. The ordering is not arbitrary; the comment explains exactly why the other order loses work.

Waking and parking

When goroutines are made runnable, someone has to notice. wakep() starts an M if there is an idle P and nobody is already spinning.

go
// src/runtime/proc.go:3221
func wakep() {
	// Be conservative about spinning threads, only start one if none exist
	// already.
	if sched.nmspinning.Load() != 0 || !sched.nmspinning.CompareAndSwap(0, 1) {
		return
	}

	// Disable preemption until ownership of pp transfers to the next M in
	// startm. Otherwise preemption here would leave pp stuck waiting to
	// enter _Pgcstop.
	//
	// See preemption comment on acquirem in startm for more details.
	mp := acquirem()

	var pp *p
	lock(&sched.lock)
	pp, _ = pidlegetSpinning(0)
	if pp == nil {
		if sched.nmspinning.Add(-1) < 0 {
			throw("wakep: negative nmspinning")
		}
		unlock(&sched.lock)
		releasem(mp)
		return
	}

wakep is called from ready(), the function that moves a goroutine from waiting to runnable, and after a timer fires. The policy is deliberately conservative: if a spinner is already out there looking for work, do not wake another thread, because the spinner will probably find it.

When the spinner has nothing, it releases its P, puts itself on the idle M list, and blocks on a futex:

go
// src/runtime/proc.go:2999
// Stops execution of the current m until new work is available.
// Returns with acquired P.
func stopm() {
	gp := getg()

	if gp.m.locks != 0 {
		throw("stopm holding locks")
	}
	if gp.m.p != 0 {
		throw("stopm holding p")
	}
	if gp.m.spinning {
		throw("stopm spinning")
	}

	lock(&sched.lock)
	mput(gp.m)
	unlock(&sched.lock)
	mPark()
	acquirep(gp.m.nextp.ptr())
	gp.m.nextp = 0
}

The three throw checks are the invariants: you cannot park while holding locks, holding a P, or while spinning. mPark sleeps on gp.m.park, a note — a one-shot futex word set by notewakeup with a single atomic exchange. Parking an M costs one futex sleep; waking it costs one atomic exchange and one futex wake. That is the price of not burning a core.

Timers are per-P too

Timers live in a per-P heap, and the scheduler checks them at the top of every round with pp.timers.check(0, nil), which returns the time of the next timer to fire. When a timer fires, the goroutines it readies land on a run queue — usually the local one of the P that ran the timer. sysmon, the runtime’s background thread, is what forces long-running goroutines to give up their P, and it deliberately refuses to sleep deeply while schedtrace is enabled:

go
// src/runtime/proc.go:6571
		// sysmon should not enter deep sleep if schedtrace is enabled so that
		// it can print that information at the right time.
		//
		// It should also not enter deep sleep if there are any active P's so
		// that it can retake P's from syscalls, preempt long running G's, and
		// poll the network if all P's are busy for long stretches.

Trade-offs

What work stealing buys you. Automatic load balancing with no central queue in the hot path. A goroutine spawned on a busy P ends up on an idle one without anybody scheduling it explicitly. The local queue costs zero locks; the cost of balancing is paid only by threads that have nothing to do.

What it costs. Spinning threads burn CPU. The 2*nmspinning < gomaxprocs-npidle cap bounds that, but a program with GOMAXPROCS=64 and one runnable goroutine can still have a spinner or two turning in the dark. And because a steal grabs half a queue, the first steal on a busy machine copies a lot of pointers to gain one goroutine.

The global queue is a lock. Every overflow and every ready() from a non-P context goes through sched.lock. It is batched to keep that cheap, but it is the one global serialisation point in the design.

Half, not all. Stealing half the victim’s queue is a heuristic balancing “don’t starve the victim” against “don’t make stealing pointless”.

Caveats

The scheduler is not a fairness guarantee. runnext deliberately jumps the queue: a goroutine that readies another one gets that one run next, and inherits its time slice.

Work stealing is invisible to your code. There is no API to ask “which P will run this goroutine”, and there should not be. If you need affinity you need runtime.LockOSThread or a channel-based baton, and you are on your own.

GOMAXPROCS is the parallelism knob, not the thread count. The runtime creates more Ms than Ps (a blocked syscall needs one), and the number of spinning Ms is separately capped. GODEBUG=schedtrace=1 prints a line per scheduling round; scheddetail=1 adds per-P detail.

The global queue is checked only every 61 ticks. A goroutine readied onto the global queue by a non-P context may wait a little while. That is the price of not taking a global lock on every scheduling decision.

Ordering between a local ready() and a global one is undefined. If one goroutine readies another onto the local queue and a third is pushed to the global queue, which runs first is unspecified.

Wrapping up

The one thing to remember: Go’s scheduler is distributed by design. Each P owns a 256-slot lock-free run queue; work that overflows spills to a global queue; and idle Ps steal half of a busy neighbour’s queue in a single atomic batch, which is how a machine with one hot goroutine and one cold P still uses every core.

The part people get wrong: the scheduler spins before it parks. A thread with no work does not immediately sleep — it becomes a spinning thief, and only gives up after the “delicate dance” that re-checks every source of work to make sure it is not about to drop the last thread that could have picked up newly submitted work.

What to go do about it: set GOMAXPROCS deliberately, run with GODEBUG=schedtrace=1000,scheddetail=1 to watch the queues move, and if you suspect scheduler pathology, look first at the global queue size and the number of spinning Ms — both are visible in the schedtrace output.