[CS] CPU 스케줄링 알고리즘

CPU 사용률이 높고, 단위 시간 당 처리량이 많으며, 프로세스의 대기 시간이 짧게 유지되도록 하는 것이 목표

비선점형 CPU 스케줄링 알고리즘

특징

• 프로세스가 CPU를 스스로 포기할 때까지 CPU를 점유. 따라서 컨텍스트 스위칭에 따른 부담이 적지만, 대기 시간이 길어질 수 있음.

종류

FCFS (First Come, First Served)

• 도착한 순서대로 프로세스를 처리. 그러나 긴 작업 때문에 다른 프로세스들이 오래 기다려야 하는 'convoy effect'가 발생 가능

• SJF (Shortest Job First): 실행 시간이 짧은 프로세스를 우선적으로 처리.

• 평균 대기 시간 최소화, 긴 작업들이 실행되지 않는 'starvation' 문제 발생 가능.

• 우선순위 기반: 프로세스에 우선순위를 할당하여 우선순위가 높은 작업을 먼저 처리. 이는 SJF의 단점을 보완하기 위해 'aging' 기법을 사용하여 오래된 작업의 우선순위를 높일 수 있음

선점형 CPU 스케줄링 알고리즘

특징

• 현대 운영 체제에서 널리 사용, 실행 중인 프로세스를 중단시키고 다른 프로세스에 CPU 할당
• 더 높은 응답성과 효율성을 제공하지만, 컨텍스트 스위칭에 따른 오버헤드가 증가.

종류

라운드 로빈(Round Robin, RR)

• 각 프로세스에 동일한 할당 시간을 주고, 시간이 초과하면 준비 큐의 뒤로 이동.
• 할당 시간 설정에 따라 효율성이 달라지며, 평균 응답 시간은 짧아지지만 전체 작업 시간은 길어질 수 있습니다.
  • 할당 시간이 너무 크면 FCFS, 너무 짧으면 컨텍스트 스위칭이 잦아져 오버헤드 발생

SRF (Shortest Remaining Time First)

• 실행 중인 프로세스 중 남은 시간이 가장 짧은 프로세스를 우선적으로 처리.
• SJF의 선점형 버전으로 볼 수 있으며, 실행 중인 작업을 중단할 수 있음.

다단계 큐

• 우선순위에 따라 여러 개의 준비 큐를 사용하고, 각 큐마다 다른 스케줄링 알고리즘(예: 라운드 로빈, FCFS)을 적용.
• 우선순위가 높은 큐부터 처리되며, 낮은 우선순위 큐의 프로세스는 기아 현상 발생 가능
• cf) 비선점형 알고리즘으로 이루어진 다단계 큐도 존재 가능

REF