Golang 스케줄러 Part.1 - OS 스케줄러

October 21, 2020 8 분 소요

Scheduling In Go : Part I - OS Scheduler을 번역한 글입니다.

프로그램은 순차적으로 실행해야하는 일련의 기계어 명령(machine instruction) 입니다.
이를 실행하기 위해 OS는 쓰레드(Thread) 라는 개념을 사용합니다.
쓰레드는 할당된 명령어 세트를 순서대로 더 이상 없을 때까지 계속 실행합니다.
그렇기 때문에 쓰레드를 실행 경로(a path of execution) 라고 부르기도 합니다.

프로그램을 실행하면 프로세스를 생성하고 각 프로세스에는 초기 쓰레드가 제공됩니다.
쓰레드는 더 많은 쓰레드를 생성할 수 있습니다. 이 모든 쓰레드들은 서로 독립적으로 실행되며
스케줄링은 프로세스 수준이 아니라 쓰레드 수준에서 결정됩니다.
쓰레드는 동시에(concurrently, 각각 개별 코어들을 사용) 또는 병렬로(parallel, 각각 다른 코어에서 동시에 실행)
실행될 수 있습니다. 쓰레드는 명령을 안전하게, 로컬 및 독립적으로 실행할 수 있도록 자체 상태를 유지합니다.

concurrency vs parallelism — 그림 1. Concurrency vs Parallelism.

OS 스케줄러는 실행 가능한 쓰레드가 있는 경우 코어(core)가 유휴 상태가 아닌지 확인합니다.
또한 실행할 수 있는 모든 쓰레드가 동시에 실행되는 것 같은 환상을 만들어야 합니다.
이 환상을 만드는 과정에서 스케줄러는 우선 순위가 낮은 쓰레드보다 높은 쓰레드를 실행해야 합니다.
그러나 우선 순위가 낮은 쓰레드가 실행 시간이 부족하지 않도록 해야합니다.
또한 스케줄러는 신속하고 현명하게 스케쥴 지연 시간을 최소화 해야합니다.

스케줄링를 위해 많은 알고리즘이 사용되지만 다행히도 업계에서 사용한 수십 년의 작업과 경험이 있습니다.
이 모든 것을 더 잘 이해하려면 중요한 몇 가지 개념을 설명하고 이해하는 것이 좋습니다.

명령 실행(Executing Instructions)

명령 포인터(Instruction Pointer) 라고도 불리는 프로그램 카운터(Program Counter) 는
쓰레드가 다음에 실행할 명령을 추적할 수 있습니다.
대부분의 프로세서에서 PC는 실행할 다음 명령을 가리킵니다.

Go 프로그램에서 스택 트레이스(Stack Trace)를 보면, 각 행의 끝에 작은 16 진수가 표시되어 있습니다.

다음 리스트1에서 +0x39 와 +0x72 를 찾아 보십시오.

리스트 1.

goroutine 1 [running]:
   main.example(0xc000042748, 0x2, 0x4, 0x106abae, 0x5, 0xa)
       stack_trace/example1/example1.go:13 +0x39                 <- LOOK HERE
   main.main()
       stack_trace/example1/example1.go:8 +0x72                  <- LOOK HERE

이 숫자들은 각 함수의 시작부터의 PC 오프셋 값을 나타냅니다.
+0x39 PC 오프셋 값은 프로그램이 패닉(panic)되지 않은 경우 쓰레드가 main.example 함수 내에서 실행할
다음 명령어를 나타냅니다.
0+x72는 PC 오프셋 값은 제어가 main.main 함수으로 되돌아가는 경우 해당 함수 내부의 다음 명령어입니다.
더 중요한 것은 그 포인터 앞의 명령어는 어떤 명령어가 실행되고 있는지 알려준다는 것입니다.

다음 리스트 2 에는 리스트 1 의 스택 트레이스가 발생한 프로그램입니다.

리스트 2.

https://github.com/ardanlabs/gotraining/blob/master/topics/go/profiling/stack_trace/example1/example1.go

func main() {
   example(make([]string, 2, 4), "hello", 10)
}

func example(slice []string, str string, i int) {
  panic("Want stack trace")
}

16 진수 +0x39 는 함수의 시작 명령어보다 57(10진수, 0x39) 바이트 아래의 example 함수 내의
명령어에 대한 PC 오프셋을 나타냅니다.
아래 리스트 3 에서 바이너리로부터 example 함수에 대한 objdump 를 볼 수 있습니다.
리스트의 맨 아래에 있는 12 번째 명령을 찾고, 명령 위의 코드 줄이 panic에 대한 호출임을 주목하세요.

리스트 3.

$ go tool objdump -S -s "main.example" ./example1
TEXT main.example(SB) stack_trace/example1/example1.go
func example(slice []string, str string, i int) {
  0x104dfa0		65488b0c2530000000	MOVQ GS:0x30, CX
  0x104dfa9		483b6110		CMPQ 0x10(CX), SP
  0x104dfad		762c			JBE 0x104dfdb
  0x104dfaf		4883ec18		SUBQ $0x18, SP
  0x104dfb3		48896c2410		MOVQ BP, 0x10(SP)
  0x104dfb8		488d6c2410		LEAQ 0x10(SP), BP
	panic("Want stack trace")
  0x104dfbd		488d059ca20000	LEAQ runtime.types+41504(SB), AX
  0x104dfc4		48890424		MOVQ AX, 0(SP)
  0x104dfc8		488d05a1870200	LEAQ main.statictmp_0(SB), AX
  0x104dfcf		4889442408		MOVQ AX, 0x8(SP)
  0x104dfd4		e8c735fdff		CALL runtime.gopanic(SB)
  0x104dfd9		0f0b			UD2              <--- LOOK HERE PC(+0x39)

Remember: PC는 현재 명령이 아니라 다음 명령입니다.
리스트 3 은 Go 프로그램의 쓰레드가 순서대로 실행되는,
amd64 기반 명령어의 좋은 예입니다.

쓰레드 상태(Thread States)

또 다른 중요한 개념은 쓰레드 상태입니다. 이는 스케줄러가 쓰레드에 수행하는 역할을 나타냅니다.
쓰레드는 세 가지 상태 중 하나 일 수 있습니다:
대기 중(Waiting), 실행 가능(Runnable) 또는 실행 중(Executing)

대기 중(Waiting):

쓰레드가 중지되었고 계속 진행하기 위해 무언가를 기다리고 있습니다.
하드웨어(디스크, 네트워크), 운영 체제(시스템 콜) 또는 동기화 콜(원자, 뮤텍스) 대기와 같은 이유로
발생할 수 있습니다.
이러한 유형의 대기 시간은 성능 저하의 근본 원인입니다.

실행 가능(Runnable):

쓰레드가 코어에서 시간을 원하고, 그렇게 되어야 할당된 기계 명령어를 실행할 수 있습니다.
시간을 원하는 쓰레드가 많은 경우 쓰레드는 더 오래 기다려야 합니다.
또한 시간이 지남에 따라 더 많은 쓰레드가 경쟁하기 때문에 주어진 쓰레드가 얻는 개별 시간이 줄어듭니다.
이러한 유형의 예약 대기 시간도 성능 저하의 원인이 될 수 있습니다.

실행 중(Executing):

쓰레드가 코어에 배치되어 해당 머신 명령어를 실행 중임을 의미합니다.
응용프로그램과 관련된 작업은 완료되었습니다. 이 상태는 모두가 원하는 것입니다.

작업 유형(Types Of Work)

쓰레드가 수행할 수있는 작업은 두 가지 유형이 있습니다.
첫 번째는 CPU-Bound 라고 하고, 두 번째는 IO-Bound 라고 합니다.

CPU-바운드(Bound):

쓰레드가 대기 상태에 놓일 수 있는 상황을 결코 만들지 않는 작업입니다.
예를 들면 계산만 수행하는 작업입니다.
N 번째 자리까지 Pi를 계산하는 쓰레드는 CPU- 바운드입니다.

IO-바운드(Bound):

쓰레드가 대기 상태로 들어가는 작업입니다.
네트워크를 통해 리소스에 대한 액세스를 요청하거나 운영 체제로 시스템 콜을 호출하는 작업입니다.
데이터베이스에 접근해야 하는 쓰레드도 IO- 바운드입니다.
쓰레드를 대기하게 하는 동기화 이벤트(뮤텍스, 원자)도 이 범주에 포함하겠습니다.

컨텍스트 전환(Context Switching)

Linux, Mac 또는 Windows는 선점형 스케줄러(Preemptive Scheduler) 가 있는 OS 입니다.
여기에는 몇 가지 중요한 의미가 있습니다.
첫째, 스케줄러는 주어진 시간에 어떤 쓰레드가 실행될 것인지 예측할 수 없다는 의미입니다.
이벤트(네트워크에서 데이터를 수신하는)와 쓰레드 우선 순위는 스케줄러가 수행할 작업과
시기를 판별하는 것이 불가능합니다.

다음으로, 매번 발생하지 않고, 운이 좋아 발생한 작업에 따라 코드를 작성해서는 안됩니다.
1000 번 같은 방식으로 발생했기 때문에 문제없다고 생각하기 쉽습니다.
애플리케이션에서 결정성(determinism)이 필요한 경우 쓰레드의 동기화 및 오케스트레이션으로 제어해야 합니다.

코어에서 쓰레드를 교환하는 물리적 동작을 컨텍스트 전환 이라고 합니다.
스케줄러가 실행 중인 쓰레드를 코어에서 빼고 실행 가능한 쓰레드로 바꾸면 컨텍스트 전환 이 발생합니다.
실행 큐에서 선택된 쓰레드는 실행 상태가 됩니다.
빼낸 쓰레드는 다시 실행 가능 상태(여전히 실행 가능한 경우) 또는 대기 상태(IO-바운드 유형의 요청으로
교체된 경우)가 됩니다.

컨텍스트 전환 은 쓰레드를 코어에서 교체하는 데 시간이 걸리기 때문에 비용이 많이 드는 것으로 간주됩니다.
컨텍스트 전환 중 지연 시간은 여러 가지 요인에 따라 다르지만 ~1000 에서 ~1500 나노초 사이로
불합리한 것은 아닙니다.
하드웨어가 코어 당 나노 초당 (평균) 12 개의 명령을 실행할 수 있다는 것을 고려할 때 컨텍스트 전환 은
~12k 에서 ~18k 명령을 실행하는 시간을 소비할 수 있습니다.
본질적으로, 프로그램은 컨텍스트 전환 중에 많은 수의 명령을 실행할 수 있는 능력을 상실합니다.

IO-바운드 작업에 중점을 둔 프로그램이 있다면 컨텍스트 전환 이 유리할 것입니다.
쓰레드가 대기 상태로 이동하면 실행 가능 상태의 다른 쓰레드가 대신 실행됩니다.
코어가 항상 작업을 수행 할 수 있기 때문에, 스케줄링에서 가장 중요한 측면 중 하나입니다.
해야할 작업(실행 가능 상태의 쓰레드)이 있다면, 코어가 유휴 상태가 되지 않도록 해야합니다.

프로그램이 CPU-바운드 작업에 중점을 둔다면 컨텍스트 전환은 성능에 좋지 않습니다.
컨텍스트 전환 으로 인해 할 수 있는 작업이 진행되지 않기 때문입니다.
이 상황은 IO-바운드 에서 발생하는 상황과 완전히 대조됩니다.

적을 수록 좋다(Less Is More)

프로세서에 코어가 하나 밖에 없었던 초기에는 스케줄이 복잡하지 않았습니다.
단일 코어를 가진 단일 프로세서를 사용했으므로 주어진 시간에 하나의 쓰레드만 실행할 수 있었습니다.
즉, [스케줄러 기간](https://lwn.net/Articles/404993/을 정의하고 해당 기간 내에 모든 실행 가능 쓰레드를
실행했습니다.

문제 없음: 예약 기간을 가져 와서 실행해야 하는 쓰레드 수로 나누었습니다.

하지만 지금은, 스케줄 결정을 할 때 스케줄러가 고려해야 하고 처리해야 할 사항이 더 있습니다.
애플리케이션에서 사용하는 쓰레드 수를 제어합니다.
고려해야 할 쓰레드가 많고 IO-바운드 작업이 발생하면 혼돈과 비결정적 동작이 더 많습니다.
스케줄하고 실행하는 데 시간이 더 걸리게 됩니다.

실행 가능 상태의 쓰레드 수가 적으면 스케줄링 부하가 줄어들고 각 쓰레드가 시간이 지남에 따라
더 많은 시간을 소비할 수 있습니다.
실행 가능 상태의 쓰레드가 많을수록 시간이 지남에 따라 각 쓰레드가 얻는 시간이 줄어듭니다.
즉, 시간이 지남에 따라 수행되는 작업이 줄어듭니다.

균형을 찾아라(Find The Balance)

보유한 코어 수와 애플리케이션에 대한 최상의 처리량을 얻는 데 필요한 쓰레드 수 사이에서 균형을 찾아야 합니다.
이 균형을 관리할 때 쓰레드 풀이 좋은 해답이었지만, Go 스케줄러에서는 더이상 필요하지 않습니다.
멀티쓰레드 응용프로그램 개발을 보다 쉽게하기 위한 Go의 장점 중 하나라고 생각합니다.

윈도우에서 멀티쓰레드 소프트웨어를 작성하려면, IOCP(IO Completion Ports) 쓰레드 풀을 사용해야 했습니다.
엔지니어는 주어진 코어 수에 대한 처리량을 최대화하기 위해 필요한 쓰레드 풀 수와
주어진 풀의 최대 쓰레드 수를 파악해야 했습니다.

(작성 중)

Cache Lines

메인 메모리에서 데이터에 접근하면 대기 시간이 길기(~100 ~ ~300 clock cycle) 때문에
프로세서와 코어에는 로컬 캐시가 있어 하드웨어 쓰레드에 필요한 데이터를 가깝게 유지합니다.
캐시에서 데이터에 접근하면 비용이 훨씬 저렴합니다(~3 ~ ~40 clock cycle).
오늘 날의 성능 개선의 한 부분은 이러한 데이터 접근 대기 시간을 줄이기 위해 프로세서로 데이터를
얼마나 효율적으로 가져올 수 있는 지에 관한 것입니다.
상태가 바뀌는 멀티쓰레드 응용프로그램을 작성하려면 캐싱 시스템의 메커니즘을 고려해야 합니다.

데이터는 캐시 라인(cache lines) 을 사용하여 프로세서와 주 메모리 간에 교환됩니다.
캐시 라인 은 주 메모리와 캐싱 시스템 간에 교환되는 64 바이트 메모리입니다.
각 코어에는 필요한 캐시 라인 의 복사본이 제공되므로 하드웨어가 값을 복사(value semantics)해서
사용합니다.
이것이 멀티쓰레드 응용프로그램에서 성능을 저하시킬 수 있는 이유가 될 수 있습니다.

병렬로 실행되는 여러 쓰레드가 동일한 데이터 값 또는 서로 가까운 데이터 값에 액세스하는 경우
동일한 캐시 라인 의 데이터에 접근합니다.
모든 코어에서 실행되는 모든 쓰레드는 동일한 캐시 라인의 자체 사본을 얻습니다.

주어진 코어에서 하나의 쓰레드가 캐시 라인 의 복사본을 변경하면 하드웨어의 마법을 통해 동일한 캐시 라인 의
다른 모든 복사본은 더티(dirty)로 표시해야합니다.
쓰레드가 더티 캐시 라인에 대한 읽기 또는 쓰기 액세스를 시도 할 때 캐시 라인의 새 복사본을 얻으려면
기본 메모리 액세스 (~100 ~ ~300 clock cycle)가 필요합니다.

2-코어 프로세서에서는 큰 문제가 아니지만 32 개의 쓰레드를 동시에 실행하여 동일한 캐시 라인 에서
데이터에 접근하고 변경하는 32-코어 프로세서는 문제가 됩니다.
각각 16 개의 코어가 있는 2 개의 물리적 프로세서가 있는 시스템도 문제가 됩니다.
프로세서 간 통신에 대한 대기 시간이 추가되어 상황이 악화될 수 있습니다.
응용프로그램이 메모리를 통해 허우적되고, 성능이 끔찍할 것이며, 당신은 그 이유를 이해할 수 없을 것입니다.

이를 캐시 일관성(cache-coherency) 문제라고 하며 허위 공유(false sharing)와 같은 문제가 발생합니다.
공유 상태를 변경하는 멀티쓰레드 응용프로그램을 작성할 때는 캐싱 시스템을 고려해야 합니다.

스케줄링 결정 시나리오(Scheduling Decision Scenario)

지금까지의 정보를 기반으로 OS 스케줄러를 작성하도록 요청했다고 상상해보십시오.
이것은 스케줄러가 스케줄 결정을 할 때 고려해야 할 많은 흥미로운 것 중 하나입니다.

응용프로그램을 시작하면 기본 쓰레드가 생성되어 코어1 에서 실행됩니다.
쓰레드가 해당 명령을 실행하기 시작하면 데이터가 필요하기 때문에 캐시 라인 이 검색됩니다.
쓰레드는 이제 동시 처리를 위해 새 쓰레드를 작성하기로 결정합니다.
이제 질문이 있습니다.

쓰레드가 생성되어 준비가 되면 스케줄러는:

코어1 에서 메인 쓰레드를 컨텍스트 전환 하시겠습니까?
이 새로운 쓰레드가 이미 캐시된 동일한 데이터를 필요로 할 가능성이 매우 높기 때문에
이를 수행하면 성능에 도움이 될 수 있습니다. 그러나 메인 쓰레드는 풀 타임 슬라이스를 얻지 못합니다.
쓰레드가 메인 쓰레드의 타임 슬라이스가 완료될 때까지 코어 1이 사용 가능할 때까지 기다리나요?
쓰레드가 실행되고 있지 않지만 데이터를 가져오는 데 걸리는 대기 시간은
일단 시작되면 제거됩니다.
쓰레드가 메인 쓰레드의 타임 슬라이스가 완료될 때까지 코어1 이 사용 가능할 때까지 기다리나요?
쓰레드가 실행되고 있지 않지만 데이터를 가져 오는 데 걸리는 대기 시간은 일단 시작되면 제거됩니다.
쓰레드가 사용 가능한 다음 코어를 기다립니까?
즉, 선택한 코어의 캐시 라인 이 플러시(flushed), 검색(retrieved) 및 복제(duplicated)되어 대기 시간이 발생합니다.
그러나 쓰레드가 더 빨리 시작되고 기본 쓰레드가 타임 슬라이스를 완료할 수 있습니다.

아직도 재미있나요? 스케줄링 결정시 OS 스케줄러가 고려해야 할 흥미로운 질문입니다.
다행스럽게도 우리는 OS 스케줄러를 만드는 사람이 아닙니다.
말할 수 있는 것은 idle 코어 가 있으면 사용된다는 것입니다.
쓰레드가 실행될 수 있을 때 실행하고 싶을 것입니다.

결론

지금까지 멀티쓰레드 응용프로그램을 작성할 때 쓰레드 및 OS 스케줄러와 관련하여
고려해야 할 사항에 대해 설명했습니다.
이 것은 Go 스케줄러도 고려해야 할 사항입니다.
다음 포스트에서는 Go 스케줄러의 의미와 OS 스케줄러와의 관계에 대해 설명합니다.

참고자료

Gloang Scheduling

Scheduling In Go : Part I - OS Scheduler
Scheduling In Go : Part II - Go Scheduler
Scheduling In Go : Part III - Concurrency
Introduction 2016 NUMA Deep Dive Series
Go FAQ - Why goroutines instead of threads?
… to multiplex independently executing functions—coroutines—onto a set of threads
Work Stealing

Twitter Facebook LinkedIn

cppis