CPU 스케쥴링 알고리즘

CPU 스케쥴링 알고리즘의 종류는 매우 다양하고 운영체제 저마다 서로 다른 스케쥴링 알고리즘을 사용하고 있다. 

스케쥴링 알고리즘의 종류

• 선입 선처리 스케쥴링
  • 선입 선처리 스케쥴링은  FCFS(First Come First Served Scheduling)이라고 부르며, 단순히 준비 큐에삽입된 순서대로 프로세스를 처리하는 비선점형 스케쥴링 방식이다. 
  • 프로세스들이 기다리는 시간이 매우 길어질 수 있다. 
  • CPU를 오래 사용하는 프로세스가 먼저 도착하면, 다른 프로세스들은 그 프로세스가 CPU를 사용하는 동안 무작정 기다릴 수 밖에 없게 된다. 이를 호위 효과(convoy effect)라고 한다. 
• 최단 작업 우선 스케쥴링
  • 최단 작업 스케쥴링은 SJF 스케쥴링 (Shortest Job First Scheduling)이라고 부르며, 준비 큐에 삽입된 프로세스 중 CPU 이용 시간의 길이가 가장 짧은 프로세스부터 실행하는 스케쥴링 방식
  • 비선점형 스케쥴링 알고리즘으로 분류되지만, 선점형으로 구현될 수 있다. 
• 라운드 로빈 스케쥴링
  • 선입 선처리 스케줄링에 타임 슬라이스라는 개념이 더해진 스케줄링 방식이다.
  • 타임 슬라이스란 각 프로세스가 CPU를 사용할 수 있는 정해진 시간을 의미하며, 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용한다. 
  • 타임 슬라이스의 크기가 매우 중요하고, 지나치게 클 경우 호위 효과가 생길 수 있고, 너무 작으면 문맥 교환에 발생하는 비용이 커질 수 있다. 
• 최소 잔여 시간 우선 스케쥴링 
  • 최단 작업 우선 스케쥴링 알고리즘과 라운드 로빈 알고리즘을 합친 스케줄링 방식이다. 
  • 최소 잔여 시간 우선 스케줄링 하에서 프로세스들은 정해진 타임 슬라이스만큼 CPU를 사용하되, CPU를 사용할 다음 프로세스로는 남아있는 작업 시간이 가장 적은 프로세스가 선택된다. 
• 우선순위 스케줄링
  • 프로세스들에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행하는 스케줄링 알고리즘이다. 
• 다단계 큐 스케줄링
• 다단계 피드백 큐 스케줄링