CPU Scheduling 기법

Scheduling 기준

CPU Scheduling은 크게 두 가지를 고려하여야 한다.

첫 번째, 공평함이다. 하나의 프로세스만 수행되는 것을 막고 모든 프로세스가 사용할 수 있도록 하여야 한다.

두 번째, 성능이다. 공평하게 수행하는 것 뿐만 아니라 가장 적은 시간 안에 수행해야 한다.

따라서 우리는 작업이 도착한 시간부터 시작까지 걸린 시간(Response Time)과 완료까지 걸린 시간(Turnaround Time)을 기준으로 각각의 기법들을 평가한다.

 

 

1. First In, First Out (FIFO)

선입선출 방식, 먼저 들어온 작업이 먼저 수행되는 방식으로 가장 기본적으로 생각할 수 있는 방식이다.

하지만 아래와 같은 경우를 보자.

첫 번째로 들어온 작업이 큰 작업일 경우 10초면 끝날 작업인 B, C는 아주 오랜 시간동안 기다려야 하는 문제가 있다.

 

 

2. Shortest Job First (SJF)

같은 시간에 들어온 작업 중 실행시간이 가장 짧은 작업 먼저 수행하는 방법이다.

FIFO 방식과 달리 수행시간이 짧은 B,C가 먼저 수행되어 평균 Turnaround Time을 줄일 수 있다.

하지만 이 방식도 문제가 있다.

A, B, C가 동시에 도착하지 않고 B, C가 조금이라도 늦게 도착할 경우, A가 먼저 실행되기 때문이다.

 

 

3. Shortest Time-to-Completion First (STCF)

SJF와 달리 이 방식은 B, C가 도착하면 그 즉시 작업을 멈추고 남은 수행시간이 가장 작은 작업부터 수행한다.

이렇게 되면 B, C가 늦게 도착하더라도 효율적으로 수행하여 Turnaround Time을 줄일 수 있다.

그렇다면 Response Time을 줄이려면 어떻게 해야 할까?

 

 

4. Round Robin(RR) Scheduling

Round Robin 방식은 작업을 Time Slice로 나누어 수행하는 방식이다.

위와 같이 1초 단위로 나누어 작업을 수행하면 평균 응답시간을 줄일 수 있다.

하지만 이 방식은 응답시간을 줄일 수는 있지만 평균 수행시간은 기존보다 증가한다.

 

※ RR 방식은 Time Slice의 크기가 매우 중요하다. Time Slice를 작게 하면 응답시간은 감소하지만 Context Switch 비용 또한 증가하게 된다. 반면 Time Slice를 크게 하면 Context Switch 비용은 아낄 수 있지만 응답시간은 증가한다.

 

 

Multi-Level Feedback Queue

MLFQ는 각 작업에 우선순위를 부여하여 수행하기 위해 만든 자료구조이다.

아래는 우선순위를 정하기 위한 규칙과 실행 규칙이다.

 

1. 우선순위가 높은 작업부터 수행한다.

2. 우선순위가 같다면 RR방식으로 수행한다.

3. 작업이 처음 들어오면 가장 높은 우선순위를 갖는다.

4-a. 작업이 Time Slice만큼 실행되고 나면 우선순위가 하락한다.

4-b. 만약 Time Slice만큼 실행되기 전에 작업을 멈춘다면 우선순위를 유지한다.

5. 일정 시간이 지나면 모든 작업을 가장 높은 우선순위로 올린다.

 

※ 우선순위가 낮을 수록 Time Slice는 커진다.

※ I/O Bound 작업은 Response Time이 중요하므로 우선순위를 높이고,

   CPU Bound 작업은 Turnaround Time이 중요하므로 우선순위를 낮춘다.