CPU 스케줄링에서 쓰이는 대표적인 알고리즘에 대해 간략히 다룹니다.
- 역할: 프로세스에서 해야 하는 일을 스레드 단위로 배치 한다.
- 프로그램이 실행될 때는 어떤 프로그램에 CPU 소유권을 줄 것인지 결정한다.
- 목표
- CPU 이용률이 높아지도록 한다.
- 주어진 시간에 많은 일을 하도록 한다.
- 준비 큐에 있는 프로세스는 적게 한다.
- 응답 시간을 짧게 한다.
- 의미: 프로세스가 스스로 CPU 소유권을 포기하는 방식이며, 강제로 프로세스를 중지하지 않는다.
- 따라서 컨텍스트 스위칭으로 인한 부하가 적다.
- 의미: 가장 먼저 온 것을 가장 먼저 처리하는 알고리즘이다.
- 특징: 길게 수행되는 프로세스가 있으면 ‘준비 큐에서 오래 기다리는 현상(convoy effect)’이 발생한다.
- 의미: 실행 시간이 가장 짧은 프로세스를 가장 먼저 실행하는 알고리즘이다.
- 특징
- 긴 시간을 가진 프로세스가 실행되지 않는 현상(starvation) 발생한다.
- 평균 대기 시간이 가장 짧다.
- 실제로는 실행 시간을 알 수 없기에 과거의 실행했던 시간을 토대로 추측해서 사용한다.
- 의미: 오래된 작업일수록 ‘우선순위를 높이는 방법(align)’을 사용한다.
- 특징: SJF 스케줄링에서 긴 시간을 가진 프로세스가 실행되지 않는 현상을 해결한다.
- 의미: 현재 사용하고 있는 프로세스를 알고리즘에 의해 중단시키고 다른 프로세스에 CPU 소유권을 할당하는 방식이다.
- 현대 운영체제가 채택한 방식이다.
- 의미: 각 프로세스에게 동일한 할당 시간을 주고 그 시간 안에 끝나지 않으면 다시 준비 큐의 뒤로 가는 알고리즘이다.
- 특징
- 현대 컴퓨터가 쓰는 선점형 알고리즘 스케줄링 방법이다.
- 할당 시간이 너무 길면 FCFS가 되고, 짧으면 컨텍스트 스위칭이 잦아져서 오버헤드가 커진다.
- 일반적으로 전체 작업 시간은 길어지지만 평균 응답 시간은 짧아진다는 특징이 있다.
- 로드밸런서에서 해당 알고리즘을 트래픽 분산 알고리즘으로도 쓰인다.
- 의미: 중간에 더 짧은 작업이 들어오면 수행하던 프로세스를 중지하고 해당 프로세스를 수행하는 알고리즘이다.
- 의미: 우선순위에 따른 준비 큐를 여러 개 사용하고, 큐마다 라운드 로빈이나 FCFS 등 다른 스케줄링 알고리즘을 적용한 것이다.
- 특징
- 큐 간의 프로세스 이동이 안 되므로 스케줄링 부담이 적지만 유연성이 떨어진다.
- 면접을 위한 CS 전공지식 노트(주홍철)