원문: https://rakyll.org/scheduler/

Go 스케줄러는 하나 이상의 프로세서에서 실행되는 여러 OS 스레드에 실행가능한 고루틴을 배포하는 일을 합니다. 멀티쓰레드 컴퓨팅에는 작업공유와, 작업훔치기라는 두가지 패러다임이 있습니다.

  • 작업공유: 프로세서가 새로운 쓰레드를 생성할 때, 대기중이거나 적게 사용되는 프로세서로 마이그레이션하려고 시도합니다.
  • 작업훔치기: 적게 사용되는 프로세서가 다른 프로세서의 쓰레드를 적극적으로 찾고 훔칩니다.

쓰레드의 마이그레이션은 작업공유보다 작업훔치기에서 적게 일어납니다. 모든 프로세서가 작동하고 있으면, 마이그레이션은 일어나지 않습니다. 대기중인 프로세서가 있으면 즉시 마이그레이션이 고려됩니다.

Go는 1.1부터 Dmitry Vyukov의 기여에 의해 작업훔치기 스케줄러를 가졌습니다. 이 글은 작업훔치기 스케줄러가 무엇이고, Go에서 어떻게 구현되어 있는지 설명합니다.

스케줄링 기본지식

Go에는 다중 프로세서를 활용할 수 있는 M:N 스케줄러가 있습니다. 언제든지 N(최대 GOMAXPROCS 설정만큼)개의 OS 쓰레드에서 M개의 고루틴을 스케줄링할 수 있습니다. Go 스케줄ㄹ러는 고루틴, 쓰레드, 프로세서에 대해 다음 용어를 사용합니다:

  • G: 고루틴
  • M: OS 쓰레드 (machine)
  • P: 프로세서

각 로컬 고루틴 큐와 글로벌 고루틴 큐는 전용 P를 가집니다. 각 M은 P에 할당됩니다. P가 블록되거나 시스템 호출 중이면 M이 없을 수 있습니다. 최대 GOMAXPROCS만큼 P를 가질 수 있습니다. 오직 하나의 M만 P에서 실행될 수 있습니다. 필요하다면 더 많은 M이 스케줄러에 의해 생성됩니다.

스케줄링시마다 실행가능한 고루틴을 찾고 실행시킵니다. 각 스케줄링에서 탐색은 다음과 같은 순서로 일어납니다:

runtime.schedule() {
    // 61분의 1 시간동안. 글로벌 큐에서 G를 확인합니다.
    // 찾을 수 없는 경우, 로컬 큐를 확인합니다.
    // 찾을 수 없는 경우,
    //     다른 P에서 작업훔치기를 시도합니다.
    //     없으면, 글로벌 큐를 확입합니다.
    //     없으면, 네트워크 폴을 합니다.
}

실행가능한 G가 발견되면, 이것이 블록될 때까지 실행합니다.

참고: 글로벌 큐가 로컬 큐보다 유리한 것처럼 보이지만, M은 로컬 큐에 대기중인 고루틴이 없을 경우에만 글로벌 큐를 확인합니다.

훔치기

새로운 G가 생기거나 기존 G가 실행가능하게 되면, P의 실행가능 고루틴 목록으로 푸시됩니다. P가 G를 실행하고 나면, 실행가능 목록에서 팝됩니다. 만약 목록이 비면, P는 임의의 다른 P의 실행가능 고루틴의 절반을 큐에서 훔칩니다.

위의 경우, P2는 실행 가능한 고루틴을 찾을 수 없습니다. 따라서, 임의의 다른 프로세서(P1)를 선택하여 세 개의 고루틴을 로컬 큐로 훔칩니다. P2는 이 고루틴들을 실행할 수 있으며 여러 프로세서 간에 공평하게 작업이 분산됩니다.

스피닝 쓰레드

스케줄러는 언제나 M들에게 실행 가능한 고루틴을 배포하여 프로세서를 활용하려고 하며, CPU와 전력을 절약하기 위해 많은 작업을 필요로 합니다. 모순되게도, 스케줄러는 높은 처리량과 CPU 중심의 프로그램에도 사용되어야 합니다.

성능이 중요한 요소일 경우 지속적인 강탈은 비용이 많이 들고, 높은 처리량의 프로그램은 문제가 됩니다. OS 쓰레드는 대기시간을 증가시키기 때문에 실행가능한 고루틴을 자주 넘겨서는 안됩니다. 시스템 호출이 있는 상황에서, OS 쓰레드는 지속적으로 블록되었다 해제됩니다. 이것은 비용이 큰 오버헤드를 유발합니다.

고루틴 넘기기를 최소화하기 위해, Go 스케줄러는 스피닝 쓰레드를 구현했습니다. 스피닝 쓰레드는 CPU를 약간 소비하지만 OS 쓰레드의 강탈을 최소화합니다. 다음의 경우에 스피닝됩니다:

  • P가 할당된 M이 실행가능 고루틴을 찾을 경우.
  • P가 할당되지 않은 M이 사용가능한 P를 찾을 경우.
  • 대기중인 P가 하나 있고 다른 스피닝 쓰레드가 없을 경우.

많으면 GOMAXPROCS만큼 스피닝 중인 M이 있습니다. 스피닝 쓰레드가 작업을 찾으면, 스피닝 상태를 벗어납니다.

P가 없는 대기중인 M이 있을 경우 P가 있는 대기중인 쓰레드는 블럭되지 않습니다. 새로운 코루틴이 생성되거나 M이 차단 될 때 스케줄러는 적어도 하나의 스피닝 M이 있음을 보장합니다. 이것은 실행가능한 고루틴이 없는 상태이며, 결과로 과도한 M 블럭/해제를 막습니다.

결론

Go 스케줄러는 OS 쓰레드의 과도한 강탈을 방지하기 위해 작업훔치기를 사용하여 스케줄링하고, 스피닝 쓰레드를 구현하여 블럭/해제가 많이 발생하는 것을 피합니다.

스케줄링 이벤트는 execution tracer로 추적가능합니다. 프로세서 사용율이 낮다고 생각되면 어떤 일이 일어나는지 조사할 수 있습니다.

참고

제안이나 의견이 있으시면 @rakyll에게 알려주십시오.