IX : 스케줄링 알고리즘과 우선순위

IX : 스케줄링 알고리즘과 우선순위

뇌를 자극하는 윈도우즈 시스템 프로그래밍 을 읽고 정리한 문서입니다 ;)

프로세스의 스케줄링

우리가 접하는 대부분의 운영체제는 멀티 프로세스 기반 운영체제이다. 하나의 프로그램이 실행되기 위해서는 하나의 CPU 코어가 필요한데, 프로세스 수만큼 CPU 코어가 존재할 수 있다면 가장 이상적일 것이다.

하지만 우리의 CPU 코어는 제한되어 있고, 웬만한 범용 OS에서 백그라운드 프로세스 개수만 해도 수십개가 넘어간다. 따라서 스케줄러라는 기능이 등장하게 된다. 실행 중인 모든 프로세스들에게 골고루 CPU 코어를 할당해주는 것이다.

RTOS

RTOS와 일반 OS의 차이는 응답성에 있다. RTOS는 응답성이 Windows와 같은 일반 OS보다 좋다. 단, 이는 결코 RTOS는 일반 OS보다 빠른 OS이다라는 결론이 아니다.

일반 OS는 범용적인 사용을 위해서 디자인되어 있지만, RTOS는 사용하는 영역이 제한적이고, 지정된 몇몇 일을 제외하고는 전력 소모량을 최소화시키며 일을 하지 않는다. 결국, 사용되는 목적이 구체적이고 제한적이다 보니, 단순하게 디자인되어있고 일반 OS보다 가볍기에 응답성이 좋은 것이다.

이러한 RTOS를 Soft RTOS라고 하고, Hard RTOS에서는 이 개념에 중요한 한 가지가 더 포함된다.

데드라인 이라는 개념인데, 이는 시간에 크리티컬한, 자동차의 ABS나 핵발전소 시스템 등 시스템이 예시가 될 수 있다. 이 Hard RTOS는 단순히 CPU 속도가 빠르다고 만족되는 것이 아니기 때문에 일반 OS와 전혀 다른 알고리즘으로 동작하게 된다.

선점형 OS와 비선점형 OS

프로세스의 실행을 다른 프로세스로 넘기는 방식에 따라서 선점형 OS와 비선점형 OS로 구분된다.

비선점형 OS는 현재 실행 중인 프로세스보다 높은 우선순위의 프로세스가 등장한다고 해서 실행의 대상을 바로 변경하지 않는다. 이는 인터렉티브한 프로그램 구현 시 프로그래머 의존도가 높아지는 문제점을 가지므로, CPU를 독차지하지 않도록 신경쓰며 프로그래밍해야 한다.

선점형 OS는 실행 중인 프로세스보다 높은 우선순위의 프로세스가 등장하면 스케줄러가 바로 조정을 가한다. 비선점형 OS에 비해 스케줄러가 하는 일이 많아졌지만, 프로그래머가 신경을 쓸 일이 줄어들었다.

이러한 특성은 둘 이상의 프로세스를 동작시키는 멀티 프로세스 기반 OS에 적합하기에, 오늘날 접할 수 있는 대부분의 운영체제는 물론 RTOS까지 선점형 OS에 포함된다.

우선순위 스케줄링 알고리즘

우선순위 스케줄링 알고리즘이란 각각의 프로세스마다 우선순위를 부여해서 우선순위가 높은 프로세스를 먼저 실행시키는 방법이다.

이 경우 우선순위가 7인 프로세스와 우선순위가 2인 프로세스가 있을 때, 우선순의 2인 프로세스는 아무리 기다려도 CPU를 할당받지 못하게 되는데, 이를 기아 상태라고 한다.

단, 일반적인 프로세스는 많은 시간을 I/O에 소모하기에, 이 시간 동안 우선순위 2인 프로세스 또한 동작할 수 있게 된다.

Windows 또한 이러한 우선순위 스케줄링 알고리즘으르 적용하고 있다.

Round-Robin 스케줄링 알고리즘

우선순위가 동일한 프로세스의 경우에는 누가 먼저 실행되는지를 해결하기 위해 라운드 로빈 방식 또한 Windows가 채용하고 있다.

실행의 최소 단위 시간 간격을 가리켜 퀀텀 또는 타임 슬라이스라고 하는데, 이를 기준으로 프로세스는 CPU의 할당을 넘기게 된다.

스케줄링의 시점

어느 시점에 스케줄러가 동작하도록 디자인하면 좋을지 고민해보자

프로세스의 실행시간 간격에 해당하는, 타임 슬라이스마다 스케줄러가 동작하여 다음 프로세스에게 CPU를 할당해주어야 한다.

또한, 새로운 프로세스가 준비 큐에 등장할 때라던지 실행중이던 프로세스가 완료될 때 또한 다음 프로세스 판단이 필요하므로 스케줄러가 동작해야 한다.

이와 비슷하게 실행중이던 프로세스가 블로킹 상태가 되면 스케줄러는 다음 프로세스에게 CPU를 할당해주어야 한다.

Priority Inversion

우선순위 역전 현상은 프로세스의 우선순위가 뒤바뀌는 현상을 의미한다.

프로세스 A, B, C 순서대로 우선순위가 높고, 만일 프로세스 A가 프로세스 C를 자식 프로세스로 가지고 있는 상황에서, 프로세스 C의 결과를 프로세스 A가 기다리려고 블로킹 상태에 들어간다고 해보자.

이 때 프로세스 A가 블로킹 상태가 되면 프로세스 C 가 아닌 프로세스 B가 CPU를 배정받을 것이다.

따라서 이를 방지하려면 프로세스 A는 블로킹 상태에 들어가기 전에 프로세스 C의 우선순위를 자신과 동일한 레벨로 올리는 작업을 선행해야 한다.

Windows 프로세스 우선순위

윈도우는 총 6단계의 우선순위 계층을 제공한다.

IDLE	기준 우선순위 4
BELOW_NORMAL	기준 우선순위 4와 9 사이
NORMAL	기준 우선순위 9
ABOVE_NORMAL	기준 우선순위 9와 13 사이
HIGH	기준 우선순위 13
REALTIME	기준 우선순위 24

만일 윈도우에서 우선순위를 높인 프로세스가 Busy waiting을 하고 있다면, 이보다 우선순위가 낮은 프로세스들은 CPU를 할당받지 못할 것이다. 이는 실행속도를 조절하기 위해 Busy waiting을 하는 것이 문제이다. 일반적인 프로세스들은 I/O 작업에 적지 않은 시간을 소모하는데다가, 실행 속도 조절이 필요하다면 Sleep 등의 블로킹 상태로의 전환을 통하기 때문이다.

이것만은 알고 갑시다

• 응답성 관점에서 RTOS와 일반 OS의 구분
  • 속도와는 별개로 응답성을 기준으로 RTOS와 일반 OS를 구분해야 한다. RTOS는 구제적인 작업에 특화되어있는 간단하고 집중된 OS이기에 어떠한 작업을 요청했을 때 응답하는 속도가 빠르다. 대신 둘 이상의 일을 동시에 처리하는 멀티 프로세스의 성격이 약해진다.
• 선점형 OS와 비선점형 OS의 특징
  • 프로세스의 실행을 다른 프로세스에게 넘기는 방식에 따라 선점형과 비선점형이 나뉘어지게 되며, 비선점형 OS인 Windows를 위시한 대부분의 OS는 우선순위와 라운드 로빈을 통해 프로세스들을 스케줄링한다.
• 스케줄러가 동작하는 시기
  • 매 타임 슬라이스가 끝날 때
  • 새로운 프로세스가 등장하거나 실행중이던 프로세스가 종료될 때
  • 실행중이던 프로세스가 블로킹 상태로 전환될 때