CPU Scheduler
- Scheduler은 ready Queue에 있는 프로세스들 중에 선택함
스케쥴링 decision이 일어날 때
- Running 하다가 I/O가 요청되면 Wait Queue 될 때 Ready
- Running 하다가 I/O 요청되면 ready Queue 될 때
- Waiting 하다가 Ready Queue로 갈 때 Interrupt 일어나서
- 본인의 역할 후 끝날 때
스케쥴링 척도 (Scheduling Criteria)
CPU utilization(사용량) : CPU를 얼마나 쉬지않고 일하게 할 수 있는 지
Throughput : 단위 시간 내에 얼마나 많은 일을 했는 지
Turnaround time : 하나 프로세스가 실행되고 끝내는 시간(전체)
Waiting time : Ready Queue에 있는데 기다린 시간
Response time : 중간중간 어느정도 인지 사용자에게 정보를 주는 것, 일반적으로 대화형 시스템에서 입력에 대한 반응 시간
Scheduling Algorithms
Preemptive vs Non-preemptive
Preemptive
- 프로세스가 CPU를 점유하고 있는 동안 I/O나 인터럽트가 발생한 것도 아니고, 모든 작업을 끝내지 않났는데 다른 프로세스가 CPU를 강제 점유 가능
Non-Preemptive
- 한 프로세스가 한 번 CPU를 점유했다면 I/O 또는 프로세스가 종료될 때까지 다른 프로세스가 CPU를 점유하지 못하는 것
1. FCFS(First-Come, First-Served)
- 먼저 온 프로세스가 먼저 CPU를 점유하는 방식
- 단순하고 많이 사용하지만 모든 부분에서 효율적이지는 않음
Waiting time : P1=0, P2=24, P3=27
평균 시간 = (0+24+27) / 3 = 17
만약, 다음과 같이 바뀐다면
Wating time : P1=6, P2=3, P3=0
평균 시간 = (6+3+0)/3 = 3
으로 앞에 비해 평균 시간이 줄어든다
- FCFS는 Waiting time에 대해 랜덤 (운에 따라 성능이 달라짐)
- Non-preemptive (하나의 프로세스가 끝나기 전에 다른 프로세스가 중간에 끼어들 수 없음)
2. SJF (Shortest-Job-First)
- 짧게 수행되는 프로세스가 가장 먼저 수행되게 하는 것
- Waiting time에 대해서는 가장 Optimal
평균 시간 : (3+16+9+0)/4 = 7
- 실제 컴퓨터 환경에서는 burst time을 알 수 없어서 비현실적
Non-Preemptive SJF
P1이 수행되는 동안 P2,P3,P4가 도착하지만 non-preemptive로 수행중인 프로세스가 끝날 때 까지 기다려야함
평균 시간 : (0+7+15+9)/4 = 7.75
Preemptive SJF
프로세스가 도착할 때마다 어떤 프로세스가 가장 짧은지 선택
P2가 도착했을 때, 현재 남은 burst time 중 가장 짧은 것이 P2이므로 P1을 멈추고 P2를 수행한다
평균 시간 : (9+0+15+2) = 6.5
3. Priority (우선순위)
- 우선순위가 높은 프로세스 부터 선택
- Preemptive → decision이 자주 일어나서 좋음
- Non-preemptive → scheduling 할 때마다 저장 시켜두고 정보를 옮겨야할 일이 없어 cost 측면에서 좋음
- 문제 : starvation, 낮은 priority는 실행이 자꾸 미뤄지며 안될 수도 있음
- 해결 : aging, ready queue에서 기다리는 동안 일정 시간이 지나면 우선순위를 일정량 높여줌
평균 시간 : (6+0+16+18+1)/5 = 8.2
4. Round-Robin(RR)
- 원 모양으로 모든 프로세스가 돌아가며 스케쥴링
- 일정 시간을 정해 하나의 프로세스가 이 시간동안 수행하고 다시 대기상태로 돌아가는 것 반복
- 마지막 프로세스가 끝나면 처음 프로세스로 돌아와 반복
- 이 일정 시간을 Time Quantum이라 함
- 기본적으로 preemptive임 ( 한 프로세스가 종료되기전 time quantum이 끝나면 다른 프로세스로 CPU 넘겨주기 때문)
Time Quantum = 4 msec
- P1에서 0에서 수행 시작해서 종료 전에 time quantum 시간이 끝나 P2가 수행됨
- P2와 P3은 time quantum이 끝나기 전 수행 끝남
- 남은 P1은 다른 프로세스가 없으므로 time quantum이 끝나더라도 계속해서 수행
평균 시간 = (6+4+7)/3 = 5.66
- time quantum에 매우 의존적
- q의 크기가 무한에 가까우면 FCFS와 동일하게 동작
- q가 0에 가깝게 설정하면 overhead가 증가해 비효율적
- 적당한 크기로 10~100msec로 설정
Multilvel Queue
- 큐를 몇 개 넣을지
- 각 큐에서 어떤 알고리즘 스케쥴링 사용할지
- 어떤 상황에서 올릴지
- 어떤 상황에서 내릴지
- 다른 프로세스에 넘어갈 때 어떤 큐에 넣을지
우선순위 기준이 다른 분리된 큐를 두어 우선순위에 맞게 스케쥴링 하는 방법
Multi-processor scheduling(멀티 프로세서 스케쥴링)
Asymmetric multiprocessing - 아키텍처가 동일하지 않음
Symmetric multiprocessing (SMP) - 모든 아키텍처가 동일
- Load Balancing
- workload를 모든 프로세서에게 공정히 배분하려는 노력함
- Push migration
- 각 프로세서 로드량 체크 후 만약 불균형 찾으면 스레드를 idle or 덜 바쁜 cpu에 옮겨 공정히 분배
- Pull migration
- idle 프로세서가 waiting processor에서 task 가져옴
상호 보완적으로 서로 병렬적으로 실행가능
Real-time CPU Scheduling
- soft real-time system
- ex) 동영상 시스템
- Hard real-time system
- ex) 자동차처럼 데드라인 넘으면 큰 손해
Priority-based Scheduling
- preemptive(실행 중 높은 priority 오면 넘겨주는 것 허용)이 있는 Priority 스케쥴링 알고리즘
- timing guarantee(hard는 deadline 맞추는것 필요
- periodic 하다
Rate Monotonic Scheduling
- preemption있는 priority
- period 짧을 수록 rate 커지며 priority 증가
- period 길면 priority 낮음
- 결국 rate-monotonic은 그들의 deadline 맞추는거 보장하지 못함
Earliest-Deadline-First Scheduling (EDF)
- deadline이 급한 것부터 우선순위 높게 줌
- 고정된 priority를 가지며, cpu burst duration이 같지 않다
- 이론상 최적화, but 이것은 context switching에 의해 현실적으로 불가능
