실시간 CPU 스케줄링

실시간 시스템은 크게 두가지로 구분될 수 있다. 연성(soft) 실시간 시스템과 경성(hard)실시간 시스템이다.

연성 실시간 시스템: 중요한 프로세스가 실행되는 시점에 관해 아무런 보장도 하지 않는다. 단순히 중요 프로세스가 다른 프로세스에 비해 높은 우선순위를 가지는 것만을 보장한다.

경성 실시간 시스템: 태스크는 반드시 마감시간까지 서비스를 받아야하며 마감시간이 지난 이후에 서비스를 받는 것은 서비스를 전혀 받지 않는것과 동일한 효과를 갖는다.

 

예를들어 자율주행 자동차에 들어가는 시스템을 생각해보자. 자율주행 자동차는 도로를 주행하던 중 갑자기 끼어든 장애물을 만났다. 장애물 회피 시스템은 즉시 ReadyQueue에 들어갈 것이다. 20ms후 장애물에 충돌될것으로 예상될 때, 25ms후에 장애물 회피 시스템이 작동하면 작동하지 않은 것과 아무런 차이가 없다. 이와같이 마감시간이 중요한 시스템을 경성 실시간 시스템이라고 하며 이러한 시스템에서는 다른 시스템에서와는 다른 스케줄링 알고리즘이 필요하다.

아래에서 소개해주는 스케줄링 기법은 이전에 소개한 스케줄링 기법과 달리 마감시간을 고려하는 실시간 스케줄링 기법이다.

 

<이전 포스팅>

2022.12.28 - CPU 스케줄링(CPU Scheduling)

지연시간

event가 발생하면 시스템은 가능한 빨리 그에 응답을 하고 그에 맞는 동작을 수행하여야 한다. 사건 지연 시간은 사건이 발생해서 그에 맞는 서비스가 수행될 때 까지의 시간을 말한다.

다음의 두 가지 유형의 지연시간이 실시간 시스템의 성능을 좌우한다.

 

1. 인터럽트 지연시간

2. 디스패치 지연시간

 

1. 인터럽트 지연시간

cpu에 인터럽트가 발생한 시점부터 해당 인터럽트 처리 루틴이 시작하기 까지의 시간을 말한다. 

인터럽트가 발생하면 우선 수행중인 명령어를 완수하고 발생한 인터럽트의 종류를 결정한다.

해당 인터럽트 서비스 루틴(ISR)을 사용하여 인터럽트를 처리하기 전에 현재 수행 중인 프로세스의 상태를 저장해 놓아야한다.

이러한 작업들을 모두 수행하는데 걸리는 시간을 인터럽트 지연시간이라 한다.

 

2. 디스패치 지연시간

디스패치 지연시간은 스케줄링 디스패처가 하나의 프로세스를 블록시키고 다른 프로세스를 시작하게 하는데 걸리는 시간을 말한다. 

 

우선순위 기반 스케줄링(Priority-Based Scheduling)

앞선 포스팅에서의 선점형 우선순위 스케줄링을 사용하면 단지 연성 실시간 기능을 제공하는 것에 불과하다. 경성 실시간 시스템에서는 태스크가 마감시간 내에 확실히 수행되는 것을 보장해야만 하며 그렇기 때문에 부과적인 스케줄링 기법이 필요하다.

 

Rate-Monotonic 스케줄링

rate-monotonic scheduling는 주기 태스크를 스케줄링 하는 우선순위기반의 선점형 스케줄링 알고리즘이다. 주기가 짧은 태스크일수록 낮은 우선순위를 주기가 긴 태스크일수록 높은 우선순위를 가진다.

 

Rate-Monotonic 스케줄링을 이해하기위해 예를 함께 들어보겠다.

두개의 프로세스 P1, P2가 있다고 하자.

P₁의 주기는 50 수행시간은 20으로 하고 각각 p₁, t₁이라 하자.

P₂의 주기는 100 수행시간은 35라 하고 각각 p₂, t₂라 하자.

 

여기서 수행시간은 cpu burst시간과 같다고 가정한다. dispatch latency와 같은 것은 고려하지 않는다.

 

p₁<p₂이므로 프로세스 P₁의 우선순위가 더 높다.

따라서 처음에 P₁이 먼저 20초 수행되고 P₂가 30초 수행된다.

P₂의 수행시간이 5초 남아있지만 P₁의 마감시간이끝나고 주기가 돌아왔기때문에 우선순위가 더 높은 P₁이 P₂를 선점한다. 이후 P₂의 남은 5초가 수행되고 이후 P₁,P₂의 마감시간이끝나고 주기가 돌아올때까지 25초간 CPU는 유휴시간에 들어간다.

 

위 예시를 따라가 보면 Rate-Monotonic 알고리즘이 작동하는 원리를 이해할 수 있을것이다.

 

두번째 예시를들어보겠다.

P₁의 주기는 50 수행시간은 25으로 하고 각각 p₁, t₁이라 하자.

P₂의 주기는 80 수행시간은 35라 하고 각각 p₂, t₂라 하자.

p₁<p₂이므로 프로세스 P₁의 우선순위가 더 높다.

 

예시 2

위 조건을 기반으로 스케줄링을 진행하면 위와 같은 결과가 나타난다.

마지막 80초경에서 마감시간이 80초인 프로세스 P2가 85초에 수행이 종료되는것을 확인 할 수 있다.

이는 deadline을 지키지 못한 경우이다.

 

서비스를 시작하기 전 미리 deadline을 지킬 수 있을지를 예측할 수 있을까?

우리는 CPU 이용률을 주기에대한 수행시간 t/p로 계산할 수있다.

예시1 에서 P1의 CPU이용률은 20/50 = 0.4 P2의 CPU이용률은 35/100=0/35 총 0.75이다

예시2 에서 P1의 CPU이용률은 25/50 = 0.5 P2의 CPU이용률은 35/80=0.44 총 0.94이다.

 

Rate-Monotonic 스케줄링 기법을 사용했을 때 cpu이용률에는 한계가 있기 때문에 cpu자원을 최대화해서 사용하는것은 불가능하다. N개의 프로세스를 스케줄 하는데 있어 최악의 경우 cpu이용률은 2(2^(1/N)-1)이다.

(어떻게 해서 저런 공식이 나왔는지는 아직 필자도 이해하지 못해서 좀 더 찾아보고 업데이트할 예정이다)

 

위 공식에 따르면 2개의 프로세스를 스케줄하는데 있어 최악의 경우 CPU이용률은 약 0.8284 정도이다. 

따라서 예시 2의 경우 최악의 경우 deadline을 지키지 못할것이다.

다만 위의 공식에서는 최악의 경우에 cpu이용률이므로 지킬지를 사전에 확실하게 알기는 조금 어려운 점이 있다.

 

Earliest-Deadline-First(EDF) Scheduling

EDF 스케줄링의 경우 앞선 Rate-monotonic 스케줄링과 유사하지만 우선순위가 고정되어있는 rate-monotonic과는 다르게 EDF에서는 마감시간을 기준으로 동적으로 우선순위를 부여한다.

 

따라서 EDF정책에서는 프로세스가 실행가능하게 되면 자신의 마감시간을 시스템에게 알려야 한다.

 

앞선 예시 2에서와 같은 경우를 생각해보자.

 

P₁의 주기는 50 수행시간은 25으로 하고 각각 p₁, t₁이라 하자.

P₂의 주기는 80 수행시간은 35라 하고 각각 p₂, t₂라 하자.

EDF Scheduling 결과

0초에서 p₁<p₂이므로 P₁의 우선순위가 P₂보다 높다. 따라서 P₁이 먼저 실행된다.

50초에서 p₂<p₁이므로 P₂의 우선순위가 P₁보다 높다. 따라서 P₂의 수행이 지속된다.

80초에서 p₁<p₂이므로 P₁의 우선순위가 P₂보다 높다. 따라서 P₁의 수행이 지속도니다.

100초에서 p₁<p₂이므로 P₁의 우선순위가 P₂보다 높다. 따라서 P₁이 선점하여 수행을 이어나간다.

 

이와같이 P₁와 P₂의 우선순위는 변화하면서 이어진다.

EDF Scheduling에서는 Rate-monotonic과는 달리 태스크가 주기 태스크일 필요가 없다. 마감시간만 알고있다면 P₁과 P₂간의 우선순위를 정하여 EDF정책으로 스케줄링을 진행할 수 있다.

다만 EDF를 진행하기 위해서는 프로세스가 실행가능해 질 때 자신의 마감시간을 스케줄러에게 알려줘야만 한다.

EDF는 CPU이용률을 100%까지 활용할 수 있다는 장점도 있다.

(물론 실제로는 Distance Latency 혹은 Interrupt Latency에 의해 CPU이용률이 100%까지는 불가능하다.)