CPU 스케쥴링 종류엔 뭐가 있을까?

박승우·2024년 8월 5일

CPU scheduling 기술 이론 컴퓨터

자 일흔 일곱 번째 키워드인 'CPU 스케줄링 종류'를 알아 보았다.

이번 키워드는 이전 키워드들의 CPU 스케쥴링 종류에 연관되는 키워드이므로 알아보았다.

선점형 스케줄링 종류엔 뭐가있나요?

1. Round Robin 스케줄링 (RR)

개념: 모든 프로세스가 동일한 시간 할당량(Time Quantum)을 받고 순환 방식으로 CPU를 할당받는 방식이다.
작동 방식
준비 상태의 프로세스는 순서대로 CPU를 할당받는다.
각 프로세스는 일정 시간(Time Quantum) 동안 실행된다.
할당 시간이 끝나면 현재 프로세스는 준비 큐의 끝으로 이동하고 다음 프로세스가 CPU를 할당받는다.
장점
공정성: 모든 프로세스가 균등하게 CPU 시간을 할당받는다.
응답 시간: 짧은 시간 내에 모든 프로세스가 최소한 한 번은 CPU를 할당받는다.
단점
컨텍스트 스위칭 오버헤드: 잦은 프로세스 전환으로 인해 성능 저하가 발생할 수 있다.
시간 할당량 선택이 중요: 너무 짧으면 오버헤드가 크고, 너무 길면 대기 시간이 길어진다.

2. 우선순위 큐 스케줄링 (Priority Queue Scheduling)

개념: 프로세스마다 우선순위가 부여되고, 우선순위가 높은 프로세스가 먼저 실행되는 방식이다.
작동 방식
준비 상태의 프로세스는 우선순위에 따라 정렬된다.
현재 실행 중인 프로세스보다 높은 우선순위의 프로세스가 도착하면 CPU가 선점된다.
우선순위가 동일한 경우, FCFS(First Come First Served) 방식으로 스케줄링된다.
장점
중요한 프로세스를 빠르게 처리할 수 있다.
긴급한 작업을 신속하게 처리할 수 있다.
단점
기아 현상(Starvation): 낮은 우선순위의 프로세스가 실행되지 못하고 무한정 대기할 수 있다.
우선순위 역전(Priority Inversion): 낮은 우선순위 프로세스가 높은 우선순위 프로세스를 블록할 수 있다.

3. 다단계 피드백 큐 스케줄링 (Multilevel Feedback Queue Scheduling)

개념: 여러 단계의 큐를 사용하여 프로세스의 우선순위를 동적으로 조정하며, 프로세스가 한 큐에서 다른 큐로 이동할 수 있는 방식다.
작동 방식
프로세스는 첫 번째 큐에서 시작하며, 각 큐마다 우선순위와 시간 할당량이 다르다.
첫 번째 큐에서 시간 할당량을 다 사용하면 다음 큐로 이동한다.
낮은 큐로 갈수록 시간 할당량이 길어지고 우선순위가 낮아진다.
특정 조건이 충족되면 다시 높은 우선순위 큐로 이동할 수 있다.
장점
유연성: 다양한 우선순위와 시간 할당량을 조정할 수 있어 다양한 프로세스 특성을 고려할 수 있다.
공정성: 자주 CPU를 필요로 하는 프로세스는 낮은 우선순위로 이동하여 CPU 독점을 방지한다.
단점
복잡성: 큐의 수와 스케줄링 정책을 결정하는 것이 복잡하다.
조정 필요: 각 큐의 시간 할당량과 이동 조건을 적절히 설정해야 효과적이다.

비선점형 스케줄링 종류엔 뭐가있나요?

1. FCFS (First Come First Served)

개념: 가장 먼저 도착한 프로세스가 먼저 CPU를 할당받는 방식이다.
작동 방식
준비 상태의 프로세스는 도착 순서대로 대기 큐에 삽입된다.
CPU가 비어 있으면, 대기 큐의 첫 번째 프로세스가 CPU를 할당받아 완료될 때까지 실행된다.
완료된 후에는 다음 프로세스가 CPU를 할당받는다.
장점
간단하고 구현이 용이하다.
공정하게 모든 프로세스를 도착 순서대로 처리한다.
단점
평균 대기 시간이 길어질 수 있다.
긴 작업이 먼저 도착하면 뒤에 도착한 짧은 작업들이 오랫동안 대기할 수 있다(Convoy Effect).

2. SJF (Shortest Job First)

개념: 실행 시간이 가장 짧은 프로세스가 먼저 CPU를 할당받는 방식이다.
작동 방식
준비 상태의 프로세스는 실행 시간을 기준으로 정렬된다.
CPU가 비어 있으면, 대기 중인 프로세스 중 실행 시간이 가장 짧은 프로세스가 CPU를 할당받는다.
해당 프로세스가 완료된 후에는 다음으로 실행 시간이 짧은 프로세스가 CPU를 할당받는다.
장점
평균 대기 시간을 최소화할 수 있다.
CPU 활용 효율성이 높다.
단점
실행 시간을 사전에 정확히 예측하기 어려울 수 있다.
기아 현상(Starvation): 긴 작업들이 짧은 작업들에 밀려 무한정 대기할 수 있다.

3. Deadline Scheduling

개념: 각 프로세스에 데드라인(마감시간)을 설정하고, 데드라인이 임박한 프로세스가 먼저 CPU를 할당받는 방식이다.
작동 방식
프로세스는 각각의 데드라인을 가지고 준비 상태에서 대기한다.
CPU가 비어 있으면, 데드라인이 가장 임박한 프로세스가 CPU를 할당받아 실행된다.
프로세스가 완료될 때까지 실행되고, 이후 다음으로 데드라인이 임박한 프로세스가 CPU를 할당받는다.
장점
실시간 시스템에서 매우 유용하며, 데드라인 내에 작업을 완료할 수 있다.
중요한 작업이 제시간에 완료되도록 보장한다.
단점
모든 작업의 데드라인을 관리하고 예측하는 것이 어렵다.
데드라인을 충족시키지 못할 경우 시스템의 안정성에 문제가 발생할 수 있다.

다단계 스케줄링은 뭐에요?

다단계 스케줄링 (Multilevel Queue Scheduling)은 프로세스를 여러 개의 큐로 분류하여 각 큐마다 다른 스케줄링 알고리즘을 적용하는 방식이다.
각 큐는 서로 다른 우선순위를 가지며, 특정 유형의 프로세스가 특정 큐에 배정된다.
다단계 스케줄링은 다양한 프로세스의 요구를 충족시키기 위해 설계되었다고 한다.
선점형 또는 비선점형으로 구성할 수 있으며, 각 큐는 다른 우선순위를 가질 수 있다.

다단계 스케줄링의 개념

여러 큐를 사용하여 프로세스를 분류하고 각 큐마다 다른 스케줄링 알고리즘을 적용하는 방식이다.

다단계 스케줄링에서는 시스템의 프로세스를 여러 큐로 분류하고, 각 큐는 고유한 우선순위와 스케줄링 정책을 가진다.

	- 예를 들어, 인터랙티브 프로세스는 빠른 응답이 필요하므로 높은 우선순위 큐에 배정되고, 배치 작업은 긴 실행 시간이 필요하므로 낮은 우선순위 큐에 배정된다.

다단계 스케줄링의 구조

여러 개의 큐
시스템에는 여러 개의 큐가 있다.
각 큐는 다른 종류의 작업이나 우선순위를 처리한다.
큐 간 우선순위
각 큐는 고유한 우선순위를 가지며, 높은 우선순위 큐가 비어있지 않으면 낮은 우선순위 큐의 프로세스는 실행되지 않는다.
예를 들어, 인터랙티브 작업이 있는 큐가 비어있지 않으면, 배치 작업이 있는 큐의 프로세스는 실행되지 않는다.
큐 내 스케줄링
각 큐는 자체적인 스케줄링 알고리즘을 사용한다.
예를 들어, 높은 우선순위 큐는 Round Robin 스케줄링을 사용할 수 있고, 낮은 우선순위 큐는 FCFS를 사용할 수 있다.

다단계 스케줄링의 작동 방식

큐에 프로세스 할당
새로 생성된 프로세스는 우선순위와 특성에 따라 적절한 큐에 배정된다.
인터랙티브 작업은 높은 우선순위 큐에, 배치 작업은 낮은 우선순위 큐에 할당된다.
CPU 할당
스케줄러는 높은 우선순위 큐부터 프로세스를 선택하여 CPU를 할당한다.
높은 우선순위 큐가 비어있으면 다음 우선순위 큐에서 프로세스를 선택한다.
큐 내 스케줄링
각 큐 내에서 정의된 스케줄링 알고리즘에 따라 프로세스가 선택되고 실행된다.
예를 들어, 높은 우선순위 큐는 Round Robin을 사용하여 프로세스를 순환하며 실행하고, 낮은 우선순위 큐는 FCFS를 사용하여 도착 순서대로 실행한다.

장점

유연성
다양한 프로세스의 요구를 충족시키기 위해 여러 스케줄링 정책을 적용할 수 있다.
시스템의 성능을 최적화할 수 있다.
응답 시간 향상
중요한 프로세스(예: 인터랙티브 작업)가 높은 우선순위를 가지므로 빠르게 처리된다.
사용자 경험이 향상된다.
분리된 큐 관리
프로세스 종류에 따라 큐를 분리하여 관리할 수 있다.
특정 유형의 프로세스가 시스템 전체에 영향을 미치는 것을 방지다.

단점

복잡성
큐의 수와 스케줄링 정책을 설정하는 것이 복잡합다.
시스템 설정 및 유지 관리가 어렵다.
기아 현상 (Starvation)
낮은 우선순위 큐의 프로세스가 높은 우선순위 큐의 프로세스에 의해 계속 대기할 수 있다.
낮은 우선순위 작업이 오랫동안 실행되지 않을 수 있다.