[전공생이 설명하는 OS] 멀티 코어 프로세스 스케줄링

 

이전 글 참고

단일 프로세스 스케줄링 & 시뮬레이션 결과 분석

 

---

1. 고려해볼 만한 요소들

  단일 코어에서는 언제, 어떤 프로세스를 실행시킬지만 결정하면 되는 문제였다. 하지만 멀티코어 환경에서는 고려해야 할 요소들이 꽤나 복잡하다.   

AMD Bulldozer Architecture 예시

• 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 Scheduling Data Structures for Each Processor

  - 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) 알고리즘

CFS

kernel 구조체 코드 예시

    - linux 2.6.23 에서부터 적용됨

    - WFQ 와 비슷하게 virtual runtime 이 가장 작은 프로세스를 고르는 문제

    - 최소값을 찾을 때 red-black-tree 를 이용함. (heap을 사용하면 내부적으로 정렬이 되어있지 않음)

    - 각 코어마다 위 그림과 같은 run queue 가 하나씩 존재한다.