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

가장 기본적인 스케줄링 알고리즘에 대해 알아보자.

스케줄링 알고리즘의 종류

선입 선처리 스케줄링(FCFS, First Come First Served 스케줄링)

• 준비 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케줄링 방식이다.
• 즉, CPU를 먼저 요청한 프로세스부터 CPU를 할당하는 스케줄링 방식이다.
• 때때로 프로세스들이 기다리는 시간이 매우 길어질 수 있다는 부작용이 있다.
  • CPU를 오래 사용하는 프로세스를 다른 프로세스들이 기다리는 현상을 호위 효과(convoy effect)라고 한다.

최단 작업 우선 스케줄링(SJF, Shortest Job First 스케줄링)

• 준비 큐에 삽입된 프로세스들 중 CPU 이용 시간의 길이가 가장 짧은 프로세스부터 실행하는 비선점형 스케줄링 방식이다.
• 비선점형 스케줄링 방식으로 분류되지만, 선점형으로 구현될 수도 있다.

라운드 로빈 스케줄링(round robin scheduling)

• 선입 선처리 스케줄링에 타임 슬라이스 개념이 더해져 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 사용하는 선점형 스케줄링 방식이다.
• 각 프로세스가 CPU를 사용할 수 있는 정해진 시간을 타임 슬라이스라고 한다.

최소 잔여 시간 우선 스케줄링(SRT, Shortest Remaining Time 스케줄링)

• 최단 작업 우선 스케줄링 알고리즘과 라운드 로빈 알고리즘을 합친 스케줄링 방식이다.
• 프로세스들은 정해진 타임 슬라이스 만큼 CPU를 사용하되, CPU를 사용할 다음 프로세스는 남아있는 작업 시간이 가장 적은 프로세스가 선택된다.

우선순위 스케줄링(priority scheduling)

• 프로세스들에 우선순위를 부여하고 가장 높은 우선순위를 가진 프로세스부터 실행하는 스케줄링 알고리즘이다.
• 우선순위가 같은 프로세스들은 선입 선처리로 스케줄링된다.
• 우선 순위가 낮은 프로세스는 우선순위가 높은 프로세스들에 의해 실행이 계속 연기되는 기아 현상이 발생할 수 있다.
• 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식으로 기아 현상을 방지하는 기법을 에이징(aging)이라고 한다.

다단계 큐 스케줄링(multilevel queue scheduling)

• 우선순위 스케줄링의 발전된 형태이다.
• 우선순위별로 준비 큐를 여러개 사용하는 스케줄링 방식.
• 각 준비 큐마다 다양한 알고리즘 방식 사용 가능하다.
  • ex. 어떤 큐에서는 선입 선처리 스케줄링, 어떤 큐에서는 라운드 로빈 스케줄링 사용

다단계 피드백 큐 스케줄링(multilevel feedback queue scheduling)

• 다단계 큐 스케줄링의 발전된 형태이다.
• 다단계 큐 스케줄링에서 프로세스들이 큐 사이를 이동할 수 있는 점이 추가된 스케줄링 방식이다.
• 낮은 우선순위 큐에서 오래기다리고 있는 프로세스를 높은 우선순위 큐로 이동시키는 에이징 기법을 적용하여 기아 현상을 예방할 수 있다.
• 어떤 프로세스의 CPU 이용 시간이 길면 낮은 우선순위 큐로 이동시키고, 어떤 프로세스가 낮은 우선순위 큐에서 너무 오래 기다린다면 높은 우선순위로 이동시킬 수 있는 알고리즘이다.
• 구현이 복잡하지만, 가장 일반적인 CPU 스케주링 알고리즘으로 알려져있다.