[OS] Lecture 5. Process Scheduling (2/4) - FCFS, RR

Basic Scheduling algorithms

1. FCFS(First Come First Service)

2. RR(Round Robin) 

3. SPN(Shortest Process Next)

4. SRTN(Shortest Remaining  Process Next)

5. HRRN(High Response Ratio Next)

6. MLQ(Multi Level Queue)

7. MFQ(Multi Level Feedback Queue)

---

1. FCFS(First Come First Service)= 선착순 알고리즘

- Non-preemptive scheduling

- 스케줄링 기준: 도착시간(ready queue 기준). 먼저 도착 프로세스 먼저 처리

- scheduling overhead가 낮다. CPU가 계속 일할 수 있다. 

- Batch sysytem(일괄처리)에 적합, interactive system에 부적합

- 단점: Convoy effect. 긴 평균 응답시간 

 

convoy effect

하나의 수행시간이 긴 프로세스에 의해 다른 프로세스들이 긴 대기시간을 갖게 되는 현상(대기시간>>실행시간)

 

 

---

RR(Round-Robin)= 돌려가며 사용

- preemptive scheduling

- 스케줄링 기준: 도착시간. 먼저 도착한 프로세스 처리(FCFS와 동일)

- 자원 사용 제한 시간(time quantum)이 존재

- 프로세스는 할당 시간이 지나면 자원 반납

- 특점 프로세스의 자원 독점(monopoly) 방지

- 단점: context switching overhead가 큼

- interactive system, Time sharing system에 적합

 

Time quantum

- 시스템 성능을 결정하는 핵심

- Very large(infinite)-> FCFS

- Very small-> processor sharing

사용자는 모든 프로세스가 각각의 프로세서 위에서 실행되는 것처럼 느낌. High context switch overhead