CPU 스케줄링 알고리즘은 어떤 것들이 있을까?
CPU 스케줄링 알고리즘
--
CPU 스케줄링 알고리즘은
운영체제가 CPU의 자원을 여러 프로세스나 스레드에게 효율적으로 분배하기 위해 사용되는 알고리즘이다.
대표적인 CPU 스케줄링 알고리즘
- 선입 선처리 스케줄링 (FCFS, First Come First Served)
- 최단 작업 우선 스케줄링 (SJF, Shortest Job First)
- 라운드 로빈 스케줄링 (Round Robin)
- 최소 잔여 시간 우선 스케줄링 (SRT, Shortest Remaining Time)
- 우선순위 스케줄링 (Priority)
- 다단계 큐 스케줄링 (Multilevel Queue)
- 다단계 피드백 큐 스케줄링 (Multilevel Feedback Queue)
--
선입 선처리 스케줄링 (FCFS, First Come First Served)
--
FCFS는
단순하게 가장 먼저 도착한(큐에 삽입된) 프로세스를 먼저 처리하는 비선점형 스케줄링 방식이다.
준비 큐에 삽입된 순으로 CPU 자원을 할당하니 간단하고 공정하다고 볼 수 있다.
하지만 프로세스 B처럼 실행시간이 고작 3ms만 소요하는 프로세스를 실행시키기 위해서 15ms를 기다려야 한다.
즉, 호위 효과(Convoy Effect)라는 문제점이 존재한다.
호위 효과 (Convoy Effect)는
긴 작업이 CPU를 점유하면서 뒤에 있는 짧은 작업들이 대기하는 현상을 의미한다.
--
최단 작업 우선 스케줄링 (SJF, Shortest Job First)
--
SJF는
호위 효과(Convoy Effect)를 방지하기 위해
준비 큐에 삽인 된 프로세스들 중에서 실행 소요 시간이 가장 짧은 프로세스를 먼저 처리하는 방식이다.
프로세스들의 평순 대기 시간을 최소화할 수 있다는 장점이 있지만
실제로 프로세스의 실행 소요 시간을 예측하기는 어렵기 때문에 실생활에서 구현이 어려울 수 있으며,
긴 실행 시간을 소요하는 프로세스들이 계속 대기하는 기아 현상(Starvation) 문제가 발생할 수 있다.
기아 현상 (Starvation)은
우선순위가 낮은 작업들이 높은 우선순위 작업들에 의해 계속 밀려 CPU 할당을 받지 못하고
대기하는 상태에 빠지는 현상을 의미한다.
SJF는
기본적으로 비선점형 스케줄링 알고리즘으로 분류되지만, 선점형으로 구현될 수도 있다.
--
라운드 로빈 스케줄링 (Round Robin)
--
Round Robin Scheduling은
FCFS + 타임 슬라이스 개념으로
FCFS처럼 먼저 준비 큐에 삽입된 순으로 CPU를 할당하지만
모든 프로세스에 동일한 할당 시간을 부여하여 해당 시간 동안 작업이 완료되지 못하면 준비 큐(대기열)의 맨 뒤로 이동하고 다음 프로세스를 처리하는 선점형 스케줄링 방식이다.
즉, 모든 프로세스에게 동일한 시간 동안만 CPU의 자원을 할당하며 해당 시간 동안 작업이 모두 완료되지 못하면
해당 프로세스는 다시 대기열 맨 뒤에 세우고 다음 프로세스에게 CPU 자원을 할당한다.
라운드 로빈 방식에서는
타임 슬라이스(시간 할당량)의 크기가 매우 중요하다.
시간 할당량이 매우 크면 FCFS와 비슷해지고,
너무 작으면 문맥 전환이 자주 발생하여 오버헤드가 증가한다.
--
최소 잔여 시간 우선 스케줄링 (SRT, Shortest Remaining Time)
--
SRT는
SJF + 라운드 로빈 개념으로
준비 큐에 존재하는 프로세스들 중에서 실행 소요 시간이 적은 순으로 CPU를 할당하는데
타임 슬라이스를 지정하여 할당된 시간 동안만 CPU를 할당하고 다시 뒤로 보내는 방식이 추가되는
선점형 스케줄링 방식이다.
--
우선순위 스케줄링 (Priority Scheduling)
--
우선순위 스케줄링은
각 프로세스들에게 우선순위를 부여하고, 우선순위가 높은 프로세스에게 CPU를 먼저 할당한다.
우선순위가 같은 경우 FCFS 방식으로 처리한다.
우선순위 스케줄링은
SJF, SRT 처럼 우선순위를 사용하는 스케줄링 알고리즘들을 묶어 가리키는 용어다.
즉, 우선순위 스케줄링은 근본적으로 기아 현상(Starvation) 문제를 가진다.
이를 방지하기 위한 대표적인 기법으로 "에이징(Aging)"이 존재한다.
에이징 (Aging)은
대기 시간이 길어진 프로세스의 우선순위를 점진적으로 상승시키는 방식이다.
--
다단계 큐 스케줄링 (Multilevel Queue)
--
다단계 큐 스케줄링은
위에 설명한 우선순위 스케줄링에서 조금 더 발전된 형태인 스케줄링 알고리즘으로
우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식이다.
모든 프로세스들은 자신의 우선순위에 맞는 준비 큐에 대기하게 되며,
우선순위가 높은 준비 큐에서 대기하고 있는 프로세스를 우선적으로 처리한다.
프로세스의 특성에 따라 차별화된 스케줄링을 적용할 수 있고,
각 준비 큐마다 개별적인 타임 슬라이스도 여러 개 지정할 수 있으며,
준비 큐 마다 다른 스케줄링 알고리즘을 사용할 수도 있다.
다만 여전히 우선순위가 낮은 준비 큐에 존재하는 프로세스들은 계속 대기에 밀릴 수 있어 기아 상태에 빠질 수 있다.
--
다단계 피드백 큐 스케줄링 (Multilevel Feedback Queue)
--
다단계 피드백 큐 스케줄링은
다단계 큐 스케줄링의 발전된 형태로
다단계 큐 스케줄링에서는 각 준비 큐에서 대기하는 프로세스들이 다른 준비 큐로 이동이 불가능하기에
발생하는 기아 상태를 보안하기 위해 다른 준비 큐로 이동할 수 있도록 구현한 방법이다.
간단하게
우선순위가 높은 프로세스지만 CPU의 자원을 할당받는 시간이 많을수록 점차 우선순위가 낮은 준비 큐로 이동시키고
우선순위가 낮은 프로세스지만 오래 대기할수록 점차 우선순위가 높은 준비 큐로 이동시킨다.
다단계 피드백 큐 스케줄링 알고리즘은
구현이 복잡하고 튜닝이 어렵지만
다양한 프로세스를 효율적으로 처리할 수 있다는 장점 때문에
가장 일반적인 CPU 스케줄링 알고리즘으로 알려져 있다.
--
