Multiprocessor scheduling

단일프로세서 스케줄링은 'time domain'에서 언제 수행할 지를 정한다.

multiprocessor 스케줄링은 'space domain'에서 어디에서 수행시킬 것인지를 결정한다.

대부분의 멀티프로세서 스케줄링의 목표는 단일프로세서 스케줄링과 비슷하다.

하지만 멀티프로세서 스케줄링은 아래의 이슈가 있다.

• ready queue를 어떻게 유지할 지
• affinity를 어떻게 정의할 지
• 다중처리기에서 프로그램을 어떻게 할당할 지
• processor heterogeneity를 어떻게 관리할 지
• 프로세서들간의 workload balance를 어떻게 관리할 지

멀티프로세서에서의 이슈를 크게 두 가지로 나누어 HW issue/SW issue로 구분해보자.

 

HW issue : Cache Affinity

multiprocessor scheduler 은 cache affinity를 고려해야 한다.

한 프로세스가 동일한 CPU를 사용하도록 유지해야 한다.

(설명 더 필요)

 

SW issue : Concurrency

 

---

 

 

 

O(1) shcheduler 

우선순위 기반의 스케줄러이다. 주로 RTOS, Linux에서 사용한다.

각각의 run queue는 linked list로 이루어져있다.

우선순위가 높은 것부터 스케줄링한다.

bit map은 priority queue를 조금 더 빨리 탐색하기 위한 방법을 제공한다.(해당 queue에 task가 있는 지 없는 지 확인)

bitmap에서 해당하는priority queue를 확인하고 priority queue를 보면 task들이 linked list형태로 연결되어있다.

이 구조는 constant time에 insert,delete,find가 가능하다.

 

run queue는 active run queue와 expired run queue로 이루어져 있다.

 

각각 active run queue / expired run queue로 가정

스케줄러는 처음에 task를 active run queue에 넣는다.

task가 time slice를 모두 소진하였을 때 active run queue에서는 remove되고 expired run queue로 삽입된다.

그러다가 모든 active run queue가 empty상태가 되고 expired run queue로 모두 옮겨졌을 때,

둘의 포인터를 swap하는 방식으로 active run queue와 expired run queue의 상태를 바꿔준다.

여기서 가장 중요한 것은 O(1) time으로 scheduling을 할 수 있다는 것이다!

 

하지만 우선순위 기반이기에 우선순위가 낮은 task는 수행이 지연되어 'starvation'이 발생할 수 있다.

 

 

Proportional Share Scheduling

task마다 share(weight)를 유지하게 하고 그 weight에 맞게금 CPU의 bandwidth를 할당하는 기법

이 스케줄링 기법이 나온 배경에 대해 설명하자면,

P1과 P2의 priority가 각각 1, 2라고 할 때,우선순위가 두 배가 높다는 것이 스케줄링에 정량적으로 어떤 영향을 주는지 guarantee 되지 않는다. multi media의 등장으로 이러한 guarantee가 굉장히 중요해졌고 이를 해결하기 위해 

각각의 priority 비율에 맞게 CPU allocation을 할당해주는 기법이 등장했다.

P1:P2 = 2:1의 우선순위를 가진다면 p1은 2/3, p2는 1/3만큼의 CPU를 할당해준다.

 

분야에 따라 다른 context를 가진다.

Fair queueing : 네트워크 분야에서 packet scheduling하는 기법 (e.g. WFQ)

Proportional share(fair share) : OS에서의 process scheduling하는 기법 (e.g. Stride Scheduling and Lottery)

둘은 동일한 스케줄링 방식인데 domain만 다르다.

 

[Proportional Fairness Accuracy]

1. Service time error

: (t1,t2)의 시간간격동안 실제로 할당된 시간량

: (t1,t2)의 시간간격동안 할당되어야 하는 시간량

: service time error

 

2. Scheduling Overhead

스케줄링 알고리즘을 계산하는 시간

 

위 두가지 metric을 고려해야 한다!

 

WFQ(Weighted fair queueing) example

WFQ는 논문인데 잘 정리되어 있다.

virtual time : 어떤 time execution 시간할당량의 개념은 그 프로세스의 weight에 반비례하는 시간(상대적으로)으로 여겨질 것이다. 정규화된 시간 , 그 프로세스에 지분에 정규화된 시간

리눅스에서 virtual time을 사용.

아 머라는건지 ㅗ모르겠다 나주에할래

 

 

CFS(Completely Fair Scheduler)

CFS,BFS중 어떤 것을 도입할 지에 대한 논란이 많았다.

virtual runtime이라는 용어를 도입하여 WFQ와 비슷하다.

virtual runtime(전역변수)의 최소값을 구하는 알고리즘이다.(red-black tree로 구현됨)

O(logn)의 비용이 든다.

O(1) 스케줄러와 비슷하게 priority기반으로 동작한다.

run queue가 CPU마다 존재한다.

---

Linux Multiprocessor Scheduler