[알고리즘]스케줄링 알고리즘 (FCFS, SJF, RR)

 

스케줄링 알고리즘은 운영 체제에서 프로세스에게 CPU를 할당하는 방식을 결정하는 알고리즘입니다.

다양한 스케줄링 알고리즘이 존재하지만,

가장 기본적인 세 가지 알고리즘인

FCFS(First-Come, First-Served), SJF(Shortest Job First), RR(Round Robin) 알고리즘에 대해 알아보겠습니다.

 

 

FCFS(First-Come, First-Served)

FCFS 알고리즘은 가장 간단한 스케줄링 알고리즘으로, 프로세스가 도착한 순서대로 CPU를 할당하는 방식입니다.

즉, 선입선출(First-Come, First-Served) 방식으로 CPU를 할당합니다.

이 알고리즘은 대화식 작업에 적합하지 않으며, 프로세스의 실행 시간이 긴 경우에는 평균 대기 시간이 길어지는 단점이 있습니다.

 

SJF(Shortest Job First)

SJF 알고리즘은 프로세스의 실행 시간이 짧은 것부터 먼저 CPU를 할당하는 방식입니다.

이 알고리즘은 대기 시간이 적은 것부터 CPU를 할당하므로, 평균 대기 시간이 짧습니다.

하지만, 프로세스의 실행 시간을 예측하기 어렵기 때문에, 실행 시간이 짧은 프로세스가 계속해서 CPU를 점유하게 되는 "기아(starvation)" 문제가 발생할 수 있습니다.

 

RR(Round Robin)

RR 알고리즘은 FCFS 알고리즘에 타임 슬라이스(time slice)라는 개념을 추가한 방식입니다.

타임 슬라이스란 CPU를 할당하는 시간 조각을 의미합니다.

예를 들어, 타임 슬라이스가 10ms인 경우, 프로세스는 10ms 동안 CPU를 사용할 수 있습니다.

이후에는 다른 프로세스에게 CPU를 넘기게 됩니다.

이 알고리즘은 대화식 작업에 적합하며, 평균 대기 시간이 짧습니다.

하지만, 타임 슬라이스의 크기가 작으면 문맥 교환이 자주 발생하여 오버헤드가 커질 수 있습니다.

 

 

 

이 외에도 우선순위 기반 스케줄링 알고리즘, 다단계 큐 기반 스케줄링 알고리즘 등이 존재합니다.

스케줄링 알고리즘을 선택할 때는 운영 체제가 지원하는 기능과