CH10-2 Multiprocessor and Real-Time Scheduling

Real-Time Scheduling

real-time computing: 시스템의 정확성이 연산의 논리적 결과뿐만 아니라 그 결과가 만들어지는 시간에도 의존하는 컴퓨팅 유형

- 정해진 시간 안에 올바른 결과를 내는 것이 핵심이다.

 

Hard real-time task: 반드시 마감 시간을 지켜야 하는 작업

- 마감 시간을 지키지 못하면 치명적인 오류를 유발한다.

Soft real-time task: 마감 시간이 있지만, 이를 지키는 것이 필수적이지 않은 작업

- 마감 시간을 지키지 못하더라도 시스템 전체가 실패하지는 않고 성능 저하만 발생한다.

 

periodic task: 일정하고 예측 가능한 시간 간격으로 반복해서 발생하는 작업

aperiodic task: 예측 불가능한 시점에 무작위로 발생하는 작업

 

soft real-time task, periodic task를 가정하고 2가지 스케줄링 방식을 알아보자.

(1) Earliest-deadline Scheduling

우선순위: deadline

0: A1, B1 도착 → A1 deadline: 20, B1 deadline: 50 A1 deadline이 더 이르기 때문에 A1을 0-10 실행

10-20: B1 실행

20: A2 도착 → A2 deadline: 40, B1 deadline: 50 A2 deadline이 더 이르기 때문에 A2를 20-30 실행

30-40: B1 실행

40: A3 도착 → A3 deadline: 60, B1 deadline: 50 B1 deadline이 더 이르기 때문에 B1을 40-45 실행

45-50: A3 실행

50: B2 도착 → A3 deadline: 60, B2 deadline: 100 A3 deadline이 더 이르기 때문에 A3를 50-55 실행

55-60: B2 실행

60: A4 도착 → A4 deadline: 80, B2 deadline: 100 A4 deadline이 더 이르기 때문에 A4를 60-70 실행

70-80: B2 실행

80: A5 도착 → A5 deadline: 100, B2 deadline: 100 deadline이 같을 때는 먼저 도착한 B2를 80-90 실행

90-100: A5 실행

 

(2) Rate Monotonic Scheduling

우선순위: 주기

T1 - 주기: 4시간, 실행 시간: 1시간

T2 - 주기: 5시간, 실행 시간: 2시간

T3 - 주기: 7시간, 실행 시간: 2시간 

 

주기가 짧은 순서대로 T1, T2, T3로 작업을 한다. 주기가 짧은 task가 도착하면 반드시 실행을 양보해야 한다.

위의 그림에서는 Deadline miss가 1번 발생했다.

 

Priority Inversion

: 더 높은 우선순위의 task가 더 낮은 우선순위의 task가 어떤 작업을 완료하기를 기다려야 하는 상황

 

T1: 가장 높은 우선순위, T2: 중간 우선순위, T3: 가장 낮은 우선순위

 

시간

t1: T3가 실행을 시작하고 공유 자원 s를 잠근다.

t2 - t3: T3 실행

t3: 더 높은 우선순위의 T1이 실행 준비가 돼서 T3은 일시 중단되고 T1 실행

t4: T1이 s를 잠그려고 시도하는데 s는 T3가 사용 중이어서 block된다.

t4-t5: 작업 가능한 T3 실행

t5: 더 높은 우선순위의 T2가 실행 준비가 돼서 T3은 일시 중단되고 T2 실행

 

T1이 T3보다 나중에 실행: priority inversion X (s lock 순서 때문에 순서가 밀린 것이다)

T1이 T2보다 나중에 실행: priority inversion O (T1과 T2는 동시에 사용하는 공유 데이터가 없다)

 

우선순위 상속

낮은 우선순위의 task가 공유 자원을 사용하고 있을 때, 해당 자원을 기다리는 더 높은 우선순위의 task가 발생하면 낮은 우선순위 task가 일시적으로 더 높은 우선순위 task의 우선순위를 물려받는 메커니즘

T3가 s를 잠근 순간부터 풀 때까지 T1의 우선순위를 물려 받는다. 이로써 T1이 T2보다 먼저 작업을 할 수 있게 된다.

 

Windows Scheduling

(1) Multi-level Priority Queue

- Real-time Priority Queues (16개): 큐에서 나와서 다시 자기 자신의 큐로 들어간다. 우선순위가 변하지 않는다.

하나의 큐에 여러 태스크가 있다면 이 태스크들에게 라운드 로빈 방식을 적용한다.

- Variable Priority Queues (16개): 큐에서 나와서 어느 큐로 들어갈지 모른다. 우선순위가 변한다.

피드백 큐를 사용한다. 기준에 따라 우선순위가 높아지기도 낮아지기도 한다.

CPU를 많이 사용하는 프로세스의 우선순위를 낮추고 CPU를 많이 사용하지 않는 프로세스의 우선순위를 높인다.

 

(2) Priority-Driven Preemptive 스케줄링 방식

항상 우선순위가 높은 task를 먼저 실행한다.

 

 

모든 프로세스는 base priority를 갖는다. 프로세스가 스레드를 생성할 때, 해당 thread's base priority는 해당 프로세스의 base priority를 기준으로 설정된다. 스레드의 기본 우선순위를 프로세스의 기본 우선순위보다 최소로 2단계 낮게 설정하거나 최대로 2단계 높게 설정할 수 있다. 스레드의 동적 우선순위는 최대 15이다. 우선순위 16번부터는 실시간 태스크 영역으로 분류되기 때문이다. 또 우선순위가 낮아질 수 있는 최소치는 해당 스레드가 속한 프로세스의 기본 우선순위에서 2를 뺀 값이다.

 

윈도우 멀티 프로세서 스케줄링(N개의 프로세서)

- 글로벌 큐를 사용하는 Load Sharing 기법으로 스케줄링

- 가장 높은 우선순위를 가진 N개의 스레드에 N개의 프로세서가 할당되도록 한다.

- soft affinity

: 디스패처는 레디 상태의 스레드를 이전에 그 스레드가 실행되었던 프로세서에 할당하려고 시도하는 것

: 캐시를 재사용하여 성능을 향상시키기 위한 것이다.

 

Windows는 response time을 줄이는 것을 가장 중요하게 생각한다.

단점으로는 starvation 발생 가능성이 있다는 것이다.

 

UNIX SVR4 Scheduling

160개의 큐가 존재한다.

- real-time processes (159-100)

- kernel-mode processes (99-60)

- user-mode processes (59-0)

 

빠르게 우선순위가 높은 큐를 찾기 위해서 비트 맵을 사용한다. 

 

- 우선순위 기반 선점형 스케줄링

우선순위를 가장 중요하게 생각하고, 선점방식은 더 높은 우선순위를 가진 프로세스나 스레드가 실행 준비 상태가 되면 현재 실행 중인 낮은 우선순위의 프로세스/스레드는 즉시 중단되고 더 높은 우선순위의 프로세스/스레드가 CPU를 차지하게 되는 것을 뜻한다.

 

real-time class

- 고정된 우선순위를 가지고 정해진 시간 퀀텀을 가진다.

- 여러 개의 실시간 클래스 작업들이 동일한 우선순위를 가지고 있다면 RR방식이다. 각 작업은 정해진 시간 퀀텀만큼 CPU를 사용하고 다음 작업에게 차례를 넘겨주는 방식으로 순환한다.

 

time-sharing class

- 우선순위가 동적으로 변경될 수 있다. CPU를 많이 사용하는 스레드는 우선순위가 점차 낮아지고, 입출력 작업을 많이 하는 스레드는 우선순위가 점차 높아진다.

 

Windows와의 차이점

시분할 프로세스에 할당되는 시간 할당량은 해당 프로세스의 우선순위에 따라 달라진다.

우선순위 0의 경우(우선순위가 가장 낮다) 가장 긴 시간 할당량인 100ms를 받는다.

우선순위 59의 경우(우선순위가 가장 높다) 가장 짧은 시간 할당량인 10ms를 받는다.

이를 통해서 starvation 발생 가능성을 낮출 수 있다.

 

Linux Scheduling

- FIFO real-time threads (0~99)

- RR real-time threads (0~99)

- non-real-time threads (100~139)

 

 

Linux Scheduling for Real-time Classes

(1) FIFO

- 실행 중인 FIFO 스레드는 일반적으로 중단되지 않는다.

 

1. 더 높은 우선순위를 가진 다른 FIFO 스레드가 준비 상태가 되었을 때

2. 현재 실행 중인 FIFO 스레드가 blocked 상태가 되었을 때

3. 시스템 콜 후 자발적으로 CPU 사용을 포기했을 때

위의 3가지에만 예외적으로 중단된다.

- 여러 개의 스레드가 동일한 우선순위를 가지고 있다면 가장 오래 기다린 스레드가 먼저 실행된다.

 

(2) RR

- FIFO와 유사하지만 각 스레드 time-slice가 추가로 설정된다. 정해진 시간만큼 실행한 뒤에 다음 스레드로 교체된다.

 

 

 

Linux Scheduling Data Structures

비트맵을 사용하여 스케줄러가 어느 우선순위 큐에 task가 있는지 즉시 알 수 있다.

 

Active Queues

- 총 140개의 큐로 구성 (각 큐는 하나의 우선순위에 해당)

- 각 큐는 해당 우선순위를 가진 ready task들을 저장한다.

- CPU에서 곧 실행될 준비가 된 task들이 이 큐에 있다.

 

Expired Queues

- 총 140개의 큐로 구성

- 시간 할당량을 다 쓴 task들이 저장된다.

- 한 번 실행되었다가 시간이 만료된 task는 이 큐로 이동된다.

 

상황 1: 더 높은 우선순위의 스레드에게 선점당하는 경우

스레드가 CPU를 점유하고 실행 중인데 자신보다 더 높은 우선순위를 가진 다른 스레드가 나타나면 현재 실행 중인 스레드는 즉시 CPU를 빼앗기고 다시 원래의 Active 큐로 돌아간다.

 

상황 2: I/0 작업이나 동기화 등으로 Blocked되는 경우

스레드가 CPU를 사용하다가 디스크 입출력, 동기화 대기 등의 이유로 Blocked 상태가 될 수 있다. 이 경우 스레드는 CPU를 놓아주고 해당 작업을 완료할 때까지 대기한다. Blocked 상태였다가 다시 실행 가능한 상태로 돌아올 때는 스케줄러가 보통 해당 스레드의 우선순위를 높여서 Active 큐로 다시 넣어준다.

 

상황 3: 할당된 Time Out을 모두 사용하는 경우

스레드가 할당된 시간 할당량을 끝까지 모두 사용하고 정상적으로 CPU 사용을 마치는 경우로, 이 스레드는 Active 큐로 돌아가는 것이 아니라 Expired 큐로 보내진다. 

 

큐 교환

Expired 큐는 시간 할당량을 다 쓴 스레드들이 계속 쌓이는 곳이다. 스케줄러는 기본적으로 Active 큐에 있는 스레드들만 처리한다. 이러다 보면 결국 Active 큐가 점차 비어가고 모든 스레드가 Expired 큐에서 대기하는 상황이 올 수 있다. 

 

Active 큐가 비어있는 것을 확인하면 Active 큐와 Expired 큐의 역할을 통째로 바꾼다.

이제 기존의 Expired 큐에 있던 모든 스레드들이 새로운 Active 큐가 되어 실행 가능한 상태가 된다.

기존의 Active 큐는 비어있는 새로운 Expired 큐가 된다.

 

우선순위가 높은 프로세스들은 preemptive 당할 가능성이 낮아서 timeout까지 CPU를 모두 사용하고 Expired 큐로 들어가게 된다. 하지만 우선순위가 낮은 프로세스들은 우선순위가 높은 프로세스들에 의해 preemptive 당할 가능성이 높아서 preemptive 되어 Active 큐에 남겨된다. 결국 Active 큐에 남은 프로세스들이 Expired 큐에 있는 프로세스들보다 우선적으로 실행되기 때문에 starvation 발생 가능성이 낮아진다.