고급 스케줄링
고급 스케줄링¶
개요¶
이 레슨에서는 실제 운영체제에서 사용되는 고급 스케줄링 기법을 학습합니다. MLFQ(Multi-Level Feedback Queue), 멀티프로세서 스케줄링, 그리고 실시간 스케줄링에 대해 알아봅니다.
목차¶
1. MLFQ (Multi-Level Feedback Queue)¶
개념¶
MLFQ = 여러 개의 준비 큐를 사용하는 스케줄링
= 프로세스의 행동에 따라 큐 간 이동
= SJF의 장점 + 적응형 스케줄링
┌─────────────────────────────────────────────────────────┐
│ MLFQ 구조 │
├─────────────────────────────────────────────────────────┤
│ │
│ 높은 우선순위 (짧은 Time Quantum) │
│ ┌─────────────────────────────────────────────────┐ │
│ │ Queue 0 (TQ=8ms): P1 → P5 → ... │ ←── 새 프로세스
│ └─────────────────────────────────────────────────┘ │
│ │ │
│ ▼ TQ 소진 시 강등 │
│ ┌─────────────────────────────────────────────────┐ │
│ │ Queue 1 (TQ=16ms): P2 → P7 → ... │ │
│ └─────────────────────────────────────────────────┘ │
│ │ │
│ ▼ TQ 소진 시 강등 │
│ ┌─────────────────────────────────────────────────┐ │
│ │ Queue 2 (TQ=32ms): P3 → P8 → ... │ │
│ └─────────────────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌─────────────────────────────────────────────────┐ │
│ │ Queue N (FCFS): P4 → P6 → ... │ │
│ └─────────────────────────────────────────────────┘ │
│ 낮은 우선순위 (긴 Time Quantum 또는 FCFS) │
│ │
└─────────────────────────────────────────────────────────┘
MLFQ 규칙¶
┌─────────────────────────────────────────────────────────┐
│ MLFQ 기본 규칙 │
├─────────────────────────────────────────────────────────┤
│ │
│ 규칙 1: 우선순위가 높은 프로세스 먼저 실행 │
│ Priority(A) > Priority(B) → A 실행 │
│ │
│ 규칙 2: 우선순위가 같으면 RR 방식 │
│ Priority(A) = Priority(B) → RR │
│ │
│ 규칙 3: 새 프로세스는 최상위 큐에 배치 │
│ 새 프로세스 → Queue 0 │
│ │
│ 규칙 4: 타임 퀀텀을 모두 사용하면 강등 │
│ TQ 소진 → Priority 감소 │
│ │
│ 규칙 5: TQ 전에 CPU를 양보하면 같은 큐 유지 │
│ I/O 요청 등 → 같은 Priority 유지 │
│ │
└─────────────────────────────────────────────────────────┘
MLFQ 동작 예제¶
시나리오: 긴 작업 (CPU-bound)와 짧은 작업 (I/O-bound) 혼합
┌─────────────────────────────────────────────────────────┐
│ 시간 0: 긴 작업 A 도착 │
│ │
│ Q0: [A] ───▶ A 실행 (8ms) │
│ Q1: [] │
│ Q2: [] │
├─────────────────────────────────────────────────────────┤
│ 시간 8: A가 TQ 소진 → 강등 │
│ │
│ Q0: [] │
│ Q1: [A] ───▶ A 실행 (16ms) │
│ Q2: [] │
├─────────────────────────────────────────────────────────┤
│ 시간 10: 짧은 작업 B 도착 (5ms 작업) │
│ │
│ Q0: [B] ───▶ B가 높은 우선순위, A 선점 │
│ Q1: [A] B 실행 시작 │
│ Q2: [] │
├─────────────────────────────────────────────────────────┤
│ 시간 15: B 완료 (TQ 전에 끝남 → I/O 많은 작업으로 간주) │
│ │
│ Q0: [] │
│ Q1: [A] ───▶ A 재개 │
│ Q2: [] │
└─────────────────────────────────────────────────────────┘
결과: 짧은 작업이 먼저 완료됨 (SJF와 유사한 효과)
실행 시간을 모르면서도 짧은 작업 우선 처리 가능
MLFQ 문제점과 해결¶
┌─────────────────────────────────────────────────────────┐
│ MLFQ 문제점과 해결 │
├─────────────────────────────────────────────────────────┤
│ │
│ 문제 1: 기아 (Starvation) │
│ ┌───────────────────────────────────────────────────┐ │
│ │ 높은 우선순위 작업이 계속 도착하면 │ │
│ │ 낮은 큐의 작업은 영원히 실행 안 됨 │ │
│ └───────────────────────────────────────────────────┘ │
│ 해결: Priority Boost │
│ ┌───────────────────────────────────────────────────┐ │
│ │ 주기적으로 모든 프로세스를 최상위 큐로 이동 │ │
│ │ 예: 매 S 시간마다 모든 작업을 Q0으로 │ │
│ └───────────────────────────────────────────────────┘ │
│ │
│ 문제 2: 게이밍 (Gaming the Scheduler) │
│ ┌───────────────────────────────────────────────────┐ │
│ │ 악의적인 프로세스가 TQ 만료 직전에 I/O 요청 │ │
│ │ → 강등 방지, CPU 독점 │ │
│ └───────────────────────────────────────────────────┘ │
│ 해결: 누적 시간 추적 │
│ ┌───────────────────────────────────────────────────┐ │
│ │ 각 레벨에서 사용한 총 시간을 누적 추적 │ │
│ │ 할당량 소진 시 강등 (여러 번에 나눠 쓰더라도) │ │
│ └───────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────┘
MLFQ 파라미터¶
┌─────────────────────────────────────────────────────────┐
│ MLFQ 주요 파라미터 │
├─────────────────────────────────────────────────────────┤
│ │
│ 1. 큐 개수 (Number of queues) │
│ • 일반적으로 3~5개 │
│ • 너무 많으면 오버헤드, 너무 적으면 차별화 부족 │
│ │
│ 2. 각 큐의 Time Quantum │
│ • 보통 2배씩 증가 (8, 16, 32, 64ms...) │
│ • 높은 큐: 짧은 TQ (빠른 응답) │
│ • 낮은 큐: 긴 TQ (컨텍스트 스위치 감소) │
│ │
│ 3. Priority Boost 주기 (S) │
│ • 너무 짧으면: CPU-bound 작업 유리 │
│ • 너무 길면: 기아 발생 │
│ • 일반적으로 1초 ~ 100ms │
│ │
│ Solaris Time-sharing 클래스 예: │
│ ┌─────────┬──────┬──────────┬─────────────┐ │
│ │ Priority │ TQ │ 강등시 │ 승격시 │ │
│ ├─────────┼──────┼──────────┼─────────────┤ │
│ │ 59 │ 20ms │ 54 │ - │ │
│ │ 40 │ 40ms │ 35 │ 45 │ │
│ │ 20 │ 80ms │ 15 │ 25 │ │
│ │ 0 │ 200ms│ 0 │ 5 │ │
│ └─────────┴──────┴──────────┴─────────────┘ │
│ │
└─────────────────────────────────────────────────────────┘
2. 멀티프로세서 스케줄링¶
멀티프로세서 시스템 유형¶
┌─────────────────────────────────────────────────────────┐
│ 멀티프로세서 시스템 유형 │
├─────────────────────────────────────────────────────────┤
│ │
│ 1. SMP (Symmetric Multi-Processing) │
│ ┌───────────────────────────────────────────────────┐ │
│ │ ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ │ │
│ │ │CPU 0│ │CPU 1│ │CPU 2│ │CPU 3│ │ │
│ │ └──┬──┘ └──┬──┘ └──┬──┘ └──┬──┘ │ │
│ │ └───────┴───────┴───────┘ │ │
│ │ │ │ │
│ │ ┌──────┴──────┐ │ │
│ │ │ 공유 메모리 │ │ │
│ │ └─────────────┘ │ │
│ │ 모든 프로세서가 동등, 메모리 공유 │ │
│ └───────────────────────────────────────────────────┘ │
│ │
│ 2. NUMA (Non-Uniform Memory Access) │
│ ┌───────────────────────────────────────────────────┐ │
│ │ ┌─────────────┐ ┌─────────────┐ │ │
│ │ │ CPU 0, 1 │ │ CPU 2, 3 │ │ │
│ │ │ 로컬 메모리 │◀───▶│ 로컬 메모리 │ │ │
│ │ └─────────────┘ └─────────────┘ │ │
│ │ │ │
│ │ 로컬 메모리 접근: 빠름 │ │
│ │ 원격 메모리 접근: 느림 │ │
│ └───────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────┘
스케줄링 접근 방법¶
┌─────────────────────────────────────────────────────────┐
│ 멀티프로세서 스케줄링 접근 방법 │
├─────────────────────────────────────────────────────────┤
│ │
│ 1. 비대칭 멀티프로세싱 (Asymmetric) │
│ ┌───────────────────────────────────────────────────┐ │
│ │ ┌─────────────────┐ │ │
│ │ │ 마스터 프로세서 │ ← 모든 스케줄링 결정 │ │
│ │ │ (CPU 0) │ │ │
│ │ └────────┬────────┘ │ │
│ │ │ 작업 할당 │ │
│ │ ┌─────┼─────┬─────┐ │ │
│ │ ▼ ▼ ▼ ▼ │ │
│ │ ┌─────┐┌─────┐┌─────┐┌─────┐ │ │
│ │ │CPU 1││CPU 2││CPU 3││CPU 4│ ← 슬레이브 │ │
│ │ └─────┘└─────┘└─────┘└─────┘ │ │
│ │ │ │
│ │ 장점: 단순, 데이터 공유 문제 없음 │ │
│ │ 단점: 마스터 병목 │ │
│ └───────────────────────────────────────────────────┘ │
│ │
│ 2. 대칭 멀티프로세싱 (SMP) │
│ ┌───────────────────────────────────────────────────┐ │
│ │ ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ │ │
│ │ │CPU 0│ │CPU 1│ │CPU 2│ │CPU 3│ │ │
│ │ │스케줄││스케줄││스케줄││스케줄│ │ │
│ │ └──┬──┘ └──┬──┘ └──┬──┘ └──┬──┘ │ │
│ │ └───────┴───┬───┴───────┘ │ │
│ │ ▼ │ │
│ │ ┌──────────────┐ │ │
│ │ │ 공유 Ready │ (동기화 필요) │ │
│ │ │ Queue │ │ │
│ │ └──────────────┘ │ │
│ │ 또는: 각 CPU가 자체 Ready Queue 유지 │ │
│ │ │ │
│ │ 장점: 확장성, 병목 없음 │ │
│ │ 단점: 동기화 복잡, 부하 불균형 가능 │ │
│ └───────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────┘
부하 분산 (Load Balancing)¶
┌─────────────────────────────────────────────────────────┐
│ 부하 분산 기법 │
├─────────────────────────────────────────────────────────┤
│ │
│ 문제: 각 CPU가 별도 큐를 가질 때 부하 불균형 발생 │
│ │
│ CPU 0: ████████ CPU 1: ██ CPU 2: ████████████ │
│ (과부하) (유휴) (과부하) │
│ │
│ 해결책 1: Push Migration (밀어내기) │
│ ┌───────────────────────────────────────────────────┐ │
│ │ 주기적으로 각 큐의 부하 검사 │ │
│ │ 과부하 큐 → 유휴 큐로 프로세스 이동 │ │
│ │ │ │
│ │ CPU 0: ████████ ──push──▶ CPU 1: ██ │ │
│ │ 결과: █████ █████ │ │
│ └───────────────────────────────────────────────────┘ │
│ │
│ 해결책 2: Pull Migration (끌어오기) │
│ ┌───────────────────────────────────────────────────┐ │
│ │ 유휴 CPU가 다른 CPU에서 작업을 가져옴 │ │
│ │ │ │
│ │ CPU 0: ████████ ◀──pull── CPU 1: (유휴) │ │
│ │ 결과: █████ ███ │ │
│ └───────────────────────────────────────────────────┘ │
│ │
│ Linux: 둘 다 사용 │
│ • 주기적 Push (rebalance 작업) │
│ • 유휴 시 Pull (idle_balance) │
│ │
└─────────────────────────────────────────────────────────┘
3. 프로세서 친화성¶
프로세서 친화성이란?¶
┌─────────────────────────────────────────────────────────┐
│ 프로세서 친화성 (Processor Affinity) │
├─────────────────────────────────────────────────────────┤
│ │
│ 정의: 프로세스가 특정 CPU에서 계속 실행되도록 하는 것 │
│ │
│ 이유: 캐시 효율 │
│ ┌───────────────────────────────────────────────────┐ │
│ │ 프로세스 P가 CPU 0에서 실행 │ │
│ │ → CPU 0의 캐시에 P의 데이터 적재 │ │
│ │ │ │
│ │ P가 다른 CPU로 이동하면: │ │
│ │ • CPU 0 캐시: P 데이터 무효화 │ │
│ │ • CPU 1 캐시: P 데이터 다시 적재 필요 │ │
│ │ → 캐시 미스 증가, 성능 저하 │ │
│ └───────────────────────────────────────────────────┘ │
│ │
│ 캐시 상태 시각화: │
│ │
│ CPU 0 CPU 1 CPU 0 CPU 1 │
│ ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ │
│ │캐시 │ │캐시 │ │캐시 │ │캐시 │ │
│ │[P의 │ │[ ]│ 이동 │[ ]│ │[P의 │ │
│ │데이터│ │ │ ───▶ │ │ │데이터│ │
│ └─────┘ └─────┘ └─────┘ └─────┘ │
│ ↑ 따뜻함 차가움 차가움 ↑ 다시 적재 │
│ │
└─────────────────────────────────────────────────────────┘
친화성 유형¶
┌─────────────────────────────────────────────────────────┐
│ 친화성 유형 │
├─────────────────────────────────────────────────────────┤
│ │
│ 1. 소프트 친화성 (Soft Affinity) │
│ ┌───────────────────────────────────────────────────┐ │
│ │ • 기본 동작: 같은 CPU에서 실행하려고 노력 │ │
│ │ • 부하 분산이 필요하면 이동 가능 │ │
│ │ • Linux 기본 동작 │ │
│ └───────────────────────────────────────────────────┘ │
│ │
│ 2. 하드 친화성 (Hard Affinity) │
│ ┌───────────────────────────────────────────────────┐ │
│ │ • 프로세스를 특정 CPU 집합에 고정 │ │
│ │ • 부하 분산에도 이동 안 함 │ │
│ │ • 시스템 호출로 설정 │ │
│ └───────────────────────────────────────────────────┘ │
│ │
│ Linux에서 설정: │
│ ```c │
│ #define _GNU_SOURCE │
│ #include <sched.h> │
│ │
│ cpu_set_t mask; │
│ CPU_ZERO(&mask); │
│ CPU_SET(0, &mask); // CPU 0에만 실행 │
│ CPU_SET(2, &mask); // CPU 2에도 실행 가능 │
│ │
│ // 현재 프로세스의 친화성 설정 │
│ sched_setaffinity(0, sizeof(mask), &mask); │
│ ``` │
│ │
│ 명령어: │
│ ```bash │
│ # CPU 0,1에서만 실행 │
│ taskset -c 0,1 ./program │
│ │
│ # 실행 중인 프로세스 친화성 변경 │
│ taskset -c 2,3 -p PID │
│ ``` │
│ │
└─────────────────────────────────────────────────────────┘
4. 실시간 스케줄링¶
실시간 시스템 개요¶
┌─────────────────────────────────────────────────────────┐
│ 실시간 시스템 개요 │
├─────────────────────────────────────────────────────────┤
│ │
│ 실시간 시스템 = 시간 제약 (Deadline)이 있는 시스템 │
│ │
│ 분류: │
│ ┌───────────────────────────────────────────────────┐ │
│ │ 경성 실시간 (Hard Real-Time) │ │
│ │ • 마감시간 위반 = 시스템 실패 │ │
│ │ • 예: 항공 제어, 의료 기기, ABS 브레이크 │ │
│ │ • 마감시간 보장 필수 │ │
│ └───────────────────────────────────────────────────┘ │
│ ┌───────────────────────────────────────────────────┐ │
│ │ 연성 실시간 (Soft Real-Time) │ │
│ │ • 마감시간 위반 = 성능 저하 │ │
│ │ • 예: 비디오 스트리밍, 게임, VoIP │ │
│ │ • 대부분의 마감시간 충족 목표 │ │
│ └───────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────┘
실시간 태스크 특성¶
┌─────────────────────────────────────────────────────────┐
│ 실시간 태스크 특성 │
├─────────────────────────────────────────────────────────┤
│ │
│ 주기적 태스크 (Periodic Task): │
│ │
│ 시간 ────────────────────────────────────────────▶ │
│ │←── 주기(Period) P ──→│←── 주기(Period) P ──→│ │
│ ┌───┐ ┌───┐ ┌───┐ │
│ │ C │ │ C │ │ C │ │
│ └───┘ └───┘ └───┘ │
│ ↑ ↑ ↑ ↑ │
│ 도착 마감시간(D) 도착 마감시간(D) │
│ │
│ 파라미터: │
│ • P (Period): 태스크가 반복되는 주기 │
│ • C (Computation time): 실행 시간 │
│ • D (Deadline): 완료해야 하는 시간 │
│ • 이용률 U = C/P │
│ │
│ 예시: 비디오 프레임 │
│ • P = 33ms (30fps) │
│ • C = 10ms (프레임 처리 시간) │
│ • D = 33ms │
│ • U = 10/33 ≈ 0.3 (30%) │
│ │
└─────────────────────────────────────────────────────────┘
Rate Monotonic Scheduling (RMS)¶
┌─────────────────────────────────────────────────────────┐
│ Rate Monotonic Scheduling (RMS) │
├─────────────────────────────────────────────────────────┤
│ │
│ 원리: 주기가 짧은 태스크 = 높은 우선순위 │
│ (Rate = 1/Period, 더 높은 Rate = 높은 우선순위) │
│ │
│ 특징: │
│ • 정적 우선순위 (고정) │
│ • 선점형 │
│ • 최적 (정적 우선순위 중) │
│ │
│ 예제: │
│ ┌─────────┬───────┬────────┬──────────┐ │
│ │ 태스크 │ 주기 P │ 실행 C │ 우선순위 │ │
│ ├─────────┼───────┼────────┼──────────┤ │
│ │ T1 │ 50 │ 20 │ 높음 │ │
│ │ T2 │ 100 │ 35 │ 낮음 │ │
│ └─────────┴───────┴────────┴──────────┘ │
│ │
│ 간트 차트: │
│ ┌──────────┬──────────────┬──────────┬─────────────┐ │
│ │ T1 │ T2 │ T1 │ T2(계속) │ │
│ └──────────┴──────────────┴──────────┴─────────────┘ │
│ 0 20 55 75 100 │
│ T2 시작 T1 재도착(선점) T2 재개 │
│ │
│ 스케줄 가능 조건: │
│ 총 이용률 ≤ n(2^(1/n) - 1) │
│ • n=1: 100% │
│ • n=2: 약 82.8% │
│ • n→∞: 약 69.3% │
│ │
│ 위 예제: U = 20/50 + 35/100 = 0.4 + 0.35 = 0.75 │
│ 0.75 < 0.828 → 스케줄 가능 │
│ │
└─────────────────────────────────────────────────────────┘
Earliest Deadline First (EDF)¶
┌─────────────────────────────────────────────────────────┐
│ Earliest Deadline First (EDF) │
├─────────────────────────────────────────────────────────┤
│ │
│ 원리: 마감시간이 가장 가까운 태스크 = 최고 우선순위 │
│ │
│ 특징: │
│ • 동적 우선순위 (마감시간에 따라 변경) │
│ • 선점형 │
│ • 이론적으로 최적 (이용률 100%까지 가능) │
│ │
│ 예제 (RMS와 동일 데이터): │
│ ┌─────────┬───────┬────────┬────────────────┐ │
│ │ 태스크 │ 주기 P │ 실행 C │ 마감시간 D │ │
│ ├─────────┼───────┼────────┼────────────────┤ │
│ │ T1 │ 50 │ 20 │ 50, 100, 150...│ │
│ │ T2 │ 100 │ 35 │ 100, 200... │ │
│ └─────────┴───────┴────────┴────────────────┘ │
│ │
│ 시간 0: │
│ • T1 마감: 50, T2 마감: 100 │
│ • T1 우선 실행 │
│ │
│ 시간 50 (T1 두번째 인스턴스): │
│ • T1 마감: 100, T2 마감: 100 (같음) │
│ • 동률 → 임의 선택 또는 다른 기준 │
│ │
│ RMS vs EDF: │
│ ┌──────────────┬────────────────┬─────────────────┐ │
│ │ 특성 │ RMS │ EDF │ │
│ ├──────────────┼────────────────┼─────────────────┤ │
│ │ 우선순위 │ 정적 │ 동적 │ │
│ │ 최대 이용률 │ ~69% (n→∞) │ 100% │ │
│ │ 구현 복잡도 │ 낮음 │ 높음 │ │
│ │ 오버헤드 │ 낮음 │ 높음 │ │
│ │ 과부하 시 │ 예측 가능 │ 도미노 효과 │ │
│ └──────────────┴────────────────┴─────────────────┘ │
│ │
└─────────────────────────────────────────────────────────┘
5. Linux CFS¶
CFS 개요¶
┌─────────────────────────────────────────────────────────┐
│ CFS (Completely Fair Scheduler) │
├─────────────────────────────────────────────────────────┤
│ │
│ Linux 2.6.23부터 기본 스케줄러 (2007년~) │
│ │
│ 핵심 아이디어: │
│ • 모든 프로세스에게 공정하게 CPU 시간 분배 │
│ • 가상 런타임 (virtual runtime)으로 공정성 추적 │
│ • Red-Black 트리로 효율적 관리 │
│ │
│ 가상 런타임 (vruntime): │
│ • 프로세스가 CPU를 사용한 가중 시간 │
│ • 우선순위가 높으면 천천히 증가 │
│ • 우선순위가 낮으면 빠르게 증가 │
│ │
│ 스케줄링 결정: │
│ • 항상 vruntime이 가장 작은 프로세스 선택 │
│ • = 가장 덜 실행된 프로세스 │
│ │
└─────────────────────────────────────────────────────────┘
CFS 동작 방식¶
┌─────────────────────────────────────────────────────────┐
│ CFS 동작 방식 │
├─────────────────────────────────────────────────────────┤
│ │
│ Red-Black 트리 (vruntime 기준 정렬): │
│ │
│ ┌───────┐ │
│ │ P2:50 │ │
│ └───┬───┘ │
│ ┌─────────┴─────────┐ │
│ ┌───────┐ ┌───────┐ │
│ │ P1:30 │ │ P3:80 │ │
│ └───┬───┘ └───┬───┘ │
│ ┌─────┴─────┐ ┌─────┴─────┐ │
│ ┌───────┐ ┌───────┐ ┌───────┐ ┌───────┐ │
│ │ P4:10 │ │ P5:40 │ │ P6:70 │ │ P7:100│ │
│ └───────┘ └───────┘ └───────┘ └───────┘ │
│ ↑ │
│ 가장 왼쪽 = 가장 작은 vruntime = 다음 실행 │
│ │
│ 시간이 지나면: │
│ 1. P4 실행, vruntime 증가 (10 → 25) │
│ 2. P4가 더 이상 최소가 아니면 다른 프로세스로 전환 │
│ 3. 트리 재구성, 새로운 최소 선택 │
│ │
└─────────────────────────────────────────────────────────┘
CFS 타임슬라이스 계산¶
┌─────────────────────────────────────────────────────────┐
│ CFS 타임슬라이스 계산 │
├─────────────────────────────────────────────────────────┤
│ │
│ CFS는 고정 타임슬라이스 대신 목표 지연 시간 사용 │
│ │
│ 목표 지연 (Target Latency): 기본 6ms (조정 가능) │
│ │
│ 계산: │
│ 각 프로세스의 타임슬라이스 = 목표 지연 × (가중치/총가중치)│
│ │
│ 예시 (n=3, 같은 우선순위): │
│ ┌───────────────────────────────────────────────────┐ │
│ │ 목표 지연 = 6ms │ │
│ │ 각 프로세스 가중치 = 1024 (nice 0) │ │
│ │ 총 가중치 = 1024 × 3 = 3072 │ │
│ │ │ │
│ │ 각 타임슬라이스 = 6ms × (1024/3072) = 2ms │ │
│ └───────────────────────────────────────────────────┘ │
│ │
│ 예시 (다른 우선순위): │
│ ┌───────────────────────────────────────────────────┐ │
│ │ P1: nice -5 (가중치 3121) │ │
│ │ P2: nice 0 (가중치 1024) │ │
│ │ P3: nice 5 (가중치 335) │ │
│ │ 총 가중치 = 4480 │ │
│ │ │ │
│ │ P1 타임슬라이스 = 6ms × (3121/4480) ≈ 4.2ms │ │
│ │ P2 타임슬라이스 = 6ms × (1024/4480) ≈ 1.4ms │ │
│ │ P3 타임슬라이스 = 6ms × (335/4480) ≈ 0.4ms │ │
│ └───────────────────────────────────────────────────┘ │
│ │
│ Nice 값과 가중치: │
│ • nice -20 (최고): 가중치 88761 │
│ • nice 0 (기본): 가중치 1024 │
│ • nice 19 (최저): 가중치 15 │
│ • 약 10% 차이 당 nice 1 차이 │
│ │
└─────────────────────────────────────────────────────────┘
6. 연습 문제¶
문제 1: MLFQ¶
3개의 큐를 가진 MLFQ 시스템에서: - Q0: TQ=4ms - Q1: TQ=8ms - Q2: FCFS
프로세스 A(CPU-bound, 30ms 작업)와 프로세스 B(I/O-bound, 3ms CPU + I/O 반복)가 동시에 도착했을 때, 처음 20ms 동안의 실행을 설명하세요.
정답 보기
**초기 상태:** - Q0: [A, B] - Q1: [] - Q2: [] **시간 0-3ms:** B 실행 (3ms), I/O 요청 → B는 Q0에 남음 **시간 3-7ms:** A 실행 (4ms), TQ 소진 → A는 Q1로 강등 **시간 7-10ms:** B가 I/O 완료 후 도착, B 실행 (3ms) **시간 10-18ms:** A 실행 (8ms), TQ 소진 → A는 Q2로 강등 **시간 18-20ms:** B가 돌아왔다면 B 실행... **결과:** - B는 짧은 작업으로 높은 큐에서 빠르게 서비스됨 - A는 점점 낮은 큐로 이동하여 긴 타임슬라이스 사용문제 2: RMS 스케줄 가능성¶
다음 태스크 집합이 RMS로 스케줄 가능한지 확인하세요.
| 태스크 | 주기 (P) | 실행 시간 (C) |
|---|---|---|
| T1 | 100 | 20 |
| T2 | 150 | 30 |
| T3 | 350 | 80 |
정답 보기
**총 이용률 계산:** - U1 = 20/100 = 0.20 - U2 = 30/150 = 0.20 - U3 = 80/350 = 0.23 **총 U = 0.20 + 0.20 + 0.23 = 0.63** **RMS 스케줄 가능 조건 (n=3):** - 한계 = 3 × (2^(1/3) - 1) = 3 × 0.26 = 0.78 **결론:** - 0.63 < 0.78 - **스케줄 가능**문제 3: 프로세서 친화성¶
소프트 친화성과 하드 친화성의 차이를 설명하고, 각각이 적합한 상황을 예시와 함께 설명하세요.
정답 보기
**소프트 친화성:** - 정의: OS가 프로세스를 같은 CPU에서 실행하려고 노력하지만, 부하 분산이 필요하면 이동 가능 - 적합한 상황: - 일반적인 응용 프로그램 - 캐시 효율과 부하 분산 균형이 필요한 경우 - 예: 웹 서버, 데이터베이스 **하드 친화성:** - 정의: 프로세스가 특정 CPU 집합에서만 실행되도록 강제 - 적합한 상황: - 실시간 시스템 (예측 가능한 성능 필요) - NUMA 시스템에서 로컬 메모리 접근 최적화 - 특정 CPU 코어 전용 할당 - 예: 게임 서버의 물리 엔진 스레드, 고빈도 트레이딩 시스템문제 4: EDF vs RMS¶
다음 태스크 집합에 대해 RMS와 EDF를 비교하세요.
| 태스크 | 주기 | 실행 시간 |
|---|---|---|
| T1 | 4 | 1 |
| T2 | 5 | 2 |
| T3 | 10 | 3 |
정답 보기
**이용률:** - U = 1/4 + 2/5 + 3/10 = 0.25 + 0.4 + 0.3 = 0.95 **RMS 분석:** - 한계 = 3 × (2^(1/3) - 1) ≈ 0.78 - 0.95 > 0.78 → RMS로 보장되지 않음 - (실제로는 스케줄 가능할 수도 있지만 보장 안 됨) **EDF 분석:** - 한계 = 1.0 (100%) - 0.95 < 1.0 → EDF로 스케줄 가능! **결론:** - 이 태스크 집합은 RMS로는 스케줄 가능성이 보장되지 않지만 - EDF로는 스케줄 가능문제 5: Linux CFS¶
nice 값이 0인 프로세스 A와 nice 값이 5인 프로세스 B가 있을 때, A가 B보다 얼마나 더 많은 CPU 시간을 받는지 계산하세요.
정답 보기
**가중치 (근사값):** - nice 0: 가중치 1024 - nice 5: 가중치 약 335 (nice 1 차이당 약 1.25배) **CPU 시간 비율:** - A의 비율 = 1024 / (1024 + 335) = 1024 / 1359 ≈ 0.753 (75.3%) - B의 비율 = 335 / 1359 ≈ 0.247 (24.7%) **A는 B보다 약 3배 더 많은 CPU 시간을 받음** (정확한 비율: 1024/335 ≈ 3.06배)다음 단계¶
- 07_Synchronization_Basics.md - 경쟁 상태와 임계 구역