Chapter5 실시간 스케줄링

1. 실시간 CPU 스케줄링(Real-Time CPU Scheduling)

1) review

프로세스 1, 2, 3, ...n 이 ready queue에 존재하고 스케줄러가 하는 일은 이들 중 하나를 스케줄링하여 CPU 자원을 할당하고 프로세스는 시작된다.

프로세스에게 CPU를 할당하는 것은 디스패처가 하는 일이다. 그리고 ready queue에 있는 프로세스를 선택하는 것은 스케줄러가 하는 일이다.

스케줄링이라고 하는 것은 스케줄러가 프로세스를 선택하는 것인데 어떤 기준으로 선택하는 것인가? -> 전체 프로세스의 wating time즉 CPU 자원을 할당받아서 실제로 실행하는데까지 걸린 시간을 최소화할 수 있는 가준으로 선택한다.

각각의 프로세스의 wating time의 합 또는 평균이 최소화 할 수 있는 프로세스를 선택하게 된다.

---

 

 

2) Minimizing latency

● Anti-lock Breaking System(ABS) 이것이 무엇이냐?

비유를 들어 자동차 운전을 하다 어떤 물체가 나타나면 브레이크를 밣는데 그럼 마찰이 일어나며 서서히 멈추게 된다. 이것을 연구를 해봤더니 바퀴를 조금 굴리고 멈추고, 조금 굴리고 멈추고를 반복하는 것이 마찰이 계속 일어난다. 즉 마찰력을 높일 수 있다는 연구 결과가 있다. 그래서 바퀴를 잠구지 않는다.(Anti) 그래서 바퀴가 현재 미끄러지고 있다는 판단이 들어면 재빨리 ABS 시스템을 개입시켜 바퀴를 굴렸다 잠궜다를 반복한다.

바퀴가 미끄러지고 있는 순간부터 ABS 시스템이 동작하기 까지 시간이 3ms~5ms가 걸려야한다는 조건이 존재한다. 그래서 ABS시스템은 상황 판단을 해서 개입까지 최소 시간인 deadline을 준다.(3ms~5ms) 따라서 3ms에 한 번씩 바퀴가 미끄러지고 있는지 판단해야한다.

즉 CPU가 3ms에 한 번씩 확인을 해야한다는 것이다. 이러한 deadline이 정해진 시스템을 Hard real-time system 이라고한다.  기존에 있는 우리가 살펴본 프로세스는 deadline이 없었다.

 

○ 선점형이란?

deadline이 정해진 프로세스라면 기존에 CPU자원을 할당받고 실행되고 있던 프로세스가 있는데 실행이 더 위급한 프로세스가 나타나게 되면 기존의 프로세스를 keep out하고 그 자리를 실행이 위급한 프로세스가 차지해야할 것이다. 이것을 (선점형 스케줄링이라고한다.) 즉 deadline이 다가오는 프로세스가 등장하면 기존에 CPU에 있는 프로세스는 keep out하고 deadline이 급한 프로세스를 실행하게 된다.

실시간 CPU 스케줄링은 선점형이 되야겠구나를 예측할 수 있다. 이후 기존에 있는 프로세스를 keep out하고 다른 프로세를 실행할 수 있도록 도와주는 작업을 Context Swtiching이라고한다.

선점형 스케줄링의 성공의 관건 중 하나는 Context Switching이 빨라야한다. 아래 두 가지 latency를 보자.

 

① Dispatch latency

Context Switching은 사실 Dispatch latency이다. 현재 실행 중인 프로세스가 다른 프로세스로 바뀌는데 걸리는 시간(latency)를 말한다.

 

② Interrupt latency

프로세스와 프로세스 간에 CPU 실행을 위한 자원 교체가 Dispatch latency라고 하면 Interrupt latency란 CPU에 interrupt가 발생한 시점부터 해당 인터럽트 처리 루틴이 시작하기까지의 시간을 말한다.

Dispatch latency, Interrupt latency이 두가지 latency를 최소화할 때 비로서 선점형 스케줄링이 신속하게 동작할 수 있다는 것이다.

---

 

 

3) 실시간 스케줄링의 개념의 필요한 내용 -> 우선순위 기반 스케줄링(Priority-Based Scheduling)

 

실시간 운영체제에서 가장 중요한 기능은 실시간 프로세세의 CPU가 필요할 때 바로 응답을 해주는 것이다. 따라서 실시간 운영체제의 스케줄러는 선점을 이용한 우선순위 기반의 알고리즘(Priority-Based Scheduling)을 지원해야한다.

 

● soft real-time 스케줄러

실시간 CPU 스케줄링에서는 우선순위가 높은 프로세스가 도착하면 우선순위가 낮은 프로세스가 양보를 해야한다. 실시간 스케줄링을 위해서는 아래 두 가지를 갖춰야한다.

 

① 프로세스의 우선순위를 표현할 수 있어야한다.

② 그리고 선점형이 되어야한다.

 

이 두가지 기능을 모두 가진 스케줄러를 soft real-time 스케줄러라고한다. (이것은 실시간 스케줄링이라고는 할 수 없다.)

 

 

● hard real time 스케줄링(실시간 스케줄링이 가져야할 조건)

① 프로세스의 우선순위를 표현할 수 있어야한다.

② 그리고 선점형이 되어야한다.

③ 프로세스가 언제까지 실행을 완료해야한다는 데드라인을 맞출 수 있어야한다.

④ 프로세스의 실행 주기가 있어야한다.

 

t -> CPU 자원을 얻었을 때마다 고정된 수행 시간

 

d -> deadline 언제까지 프로세스가 종료해야하는지(CPU로부터 반드시 서비스를 받아야하는 마감 시간) -> 예를 들어 주기가 50이라면 데드라인은 50, 100, 150이 되고 이 데드라인은 CPU로부터 반드시 서비스를 받아야하는 시간임을 의미한다.

 

p -> 주기로 deadline에 맞춰 작업을 종료하는 것이 얼마만에 한 번씩 이루어져야 하는지?(50ms라면 0, 50ms, 100ms..에서 프로세스가 실행되야한다.)

 

 

● 실시간 스케줄링의 종류: Rate Motonic 스케줄링

P1은 주기가 50ms, 실행 시간은 20ms이다

P2는 주기가 100ms, 실행 시간은 35ms이다.

 

이 스케줄링에서는 주기가 짧을수록 우선순위가 높게 부여된다.

처음 P1이 우선순위가 높기 때문에 먼저 20ms 만큼 실행하고 다음 P2가 실행하는데 P1의 주기인 50ms까지만 실행하고 선점되어 P1이 다시 실행한다.

즉 P1은 50ms 마다 실행이되야함을 의미한다. P2는 100ms 단위 마다 실행이 되야한다.

100ms에서는 P1, P2가 동시에 실행되길 원하는데 이때는 우선순위가 높은 P1이 실행된다.

 

 

● 실시간 스케줄링의 종류: Rate Motonic 스케줄링로도 해결이 안되는 경우

Rate Motonic 스케줄링으로도 해결이 안되는 경우가 있는데 그 예로

P1은 주기가 50ms, 실행시간(t) = 25ms

P2은 주기가 80ms, 실행시간(t) = 35ms

 

이 경우는 P1이 주기가 짧기에 우선순위가 높다. 따라서 먼저 P1이 25ms 실행한다. 그 다음 P2는 (50-25) 35ms 만큼 실행한다. 주기가 50ms이 되면 P2가 선점되어 P1이 25만큼 실행하여 P2가 실행할려고 하는데 현재 총 실행시간은 75ms이다. 이때 P2가 실행하게 되는데 이는 데드라인 80에 충족되지 못하게 된다.

 

따라서 Rate Motonic 스케줄링로도 해결이 안되는 경우가 있다.

 

 

○ CPU 이용률 = t/p (시간/주기)

P1은 주기가 50ms, 실행 시간은 20ms이다

P2는 주기가 100ms, 실행 시간은 35ms이다.

이 경우의 이용률을 계산해보면

P1의 이용률 : 20/50 = 0.40

P2의 이용률 : 35/100 = 0.35

P1 + P2 = 75% 즉 CPU 이용률이 75%이다.

 

하지만

P1은 주기가 50ms, 실행시간(t) = 25ms

P2은 주기가 80ms, 실행시간(t) = 35ms 이 경우를 보자

P1의 이용률 : 25/50 = 0.5

P2의 이용률 : 35/80 = 0.35

P1 + P2 = 94% 즉 CPU 이용률이 94%이다.

 

n개의 프로세스를 스케줄링하면서 최악의 CPU 이용률은 아래와 같다. 

위 값보다 작아야한다. (N은 스케줄링할 프로세스의 개수이다.)
즉 위 수식은 N개의 프로세스를 스케줄링할 때 CPU이용률은 위 수식보다는 작아야한다는 것이다. N이 2일 때는 대략 83%가 된다. 따라서 CPU 이용률이 75%이다. 인경우에서는 실시간 스케줄링이 가능했던 것이고, CPU 이용률이 94%일때는 실시간 스케줄링이 안되는 것이었다.

 

 

실시간 스케줄링의 종류: Rate Motonic 스케줄링로도 해결이 안되는 경우를 해결하기 위해 아래 실시간 스케줄링 기법을 만들게 된다.

 

 

● Earliest Deadline First 스케줄링(EDF)

이는 데드라인에 따라서 우선순위를 동적으로 변경하는 것이다.

이전 내용에서는 주기에 따라 우선순위가 고정되어 있었다.

이 알고리즘에서는 프로세스는 실행 가능하게 되면 자신의 마감시간을 시스템에게 알려야한다.우선순위는 새로 실행 가능하게 된 프로세스의 마감시간에 맞춰서 다시 조정된다.

 

위 예시는

P1의 주기 : 50

P1의 실행 시간 : 25

P2의 주기 : 80

P2의 실행 시간 : 35

 

일단 처음 데드라인은 50, 80이므로 P1이 먼저 25만큼 실행되고 그 다음 P2가 실행되다가 50ms인 시점에 P1의 주기가 돌기 때문에 이 시점에 P1의 데드라인과 P2의 데드라인을 비교한다. 50ms인 시점에 만약 P1이 들어온다면 데드라인은 100ms가 되고 P2는 현재 데드라인이 80이기 때문에 P2의 데드라인이 더 작아 P2의 실행을 계속한다.

그리고 시간 80ms인 시점에 똑같이 P1의 데드라인은 100이고 P2의 데드라인은 160이 된다. 따라서 P1이 계속 실행을 이어간다.

그리고 시간이 100ms인 시점에 P1이 실행된다면 P1의 데드라인은 150이 되고 P2의 데드라인은 180이므로 P1이 선점하여 실행된다.

---