5. CPU 스케줄링
프로세스의 특성 분류
- I/O bound job
CPU 사용시간이 짧은 프로세스
many short CPU bursts - CPU bound job
CPU 사용시간이 긴 프로세스, 계산 위주의 job
few very long CPU bursts
여러 종류의 프로세스가 섞여 있기 때문에 CPU 스케줄링이 필요
CPU Scheduler & Dispatcher
- CPU Scheduler
Ready 상태의 프로세스 중 CPU를 줄 프로세스 결정 - Dispatcher
CPU 제어권을 선택된 프로세스에게 넘김 - 문맥 교환 (context switch)
CPU 스케줄링이 필요한 경우
1. Running → Blocked
2. Running → Ready
3. Blocked → Ready
4. Terminated
Nonpreemptive (=자진 반납) - 1, 4의 스케줄링
Preemptive (=강제로 빼앗음) - 다른 모든 스케줄링
Scheduling Criteria (성능 척도)
- CPU utilization (이용률) - 높을수록 좋음
- Throughput (처리량) - 많을수록 좋음
- Time - 짧을수록 좋음
- Turnaround time (소요시간, 반환시간) - 큐에서 기다린 시간 + CPU 사용 시간
- Waiting time (대기시간) - 기다린 시간의 합
- Response time (응답시간) - 프로세스가 최초로 들어와서 CPU를 얻기까지 걸린 시간
FCFS (First-Come First-Served)
먼저 온 순서대로 CPU 사용 - Nonpreemptive
Convoy effect: short process behind long process
SJF (Shortest-Job-First)
CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케줄
- Nonpreemptive
더 짧은 CPU burst time을 가진 프로세스가 들어와도 빼앗지 않음 - Preemptive (SRTF: Shortest-Remaining-Time-First)
남은 시간을 기준으로 더 짧은 CPU burst time을 가진 프로세스가 들어오면 빼앗음 - Optimal waiting time 보장 - Problem
- Starvation - long burst time 프로세스는 CPU를 사용하지 못할 수 있음
- CPU 사용시간을 미리 알 수 없음 - 과거 n번의 실제 사용시간을 통해 예측
Priority Scheduling
highest priority를 가진 프로세스에게 CPU 할당
preemptive, nonpreemptive
SJF도 일종의 priority scheduling
Problem - Starvation
Solution - Aging (오래 기다리면 우선순위를 높임)
Round Robin (RR)
각 프로세스에 동일한 크기의 시간 할당 (rime quantum)
할당 시간이 끝나면 timer interrupt
프로세스가 (n-1)q time unit 이상 기다리지 않음
기다리는 시간이 CPU 사용시간에 비례 - 공평함
일반적으로 SJF보다 avarage turnaround time이 길지만 response time은 더 좋음
homogeneous job에서는 비효율적
Multilevel Queue
- Foreground (interactive) - RR
- Background (batch - no human interaction) - FCFS
큐에 대한 스케줄링 필요
Fixed priority scheduling - Foregound 먼저 → Background
Time slice
큐 사이의 이동이 불가
Multilevel Feedback Queue
프로세스가 다른 큐로 이동 가능
- Queue의 수
- 각 큐의 scheduling algorithm
- Process를 상위/하위 큐로 보내는 기준
- 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준
Multiple-Processor Scheduling
- Homogeneous processor
Queue에 한 줄로 세워서 프로세서가 알아서 꺼냄 - Load sharing
특정 CPU에 몰리지 않도록 적절히 공유 - Symmetric Multiprocessing
각 프로세서가 각자 알아서 스케줄링 결정 - Asymmetric multiprocessing
한 프로세서가 나머지 프로세서의 스케줄링 결정
Real-Time Scheduling
- Hard real-time systems
정해진 시간 안에 반드시 끝내도록
offline으로 미리 스케줄링하는 경우도 많음 - Soft real-time computing
일반 프로세스에 비해 높은 priority를 갖도록
Thread Scheduling
- Local Scheduling
User level thread - 프로세스 자신이 어떤 thread에 CPU를 줄지 결정 - Global Scheduling
Kernel level thread - 커널이 어떤 thread에 CPU를 줄지 결정
Algorithm Evaluation
- Queueing models - arrival rate, service rate → performance index 계산
- Impementation (구현) & Measurement (성능 측정) - 알고리즘 실제로 구현하여 측정
- Simulation (모의 실험) - trace 입력하여 가상으로 알고리즘 실행
