프로세스 스케줄링 기법
비선점 : FCFS, SJF, HRN, 우선순위, 기한부
선점 : R-R, SRT, MLQ, MLFQ
비선점(Non-preemptive) 스케줄링
- 한 프로세스가 일단 CPU를 할당받으면 다른 프로세스가 CPU를 강제로 빼앗을 수 없고, 사용이 끝날 때까지 기다리는 방식
- 모든 프로세스들에 대한 요구를 공정히 처리하여 응답 시간의 예측이 용이
- CPU의 사용 시간이 짧은 프로세스들이 사용시간이 긴 프로세스들로 인하여 오래 기다리는 경우가 발생할 수 있음
<FIFO(First In First Out)>
준비 상태 큐에 도착한 순서대로 CPU를 할당
=> FCFS(First Come First Service)라고도 함.
| 작업 | 도착시간 | 실행시간 |
| P1 | 0 | 13 |
| P2 | 3 | 35 |
| P3 | 8 | 10 |
실행 순서 : P1 -> P2 -> P3
대기 시간 : P1(0), P2(10), P3(40)
평균 대기 시간 : (0+10+40) / 3 = 16.66
반환 시간 : P1(13), P2(45), P3(50)
평균 반환 시간 : (13+45+50) / 3 = 36
<SJF(Shortest Job First)>
실행시간이 가장 짧은 프로세스에 가장 먼저 CPU 할당
| 작업 | 실행시간 |
| P1 | 6 |
| P2 | 3 |
| P3 | 8 |
| P4 | 7 |
실행 순서 : P2 -> P1 -> P4 -> P3
대기 시간 : P2(0), P1(3), P4(9), P3(16)
평균 대기 시간 : (0+3+9+16)/3=7
반환 시간 : P2(3), P1(9), P4(16), P3(24)
평균 반환 시간 : (3+9+16+24)/4 = 13
<HRN(Highest Response - ration Next)>
어떤 작업이 서비스 받을 시간과 그 작업이 서비스를 기다린 시간으로 결정되는 우선순위에 따라 CPU할당
우선 순위 계산식 : (대기시간 + 서비스 시간) / 서비스 시간
| 작업 | 대기시간 | 서비스(실행) 시간 |
| P1 | 5 | 20 |
| P2 | 40 | 20 |
| P3 | 15 | 45 |
| P4 | 20 | 20 |
P1 대기시간 (5+20) / 20 = 1.25
P2 대기시간 (40+20) / 20 = 3
P3 대기시간 (15+45) / 45 = 1.333
P4 대기시간 (20+20) / 20 = 2
실행 순서 : P2 -> P4 -> P3 -> P1
<우선순위>
우선순위가 가장 높은 프로세스에게 먼저 CPU할당
우선순위가 낮은 프로세스는 무한정지가 발생할 수 있고 에이징 기법으로 이를 해결.
선점(Preemptive) 스케줄링
- 한 프로세스가 CPU를 할당받아 실행 중이라도 우선순위가 높은 다른 프로세스가 CPU를 뺏을 수 있음
<RR(Round Robin)>
- 시분할 시스템을 위해 고안
- 시간 할당량이 커지면 FCFS와 같은 효과
- 시간 할당이 작아지면 프로세스 문맥 교환이 자주 일어난다
<SRT(Shortest Remaining Time)>
- 작업이 끝나기까지의 실행시간 추정치가 가장 작은 작업을 먼저 실행
- FIFO 기법보다 평균 대기 시간이 감소
- 작업시간이 큰 경우 오래 대기해야함
<다단계 큐>
- 프로세스들을 우선순위에 따라 상위,중위,하위 단계의 단계별 준비상태 큐를 배치하는 기법
<다단계 피드백 큐>
- 각 준비 상태 큐마다 부여된 시간 할당량 안에 완료하지 못한 프로세스는 다음 단계의 준비 상태 큐로 이동.