스케줄링: 개요

스케줄링: 개요#

이제 프로세스를 실행하기 위해 필요한 문맥 교환(Context Switch)과 같은 저수준 기술에 대해 명확히 이해하고 있어야 합니다. 만약 이러한 기술들의 동작 방식에 대해 잘 모르겠다면, 앞서 배운 내용을 다시 복습하는 것이 좋습니다. 또한, 운영체제 스케줄러의 고수준 정책에 대한 이해도 필요합니다.

지금부터는 다양한 스케줄링 정책(Scheduling Policy)을 소개하고, 이에 대한 이해를 높이는 데 집중하겠습니다. 이러한 정책은 스케줄링 기법(Scheduling Discipline)이라고도 불리며, 많은 優秀하고 부지런한 연구자들이 오랜 시간 동안 개발해 온 것들입니다.

사실, 스케줄링의 기원은 컴퓨터 시스템이 개발되기 이전으로 거슬러 올라갑니다. 초기의 스케줄링 방법들은 생산 관리(Production Management) 분야에서 개발되었고, 이후 컴퓨터 시스템에 적용되었습니다. 이는 그리 놀라운 일이 아닙니다. 생산 공정과 인간의 다양한 활동에서도 스케줄링이 필요하고, 효율성 향상과 같은 공통된 목표를 가지고 있기 때문입니다.

우리가 해결해야 할 핵심 질문은 다음과 같습니다.

1. 스케줄링 정책은 어떻게 개발할 수 있을까요?
2. 스케줄링 정책을 설계하기 위한 기본적인 프레임워크는 무엇일까요?
3. 정책 개발에 필요한 핵심 가정은 무엇일까요?
4. 어떤 평가 기준이 중요할까요?
5. 컴퓨터 시스템 초창기에 사용된 기본 접근 방식은 무엇일까요?

이러한 질문에 대한 답을 찾아가면서, 스케줄링 정책의 개발 과정과 그 기반이 되는 개념들을 이해할 수 있을 것입니다. 이를 통해 운영체제의 스케줄링 메커니즘에 대한 포괄적인 지식을 갖추게 될 것입니다.

워크로드에 대한 가정[1]#

스케줄링 정책을 개발하기에 앞서, 우리는 프로세스에 대해 몇 가지 가정을 해야 합니다. 이러한 가정들은 시스템에서 실행되는 프로세스들의 집합인 워크로드(Workload)를 정의하는 데 도움을 줍니다. 워크로드에 대해 잘 이해할수록 그에 맞는 최적의 스케줄링 정책을 설계할 수 있습니다.

우리는 시스템에서 실행 중인 프로세스 또는 작업에 대해 다음과 같은 가정을 합니다.

1. 모든 작업의 실행 시간은 동일합니다.

   - 예를 들어, 모든 작업이 정확히 10초 동안 실행된다고 가정합니다.

2. 모든 작업은 동시에 시스템에 도착합니다.

   - 즉, 모든 작업이 시작 시점에 한꺼번에 도착한다는 것입니다.

3. 각 작업은 한 번 시작되면 중간에 중단되지 않고 완료될 때까지 실행됩니다.

   - 작업이 실행되는 동안 다른 작업으로 전환되지 않습니다.

4. 모든 작업은 오직 CPU 자원만 사용합니다.

   - 작업 실행 중에는 입출력(I/O) 작업이 발생하지 않는다고 가정합니다.

5. 각 작업의 실행 시간은 스케줄러가 미리 알고 있습니다.
   - 스케줄러는 작업의 실행 시간을 사전에 파악하고 있다고 가정합니다.

하지만 이러한 가정들은 현실 세계와는 거리가 멉니다. 특히 작업의 실행 시간을 미리 알고 있다는 가정은 매우 비현실적입니다. 이는 마치 스케줄러가 모든 것을 알고 있다고 가정하는 것과 같습니다.

이러한 가정들은 스케줄링 정책을 단순화하여 이해하기 쉽게 만들어 주지만, 실제 시스템에 적용할 때는 현실적인 제약 사항들을 고려해야 합니다. 그럼에도 불구하고, 이 가정들은 스케줄링 정책의 기본 개념을 이해하는 데 도움을 줍니다.

스케줄링 평가 항목#

스케줄링 알고리즘을 평가하기 위해서는 워크로드에 대한 가정뿐만 아니라 평가 기준도 정해야 합니다. 스케줄링 분야에서는 다양한 평가 기준이 사용되지만, 여기서는 간단히 반환 시간(turnaround time)이라는 하나의 척도만 살펴보겠습니다.

반환 시간이란 어떤 작업이 시스템에 도착한 시점부터 완료되는 시점까지 걸린 총 시간을 말합니다. 수식으로 표현하면 다음과 같습니다.

\(T_{turnaround} = T_{completion} - T_{arrival}\)

여기서 \(T_{turnaround}\)은 반환 시간, \(T_{completion}\)은 작업 완료 시각, \(T_{arrival}\)은 작업 도착 시각입니다.

지금은 모든 작업이 동시에 도착한다고 가정하므로 \(T_{arrival} = 0\)이라 할 수 있습니다. 따라서 반환 시간은 곧 작업 완료 시각과 같아집니다. 나중에는 이 가정을 완화해 나가도록 하겠습니다.

반환 시간은 시스템의 성능 측면에서 본 척도라는 점에 주목할 필요가 있습니다. 또 다른 중요한 기준으로는 공정성(fairness)이 있는데, 이는 Jain’s Fairness Index와 같은 지표로 측정될 수 있습니다.

스케줄링에서 성능과 공정성은 종종 상충되는 목표가 됩니다. 예를 들어 스케줄러가 시스템 성능을 극대화하기 위해 일부 작업을 오랫동안 미루게 되면, 그만큼 공정성은 나빠지게 됩니다. 안타깝게도 우리 삶의 많은 부분이 그렇듯 모든 것을 다 잡기란 쉽지 않습니다.

선입선출[2]#

선입선출(First-Come, First-Served)은 가장 간단한 스케줄링 알고리즘 중 하나입니다. 이 알고리즘은 작업이 도착한 순서대로 실행되는 방식으로, 먼저 도착한 작업이 먼저 실행되고, 그 다음으로 도착한 작업이 실행됩니다.

../_images/fcfs.png

선입선출 스케줄링은 비선점형 스케줄링이므로 프로세스가 자발적으로 CPU를 반납할 때 까지 CPU를 빼앗지 않습니다.

비선점형 스케줄링

실행 중인 프로세스가 CPU를 점유하고 있을 때 다른 프로세스가 CPU를 빼앗을 수 없는 방식입니다.

예를 들어, 실행 중인 프로세스가 입출력 작업을 요청하거나 종료될 때까지 CPU를 계속 사용합니다. 이렇게 하면, 프로세스의 교체가 적게 일어나서 오버헤드가 줄고, 실행 순서가 예측하기 쉽습니다. 하지만 긴 작업이 CPU를 오랫동안 점유하면 다른 작업들이 오래 기다려야 합니다.

비전형 스케줄링의 예로는 선입선출(FIFO), 최단 작업 우선 스케줄링(SJF) 등이 있습니다.

예를 들어, 프로세스 A, B, C가 각각 3초, 5초, 2초의 서비스 시간을 가지고 있고, A가 먼저 도착하고 B가 그 다음에 도착하고 C가 마지막에 도착한다면, FCFS 스케줄링은 다음과 같은 순서로 프로세스를 실행합니다.

프로세스

서비스 시간

대기 시간

응답 시간

반환 시간

A

3초

0초

0초

3초

B

5초

3초

3초

8초

C

2초

8초

8초

10초

이렇게 되면 평균 대기 시간은 (0 + 3 + 8) / 3 = 3.67초, 평균 응답 시간은 (0 + 3 + 8) / 3 = 3.67초, 평균 반환 시간은 (3 + 8 + 10) / 3 = 7초가 됩니다.

장점#

  • 구현이 쉽습니다.

  • 선착순으로 처리하기 때문에 프로세스를 공평하게 처리할 수 있습니다.

단점#

  • 짧은 작업이 긴 작업보다 늦게 도착하면 긴 작업을 기다려야 하므로 평균 대기 시간이 증가할 수 있습니다. 이를 호위 효과(convoy effect)라고 합니다.

  • FCFS 스케줄링은 비선점형(nonpreemptive) 방식이므로 한 프로세스가 CPU를 점유하고 있으면 다른 프로세스는 CPU를 빼앗을 수 없습니다. 이는 CPU 사용률을 낮추고 I/O 바운드 프로세스의 대기 시간을 증가시킬 수 있습니다.

최단 작업 우선[3]#

이 문제는 ‘최단 작업 우선(Shortest Job First, SJF)’ 스케줄링 기법을 적용하면 쉽게 해결할 수 있습니다. SJF는 이름 그대로 실행 시간이 가장 짧은 작업을 가장 먼저 처리하는 방식인데, 사실 이 아이디어는 원래 운영 연구(Operations Research) 분야에서 유래한 것을 컴퓨터 시스템의 작업 스케줄링에 적용한 것입니다.

모든 작업이 동시에 도착한다는 가정 하에서는 SJF가 최적(optimal)의 스케줄링 알고리즘임을 증명할 수 있습니다. 하지만 지금은 이론이나 운영 연구 수업이 아닌 시스템 수업이므로 증명은 생략하겠습니다.

그런데 SJF라는 훌륭한 기법을 고안했음에도 불구하고, 앞서 세운 가정은 여전히 비현실적입니다.

이 가정을 좀 더 현실에 가깝게 완화해 보기 위해, 다음과 같은 상황을 생각해 봅시다. 작업 A는 시간 0에 도착하고 실행 시간이 100초인 반면, 작업 B와 C는 시간 10에 도착하고 실행 시간은 각각 10초라고 합니다.

순수한 SJF 스케줄링을 적용하면, B와 C가 A 바로 뒤인 시간 10에 도착함에도 불구하고 A가 끝날 때까지 기다려야만 합니다. 이렇게 되면 이전에 봤던 호위 효과(convoy effect) 문제가 다시 발생하게 됩니다.

이 경우 평균 반환 시간은 다음과 같이 계산됩니다.

\(\frac{100 + (110 - 10) + (120 - 10)}{3} = 103.33\)

즉, \((100 + 100 + 110) / 3 = 103.33\)이 됩니다.

최소 잔여시간 우선#

이 문제를 해결하기 위해 ‘최소 잔여시간 우선(Shortest Time-to-Completion First, STCF)’ 스케줄링 기법을 적용해 보겠습니다. 이 기법은 SJF를 조금 변형한 것인데, 작업의 총 실행 시간이 아니라 남아있는 실행 시간, 즉 잔여 실행 시간을 기준으로 삼는다는 점이 다릅니다.

STCF에서는 새로운 작업이 시스템에 도착할 때마다 현재 실행 중인 작업의 잔여 실행 시간과 새 작업의 실행 시간을 비교합니다. 그리고 그 중 가장 짧은 잔여 실행 시간을 가진 작업을 선택하여 실행합니다. 필요하다면 현재 작업을 선점(preemption)하고 새 작업에게 CPU를 할당하는 것이죠.

앞서 예시로 든 시나리오에서 STCF를 적용해 보면, 작업 A가 시작된 후 10초 시점에 B와 C가 도착했을 때, 스케줄러는 A를 선점하고 B 또는 C를 먼저 실행할 것입니다. B와 C는 실행 시간이 각각 10초로 동일하므로 둘 중 어느 것을 먼저 실행해도 상관없습니다. B와 C가 모두 끝난 후에야 비로소 A가 다시 스케줄되어 남은 시간 동안 실행을 이어나가게 됩니다.

모든 작업이 동시에 도착하는 특별한 경우에는 SJF가 최적의 스케줄을 보장한다는 사실을 떠올려 봅시다. 그렇다면 작업들이 서로 다른 시간에 도착하는 일반적인 상황에서는 STCF가 최적이 될 것이라는 점을 직관적으로 이해할 수 있을 것입니다. STCF는 새 작업이 도착할 때마다 잔여 작업량을 재평가하여 그때그때 가장 적절한 프로세스를 선택하기 때문입니다.

새로운 평가 기준 : 응답 시간#

STCF는 작업의 실행 시간을 미리 알고, CPU만을 사용하며, 반환 시간이라는 단일 평가 기준을 가정할 때는 매우 효과적인 스케줄링 정책입니다. 초기의 일괄 처리(batch processing) 시스템에서는 이런 알고리즘이 적절했습니다. 그러나 시분할(time-sharing) 시스템의 등장으로 상황이 달라졌습니다.

이제 사용자들은 터미널을 통해 컴퓨터와 상호작용하게 되었고, 이에 따라 시스템의 응답성(responsiveness)이 중요한 성능 지표로 부상했습니다. 이를 반영하기 위해 ‘응답 시간(response time)’이라는 새로운 평가 기준이 도입되었는데, 이는 작업이 도착한 시점부터 실제로 처음 실행되기 시작할 때까지 걸린 시간을 말합니다.

예를 들어 세 개의 작업 A, B, C가 동시에 도착했다고 합시다. STCF 스케줄링을 적용하면 실행 시간이 가장 긴 작업, 가령 C는 나머지 두 작업이 모두 끝날 때까지 기다려야 비로소 CPU를 할당받을 수 있습니다. 반환 시간 측면에서는 최적일 수 있지만, 응답 시간 측면에서 보면 형편없는 결과라 할 수 있겠죠.

사용자와의 상호작용이 중요해진 상황에서 STCF는 더이상 적절한 스케줄링 기법이 아닙니다. 응답 시간을 개선하면서도 시스템의 전반적인 성능을 높일 수 있는 새로운 스케줄링 알고리즘이 필요해진 것입니다.

라운드 로빈#

응답 시간 문제를 해결하기 위해 ‘라운드 로빈(Round Robin, RR)’ 스케줄링이라는 새로운 알고리즘이 도입되었습니다.

RR에서는 각 작업이 완료될 때까지 기다리지 않고, 대신 정해진 시간 동안만 실행한 후 다음 작업으로 전환합니다. 이때 각 작업에 할당되는 실행 시간을 ‘타임 슬라이스(time slice, ts)’ 또는 ‘스케줄링 퀀텀(scheduling quantum, sq)’이라고 부릅니다. 이 과정은 모든 작업이 끝날 때까지 계속 반복되는데, 이런 특성 때문에 RR을 ‘타임 슬라이싱(time slicing)’이라고도 합니다.

타임 슬라이스의 길이는 타이머 인터럽트 주기의 배수로 설정해야 합니다. 예를 들어 타이머 인터럽트가 10밀리초(msec)마다 발생한다면, 타임 슬라이스는 10, 20, 30 등 10의 배수로 정해질 수 있습니다.

RR 스케줄링에서 타임 슬라이스의 길이는 매우 중요한 요소입니다. 일반적으로 타임 슬라이스가 짧을수록 응답 시간 측면에서의 성능은 좋아집니다. 그러나 너무 짧게 설정하면 문맥 교환(context switch) 오버헤드가 전체 성능에 부정적인 영향을 미칠 수 있습니다.

따라서 시스템 설계자는 문맥 교환에 드는 비용과 응답 시간 개선 효과를 고려하여 최적의 타임 슬라이스 길이를 결정해야 합니다. 이는 해당 시스템의 특성과 워크로드에 따라 달라질 수 있는 중요한 튜닝 포인트 중 하나입니다.

입출력 연산의 고려#

지금까지는 CPU 작업만 고려했지만, 실제 시스템에서는 입출력(I/O) 작업도 빈번하게 발생합니다. 이는 스케줄링에 또 다른 도전 과제를 제기합니다.

어떤 프로세스가 I/O 작업을 요청하면, 그 프로세스는 I/O가 완료될 때까지 CPU를 사용하지 않습니다. 대신 I/O 작업이 끝나기를 기다리면서 ‘대기(blocked)’ 상태로 전환됩니다. 특히 하드 디스크 드라이브 같은 장치에 I/O 요청을 보냈다면, 현재의 I/O 부하에 따라 몇 초 또는 그 이상 블록 상태로 남아있게 됩니다.

이때 스케줄러의 역할은 블록된 프로세스 대신 실행할 다른 프로세스를 선택하는 것입니다. 이를 통해 CPU가 쉬지 않고 일할 수 있도록 해야 하죠.

반대로, I/O 작업이 완료되면 스케줄러는 또 다른 결정을 내려야 합니다. I/O 완료는 인터럽트를 발생시키고, 이를 처리하기 위해 운영체제가 실행됩니다. 운영체제는 I/O를 요청했던 프로세스를 대기 상태에서 준비(ready) 상태로 전환시킵니다. 여기서 스케줄러는 해당 프로세스를 바로 실행할 것인지, 아니면 다른 프로세스에게 CPU를 할당할 것인지 결정합니다.

이렇듯 I/O 작업은 스케줄링 문제를 더욱 복잡하게 만듭니다. 스케줄러는 CPU 사용 패턴뿐만 아니라 I/O 특성까지 고려하여 적절한 프로세스를 선택해야 합니다. 이를 통해 전체 시스템의 CPU 활용도와 응답성을 높이는 것이 목표입니다.

만병통치약은 없다 (No More Oracle)#

이제 입출력을 고려한 기본적인 스케줄링 접근 방식에 대해 살펴보았으니, 마지막으로 남은 가정에 대해 생각해 봅시다. 바로 스케줄러가 각 작업의 실행 시간을 미리 알고 있다는 가정인데, 앞서 언급했듯이 이는 아마도 우리가 할 수 있는 가정 중 가장 비현실적인 것일 겁니다.

사실 범용 운영체제에서는 개별 작업의 실행 시간을 정확히 예측하는 것이 거의 불가능합니다. 프로세스의 행동은 입력 데이터, 사용자 상호작용, 외부 이벤트 등 다양한 요인에 따라 달라지기 때문이죠.

그렇다면 작업의 실행 시간에 대한 사전 지식 없이도 SJF나 STCF처럼 동작하는 스케줄링 알고리즘을 만들 수 있을까요? 나아가 이런 알고리즘에 라운드 로빈에서 봤던 것처럼 응답 시간을 개선하는 아이디어도 접목시킬 수 있을까요?

안타깝게도 이 모든 조건을 완벽히 만족시키는 만병통치약 같은 솔루션은 존재하지 않습니다. 스케줄러가 완벽한 정보를 가질 수 없는 상황에서는 어떤 알고리즘을 사용하더라도 트레이드오프가 발생할 수밖에 없습니다.

하지만 현대의 스케줄러들은 과거의 실행 이력, 휴리스틱, 피드백 등을 활용하여 이 문제에 대한 나름의 해법을 모색하고 있습니다. 비록 최적解는 아닐지라도, 주어진 환경에서 최선의 성능을 끌어내기 위해 노력하고 있는 것이죠. 다음 장에서는 이런 아이디어들을 적용한 몇 가지 실제 스케줄링 알고리즘을 소개하도록 하겠습니다.

요약#

이번 장에서는 스케줄링의 기본 개념과 두 가지 주요 접근 방식에 대해 알아보았습니다.

첫 번째 접근법은 SJF(Shortest Job First)와 STCF(Shortest Time-to-Completion First)로 대표되는데, 남은 작업들 중 실행 시간이 가장 짧은 것을 우선적으로 처리함으로써 전체 반환 시간(turnaround time)을 최소화하는 것이 목표입니다.

두 번째 접근법은 라운드 로빈(Round Robin) 스케줄링으로, 모든 작업에게 동등한 CPU 시간을 할당하고 순환하며 실행함으로써 응답 시간(response time)을 최소화하고자 합니다.

그러나 안타깝게도 이 두 가지 목표, 즉 반환 시간과 응답 시간은 상호 보완적인 관계에 있습니다. 하나를 최적화하면 다른 하나는 희생될 수밖에 없는 것이죠. 이는 시스템 설계에서 흔히 마주치는 트레이드오프(trade-off) 상황의 전형적인 예라 할 수 있습니다.

우리는 또한 입출력(I/O) 작업이 스케줄링에 미치는 영향에 대해서도 살펴보았습니다. I/O bound 프로세스와 CPU bound 프로세스를 적절히 섞어 스케줄링하는 것이 전체 시스템 성능에 중요한 요소임을 확인했습니다.

하지만 운영체제가 개별 프로세스의 실행 시간을 정확히 예측할 수 없다는 근본적인 한계는 여전히 남아 있습니다. 결국 완벽한 스케줄링 알고리즘이란 존재하기 힘들며, 주어진 상황에서 최선의 trade-off를 찾아내는 것이 관건이라 할 수 있겠습니다.

Contents