스케줄링 알고리즘
스케줄링 알고리즘¶
개요¶
이 레슨에서는 다양한 CPU 스케줄링 알고리즘을 학습합니다. FCFS, SJF, SRTF, Priority, Round Robin 알고리즘의 동작 원리를 이해하고, 간트 차트를 통해 평균 대기 시간과 총 처리 시간을 계산합니다.
목차¶
- FCFS (First-Come, First-Served)
- SJF (Shortest Job First)
- SRTF (Shortest Remaining Time First)
- Priority Scheduling
- Round Robin
- 알고리즘 비교
- 연습 문제
1. FCFS (First-Come, First-Served)¶
개념¶
FCFS = 먼저 도착한 프로세스를 먼저 처리
= 가장 간단한 스케줄링 알고리즘
= 비선점 (Non-preemptive)
┌─────────────────────────────────────────────────────────┐
│ FCFS 동작 │
├─────────────────────────────────────────────────────────┤
│ │
│ Ready Queue (FIFO): │
│ ┌───┐ ┌───┐ ┌───┐ ┌───┐ │
│ │P1 │ → │P2 │ → │P3 │ → │P4 │ → CPU │
│ └───┘ └───┘ └───┘ └───┘ │
│ 먼저 두번째 세번째 네번째 │
│ 도착 도착 도착 도착 │
│ │
│ 실행 순서: P1 → P2 → P3 → P4 │
│ │
└─────────────────────────────────────────────────────────┘
예제 1: 기본¶
입력:
┌──────────┬───────────┬───────────┐
│ 프로세스 │ 도착 시간 │ 실행 시간 │
├──────────┼───────────┼───────────┤
│ P1 │ 0 │ 24 │
│ P2 │ 0 │ 3 │
│ P3 │ 0 │ 3 │
└──────────┴───────────┴───────────┘
간트 차트 (순서: P1 → P2 → P3):
┌────────────────────────────────────┬──────┬──────┐
│ P1 │ P2 │ P3 │
└────────────────────────────────────┴──────┴──────┘
0 24 27 30
계산:
┌──────────┬────────────┬───────────────────────┐
│ 프로세스 │ 대기 시간 │ 총 처리 시간 │
├──────────┼────────────┼───────────────────────┤
│ P1 │ 0 │ 24 - 0 = 24 │
│ P2 │ 24 │ 27 - 0 = 27 │
│ P3 │ 27 │ 30 - 0 = 30 │
├──────────┼────────────┼───────────────────────┤
│ 평균 │ (0+24+27)/3 = 17 │ (24+27+30)/3 = 27│
└──────────┴────────────┴───────────────────────┘
Convoy Effect (호위 효과)¶
┌─────────────────────────────────────────────────────────┐
│ Convoy Effect │
├─────────────────────────────────────────────────────────┤
│ │
│ 긴 프로세스가 먼저 도착하면: │
│ ┌────────────────────────┬──┬──┬──┐ │
│ │ P1 (긴 작업) │P2│P3│P4│ │
│ └────────────────────────┴──┴──┴──┘ │
│ 0 100 │
│ │
│ 짧은 프로세스들이 긴 프로세스를 기다림 │
│ → 평균 대기 시간 크게 증가 │
│ │
│ 만약 순서가 바뀌었다면 (P2, P3, P4, P1): │
│ ┌──┬──┬──┬────────────────────────┐ │
│ │P2│P3│P4│ P1 (긴 작업) │ │
│ └──┴──┴──┴────────────────────────┘ │
│ 0 3 6 9 109 │
│ │
│ 짧은 작업들이 빠르게 완료됨 │
│ → 평균 대기 시간 감소 │
│ │
└─────────────────────────────────────────────────────────┘
FCFS 특징¶
┌──────────┬─────────────────────────────────────────────┐
│ 장점 │ • 구현이 매우 간단 (FIFO 큐) │
│ │ • 기아(Starvation) 없음 │
│ │ • 공정함 (먼저 온 순서대로) │
├──────────┼─────────────────────────────────────────────┤
│ 단점 │ • Convoy Effect 발생 가능 │
│ │ • 평균 대기 시간이 길어질 수 있음 │
│ │ • I/O-bound 프로세스에 불리 │
├──────────┼─────────────────────────────────────────────┤
│ 적합한 상황│ • 모든 프로세스의 실행 시간이 비슷한 경우 │
│ │ • 배치 시스템 │
└──────────┴─────────────────────────────────────────────┘
2. SJF (Shortest Job First)¶
개념¶
SJF = 실행 시간이 가장 짧은 프로세스를 먼저 실행
= 최적의 평균 대기 시간 제공 (비선점 경우)
= 비선점 (Non-preemptive)
┌─────────────────────────────────────────────────────────┐
│ SJF 동작 │
├─────────────────────────────────────────────────────────┤
│ │
│ Ready Queue에서 실행 시간이 가장 짧은 것 선택: │
│ │
│ ┌───┐ ┌───┐ ┌───┐ ┌───┐ │
│ │P1 │ │P2 │ │P3 │ │P4 │ │
│ │24 │ │ 3 │ │ 3 │ │ 5 │ ← 실행 시간 │
│ └───┘ └───┘ └───┘ └───┘ │
│ │
│ 선택 순서: P2(3) → P3(3) → P4(5) → P1(24) │
│ │
└─────────────────────────────────────────────────────────┘
예제 2: SJF 비선점¶
입력:
┌──────────┬───────────┬───────────┐
│ 프로세스 │ 도착 시간 │ 실행 시간 │
├──────────┼───────────┼───────────┤
│ P1 │ 0 │ 6 │
│ P2 │ 2 │ 8 │
│ P3 │ 4 │ 7 │
│ P4 │ 5 │ 3 │
└──────────┴───────────┴───────────┘
간트 차트:
시간 0: P1만 도착 → P1 실행
시간 6: P1 완료, P2,P3,P4 중 가장 짧은 P4 선택
시간 9: P4 완료, P2,P3 중 가장 짧은 P3 선택
시간 16: P3 완료, P2 실행
시간 24: P2 완료
┌──────────┬─────┬──────────┬────────────┐
│ P1 │ P4 │ P3 │ P2 │
└──────────┴─────┴──────────┴────────────┘
0 6 9 16 24
계산:
┌──────────┬─────────────────────────┬───────────────────────┐
│ 프로세스 │ 대기 시간 │ 총 처리 시간 │
├──────────┼─────────────────────────┼───────────────────────┤
│ P1 │ 0 - 0 = 0 │ 6 - 0 = 6 │
│ P2 │ 16 - 2 = 14 │ 24 - 2 = 22 │
│ P3 │ 9 - 4 = 5 │ 16 - 4 = 12 │
│ P4 │ 6 - 5 = 1 │ 9 - 5 = 4 │
├──────────┼─────────────────────────┼───────────────────────┤
│ 평균 │ (0+14+5+1)/4 = 5 │ (6+22+12+4)/4 = 11 │
└──────────┴─────────────────────────┴───────────────────────┘
실행 시간 예측 문제¶
┌─────────────────────────────────────────────────────────┐
│ SJF의 실행 시간 예측 문제 │
├─────────────────────────────────────────────────────────┤
│ │
│ 문제: 프로세스의 다음 CPU burst 길이를 어떻게 알 수 있나?│
│ │
│ 해결책: 과거 기록을 기반으로 예측 (지수 평균) │
│ │
│ τ(n+1) = α * t(n) + (1 - α) * τ(n) │
│ │
│ 여기서: │
│ τ(n+1) = 다음 CPU burst 예측값 │
│ t(n) = 실제 n번째 CPU burst 값 │
│ τ(n) = 이전 예측값 │
│ α = 0 ≤ α ≤ 1 (가중치) │
│ │
│ α = 0.5 예시: │
│ ┌───────┬────────┬────────┬────────┐ │
│ │ n │ t(n) │ τ(n) │ τ(n+1) │ │
│ ├───────┼────────┼────────┼────────┤ │
│ │ 0 │ - │ 10 │ - │ │
│ │ 1 │ 6 │ 10 │ 8 │ │
│ │ 2 │ 4 │ 8 │ 6 │ │
│ │ 3 │ 6 │ 6 │ 6 │ │
│ └───────┴────────┴────────┴────────┘ │
│ │
└─────────────────────────────────────────────────────────┘
3. SRTF (Shortest Remaining Time First)¶
개념¶
SRTF = SJF의 선점 버전
= 남은 실행 시간이 가장 짧은 프로세스 선택
= 새 프로세스 도착 시 선점 가능
┌─────────────────────────────────────────────────────────┐
│ SRTF 동작 │
├─────────────────────────────────────────────────────────┤
│ │
│ 시간 0: P1(6) 실행 중 │
│ 시간 2: P2(8) 도착 │
│ P1 남은 시간 = 4 │
│ P2 남은 시간 = 8 │
│ → P1(4) < P2(8) → P1 계속 실행 │
│ │
│ 시간 4: P3(7) 도착 │
│ P1 남은 시간 = 2 │
│ P2 남은 시간 = 8 │
│ P3 남은 시간 = 7 │
│ → P1(2) 가장 짧음 → P1 계속 실행 │
│ │
│ 시간 5: P4(3) 도착 │
│ P1 남은 시간 = 1 │
│ → P1(1) 가장 짧음 → P1 계속 실행 │
│ │
└─────────────────────────────────────────────────────────┘
예제 3: SRTF¶
입력:
┌──────────┬───────────┬───────────┐
│ 프로세스 │ 도착 시간 │ 실행 시간 │
├──────────┼───────────┼───────────┤
│ P1 │ 0 │ 8 │
│ P2 │ 1 │ 4 │
│ P3 │ 2 │ 9 │
│ P4 │ 3 │ 5 │
└──────────┴───────────┴───────────┘
간트 차트 분석:
시간 0: P1(8) 실행 시작
시간 1: P2(4) 도착
P1 남은=7, P2 남은=4 → P2로 선점!
시간 2: P3(9) 도착
P1 남은=7, P2 남은=3, P3 남은=9 → P2 계속
시간 3: P4(5) 도착
P1 남은=7, P2 남은=2, P3 남은=9, P4 남은=5 → P2 계속
시간 5: P2 완료
P1 남은=7, P3 남은=9, P4 남은=5 → P4 선택
시간 10: P4 완료
P1 남은=7, P3 남은=9 → P1 선택
시간 17: P1 완료
P3 남은=9 → P3 선택
시간 26: P3 완료
┌──┬────────┬──────────┬──────────────┬──────────────────┐
│P1│ P2 │ P4 │ P1 │ P3 │
└──┴────────┴──────────┴──────────────┴──────────────────┘
0 1 5 10 17 26
계산:
┌──────────┬─────────────────────────────────┬─────────────────────┐
│ 프로세스 │ 대기 시간 │ 총 처리 시간 │
├──────────┼─────────────────────────────────┼─────────────────────┤
│ P1 │ (10-1)-(0) = 9 │ 17 - 0 = 17 │
│ P2 │ 0 (선점 후 바로 실행) │ 5 - 1 = 4 │
│ P3 │ 17 - 2 = 15 │ 26 - 2 = 24 │
│ P4 │ 5 - 3 = 2 │ 10 - 3 = 7 │
├──────────┼─────────────────────────────────┼─────────────────────┤
│ 평균 │ (9+0+15+2)/4 = 6.5 │ (17+4+24+7)/4 = 13 │
└──────────┴─────────────────────────────────┴─────────────────────┘
SRTF 특징¶
┌──────────┬─────────────────────────────────────────────┐
│ 장점 │ • 이론적으로 최적의 평균 대기 시간 │
│ │ • 짧은 프로세스에 우선권 │
├──────────┼─────────────────────────────────────────────┤
│ 단점 │ • 실행 시간 예측 필요 │
│ │ • 긴 프로세스가 기아 상태에 빠질 수 있음 │
│ │ • 컨텍스트 스위치 오버헤드 │
├──────────┼─────────────────────────────────────────────┤
│ Starvation│ 짧은 프로세스가 계속 도착하면 │
│ (기아) │ 긴 프로세스는 영원히 실행되지 못할 수 있음 │
└──────────┴─────────────────────────────────────────────┘
4. Priority Scheduling¶
개념¶
Priority Scheduling = 우선순위가 높은 프로세스를 먼저 실행
= 선점/비선점 모두 가능
= 낮은 숫자 = 높은 우선순위 (일반적)
┌─────────────────────────────────────────────────────────┐
│ Priority Scheduling │
├─────────────────────────────────────────────────────────┤
│ │
│ Ready Queue에서 우선순위 비교: │
│ │
│ ┌───┐ ┌───┐ ┌───┐ ┌───┐ │
│ │P1 │ │P2 │ │P3 │ │P4 │ │
│ │ 3 │ │ 1 │ │ 4 │ │ 2 │ ← 우선순위 │
│ └───┘ └───┘ └───┘ └───┘ │
│ │
│ 선택 순서: P2(1) → P4(2) → P1(3) → P3(4) │
│ │
│ 우선순위 결정 기준: │
│ • 내부: 시간 제한, 메모리 요구량, I/O 대 CPU 비율 │
│ • 외부: 사용자 중요도, 비용, 정치적 요소 │
│ │
└─────────────────────────────────────────────────────────┘
예제 4: Priority (비선점)¶
입력:
┌──────────┬───────────┬───────────┬──────────┐
│ 프로세스 │ 도착 시간 │ 실행 시간 │ 우선순위 │
├──────────┼───────────┼───────────┼──────────┤
│ P1 │ 0 │ 10 │ 3 │
│ P2 │ 0 │ 1 │ 1 │
│ P3 │ 0 │ 2 │ 4 │
│ P4 │ 0 │ 1 │ 5 │
│ P5 │ 0 │ 5 │ 2 │
└──────────┴───────────┴───────────┴──────────┘
(낮은 숫자 = 높은 우선순위)
간트 차트:
우선순위 순서: P2(1) → P5(2) → P1(3) → P3(4) → P4(5)
┌──┬───────┬────────────┬────┬──┐
│P2│ P5 │ P1 │ P3 │P4│
└──┴───────┴────────────┴────┴──┘
0 1 6 16 18 19
계산:
┌──────────┬────────────┬───────────────────────┐
│ 프로세스 │ 대기 시간 │ 총 처리 시간 │
├──────────┼────────────┼───────────────────────┤
│ P1 │ 6 │ 16 │
│ P2 │ 0 │ 1 │
│ P3 │ 16 │ 18 │
│ P4 │ 18 │ 19 │
│ P5 │ 1 │ 6 │
├──────────┼────────────┼───────────────────────┤
│ 평균 │ 8.2 │ 12 │
└──────────┴────────────┴───────────────────────┘
Starvation과 Aging¶
┌─────────────────────────────────────────────────────────┐
│ 기아(Starvation) 문제 │
├─────────────────────────────────────────────────────────┤
│ │
│ 문제 상황: │
│ ┌────────────────────────────────────────────────────┐ │
│ │ Ready Queue: │ │
│ │ P(우선순위 낮음) ──────────────────────────────▶ │ │
│ │ ↑ 높은 우선순위 프로세스가 계속 도착 │ │
│ │ P(고), P(고), P(고), P(고), ... │ │
│ │ │ │
│ │ 낮은 우선순위 프로세스는 영원히 실행 안 됨 │ │
│ └────────────────────────────────────────────────────┘ │
│ │
│ 해결책: Aging (에이징) │
│ ┌────────────────────────────────────────────────────┐ │
│ │ 대기 시간이 증가하면 우선순위를 점진적으로 높임 │ │
│ │ │ │
│ │ 시간 0: P 우선순위 = 100 (낮음) │ │
│ │ 시간 10: P 우선순위 = 90 │ │
│ │ 시간 20: P 우선순위 = 80 │ │
│ │ ... │ │
│ │ 시간 100: P 우선순위 = 0 (최고) → 결국 실행됨 │ │
│ │ │ │
│ │ → 기아 문제 해결 │ │
│ └────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────┘
5. Round Robin¶
개념¶
Round Robin (RR) = 시분할 시스템을 위한 알고리즘
= 각 프로세스에 동일한 시간(Time Quantum) 할당
= 선점 (Preemptive)
= FCFS + 선점
┌─────────────────────────────────────────────────────────┐
│ Round Robin 동작 │
├─────────────────────────────────────────────────────────┤
│ │
│ Time Quantum (타임 퀀텀) = 4ms │
│ │
│ Ready Queue (순환): │
│ ┌───┐ ┌───┐ ┌───┐ │
│ │P1 │ → │P2 │ → │P3 │ ─┐ │
│ └───┘ └───┘ └───┘ │ │
│ ↑ │ │
│ └─────────────────────┘ │
│ │
│ 동작: │
│ 1. P1이 4ms 동안 실행 │
│ 2. 타임 퀀텀 만료 → P1은 Ready Queue 끝으로 │
│ 3. P2가 4ms 동안 실행 │
│ 4. 반복... │
│ │
└─────────────────────────────────────────────────────────┘
예제 5: Round Robin¶
입력:
┌──────────┬───────────┬───────────┐
│ 프로세스 │ 도착 시간 │ 실행 시간 │
├──────────┼───────────┼───────────┤
│ P1 │ 0 │ 24 │
│ P2 │ 0 │ 3 │
│ P3 │ 0 │ 3 │
└──────────┴───────────┴───────────┘
Time Quantum = 4ms
간트 차트:
시간 0: P1 실행 (4ms)
시간 4: P1 중단 (남은=20), P2 실행 (3ms에 완료)
시간 7: P2 완료, P3 실행 (3ms에 완료)
시간 10: P3 완료, P1 실행 (4ms)
시간 14: P1 중단 (남은=16), 다른 프로세스 없음, P1 실행
시간 18: P1 중단 (남은=12), P1 실행
시간 22: P1 중단 (남은=8), P1 실행
시간 26: P1 중단 (남은=4), P1 실행
시간 30: P1 완료
┌────┬───┬───┬────┬────┬────┬────┬────┐
│ P1 │P2 │P3 │ P1 │ P1 │ P1 │ P1 │ P1 │
└────┴───┴───┴────┴────┴────┴────┴────┘
0 4 7 10 14 18 22 26 30
계산:
┌──────────┬────────────┬───────────────────────┐
│ 프로세스 │ 대기 시간 │ 총 처리 시간 │
├──────────┼────────────┼───────────────────────┤
│ P1 │ 30-24 = 6 │ 30 - 0 = 30 │
│ P2 │ 4 - 0 = 4 │ 7 - 0 = 7 │
│ P3 │ 7 - 0 = 7 │ 10 - 0 = 10 │
├──────────┼────────────┼───────────────────────┤
│ 평균 │ (6+4+7)/3 = 5.67│ (30+7+10)/3 = 15.67│
└──────────┴────────────┴───────────────────────┘
Time Quantum 영향¶
┌─────────────────────────────────────────────────────────┐
│ Time Quantum의 영향 │
├─────────────────────────────────────────────────────────┤
│ │
│ Time Quantum이 매우 크면: │
│ ┌─────────────────────────────────────────────────┐ │
│ │ → FCFS와 동일해짐 │ │
│ │ → 응답 시간 증가 │ │
│ └─────────────────────────────────────────────────┘ │
│ │
│ Time Quantum이 매우 작으면: │
│ ┌─────────────────────────────────────────────────┐ │
│ │ → 컨텍스트 스위치 오버헤드 증가 │ │
│ │ → CPU 시간 낭비 │ │
│ └─────────────────────────────────────────────────┘ │
│ │
│ 권장 Time Quantum: │
│ • 평균 CPU burst의 80%가 Time Quantum 내에 완료되도록 │
│ • 일반적으로 10~100ms │
│ • Context switch time의 10배 이상 │
│ │
│ 시각화: │
│ │
│ q=∞: │P1(전체) │P2(전체) │P3... │
│ └────────────────────────────┴───────────┴──... │
│ │
│ q=1: │P│P│P│P│P│P│...│ ← 컨텍스트 스위치 너무 많음 │
│ └─┴─┴─┴─┴─┴─┴...┘ │
│ │
│ 적절한 q: │──P1──│──P2──│──P1──│──P3──│...│ │
│ └──────┴──────┴──────┴──────┴...┘ │
│ │
└─────────────────────────────────────────────────────────┘
6. 알고리즘 비교¶
종합 비교표¶
┌─────────────┬────────┬─────────┬─────────┬─────────────┬──────────┐
│ 알고리즘 │ 선점 │ 기아 │ 평균대기 │ 구현 │ 특징 │
├─────────────┼────────┼─────────┼─────────┼─────────────┼──────────┤
│ FCFS │ X │ X │ 길다 │ 매우 단순 │Convoy효과│
├─────────────┼────────┼─────────┼─────────┼─────────────┼──────────┤
│ SJF │ X │ O │ 최적 │ 실행시간예측│ 기아가능 │
├─────────────┼────────┼─────────┼─────────┼─────────────┼──────────┤
│ SRTF │ O │ O │ 최적 │ 실행시간예측│ 기아가능 │
├─────────────┼────────┼─────────┼─────────┼─────────────┼──────────┤
│ Priority │ O/X │ O │ 다양 │ 우선순위관리│Aging필요 │
├─────────────┼────────┼─────────┼─────────┼─────────────┼──────────┤
│ RR │ O │ X │ 중간 │ 단순 │TQ선택중요│
└─────────────┴────────┴─────────┴─────────┴─────────────┴──────────┘
동일 데이터 비교 예제¶
입력:
┌──────────┬───────────┬───────────┐
│ 프로세스 │ 도착 시간 │ 실행 시간 │
├──────────┼───────────┼───────────┤
│ P1 │ 0 │ 7 │
│ P2 │ 2 │ 4 │
│ P3 │ 4 │ 1 │
│ P4 │ 5 │ 4 │
└──────────┴───────────┴───────────┘
FCFS:
┌────────────────┬─────────┬──┬─────────┐
│ P1 │ P2 │P3│ P4 │
└────────────────┴─────────┴──┴─────────┘
0 7 11 12 16
평균 대기 시간: (0 + 5 + 7 + 7) / 4 = 4.75
SJF (비선점):
┌────────────────┬──┬─────────┬─────────┐
│ P1 │P3│ P4 │ P2 │
└────────────────┴──┴─────────┴─────────┘
0 7 8 12 16
평균 대기 시간: (0 + 10 + 3 + 3) / 4 = 4.00
SRTF:
┌────┬─────────┬──┬─────────┬────────┐
│ P1 │ P2 │P3│ P4 │ P1 │
└────┴─────────┴──┴─────────┴────────┘
0 2 6 7 11 16
평균 대기 시간: (9 + 0 + 2 + 2) / 4 = 3.25
RR (q=2):
┌────┬────┬────┬──┬────┬────┬────┐
│ P1 │ P2 │ P1 │P3│ P4 │ P2 │ P1 │
└────┴────┴────┴──┴────┴────┴────┘
0 2 4 6 7 9 11 14 16
평균 대기 시간: 계산 필요...
결론: SRTF가 가장 짧은 평균 대기 시간 제공
7. 연습 문제¶
문제 1: FCFS¶
다음 프로세스에 대해 FCFS 스케줄링을 적용하고 평균 대기 시간을 계산하세요.
| 프로세스 | 도착 시간 | 실행 시간 |
|---|---|---|
| P1 | 0 | 5 |
| P2 | 1 | 3 |
| P3 | 2 | 8 |
| P4 | 3 | 6 |
정답 보기
**간트 차트:**┌───────┬─────┬──────────┬────────┐
│ P1 │ P2 │ P3 │ P4 │
└───────┴─────┴──────────┴────────┘
0 5 8 16 22
문제 2: SJF (비선점)¶
문제 1과 동일한 데이터에 대해 SJF(비선점)를 적용하세요.
정답 보기
**간트 차트:**시간 0: P1(5) 실행 (P1만 도착)
시간 5: P1 완료, P2(3), P3(8), P4(6) 중 P2 선택
시간 8: P2 완료, P3(8), P4(6) 중 P4 선택
시간 14: P4 완료, P3 선택
시간 22: P3 완료
┌───────┬─────┬────────┬──────────┐
│ P1 │ P2 │ P4 │ P3 │
└───────┴─────┴────────┴──────────┘
0 5 8 14 22
문제 3: Round Robin¶
문제 1과 동일한 데이터에 대해 RR(Time Quantum = 2)를 적용하세요.
정답 보기
**간트 차트:**시간 0-2: P1(남은 3)
시간 2-4: P2(남은 1) - P2가 시간 1에 도착했으므로
시간 4-6: P3(남은 6) - P3가 시간 2에 도착
시간 6-8: P4(남은 4) - P4가 시간 3에 도착
시간 8-10: P1(남은 1)
시간 10-11: P2 완료
시간 11-13: P3(남은 4)
시간 13-15: P4(남은 2)
시간 15-16: P1 완료
시간 16-18: P3(남은 2)
시간 18-20: P4 완료
시간 20-22: P3 완료
┌──┬──┬──┬──┬──┬─┬──┬──┬─┬──┬──┬──┐
│P1│P2│P3│P4│P1│P2│P3│P4│P1│P3│P4│P3│
└──┴──┴──┴──┴──┴─┴──┴──┴─┴──┴──┴──┘
0 2 4 6 8 10 11 13 15 16 18 20 22
문제 4: Priority (선점)¶
다음 데이터에 대해 Priority(선점) 스케줄링을 적용하세요. (낮은 숫자 = 높은 우선순위)
| 프로세스 | 도착 시간 | 실행 시간 | 우선순위 |
|---|---|---|---|
| P1 | 0 | 4 | 2 |
| P2 | 1 | 3 | 1 |
| P3 | 2 | 2 | 3 |
| P4 | 3 | 5 | 4 |
정답 보기
**간트 차트:**시간 0: P1(우선순위 2) 실행
시간 1: P2(우선순위 1) 도착 → P1 선점, P2 실행
시간 4: P2 완료, P1(우선순위 2), P3(우선순위 3), P4(우선순위 4) 중 P1 선택
시간 7: P1 완료, P3와 P4 중 P3 선택
시간 9: P3 완료, P4 선택
시간 14: P4 완료
┌─┬─────┬─────┬────┬────────────┐
│P1│ P2 │ P1 │ P3 │ P4 │
└─┴─────┴─────┴────┴────────────┘
0 1 4 7 9 14
문제 5: 알고리즘 선택¶
다음 상황에 가장 적합한 스케줄링 알고리즘을 선택하고 이유를 설명하세요.
- 배치 처리 시스템에서 처리량을 최대화하고 싶다
- 대화형 시스템에서 응답 시간을 최소화하고 싶다
- 모든 프로세스를 공정하게 처리하고 싶다
정답 보기
1. **SJF (또는 SRTF)** - 짧은 작업을 먼저 처리하여 평균 대기 시간 최소화 - 처리량 최대화 - 배치 시스템에서는 실행 시간 예측이 가능한 경우가 많음 2. **Round Robin** - 모든 프로세스에 빠르게 CPU 시간 할당 - 응답 시간이 짧음 - 적절한 Time Quantum 선택이 중요 3. **Round Robin** 또는 **FCFS** - 모든 프로세스에 동등한 기회 제공 - FCFS: 도착 순서대로 공정하게 처리 - RR: 각 프로세스에 동일한 시간 할당 - 기아 현상 없음다음 단계¶
- 06_Advanced_Scheduling.md - MLFQ, 멀티프로세서 스케줄링, 실시간 스케줄링