멀티프로세서 스케쥴링

멀티 프로세서의 발전 - 처리기가 늘어남에 따라 어떤 프로세스에 어떤 처리기를 할당할지 복잡해짐

주요 이슈

 

cache affinity (친화력)

- 특정 프로세서에서 실행된 프로세스는 가능하다면 계속 동일한 프로세서에 할당함

Concurrency (병행성)

여러 프로세서에 프로세스를 할당하기 위해 레디큐(싱글 큐라고 가정)에 동시 접근하여 프로세스를 불러올 때 생기는 문제를 해결

 

Shared data를 이용할 때 생기는 문제 -> race condition

공유자원에 대해서 한번에 한번씩 접근하게 하는 기법 -> mutual exclusion (ex: 동기화, 데드락)

 

 

SQMS(single-queue multiprocessor scheduling)

각 cpu가 단순히 전역적인 싱글큐에서 프로세스를 선택하고 실행

장점 : 구현이 단순함

단점 : concurrency 때문에 동기화 기법을 적용해야 하고 그로 인해 확장성이 떨어짐, 캐시 친화력을 복잡한 방식으로 구현

 

 

MQMS(multi-queue multiprocessor scheduling)

프로세서마다 별도의 큐가 존재하고 프로세스들은 계속 같은 큐에서 스케쥴링됨

캐시 친화력을 유지

큐가 분리되었기 때문에 shared data에 대한 race condition을 해결

큐마다 별도의 rule을 만들 수 있음

 

 

단점 :  특정 CPU에서 큐에 존재하는 모든 프로세스가 끝나면 대기시간이 생김 -> load imbalance

한가한 프로세서에 다른 프로세서의 프로세스를 할당하는 것 -> migration

하지만 cache 친화력의 이점을 해칠 수 있다.

 

 

migration

큐의 길이의 정도에 따라서 프로세스를 다른 cpu에 할당함

너무 빈번하게 하면 overhead 발생

 

 

---

 

초기 리눅스의 멀티 프로세서 스케쥴러

 

o(1) scheduler - 리눅스 2.5

 

멀티 큐에서 큐들은 각각 우선순위와 task를 가지고 있다

task가 우선순위를 받으면 해당하는 순위의 queue에 들어감

특정 큐에 더 빠르게 접근하기 위해 bitmap이 존재 

 

active queue와 expired queue가 동시에 존재하는데,

time slice를 모두 소진한 task들은 expired queue에 저장되고 active queue가 비었을 때 active queue가 expired queue가 되고 expired queue가 active queue가 되서 다시 실행 (서로 포인터를 바꿈)

-> 우선순위를 지킬 수 있다

 

할당할 프로세스를 탐색할 때 우선순위 큐의 크기만큼만 탐색하면 되므로 O(1) scheculer

-> 프로세스의 수와 상관없음

 

proportional Share schedling - 리눅스 2.6

멀티 미디어에 대한 요구사항이 올라감 -> 하나의 프로세스에서 충분한 CPU 할당 시간을 요구

프로세스마다 다른 weight에 적절한 CPU 수행 시간을 각각 다르게 할당

 

WFQ 알고리즘

위의 스케쥴링에서 weight를 계산하는 알고리즘

누적 수행시간을 정규화 -> virtual time

A:B:C:D = 4:3:2:1 의 weight를 가지고 있을 때 정규화된 virtual time은 다음과 같다.

같은 1초라도 가중치가 다르기 때문에 자신의 weight로 실행한 시간을  정규화 하여 낮은 실행 시간을 가지는 프로세스의 우선순위를 높게 하자

 

 

누적합

 

completely fair scheduler - 현재

 

레드 블랙 트리로 프로세스 순위를 저장하여 계속 균형을 맞춰줌