[OSTEP] 10. Multi-CPU Scheduling
이 포스팅은 Operating Systems: Three Easy Pieces, Remzi H. Arpaci-Dusseau & Andrea C. Arpaci-Dusseau을 읽고 개인 학습용으로 정리한 글입니다.
CH 10. 멀티프로세서 스케쥴링 (고급)
- 여러 CPU에 작업을 어떻게 스케쥴해야 하는가?
1. 배경: 멀티 프로세서 구조
-
단일 CPU 하드웨어와 멀티 CPU하드웨어의 차이점:
다수의 프로세서 간에 데이터 공유, 하드웨어 캐시의 사용 방식에 차이 발생 -
단일 CPU 시스템에는 하드웨어 캐시 계층 존재
-> 자주 접근되는 데이터를 캐시에 임시로 저장
-> 시스템은 크고 느린 메모리를 빠른 메모리처럼 보이게 한다 -
캐시는 지역성에 기반한다
-> 시간 지역성(temporal locality): 데이터가 한 번 접근되면 가까운 미래에 다시 접근되기 쉽다
-> 공간적 지역성(spatial locality): 프로그램이 주고 x의 데이터를 접근하면 x 주변의 데이터가 접근되기 쉽다
캐시 일관성 문제(cache coherence)
- 하나의 시스템에 여러 프로세서가 존재하고 하나의 공유 메인 메모리가 있는 경우
-> 캐시 일관성 문제 발생
- 기본적인 해결책은 하드웨어에 의해 제공된다
-> 메모리 주소를 계속 감시하여 항상 제대로된 상황만 발생하도록
-> 여러 개의 프로세스들이 하나의 메모리에 갱신할 때에는 항상 공유되도록
버스 스누핑(bus snooping)
-
버스 기반 시스템에서는 버스 스누핑 기법을 사용한다
-
캐시는 자신과 메모리를 연결하는 버스의 통신 상황을 계속 모니터링한다
-> 캐시 데이터에 대한 변경이 발생하면, 자신의 복사본을 무효화(invalidate)시키거나, 갱신한다.
2. 동기화를 잊지 마시오
-
일관성 유지에 대한 모든 일을 캐시에서 담당한다면, 프로그램 또는 운영체제 자신은 고유 데이터를 접근할 때 걱정할 필요가 있을까? YES
-
CPU들이 동일한 데이터 또는 구조체에 접근/갱신할 때, 올바른 연산 결과를 보장하기 위해 lock과 같은 상호 배제를 보장하는 동기화 기법 사용
(락-프리(lock-free) 데이터 구조 등의 다른 방식은 복잡함 & 특별한 경우에만 사용된다) -
lock 사용법:
간단한 mutex (ex. pthread_mutex_t m;)를 할당하여 루틴의 시작에 lock(&m) , 마지막에 unlock(&m) 추가한다 -
CPU의 개수가 증가할수록 동기화된 자료구조에 접근하는 연산은 매우 느리게 된다
3. 마지막 문제점: 캐시 친화성
-
캐시 친화성(cache affinity)
-
CPU에서 실행될 때 프로세스는 해당 CPU 캐시와 TLB에 상당한 양의 상태 정보를 올려 놓게 됨
-> 다음 번에 프로세스가 실행될 때 동일한 CPU에서 실행되는 것이 유리
-> 프로세스가 매번 다른 CPU에서 실행되면 실행할 때마다 필요한 정보를 캐시에 탑재해야 함
4. 단일 큐 스케쥴링
- 단일 큐 멀티프로세서 스케쥴링 (single queue multi processor scheduling, SQMS)
-> 단일 프로세서 그케쥴링의 기본 프레임 워크 그대로 사용
-> CPU가 2개라면 실행할 작업 두 개를 선택한다.
확장성(scalability) 결여
- 스케쥴러가 다수의 CPU에서 제대로 동작하게 하기 위해 코드에 일정 형태의 락 삽입
-> 락은 시스템의 CPU 개수가 증가할수록 성능을 크게 저하시킬 수 있다
-> 동기화 오버헤드
캐시 친화성 문제
- 실행할 5개의 작업(A, B, C, D, E)이 있고 4개의 프로세서가 있는 경우
캐시 친화성 문제 해결
- 대부분의 SQMS 스케쥴러는 가능한 프로세스가 동일한 CPU에서 실행될 수 있도록 함
-> 특정 작업들(ex. A, B, C, D)에 대하여 캐시 친화성을 고려하여 스케쥴링 & 다른 작업들(ex. E)은 오버헤드를 균등하게 하기 위해 여러 군데로 분산시키는 정책 사용
- 다음에는 다른 작업(ex. E가 아닌 작업)을 이동시켜 일종의 친화성에 대한 형평성도 추구할 수 있다
5. 멀티 큐 스케쥴링
-
일부 시스템은 멀티 큐, 예를 들어 CPU마다 큐를 하나씩 둔다
-
멀티 큐 멀티프로세서 스케쥴링(multi-queue multiprocessor scheduling, MQMS)
-> 기본적인 스케쥴링 프레임워크는 여러 개의 스케쥴링 큐로 구성
-> 각 큐는 RR같은 특정 스케쥴링 규칙을 따른다 -
작업이 시스템에 들어가면 하나의 스케쥴링 큐에 배치된다.
-> 배치된 큐의 결정은 적당한 방법을 따른다 (ex. 무작위, 다른 큐보다 작은 수의 작업이 있는 큐로 배치, ...)
-> 그 후는 각각이 독립적으로 스케쥴되기 때문에 공유 및 동기화의 문제를 피할 수 있다
예.
- 2개의 CPU와 4개의 작업(A, B, C, D)
- CPU는 각자 하나씩의 스케쥴링 큐를 가짐
-
확장성 좋음
-> CPU 개수가 증가할수록 큐의 개수도 증가
-> 락과 캐시 경합(cache contention) 문제 X
(cache contention: when two or more CPUs alternately and repeatedly update the same cache line) -
친화성 좋음
-> 작업이 같은 CPU에서 계속 사용됨
-> 캐시에 저장된 내용을 재사용하는 이점
워크로드의 불균형(load imbalance)
- 2개의 CPU와 4개의 작업(A, B, C, D) 중 하나(예. C)가 종료된 경우
-> A가 B와 D보다 2배의 CPU를 차지하게 된다
- 위 상태에서 작업 A도 종료된 경우
-> CPU 하나는 유휴 상태가 된다
워크로드 불균형에 대처하는 방법
- 이주(migration): 작업을 한 CPU에서 다른 CPU로 이주시킴으로써 워크로드 균형 달성
- 예. B또는 D 중 하나를 다른 CPU로 이동시킨다
-> 한 번의 작업 이주로 워크로드가 균형을 이루게 됨
- 예. 이 경우 한 번의 이주만으로는 문제가 해결되지 않는다
-> 작업들을 지속적으로 이주시켜야
이주의 필요 여부를 어떻게 결정할까?
-
작업 훔치기(work stealing): 작업 개수가 낮은 (소스)큐가 가끔 다른 (대상) 큐에 훨씬 많은 수의 작업이 있는지를 검사
-> 대상 큐가 소스 큐보다 더 가득 차 있다면 워크로드 균형을 맞추기 위해 소스는 대상에서 하나 이상의 작업을 가져온다 -
큐를 너무 자주 검사하게 되면 -> 높은 오버헤드 -> 확장성 문제
-
큐를 자주 검사하지 않으면 -> 심각한 워크로드 불균형 문제
6. Linux 멀티프로세서 스케쥴러
- Linux 커뮤니티에서는 멀티프로세서 스케쥴로를 위한 단일화된 방식 존재하지 않았음
- O(1) 스케쥴러
- 멀티 큐 사용
- 우선순위 기반 스케쥴러(MLFQ와 유사)
-> 프로세스의 우선순의를 시간에 따라 변경하여 우선순위가 가장 높은 작업 선택
-> 상호작용 가장 우선시함
- Completely Fair Scheduler(CFS)
- 멀티 큐 사용
- 결정론적 비례배분 방식 (보폭 스케쥴링과 유사)
- BF 스케쥴러(BFS)
- 단일 큐 사용
- 비례배분 방식: Earliest Eligible Virtual Deadline First (EEVDF) 방식에 기반
7. 요약
-
단일 큐 방식(SQMS)
-> 정점: 구현 용이, 워크로드 균형 맞추기 용이
-> 단점: 많은 개수의 프로세서레 대한 확장성과 캐시 친화성 bad -
멀티 큐 방식(MQMS):
-> 장점: 확장성 좋음, 캐시 친화성 좋음
-> 단점: 워크로드 불균형의 문제, 구현 복잡
