FCFS 스케줄링

FCFS 스케줄링(First Come First Served, 선입선처리, FIFO 스케줄링)은 준비 큐에 먼저 도착한 프로세스에게 먼저 CPU 를 주고, 그 프로세스가 끝나거나 스스로 CPU 를 내놓을 때까지 빼앗지 않는 비선점 프로세스 스케줄링 기법이다.

개요

준비 큐를 단순한 FIFO 큐로 두고 맨 앞의 프로세스를 실행하는, 가장 단순한 CPU 스케줄링이다. 은행 창구에 줄 선 순서대로 처리하는 것과 같다. 구현이 쉽고 도착 순서대로 처리하므로 공정해 보이며 기아 현상도 없다. 그러나 평균 대기 시간이 도착 순서에 크게 좌우되고, 대화형 시스템에서는 응답 시간이 길어진다.

호위 효과

실행 시간이 긴 프로세스가 먼저 오면 뒤의 짧은 프로세스들이 모두 오래 기다린다. 이를 호위 효과(convoy effect)라 한다.

P1(실행 24), P2(3), P3(3)이 동시에 도착했을 때

• P1, P2, P3 순서 - 대기 시간 0, 24, 27, 평균 (0 + 24 + 27) / 3 = 17
• P2, P3, P1 순서 - 대기 시간 0, 3, 6, 평균 (0 + 3 + 6) / 3 = 3

같은 작업이라도 순서만으로 평균 대기 시간이 다섯 배 넘게 차이 난다. 짧은 작업을 먼저 하면 평균 대기 시간이 가장 작아진다는 것이 SJF 스케줄링의 출발점이다.

라운드 로빈과의 관계

라운드 로빈(RR)은 FCFS 의 도착 순서를 그대로 쓰되 시간 할당량(time quantum)마다 CPU 를 빼앗아 큐의 맨 뒤로 보낸다. 할당량이 커질수록 할당량 안에 끝나는 프로세스가 늘어 선점이 거의 일어나지 않으므로, 시간 할당량이 무한히 커지면 RR 은 FCFS 와 같아진다. 반대로 할당량이 너무 작으면 문맥 교환이 잦아져 오버헤드가 커진다.

다른 스케줄링과 구별하기

기법	선점	고르는 기준	특징
FCFS	비선점	도착 순서	단순, 호위 효과
SJF	비선점	실행 시간이 짧은 것	평균 대기 시간 최소, 긴 작업 기아
HRRN	비선점	(대기 시간 + 실행 시간) / 실행 시간 이 큰 것	오래 기다린 긴 작업도 순위가 올라 기아 완화
SRT(SRTF)	선점	남은 실행 시간이 짧은 것	SJF 의 선점형
라운드 로빈	선점	도착 순서 + 시간 할당량	할당량 무한대면 FCFS

같이 보기

• 프로세스 스케줄링
• 비선점 스케줄링
• 라운드 로빈
• SJF 스케줄링
• 디스크 스케줄링