[CS] CPU 스케줄링

CPU 스케줄링

: 여러 프로세스가 CPU를 공정하고 효율적으로 사용할 수 있도록 운영체제가 CPU를 배분하는 방식.

• 스케줄링이 없다면,
  • 긴 작업이 모든 자원을 점유해 다른 작업이 무한정 대기하거나, 낮은 우선순위의 작업이 먼저 실행되는 비효율적 상황이 발생

 

스케줄링 방식

• 선점형: 운영체제가 CPU를 강제로 회수해 다른 프로세스에게 할당 가능
  • CPU를 도중에 뺏을 수 있음   
  • 빠른 응답 시간
  • 컨텍스트 스위칭(작업 전환)에 따른 높은 오버헤드 발생
  • 대표 알고리즘: SRT, Round Robin, MLFQ
• 비선점형: 현재 실행 중인 프로세스가 스스로 CPU를 반납할 때까지 다른 프로세스는 대기
  • CPU를 자발적으로 놓을 때까지 유지
  • 짧은 작업이 긴 작업 뒤에 오래 대기할 수 있음
  • 처리 흐름이 단순하고 안정적
  • 대표 알고리즘: FCFS, SJF

 

 

주요 알고리즘

알고리즘	특징		유형
FCFS (선입 선처리)	먼저 도착한 순서대로 처리	긴 작업이 앞에 있으면 전체 지연	비선점
SJF (최단 작업 우선)	실행 시간이 짧은 순서대로 처리	긴 작업이 기아 상태에 빠질 수 있음	비선점
SRT (최소 잔여 시간)	남은 실행 시간이 가장 짧은 프로세스를 실행	컨텍스트 스위칭 많음	SJF + 선점
RR (라운드 로빈)	정해진 시간(Time Quantum)만 사용 후 교체	타임이 너무 짧으면 오버헤드 증가	선점
Multilevel Queue	우선순위 큐를 여러 개로 나누고, 각각 다른 정책 적용	큐 간 이동이 불가능 기아 현상 발생 가능	혼합
MLFQ (다단계 피드백 큐)	대기 시간 긴 프로세스 우선순위 상승	에이징은 적용됐으나 구현 복잡	선점+에이징

 

 

기아 현상 & 해결법

• 기아(Starvation): 낮은 우선순위의 프로세스가 계속해서 CPU를 배정받지 못하고 무한 대기하는 현상.
• 에이징(Aging): 오래 기다린 프로세스의 우선순위를 점점 높여 해결.
  • 다단계 피드백 큐(MLFQ) 스케줄링은 에이징 기법을 도입하여 실시간성과 공정성을 동시에 만족