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

process의 deadline을 고려하여 스케줄링하는 알고리즘이다.

1. 실시간 시스템

(1) 연성 실시간 시스템 (Soft real-time systems)

• 데드라인(deadline)을 만족하다는 것을 보장하지 않는다.
• 중요한 실시간 프로세스가 그렇지 않은 프로세스에 비해 우선권만 가지고 있다.

(2) 경성 실시간 시스템 (Hard real-time systems)

• 데드라인(deadline)을 100% 만족한다는 것을 보장한다
• 데드라인이 지난 후 서비스를 받는 것은 서비스를 전혀 받지 않는 것과 동일한 결과이다.

 

2. 지연 시간 (Latency)

(1) 이벤트 지연시간 (Event Latency)

이벤트가 발생해서 그에 맞는 서비스가 수행될 때까지의 시간

• 인터럽트 지연시간과 디스패치 지연시간으로 나누어진다.

(2) 인터럽트 지연시간 (Interrupt Latency)

CPU에 인터럽트가 발생한 시점부터 해당 인터럽트 처리 루틴이 시작하기 전까지의 시간

• 인터럽트 발생하면 운영체제는 우선 수행 중인 명령어를 완수하고 발생한 인터럽트의 종류를 결정한다.
• 인터럽트를 처리하기 전에 현재 수행 중인 프로세스의 상태를 저장해 놓는다. 
• 실시간 태스크가 즉시 수행될 수 있도록 인터럽트 지연시간을 최소화해야 한다.

(3) 디스패치 지연시간 (Dispatch Latency)

스케줄링 디스패처가 하나의 프로세스를 block 시키고 다른 프로세스를 시작하는 데까지 걸리는 시간

• 디스패치 지연시간의 충돌 단계
  • 커널에서 동작하는 프로세스에 대한 선점
  • 높은 우선순위의 프로세스가 필요한 자원을 낮은 우선순위 프로세스 자원이 방출
• 디스패치 단계는 우선순위가 높은 프로세스를 사용 가능한 CPU에 스케줄 한다.

 

3. Rate Monotonic 스케줄링 (정적 우선순위 스케줄링)

주기(Priority)에 따라서 우선순위가 정해진다.

• 주기가 짧을수록 우선순위가 높아지고, 주기가 길면 낮은 우선순위를 가진다. 즉, CPU를 더 자주 필요로 하는 태스크에게 더 높은 우선순위를 준다.
• 선점 가능한 정적 우선순위 정책을 이용하여 주기 태스크들을 스케줄 한다. 낮은 우선순위의 태스크의 작업이 실행 중, 높은 우선순위 태스크의 작업이 준비되면, 높은 우선순위의 태스크가 CPU를 선점한다. 

(1) Example

• Process P1, P2
• P1의 주기 : 50, P2의 주기 : 100
• P1의 수행 시간 : 20, P2의 수행 시간 : 35
• P1의 CPU 이용률 20/50 = 40%, P2의 CPU 이용률 35/100 = 35%, 총 75%
• 프로세스의 마감시간(deadline)은 다음 주기가 시작하기 전까지.
• P1의 주기가 P2의 주기보다 짧기 때문에 우선순위 P1 > P2

• 50에서 새로운 P1이 생성되면 P1의 우선순위가 높기 때문에 P1이 CPU를 선점한다.
• P1의 수행이 끝나면(70) 나머지 P2 작업이 실행된다.
• P1, P2 모두 deadline안에 작업이 끝난다.

(2) 문제 발생

• Process P1, P2
• P1의 주기 : 50, P2의 주기 : 80
• P1의 수행 시간 : 25, P2의 수행 시간 : 35
• P1의 CPU 이용률 25/50 = 50%, P2의 CPU 이용률 35/80 = 44%, 총 94%
• 프로세스의 마감시간(deadline)은 다음 주기가 시작하기 전까지.
• P1의 주기가 P2의 주기보다 짧기 때문에 우선순위 P1 > P2

• P2의 작업이 85에서 끝난다. 이것은 deadline을 지키지 못한다.
• Rate Monotonic은 CPU 이용률에 한계가 있다. 자원을 최대로 사용하는 것이 불가능한다.
  • 위의 예시는 이용률 94%이므로 2개일 때의 이용률 상한 83%를 넘는다.
• CPU 이용률 상한 : N(2^(1/N)-1)
• 1개일 때는 100%, 2개일 때는 83%.... 최저 69%

 

4. Earliest Deadline First, EDF 스케줄링 (동적 우선순위 스케줄링)

마감시간(Deadline)에 따라서 우선순위를 동적으로 부여

• 마감시간이 빠를수록 우선순위는 높아지고, 늦을수록 낮아진다.
• 프로세스가 실행 가능하게 되면 자신의 마감시간을 시스템에 알려주어야 한다.
• 프로세스들이 주기적일 필요도 없고, CPU 할당 시간도 상수 값으로 정해질 필요 없다.
• 이론적으로는 EDF는 최적으로 100% CPU를 사용할 수 있다.
  • 실제로는 Context Switching 등의 overhead로 인해 100% 사용률은 불가능

(1) Example

• Process P1, P2
• P1의 주기 : 50, P2의 주기 : 80
• P1의 수행 시간 : 25, P2의 수행 시간 : 35
• 프로세스의 마감시간(deadline)은 다음 주기가 시작하기 전까지.

• t=0, P1(deadline: t=50) vs P2(deadline: t=80), P1이 우선순위를 가진다.
• t=50, P1(deadline: t=100) vs P2(deadline: t=80), P2가 우선순위를 가진다.
• t=80, P1(deadline: t=100) vs P2(deadline: t=160), P1이 우선순위를 가진다.
• t=100, P1(deadline: t=150) vs P2(deadline: t=160), P1이 우선순위를 가진다.
  • P2 실행 중 P1이 들어오면 P1이 CPU를 선점하게 된다.

 

5. 일정 비율의 몫 스케줄링 (Proportionate Share Scheduling)

스케줄러는 모든 응용들에 T개의 시간 몫을 할당하여 동작한다.

• 일정 비율 몫 스케줄러는 응용이 시간 몫을 할당받는 것을 보장하는 승인 제어 정책과 함께 동작해야 한다.
• 승인 제어 정책은 사용 가능한 충분한 몫이 존재할 때, 그 범위 내의 몫을 요구하는 클라이언트에게만 실행을 허락한다.
• Ex) A:50, B:15, C:20 총 85개의 몫만 할당, D가 30 몫을 요구하면 승인 컨트롤러는 D의 시스템 진입을 거부한다.