[전공생이 설명하는 OS] 멀티 코어 프로세스 스케줄링
이전 글 참고
단일 프로세스 스케줄링 & 시뮬레이션 결과 분석
1. Scheduling 분류 3가지 (1) Long-term schedule - job scheduler 라고도 한다. - 제출된 프로그램 실행 요청 중에서 어떤 것을 프로세스로 실행시킬 지 결정하는 스케줄링이다. - 사용자가 OS에 프로그램 실행.
letsmakemyselfprogrammer.tistory.com
1. 고려해볼 만한 요소들
단일 코어에서는 언제, 어떤 프로세스를 실행시킬지만 결정하면 되는 문제였다. 하지만 멀티코어 환경에서는 고려해야 할 요소들이 꽤나 복잡하다.
- ready queue 를 어떻게 운영할 것인가? 한개의 global 큐만 사용할 것인가? 코어 당 한개씩 큐를 사용할 것인가?
- Cache affinity 를 어떻게 활용할 것인가?
(cache affinity 란 캐시 친화력이라고 번역할 수 있다. cpu 내부에는 메모리에 덜 접근하기 위해 캐시메모리가 존재) - 프로세스를 어떤 코어에 매핑해야하는가?
- Heterogenous 한 멀티코어를 어떻게 다루어야하는가?
(모든 코어가 동등하지 않고 big core, little core 가 쌍을 이루는 cpu 설계 방식이 존재함.) - workload 를 코어에 어떻게 load balancing 할 것인가?
- race condition 을 어떻게 해결할 것인가?
2. Scheduling Algorithms
1) SQMS
- Single Queue Multiprocessor Scheduling
- 가장 단순한 형태, global queue가 단 하나 존재. 각 코어들은 queue 에서 pop() 한 프로세스를 실행시키면 된다.
- cache affinity를 고려하지 않는 방식.
- 동기화 방식에 대한 고려가 부족하다 -> 확장에 불리하다.
2) MQMS
- Multi Queue Multiprocessor Scheduling
- 하나의 코어는 한개의 queue만 사용하도록 한다. -> cache affinity 해결
- 코어들이 어느정도 분리된 queue를 사용하기 때문에 race condition을 어느 정도 해결
- 큐마다 별도의 알고리즘을 적용할 수 있다.
- load imbalance 문제가 있다.
=> fairness 가 중요한 시스템에서는 바람직하지 않다. 또 cpu utilization 측면에서도 좋지 않다.
=> migration을 도입(idle 한 cpu 로 job을 옮기는 것, cache affinity와 trade-off 관계)
- work stealing(=pull migration) : queue 의 길이를 검사해서 상대적으로 적은 쪽에게 프로세스를 넘겨주기. (얼마나 자주 검사하는지가 중요함. heuristic하게 threshold를 찾는 것이 중요)
3. MQMS 알고리즘 예
(1) O(1) Scheduling
- linux 2.6 버전에서 도입 (2000년대 초반, 멀티코어 등장 시기)
- 비트맵 구조를 이용해서 각 우선순위 큐에 내용물이 있는지 상수시간에 확인한다.
- 우선순위 기반 140개의 큐를 사용한다. (두 그룹의 run queues가 있는데, active와 expired 각각 140개씩)
- time slice를 다 소진하면 expired queue로 이동하는 방식으로 낮은 우선순위의 active queue starvation을 방지한다. active queue가 empty가 되면 두 그룹의 큐를 swap 한다. 이 주기를 한 epoch라고 한다.
- 우선순위가 가장 높은 프로세스를 O(1)에 찾을 수 있어서 이름이 O(1) scheduling 이다.
- 한 코어마다 active와 expired를 따로 갖는다. 즉 MQMS 방식이다.
- real time task 들은 active 큐에만 존재하도록 하는 보상도 있다.
(2) Proportional Share Scheduling
- CFS 라는 이름으로 2000년대 중후반 linux에 적용되었음.
- 2000년대 중반, 모바일 기기의 성능이 향상되면서 멀티미디어에 대한 요구가 중요해졌다. 즉 일정시간동안의 cpu 사용 (cpu bandwidth)을 보장해야 질 좋은 컨텐츠를 소비할 수 있다. 이전의 priority-based-scheduling에서는 우선순위가 5배 높다고 해서 cpu 사용시간이 5배 더 보장되는 것이 아니었다.
- virtual machine monitor 에 적용된다. (vCPU 등의 클라우드 서비스 등) PCB에 weight를 주어서 해당 weight 만큼 하드웨어 자원을 사용하도록 하는 기술이다. 또 네트워크 분야에서 packet schedule 에도 사용되기도 한다.
- optimization criteria : \(E_i(t_1,t_2)=W_i(t_1,t_2)-(t_2-t_1)\frac{\phi_i}{\sum_j\phi_j}\) (오차 = 실제-이론)
- 위의 오차를 최소화하는 방향으로 발전
(a) WFQ (Weighted Fair Queueing) 알고리즘
- 1996년 네트워크 논문에서 소개된 패킷 스케줄 알고리즘 -> 현대 os의 CFS에 영향을 주었음.
- virtual finish time(정규화된 누적수행시간)이 가장 작은 프로세스에게 자원을 할당
- virtual time : \(\frac{프로세스 \ A의 \ 누적수행시간} {프로세스 \ A의 \ weight}\) => 자신의 weight로 정규화된 누적수행시간
- virtual finish time : \(\frac{프로세스 \ A의 \ 누적수행시간 + 1} {프로세스 \ A의 \ weight}\) => 단위시간만큼 한차례 더 자원을 할당받는다고 했을 때의 정규화된 총 누적수행시간
- 오차의 하한이 -1 을 넘지 않는다는 것이 보장된 방법
(b) CFS (Completely Fair Scheduler) 알고리즘
- linux 2.6.23 에서부터 적용됨
- WFQ 와 비슷하게 virtual runtime 이 가장 작은 프로세스를 고르는 문제
- 최소값을 찾을 때 red-black-tree 를 이용함. (heap을 사용하면 내부적으로 정렬이 되어있지 않음)
- 각 코어마다 위 그림과 같은 run queue 가 하나씩 존재한다.