[면접을 위한 CS 전공 지식 노트] 3.4 CPU 스케줄링 알고리즘

Section 4. CPU 스케줄링 알고리즘

스케줄링 알고리즘이란?

프로그램이 실행될 때, CPU 스케줄링 알고리즘이 어떤 프로그램에 CPU 소유권을 줄 것인지 결정하고 CPU 스케줄러가 이에 따라 프로세스에서 해야 하는 일을 스레드 단위로 CPU에 할당한다.

 

3.4.1 비선점형 방식

비선점형 방식(non-preemptive)은 프로세스가 스스로 CPU 소유권을 포기하는 방식이며, 강제로 프로세스를 중지하지 않는다. 따라서 컨텍스트 스위칭으로 인한 부하가 적다.

 

• FCFS(First Come, First Served)
  • 가장 먼저 온 것을 가장 먼저 처리하는 알고리즘이다.
  • 단점: 길게 수행되는 프로세스라 '준비 큐에서 오래 기다리는 현상'이 발생한다.
• SJF(Shortest Job First)
  • 실행 시간(과거 실행시간으로 추측)이 가장 짧은 프로세스를 우선적으로 실행하는 알고리즘이다. 평균 대기 시간이 가장 짧다.
  • 따라서 실행 시간이 긴 프로세스는 짧은 프로세스가 계속 도착하면 실행 순서가 계속 뒤로 밀리게 된다. 특히, 짧은 작업이 자주 들어오는 경우, 긴 프로세스는 무한정 대기(Starvation) 상태에 빠질 수 있다.
• 우선순위
  • 오래된 작업일수록 '우선순위를 높이는 방법'을 통해 SJF의 무한정 대기의 단점을 보완한 알고리즘이다.

 

3.4.2 선점형 방식

선점형 방식(preemptive)은 현재 운영체제가 쓰는 방식이다. 지금 사용하고 있는 프로세스를 알고리즘에 의해 중단시켜 버리고 강제로 다른 프로세스에 CPU 소유권을 할당하는 방식을 말한다.

 

• 라운드 로빈(RR, Round Robin)
  
  • 모든 프로세스가 공평하게 CPU를 사용할 기회를 가지도록 설계된 방식입니다. 각 프로세스는 정해진 시간(Time Quantum) 동안만 CPU를 사용하며, 그 시간이 지나면 선점(강제 중단)되어 대기열(Ready Queue)의 맨 뒤로 이동하게 된다.
  • 할당시간이 너무 크면 FCFS가 되고, 짧으면 컨텍스트 스위칭이 잦아져서 비용이 커진다.(오버헤드)
• SRF(Shortest Remaining Time First)
  • 남은 실행 시간이 가장 짧은 프로세스를 우선 실행하는 방식이다.
  • 현재 실행 중인 프로세스보다 더 짧은 실행 시간이 필요한 프로세스가 도착하면, 실행 중인 프로세스를 선점하고 새 프로세스를 실행한다.

 

 

▶︎ 스케줄링 구조: 다단계 큐

• 다단계 큐 스케줄링은 우선순위에 따라 여러 개의 준비 큐를 사용하는 방식이다.
• 각 큐는 다른 우선순위를 가지며, 다른 스케줄링 알고리즘을 적용한다.
• 시스템은 높은 우선순위의 큐를 먼저 처리하고, 모든 프로세스를 처리한 후에 낮은 우선순위 큐를 실행한다.
• 큐 간의 프로세스 이동이 안 되므로 스케줄링 부담이 적지만 유연성이 떨어지는 특징이 있다.