Goroutine이 thread에 비해 lightweight인 이유
기존에 커널이 처리하던 스케줄링을 Goroutine은 컴파일러와 Go 런타임이 처리.
대다수의 커널은 Preemptive Scheduling(선점 스케줄링)을 택하고 있으므로 프로세스나 스레드는 커널에 의해 원치 않게 CPU를 회수당할 수 있음.(자원 독점을 방지하기 위해)
Go런타임은 Cooperative Scheduling(협조 스케줄링)을 택하여 Goroutine이 자발적으로 실행을 종료하거나 대기상태로 전환되길 기다림.
- 이렇게 Cooperative한 서브루틴들을 Co-routine이라고 함.(Go-routine도 여기서 따옴...)
스레드 스위칭에서는 Stack Pointer, Program Counter와 같은 Thread Control Block을 저장 후 로드해야 함.(PCB보단 오버헤드가 훨씬 적음)
Goroutine은 well-defined safe-point function call에서만 프로세서를 양보하며, 이러한 point들은 blocking에 관한 operation들이므로 구동에 필요한 레지스터 이외에는 사용하지 않음.
- Goroutine switch에는 단 3개(SP, PC, DX)만 store/restore하면 됨.
OS 대신 Go 런타임이 Goroutine에 스택 할당.
- OS 스레드는 실행 중에 스택 크기를 조정할 수 없지만, Go 런타임은 유동적으로 Goroutine의 스택 사이즈를 조절할 수 있음.
- 하나의 스레드 스택이 수십~수천 KB를 차지하는 반면 Goroutine 스택은 단 2KB에서 시작됨.
- 그래서 많은 Goroutine을 생성해도 문제가 없음.
생성 및 삭제 시 Goroutine은 System Call 없이 유저 스페이스에서 동작해 훨씬 빠름.
스케줄링 원칙
커널 스레드는 비싸기 때문에 되도록 작은 수를 사용.
많은 수의 goroutine을 실행하여 높은 concurrency[1]를 유지.
N 코어 머신에서 N개의 goroutine을 Parallel[1]하게 동작시킴.
스케줄러 내부 구성
G: Goroutine을 의미.
M: Machine, 즉 OS의 스레드를 의미. 표준 POSIX 스레드를 따름.
P: Processor, 스케줄링에 대한 context를 지니고 있음.
- Goroutine은 반드시 P와 M이 존재할 경우에만 executing 상태가 되므로, 동시에 최대로 구동시킬 수 있는 Goroutine의 개수는 P의 개수에 따라 정해짐.
- GOMAXPROCS 환경 변수 혹은 runtime.GOMAXPROCS() 함수로 갯수 조절 가능.
- v1.15 이전 기본값은 1, v1.15부터 기본값은 사용 가능한 코어 수.
Run Queue
실행 가능한 상태의 Goroutine들을 보관하는, 힙에 할당된 리소스.(즉 대기열)
GRQ(Global Run Queue)
LRQ에 할당되지 못한 대부분의 Goroutine들이 모여 있는 Run queue.
Goroutine이 생성되었을 때 해당 Processor의 LRQ가 가득찬 경우 GRQ에 저장됨.
GRQ는 Heap 영역의 공동 리소스이고, 접근할 때마다 Lock이 필요함.
LRQ(Local Run Queue)
각 Processor마다 존재하는 Run queue.
- 스레드가 소유한 게 아닌 이유는, 스레드 수만큼 LRQ를 만들면 LRQ가 너무 많아지기 때문.(Work stealing 등의 오버헤드가 커짐)
Processor는 자신이 소유하는 LRQ로부터 Goroutine을 하나씩 가져와 구동시킴.
GRQ에서 발생하는 Race Condition을 줄임.
FIFO와 Size 1짜리 LIFO로 이루어짐.
- Enqueue 시: LIFO에 먼저 저장되고, 이후 FIFO 부분에 저장.
- Dequeue 시: LIFO에서 먼저 꺼내고, 이후 FIFO에서 꺼냄.
- Goroutine에서 새로 생성된 Goroutine을 해당 Processor의 LRQ LIFO에 저장하여 빠르게 생성한 곳과 동일한 Processor에서 실행.
- 이를 통해 Goroutine에 Locality 부여.
스케줄링 방식
Reuse thread
Create threads when needed; Keep them around for reuse.
Runtime Scheduler는 goroutine이 필요할 때 스레드를 생성.
스레드에 더 이상 실행할 goroutine이 없다면 스레드를 종료하는 대신 idle 상태로 둠.
- 종료 시 System Call이 필요하며, 자원 반납에 로드가 있음.
- 나중에 다시 스레드가 필요해지면 부하가 또 발생.
- idle 상태일 경우 CPU 코어를 사용하지 않고 대기할 수 있음.
- idle 상태의 스레드 리스트는 별도 보관.
Limit threads accessing runqueue
Goroutine이 끊임 없이 생성되더라도 생성할 수 있는 스레드 수가 Processor 수를 넘지 않음.
- 단, 이 스레드 limit은 goroutine을 실행하고 있는 스레드만 해당됨.
- System Call에서 사용되는 스레드는 이 조건에 포함되지 않음.
Distributed runqueues
Use N runqueues on an N-core machine.
스레드가 새로 만들어졌거나 작업이 너무 빨리 끝날 경우 run queue에 할당된 goroutine이 없을 수 있음.
이를 해결하기 위해, 다음 순서대로 goroutine을 가져옴.(Work Stealing)
1. 다른 LRQ에 goroutine이 있는지 보고, 있을 경우 절반의 goroutine을 가져옴.
2. 1에 goroutine이 없을 경우 GRQ에 goroutine이 있는지 보고, 있을 경우 goroutine을 가져옴.
3. 2에도 goroutine이 없을 경우 Net poller에 goroutine이 있는지 보고, 있을 경우 goroutine을 가져옴.
단, Goroutine의 Locality를 위해 새로 생성된 goroutine은 3ms동안 stealing 되지 않도록 제한함.
Fairness
모든 Goroutine은 되도록 공평하게 실행되어야 함.
Thread: Goroutine이 이용중인 스레드를 반환하지 않고 계속 이용할 수 있으므로 goroutine이 10ms 이상 실행되는 경우 해당 goroutine을 timeout시키고 선점하여 강제로 GRQ로 보냄.
LRQ: 2개의 Goroutine이 LRQ에 번갈아가면서 저장되고 실행될 경우 LRQ의 LIFO 부분에 의해 FIFO 부분의 goroutine이 실행되지 않을 수 있음. 이를 막기 위해 LIFO 부분의 goroutine은 10ms timeout이 초기화되지 않도록 하여, LRQ의 LIFO 부분을 하나의 10ms 이상 점유하지 못하게 함.
GRQ: LRQ에 존재하는 goroutinea만을 실행하면 GRQ에 존재하는 Goroutine이 실행되지 않을 수 있으므로 '61번' Goroutine Scheduling을 수행할 때 LRQ보다 GRQ에 있는 Goroutine을 먼저 확인하고 실행하게 함.
Network Poller: 독립된 Background thread로, OS Scheduler에 따라 동작을 보장 받음.
System Call
I/O와 같은 sync system call이 발생할 경우 Blocking이 발생함.
스레드를 새로 만들고, block된 goroutine을 제외한 Processor를 통째로 새로운 스레드로 넘겨서(Hand off) 다음 goroutine 실행.
- 이렇게 context를 유지하며 다른 스레드로 넘겨 지속적으로 처리를 할 수 있게끔 Processor가 존재.
- 그 동안 기존 스레드와 goroutine은 sync system call 수행.
- 즉 block된 goroutine 수만큼 스레드가 더 생성됨.(System call에서 사용되는 스레드는 Limit 조건에 포함되지 않으므로)
Sync system call이 완료되었다면 다시 LRQ에 들어가고, 남은 스레드는 idle 상태로 진입.
Async system call을 호출한 goroutine은 Network Poller에 들어가서 완료 event 대기.
Network poller가 완료 event를 수신하고, 해당 goroutine을 다시 LRQ로 보냄.
Goroutine이 자원을 양보하는 경우
- Go 키워드
- 새로운 goroutine을 시작할 때 starvation을 방지하기 위해 스케줄링 요청.(새로운 goroutine이 스케줄링 되는 것을 보장하진 않음)
- Garbage Collection
- Go 런타임은 어떤 goroutine이 heap을 사용하는지 알 수 있으므로 STW(Stop-The-World)를 하지 않고 GC 전후로 복잡한 스케줄링 진행.
- Goroutine이 Syscall을 발생시키는 경우
- System I/O 발생
- cgocall(go에서 직접 c코드 실행)에서도 발생.
- User code로 blocking이 발생하는 경우
- 채널 send/receive로 block
- atomic, sync 패키지들의 block operation들
- time.Sleep
- runtime.Gosched: 명시적으로 자원 양보하는 function
[1] Concurrency vs Parallelism
Concurrenty is a property of the program and parallel execution is a property of the machine.
Concurrency는 프로그램의 성질이고 Parallel execution은 기계의 성질이다.
Concurrency(병행성)
어떤 프로그램이나 알고리즘이 순서에 상관 없이 동시에 수행될 수 있음.
프로그램 혹은 알고리즘의 개념이며, 싱글코어와 같이 병렬성을 제공하지 않는 머신에서도 동작 가능함.
- 물리적인 제약으로 시분할 형태로 돌아가겠으나, 분할된 각 알고리즘은 순서 관계 없이 동시에 진행되는 것처럼 보이게 할 수 있음.
Concurrency bug: 멀티 스레드 프로그램에서 벌어지는 각종 버그.
- 병렬성과 별개로 논리적으로 발생하므로 concurrency가 맞음.
Parallellism(병렬성)
어떤 작업을 물리적으로 동시에 처리할 수 있음.
OpenMP, MPI, CUDA 등은 물리적으로 제공되는 다양한 병렬 하드웨어를 활용하므로 병렬 프로그래밍.
참고자료
