- CPU의 utilization을 극대화 하기 위해서
- Throughput을 최대화 하자
- Throughput: 단위시간내에 완료되는 프로세스 수- Turnaround time:
- 프로세스가 실행에서 종료되기까지의 시간을 최소화 하자- Waiting time:
- 프로세스가 대기하는 시간을 최소화 하자- Response time:
- 응답하기 까지의 시간을 최소화 하자
Fist In First Out
- CASE 1 running -> waiting: I/O 작업이나 이벤트가 발생하여 대기상태에 들어감 (Non-preemptive)
- CASE 2 running -> ready
- CASE 3 wating -> ready
- CASE 4 terminate: 프로세스 종료 후 exit (Non-preemptive)
CPU 제어권을 바꿔주는 장치
functions of dispatcher:
- Context Switching (문맥 교환)
- user mode로 전환
- 새로운 프로세스의 위치로 resume
Dispatcher는 가능한 최대로 빨라야 함
문맥 교환시 지연되는 시간을 (save PCB or restore PCB) dispatcher latency 라고 함
따라서 dispatcher latency는 짧아야 함
- $ vmstat 1 3
cs부분에 나오는 숫자가 1초에 context switching이 일어나는 횟수- $ cat /proc/1/status | grep ctxt
voluntary_ctxt_switches: Non-preemptive
nonvoluntary_ctxt_switches: preemptive
- CPU를 먼저 요청한 프로세스에 CPU를 할당
- FIFO Queue에 도착한 프로세스를 순서대로 pop한 후 실행
- 프로세스가 P1, P2, P3 순서로 큐에 들어올 때
- 프로세스가 P2, P3, P1 순서로 큐에 들어올 때
도착 순서만 바꼈을 뿐인데
Waiting Time이 17s -> 3s로 바뀜
Turnaround Time이 27s -> 13s로 바뀜
- Convoy Effect:
CPU-burst 시간이 긴 프로세스가 아주 짧은 CPU-burst 시간을 가지는 프로세스보다 먼저 왔을 때 나머지 프로세스 들이 기다리는 시간이 길어지는 것을 의미
FCFS 알고리즘은 Non-preemptive
- 작업 시간이 짧은 것부터 실행
- shortest-next-CPU-burst-fist scheduling
- 프로세스 도착 순서: P1(6s) / P2(8s) / P3(7s) / P4(3s)
SJF 알고리즘은 provably optimal. 즉 최적임을 증명할 수 있다.
P2 (작업 시간이 긴 프로세스) 앞으로 P1 (작업 시간이 짧은 프로세스) 을 이동시켰을 때 P2의 WT(Waiting Time)이 0초에서 3초로 늘어난 것 보다 P1의 WT이 6초에서 0초로 줄어든 것이 훨씬 더 효율적
하지만 SJF는 구현을 할 수 없다.
비슷하게 구현하는 방법은
SJF는 Preemptive, Non-Preemptive 둘 다 된다
Preemptive
- 프로세스가 실행중이더라도 ready queue에 도착하는 프로세스의 작업 시간이 짧다면 나중에 도착한 프로세스에게 CPU 점유를 뺏긴다.
Non-Preemptive
- 프로세스가 실행중일 때 자신보다 작업시간이 더 긴 프로세스가 ready queue에 들어오면 현재 프로세스는 끝까지 진행
하지만 ready queue에 들어갈 때 마다 남은 CPU-burst 타임을 알아야 한다
SRTF == Preemptive SJF Scheduling
- ready queue에 들어온 process가 현재 실행중인 프로세스의 CPU-burst 시간(Remaining Time) 보다 더 작으면 switching
Process - Arrival Time - Burst Time
P1 - 0 - 8
P2 - 1 - 4
P3 - 2 - 9
P4 - 3 - 5
Preemptive FCFS with time quantum(time slice)
- 보통 10ms
- ready queue는 circular queue로 구현
프로세스 / Burst time
- P1 / 24
- P2 / 3
- P3 / 3
time quantum: 4s
P2의 경우 time quantum 보다 짧아 자발적으로 종료됨
RR의 평균 대기 시간은 대부분의 상황에서 더 크다
- 그렇기 때문에 다른 알고리즘과 함께 활용
- time quantum을 얼마나 주냐에 따라 성능이 달라진다
- time quantum을 각각 12s, 6s, 1s로 주었을 때 context switching은 각각 0회, 1회, 9회 일어남
- context switching이 일어날 때 dispatch latency가 발생
- quantum time을 무한대로 주면 FCFS 방식과 동일
- SJF도 Prioirity-based 중 하나 (next CPU burst를 기준으로 잡음)
- Preemptive or Non-preemptive
- starvation 상황 발생:
자료 캡쳐 및 참고: