cppis

Software Engineer Blog.
(>w<)

9 분 소요


Scheduling In Go : Part II - Go Scheduler을 정리한 글입니다.


Go 스케줄러 는 복잡한 시스템이지만, 작동하는 방식에 대한 이해가 중요합니다.
이를 통해 더 나은 엔지니어링 결정을 내릴 수 있습니다.


Go 프로그램이 시작되면 호스트 시스템의 모든 가상 코어에 대해 논리 프로세서(P) 가 제공됩니다.

물리적 코어 당 여러 개의 하드웨어 쓰레드(Hyper-Threading) 가 있는 프로세서의 경우,
각 하드웨어 쓰레드 는 Go 프로그램에서 가상 코어 로 표시됩니다.

다음 MacBook Pro의 시스템 보고서를 예로 설명하겠습니다.


그림 1. Hardware Overview.


그림 1 를 보면, 단일 프로세서에 4 개의 물리적 코어가 있다는 것을 알 수 있습니다.

이 보고서에는 코어 당 보유한 하드웨어 쓰레드 수는 나오지 않았지만,
인텔 코어 i7 프로세서에는 하이퍼 쓰레딩이 있기 때문에, 물리 코어 당 2 개의 하드웨어 쓰레드 가 있습니다.
Go 프로그램에서는 OS 쓰레드를 병렬로 실행할 수 있는 8 개의 가상 코어 를 사용할 수 있습니다.


다음 예제로 확인해보겠습니다.

package main

import (
	"fmt"
	"runtime"
)

func main() {

    // NumCPU returns the number of logical
    // CPUs usable by the current process.
    fmt.Println(runtime.NumCPU())
}

----------------------------------------------------------------
8


위 머신에서 이 프로그램을 실행하면 NumCPU() 함수 호출의 결과 값이 8 입니다.
이 시스템에서 실행하는 모든 Go 프로그램에는 8P가 제공됩니다.


그림 2. Go Scheduler Overview.

각 구성요소에 대한 설명입니다:
M: OS 쓰레드
P: 논리 프로세서(Logical Processor)
GRQ: 글로벌 실행 대기열(Global Run Queue)
LRQ: 로컬 실행 대기열(Local Run Queue)
G: 고루틴(Goroutine)

모든 P 에는 OS 쓰레드(M)가 할당됩니다.(M은 머신을 의미합니다.)
이 쓰레드는 여전히 OS에 의해 관리되며 OS는 쓰레드에 코어를 배치하여 실행합니다.
이는 Go 프로그램을 실행할 때 각각 개별적으로 P에 연결된 8 개의 쓰레드를 사용할 수 있다는 뜻입니다.

모든 Go 프로그램에는 프로그램의 실행 경로인 초기 고루틴(G)이 제공됩니다.
고루틴은 본질적으로 코루틴(Coroutine)입니다.
(고루틴은 코루틴을 쓰레드 셋으로 다중화하는 것을 참고하세요.)
고루틴은 애플리케이션 레벨 쓰레드로 생각할 수 있으며 OS 쓰레드와 비슷합니다.
OS 쓰레드가 코어에서 컨텍스트 전환되는 것처럼 고루틴은 M에서 컨텍스트 전환됩니다.


퍼즐의 마지막 조각은 실행 대기열(Run Queue) 입니다.
Go 스케줄러에는 GRQ(Global Run Queue) 와 LRQ(Local Run Queue) 가 있습니다.

각 P에는 LRQ가 주어지며, P의 컨텍스트 내에서 실행되도록 지정된 고루틴을 관리합니다.
이 고루틴들은 교대로 해당 P에 지정된 M에 컨텍스트 전환됩니다.
GRQ는 아직 P에 지정되지 않은 고루틴들를 위한 것입니다.
고루틴들를 GRQ에서 LRQ로 옮기는 프로세스도 있습니다.




협력형 스케줄러(Cooperating Scheduler)

OS 스케줄러는 선점형 스케줄러(Preemptive Scheduler)입니다.
이는 스케줄러가 주어진 시간에 수행할 작업을 예측할 수 없다는 의미입니다.
커널이 이 결정을 내리고 있으며 모든 것이 비결정적(non-deterministic) 입니다.
OS에서 실행되는 응용 프로그램은 원자 명령(Atomic Instruction) 및 뮤텍스 호출(Mutex Calls)과 같은
동기화 기본 요소를 활용하지 않는 한 스케줄링을 사용하여 커널 내부에서 발생하는 상황을 제어할 수 없습니다.

non-deterministic, 같은 입력에도 경우에 따라 다른 결과가 나오는 성질을 의미합니다.


Go 스케줄러는 Go 런타임의 일부이며 Go 런타임은 애플리케이션에 내장되어 있습니다.
이는 Go 스케줄러가 커널 위의 사용자 공간에서 실행됨을 의미합니다.
Go 스케줄러의 현재 구현은 선점형 스케줄러 가 아니라 협력형 스케줄러 입니다.
협력형 스케줄러를 위해 스케줄러는 스케줄 결정을하기 위해 코드의 안전한 지점에서 발생되는
명확한 사용자 공간 이벤트가 필요합니다.


Go의 협력 스케줄러에서 눈에 띄는 점은 선점적으로 보이는 느낌입니다.
Go 스케줄러가 수행 할 작업을 예측할 수 없습니다.
이 협력 스케줄러의 의사 결정은 개발자의 손이 아니라 Go 런타임에 있기 때문입니다.
Go 스케줄러를 선점 스케줄러와 같기 때문에 비결정적이라고 생각할 수 있습니다.




고루틴 상태(Goroutine States)

쓰레드와 마찬가지로 고루틴은 동일한 세 가지 상위 레벨 상태(High-level States)를 갖습니다.
이는 Go 스케줄러가 고루틴 관리하는 상태로, 고루틴은 세 가지 상태 중 하나입니다:
대기 중(Waiting), 실행 가능(Runnable) 또는 실행 중(Executing).


대기 중(Waiting):

고루틴이 멈췄고 계속하기 실행하기 위해 기다린다는 의미합니다.
운영 체제(시스템 콜) 또는 동기화 호출(원자 및 뮤텍스 작업)을 대기하는 것이 원인일 수 있습니다.
이러한 유형의 대기 시간은 성능 저하의 근본 원인입니다.

실행 가능(Runnable):

이는 고루틴이 할당된 명령을 실행하기 위해 M에 시간을 원하는 것을 의미합니다.
시간을 원하는 고루틴들이 많다면, 시간을 얻기 위해 더 오래 기다려야 합니다.
또한, 더 많은 고루틴들이 경쟁할수록 얻는 개별 시간이 단축됩니다.
이러한 유형의 예약 대기 시간도 성능 저하의 원인이 될 수 있습니다.

실행 중(Executing):

고루틴이 M에 배치되었고 명령을 실행하고 있다는 의미입니다.
작업이 진행되고 있다는 상태입니다.




컨텍스트 전환(Context Switching)

Go 스케줄러에는 컨텍스트 전환을 위해 코드의 안전한 지점에서 발생하는
명확한 사용자 공간 이벤트가 필요합니다.
이러한 이벤트와 안전 지점은 함수 호출 내에서 나타납니다.
함수 호출은 Go 스케줄러 상태에 아주 중요합니다.
Go 1.11 에서는, 함수를 호출하지 않는 엄격한 루프(tight loop)를 실행하면
스케줄러 및 가비지 콜렉션 내에 지연이 발생합니다.
즉, 함수 호출은 적절한 시간 내에 발생하는 것이 좋습니다.

Note:
Go 1.12에서는 Go 스케줄러에 비협조적인 선점 기술들(Non-cooperative Preemption Techniques)을 적용하여
엄격한 루프의 선점을 허용하는 것에 대한 제안이 승인되었습니다.

Go 프로그램에서 스케줄러가 스케줄을 결정할 수 있도록 발생하는 네 개의 이벤트가 있습니다.
스케줄이 항상 이러한 이벤트 중 하나에서 발생한다는 의미는 아니고, 스케줄러가 기회를 얻는다는 의미입니다.

  • go 키워드 사용
  • 가비지 컬렉션(Garbage collection)
  • 시스템 콜(System calls)
  • 동기화와 조정(Synchronization and Orchestration)


go 키워드 사용

키워드 go는 고루틴을 만드는 방법입니다.
새 고루틴이 작성되면 스케줄러가 스케줄을 결정합니다.


가비지 컬렉션(Garbage collection)

GC(Garbage collector)는 자체로 고루틴 셋을 사용하기 때문에
이 고루틴들은 실행하는 데 M의 시간이 필요합니다.
이런 이유로 GC는 많은 스케줄링 혼란을 발생합니다.
그러나 스케줄러는 매우 똑똑하기 때문에 고루틴이 수행하는 작업에 대해 현명한 결정을 내립니다.
그 중 하나는 GC 동안 힙(Heap)을 건드리지 않는 고루틴을 힙을 건드릴 고루틴과 컨텍스트 전환하는 것입니다.
GC가 실행될 때, 많은 스케줄 결정이 이루어집니다.

시스템 콜(System calls)

만약 고루틴의 M을 차단하게 하는 시스템 호출을 고루틴에서 하면,
가끔 스케줄러는 고루틴을 M에서 컨텍스트 전환 Off(Context-switch Off)하고
새 고루틴을 동일한 M으로 전환 할 수 있습니다.
그러나 때때로 새로운 M은 P에 대기중인 고루틴을 계속 실행하는 데 필요합니다.
작동 방식은 다음 섹션에서 자세히 설명합니다.

동기화와 조정(Synchronization and Orchestration)

만약 원자(Atomic), 뮤텍스(Mutex) 또는 채널(Channel) 작업 호출로 고루틴이 블록(block)되면,
스케줄러가 새로운 고루틴을 실행하도록 컨텍스트 전환을 할 수 있습니다.
고루틴을 다시 실행할 수 있게 되면 다시 큐에 추가되어 다시 M으로 컨텍스트 전환이 가능합니다.




비동기 시스템 콜(Asynchronous System Calls)

사용하는 OS에서 시스템 호출을 비동기로 처리 할 수 있는 경우, 네트워크 폴러 를 사용하여
시스템 호출을 효율적으로 처리 할 수 있습니다.
이는 각 OS에서 kqueue(MacOS), epoll(Linux) 또는 iocp(Windows) 를 사용하여 수행할 수 있습니다.


오늘날 우리가 사용하는 많은 OS에서 네트워킹 기반 시스템 호출은 비동기로 처리 할 수 있습니다.
네트워크 폴러의 주요 용도는 네트워킹 작업을 처리하기 때문에 네트워크 폴러라는 이름을 사용합니다.


스케쥴러는 네트워킹 시스템 콜에 네트워크 폴러를 사용하여 시스템 콜을 호출할 때
고루틴이 M을 블록(block)하지 못하게 할 수 있습니다.
이를 통해 새로운 M을 만들지 않고도 P의 LRQ에서 다른 고루틴들을 실행할 수 있도록
M을 유지할 수 있으므로 OS의 예약 부담을 줄일 수 있습니다.

다음 예를 통해 동작을 확인해 보겠습니다.

그림 3. Go Scheduler Async System Call #0.


그림 3 는 기본 스케줄링을 보여줍니다. 고루틴-1(G1)이 M에서 실행 중이며 LRQ에서 M에 대한 시간을
얻기 위해 대기중인 3 개의 고루틴들이 더 있습니다. 네트워크 폴러는 유휴 상태입니다.


그림 4. Go Scheduler Async System Call #1.


그림 4 에서 고루틴-1(G1)은 네트워크 시스템 호출을 원하므로 G1이 네트워크 폴러로 이동하고
비동기 네트워크 시스템 호출이 처리됩니다.
G1이 네트워크 폴러로 이동하면 M은 LRQ의 다른 고루틴을 실행할 수 있습니다.
이 경우 고루틴-2(G2)가 M에서 컨텍스트 전환되었습니다.


그림 5. Go Scheduler Async System Call #2.


그림 5 에서 비동기 네트워크 시스템 호출이 네트워크 폴러에 의해 완료되면, G1은 다시 P의 LRQ에 추가됩니다.
G1을 M에서 컨텍스트 전환되면 Go 관련 코드가 실행됩니다.
여기서 가장 큰 장점은 네트워크 시스템 호출을 실행하기 위해 추가 M이 필요하지 않다는 것입니다.
네트워크 폴러는 OS 쓰레드를 가지고 있으며 이벤트 루프를 효율적으로 처리합니다.




Synchronous System Calls

고루틴이 비동기로 수행 할 수 없는 시스템 호출을 원할 경우 네트워크 폴러를 사용할 수 없고,
시스템 호출을 하는 고루틴이 M을 블록(block)됩니다.
유감스럽지만 이를 막을 수 있는 방법은 없습니다.
비동기로 수행 할 수없는 시스템 호출의 한 예는 파일 기반 시스템 호출입니다.
CGO 를 사용하는 경우 C 함수를 호출하면 M도 차단되는 다른 상황이 있을 수 있습니다.

Note:
Windows OS에는 파일 기반 시스템 호출을 비동기로 수행하는 기능이 있습니다.
기술적으로 Windows에서는 이 기능에 네트워크 폴러를 사용할 수 있습니다.

M을 블록(block)하는 동기 시스템 콜(예, 파일 I/O)에서 발생하는 작업을 살펴 보겠습니다.

그림 6. Go Scheduler Sync System Call #0.


그림 6 은 기본 스케줄링을 보여 주지만 이번에는 G1이 M1을 차단하는 동기 시스템 호출을 할 것입니다.


그림 7. Go Scheduler Sync System Call #1.


그림 7 에서 스케줄러는 G1로 인해 M이 블록(block)되었음을 알 수 있습니다.
이 시점에서 스케줄러는 차단된 G1이 여전히 연결된 상태로 P1에서 M1을 분리합니다.
그 다음 스케줄러가 P를 서비스하기 위해 새로운 M2를 가져옵니다.
이 시점에서 G2를 LRQ에서 선택하고 M2로 컨텍스트 전환 할 수 있습니다.
이전 스왑으로 인해 M이 이미 존재하는 경우 새 M을 작성하는 것보다 이 전환이 더 빠릅니다.


그림 8. Go Scheduler Sync System Call #2.


그림 8 에서 G1에 의한 블록(block)된 시스템 호출이 완료되었습니다.
이 시점에서 G1은 LRQ로 다시 이동하여 P를 다시 사용할 수 있습니다.
이 시나리오가 다시 발생하는 경우를 위해 M1이 옆에 배치됩니다.




작업 스틸링(Work Stealing)

스케줄러의 또 다른 측면은 작업 스틸링 스케줄러라는 것입니다.
이를 통해 일부 영역에서 스케줄을 효율적으로 유지할 수 있습니다.
우선, 가장 원하지 않는 경우는 M이 대기 상태로 전환하는 것인데,
일단 이 상황이 발생하면 OS가 M을 코어에서 컨텍스트 전환 Off(Context-Switch off)하기 때문입니다.
즉, P가 M에서 컨텍스트 전환될 때까지 실행 가능한 상태의 고루틴이 있어도 P는 어떤 작업도 수행할 수 없습니다.
작업 스틸링은 또한 모든 P에서 고루틴의 균형을 유지하는 데 도움이 되므로 작업이 더 효율적으로 분산되고 완료됩니다.


예제를 통해 확인해보겠습니다.


그림 9. Go Scheduler Work Stealing #0.


그림 9 에는 GRQ에서 각각 4 개의 고루틴과 단일 고루틴을 서비스하는 2 개의 P가 있는
멀티 쓰레드 Go 프로그램이 있습니다.
P의 서비스 중 하나가 모든 고루틴을 빠르게 처리하면 어떻게 될까요?


그림 10. Go Scheduler Work Stealing #1.


그림 10 에서 P1에는 더 이상 고루틴이 없습니다.
그러나 P2의 LRQ와 GRQ 에 실행 가능한 상태의 고루틴이 있습니다.
이 때가 P1이 작업을 훔쳐야 할 순간입니다.
작업 스틸링 규칙은 다음과 같습니다.

runtime.schedule() {
    // only 1/61 of the time, check the global runnable queue for a G.
    // if not found, check the local queue.
    // if not found,
    //     try to steal from other Ps.
    //     if not, check the global runnable queue.
    //     if not found, poll network.
}

위 규칙에 따라 P1은 P2의 LRQ에서 고루틴들을 찾아 절반을 가져옵니다.


그림 11. Go Scheduler Work Stealing #2.


그림 11 에서 절반의 고루틴들을 P2에서 가져와서 P1은 고루틴들을 실행할 수 있습니다.
P2가 모든 고루틴들을 실행하고 P1에 LRQ가 남아 있지 않으면 어떻게 될까요?


그림 12. Go Scheduler Work Stealing #3.


그림 12 에서 P2는 모든 작업을 완료했으며 이제 작업을 훔쳐와야 합니다.
먼저 P1의 LRQ를 살펴 보지만 고루틴들을 찾지 못합니다. 다음으로 GRQ에서 G9를 찾았습니다.


그림 13. Go Scheduler Work Stealing #4.


그림 13 에서 P2는 GRQ에서 G9를 훔쳐서 작업을 시작합니다.
이 작업 스틸링의 좋은 점은 M들이 유휴 상태가 되지 않도록 만드는 것입니다.
이 작업 스틸링은 내부에서는 M을 회전시키는 것으로 간주합니다.
이 회전의 다른 장점은 JBD의 블로그 포스트에서 잘 설명되어 있습니다.




Practical Example

(작성 중)




결론

Go 스케줄러는 복잡한 OS와 하드웨어 작업 방식을 고려하여 설계되어 정말 놀랍습니다.
OS 레벨에서 I/O 블락킹 작업을 CPU-바운드 작업으로 전환하는 기능은 더 많은 CPU 용량을 활용하는 데 좋습니다.
이런 이유로 가상 코어보다 더 많은 OS 스레드가 필요하지 않습니다.
가상 코어 당 하나의 OS 스레드만으로 모든 작업(CPU 및 IO 블락킹 바운드)을 기대할 수 있습니다. 이렇게하면 OS 스레드를 차단하는 시스템 호출이 필요없는 네트워킹 앱 및 기타 앱에서 가능합니다.

개발자는 여전히 처리중인 작업의 종류에서 앱이 수행하는 작업을 이해해야합니다. 무제한 수의 고 루틴을 만들 수 없으며 놀라운 성능을 기대할 수 있습니다. 항상 적은 것이 더 많지만 이러한 Go Scheduler 의미를 이해하면 더 나은 엔지니어링 결정을 내릴 수 있습니다. 다음 포스트에서는 코드에 추가해야 할 복잡도의 균형을 유지하면서 더 나은 성능을 얻기 위해 보수적 인 방식으로 동시성을 활용하는 아이디어를 탐구 할 것입니다.




참고자료

Gloang Scheduling

댓글남기기

참고