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

CPU 스케줄링 알고리즘

운영체제에서 CPU 스케줄링(CPU Scheduling)은 여러 프로세스(또는 스레드)가 제한된 CPU 자원을 효율적으로 공유할 수 있도록, 어느 시점에 어떤 프로세스에 CPU를 할당할지를 결정하는 핵심 기법임.

스케줄링 알고리즘은 다양한 시스템 목표(처리량, 응답 시간, 공정성, 실시간성 등)를 최대화 또는 최적화하기 위한 전략을 제시함.

 

CPU 스케줄링 개념과 배경

1. 프로세스 상태와 준비 큐(Ready Queue)

프로세스(또는 스레드)는 Running, Ready, Waiting 등의 상태를 가짐.

CPU 스케줄러는 주로 Ready 상태에 있는 프로세스 중 하나를 선택하여 CPU를 할당함.

 

2. 선점(Preemption) vs 비선점(Non-preemptive)

비선점(Non-preemptive): 한 프로세스가 CPU를 할당받으면, 스스로 종료하거나 I/O 요청 등으로 대기 상태가 되기 전까지 CPU를 빼앗지 않음.

선점(Preemptive): 타이머 인터럽트나 우선순위 변화 등으로 인해, 현재 실행 중인 프로세스에서 강제로 CPU를 회수할 수 있음. 멀티태스킹 환경에서 주로 사용됨.

 

3. 스케줄링 기준(Criteria)

CPU 이용률(CPU Utilization): CPU가 유휴 상태가 되지 않고 최대한 바쁘게 일하도록 함.

처리량(Throughput): 단위 시간당 처리(완료)되는 프로세스의 수.

대기 시간(Waiting Time): 프로세스가 준비 큐에서 기다리는 총 시간.

응답 시간(Response Time): 프로세스가 처음으로 CPU를 할당받기까지 걸린 시간. (대화형 시스템에서 중요)

반환 시간(Turnaround Time): 프로세스가 제출된 시점부터 종료될 때까지 걸린 총 시간.

공정성(Fairness): 모든 프로세스가 과도하게 기아(Starvation) 상태에 빠지지 않도록 하는 정도.

 

주요 스케줄링 알고리즘 : 비선점 알고리즘

1. FCFS (First-Come, First-Served)

원리: 프로세스가 도착한 순서대로 CPU를 할당받아 실행.

장점: 구현이 단순, 공정해 보이는 방식(순서만 보장).

단점: 긴 CPU 버스트(수행 시간)가 먼저 도착하면 뒤의 짧은 작업들이 오래 기다리는 ‘콘보이 효과(Convoy effect)’ 발생 가능.

적용 사례: 배치(Batch) 처리 시스템에서 일부 사용. 현대 범용 OS에서는 거의 사용되지 않음.

 

2. SJF (Shortest Job First)

원리: 다음 CPU 버스트 시간이 가장 짧은 프로세스에게 CPU를 할당. (CPU 사용 시간이 짧은 작업을 먼저 완료시켜 전체 대기 시간을 줄이려는 전략)

장점: 이론적으로 최소 평균 대기 시간을 제공(프로세스 도착 시간이 모두 주어져 있다고 가정 시).

단점: 실제로 CPU 버스트 예측이 어렵고, 긴 작업의 기아(Starvation) 가능성.

변형: 오직 현재 남은 실행 시간만 고려하는 형태는 비선점이지만, 이를 선점으로 확장한 것이 SRTF(Shortest Remaining Time First).

 

3. 우선순위(비선점형 Priority) 스케줄링

원리: 프로세스마다 우선순위(Priority)를 두고, 우선순위가 가장 높은 프로세스부터 CPU를 할당.

장점: 중요한 작업(우선순위가 높은)을 먼저 끝낼 수 있음.

단점: 우선순위가 낮은 프로세스는 영원히 CPU를 얻지 못해 기아 현상 발생 가능.

해결: 우선순위의 동적 상향(우선순위 에이징, aging) 기법으로 기아 방지.

 

주요 스케줄링 알고리즘 : 선점 알고리즘

1. SRTF (Shortest Remaining Time First)

원리: SJF를 선점 가능하게 확장한 알고리즘. 현재 Running 중인 프로세스보다 더 짧은 ‘남은 실행 시간’을 가진 프로세스가 도착하면, CPU를 빼앗아서 그 프로세스에 할당.

특징: 문맥 교환(Context Switch)이 자주 일어날 수 있으므로 오버헤드가 커질 수 있음.

 

2. 우선순위(선점형 Priority) 스케줄링

원리: 높은 우선순위를 가진 새 프로세스가 도착하면, 현재 실행 중인 프로세스를 선점하고 스케줄링한다.

특징: 기아(Starvation) 문제가 더욱 심각할 수 있으나, 선점 특성상 대화형 업무(긴급 작업)에 유리.

 

3. RR (Round Robin)

원리: 준비 큐에서 시간 할당량(Time Quantum, Time Slice)을 정해두고, 각 프로세스에게 일정 간격(예: 10ms)마다 CPU를 선점적으로 돌려가며 할당.

장점: 대화형 시스템(Interactive System)에서 응답 시간(Response Time)을 일정하게 유지하기 좋음.

단점: 할당량이 너무 크면 FCFS에 가까워지고, 너무 작으면 문맥 교환(컨텍스트 스위치) 오버헤드가 커져서 전체 성능 저하.

설계 포인트: 알맞은 타임 슬라이스 설정이 관건.

 

주요 스케줄링 알고리즘 : 다단계 큐, 다단계 피드백 큐

1. 다단계 큐 스케줄링(Multilevel Queue Scheduling)

원리: 우선순위가 서로 다른 여러 큐(예: 시스템 프로세스, 대화형 프로세스, 배치 프로세스 등)를 두고, 큐 간 우선순위를 두거나 Time Slice를 할당.

특징: 프로세스가 어느 큐에 속하는지 정해지면 보통 그 큐에서만 스케줄링(큐 간 이동이 없음).

장점: 프로세스 성격(대화형, 배치 등)에 따라 큐를 분리하여 다른 스케줄링 정책을 적용 가능.

단점: 큐 간 우선순위가 고정되어 있으면 하위 큐는 기아가 발생 가능.

 

2. 다단계 피드백 큐(Multilevel Feedback Queue, MLFQ)

원리: 다단계 큐처럼 여러 우선순위 큐가 있지만, 프로세스가 자신의 CPU 점유 성향(짧게 쓰는지, 길게 쓰는지)에 따라 동적으로 큐를 이동함.

핵심 아이디어: 짧은 CPU 버스트 작업은 높은 우선순위 큐에서 빨리 처리, 오래 실행하는 프로세스는 점점 낮은 우선순위 큐로 내려보내 CPU 독점을 막음.

장점: 짧은 작업은 높은 우선순위에서 신속히 처리되고, 긴 작업도 계속 처리 기회를 얻으면서, 전체적으로 대화형 응답성을 높임.

복잡도: 타임 슬라이스, 이동 기준, 우선순위 조정 방침 등 파라미터가 많아 설계가 복잡하지만, 현대 범용 OS 스케줄러에서 가장 널리 채택된 아이디어.

 

주요 스케줄링 알고리즘 : 실시간 스케줄링

1. 하드 실시간(Hard Real-Time) vs 소프트 실시간(Soft Real-Time)

하드 실시간: 마감 시한(Deadline)을 절대적으로 지켜야 함(안 지키면 시스템 기능 상실).

소프트 실시간: 일정 수준 이상 지연이 없도록 보장하는 수준.

 

2. 예시 알고리즘

Rate Monotonic (RM): 주기가 짧은 태스크(자주 실행해야 하는 작업)에 높은 우선순위를 부여. 고정 우선순위 방식.

Earliest Deadline First (EDF): 가장 촉박한 마감 시한을 가진 작업부터 우선적으로 스케줄링. 동적 우선순위 방식.

 

특징: 일정한 응답 시간 보장이 핵심이므로, 스케줄러는 시스템의 최악 경로(Worst-Case Execution Time, WCET)나 휴대가능성(Schedulability)을 분석.

적용: 임베디드 제어 시스템, 항공/자동차 전자제어장치(ECU), 음성/영상 실시간 스트리밍 등.

 

스케줄링 알고리즘 평가 : 스케줄링 평가 방법

1. 이론적 분석

평균 대기 시간, 평균 반응 시간, 처리량 등을 수식이나 시뮬레이션으로 계산.

예: SJF의 평균 대기 시간 최소 증명(단, 도착 시간 및 CPU 버스트가 확정적이라고 가정).

 

2. 시뮬레이션(Simulation) 및 벤치마크

실제 시스템 혹은 시뮬레이터를 통해 다양한 워크로드(짧은 작업, 긴 작업, 혼합 작업 등)에서의 성능을 측정.

 

3. 실제 운영체제 적용

리눅스의 CFS(Completely Fair Scheduler), 윈도우즈의 우선순위 기반 라운드 로빈, macOS의 hybrid 스케줄러 등 실제 구현을 통해 관찰.

 

스케줄링 알고리즘 평가 : 문맥 교환과 오버헤드

1. 문맥 교환 오버헤드

CPU 레지스터, 프로그램 카운터, 메모리 매핑 정보 등을 저장/복원하는 작업 + 캐시 지역성 손실 등.

 

2. 빈번한 선점

스케줄링 간격이 짧으면 응답성은 좋아지지만, 문맥 교환 오버헤드가 증가해 실제 처리량이 낮아질 수 있음.

 

3. 균형점 찾기

시스템 목표(응답 시간 vs 처리량)에 따라 적절한 선점 빈도를 설계.

 

스케줄링 알고리즘 평가 : 스케줄링 평가 방법

우선순위 알고리즘에서의 기아(Starvation): 낮은 우선순위를 가진 프로세스가 영원히 CPU 기회를 얻지 못함.

해결: 시간이 지날수록 우선순위를 조금씩 높이는(aging) 기법을 통해 언젠가 CPU를 배정받을 수 있도록 함.

 

스케줄링 알고리즘 평가 : 멀티코어/멀티프로세서 환경 스케줄링

1. SMP(Symmetric Multiprocessing)

여러 CPU(core)가 동일 자격을 가지므로, Ready Queue를 공유하거나 코어별 큐를 둬서 부하 균등화(load balancing)를 수행해야 함.

 

2. NUMA(Non-Uniform Memory Access) 구조

메모리 뱅크가 CPU 소켓마다 달라서 접근 시간이 다름.

스케줄러가 프로세스의 캐시/메모리 지역성을 고려하여 CPU를 배정하는 것이 성능에 중요.

 

3. 스레드(Affinity) 스케줄링

특정 프로세스를 이전에 실행하던 CPU 코어에 다시 배정(Processor Affinity)함으로써 캐시 미스 감소, 성능 최적화.

 

현대 운영체제 스케줄러 예시

1. Linux CFS(Completely Fair Scheduler)

우선순위 큐 기반의 MLFQ + ‘공정성(Fairness)을 수학적으로 근사’하는 기법 적용.

각 태스크의 가상 런타임(virtual runtime)을 추적하여, CPU 점유 시간이 적은 태스크에게 우선 기회를 주어 CPU 시간을 균등 분배.

 

2. Windows 스케줄러

우선순위 기반의 라운드 로빈 + 다양한 우선순위 클래스(실시간 우선순위 클래스, 일반 우선순위 클래스 등).

우선순위가 높으면 CPU를 선점적으로 더 많이 할당하며, 에이징 기법 적용.

 

3. macOS / iOS 스케줄러

우선순위 + 시분할 기법을 혼합해 구현.

Grand Central Dispatch(GCD)로 스레드 풀 관리, 작업(Work Item)을 큐에 넣어 OS가 스케줄링.

 

정리

CPU 스케줄링은 시스템 응답성과 처리량을 높이고 기아 현상을 방지하며 CPU 자원을 최대한 활용하기 위해 중요한 운영체제 기능임.

알고리즘은 크게 비선점(FCFS, SJF, Priority Non-preemptive)과 선점(SRTF, Round Robin, Priority Preemptive, 다단계 피드백 큐)으로 나뉨.

현대 범용 OS들은 보통 우선순위 기반의 선점형 다단계 피드백 큐 또는 이를 변형해 공정성을 지향하는 알고리즘(CFS 등)을 구현함.

멀티코어 시대에는 부하분산, 캐시 지역성, NUMA 구조 등을 고려한 고급 기법도 필수가 됨.

각각의 알고리즘은 다른 스케줄링 목표와 워크로드 특성에 맞추어 장단점이 있으므로, 운영체제 혹은 특정 응용 분야에 최적화된 방식을 선정함.

실시간 시스템에서는 엄격한 마감 시한 관리가 중요하므로, Rate Monotonic, EDF 같은 다른 차원의 알고리즘이 사용됨.

 

결국, CPU 스케줄링 알고리즘은 운영체제의 전반적인 성능, 사용자 체감 응답성, 그리고 프로세스 간 공정성 보장에 큰 영향을 미치며, 시스템의 목적과 환경(싱글 코어 vs 멀티코어, 실시간 vs 범용, 서버 vs 데스크톱 등)에 따라 서로 다른 접근을 필요로 함.