운영체제 — 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. 면접 핵심 정리

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

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

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

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

---

참고 자료

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