운영체제 — CPU 스케줄링 알고리즘

개요 — CPU 스케줄링이 게임에 미치는 영향

멀티태스킹 환경에서 CPU는 여러 프로세스·스레드를 처리합니다.

• 게임 서버에서 네트워크 처리 스레드가 게임 로직 스레드보다 높은 우선순위를 가져야 하는 이유
• 실시간 게임에서 컨텍스트 스위칭이 프레임 레이트에 미치는 영향
• 스레드 수를 코어 수에 맞추는 것이 왜 성능에 유리한가
• 우선순위 역전(Priority Inversion) 문제가 게임 엔진에서 발생하는 사례

CPU 스케줄링 원리를 이해하면 고성능 게임 서버 설계에 필요한 판단을 내릴 수 있습니다.

---

1. CPU 스케줄러의 역할

CPU 스케줄러는 준비(Ready) 상태에 있는 프로세스 중 다음에 CPU를 사용할 프로세스를 선택합니다.

프로세스 상태 다이어그램

        [New]
          |
          | (admitted)
          v
        [Ready] <---------- [Waiting]
          |    <--------        |
          | (scheduler         |
          |  dispatch)         | (I/O or event wait)
          v                   |
       [Running] ------------->|
          |
          | (exit)
          v
      [Terminated]

Ready: CPU 사용 가능, 할당 대기 중
Running: 현재 CPU 사용 중
Waiting: I/O 완료 등 이벤트 대기 중

스케줄링 기준 용어

도착 시간(Arrival Time, AT): 프로세스가 Ready 큐에 도착한 시간
버스트 시간(Burst Time, BT): 프로세스가 필요한 CPU 실행 시간
완료 시간(Completion Time, CT): 프로세스 실행 완료 시간
반환 시간(Turnaround Time, TAT): CT - AT (도착부터 완료까지)
대기 시간(Waiting Time, WT): TAT - BT (실제 대기한 시간)
응답 시간(Response Time, RT): 첫 번째 CPU 할당까지 걸린 시간

---

2. 주요 스케줄링 알고리즘

FCFS (First-Come, First-Served)

도착 순서대로 CPU를 할당하는 가장 단순한 알고리즘입니다.

프로세스: P1(BT=24), P2(BT=3), P3(BT=3)  모두 시간 0에 도착

간트 차트:
|------P1(24)------|--P2(3)--|--P3(3)--|
0                 24        27        30

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

문제: 호위 효과(Convoy Effect) — 짧은 프로세스가 긴 프로세스 뒤에서 오래 대기

특징:

• 비선점(Non-preemptive): 실행 중인 프로세스를 중단시키지 않음
• 구현 단순
• 짧은 작업이 긴 작업 뒤에 대기해야 하는 Convoy Effect 발생

SJF (Shortest Job First)

버스트 시간이 가장 짧은 프로세스를 먼저 실행합니다.

프로세스: P1(BT=6, AT=0), P2(BT=8, AT=0), P3(BT=7, AT=0), P4(BT=3, AT=0)

간트 차트 (비선점 SJF):
|--P4(3)--|----P1(6)----|------P3(7)------|--------P2(8)--------|
0         3             9                16                      24

대기 시간:
P1: 3ms, P2: 16ms, P3: 9ms, P4: 0ms
평균 대기 시간: (3+16+9+0)/4 = 7ms  (FCFS 17ms에 비해 훨씬 짧음)

단점: 긴 프로세스는 영원히 실행 안 될 수 있음 (기아 현상, Starvation)
      실제 CPU 버스트 시간을 미리 알 수 없음 (예측 필요)

SRTF (Shortest Remaining Time First): SJF의 선점 버전으로, 새로운 프로세스가 도착할 때마다 남은 시간이 가장 짧은 프로세스로 전환합니다.

Round Robin (RR)

각 프로세스에 동일한 시간 할당량(Time Quantum)을 부여하고 순환 방식으로 실행합니다.

프로세스: P1(BT=24), P2(BT=3), P3(BT=3)  Time Quantum = 4ms

간트 차트:
|P1(4)|P2(3)|P3(3)|P1(4)|P1(4)|P1(4)|P1(4)|P1(4)|
0     4     7    10    14    18    22    26   30

P1 실행 흐름: 4ms -> 대기 -> 4ms -> 대기 -> ... (총 6번으로 나뉘어 완료)
P2, P3: 짧아서 한 번에 완료

대기 시간:
P1: 6ms (10-4 + 14-8 + ...), P2: 4ms, P3: 7ms

Time Quantum 선택의 중요성:

너무 작으면: 컨텍스트 스위칭 오버헤드 증가 (Time Quantum -> 0이면 FCFS처럼 됨 X, 오히려 processor sharing)
너무 크면:  FCFS와 동일해짐 (응답성 저하)

적절한 Time Quantum:
- 일반적으로 10~100ms
- CPU 버스트 시간의 80%보다 커야 효율적

특징:

• 선점 방식 (공정성 보장)
• 타임 쉐어링 시스템에 적합
• 응답 시간이 상대적으로 균등

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

각 프로세스에 우선순위를 부여하고 높은 우선순위 프로세스를 먼저 실행합니다.

프로세스: P1(우선순위=3, BT=10), P2(우선순위=1, BT=1), P3(우선순위=4, BT=2),
          P4(우선순위=5, BT=1), P5(우선순위=2, BT=5)  (숫자가 작을수록 높은 우선순위)

실행 순서: P2(1) -> P5(2) -> P1(3) -> P3(4) -> P4(5)

기아 현상(Starvation) 해결: 에이징(Aging)
-> 오래 대기한 프로세스의 우선순위를 점진적으로 높여줌

---

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

실제 OS(Windows, Linux, macOS)에서 사용하는 방식으로, 여러 단계의 큐와 동적 우선순위를 조합합니다.

Queue 0 (RR, Quantum=8ms)     <- 최고 우선순위
Queue 1 (RR, Quantum=16ms)
Queue 2 (FCFS)                <- 최저 우선순위

규칙:
1. 새 프로세스는 Queue 0에 배치
2. Quantum 안에 완료 안 하면 Queue 1로 강등
3. Queue 1에서도 완료 안 하면 Queue 2로 강등
4. 낮은 큐에서 오래 대기하면 높은 큐로 승격 (에이징)

효과:
- CPU 버스트가 짧은 인터랙티브 프로세스는 빠르게 처리 (Queue 0에서 완료)
- CPU 버스트가 긴 배치 작업은 낮은 큐에서 처리

---

4. 컨텍스트 스위칭 (Context Switching)

CPU가 현재 실행 중인 프로세스에서 다른 프로세스로 전환할 때 발생하는 오버헤드입니다.

컨텍스트 스위칭 과정

컨텍스트(Context): 프로세스의 실행 상태 정보
- CPU 레지스터 값 (PC, SP, 범용 레지스터 등)
- 프로세스 상태
- 메모리 관리 정보 (페이지 테이블 포인터)

스위칭 과정:
1. 현재 프로세스의 컨텍스트를 PCB(Process Control Block)에 저장
2. 다음 프로세스의 PCB에서 컨텍스트 복원
3. CPU가 새 프로세스 실행 재개

비용:
- 레지스터 저장/복원: 수십 나노초
- TLB 플러시 (메모리 매핑 무효화): 수백 나노초
- 캐시 콜드(Cache Cold): 이전 프로세스 데이터가 L1/L2 캐시에서 제거됨
  -> 새 프로세스 시작 시 캐시 미스 급증

스레드 vs 프로세스 컨텍스트 스위칭

프로세스 컨텍스트 스위칭:
- 주소 공간 전환 필요 (CR3 레지스터 변경 -> TLB 전체 플러시)
- 캐시 무효화 심각
- 비용: 수 마이크로초 ~ 수십 마이크로초

스레드 컨텍스트 스위칭 (같은 프로세스 내):
- 주소 공간 공유, TLB 플러시 최소화
- 레지스터 상태만 교체
- 비용: 프로세스 전환의 1/10 ~ 1/5

-> 게임 서버에서 멀티스레딩이 멀티프로세싱보다 효율적인 이유 중 하나

---

5. 우선순위 역전 (Priority Inversion)

높은 우선순위 태스크가 낮은 우선순위 태스크가 점유한 자원을 기다리는 현상입니다.

시나리오:
- Task H (우선순위: 높음)
- Task M (우선순위: 중간)
- Task L (우선순위: 낮음)

시간 흐름:
T1: Task L이 공유 자원(mutex) 획득
T2: Task H 실행 시작, 같은 mutex 필요 -> 대기
T3: Task M이 실행 가능 상태 -> Task M이 Task L을 선점
T4: Task L은 Task M이 완료될 때까지 mutex 해제 못 함
T5: Task H는 Task M, Task L 순으로 완료될 때까지 대기

결과: Task H가 Task M보다 낮은 우선순위처럼 동작 (우선순위 역전)

해결책 — 우선순위 상속 (Priority Inheritance):

Task H가 Task L이 가진 mutex를 기다릴 때,
Task L의 우선순위를 Task H 수준으로 임시 상승
-> Task L이 Task M에 선점되지 않고 빠르게 mutex 해제 가능

실제 사례: 1997년 Mars Pathfinder 탐사선에서
우선순위 역전으로 인한 실시간 운영체제 리셋 버그 발생

---

6. 게임 서버에서의 스레드 설계

스레드 역할 분리

// 게임 서버 스레드 구조 예시

// 1. 네트워크 I/O 스레드 (높은 우선순위)
// - 패킷 수신/발신을 전담
// - 블로킹 없이 빠른 처리
std::thread networkThread([]()
{
    SetThreadPriority(GetCurrentThread(), THREAD_PRIORITY_ABOVE_NORMAL);

    while (IsRunning)
    {
        // 패킷 수신 후 작업 큐에 추가
        auto packet = ReceivePacket();
        gameLogicQueue.Push(packet);
    }
});

// 2. 게임 로직 스레드 (보통 우선순위)
// - 게임 상태 업데이트 전담
// - 고정 틱레이트 유지
std::thread logicThread([]()
{
    const float TICK_RATE = 1.0f / 30.0f;  // 30Hz

    while (IsRunning)
    {
        auto startTime = Now();

        ProcessPendingPackets();
        UpdateGameState(TICK_RATE);
        BroadcastState();

        // 남은 시간만큼 대기 (CPU 낭비 방지)
        SleepUntil(startTime + TICK_RATE);
    }
});

// 3. DB I/O 스레드 (낮은 우선순위)
// - 게임 로직과 분리해 DB 지연이 게임에 영향 없게 함
std::thread dbThread([]()
{
    SetThreadPriority(GetCurrentThread(), THREAD_PRIORITY_BELOW_NORMAL);

    while (IsRunning)
    {
        auto task = dbTaskQueue.Pop();  // 블로킹 대기
        ExecuteDBTask(task);
    }
});

적정 스레드 수

CPU 코어 수 = N이라 할 때:

CPU 바운드 작업 (게임 로직, 물리 연산):
-> 스레드 수 = N (코어 수와 동일)
-> 이유: N개 이상이면 컨텍스트 스위칭 오버헤드만 증가

I/O 바운드 작업 (네트워크, 디스크):
-> 스레드 수 = N * 2 ~ N * 4
-> 이유: I/O 대기 중에 다른 스레드가 CPU 사용 가능

혼합 워크로드:
-> 스레드 수 = N * (1 + I/O 대기 비율 / CPU 사용 비율)

---

7. 실제 OS 스케줄러

Linux CFS (Completely Fair Scheduler)

Linux 2.6.23부터 기본 스케줄러로 사용.
각 프로세스에 "공정한 CPU 시간"을 부여하는 것이 목표.

핵심 개념: vruntime (가상 실행 시간)
- 각 프로세스마다 vruntime 추적
- CPU를 사용할수록 vruntime 증가
- 스케줄러는 항상 vruntime이 가장 작은 프로세스를 실행 (Red-Black 트리)
- 낮은 우선순위(nice 값이 높은) 프로세스는 vruntime이 더 빠르게 증가
  -> 자연스럽게 CPU를 덜 받음

nice 값: -20 (가장 높은 우선순위) ~ +19 (가장 낮은 우선순위)

$ nice -n -10 ./game_server    # 높은 우선순위로 게임 서버 실행
$ renice -n -5 -p <PID>        # 실행 중인 프로세스 우선순위 변경

실시간 스케줄링 정책 (게임 서버에서 활용 가능):
- SCHED_FIFO: 실시간, 선점당하지 않음 (같은 우선순위 내)
- SCHED_RR:   실시간, 타임 퀀텀 후 같은 우선순위 내에서 라운드 로빈
- SCHED_OTHER: 일반 CFS 스케줄링 (기본값)

// C++ 실시간 스케줄링 설정 (Linux, root 권한 필요)
#include <sched.h>
struct sched_param param;
param.sched_priority = 80;  // 1(낮음) ~ 99(높음)
sched_setscheduler(0, SCHED_FIFO, &param);
// 이후 이 스레드는 우선순위 80 이상 스레드에게만 선점됨

Windows 스케줄러

Windows는 32개 우선순위 레벨(0~31)을 사용합니다.
- 0: 시스템 전용 (제로 페이지 스레드)
- 1~15: 동적 우선순위 (일반 프로세스)
- 16~31: 실시간 우선순위 (드라이버, 오디오 등)

우선순위 조정:
- 포그라운드 앱: 우선순위 부스트 적용
- I/O 완료 후: 임시 부스트
- 오래 대기한 스레드: 에이징으로 부스트

// Windows API로 스레드 우선순위 설정
SetThreadPriority(GetCurrentThread(), THREAD_PRIORITY_HIGHEST);
// THREAD_PRIORITY_IDLE          = -15
// THREAD_PRIORITY_LOWEST        = -2
// THREAD_PRIORITY_BELOW_NORMAL  = -1
// THREAD_PRIORITY_NORMAL        =  0
// THREAD_PRIORITY_ABOVE_NORMAL  = +1
// THREAD_PRIORITY_HIGHEST       = +2
// THREAD_PRIORITY_TIME_CRITICAL = +15

// 프로세스 우선순위 클래스
SetPriorityClass(GetCurrentProcess(), HIGH_PRIORITY_CLASS);
// IDLE_PRIORITY_CLASS, BELOW_NORMAL_PRIORITY_CLASS,
// NORMAL_PRIORITY_CLASS (기본), ABOVE_NORMAL_PRIORITY_CLASS,
// HIGH_PRIORITY_CLASS, REALTIME_PRIORITY_CLASS

// 게임 엔진 적용:
// Unreal Engine: 렌더링 스레드 THREAD_PRIORITY_ABOVE_NORMAL
// Unity: 메인 스레드 THREAD_PRIORITY_NORMAL, 로딩 스레드 낮게 설정

---

8. CPU 친화도 (CPU Affinity)

특정 스레드를 특정 CPU 코어에 고정시켜 캐시 재사용률을 높이고 NUMA 효과를 활용할 수 있습니다.

// Windows: 스레드를 코어 0에 고정
DWORD_PTR mask = 1ULL << 0;  // 코어 0만 허용
SetThreadAffinityMask(GetCurrentThread(), mask);

// 게임 서버 활용 예:
// 네트워크 I/O 스레드 -> 코어 0, 1
// 게임 로직 스레드   -> 코어 2, 3, 4, 5
// DB I/O 스레드      -> 코어 6, 7
// -> 각 스레드가 자신의 코어 캐시를 독점적으로 활용

// Linux: pthread_setaffinity_np
#include <pthread.h>
cpu_set_t cpuset;
CPU_ZERO(&cpuset);
CPU_SET(2, &cpuset);  // 코어 2에 고정
pthread_setaffinity_np(pthread_self(), sizeof(cpuset), &cpuset);

// 주의: 과도한 코어 고정은 OS의 부하 분산을 방해할 수 있음
// 벤치마크로 효과 확인 후 적용 권장

---

9. 면접 핵심 정리

CPU 스케줄링이란? 준비 상태의 여러 프로세스 중 다음에 CPU를 사용할 프로세스를 선택하는 과정입니다. 처리량 최대화, 응답 시간 최소화, 공정성 보장 등을 목표로 합니다.

Round Robin 알고리즘이란? 각 프로세스에 동일한 시간 할당량(Time Quantum)을 부여하고 순환 방식으로 CPU를 배분하는 알고리즘입니다. 공정성이 높고 응답 시간이 균등하지만 Time Quantum 크기 선택이 성능에 영향을 줍니다.

컨텍스트 스위칭 비용이란? CPU가 프로세스/스레드를 전환할 때 현재 상태를 저장하고 다음 상태를 복원하는 과정의 오버헤드입니다. 레지스터 저장/복원, TLB 플러시, 캐시 콜드 등이 포함됩니다.

기아 현상(Starvation)이란? 우선순위 스케줄링이나 SJF에서 낮은 우선순위 프로세스가 높은 우선순위 프로세스에 밀려 CPU를 할당받지 못하는 현상입니다. 에이징(Aging)으로 해결합니다.

Linux CFS와 일반 Round Robin의 차이는? CFS는 vruntime(가상 실행 시간)을 기반으로 가장 적게 실행된 프로세스를 선택하는 공정 공유 방식입니다. 고정 Time Quantum이 없고 Red-Black 트리로 O(log n) 스케줄링을 보장합니다.

우선순위 역전(Priority Inversion)이란? 높은 우선순위 태스크가 낮은 우선순위 태스크가 점유한 자원을 기다리는 동안 중간 우선순위 태스크가 끼어드는 현상입니다. 우선순위 상속(Priority Inheritance)으로 해결합니다.

---

참고 자료

• Operating System Concepts (Silberschatz, Galvin, Gagne)
• Linux Completely Fair Scheduler
• Windows Thread Scheduling