Heterogeneous Multiprocessing(HMP)
clock 속도나, 전력 소모 측면에서 코어들이 기능적으로 다르게 설계된 시스템을 의미한다.
앞서 배운 asymmetric multiprocessing과 다르다. 각각의 코어들이 기능적으로 다른 것이지. 모든 코어에서 커널을 처리할 수 있다.
이 HMP의 목적은 일의 특성에 따라 이에 적합한 코어를 할당하여 전력소모를 줄이는 목적으로 개발되었다.
대표적으로 ARM에서 사용하는 big.LITTLE solution이 있다. 이는 big core와 little(energy efficient) core를 함께 구성한다.
- little core: 에너지 소비가 적고, 낮은 성능을 요구하는 장기적인 일에 사용된다.
- big core: 에너지 소비가 많지만, 좋은 성능을 요구하고 단기적인 일에 사용된다.
Real-Time Scheduling
실시간 시스템(Real-Time process)이란 실시간으로 발생하는 event를 기다리고 이를 주어진 시간안에 처리한다.
(e.g. 주기적인 timer, 임의적인 event)
event가 발생하면 이를 처리하는 시간이 가능한 빨라야한다.(event driven의 특성)
이벤트 지연시간(event latency)은 Interrupt latency + dispatch latency의 총합이며 Interrupt latency는 Interrupt가 발생한 후, ISR이 처리되는 시간을 포함할 수 있다. 그리고 Scheduler가 원하는 real time process를 바로 시작할 수 없을 수 있다.(다양한 정책에 따라) 이 프로세스를 시작할 때까지의 지연시간을 dispatch latency라 부른다.
그림 (a)를 보면 Round-Robin scheduling에서 real-time process가 들어왔을 때인데, 실제 CPU에 할당받기 위해 queue에 삽입되어 대기하는 상태이다. 이는 많은 시간이 걸릴 수 있으므로 적절하지 않다. dispatch latency가 길다는 것이다.
(b)와 같이 우선순위 기반의 scheduling을 사용해도, 비선점 모드라면 현재 처리 중인 프로세스가 끝나야 처리될 수 있기 때문에 waiting 시간의 dispatch latency가 필요하다.
그럼 여기서 비선점 모드나, Round-Robin과 같이 dispatch latency가 긴 scheduling 방식은 실시간 process를 처리하기 적합하지 않다.
(c)와 (d) 같이 실시간 프로세스를 바로 처리할 수 있거나, 선점 가능한 지점까지 약간의 지연을 허용하는 것은 적합하다.
실시간 시스템에서 선점 커널(preemptive kernel)을 제공하는 것이 latency를 줄일 수 있는 가장 효율적인 방법이다.
지금까지 본 것으로 실시간 event 처리에 있어서 latency를 최소화 하는 것이 중요하고, 대부분 실시간 OS들은 선점 scheduling 방법을 사용하며 발전하였다.
하지만 지연시간을 최소화하는 것이 real time scheduling의 핵심적인 평가 기준은 아니다.
Real-time 시스템에선 프로세스가 제때 종료되거나 처리를 시작을 보장해주는 것이 더 중요하다.
프로세스 시간적 제약의 보장의 정도, 또는 피해의 정도에 따라 두 가지 실시간 시스템으로 분류할 수 있다.
- Soft real-time system(연성 실시간 시스템): 별로 중요하지 않은 프로세스보다 더 큰 우선순위를 얻는다는 것을 보장한다.(언제 처리가 시작 or 종료되는지는 보장하지 않는다.)
이러한 기법은 작업의 deadline을 지키지 못했을 때, 치명적인 피해를 주지 않는 환경에서 사용된다.- Hard real-time system(경성 실시간 시스템): 반드시 마감 시간까지 process가 시작 or 처리를 보장해야한다.
이는 작업의 시작, 완료의 요구사항을 지키지 못했을 때, 시스템에 치명적 피해를 발생한다면 이러한 방법을 시용해야한다.
이러한 환경에선 요구를 충족시키지 못하는 것이 시스템 실패로 이어질 수 있기 때문에, scheduling 능력이 굉장히 중요하다.
Real-Time Task
지금까지 실시간 시스템과 실시간 스케줄링의 성질을 알아보았다면, 실시간 일(Real-time task)에 대해 알아보자.
- Periodic task: 고정된 interval을 가지고 반복적으로 발생하는 task이다.
- Aperiodic task: 고정된 시간은 없지만 간혈적으로 발생하는 task이다.
- Starting deadline: task 처리가 시작되어야만 하는 deadline
- Completion deadline: task 처리가 종료되어야만 하는 deadline
둘 중 하나만 가진다.
Priority-Based Scheduling
Real-time OS에서 가장 중요한 기능은 바로 응답하는 것이다. 그래서 선점형 scheduling을 지원한다.
이 방식은 프로세스마다 우선순위를 부여하고, current process보다 더 우선순위가 높은 프로세스가 들어오면, 바로 processor를 빼앗고 할당한다.
(우선순위 별로 ready queue를 만들어놓았다. 여기서 우선순위가 낮은 프로세스가 수행되다 높은 프로세스가 큐에 들어온다면, 바로 선점 당한다.)
우선 실행만 보장해주기 때문에, soft real-time system이다.
hard real-time은 마감시간까지 보장해줘야 한다.
게다가 낮은 우선순위의 프로세스에 starvation 문제도 발생할 수 있다.
Earliest-Deadline-First(EDF)
EDF schedulign 알고리즘은 마감시간이 가장 이른 task를 먼저 수행하는 알고리즘이다.
프로세스들가 실행 가능할 때마다 마감시간이 주어져야한다. 그럼 scheduler가 deadline에 따라 우선순위를 부여하는 방식으로 동작한다.
당연히 마감시간이 일러야 우선순위가 높다.
새로운 프로세스가 발생하면, deadline을 반영하여 우선순위가 조정된다.
이는 deadline ratio를 최대화한다.
e.g. EDF는 선점, 비선점 모두 가능하다.
위는 비선점이고, 자발적 idle을 이용하여 처리했다.
CPU utilization이 높아지는 것을 볼 수 있다.
Rate Monotonic Scheduling(RMS)
유명한 실시간 스케줄링 중 하나이다. 주기적인 일을 선점적으로 처리한다.
우선순위를 실행주기로 결정한다. 실행빈도(rate)가 길면 높은 우선순위를 가진다.
다르게 말하면 실행주기(period)가 짧아야 높은 우선순위를 가진다.
RMS는 주기가 변하지 않는 이상 static하게 결정할 수 있기 때문에 주기성이 꼭 필요하다.
이러한 이유로 실행빈도에 비례하는 우선순위를 확인할 수 있다.
일반적으로 scheduling의 CPU utilization의 upper bound는 다음과 같다.
하지만 RMS scheduling을 사용하기 위해선 다음과 같은 upper bound를 만족해야한다.
EDF vs RMS
RMS가 더 많이 사용된다.
RMS의 상한을 만족하는 것은 현실에서 쉽게 충족 가능하다.(위에서 본 예시는 보수적인 상한이다. 실제론 더 널널하게 잡는다.)
EDF는 프로세스의 우선순위를 변경하기 위해서 모든 주기의 데드라인을 변경해야 하지만, RMS는 주기만 바꿔주면 된다. EDF는 CPU utilization이 좋아 많은 real-time process를 처리할 수 있다.
