[OS] 선입 선처리(FIFO) 스케줄링(Scheduling) 이란?

FIFO (First In First Out) 스케줄링이란?

FIFO 스케줄링 방식은 스케줄링 기법중 가장 간단한 방법으로 자료구조 큐(Queue)와 같은 원리를 가진 스케줄링 기법이다.

자료구조 큐의 원리는 처음 들어온 작업이 먼저 실행 되는 구조이며 FIFO 스케줄링 기법도 마찬가지로, 들어온 작업이 어떤 것이든 먼저 들어온 작업이 먼저 수행되고 해당 작업이 모두 끝난 후에 뒤에 들어온 작업이 수행된다.

 

예시를 통해서 FIFO 스케줄링 기법을 이해해보자.

 

해당 프로세스는 다음과 같은 특징을 가지고 있다.

• A,B,C 3개의 프로세스는 모두 0초에 동시에 도착했다.
• 동시에 도착한 프로세스가 있다면 알파벳 순서대로 CPU를 할당 받아 작업을 수행한다.

다음과 같은 특징을 가지는 3개의 프로세스가 존재할 때 FIFO 스케줄링 흐름은 다음과 같다.

• 알파벳 순서가 제일 빠른 A가 0초에 CPU를 할당 받아 10만큼 일을 수행한다.
• 10초 뒤에 다음 순서인 B가 10만큼 일을 수행하여 20초에 종료한다.
• 마지막으로 C가 CPU를 할당 받아 10만큼 일을 수행 후 30초 시점에서 일을 종료한다.

위 그림을 토대로 반환 시간, 대기 시간을 구해보면 다음과 같다.

• 반환 시간(turnaround time) : 프로세스가 시작해서 끝날 때까지 걸리는 시간 (완료 시간 - 도착 시간)
• 대기 시간(waiting time) : 프로세스가 준비 상태에서 대기한 시간 (시작 시간 - 도착 시간)

	대기 시간	반환 시간	도착 시간
A	0	10	0
B	10	20	0
C	20	30	0

위 표를 이용하여 평균 반환시간, 평균 대기시간을 구하면 다음과 같다.

• 평균 반환시간 : (10 + 20 + 30) / 3 = 20
• 평균 대기시간 : (0 + 10 + 20) / 3 = 10

위 예제로만 보면 평균 반환시간과 평균 대기시간 모두 그다지 길지 않은 것을 확인할 수 있지만, 프로세스의 작업량이 동일하지 않은 경우에는 FIFO 스케줄링 기법이 매우 비효율적인 경우가 될 수 있다. 예시로 살펴보자.

 

해당 프로세스는 다음과 같은 특징을 가지고 있다.

• A,B,C 3개의 프로세스는 모두 0초에 동시에 도착했다.
• 동시에 도착한 프로세스가 있다면 알파벳 순서대로 CPU를 할당 받아 작업을 수행한다.

다음과 같은 특징을 가지는 3개의 프로세스가 존재할 때 FIFO 스케줄링 흐름은 다음과 같다.

• 알파벳 순서가 제일 빠른 A가 0초에 CPU를 할당 받아 100만큼 일을 수행한다.
• 100초 뒤에 다음 순서인 B가 10만큼 일을 수행하여 110초에 종료한다.
• 마지막으로 C가 CPU를 할당 받아 10만큼 일을 수행 후 120초 시점에서 일을 종료한다.

위 그림을 토대로 반환 시간, 대기 시간을 구해보면 다음과 같다.

	대기 시간	반환 시간	도착 시간
A	0	100	0
B	100	110	0
C	110	120	0

위 표를 이용하여 평균 반환시간, 평균 대기시간을 구하면 다음과 같다.

• 평균 반환시간 : (100 + 110 + 120) / 3 = 110
• 평균 대기시간 : (0 + 100 + 110) / 3 = 70

이처럼 FIFO 스케줄링 기법은 시간이 많이 소요되는 작업이 먼저 수행되는 경우 빨리 끝날 수 있는 작업들이 먼저 처리되지 못한다는 단점이 있다. 이러한 단점을 Convoy Effect라고 부른다.

• Convoy Effect : 작업 시간이 긴 프로세스가 먼저 수행되어 시간을 잡아먹기 때문에 작업 시간이 짧은 프로세스가 수행하지 못하는 현상을 일컫는다.
• 위의 경우 B,C 프로세스는 작업 시간이 짧아 먼저 수행되는 것이 좋은 방법이지만 프로세스 A 때문에 시간을 낭비하고 있다.