[OS] CPU 스케줄러

CPU 스케줄링

운영 체제에서 다중 프로세스를 관리하고 CPU의 사용을 최적화하기 위한 방법
여러 프로세스가 CPU를 공유하는 다중 프로그래밍 환경에서 CPU 스케줄러는 어떤 프로세스가 CPU를 사용할 수 있는지 결정하고, 프로세스들 사이의 우선순위를 관리한다.

 

선점 스케줄링 vs 비선점 스케줄링

선점 스케줄링 (Preemptive Scheduling)

현재 실행 중인 프로세스가 다른 프로세스에 의해 강제로 중단되고, 다른 프로세스가 CPU를 차지할 수 있는 방식

• 우선순위가 높은 프로세스가 CPU 시간을 뺏어갈 수 있다.
• 실시간 시스템에서 중요하다.
• 프로세스의 응답 시간을 보장하고 우선순위가 높은 작업을 즉시 처리할 수 있다.
• 컨텍스트 스위칭에 따른 오버헤드가 발생할 수 있다.
• 종류 : SRTF, 우선순위 기반, Round Robin, Multi-Level Queue, Multi-Level Feedback Queue

 

비선점 스케줄링 (Non-preemptive Scheduling)

현재 실행 중인 프로세스가 자발적으로 종료되거나 I/O 요청 등의 이벤트가 발생하기 전까지 계속 CPU를 점유하는 방식

• 한 번 CPU를 할당받은 프로세스는 스케줄링이 이루어질 때까지 CPU를 사용한다.
• 컨텍스트 스위칭에 따른 오버헤드가 적고, 단순한 구현이 가능하다.
• 응답 시간이 긴 작업이 우선순위가 높아도 CPU를 점유하여 다른 작업의 실행을 지연시킬 수 있다.
• 종류 : FCFS, SJF, 우선순위 기반

 

CPU 스케줄러 종류

FCFS (First-Come, First-Served) 스케줄러

• 먼저 도착한 작업부터 순서대로 처리하는 알고리즘 (배치 처리 시스템)
  • ex) 프로세스가 저장매체를 읽거나 프린팅 하는 작업 없이 쭉 CPU 를 처음부터 끝까지 사용
    
    
• 간단한 알고리즘으로, 구현이 쉽고 오버헤드가 적다.
  • 오버헤드: 어떤 작업을 수행하기 위해 필요한 부가적인 작업 또는 자원이다. 즉, 주요 작업을 수행하기 위해 추가적인 작업이나 자원을 사용하는 것을 말한다.
    
    
  • 소프트웨어 개발에서도 오버헤드가 발생할 수 있다. 예를 들어, 함수 호출 시 매개변수 전달, 스택 프레임 생성, 반환값 복사 등의 추가 작업이 필요한 경우가 있다. 이러한 오버헤드는 프로그램의 성능에 영향을 미치므로 최소화하는 것이 좋다.
    
    
• 하지만, 작업의 크기가 크거나 도착 시간이 늦은 작업이 많은 경우, 평균 대기 시간이 길어질 수 있다.

 

SJF (Shortest-Job-First) 스케줄러

• 수행 시간이 짧은 작업부터 처리하는 알고리즘
  • SJF 를 구현하려면 우선순위 큐와 힙 (최소 힙) 자료구조 사용을 고려해야 한다.
    
    
• 평균 대기 시간을 최소화할 수 있으며, 작업의 길이가 일정하지 않을 때도 잘 동작한다.
• 하지만, 작업의 수행 시간을 미리 예측해야 하므로, 예측이 어려운 경우에는 성능이 저하될 수 있다.
  또한, 프로세스 시작전에 얼마나 걸리지 모르기 때문에 현실적으로 적용하기 어렵다.

 

SRTF (Shortest Reamining Time First) 스케줄러

• 현재 실행 중인 프로세스들 중에서 실행 시간이 가장 짧은 프로세스에 CPU를 할당하는 알고리즘
• 각 프로세스에 대해 남은 실행 시간을 추적하고, 현재 실행 중인 프로세스보다 남은 실행 시간이 더 짧은 프로세스가 도착하면 CPU를 선점한다.
• 따라서, 도착한 프로세스 중에서 가장 짧은 실행 시간을 가진 프로세스에 CPU 시간을 할당하여 최소 실행 시간을 보장한다.
• 그러나, 스케줄링 결정을 위해 실행 시간 추정이 필요하기 때문에 추가적인 계산 비용이 발생할 수 있으며, 잦은 컨텍스트 스위칭으로 인해 오버헤드가 많아진다. SJF와 마찬가지로 현실적으로 적용하기 어렵다.
• 기아 현상이 발생할 수 있다.

 

Priority Scheduling (우선순위 기반 스케줄러)

• 작업의 우선순위를 기준으로 처리하는 알고리즘으로 선점과 비선점 방식이 모두 가능하다.
  • 정적 우선순위: 프로세스마다 우선순위를 미리 지정
  • 동적 우선순위: 스케쥴러가 상황에 따라 우선순위를 동적으로 변경 (한 번도 실행되지 않은 알고리즘에 높은 우선순위 부여)
    
    
• 우선순위가 높은 작업부터 처리되기 때문에, 중요한 작업에 대한 응답 시간을 줄일 수 있다.
• 하지만, 우선순위가 낮은 작업이 무한정 대기할 수 있으므로, 기아 상태가 발생할 가능성이 있다.

 

Round Robin 스케줄러

• 일정한 시간 단위(quantum)를 두고, 작업을 순환하며 처리하는 알고리즘 (시분할 시스템)
• 시간 단위안에 완료하지 못한 경우 큐의 맨 뒤에 배치되어 CPU를 독점하지 않는다.
• 모든 작업에게 공평한 할당량을 보장할 수 있고, 응답 시간이 빠르다는 장점이 있다.
• 하지만, 시간 단위가 너무 작으면 컨텍스트 스위칭이 잦아져서 오버헤드가 커지고, 시간 단위가 크면 평균 대기 시간이 길어질 수 있다.
• 시간 단위가 너무 크면 FCFS와 비슷해진다.

 

Multi-Level Queue

• 여러 개의 우선순위 큐로 구성되며, 각 큐마다 다른 우선순위 레벨이 할당되고, 각 큐마다 다른 Time Quantum 을 설정하는 방식
• 일반적으로 우선순위가 높은 큐는 작은 Time Quantum 을 할당받고, 우선순위가 낮은 큐는 큰 Time Quantum 을 할당받는다.
• 우선순위가 낮은 큐들이 실행을 못하는 상황을 방지한다.

 

Multi-Level Feedback Queue

• 프로세스가 다른 우선순위 큐로 이동할 수 있는 동적인 방식
• 각 큐는 선점형 스케줄링 알고리즘을 사용하며, 일반적으로 우선순위가 높은 큐에서 실행 중인 프로세스가 낮은 우선순위 큐로 이동할 수 있다.
  실행 시간이 긴 프로세스나 CPU를 많이 사용한 프로세스 등이 이동한다.
• 반환 시간을 최적화 하고, 응답 시간을 최적화 하기 위해 사용한다.
• 규칙
  1. 우선순위에 따라 실행되는 프로세스가 결정된다.
  2. 우선순위가 같다면 라운드 로빈 방식으로 실행하며, 시분할 방식으로 공정하게 CPU를 할당받는다.
  3. 작업이 도착하면 가장 높은 우선순위 큐에서 시작하며, 나중에 도착한 작업은 해당 우선순위 큐에서 대기한다.
  4. 작업이 지정된 단계에서 할당받은 시간을 소진하면, 우선순위가 낮은 큐로 이동하고 다른 작업에 CPU를 할당한다.
  5. 프로세스의 성격이나 실행 시간이 변경되는 상황에 대응할 수 있도록 일정 주기마다 모든 작업을 가장 높은 우선순위 큐로 이동시킨다. 이로 인해 스케줄링을 유연하게 진행할 수 있다.