[Linux Kernel] Real-Time CPU Scheduling

Real-Time Scheduling

정해진 시간 안에 주어진 기능이 제대로 동작하게 하는 스케쥴링 방식.

 

Real-Time이 Super-Fast를 의미하는 것은 아니다.

 

Real-Time Scheduling: Types

Hard Real-Time

실행 시간이 정해진 Deadline을 넘어서면 치명적인 문제가 발생한다.

예를 들어 자동차 자율 주행 시스템이나, 원자로 감시 시스템 처럼 감지와 대응이 늦어질 경우 큰 사고로 이어질 수 있는 분야에 적용되는 기법이다.

 

Soft Real-Time

실행 시간이 정해진 Deadline을 넘어서면 시스템의 품질이 하락하는 경우. (치명적인 사고를 발생시키지는 않음)

예를 들어, 축구 실시간 중계 방송에서 실행 시간이 Deadline을 넘어서면 buffering이나 화면이 일그러지는 문제가 발생하는 분야에 적용되는 기법이다.

 

Firm Real-Time

Deadline을 넘어서 처리된 data는 더이상 가치가 없는 시스템.

예를 들어, 공장의 불량품 감시 시스템은 만약 정해진 시간 내에 검사를 마치지 못했을 경우 다음 물품 검사를 포기하는 것이 아니라, 

현재 데이터를 포기하고 다음 물품에 대한 불량을 검사해야 한다.

 

Hard Real-Time Scheduling: Types

Static Schedule

컴파일 타임에 모든 스케쥴링이 끝나는 경우

 

Dynamic Schedule

런타임에 스케쥴링이 결정되는 경우

 

Schedulability Test

주어진 작업들이 스케쥴링 조건을 만족시키는지 검사하는 기법

 

Scedulability Test는 가장 최악의 경우(Critical Instant)를 상정하고 실시한다.

=> 우선순위가 더 높거나 같은 작업들을 최대로 배치하고, 가장 오래 걸리는 작업들만 있다고 설정

 

Schedulability Test는 비관적으로 테스트하기 때문에,

테스트를 통과했다는 것은 반드시 스케쥴링 조건을 만족시킨다는 것을 의미하지만

테스트를 통과하지 못하는 경우에도 스케쥴링 조건을 만족시키는 경우가 있을 수 있다.

 

각 스케쥴링 방법마다 테스트 방법 역시 다른데, 아래에서 계속 알아보겠다.

 

Rate Monotinic (RM)

Dynamic preemptive scheduling 기법이다.

 

세로줄 사이의 간격이 period, 세로줄이 deadline

 

짧은 실행 시간을 가진 task에게 높은 우선순위를 부여하고 고정시킨다.

이를 위해, 시스템은 모든 task에 대한 실행 시간을 전부 알고 있어야 한다.

 

Scedulability Test

=> Σ( Cpu Utilizations )  <= n* (2^(1/n)-1)

=> n은 task 갯수, Cpu Utilization[i]= critical instances[i]/periods[i] (해당 period에서 얼마만큼 task가 실행되었는지; 최대값)

 

Ealiest Deadline First (EDF)

Dynamic preemptive scheduling 기법이다.

 

deadline이 임박한 Task에게 더 높은 우선순위를 부여한다.

매 시간마다 스케쥴러는 Task들의 deadline을 비교하여 우선순위를 조정해 주어야 한다.

 

Scedulability Test

=> Σ( Cpu Utilizations )  <= 1

=> Cpu Utilization[i]= critical instances[i]/periods[i] (해당 period에서 얼마만큼 task가 실행되었는지; 최대값)

 

RM과 비교하면 sum of utilization의 thresold가 EDF가 더 높은 것을 알 수 있다.

따라서 RM보다 더 task들을 꽉 채워서 task를 실행시킬 수 있다.

 

그러나 계속해서 task의 deadline을 비교해 우선순위를 변경시켜줘야 하기 때문에

RM보다 utlizations는 높지만 Overhead는 커진다.

 

Ealiest Deadline First (EDF): Linux 

EDF와 유사한 스케쥴링 방식으로 Linux에는 SCHED_DEADLINE이 있다.

 

단 EDF와는 다르게, utilization 임계값을 0.95로 설정한다.

 

1로 설정하게 되면, SCHED_DEADLINE 특성 상 일반 프로세스들은 전혀 실행하지 못하게 되어

SCHED_DEADLINE으로 설정된 프로세스가 스스로 block상태가 되지 않으면 다른 프로세스들이 자원 점유 기회를 전혀 얻지 못하게 되기 때문이다.

 

이 스케쥴러를 사용하는 프로세스들은 일반적인 프로세스보다 높은 우선순위를 갖는다.

Fixed Priority Schedulers: Linux

이 스케쥴러를 사용하는 프로세스들은 일반적인 프로세스보다 높은 우선순위를 갖는다.

 

RM과 우선순위를 고정한다는 점에서는 비슷하다.

그러나 여기에서는 프로그램의 실행 시간(period)를 알 수 없기 때문에 사용자가 우선순위를 지정해줘야 한다.

 

SCHED_FIFO

큐에 먼저 들어온 작업들부터 처리한다.

다만 SCHED_FIFO에서도 우선순위가 존재하는데, 더 높은 우선순위의 SCHED_FIFO가 추가될 경우 점유 권한을 빼앗긴다.

 

SCHED_RR

가장 높은 우선순위 큐에 존재하는 프로세스들을 Round Robin 기법으로 실행한다.

SCHED_RR에도 우선순위가 존재하며, 더 높은 우선순위의 SCHED_RR이 추가될 경우 해당 우선순위의 큐를 실행하게 된다.