[운영체제] 05. CPU 스케줄링 알고리즘

CPU 스케줄링 기본 개념

CPU 버스트와 I/O 버스트

프로세스 실행은 CPU 버스트와 I/O 버스트의 교대로 구성된다.

[프로세스 실행 사이클]

CPU 버스트 -> I/O 버스트 -> CPU 버스트 -> I/O 버스트 -> ...

  |-------|          |--------|          |--|
  CPU 실행          I/O 대기           CPU 실행
  (계산)           (디스크 읽기)       (계산)

CPU 바운드 프로세스: 긴 CPU 버스트, 적은 I/O 버스트
I/O 바운드 프로세스: 짧은 CPU 버스트, 많은 I/O 버스트

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

비선점형(Non-preemptive): 프로세스가 자발적으로 CPU를 반납할 때까지 실행 계속
선점형(Preemptive): OS가 실행 중인 프로세스로부터 CPU를 강제로 회수 가능

CPU 스케줄링이 필요한 네 가지 상황이 있다.

실행 상태에서 대기 상태로 전환 (I/O 요청) - 비선점
실행 상태에서 준비 상태로 전환 (인터럽트) - 선점
대기 상태에서 준비 상태로 전환 (I/O 완료) - 선점
프로세스 종료 - 비선점

디스패처 (Dispatcher)

디스패처는 CPU 스케줄러가 선택한 프로세스에게 실제로 CPU를 넘겨주는 모듈이다.

컨텍스트 스위치 수행
사용자 모드로 전환
프로그램의 적절한 위치로 점프

디스패치 지연(dispatch latency)은 가능한 짧아야 한다.

스케줄링 기준

기준	설명	최적화 방향
CPU 이용률	CPU가 작업하는 시간 비율	최대화
처리량(Throughput)	단위 시간당 완료 프로세스 수	최대화
총처리 시간(Turnaround)	제출부터 완료까지 걸린 시간	최소화
대기 시간(Waiting)	준비 큐에서 대기한 총 시간	최소화
응답 시간(Response)	제출부터 첫 응답까지 시간	최소화

스케줄링 알고리즘

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

가장 단순한 스케줄링. 먼저 도착한 프로세스가 먼저 실행된다.

[FCFS 예시]

프로세스  도착 시간  CPU 버스트
  P1        0         24
  P2        0          3
  P3        0          3

실행 순서: P1 -> P2 -> P3

Gantt 차트:
|----P1----|--P2--|--P3--|
0         24    27     30

대기 시간: P1=0, P2=24, P3=27
평균 대기 시간: (0+24+27)/3 = 17

만약 P2, P3, P1 순서라면?
|P2|P3|----P1----|
0  3  6         30

대기 시간: P1=6, P2=0, P3=3
평균 대기 시간: (6+0+3)/3 = 3  (큰 차이!)

호위 효과(Convoy Effect): 긴 프로세스 뒤에 짧은 프로세스들이 줄서는 현상. FCFS의 대표적 단점이다.

2. SJF (Shortest-Job-First)

CPU 버스트가 가장 짧은 프로세스를 먼저 실행한다. 이론적으로 최적의 평균 대기 시간을 보장한다.

[SJF 예시 - 비선점형]

프로세스  도착 시간  CPU 버스트
  P1        0         6
  P2        2         8
  P3        4         7
  P4        5         3

Gantt 차트:
|--P1--|P4|---P3---|----P2----|
0      6  9      16         24

대기 시간: P1=0, P2=16, P3=5, P4=1
평균 대기 시간: (0+16+5+1)/4 = 5.5

[SRTF (Shortest Remaining Time First) - 선점형 SJF]

프로세스  도착 시간  CPU 버스트
  P1        0         6
  P2        2         8
  P3        4         7
  P4        5         3

시간 0: P1 시작 (남은: 6)
시간 2: P2 도착 (남은: 8) -> P1 계속 (남은: 4)
시간 4: P3 도착 (남은: 7) -> P1 계속 (남은: 2)
시간 5: P4 도착 (남은: 3) -> P1 계속 (남은: 1)
시간 6: P1 완료 -> P4 시작 (남은: 3)
시간 9: P4 완료 -> P3 시작 (남은: 7)
시간 16: P3 완료 -> P2 시작 (남은: 8)
시간 24: P2 완료

Gantt 차트:
|--P1--|P4|---P3---|----P2----|
0      6  9      16         24

SJF의 핵심 문제는 다음 CPU 버스트 길이를 미리 알 수 없다는 것이다. 실제로는 과거 버스트를 기반으로 **지수 평균(exponential averaging)**으로 예측한다.

다음 예측값 = alpha * 최근 실측값 + (1 - alpha) * 이전 예측값

alpha = 0이면 최근 값 무시 (이전 예측값만 사용)
alpha = 1이면 이전 예측 무시 (최근 실측값만 사용)
보통 alpha = 0.5 사용

3. 우선순위 스케줄링 (Priority Scheduling)

각 프로세스에 우선순위를 부여하고, 가장 높은 우선순위의 프로세스를 먼저 실행한다.

[우선순위 스케줄링 예시] (낮은 숫자 = 높은 우선순위)

프로세스  CPU 버스트  우선순위
  P1        10         3
  P2         1         1
  P3         2         4
  P4         1         5
  P5         5         2

실행 순서: P2 -> P5 -> P1 -> P3 -> P4

Gantt 차트:
|P2|--P5--|----P1----|P3|P4|
0  1      6        16 18 19

평균 대기 시간: (6+0+16+18+1)/5 = 8.2

기아(Starvation): 낮은 우선순위 프로세스가 영원히 실행되지 않는 문제. 에이징(Aging) 기법으로 해결한다. 시간이 지남에 따라 대기 중인 프로세스의 우선순위를 점진적으로 높인다.

4. 라운드 로빈 (Round Robin)

시분할 시스템용 스케줄링. 각 프로세스에 고정 시간 할당량(time quantum)을 부여한다.

[라운드 로빈 예시] (시간 할당량 = 4)

프로세스  CPU 버스트
  P1        24
  P2         3
  P3         3

Gantt 차트:
|P1|P2|P3|P1|P1|P1|P1|P1|
0  4  7 10 14 18 22 26 30

P1: 4단위 실행 -> 준비 큐 뒤로
P2: 3단위 실행 (완료)
P3: 3단위 실행 (완료)
P1: 나머지 20단위를 4씩 나눠 실행

대기 시간: P1=6, P2=4, P3=7
평균 대기 시간: (6+4+7)/3 = 5.67

시간 할당량(q)의 선택이 중요하다.

q가 너무 크면: FCFS와 동일
q가 너무 작으면: 컨텍스트 스위치 오버헤드 증가
경험적으로 CPU 버스트의 80%가 q 이내에 완료되도록 설정

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

준비 큐를 여러 개의 큐로 분리하고, 각 큐에 다른 스케줄링 알고리즘을 적용한다.

[다단계 큐 스케줄링]

높은 우선순위
+------------------------------------------+
| 시스템 프로세스       | FCFS              |
+------------------------------------------+
| 대화형 프로세스       | RR (q=8)          |
+------------------------------------------+
| 대화형 편집 프로세스   | RR (q=16)         |
+------------------------------------------+
| 배치 프로세스         | FCFS              |
+------------------------------------------+
| 학생 프로세스         | FCFS              |
+------------------------------------------+
낮은 우선순위

상위 큐가 비어야 하위 큐 실행 (고정 우선순위)
또는 큐 간 시간 분배 (예: 80% 대화형, 20% 배치)

6. 다단계 피드백 큐 (Multilevel Feedback Queue)

프로세스가 큐 사이를 이동할 수 있다. 가장 유연한 스케줄링 알고리즘이다.

[다단계 피드백 큐]

큐 0: RR (q=8)   <--- 새 프로세스 진입
  |
  | q=8 내 미완료 시 큐 1로 이동
  v
큐 1: RR (q=16)
  |
  | q=16 내 미완료 시 큐 2로 이동
  v
큐 2: FCFS

동작 예시:
- CPU 버스트 짧은 프로세스: 큐 0에서 바로 완료 (빠른 응답)
- CPU 바운드 프로세스: 큐 0 -> 큐 1 -> 큐 2로 내려감
- I/O 완료 후 복귀하는 프로세스: 다시 큐 0으로 올라감

결과: I/O 바운드 + 대화형 프로세스에 높은 우선순위
      CPU 바운드 프로세스는 낮은 큐에서 긴 시간 할당

스레드 스케줄링

PCS(Process-Contention Scope): 사용자 수준에서 같은 프로세스의 스레드끼리 경쟁
SCS(System-Contention Scope): 시스템 수준에서 모든 스레드가 경쟁

Linux와 Windows는 SCS를 사용한다. 커널 스레드만 CPU에 스케줄링된다.

다중 프로세서 스케줄링

접근 방법

비대칭 멀티프로세싱: 하나의 프로세서가 모든 스케줄링 결정 (단순하지만 병목)
대칭 멀티프로세싱(SMP): 각 프로세서가 독립적으로 스케줄링 (현대 표준)

프로세서 친화성 (Processor Affinity)

프로세스는 현재 실행 중인 프로세서에 머무르려는 경향이 있다. 캐시에 데이터가 올라가 있기 때문이다.

소프트 친화성: 가능하면 같은 프로세서에서 실행하지만 보장하지 않음
하드 친화성: 특정 프로세서 집합에서만 실행을 보장

// Linux에서 프로세서 친화성 설정
#define _GNU_SOURCE
#include <sched.h>

void set_cpu_affinity(int cpu_id) {
    cpu_set_t cpuset;
    CPU_ZERO(&cpuset);
    CPU_SET(cpu_id, &cpuset);

    // 현재 스레드를 특정 CPU에 바인딩
    sched_setaffinity(0, sizeof(cpuset), &cpuset);
}

부하 균형 (Load Balancing)

SMP 시스템에서 모든 프로세서에 작업을 고르게 분배한다.

Push 이주: 주기적으로 과부하 프로세서의 작업을 이동
Pull 이주: 유휴 프로세서가 바쁜 프로세서로부터 작업을 가져옴

Linux CFS (Completely Fair Scheduler)

Linux 2.6.23부터 기본 스케줄러로 사용되는 CFS는 각 프로세스에 "공정한" CPU 시간을 분배한다.

핵심 개념: 가상 실행 시간 (vruntime)

[CFS 동작 원리]

각 프로세스의 vruntime을 추적
vruntime이 가장 작은 프로세스를 다음에 실행

vruntime 증가율 = 실제 실행 시간 / 가중치(nice 값 기반)

nice 값이 낮은(우선순위 높은) 프로세스:
  -> 가중치가 큼 -> vruntime이 천천히 증가 -> 더 자주 스케줄링

nice 값이 높은(우선순위 낮은) 프로세스:
  -> 가중치가 작음 -> vruntime이 빨리 증가 -> 덜 자주 스케줄링

Red-Black 트리

CFS는 Red-Black 트리를 사용하여 프로세스를 vruntime 기준으로 관리한다.

[CFS의 Red-Black 트리]

         vruntime 기준으로 정렬

              (P3: 50)
             /        \
        (P1: 30)    (P5: 70)
        /    \          \
   (P2: 20) (P4: 40)  (P6: 80)

가장 왼쪽 노드(P2, vruntime=20)가 다음 실행 대상

삽입/삭제/검색: O(log N) 보장

// CFS에서 다음 실행할 프로세스 선택 (개념적 코드)
struct task_struct *pick_next_task_fair(struct rq *rq) {
    struct cfs_rq *cfs_rq = &rq->cfs;
    struct rb_node *left;

    // Red-Black 트리에서 가장 왼쪽 노드 선택
    // = vruntime이 가장 작은 프로세스
    left = rb_first_cached(&cfs_rq->tasks_timeline);
    if (!left)
        return NULL;

    struct sched_entity *se = rb_entry(left,
                                        struct sched_entity,
                                        run_node);
    return container_of(se, struct task_struct, se);
}

목표 지연 시간 (Target Latency)

CFS는 목표 지연 시간 내에 모든 실행 가능한 프로세스가 최소 한 번은 실행되도록 보장한다.

예시: 목표 지연 시간 = 20ms, 실행 가능 프로세스 = 4개

동일 우선순위라면 각 프로세스에 5ms 할당
프로세스가 너무 많으면 최소 단위(min_granularity) 보장

알고리즘 비교 요약

[스케줄링 알고리즘 비교]

알고리즘         선점  기아  장점              단점
-------         ----  ----  ----              ----
FCFS            X     X     단순함            호위 효과
SJF             X     O     최적 대기 시간     버스트 예측 어려움
SRTF            O     O     SJF보다 나은 성능  버스트 예측 어려움
우선순위         둘 다  O     유연함            기아 (에이징 필요)
라운드 로빈      O     X     공정, 좋은 응답    q 선택 중요
다단계 큐        O     O     차별화된 서비스    큐 간 이동 불가
다단계 피드백 큐  O     가능   가장 유연         매개변수 설정 복잡
CFS             O     X     공정한 CPU 분배    구현 복잡

정리

CPU 스케줄링은 멀티프로그래밍 OS의 핵심이다. FCFS, SJF, 우선순위, 라운드 로빈 등 다양한 알고리즘이 있으며, 각각 처리량, 응답 시간, 공정성 사이에서 다른 절충점을 제공한다. Linux의 CFS는 Red-Black 트리와 가상 실행 시간 개념을 활용하여 효율적이면서도 공정한 스케줄링을 구현한다.