[GopherCon 2021] Go Scheduler

스케줄러는 go 프로그램의 뒤에서 지휘하는 orchestrator이다.

go의 스케줄러가 어떻게 동작하는지 알아본다.

1. 왜 스케줄러를 갖고 있지?

• 고루틴은 OS가 아닌 go runtime에 의해 관리되는 user-space 스레드들이다.
• 커널 스레드보다 경량이다.
  • 생성, 삭제, context switch가 스레드보다 빠르다.
  • 메모리 사용이 더 적다.

goroutine은 kernal thread 위에서 동작한다.

runtime중 switch가 일어날 경우 해당 thread에 다른 goroutine을 스케줄링할 수 있다.

• 고루틴의 목표
  • 작은 커널 스레드를 유지한다.
  • 높은 동시성을 제공한다.
  • core 갯수만큼 고루틴을 병렬로 실행한다.

2. 어떻게 thread들 사이에서 고루틴을 분산하지?

• 실행할 준비가 되어 있고 스케줄되어야 하는 고루틴은 heap에 할당된 FIFO unqueue에 저장된다.

• single thread에서 모든 고루틴을 돌린다면?
  • 동시성, 병렬성 제공 불가
• 고루틴마다 thread를 만든다면?
  • thread는 무거운 자원이므로, 고루틴의 목적에 어긋난다.
• 고루틴에서 thread t1를 생성하고, 작업이 끝났으면 runqueue에 park 해놓는다.
• 새로운 g2가 실행되면 이미 만들어진 t1에 할당해서 실행한다. (재사용)
• https://speakerdeck.com/kavya719/the-scheduler-saga?slide=31

The Scheduler Saga

• 이렇게 하면 스레드 생성을 줄일 수 있지만, 여러 스레드에서 하나의 runqueue에 접근할 수 있으므로 lock이 필요하다.
• 무한한 수의 스레드가 생성될 수 있다. 이 스레드들이 runqueue에 접근 가능하다면 경쟁이 발생한다.
• -> runqueue에 접근 가능한 스레드의 수를 CPU core 수만큼 제한한다.
• https://speakerdeck.com/kavya719/the-scheduler-saga?slide=53
• CPU 개수가 늘어난다면?

늘어나면 그만큼 오래 걸린다.

• runqueues를 core 수만큼 생성한다.
• local runqueue가 비었으면 다른 runqueue에서 훔쳐서 스레드간 밸런스를 맞춘다.
• https://speakerdeck.com/kavya719/the-scheduler-saga?slide=67

• 위처럼 thread가 block된 경우는?
• background의 모니터 스레드가 block된 스레드를 찾고, 차단된 스레드의 실행 대기열을 다른 스레드로 전송한다.
• park된 스레드를 실행하거나 필요한 경우 새로 스레드를 시작한다.
  • thread limit은 실행중인 고루틴 스레드에만 적용되므로, 새로 시작해도 된다!

• 거대한 작업이 CPU를 점유한다면? -> go 스케줄러는 preemption(선점)을 구현한다.
  • sysmon이라는 background 스레드에서 돌아간다.
  • 10ms 이상 걸리는 goroutine을 찾고 가능할 때 unschedule한다.
  • 본질적으로 다른 고루틴의 실행을 방해하므로 코어별 실행 대기열에 다시 넣고 싶지 않을 수 있다.
  • 고루틴은 분산 runqueue와 더불어 global runqueue를 갖고있다.
  • global runqueue는 우선 순위가 낮아 스레드가 local runqueue보다 덜 적게 접근하므로, 경쟁이 이슈가 되지 않는다.
• thread spinning
  • 작업이 없는 스레드는 parking 상태가 되기 전에 작업을 찾기 위해 spin한다.
  • global runqueue 확인, 네트워크 poll, gc 시도, 작업을 훔친다.
  • 이 작업은 CPU 소모가 많지만 병렬성을 극대화한다.

3. 정리

• 고루틴의 목표는 구현 방식으로 달성된다.
  • 작은 커널 스레드를 유지한다. -> reuse & thread 개수 제한
  • 높은 동시성을 제공한다. -> 스레드가 독립적인 runqueue를 갖고있고 균형있게 유지된다.
  • core 갯수만큼 고루틴을 병렬로 실행한다. -> core당 runqueue 할당 & thread spinning
• 한계가 있다.
  • FIFO runqueue - 글로벌 우선순위에 대한 개념이 없다.
  • no real locality - system topology에 대한 이해가 없다.
    • 최근에 runqueue에 FIFO 대신 LIFO 사용해서 cache utilization을 활용하고 있다.

 

https://www.youtube.com/watch?v=wQpC99Xu1U4

위 영상을 보고 정리한 글입니다.