04-1. CPU Scheduling

Introduction¶

핵심 질문 : 스케줄링 정책은 어떻게 개발하는가
스케줄링 정책을 생각하기 위한 기본적인 프레임워크를 어떻게 만들어야 하는가? 핵심
가정은 무엇인가? 어떤 평가 기준이 중요한가? 컴퓨터 시스템의 초창기에 사용되었던
기본 접근법은 무엇인가?

일련의 프로세스들이 실행하는 상황 가정 (Workload assuption)

1. 모든 작업은 같은 시간 동안 실행된다.
2. 모든 작업은 동시에 도착한다.
3. 각 작업은 시작되면 완료될 때까지 실행된다.
4. 모든 작업은 CPU만 사용한다 (= 입출력을 수행하지 않는다).
5. 각 작업의 실행 시간은 사전에 알려져 있다.

• Performance metric: Turnaround time (반환 시간)
  The time at which the job completes minus the time at which the time arrived in the system.

조건 2에서 모든 작업은 동시에 도착한다고 가정했으므로 이다.
이다.

• Another metric is fairness.
  성능과 공정성은 스케줄링에서는 서로 상충되는 목표이다.

스케줄러는 성능을 극대화하기 위해 몇몇 작업의 실행을 중지하며, 결과적으로 공정성이 악화된다.

FIFO, FCFS (First In First Out, 선입선출) 스케줄링¶

혹은 First Come First Served, FCFS, 선도착선처리라고도 한다.

평균 반환시간이 엄청나게 늘어난다.
이 문제점은 convoy efect 라고 칭해지며 짧은 시간 동안 자원을 사용할 프로세스들이 자원을 오랫동안 사용하는 프로세스의 종료를 기다리는 현상을 말한다.

작업 실행 시간이 다른 경우 더 좋은 알고리즘은 무엇일까?

SJF (Shortest Job First, SJF , 최단 작업 우선) 스케줄링¶

모든 작업이 동시에 도착한다면 SJF가 최적(optimal)의 스케줄링 알고리즘이다.
FIFO 알고리즘 최악의 경우 평균 반환시간이 110초였는데 SJF에서는 50초로 평균 반환 시간을 2배 이상 줄였다.

그러나 짧은 작업들이 늦게 도착한 경우, 타이밍이 안맞으면 이전의 convoy 문제가 발생한다.

또한 준비 큐에 먼저 들어왔음에도 불구하고 작업 시간이 길다는 이유로 계속 뒤로 밀리는 아사현상이 발생하는 단점이 있다.

선점형 스케줄러
- 선점형 스케줄링 : 어떤 프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 CPU를 강제로 빼앗을 수 있는 스케줄링 방식
- 비선점형 스케줄링 : 어떤 프로세스가 CPU를 점유하면 다른 프로세스가 이를 빼앗을 수 없는 스케줄링 방식

STCF (Shortest Time-to-Completion First, 최단 잔여시간 우선)¶

SJF 에 선점 기능을 추가한 스케줄러, (PSJF, 선점형 최단 작업 우선)

타이머 인터럽트와 문맥 교환을 고려하면 B와 C가 도착했을 때 스케줄러는 다른 일을 할 수 있다. 작업 A를 중지하고 지금 도착한 B나 C를 실행하기로 결정할 수도 있다. 선점된 A는 나중에 다시 실행된다.
그러나 SJF는 비선점형 스케줄러이기 때문에 이와 같은 동작을 하지 못한다.

이를 개선하기 위해서 STCF 스케줄링 기법이 탄생했다.
이 알고리즘은 남아 있는 작업과 새로운 작업의 잔여 실행 시간을 계산하고 그 중 가장 적은 잔여 실행 시간을 가진 작업을 스케줄한다.

그러나 이 알고리즘은 초기 일괄처리 컴퓨터 시스템에서에만 유효하다.
또한 이 알고리즘은 작업의 길이를 미리 알고 있고, 작업이 오직 CPU만 사용하며, 평가 기준이 반환 시간 하나인 경우에 최적의 상황이다.
시분할 컴퓨터 시스템에서는 응답시간 또한 중요한 평가 기준이다.

응답 시간은 작업이 도착할 때부터 처음 스케줄 될 때까지의 시간으로 정의된다.

예를 들어, 위와 같은 스케줄의 (A는 시간 0, B 와 C는 시간 10에 도착) 경우, 각 작업의 응답 시간은 A는 0, B는 0, C는 10, 평균 3.33이 된다.

다시 말해서, STCF 알고리즘은 반환 시간 기준으로는 매우 훌륭한 반면, 응답 시간과 상호작용 측면에서는 좋지 못하다.

Round-Robin (RR, 라운드 로빈) 스케줄링¶

RR은 작업이 끝날 때까지 기다리지 않고 일정 시간 동안 실행한 후 실행 큐의 다음 작업으로 전환한다.
한 프로세스가 타임 슬라이스 동안 작업하다가 작업 완료 못 할 시 준비 큐의 맨 뒤로가서 차례 기다린다.

이때 작업이 실행되는 일정 시간을 타임 슬라이스(time slice) 또는 스케줄링 퀀텀(scheduling quantum) 이라 부른다. 작업이 완료될 때까지 이런 식으로 계속 진행된다. 이러한 이유로 RR은 때때로 타임 슬라이싱이라고 불린다. 타임 슬라이스의 길이는 타이머 인터럽트 주기의 배수여야 한다.
타이머가 10 msec 마다 인터럽트를 발생시킨다면 타임 슬라이스는 10, 20 등 10 msec의 배수가 될 수 있다.

타임 슬라이스의 길이는 RR에게 매우 중요하다. 타임 슬라이스가 짧을수록, 응답 시간 기준으로 RR의 성능은 더 좋아진다. 그러나 타임 슬라이스를 너무 짧게 지정하면 문제가 생긴다.
짧게 지정하면 문맥 교환 비용이 전체 성능에 큰 영향을 미치게 된다. (오버 헤드 발생)

문맥 교환 비용에는 레지스터를 저장/복원, CPU 캐시, TLB, 분기 예측 등을 비롯하여 다른 하드웨어에도 프로그램과 관련된 다양한 작업 정보들이 저장되어 있다. 작업이 전환되면 이 정보들은 모두 갱신되어야 한다.
갱신 작업은 매우 큰 성능 비용을 유발한다.

너무 클 경우 반응 속도 느려짐
너무 작을 경우 전반적인 성능 떨어짐

그러나 이 알고리즘은 응답 시간을 최적화하지만 반환 시간이 나쁘다.

Recall) 일련의 프로세스들이 실행하는 상황 가정 (Workload assuption)

1. 모든 작업은 같은 시간 동안 실행된다.
2. 모든 작업은 동시에 도착한다.
3. 각 작업은 시작되면 완료될 때까지 실행된다.
4. 모든 작업은 CPU만 사용한다 (= 입출력을 수행하지 않는다).
5. 각 작업의 실행 시간은 사전에 알려져 있다.

4, 5번 가정에 대해서도 생각해보아야한다.

입출력 연산 고려¶

가정 4 완화

입출력 작업을 요청한 경우:
스케줄러는 다음에 어떤 작업을 실행할지를 결정한다
(현재 실행 중인 작업은 입출력이 완료될 때까지 CPU를 사용하지 않는다.)

입출력 요청을 발생시킨 작업은 입출력 완료를 기다리며 대기 상태가 된다.
입출력이 하드 디스크 드라이브에 보내진 경우, 프로세스는 드라이브의 현재 입출력 워크로드에 따라 몇 초 또는 좀 더 긴 시간 동안 블록될 것이다. 스케줄러는 그 시간 동안 실행될 다른 작업을 스케줄 해야 한다.

스케줄러는 입출력 완료 시에도 의사 결정을 해야 한다. 입출력이 완료되면 인터럽트가 발생하고 운영체제가 실행되어 입출력을 요청한 프로세스를 대기 상태에서 준비 상태로 다시 이동시킨다.

물론, 인터럽트가 발생했을 때 요청 프로세스를 즉시 실행시키기로 결정할 수도 있다.

두 개의 작업 A와 B가 있다고 하자. 각 작업은 50 msec의 CPU 시간을 필요로 한다.

그러나 둘은 한 가지 큰 차이를 가진다. A는 10 msec 동안 실행된 후, 입출력 요청을 한다 (여기서 입출력 시간은 10 msec라고 가정한다). 반면에 B는 입출력을 수행하지 않는다. 스케줄러는 A를 먼저 실행시키고 B를 다음에 실행시킨다 (그림 10.8).

STCF 스케줄러를 구축하려고 한다고 가정하자. A가 5개의 10 msec 작업으로 분할되는 반면에 B는 하나의 50 msec의 CPU를 요청한다는 사실을 어떻게 활용할까?

분명히 입출력을 고려하지 않고 작업을 하나씩 실행시키는 것은 의미가 없다.

일반적인 접근 방식은 A의 각 10 msec 하위 작업을 독립적인 작업으로 다루는 것이다. 시스템이 시작할 때 10 msec 작업들과 50 msec를 스케줄하는 것이다. STCF의 경우 가장 짧은 작업을 선택해서 처리한다.

이 경우에는 A가 된다. 그러면 A의 첫 번째 소 작업이 완료되면 B만 남게 되어 실행을 시작한다. A의 다음 작업이 제출되고 B를 선점하여 10 msec 동안 실행한다. 이렇게 하면 프로세스의 입출력이 끝나기를 기다리는 동안 CPU는 다른 프로세스에 의해 사용되어 연산의 중첩이 가능해진다. (그림 10.9).

정리¶

입출력을 고려한 스케줄러 방법에 대해서 알아보았다. 각 CPU 버스트를 하나의 작업으로 간주함으로써 스케줄러는 대화형 프로세스가 더 자주, 즉 유리하게 실행되는 것을 보장한다. 이러한 대화형 작업이 입출력을 실행하는 동안 다른 CPU-집중 작업들이 실행되고 CPU의 이용률은 더 높아진다.

스케줄러가 각 작업의 실행 시간을 알고 있다는 가정은 가장 비현실적이다.
사실 범용 운영체제에서 (우리가 현재 고려 중인 것과 같은) 작업의 길이에 대해서 알 수 있는 길은 없다.

최종적으로 생각해봐야 할 것:

1. 아무런 사전 지식 없이 SJF/STCF 처럼 행동하는 알고리즘을 구축할 수 있을까?
   → 남아 있는 작업 중 실행 시간이 제일 짧은 작업을 수행하고, 반환 시간을 최소화한다.
2. 응답 시간도 좋게 하기 위하여 RR 스케줄러의 경우에 보았던 아이디어(시분할)를 어떻게 하면 포함시킬 수 있을까?
   → 모든 작업을 번갈아 실행시키고 응답 시간을 최소화한다.

그러나 반환 시간과 응답 시간 중 하나를 최적화하면 나머지 하나는 좋지 않은 특성을 나타낸다.
이는 시스템에서 흔히 보이는 절충을 요구하는 상황이다. (Trade-off)

그렇지만 미래를 예측할 수 없는 운영체제의 근본적인 문제는 해결할 수 없었다.

이를 해결하기 위해 멀티 레벨 피드백 큐(multi-level feedback queue)라는 기법이 생겼다. 이 방법은 가까운 과거를 이용하여 미래를 예측하는 스케줄러다. 다음 장에서 살펴보기로 한다.