golang 비동기. goroutine은 왜 순서대로 실행되지 않을까: 고루틴 스케줄링

flangdu

21 min readJul 8, 2024

해당 아티클은 다음 수준의 지식을 요구합니다.

goroutine을 사용해본 경험

다음은 다루지 않습니다.

goroutine이 무엇이고 어떻게 사용하나요?

다음 실행환경에서 동작합니다.

wsl2 Ubuntu-22.04
go1.22.2 linux/amd64

“goroutine은 순서대로 실행되지 않는다”에서 알아볼 것은 고루틴의 스케줄러입니다. 고루틴 스케줄러는 흔히 알려져 있는 MPG로 불리는 machine, process, goroutine의 세 가지 큰 내부 구성 요소로 동작합니다. 해당 아티클에는 고루틴 스케줄러의 동작 원리를 go 내부 소스 코드를 함께 보면서 어떻게 동작하는지, 또 어떻게 동작하기에 순서대로 실행되지 않는다는 의미를 붙인 것인지 탐구해보겠습니다.

샘플 코드 실행해보기

다음 코드는 100개의 고루틴을 main 고루틴에서 생성하고 생성 시간과 생성 인덱스를 주입하여 출력하는 단순한 코드입니다. wg는 고루틴을 올바르게 종료하기 위한 도구일 뿐이므로 여기서 중요하지 않으니 넘어갑니다.

package main

import (
	"fmt"
	"sync"
	"time"
)

func main() {
	wg := &sync.WaitGroup{}

	for i := range 100 {
		wg.Add(1)
		go func(i int, t time.Time) {
			fmt.Println(i, t.String())
			wg.Done()
		}(i, time.Now())
	}

	wg.Wait()
}

위의 코드를 실행하면 다음 결과를 얻을 수 있습니다.

$ go mod init main
$ go build .
$ ./main
99 2024-06-26 23:05:01.256806518 +0900 KST m=+0.000040670
49 2024-06-26 23:05:01.256797908 +0900 KST m=+0.000032060
50 2024-06-26 23:05:01.256798068 +0900 KST m=+0.000032220
27 2024-06-26 23:05:01.256793918 +0900 KST m=+0.000028070
85 2024-06-26 23:05:01.256804268 +0900 KST m=+0.000038420
10 2024-06-26 23:05:01.256790488 +0900 KST m=+0.000024630
...

순서에 있어서 그 어떤 일관성도 찾을 수 없습니다. main 바이너리를 실행 시키면 main 프로세스 내부의 임의의 쓰레드가 랜덤하게 고루틴을 선택하여 실행하는 것처럼 보입니다.

고루틴 스케줄링

위의 그림은 https://www.ardanlabs.com/blog/2018/08/scheduling-in-go-part2.html 에서 소개된 고루틴 스케줄러를 설명하는 그림중 일부분입니다. “go 100가지 실수 패턴과 솔루션”책을 참고해보면 아주 간단하게 golang의 내부 스케줄러 동작을 살펴보면 고루틴 스케줄러 동작을 다음과 같이 요약해 볼 수 있습니다.

go 스케줄러는 다음 요소로 이루어집니다: [g: 고루틴, m: machine. OS 쓰레드. p: processor. 논리적 CPU]
OS 스케줄러는 OS 쓰레드(m)마다 CPU 코어(p)를 할당하고 고루틴(g)를 m에서 실행시킵니다. golang에는 GOMAXPROCS라는 값이 존재하고 해당 값 만큼 동시에 실행시킬 m의 최대 개수를 정의합니다. 만약 시스템 콜에 의해 쓰레드가 중지됐다면, 스케줄러는 m을 더 생성합니다.
고루틴의 생명주기는 다음 중 하나입니다: 실행 중, 실행 가능, 대기
스케줄링에서 고루틴이 생성되어도 모든 m이 g를 실행하고 있다면, g는 실행되지 않고 큐에 고루틴을 넣습니다. golang 런타임은 모든 p가 같이 사용하는 글로벌 큐와 p 개별로 사용하는 로컬 큐를 이용하여 실행 가능한 고루틴을 저장합니다. 지금은 이 정도로 스케줄러가 동작한다고 이해하고 넘어갑니다.

위의 그림은 https://youtu.be/wQpC99Xu1U4?si=Hv1O5Hn7bWvSvxVa gophercon 2021의 GopherCon 2021: Madhav Jivrajani — Queues, Fairness, and The Go Scheduler에서 가져왔습니다. 고루틴이 golang 내부에서 어떻게 동작하는지 한눈으로 보여주는 다이어그램이라고 생각합니다.

위의 그림처럼, 보통의 경우에 golang에 관한 scheduler 자료를 보면 어떤 큐를 통하여 고루틴이 순차적으로 실행되는 것 같아 보입니다. 그러나 결과는 어떤 방식으로도 선입 선출을 확인하기는 어려워 보입니다. 해당 이유를 golang 소스 코드를 확인해보면서 고루틴이 어떻게 생성되고 어떻게 관리되는지, 또 어떻게 이렇게 섞이게 됐는지 탐색해봅니다.

고루틴 생성 및 실행 과정

goroutine 생성 시 golang 소스 코드에서 다음과 같이 디버깅을 할 수 있습니다. 디버깅을 해보면 다음처럼 디버깅 포인트를 걸 수 있습니다. 위의 예시에서는 루프를 100으로 걸었지만 편의를 위해 1로 잡고 진행해보면 다음과 같습니다.

즉, 고루틴을 생성하게 되면 다음처럼 go로 생성한 함수가 runtime/newproc이라는 golang/go의 runtime 패키지 내부에 존재하는 함수로 이동되는 것을 확인할 수 있습니다.

해당 함수를 짧게 설명해보면 다음과 같습니다.

// Create a new g running fn.
// Put it on the queue of g's waiting to run.
// The compiler turns a go statement into a call to this.
func newproc(fn *funcval) {
	gp := getg()
	pc := getcallerpc()

// process의 stack 공간에서 직접 호출
	systemstack(func() {
	// 새로운 고루틴 생성
		newg := newproc1(fn, gp, pc)
	
	// process의 local run queue에 고루틴 삽입
		pp := getg().m.p.ptr()
		runqput(pp, newg, true)

	// main 쓰레드가 실행중이라면 p 깨움
		if mainStarted {
			wakep()
		}
	})
}

runtime/systemstack을 통해 프로세스 내부에서 할당된 스택 메모리 공간(고루틴 내부의 스택과는 다른 영역입니다. 일반적인 스택이라고 보시면 됩니다)안에서 고루틴을 생성하는 함수인 runtime/newproc1을 호출합니다.
다음은 runtime/newproc1의 내부입니다. runtime/newproc1 함수는 고루틴을 할당 & 초기화하고 go func(…)에서 주어진 인자를 고루틴 스택에 복사하고 고루틴의 필드의 다른 값을 세팅 후 함수를 빠져나옵니다.
이후 runtime/newproc으로 돌아가서 runtime/runqput()함수를 통해 큐에 추가합니다.
mainStarted 조건에 따라 wakep를 호출합니다.

위의 코드를 확인해봤을 때는 더 이상합니다. 어디서 순서가 섞여서 실행되는 걸까요? 이 부분을 찾기 위해 runtime/runqput()함수 내부를 살펴봅니다.

// runqput tries to put g on the local runnable queue.
// If next is false, runqput adds g to the tail of the runnable queue.
// If next is true, runqput puts g in the pp.runnext slot.
// If the run queue is full, runnext puts g on the global queue.
// Executed only by the owner P.
func runqput(pp *p, gp *g, next bool) {
	// randomizeScheduler는 일반 빌드에서 false입니다. 따라서 해당 조건문을 타지 않습니다.
	if randomizeScheduler && next && randn(2) == 0 {
		next = false
	}

	// newproc에서 넘어오면 next는 true입니다.
	if next {
	retryNext:
		oldnext := pp.runnext

		// 다음에 실행할 값과 oldnext를 비교하여 같으면 새롭게 생성한 고루틴으로 변경합니다.
		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를 old로 변경합니다.
		gp = oldnext.ptr()
	}

retry:
	// queue의 header, tail을 가져와서 큐가 차있는지 비교합니다.
	h := atomic.LoadAcq(&pp.runqhead) // load-acquire, synchronize with consumers
	t := pp.runqtail

	// t-h가 runq의 사이즈(256)보다 작다면: 큐가 가득차지 않았다면
	if t-h < uint32(len(pp.runq)) {
		
		// queue에 원소를 삽입합니다.
		pp.runq[t%uint32(len(pp.runq))].set(gp)
		atomic.StoreRel(&pp.runqtail, t+1) // store-release, makes the item available for consumption
		return
	}

	// 가득 찾다면 runqputslow함수를 호출합니다.
	if runqputslow(pp, gp, h, t) {
		return
	}
	// the queue is not full, now the put above must succeed
	goto retry
}

요약하면 다음과 같습니다.

next활성화 시 로컬 큐 내부에서 다음에 실행될 고루틴과 runtime/runqput의 입력으로 주어지는 고루틴의 위치를 변경합니다.
남은 고루틴(여기서는 기존에 pop한 고루틴입니다)을 다시 로컬 큐에 집어넣습니다.

즉, 가장 최근에 만든 고루틴이 실행 우선순위를 갖게 됩니다.

이를 확인하는 방법으로 코드를 다음과 같이 수정해봅시다.

package main

import (
	"fmt"
	"runtime"
	"sync"
	"time"
)

func main() {
	runtime.GOMAXPROCS(1) // GOMAXPROCS를 1로 주어 p를 1대로 제한합니다.

	wg := &sync.WaitGroup{}

	for i := range 100 {
		wg.Add(1)
		go func(i int, t time.Time) {
			fmt.Println(i, t.String())
			wg.Done()
		}(i, time.Now())
	}

	wg.Wait()
}

변경된 부분은 한 줄입니다. runtime.GOMAXPROCS(1)는 p를 하나로 변경해서 로컬 큐를 한 대만 사용하도록 변경합니다. 그리고 나서 다시 재빌드를 진행해봅니다.

$ go build .
$ ./main
99 2024-07-02 18:35:31.486893897 +0900 KST m=+0.000094570
0 2024-07-02 18:35:31.486879887 +0900 KST m=+0.000080560
1 2024-07-02 18:35:31.486882197 +0900 KST m=+0.000082870
2 2024-07-02 18:35:31.486882477 +0900 KST m=+0.000083150
3 2024-07-02 18:35:31.486882657 +0900 KST m=+0.000083330
4 2024-07-02 18:35:31.486888087 +0900 KST m=+0.000088760
5 2024-07-02 18:35:31.486888377 +0900 KST m=+0.000089050
6 2024-07-02 18:35:31.486888607 +0900 KST m=+0.000089270
7 2024-07-02 18:35:31.486888767 +0900 KST m=+0.000089430
8 2024-07-02 18:35:31.486889637 +0900 KST m=+0.000090310
9 2024-07-02 18:35:31.486889917 +0900 KST m=+0.000090580
10 2024-07-02 18:35:31.486890177 +0900 KST m=+0.000090850
11 2024-07-02 18:35:31.486891687 +0900 KST m=+0.000092360
12 2024-07-02 18:35:31.486892437 +0900 KST m=+0.000093110
13 2024-07-02 18:35:31.486892637 +0900 KST m=+0.000093300
14 2024-07-02 18:35:31.486892817 +0900 KST m=+0.000093490
15 2024-07-02 18:35:31.486892987 +0900 KST m=+0.000093650
16 2024-07-02 18:35:31.486893307 +0900 KST m=+0.000093970
17 2024-07-02 18:35:31.486893567 +0900 KST m=+0.000094230
18 2024-07-02 18:35:31.486893707 +0900 KST m=+0.000094380
...

99가 먼저 실행되고 그 다음에 0부터 98 까지 다시 순서대로 진행되는 결과를 확인할 수 있습니다. 왜 그럴까요?? 고루틴을 하나씩 만들어보면서 탐색해봅니다.

처음에 0번 고루틴이 생성되고 runtime/runqput에서 p의 runnext가 됩니다.
다음 1번 고루틴이 생성되고 기존 0번 고루틴은 oldnext가 되고 queue에 적재됩니다. 즉, 다음 상태라 볼 수 있습니다: 큐에는 0, 다음 실행은 1이 지정됩니다.
이제 2번 고루틴이 생성됩니다. 기존 1번 고루틴은 oldnext가 되고 queue의 맨 뒤에 적재됩니다: 큐에는 0, 1, 다음 실행은 2가 지정됩니다.
이제 5번까지 가봅니다: 큐에는 0, 1, 2, 3, 4, 다음 실행은 5가 지정됩니다.
이런 식으로 지속되면 0부터 98까지 큐에 쌓이고 다음 실행은 99가 됩니다.

p가 여러 대인 경우: 어떻게 다른 p에서 실행할 고루틴을 탐색할까?

이번에는 p를 여러 개 만들어서 진행해봅시다. 다음처럼 코드를 변경합니다.

package main

import (
	"fmt"
	"runtime"
	"sync"
	"time"
)

func main() {
	runtime.GOMAXPROCS(2) // GOMAXPROCS를 2로 주어 p를 2대로 제한합니다.

	wg := &sync.WaitGroup{}

	for i := range 100 {
		wg.Add(1)
		go func(i int, t time.Time) {
			fmt.Println(i, t.String())
			wg.Done()
		}(i, time.Now())
	}

	wg.Wait()
}

이후 다시 실행해보면 다음 결과가 출력됩니다.

$ go build .
$ ./main
22 2024-07-08 12:16:34.772083054 +0900 KST m=+0.000141390
17 2024-07-08 12:16:34.772082074 +0900 KST m=+0.000140410
23 2024-07-08 12:16:34.772083214 +0900 KST m=+0.000141540
4 2024-07-08 12:16:34.772077234 +0900 KST m=+0.000135570
26 2024-07-08 12:16:34.772083934 +0900 KST m=+0.000142270
72 2024-07-08 12:16:34.772093083 +0900 KST m=+0.000151419
27 2024-07-08 12:16:34.772084094 +0900 KST m=+0.000142430
8 2024-07-08 12:16:34.772079874 +0900 KST m=+0.000138210
76 2024-07-08 12:16:34.772093933 +0900 KST m=+0.000152269
10 2024-07-08 12:16:34.772080224 +0900 KST m=+0.000138560
40 2024-07-08 12:16:34.772086594 +0900 KST m=+0.000144930
12 2024-07-08 12:16:34.772081234 +0900 KST m=+0.000139570
78 2024-07-08 12:16:34.772094273 +0900 KST m=+0.000152599
41 2024-07-08 12:16:34.772086754 +0900 KST m=+0.000145080
15 2024-07-08 12:16:34.772081754 +0900 KST m=+0.000140080
16 2024-07-08 12:16:34.772081924 +0900 KST m=+0.000140250
99 2024-07-08 12:16:34.772099713 +0900 KST m=+0.000158049
...

다시 예측할 수 없어졌습니다. 이 이유는 runtime/wakep함수 내부에서 p를 2 이상으로 지정하여 멀티 쓰레드로 동작했기 때문임을 알 수 있는데, 해당 부분은 복잡하니 대략적으로 아래 과정으로 이루어진다고 보면 되겠습니다.

runtime/wakep로 p 깨우기 시도
runtime/startm → runtime/newm → runtime/newm1 → runtime/newosproc → runtime/mstart → (어셈블리) → runtime/mstart0 → runtime/mstart1: m을 생성하여 쓰레드 활성화
runtime/mstart1 → runtime/schedule → runtime/findrunnable호출

여기서 중요한 것은 runtime/startm → … → schedule 사이의 과정보다 runtime/findrunnable함수이므로 해당 함수를 살펴봅시다. 해당 함수의 역할은 p에서 실행할 고루틴을 탐색하는 함수라고 볼 수 있습니다.

함수가 길어서 주요 지점을 나눠서 살펴봅니다.

전역 실행 대기 큐 확인

// ...
if pp.schedtickr%61 == 0 && sched.runqsize > 0 {
    lock(&sched.lock)
    gp := globrunqget(pp, 1) // grq에서 goroutine을 가져옴
    unlock(&sched.lock)
    if gp != nil {
        return gp, false, false
    }
}
// ...

schedtickr은 p가 고루틴 스케줄링을 얼마나 했는지 나타내는 카운터입니다. findrunnable 내부에서는 다음처럼 61번마다 강제로 전역 대기 큐를 확인하여 전역으로 등록된 고루틴을 가져와 실행하도록 구현되어 있습니다. 그래서 너무 로컬 큐에 존재하는 고루틴만 실행하지 않도록 다음처럼 강제하고 있습니다.

로컬 대기 큐 확인

// ...
if gp, inheritTime := runqget(pp); gp != nil { // lrq에서 고루틴 가져오기
    return gp, inheritTime, false
}

if sched.runqsize != 0 { // 스케줄러의 큐사이즈가 0이 아니면 락 획득
    lock(&sched.lock)
    gp := globrunqget(pp, 0) // glq에서 가져옴
    unlock(&sched.lock)
    if gp != nil {
        return gp, false, false
    }
}
// ...

이후 로컬 대기 큐인 lrq에서 고루틴을 가져와 리턴합니다. 만약 gp가 nil로 실패했다면 전역 대기 큐인 grq를 탐색합니다.

작업 훔치기

// ...
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
    }
    if newWork {
        // There may be new timer or GC work; restart to
        // discover.
        goto top
    }

    now = tnow
    if w != 0 && (pollUntil == 0 || w < pollUntil) {
        // Earlier timer to wait for.
        pollUntil = w
    }
}
// ...

이전 프로세스(netpoller 등…)가 몇 개 더 있지만 중요한 부분을 보기 위해 작업 훔치기로 내려왔습니다. 만약 여기까지 작업을 찾지 못했다면 runtime/stealWork함수를 호출합니다. 해당 함수의 역할은 실행 중인 p를 순회하면서 훔치기가 가능하면 해당 p의 로컬 큐에 저장된 고루틴을 훔쳐옵니다.

다시 실행과정 정리

자, 그럼 어떻게 순서가 섞이는지 이제 알 수 있게 됩니다. 즉, 실행한 코드의 흐름이 다음과 같음을 이해할 수 있습니다.

main함수가 실행되며 main을 실행하는 main p가 고루틴을 생성하여 자신의 로컬 큐에 적재합니다(runtime/newproc).
newproc이 호출되어 wakep로 대기 중인 p 깨우기를 시도하고 깨어난 sub p는 runtime/schedule을 통해 runtime/findrunnable로 실행할 수 있는 고루틴 탐색을 시작합니다.
글로벌 큐와 로컬 큐에 고루틴이 비어 있으므로(글로벌 큐는 로컬 큐가 다 찼을 때 집어넣게 됩니다) sub p는 runtime/stealWork함수를 통해 다른 p의 로컬 큐에 저장된 고루틴을 훔치기 시도합니다.
sub p는 main p의 로컬 큐에 고루틴을 가져와 실행하게 됩니다.
멀티 쓰레드 환경에서 stdout이 실행되어 어떤 라인이 우선 출력될 지 알 수 없게 됩니다.

해당 부분을 그림으로 표현하면 다음과 같습니다.

따라서 고루틴의 스케줄링에 대해 다음 사실을 알 수 있습니다.

순서대로 고루틴이 생성되어도 순서대로 실행될 지 보장할 수 없습니다.
하나의 p에서 생성된 고루틴이 다른 여러 p에서 작업 훔치기로 인해 순서가 보장되지 않습니다.
둘 이상의 p가 실행되는 경우 멀티 쓰레드 프로그래밍처럼 동작한다는 것을 이해해야 합니다. 즉 동시성을 제어하기 위한 코드가 들어갑니다.

여기서 탐구하진 않았지만, 다음 과정에서도 고루틴이 대기가 걸려 큐의 다른 고루틴이 먼저 실행될 수 있습니다.

네트워크나 시스템 콜
타이머로 인한 대기
채널 블로킹

고루틴의 스케줄링은 여러 요인에 의하여 복잡하게 동작함을 알 수 있었습니다. 고루틴을 생성하고 실행할 때 로컬 큐와 전역 큐, 그리고 작업 훔치기의 메커니즘을 알아보았고 이로 인해 순서대로 실행되지 않으며 이를 추적하는 게 어려운 일이라는 것을 파악했습니다. 따라서 동시성 프로그래밍을 진행할 때 적절한 동기화 메커니즘을 활용하여 실행 순서를 고려해주어야 합니다.

다음에는 이런 주제를 알아보겠습니다.

그럼 왜 스케줄러는 로컬 큐와 글로벌 큐로 큐를 분산했을까?
golang의 동기화를 위한 sync 패키지

참고자료

(번역) Go 스케줄링 파트 2

Scheduling In Go : Part II — Go Scheduler