[ 뇌를 자극하는 윈도우즈 시스템 프로그래밍 ] Chapter 09. 스케줄링 알고리즘과 우선순위

01. 프로세스의 스케줄링(Scheduling)

우리가 쉽게 접하는 대부분의 운영체제는 멀티 프로세스(Multi-Process) 기반 운영체제이다. 따라서 실행 중인 모든 프로세스들에게 골고루 CPU를 할당하는 일이 필요하기 때문에, 스케줄러(Scheduler)가 필요하다.

 

일반 OS와 리얼타임(Real Time) OS의 차이점

RTOS와 일반 OS의 차이는 응답성(응답속도)에 있다. RTOS는 응답성이 Windows와 같은 일반 OS보다 좋다. 따라서 우리가 명령하는 일들을 신속히 처리한다.

일반 OS는 범용적인 사용을 위해서 디자인되어 있다. 즉, Windows나 Linux는 특수한 목적이 정해져 있는 OS가 아니다.

반면에 RTOS는 사용하는 영역이 제한적이다. 범용적인 OS보다 하는 일이 적다. 예를 들어, 핸드폰에 들어가는 RTOS는 키를 입력하거나 수신되는 데이터가 없으면 하는 일이 거의 없다. 때문에 RTOS는 핸드폰 환경에서 최고의 응답성을 보인다.

정리하면, RTOS는 일반 OS에 비해서 속도가 빠른 것이 아니다. 사용되는 목적이 구체적이고 제한적이다 보니, 보다 단순하게 디자인되어 있고, 일반 OS에 비해서 훨씬 가볍다. 따라서 응답성이 좋을 뿐이다.

 

 

Soft RTOS vs Hard RTOS

앞에서 ROTS가 일반 OS와 별반 차이가 없지만, 하는 일이 특화되다 보니 응답성이 일반 OS에 비해 좋은 것뿐이라고 하였다. 이러한 RTOS를 가리켜 Soft RTOS라 한다.

그러나 전통적으로 말하는 RTOS는 Hard RTOS를 의미한다. Hard RTOS는 일반 OS에 비해서 단순히 응답성이 좋은 정도로 설명되지 않는다. Hard RTOS에서 중요시하는 것은 단순히 개선된 응답성이 아니라, 데드라인(Dead Line)이다.

데드라인은 정말로 시간에 크리티컬(Critical)한 상황에서 발생한다. 예를 들어 자동차의 ABS 시스템은 시간에 크리티컬하다. 만약 0.1초라도 늦게 동작하면 이는 인명피해로 연결될 수 있다. 이처럼 데드라인이 중요한 시스템에서 이를 충족시킬 수 있는 능력을 지니는 RTOS를 가리켜 Hard RTOS라 한다.

데드라인 충족은 단순히 CPU의 속도가 빠르다고 만족되는 것이 아니기 때문에 Hard RTOS를 디자인하는 것은 결코 쉬운 일이 아니며, 이를 위해서는 일반 OS와는 전혀 다른 알고리즘으로 스케줄러가 디자인된다.

 

선점형(Preemptive) OS와 비선점형(Non-Preemptive) OS

OS를 구분할 때 응답성을 기준으로 범용 OS와 RTOS를 구분하듯이, 프로세스의 실행을 다른 프로세스로 넘기는 방식에 따라서 선점형 OS와 비선점형 OS를 구분한다.

 

비선점형 OS

비선점형 OS는 현재 실행 중인 프로세스보다 높은 우선순위의 프로세스가 등장한다고 해서 실행의 대상을 바로 변경하지는 않는다. 새로 등장한, 보다 높은 우선순위의 프로세스가 실행되기 위해서는 현재 실행 중인 프로세스가 명시적으로 CPU를 양보할 때까지, 혹은 I/O 작업 등으로 블로킹 상태에 놓일 때까지 기다려야만 한다.

따라서 이러한 비선점형 OS는 인터렉티브(Interactive)한 프로그램 구현 시 프로그래머 의존도가 높아지는 문제점을 지닌다. 프로그래머는 자신이 개발한 프로그램이 CPU를 독차지하지 않도록 신경 써서 프로그래밍해야 한다.

 

선점형 OS

선점형 OS는 현재 실행 중인 프로세스보다 높은 우선순위의 프로세스가 등장하면 스케줄러에 의한 실행순서 조정이 적극! 가해진다.

이는 비선점형 OS에 비해 스케줄러가 하는 일이 많다는 점이 특징이다. 이러한 특성은 둘 이상의 프로세스를 동작시키는 멀티 프로세스 기반 OS에 적합하다. 왜냐하면 스케줄러에 의해 실행순서가 적절히 조정되기 때문에 프로그래머가 신경 쓸 일이 거의 없어지기 때문이다. 오늘날 접하는 대부분의 OS는 선점형 OS로, RTOS도 선점형 OS에 포함된다.

 

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

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

예를 들어, 우선 순위가 7인 프로세스와 우선순위가 2인 프로세스를 동시에 실행시켰다고 가정해 보자. (숫자가 큰 것이 우선순위가 높은 것) 흔히 생각할 수 있는 것이 시간의 배분이다. 우선순위 7인 프로세스가 10초 정도 실행되면, 우선순위 2인 프로세스는 적어도 2초 정도는 실행될 걸로 생각한다. 정답은 “Yes”가 될 수도 있고 “No”가 될 수도 있다.

먼저, 우선순위가 높은 프로세스가 작업을 마쳐야 그다음 우선순위의 프로세스가 실행된다는 관점에서 본다면 위 질문의 답은 “No”이다.

하지만, 높은 우선순위 프로세스가 I/O관련 작업을 하는 과정에서, 낮은 우선순위의 프로세스가 실행 기회를 얻을 수도 있기 때문에 “Yes”라고도 답할 수 있다.

그러나 보편적인 운영체제에서는 우선순위가 2인 프로세스는 결코 실행되지 않는다. 이러한 상황을 가리켜 기아(Starvation) 상태라 하는데, 우선순위가 2인 프로세스는 기아 상태에 빠지게 된다.

 

라운드 로빈(Round-Robin) 스케줄링 알고리즘

우선순위가 동일한 프로세스의 경우에는 누가 먼저 실행되는가? 이때 형평성 문제가 발생하게 된다.

이 알고리즘은 같은 우선순위의 프로세스들간 형평성 유지를 위해, 정해진 시간 간격만큼만 실행을 하고 우선순위가 동일한 다른 프로세스들에게 CPU의 할당을 넘기는 방식을 제공한다.

이때, 실행의 최소 단위 시간 간격을 가리켜 퀀텀(Quantum) 혹은 타임 슬라이스(Time Slice)라 하는데, 동일한 우선순위의 모든 프로세스들은 이 타임 슬라이스를 기준으로 CPU의 할당을 넘기게 된다.

타임 슬라이스를 길게 하면 인터렉티브한 시스템에서 문제가 될 수 있다. 그렇다고 타임 슬라이스를 너무 짧게 하면 그만큼 컨텍스트 스위칭이 자주 발생하여 성능에 저하를 가져다준다.

 

정리하면 다음과 같다.

Windows 운영체제는 프로세스를 스케줄링하는 데에 있어서 우선순위, 그리고 라운드 로빈 기반의 알고리즘을 적용하고 있다. (대부분의 운영체제의 이야기다.) 

 

즉, 다음과 같은 구조로 관리되는 것이다.

 

 

스케줄링 알고리즘에 의해서 스케줄링이 진행되는 시점

스케줄러가 언제 동작하는지를 이해하는 것도 중요하다.

세 가지 관점에서 생각해 보자.

첫 번째는 라운드 로빈 방식의 스케줄링 알고리즘 적용에 대한 관점이다. 정해진 시간이 지나면 다음 프로세스에게 실행순서를 넘겨야 한다. 그런데 실행순서를 넘기기 위해서는 스케줄러가 동작해야 한다. 따라서, 프로세스의 실행시간 간격에 해당하는 매 타임 슬라이스마다 스케줄러는 동작해야 한다.

 

두 번째는 우선순위 방식의 스케줄링 알고리즘 적용에 대한 관점이다. 우선순위가 높은 프로세스는 무조건 먼저 실행되어야 하기 때문에, 새로운 프로세스가 생성 및 소멸될 때마다 스케줄러가 동작해야 한다.

 

세 번째 관점은 블로킹 상황이다. 현재 실행 중인 프로세스가 블로킹 상태가 되면 프로세스가 대신 실행되기 때문에, 현재 실행 중인 프로세스가 블로킹 상태에 놓이면, 다음 실행될 프로세스 선정을 위해서도 스케줄러가 동작하게 된다.

정리하면 다음과 같다.

 

Case 1. 매 타임 슬라이스(Time Slice)마다 스케줄러 동작

Case 2. 프로세스가 생성 및 소멸될 때마다 스케줄러 동작

Case 3. 현재 실행 중인 프로세스가 블로킹 상태에 놓일 때마다 스케줄러 동작

 

Priority Inversion

이는 말 그대로 프로세스의 우선순위가 뒤바뀌는 현상을 말한다. 예를 들어 다음과 같은 우선순위를 가지는 프로세스가 있다고 가정해 보자.

 

프로세스 A > 프로세스 B > 프로세스 C

 

프로세스 A가 우선순위가 가장 높기 때문에 실행 중인 상황에서 A는 C가 계산한 값을 받기 위해 C가 실행될 수 있도록 A 스스로 Blocked 상태에 들어가 C에게 기회를 주었다. 하지만, C보다 B의 우선순위가 높기 때문에 B가 CPU를 차지하고 만다. 이러한 상황이 Priority Inversion이다.

 

이것의 해결책은 의외로 단순하다. 프로세스 A가 그냥 Blocked 상태로 빠지는 것이 아닌, 프로세스 C에게 자신의 우선순위를 잠시 위임하고 Blocked 상태로 빠지면 된다. 이러한 Priority Inversion의 해결책은 운영체제마다 다양하다.

---

02. Windows 프로세스 우선순위

Windows는 총 6단계의 우선순위 계층을 제공한다. 숫자가 높을수록 높은 우선순위를 지닌다.

---

참고 자료:

윤성우. 『뇌를 자극하는 윈도우즈 시스템 프로그래밍』.한빛미디어, 2007.