[OS] CPU 스케쥴링 (CPU Scheduling)

 

3️⃣ CPU 스케줄링 (CPU Scheduling)

✅ 왜 스케줄링이 필요한가?

컴퓨터 시스템은 멀티태스킹 환경에서 여러 프로세스가 동시에 실행되는 것처럼 보이지만, 실제로는 한정된 CPU가 프로세스를 순차적으로 실행합니다. 따라서 운영체제는 어떤 프로세스가 언제 CPU를 차지할지 결정해야 합니다. 이게 바로 스케줄링이에요.

---

✅ 스케줄링 시점

• Non-preemptive (비선점):
  • 현재 실행 중인 프로세스가 CPU를 자발적으로 내놓을 때만 스위칭.
• Preemptive (선점형):
  • OS가 강제로 CPU를 회수하여 다른 프로세스에 할당 가능.

대부분의 현대 OS는 선점형 스케줄링을 사용합니다.

---

✅ 주요 스케줄링 알고리즘

알고리즘 설명 특징

FCFS (First-Come First-Served)	먼저 도착한 프로세스부터 순차 실행	구현 간단 / 긴 대기시간 발생 가능
SJF (Shortest Job First)	실행 시간이 가장 짧은 프로세스를 우선 실행	평균 대기시간 최소 / 실행 시간 예측 필요
Priority Scheduling	우선순위 높은 프로세스부터 실행	기아(Starvation) 문제 발생 가능
Round Robin (RR)	고정된 시간 할당(Quantum) 후 선점하여 순환	응답 시간 개선 / Context Switch 오버헤드 발생
Multilevel Queue	여러 큐로 분류(예: 상호작용/배치) 후 각 큐 별 알고리즘 적용	복잡한 환경 최적화 가능
Multilevel Feedback Queue	우선순위 큐 + 동적 이동 (실행 패턴에 따라 큐 위치가 바뀜)	매우 유연 / 구현 복잡

---

✅ 평가 지표

• CPU Utilization (CPU 이용률): 얼마나 CPU가 바쁘게 일하는지.
• Throughput (처리량): 단위 시간당 완료된 프로세스 수.
• Turnaround Time (반환 시간): 프로세스 제출 → 완료까지 걸린 시간.
• Waiting Time (대기 시간): 프로세스가 Ready 상태로 기다린 총 시간.
• Response Time (응답 시간): 프로세스 제출 → 첫 응답까지의 시간.

👉 이 지표들은 서로 Trade-off 관계가 있으므로 OS의 목적에 따라 우선순위가 달라집니다.

🔎 스케줄링 평가 지표 간의 연관 공식

다음 3가지가 서로 밀접하게 연결되어 있습니다:

1️⃣ Turnaround Time (반환 시간)
2️⃣ Waiting Time (대기 시간)
3️⃣ Burst Time (실행 시간)

---

✅ 공식 ①

Turnaround Time (TAT)

Turnaround Time=Completion Time−Arrival Time\text{Turnaround Time} = \text{Completion Time} - \text{Arrival Time}

즉, 프로세스가 들어온 시점부터 끝나는 시점까지 전체 소요 시간입니다.

---

✅ 공식 ②

Waiting Time (WT)

Waiting Time=Turnaround Time−Burst Time\text{Waiting Time} = \text{Turnaround Time} - \text{Burst Time}

• Burst Time (BT): CPU에서 실제로 실행된 시간.

따라서:

WT=(CT−AT)−BTWT = (CT - AT) - BT

👉 이 공식은 대기 시간 = 전체 걸린 시간 - 실제 실행 시간이라는 의미예요.

---

✅ 공식 ③

Response Time (RT)

Response Time=First CPU Start Time−Arrival Time\text{Response Time} = \text{First CPU Start Time} - \text{Arrival Time}

Round Robin 등에서는 Response Time이 중요하며, 첫 응답 시점을 측정합니다.

---

✅ 정리된 공식 관계

지표 공식

Turnaround Time (TAT)	Completion Time (CT) - Arrival Time (AT)
Waiting Time (WT)	Turnaround Time (TAT) - Burst Time (BT)
Response Time (RT)	First Execution Start Time - Arrival Time (AT)

---

예제 👀

프로세스: P1 (AT=0, BT=5)

• CT = 10
• AT = 0
• BT = 5
• TAT = 10 - 0 = 10
• WT = 10 - 5 = 5
• (만약 첫 실행이 3초에 시작했다면) RT = 3 - 0 = 3

---

✅ 결론

평가지표들은 서로 긴밀하게 연결되어 있어, 한 지표만 알면 나머지를 유추할 수 있습니다. 다만, 스케줄링 정책이나 프로세스 간 선점 여부에 따라 값이 달라질 뿐, 기본 공식은 일정합니다.

---

✅ 심화: 다중 프로세서 스케줄링

멀티코어 환경에서는 스케줄링이 더 복잡해집니다.

• 대칭형 (SMP): 모든 CPU가 OS의 스케줄링 알고리즘을 공유.
• 비대칭형 (AMP): 한 CPU가 스케줄링만 담당.

Load Balancing: 각 CPU에 작업을 고르게 분배해야 병목을 방지할 수 있음.

 

🔥 다중 프로세서 스케줄링의 Load Balancing

목표:
CPU가 여러 개 있을 때 특정 프로세서만 과부하 걸리는 걸 방지하고, 작업을 고르게 분산하여 전체 시스템 효율을 높이는 것.

---

✅ Load Balancing 방식

1️⃣ Central Queue 방식

• 설명: 모든 CPU가 하나의 공통 큐에서 작업을 가져감.
• 장점: 자연스럽게 부하가 균형을 이룸.
• 단점: 큐 자체가 병목이 될 수 있음 (Lock 경쟁).

예: 단순한 멀티코어 OS, 예제 수준의 스케줄러.

---

2️⃣ Local Queue + Work Stealing 방식

• 설명: 각 CPU는 자신만의 로컬 큐를 가지고 작업을 관리.
  부하가 한쪽에 몰리면 작업이 없는 CPU가 다른 CPU에서 작업을 "훔쳐옴".
• 장점: 병렬성이 뛰어나고 큐 병목이 줄어듦.
• 단점: Stealing 시 약간의 오버헤드 발생.

예:

• Linux CFS (Completely Fair Scheduler)에서 NUMA-aware 로드 밸런싱 시.
• 멀티스레딩 라이브러리(TBB, Go 런타임 등).

---

3️⃣ Periodic Balancing (주기적 균형 재조정)

• 설명: 스케줄러가 일정 시간마다 CPU별 로드 상태를 점검하고 불균형 시 프로세스를 재배치.
• 장점: 단순하지만 안정적.
• 단점: 너무 잦으면 오버헤드 발생.

---

4️⃣ Push vs Pull 전략

• Push:
  • 과부하가 걸린 CPU가 스스로 일부 작업을 다른 CPU로 밀어냄.
• Pull:
  • 빈 CPU가 적극적으로 다른 CPU에서 작업을 가져옴.

현대 OS들은 보통 Push + Pull 혼합 전략을 씁니다.

---

✅ 심화 예시: Linux CFS

• 다중 러너블 큐 (Per-CPU Runqueue)
• Idle CPU는 Steal 우선 / 부하 심하면 Push도 수행
• NUMA 환경에선 메모리 locality도 고려

---

✅ 간단 비교표

방식 특징

Central Queue	단순 / 병목 발생 가능
Local Queue + Stealing	고성능 / 구현 복잡
Periodic Balancing	간단 / 자주 하면 오버헤드
Push / Pull	균형 감시 / 유연한 분산

---

👉 정리: 현대의 다중 프로세서 스케줄러는 Local Queue + Work Stealing + Periodic Rebalance 같은 복합적인 방식을 채택해 높은 병렬성과 효율을 추구합니다.

---

✅ 심화: 실시간 스케줄링

실시간 시스템은 데드라인이 핵심입니다.

• Hard Real-Time: 데드라인 미스 절대 금지 (항공, 의료).
• Soft Real-Time: 데드라인 미스 가능하지만 성능 저하 (멀티미디어).

알고리즘:

• Rate Monotonic (RM)
• Earliest Deadline First (EDF)

---

🛠 간단한 Round Robin 예시 (C++)

#include <iostream>
#include <queue>

struct Process {
    int id;
    int burst;
};

int main() {
    std::queue<Process> q;
    q.push({1, 5});
    q.push({2, 10});
    q.push({3, 7});

    int quantum = 3;

    while (!q.empty()) {
        Process p = q.front(); q.pop();
        if (p.burst > quantum) {
            std::cout << "Process " << p.id << " runs for " << quantum << "\n";
            p.burst -= quantum;
            q.push(p);
        } else {
            std::cout << "Process " << p.id << " finishes\n";
        }
    }
}

---

✅ 스케줄링의 핵심 요약

• 선점형 스케줄링은 컨텍스트 스위치를 동반하며 응답성이 좋음.
• 알고리즘 선택은 시스템의 특성(대화형? 배치형? 실시간?)에 따라 달라짐.
• 현대 OS들은 대개 Multilevel Feedback Queue 같은 복합 스케줄러를 사용.