CPU 스케줄링과 프로세스 실행 순서 설계

준비 큐에서 다음 실행 대상을 고르는 일

CPU 스케줄링은 준비 큐에 있는 프로세스 또는 스레드 가운데 CPU를 이어받을 대상을 결정하는 운영체제 기능이다. CPU는 한정돼 있으므로 I/O 대기 중인 작업이 생겼을 때 다른 작업을 실행하고, 대화형 요청에는 빠르게 반응하며, 데드라인 작업은 제때 끝낼 수 있어야 한다.

이 과정에서 스케줄러는 선택 알고리즘을 수행하고, 실행 대상을 바꿀 때는 문맥 교환이 일어난다. 여러 프로세스를 메모리에 유지하는 멀티프로그래밍은 CPU 활용률을 높이고, CPU 시간을 작은 단위로 나누는 시분할은 여러 프로세스가 실행 기회를 얻도록 한다.

CPU 활용률, 응답 시간, 처리량, 공정성, 실시간 제약은 모두 스케줄링이 다루는 목표다. I/O 대기 시간에는 다른 프로세스를 실행해 CPU 활용률을 높일 수 있고, 사용자 상호작용 프로그램의 응답 시간이나 단위 시간당 완료 프로세스 수 역시 선택 정책의 영향을 받는다.

⤢✕

실행 순서를 정하는 대표 정책

FCFS는 도착 순서를 그대로 따른다

FCFS(First-Come, First-Served)는 먼저 도착한 프로세스를 먼저 처리하는 비선점형 정책이다. 실행을 시작한 프로세스는 자발적으로 CPU를 반환할 때까지 실행되므로 구현은 단순하고, 도착 순서라는 기준에서는 공정하다. 반면 긴 작업 뒤에 짧은 작업이 줄지어 기다리는 Convoy Effect가 생길 수 있어 평균 대기 시간이 길어지고 응답 시간을 예측하기 어렵다.

⤢✕

SJF는 짧은 CPU 사용 시간을 우선한다

SJF(Shortest Job First)는 CPU Burst가 짧은 프로세스를 먼저 실행하는 비선점형 방식이다. 이론적으로 평균 대기 시간을 최소화하지만, 다음 CPU 사용 시간을 예측해야 하며 긴 프로세스가 무한히 밀릴 수 있는 기아 문제가 있다.

⤢✕

SRTF(Shortest Remaining Time First)는 SJF의 선점형 변형이다. 새로 도착한 프로세스의 남은 시간이 더 짧으면 현재 작업을 선점해 실행 순서를 바꾼다. 실행 중에도 조정할 수 있는 대신, 잦은 선점은 문맥 교환 오버헤드를 늘린다.

우선순위 정책은 중요도를 실행 순서에 반영한다

우선순위 스케줄링은 프로세스마다 우선순위 번호를 부여하고 높은 우선순위의 작업부터 선택한다. 선점형과 비선점형으로 모두 구현할 수 있다. 낮은 우선순위의 작업이 계속 대기하는 기아 문제를 피하려면, 대기 시간이 길어질수록 우선순위를 높이는 에이징을 적용할 수 있다.

⤢✕

에이징은 대기 시간에 비례해 우선순위를 올리는 방식이다. 동적 우선순위를 사용하면 모든 프로세스가 결국 실행될 수 있다.

Round Robin은 CPU 시간을 순환 배분한다

Round Robin은 준비 큐를 순환 큐로 관리하는 선점형 방식이다. 시간 할당량(Time Quantum)이 지나면 실행 중인 프로세스를 선점하고 다음 프로세스에 CPU를 넘긴다. 모든 프로세스가 균등하게 CPU 시간을 얻으므로 시분할과 대화형 시스템에 적합하다.

⤢✕

시간 할당량이 너무 작으면 문맥 교환 오버헤드가 커지고, 너무 크면 FCFS와 비슷해져 응답 시간이 증가한다. 일반적인 시간 할당량은 10-100ms다.

큐를 나누거나 이동시키는 방식

다단계 큐는 프로세스 유형에 따라 준비 큐를 분리한다. 시스템 프로세스, 대화형 프로세스, 배치 프로세스처럼 큐를 구분하고, 각 큐에 서로 다른 알고리즘을 적용할 수 있다. 프로세스는 생성될 때 배정된 큐에 영구적으로 머물며, 큐 간에는 우선순위 또는 시간 할당으로 실행 순서를 정한다.

⤢✕

다단계 피드백 큐는 프로세스가 큐 사이를 이동할 수 있게 해 고정 배정의 한계를 보완한다. 짧게 CPU를 쓰는 I/O 바운드 프로세스는 상위 큐에 유지하고, 긴 CPU 사용을 반복하는 CPU 바운드 프로세스는 하위 큐로 내린다. 워크로드 특성에 맞춰 우선순위를 조정하는 정책이다.

⤢✕

어떤 지표로 스케줄러를 평가하는가

CPU 활용률은 CPU가 실제 작업을 수행하는 시간의 비율이며 목표는 40% ~ 90%다. 처리량은 단위 시간에 완료된 프로세스 수를, 반환 시간은 프로세스 제출부터 완료까지 걸린 총 시간을 뜻한다. 준비 큐에서 기다린 시간은 대기 시간이고, 요청 제출 후 첫 응답까지 걸린 시간은 응답 시간이다.

동일한 예제에서도 알고리즘마다 결과는 달라진다.

알고리즘	평균 대기 시간	평균 반환 시간	특징
FCFS	17ms	27ms	간단, Convoy Effect
SJF	7ms	17ms	최소 대기 시간, 기아
RR (q=4)	12.67ms	22.67ms	공정, 응답 빠름
Priority	8.2ms	18.2ms	중요도 반영, 기아

데드라인을 기준으로 CPU를 배정하는 경우

경성 실시간(Hard Real-Time) 시스템에서는 데드라인을 반드시 지켜야 하며, 실패는 치명적일 수 있다. 항공기 제어, 의료 장비, 자동차 브레이크가 여기에 해당한다. 최악의 경우에도 실행 시간을 보장해야 하므로 예측 가능성이 중요하고, 데드라인이 가까운 작업을 우선 실행한다.

연성 실시간(Soft Real-Time)은 데드라인 준수를 목표로 하지만 위반 시 성능이 저하되는 형태다. 비디오 스트리밍, 게임, VoIP가 예시이며 일반 프로세스보다 높은 우선순위를 둘 수 있다.

주기가 짧을수록 높은 우선순위를 주는 Rate Monotonic Scheduling, 가장 가까운 데드라인을 먼저 고르는 Earliest Deadline First (EDF), 여유 시간이 가장 적은 작업을 선택하는 Least Laxity First가 실시간 알고리즘으로 사용된다.

멀티프로세서에서 추가되는 문제

비대칭 멀티프로세싱은 하나의 CPU가 스케줄링을 맡는 마스터-슬레이브 구조다. 스케줄링 로직은 단순하지만 마스터 CPU가 병목이 될 수 있다.

대칭 멀티프로세싱(SMP)에서는 각 CPU가 독립적으로 스케줄링하고 공통 준비 큐에 접근한다. 큐 접근에는 lock이 필요하므로 CPU 수가 많아질수록 lock 경쟁과 동기화 오버헤드를 고려해야 한다.

⤢✕

프로세서 친화도는 같은 프로세스를 가능한 한 같은 CPU에서 실행해 캐시를 재사용하려는 방식이다. Soft Affinity는 같은 CPU를 선호하고, Hard Affinity는 특정 CPU에서만 실행하도록 제한한다. NUMA-aware 정책은 NUMA 노드를 고려해 로컬 메모리 접근을 최적화한다.

부하 분산은 프로세서 친화도와 충돌할 수 있다. Push Migration은 주기적으로 부하를 확인해 프로세스를 옮기고, Pull Migration은 유휴 CPU가 바쁜 CPU에서 프로세스를 가져온다.

자바 스레드와 OS 스케줄러의 경계

과거의 Green Thread는 JVM이 스레드를 관리해 OS와 독립적이었다. 현재의 Native Thread는 OS 스레드에 1:1로 매핑되며, 실제 스케줄링은 OS 스케줄러에 위임된다. 따라서 스케줄링 동작은 플랫폼마다 다를 수 있다.

스레드 우선순위는 JVM이 OS에 제공하는 힌트일 뿐 실행 순서를 보장하지 않는다. Windows는 7단계이고 Linux는 이를 무시할 수 있으므로, 우선순위에 의존하는 설계는 지양해야 한다.

// 자바 스레드 우선순위 예제
Thread thread1 = new Thread(() -> {
    System.out.println("Thread 1 실행");
});

Thread thread2 = new Thread(() -> {
    System.out.println("Thread 2 실행");
});

// 우선순위 설정 (1 ~ 10)
thread1.setPriority(Thread.MIN_PRIORITY);  // 1
thread2.setPriority(Thread.MAX_PRIORITY);  // 10

thread1.start();
thread2.start();

MIN_PRIORITY는 1, NORM_PRIORITY는 기본값 5, MAX_PRIORITY는 10이다.

스레드 실행 흐름은 yield(), sleep(), join(), interrupt() 같은 메서드로 제어할 수 있다.

// yield(): 다른 스레드에게 CPU 양보
Thread.yield();

// sleep(ms): 지정 시간 동안 대기
Thread.sleep(1000);  // 1초 대기

// join(): 다른 스레드 종료 대기
Thread t = new Thread(() -> {
    // 작업
});
t.start();
t.join();  // t가 종료될 때까지 대기

// interrupt(): 대기 중인 스레드 깨우기
t.interrupt();

Executor 프레임워크는 작업 제출과 스레드 관리 방식을 분리한다. FixedThreadPool은 고정된 수의 스레드를, CachedThreadPool은 필요에 따라 생성하고 재사용하는 스레드를 제공한다. SingleThreadExecutor는 단일 스레드에서 순차 실행하며, ScheduledThreadPool은 지연 또는 주기 작업에 사용한다.

// Executor 프레임워크
ExecutorService executor = Executors.newFixedThreadPool(4);

executor.submit(() -> {
    // 작업
});

// ScheduledExecutor: 스케줄된 작업 실행
ScheduledExecutorService scheduler =
    Executors.newScheduledThreadPool(2);

scheduler.scheduleAtFixedRate(
    () -> System.out.println("주기적 작업"),
    0,      // 초기 지연
    1,      // 주기
    TimeUnit.SECONDS
);

Fork/Join 프레임워크는 분할 정복 방식의 병렬 처리에 쓰인다. 유휴 스레드가 바쁜 스레드의 작업을 가져오는 Work Stealing으로 스레드 간 작업을 분산해 CPU 활용률을 높인다.

// Fork/Join: 분할 정복 병렬 처리
class SumTask extends RecursiveTask<Long> {
    private long[] array;
    private int start, end;

    @Override
    protected Long compute() {
        if (end - start <= THRESHOLD) {
            // 작은 작업: 직접 계산
            long sum = 0;
            for (int i = start; i < end; i++) {
                sum += array[i];
            }
            return sum;
        } else {
            // 큰 작업: 분할
            int mid = (start + end) / 2;
            SumTask left = new SumTask(array, start, mid);
            SumTask right = new SumTask(array, mid, end);

            left.fork();  // 비동기 실행
            long rightResult = right.compute();
            long leftResult = left.join();  // 결과 대기

            return leftResult + rightResult;
        }
    }
}

ForkJoinPool pool = new ForkJoinPool();
long result = pool.invoke(new SumTask(array, 0, array.length));

Linux 스케줄러와 설계 선택의 기준

CFS(Completely Fair Scheduler)는 Linux 2.6.23부터 기본 스케줄러다. 프로세스의 가상 실행 시간을 추적하고 Red-Black Tree로 정렬해 모든 프로세스에 공평한 CPU 시간을 배분한다.

BFS(Brain Fuck Scheduler)는 모든 CPU가 하나의 큐를 공유하고 고정된 시간 할당량을 사용하며, 데스크톱 응답성을 중시한다. O(1) Scheduler는 스케줄링 결정을 O(1) 시간에 수행하고 Active/Expired 큐의 두 우선순위 배열을 사용했으며, Linux 2.6.23 이전에 쓰였다.

스케줄러를 설계하거나 선택할 때는 목표의 충돌을 먼저 봐야 한다. 배치 시스템은 처리량을, 대화형 시스템은 응답 시간을 우선한다. 완전한 공정성은 성능 저하로 이어질 수 있고, 실시간 환경은 예측 가능성을, 범용 환경은 적응성을 더 중시한다.

CPU 바운드 작업, I/O 대기가 많은 I/O 바운드 작업, 빠른 사용자 응답이 필요한 대화형 작업, 대량 데이터를 다루는 배치 작업은 서로 다른 정책을 요구한다. 단일 프로세서에서는 문맥 교환을 줄이고, 멀티프로세서에서는 부하 분산과 캐시 친화도를 조정해야 한다. 실시간 시스템은 데드라인 보장이 필요하며 모바일 환경은 전력 소비도 함께 고려한다.

이종 멀티코어에서는 ARM의 big.LITTLE처럼 고성능 코어와 저전력 코어를 작업 특성에 맞춰 선택한다. AI 기반 스케줄링은 워크로드 패턴 학습, 미래 자원 수요 예측, 매개변수 자동 튜닝을 대상으로 한다. 클라우드와 컨테이너 환경에서는 Kubernetes 스케줄러, cgroup·namespace 기반 자원 격리, Auto-scaling이 스케줄링의 범위를 확장한다.