[05] Multiprocessor Real-Time Scheduling

앞에서는 uniprocessor 환경이었고 이제는 multiprocessor 환경이다. Multiprocessor에는 칩 성능에 따라 크게 3가지 종류가 있다.

identical	uniform heterogeneous	unrelated heterogeneous
Speed : 동일 Capability : 동일	Speed : 다름 Capability : 동일	Speed : 다름 Capability : 다름

 

Multiprocessor 환경에서 스케쥴링이 어려운 이유는 task마다 한개의 processor를 사용하기 때문이다. 대표적으로 두 가지 스케쥴링 방식이 있다.

• Partitioned scheduling
  • Task가 statically 코어에 할당됨
  • 코어 당 하나의 ready queue가 있음
  • Uniprocessor scheduling 방식 사용 가능
• Global scheduling
  • Job이 코어를 자유롭게 migrate
  • 모든 코어에 shared ready queue
  • 새로운 schedulability analysis가 필요함

 

1. Utilization - Dhall effect

Uniprocessor에서의 utilization은 EDF=1, RM=ln2였다. Multiprocessor에서 m개의 processor가 있다고 가정했을 때, global EDF나 global RM utilization은 얼마일까?

 

Global scheduling을 가정한다. m+1개의 task가 있고 m개의 task는 period:1, WCET:$2\epsilon$이다. m+1번 째 task는 period:$1+\epsilon$, WCET:1인 상황이다.

 

Dhall effect란 m개의 task를 먼저 돌리고 가장 긴 task를 나중에 돌리는 경우, utilization이 m이 아닌 1에 가까워지는 것을 의미한다. 또한, 냅따 global EDF나 RM으로 돌리면 m+1번째 task가 deadline miss가 되어 스케쥴링 되지 않는다. 이게 관심을 받는 이유는 그동안 편의를 위해 고려하지 않았다고 한다.

이는 한 task가 한 코어에서 돌기 때문이다. Parallelism을 고려하는 것이 중요하며, 보통 deadline을 고려하여 남아있는 job의 수를 maximize하는 방식으로 스케쥴링하면 optimal이 된다.

 

2. Partitioned Scheduling

m개의 uniprocessor 환경이랑 같다고 볼 수 있다. 따라서 task mapping이 주된 관심이며, 각 코어에서는 PFP나 EDF를 통해 스케쥴링을 수행하게 된다. Task mapping의 주된 관심사는 over-utilized되지 않는 것과 각 코어에서의 schedulability를 보장하는 것이다.

 

M개의 processor에 task를 mapping하는 것은 Bin packing problem으로 reduction 가능하다. 쉽게 생각해보기 위해, unit-speed processors를 가정하고 implicit-deadline sporadic task들을 생성한다. Task의 주기는 임의로 설정해 WCET를 적절하게 설정하고 B개의 processors에 대해 P-EDF가 가능한지 분석해볼 수 있다. 당연히도 NP-hard이다.

 

2001년 RTSS에 upper utilization bound에 대한 theorem이 제안되었다.

• m개의 processor에 대해서, task set의 utilization이 $(m+1)/2$와 유사하면, 해당 task set은 partitioned될 수 없다.

 

가령, m+1 task가 있고 period: 2, WCET: 1+$\epsilon$, utilization: $(1+\epsilon)/2$이면, total utilization은 $(m+1)(1+\epsilon)/2$이 되어 불가능하다고 볼 수 있다. 실제로 두 개의 task만 모여도 utilization이 1을 넘어 안되는 것을 알 수 있다.

 

2.1. Partitioning in Practice

• First-fit : 첫 번째로 만나는 여유공간이 있는 processor에 할당
  • 할당 시간이 빠름, 전체적인 utilization이 낮을 수 있음
• Best-fit : 가장 적합한 processor에 할당
  • Utilization 극대화, 할당 시간이 느림
• Next-fit : 이전에 할당한 processor 다음부터 first-fit 적용
  • First-fit보다 조금 더 utilization이 좋음, first-fit과 같은 문제 있음
• Worst-fit : 여유 공간이 가장 많은 processor에 할당
  • processor 부하가 분산됨, 모든 processor를 확인해야 함

여전히, heuristic이 제일 좋은 성능을 보이고 있다. 이외에도 task-per-core로 partition할 수도 있다.

 

Worst-case에 대한 성능 개선이나, utilization을 m을 보장하기, offline 할당을 피하는 방법 등의 이유로 global scheduling이 제안된다.

 

3. Global scheduling

최근 연구가 진행되고 있는 파트로, 어떤 시간 t에서 shared ready queue에 있는 m개의 highest-priority jobs을 각 코어에 할당한다. 주요 고려사항은 다음과 같다.

• Migrations require coordination
• Cache affinity
• Lock contention
• No general critical instant
• Task는 하나의 processor만 사용가능

 

대표적으로 Global EDF (G-EDF), G-JSFP는 optimal하지 않다. Fixed priority를 가지는 것이 스케쥴링에 방해되기 때문이다. 다음의 예시와 같다.

 

G-EDF 좋은 스케쥴링이지만, deadline 하나만 보고 스케쥴링하면 optimal하지 못하다. 이에 jobs을 더 작은 단위로 나누거나 tie-breaking rule을 만들어 스케쥴링 하는 Job-level Dynamic Priority (JLDP) 기반의 방법이 제안된다. $PD^2$이다.

 

3.1. Pfair/$PD^2$

• Pfair
  • Task의 execution time을 일정 간격으로 나눔 (ex. 1)
  • Task마다 processor 사용 시간을 보장받음
  • Pfair하면, implicit-deadline task는 miss되지 않음
• $PD^2$
  • Pfair하면서, deadline 기반으로 EDF 수행해 task를 할당함
  • (10, 5) $\rightarrow$ (2,1) 5개의 subtask로 나눔

 

다만 문제는 periodic implicit-deadline task에서만 $PD^2$이 optimal 존재하게 된다. 아쉽게도 Arbitrary deadlines + constrained deadline에서는 아직 optimal 스케쥴러가 존재하지 않는다.

 

3.2. Non-Existence of optimal online schedulers for general sporadic tasks

2010년 연구에서, sporadic task with constrained deadlines에 대한 optimal online scheduler는 없음이 증명되었다.

미래의 task가 언제 release될지 모르면, 위처럼 항상 deadline을 miss할 수 있다.

 

4. Multiprocessor 스케쥴링 알고리즘 분류

 

5. 정리

Partitioned Scheduling

• Advantage
  • Uniprocessor 스케쥴링 방법 및 자원 관리법 사용 가능
  • Automative industry에서 사용중
  • Migration 없음
  • Isolation between cores
  • Low scheduling overhead
• Disadvantage
  • Unused execution time 존재
  • WCET 기반으로 동작하는 데, 그것보다 빨리 끝나면 시간이 남음
  • NP-hard allocation

 

Global Scheduling

• Advantage
  • 대부분의 OS에서 사용중
  • 자원의 효율적인 사용 가능
  • Low average response time
• Disadvantage
  • 이론적 프레임워크가 약함
  • Migration cost가 비쌈

 

6. Migration + Clustered scheduling

Migration이란 task가 한 processor에서 다른 processor로 할당되는 것으로, 관련된 모든 데이터가 이동하게 된다. 이는 시간을 매우 크게 잡아먹는다. 한 benchmark에서는 코어 수가 늘어나자 WCET가 6배 커졌다. Shared resource(ex. main memory, memory-bus, last-level cache, I/O)를 사용하기 때문이다.

 

이런 migration을 줄이고자 clustered scheduling이 제안되었다. Partitioned와 Global을 적절히 섞은 방법이다.

Cluster를 작게하면, Bin packing 문제의 어려움이 커지고 / Cluster를 크게하면, migration 문제가 발생한다.

 

또 다른 방법으로는 semi-partitioned scheduling이 있다. 일단 partition하고, task 할당하고, 할당되지 못한 task를 multiprocessor에 알아서 잘 분배(쪼개든 그대로 주든)하는 방법이다.