운영체제 다중처리 실시간 CPU 스케줄링 (OS scheduling 2)

다중처리 스케줄링

 다중처리가 가능한 CPU의 경우 단일처리와 다르게 스케줄링 알고리즘의 보완이 필요합니다. 프로세스 큐의 부하 공유가 필요합니다. 다중 처리를 위해 대칭 다중처리가 일반적이고 그중에서 공통 준비 큐, 각각의 준비 큐를 할 수 있는 두 가지 방법이 존재합니다.

공통 준비 큐

코어당 실행 큐

 각 전략별 중점은 공통 준비 큐의 경우 경쟁 조건을 방지해야 합니다. 프로세서간 동일한 스레드를 스케줄 해서는 안됩니다. 코어당 실행 큐의 경우 부하를 적절히 나눠야 합니다. 대부분의 운영체제, cpu들은 대칭 다중 처리(SMP, symmetric multiprocessing)를 지원합니다.

 

로드 밸런싱 Load balancing

 다중 처리기에서는 부하를 처리기마다 균등하게 배분하는 것이 문제입니다. 자칫하면 어떤 처리기는 놀게 되고 또 다른 처리기의 준비 큐는 계속 쌓이게 됩니다. 공통 준비 큐라면 이 문제를 고민할 필요가 없지만 코어당 실행 큐의 경우 이 문제를 고민해야 합니다. 부하 균등화를 위해 마이그레이션(이주 기법) 방식을 사용합니다. push 마이그레이션과 pull 마이그레이션 방식이 있습니다. pull 마이그레이션의 경우 덜 바쁜 코아가 스레드를 가져오는 것이고 push의 경우 바쁜 코어가 스레드를 다른 곳으로 밀어내는 방식입니다. 

 

이기종 다중 처리 HMP

 다중의 다른 모델의 코어가 각기 다른 목적을 위해 존재하는 방식입니다. 고성능 코어와 효율 코어로 차이를 둔 시스템을 이기종 다중 처리라고 합니다. 현재 모바일 시스템은 당연하게도 널리 사용중입니다. 현재 고성능 데스크톱 CPU에도 전력 사용량 감소 등 향상된 성능을 위해 현재 개발 중이거나 사용 중입니다. 느리거나 가벼운 처리 또는 백그라운드 프로세스의 경우 효율 코어를 사용하고 고성능, 포그라운드 위주의 처리는 고성능 코어가 처리하게 되는 방식을 주로 사용합니다.

 

 

---

실시간 CPU 스케줄링

 다중처리에서 지연시간을 최소화해야합니다. 어떤 이벤트 α가 발생 시점부터 처리를 시작하기까지를 이벤트 지연시간이라고 합니다. 

 이런 지연시간은 인터럽트 지연시간, 디스패치 지연시간이 두가지가 대부분을 차지합니다. 인터럽트 지연시간은 인터럽트 처리 루틴이 시작하기까지의 시간입니다. 이 시간에 주요 요인중 하나가 커널 자료 구조 갱신인데 이동안 인터럽트가 불능이 됩니다. 이 시간을 얼마나 줄이느냐에 따라 인터럽트 지연시간이 줄어들게 됩니다. 

 디스패치 지연시간은 문맥 교환하는 시간, 프로세스를 차단하고 다른 프로세스를 시작하는 시간을 말합니다. 이 경우 선점형이 매우 효과적입니다.

 우선 순위 기반 알고리즘은 중요성에 따라 그 우선순위를 부여한 뒤 우선순위에 따라서 처리를 합니다. 선점형일 경우 더 높은 프로세스에게 선점할 수 있습니다. 단지 이 방식으로는 실시간 스케줄링 하기에는 부족합니다.

 

이벤트 지연시간 : 이벤트 발생 시점부터 처리를 시작하기까지의 시간

인터럽트 지연시간 : 인터럽트를 발생시키고 인터럽트 처리 루틴이 시작하기까지의 시간

 

비율 단조 스케줄링 (Rate-Monotonic Scheduling)

 이 알고리즘은 선점형, 선점이 가능한 우선순위를 사용하여 스케줄링합니다. 낮은 순위가 실행 중이고 높은 순위가 실행 준비가 될 때 선점합니다. 짧은 주기 태스크는 높은 우선순위를 부여합니다.

 Rate-Monotonic의 예로 프로세스 $p_{1}, p_{2}$가 있다고 할 때 $p_{1}$의 주기는 50 ,$p_{2}$의 주기는 100이다. $p_{1}$의 수행 시간은 15, $p_{2}$의 수행 시간은 40일 때 주기가 짧은 $p_{1}$이 우선순위를 받게 됩니다. $p_{1}$의 경우 마감시간이 50마다, $p_{2}$의 경우 100마다 마감시간이 됩니다.

수행

 위와 같은 처리 스케줄이 나옵니다. 그러나 이 기법에는 제약이 존재합니다. 이용률에는 한계가 있어 최악의 경우 프로세스 수 N에 대해$N(2 ^{{1} / {N}} -1)$까지 떨어집니다.

 

EDF 스케줄링 (Earlist-Deadline First Scheduling)

 이 기법은 마감시간에 따라 우선순위를 동적으로 변경합니다. 마감시간이 빠를수록 높은 우선순위를 가집니다. 프로세스가 실행 가능할 때 시스템에게 마감시간을 알리고 우선순위를 재조정합니다. $p_{2}$의 프로세서 주기가 짧아진다고 가정합니다. Rate Monotonic의 경우 $p_{2}$의 프로세스를 처리하지 못합니다. EDF를 사용한다면 우선순위가 높은 $p_{1}$의 주기가 오더라도 문맥교환을 하지 않고 $p_{2}$의 처리를 완료하고 $p_{1}$를 처리하게 됩니다.

 이 알고리즘을 사용하면 CPU의 이용률도 오르고 프로세스가 주기적일 필요도 없습니다. 다만 프로세스가 실행 가능할 때 자신의 마감시간을 스케줄러에게 알려야 합니다.