Goroutine에 관하여

goroutine을 사용하여 concurrency를 쉽게 구현할 수 있고, multi-thread app들을 매우 빠르게 동작시킬 수 있다. goroutine에 대해서 깊게 알아보기 전에 concurrency와 parallelism에 대해서 알아보도록 하자.

Concurrency와 Parallelism

둘 다 한국어로 번역하면 '동시성'이라고 할 수 있다. 정확히는 '동시성'과 '병렬성'인데, '동시성'을 제공하는 방법이 다른 것 뿐이라고 생각하면 된다. 'Parallelism'은 병렬성으로 동시성을 제공할 때, 실제로 여러 개의 주체들이 동시에 병렬적으로 실행된다.

다음은 각 process들이 각자의 CPU점유시간을 가지는 것을 나타낸다.

process1 ----------->
process2 ------>
process3 --------->
process4 ------------------>

-----------시간-------------->

시간 축에 여러 process들이 병렬적으로 동시에 실행되는 것을 볼 수 있다. 이는 특정 시간 t 시점에 여러 process들이 실행된다고 볼 수 있다.

반면에 'Concurrency'는 병렬적으로 주체들이 실행되지 않는다. 즉, 특정 시간 t시점에 여러 process들이 실행되는 것이 아니라, 특정 process만이 실행된다는 것이다. 한 번에 여러 process를 실행하는 것이 아니기 때문에, 'Concurrency'가 동시성을 제공한다는 것은 여러 개의 일을 쪼개어 짧은 시간마다 실행된다고 생각하면 된다. 따라서, 마치 여러 process들이 동시에 실행되는 것처럼 보이게 하는 것이다.

process1->
                       process2->
            process3->
                                process4->

-----------시간----------------------------->

다음과 같이 process들이 특정 시간 t시점에 같이 실행되지 않는다. 단, process들 각각이 서로 짧게 자신의 CPU에 점유하는 시간을 가져 실행되는 것이다. 이렇게 CPU는 마치 우리에게 동시에 여러 일이 가능한 것처럼 보이게 하고 있는 것이다.

concurrency는 단지 single core CPU만 있어도 동작이 가능하다. 반면에 parallelism은 여러 process를 동시에 동작시켜야 하기 때문에 multiple-core CPU가 필요하다.

여기서 오해하면 안되는 것이, '현재의 CPU들은 대부분 multi-core CPU이므로 parallelism이 제공된다. 따라서 굳이 concurrency가 필요하진 않지 않을까??' 하는 것이다. 이에 대한 대답은 '아니다', 엄밀히 말하자면 concurrency와 parallelism은 다른 주제이다. multiple-core를 가진 CPU라고 해도 개별적인 core들에 concurrency가 적용될 수 있기 때문이다. 따라서, concurrency는 개별 core에서 동작하는 process들 차원에서의 최적화에도 관련이 있다는 것이다.

Thread란?

thread는 process의 '실행 컨텍스트 단위'로 보면 된다. 실제로 대부분의 프로그램들은 process로 실행될 때 main thread가 실행되고, sub task들에 대해서 sub thread들을 파생하는 방법으로 동작한다. 따라서, thread들은 CPU에 스케줄링되어 실행되는 하나의 실행 단위이며, 개별적인 context를 가지고 있어 실행에 필요한 정보들을 유지한다. context는 thread가 CPU에 할당되어 동작되는 중에 context switching가 발생했을 때, 실행 정보를 담는 대상이 되는 것이다. 다시 time slice(window)를 받아서 thread가 실행될 때 이 context에 담긴 데이터를 register와 memory에 넣어, 이전 실행 상태를 복원하는 것이다.

따라서, process는 여러 thread들로 이루어져 있고, 이 thread들이 process의 실행 주체이며, CPU에 할당되어 실행될 때 필요한 정보를 저장하기 때문에 '실행 컨텍스트'라고 불리는 것이다.

일반적으로 process는 global 데이터를 저장하는 data, code에 대한 정보를 저장하는 code, local 데이터를 저장하는 stack, 사용자 지정 메모리 영역인 heap을 가진다. thread의 경우는 process의 data, code, heap영역은 모두 공유하고, 각자의 local 데이터를 저장용으로 stack을 가진다.

또한 process는 register정보를 기록하여 상태를 저장하는 PCB(process control block)와 다음 명령어 실행을 위한 Program Counter를 가지는데, thread 역시도 register 정보를 가지는 TCB(thread control block)과 다음 명령어 실행을 위한 Program Counter를 가진다.

다음과 같이 각 thread들은 process의 code, data, file들을 모두 공유하고, register, stack, counter(program counter)를 가지는 것을 볼 수 있다. 따라서 thread를 하나의 경량 process라고 볼 수 있는 것이고, CPU 실행에 필요한 regsiter 정보, program counter를 가지고 있으므로 '실행 컨텍스트'라고 불릴 수 있는 것이다.

User level thread와 Kernel level thread

user level thread는 application level에서 실행되는 thread라고 생각하면 된다. 가령, c의 Pthread와 같은 것들이 대표적이다. 이러한 user level thread는 생성 주체가 개발자이고, 이를 관리, 동기화 제공, 스케줄링 주체 역시 모두 개발자이다.

반면에 kernel level thread의 주체는 kernel이다. kernel이 OS의 동작을 위해 thread를 직접 관리, 생성하는 것이다.

user level thread는 kernel의 개입없이 user space에서만 관리되므로 훨씬 더 가볍고, 여러 운영체제와 호환성이 높다. 단, 하나의 thread가 process의 동작에 영향을 주면 다른 thread들도 죽을 수 있기 때문에 격리 수준이 높지 않다.

반면에 kernel level thread는 kernel space에서 관리되므로 훨씬 더 격리 수준도 높고, 실수없이 동작한다. 단, kernel space에서 동작하므로 user space보다 오버헤드가 높다.

User level thread와 Kernel level thread의 맵핑

user level thread는 user space에서 실행되지만 CPU를 할당받아 실행되기 위해서는 kernel space로 진입해야한다. 이 경우 user level thread는 kernel level thread와 맵핑되어야 하는 것이다. 이 밖에도 user level thread는 kernel space에 진입해야할 때마다 kernel level thread와 맵핑되는 것이다.

user level thread가 kernel level thread에 맵핑되어 실행되는 경우들을 정리하면 다음과 같다.
1. CPU 실행: user level thread가 실제로 CPU에서 실행되기 위해서는 kernel 스케줄링에 의해 CPU가 할당되어야 한다.
2. I/O 작업 및 system call: file을 읽거나, 네트워크 작업, 메모리 할당, process 생성 등 I/O 작업과 system call을 하기 위해서는 user level thread가 kernel level thread에 맵핑되어야 한다.
3. multi-process 환경에서의 병렬 실행: 멀티 프로세서 환경은 여러 thread가 병렬적으로 실행될 수 있는데, user level thread가 병렬로 실행되기 위해서는 각각의 user level thread가 서로 다른 CPU에서 동시에 실행될 수 있어야 한다. 이를 위해서 user level thread들은 kernel level thread에 맵핑되어야 한다.
4. Thread 스케줄링 및 관리: kernel이 user level thread를 인식하여 스케줄링, 우선순위 변경, wait, awake 등의 thread 관리 기능을 제공하기 위해서는 kernel level thread에 할당되어야 한다.

정리하자면 user level thread는 CPU에서 실행되기 위해서 kernel level thread에 맵핑되어야 한다는 것이다.

이 맵핑에는 3가지 방식이 존재하는데 다음과 같다.

1. 1:1 맵핑: user level thread와 kernel level thread가 1대1로 맵핑된다. 이 경우 user level thread가 생겨나면 새로운 kernel level thread도 생겨나 맵핑되는 것이다. java의 Thread class와 c의 pthread가 그렇다.

2. N:1 맵핑: 여러 개의 user-level thread가 하나의 kernel-level thread에 맵핑된다. 즉 하나의 process마다 하나의 kernel level thread가 존재하고 이 process의 모든 user level thread들은 이 kernel level thread에 맵핑되어 스케줄링, CPU할당을 받는 것이라고 생각하면 된다.

3. N:M 맵핑: N개의 user level thread가 M개의 kernel level thread에 맵핑되는데, N:1는 이미 user level thread들이 자신이 맵핑될 kernel level thread들이 무엇인지 아는 반면에, N:M은 모른다. 이는 맵핑이 필요한 시점에 결정되며, 효율적으로 thread 관리가 가능하다.

User level thread의 한계

user level thread들은 저 마다의 memory 영역을 가지고 있고, application의 일부로 동작한다. 이는 user level thread 자체가 application 내에서 library를 통해 관리되며, context switching이 발생해도 kernel mode로 진입하지 않아도 된다는 것이다. 즉, user level thread들은 application level에서 관리되기 때문에 context switching 역시도 application 수준에서 실행된다.

반면 kernel level thread는 kernel mode로 진입해야하며, context switching이 kernel에서 발생하기 때문에 매우 비싸다.

user level thread는 사실 kernel 입장에서 보면 하나의 kernel level thread에 불과하다. 따라서, user level thread 끼리의 application level에서의 context switching이 발생해도 kernel은 kernel level thread에 대해서 context switching을 하지 않는다.

그러나 이는 반대로 단점으로도 이루어지는데, 하나의 user level thread가 block되면, 거기에 연결된 kernel level thread도 block된다. 문제는 kernel은 해당 user level thread를 인식하지 못하고, 하나의 kernel level thread로만 생각하기 때문에 kernel level thread가 block되었다고만 인식하여, block된 user level thread를 바꾸는 것이 아니라, 해당 kernel level thread를 계속 block 시키게되고, 이는 전체 process를 block시키게 된다.

즉, process의 user level thread중 한 개가 block되면, process 전체가 block될 수 있다는 것이다.

user level thread의 또 다른 단점 중 하나는 multi-core CPU로 동작한다하더라도, single kernel thread에 맵핑되면 사실상 multi processor의 힘을 보기 힘들다는 것이다. 즉, user level thread를 서로 다른 core에 맵핑하지 못한다는 것이다.

Goroutine

이러한 문제를 해결하기위해서 goroutine은 user level model과 kernel level model의 혼합 형식을 가진다. golang은 goroutine을 관리하고 적절하게 스케줄링하기 위한 queue들을 가지는데, queue하나 당 kernel level thread가 하나가 존재하여 이 queue에 넣은 goroutine들을 실행하는 것이다. 물론 queue에 들어간다해서 반드시 들어온 순서대로만 실행되는 것은 아니며, 우선순위에 따라서 실행되는 순서가 달라질 수 있다.

이렇게만 보면, goroutine이 하나의 user level thread와 별반 다를 바 없어보여서 blocking이 발생하면 kernel level thread가 같이 block될 것처럼 보인다. 그러나, golang은 재밌게도 go-runtime이 goroutine을 따로 관리하기 때문에, go-runtime이 해당 goroutine이 block되었다는 사실을 kernel에게 알려준다. 알려주는 방법은 매우 간단한데, block된 goroutine을 감싸서 '이 녀석은 나중에 실행될 놈이다'라는 것을 kernel level thread에 알려주는 것이다. 이렇게되면 kernel level thread이 blocking되는 동작을 멈추고, 다른 goroutine을 마저 실행하게 된다. 정확히는 그렇게 동작하는 것처럼 보이게 하는 것이다.

go-runtime은 process가 실행될 때 몇몇 kernel level thread들을 만든다. kernel level thread의 수는 GOMAXPROCS 환경 변수에 맞게 생성되는데, default로 machine의 core수와 동일하다.

Local Run Queue(LRQ), Global Run Queue(GRQ)

goroutine을 위한 queue는 두 가지 종류가 존재한다. 하나는 goroutine을 실행하기 위해 스케줄되는 LRQ(Local Run Queue)이고, 하나는 아직 스케줄되지 않은 goroutine을 담는 GRQ(Global Run Queue)이다.

LRQ가 비어지게 되면, GRQ에서 goroutine을 빼내어 LRQ에 넣는 구조이다.

사실 위에서 kernel thread 하나 당 goroutine을 스케줄링하기 위한 queue가 있다고 했는데, 정확히는 CPU core에 goroutine 실행을 위한 queue가 있는 것이며 이를 LRQ라고 하는 것이다.

이 core 하나 당 kernel thread가 하나 씩 배정되어 실행되므로 마치 kernel thread 하나 당 LRQ가 있는 것처럼 보이지만 엄밀히 말하자면 core 당 LRQ가 있는 것이다.

-----GRQ-----
|G6 G7 G8   |
-------------

-LRQ1-   
| G3 |   -LRQ2-
| G2 |   | G5 |
| G1 |   | G4 |
------   ------
  |        |
  K1       K2
  |        |
core1    core2

G는 goroutine이고 K는 kernel thread로 보면 된다. LRQ가 kernel thread가 아니라 core마다 할당된다는 말은, core에 할당된 kernel thread가 다운되어도 LRQ는 유지되어 core가 새로운 kernel thread를 만들어 자신의 LRQ를 배정할 수 있다는 말이다.

또한, 현재는 core1이 K1 kernel thread를 맵핑하여 실행하고 있지만, K1을 버리고 아예 새로운 kernel thread인 K3를 생성하여 core1에 할당해줄 수도 있다. 어차피 LRQ는 core 종속이기 때문에 kernel thread를 바꾸어도 실행에는 지장이 없다. 따라서, goroutine과 kernel thread간의 맵핑은 M:N이 되는 것이다.

그런데, 위에서 user-level thread의 단점으로 user-level thread에서의 blocking 연산(IO작업, 네트워크 작업)이 kernel thread에 blocking을 유발하도록하고, kernel입장에서는 kernel thread이 block되었다고만 생각하여 해당 kernel thread를 스케줄링 하지 않는다는 문제가 있다고 했다. 이는 곧 해당 core의 LRQ에 있는 goroutine들도 모두 block처리된다는 것을 말한다.

이에 대해 golang의 go runtime은 다음의 해결방법을 제시한다.

blocking operation(io 작업)이 goroutine에서 실행되려고 할 때, go runtime은 kernel thread에게 '이제 곧 kernel thread에 blocking 연산이 실행될 것이다'라는 신호를 준다. goroutine의 blocking 연산이 실행되면, 해당 goroutine을 실행하는 kernel thread도 block되는데, 이때 새로운 kernel thread를 생성하여 해당 core에 연결한 다음 LRQ에 있는 나머지 goroutine들을 실행하던지, kernel thread pool에서 놀고있는 kernel thread를 core에 할당하여 LRQ의 goroutine들을 병목없이 실행시킬 수 있다.

• block

-----GRQ-----
|G6 G7 G8   |
-------------

-LRQ1-   
| G3 |          -LRQ2-
| G2 |          | G5 |
|    |          | G4 |
------          ------
  |                |
K1(G1 Block)       K2
  |                |
core1            core2

K1이 G1을 실행하다가 block되었다고 하자. go runtime은 core1을 가용하기 위해서 core1에 새로운 thread를 배정하여 LRQ1에 있는 goroutine들을 실행시킬 수 있도록 한다.

• 1. 새로운 kernel thread 배정

-----GRQ-----
|G6 G7 G8   |
-------------

-LRQ1-   
| G3 |   -LRQ2-
| G2 |   | G5 |
|    |   | G4 |
------   ------
  |        |
 K3       K2      K1(G1 Block)
  |        |
core1    core2

K3라는 kernel thread를 새로 생성하고 core1에 할당해주어 LRQ1에 있는 goroutine들을 실행시켜줄 수 있다.

또는 pool에서 K3라는 kernel thread가 놀고 있다면 해당 kernel thread를 가져와서 실행이 가능하다. 즉, kernel thread pool에서 하나를 가져오는 방식이다.

• 2. 다른 kernel thread에 할당

-----GRQ-----
|G6 G7 G8   |
-------------

   
-LRQ1-   -LRQ2-
| G3 |   | G5 |
| G2 |   | G4 |
------   ------
  |        |  
  K3       K2   K1(G1 Block)
  |        |
core1    core2

이러한 작업이 수행되면 LRQ1에 있는 goroutine들은 block되지 않고 계속해서 실행이 될 수 있는 것이다.

이후 G1의 IO block이 끝난 후에는 K1 kernel thread도 block상태에서 해제되어 실행 가능한 상태가 된다. G1은 GRQ나 LRQ에 들어가 스케줄링되어 실행될 수 있으며, K1은 다시 사용 가능한 resource로서 go runtime에 의해 재사용된다. 즉, pool에 들어가거나 다른 core에 할당 가능해질 수 있다는 것이다.

추가적으로 goroutine의 비동기 network 작업(socket create, write,read)의 경우는 IO작업처럼 blcok되지 않는데, 이는 network poller 덕분이다. network poller는 network IO작업이 완료되면 kenrel에서 event를 발생시켜 goroutine이 다음 실행을 할 수 있도록 하는 것이다. 즉, epoll과 동작이 비슷하다.

가령 G1 goroutine이 socket에서 데이터를 읽는다고 하자. 다음의 순서로 동작하게 된다.
1. G1이 대기 상태로 변한다. 단, K1 kernel thread은 block되지 않는다.
2. K1 kernel thread는 LRQ에서 다른 gorotuine들을 처리한다.
3. socket read가 완료되면 network poller가 G1을 깨워준다.
4. G1은 다시 스케줄링의 대상이되며, 이전과 다른 kernel thread에서 실행될 수도 있다.

network 작업을 수행하는 goroutine은 비차단 방식으로 처리되므로 goroutine이 network IO 작업을 수행하더라도 다른 goroutine에 영향을 주지 않는 것이다.

Work stealing(작업 훔치기)

go-scheduler가 goroutine을 한 queue에서 다른 queue로 옮기는 것을 work stealing(작업 훔치기)이라고 한다. 이는 LRQ간의 불균형이 있을 때와 같은 경우에 발생하며 하나의 로드밸런싱기능을 하는 것이다. 즉 processor core 간의 로드 밸런싱이 이루어지는 것이다.

이를 통해서 go는 멀티 core를 효과적으로 활용해 효율성을 유지하는 것이다.

각 processor core에서 실행할 goroutine 선택하는 과정은 다음과 같다.
1. 자신의 LRQ에서 goroutine을 가져온다.
2. GRQ에서 goroutine을 가져온다.
3. LRQ와 GRQ가 비어있을 때, 다른 core에 있는 LRQ를 훔쳐온다. (work stealing)

아래와 같이 P0(core0)의 LRQ에 goroutine이 하나도 없는 경우 work stealing이 발생한다.

P1(core1)의 LRQ에서 gorutine들을 P0의 LRQ로 가져와 실행하도록 하는 것이다.

Go scheduler

kernel thread를 스케줄링하고 다루는 것은 os-scheduler이다. 이는 현재 kernel thread의 register, stack pointer, PC(program counter), memory 맵핑 등을 메모리에 context switching 할 수 있어야한다.

그에 반해 goroutine은 thread보다 훨씬 더 가벼운 편이다. 일부의 register와 2KB의 stack만으로도 context를 표현할 수 있어 context switching이 매우 간편하다. 이러한 goroutine을 kernel thread에 스케줄링하고 context switching하는 역할이 바로 go-scheduler인 것이다.

go-scheduler는 user-level(application)에서 event를 사용하여 kernel thread에 goroutine을 스케줄링한다. 여기서 user-level의 event가 바로 file IO 작업, network 요청을 말하며, 이러한 event들을 효과적으로 다루기 위해 LRQ, GRQ를 사용해 goroutine 스케줄링을 조절하는 것이다.

아래 그림은 user-level event를 사용해 kernel thread에 goroutine을 스케줄링하는 모습을 보여준다.

참고로 go-scheduler는 go-runtime의 일부 기능이라고 생각하면 된다. 즉, 별도의 component가 아니다.

• 참고

1. https://medium.com/codex/the-anatomy-of-golang-goroutines-58cf8b6bf813
2. https://medium.com/a-journey-with-go/go-work-stealing-in-go-scheduler-d439231be64d
3. https://velog.io/@kineo2k/%EA%B3%A0%EB%A3%A8%ED%8B%B4%EC%9D%80-%EC%96%B4%EB%96%BB%EA%B2%8C-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81%EB%90%98%EB%8A%94%EA%B0%80
4. https://tech-blog.cymetrics.io/en/posts/genchilu/javas-thread-model-and-golang-goroutine-en/
5. https://www.youtube.com/watch?v=wQpC99Xu1U4
6. https://www.youtube.com/watch?v=YHRO5WQGh0k