[운영체제] 스케줄링 알고리즘

1️⃣ FCFS (First Come First Served)

1. 특징
   • 비선점 스케줄링
     • 이미 할당된 CPU를 다른 프로세스가 강제로 빼앗아 사용할 수 없는 스케줄링 기법
     • 짧은 작업이 긴 작업을 기다리는 경우가 발생할 수 있음
     • 프로세스 응답 시간의 예측이 용이하며, 일괄 처리 방식 (Batch Processing) 에 적합 -Batch Processing : 여러 개의 프로그램을 읽어놓고, 한 번에 하나의 프로그램만 실행함
       
   • 먼저 도착한 프로세스가 먼저 CPU를 선점함
2. 단점
   • Convoy Effect : 실행시간이 짧은 프로세스들이 실행시간이 긴 프로세스를 계속해서 기다리면서 효율성이 저하됨

2️⃣ **SJF (Shortest Jop First)**

1. 특징
   • 실행시간(Burst Time) 이 가장 짧은 프로세스부터 실행함
   • 비선점 스케줄링, 이미 긴 프로세스가 실행중이라면 새로 도착한 짧은 프로세스는 기다리긴 해야함
2. 단점
   • Starvation : 실행시간이 긴 프로세스가 영원히 CPU를 할당받을 수 없게됨

3️⃣ SRTF (Shortest Remaining Time First) , SRT

1. 특징
   • 선점형 스케줄링 현재 실행 중인 프로세스보다 우선순위가 더 높은 프로세스가 도착하면 cpu를 뺏김
     
   • 새로운 프로세스가 도착할 때마다 새롭게 스케줄링을 진행함
   • 새로운 프로세스가 들어온 시점에서 현재까지 남은 실행시간이 가장 적은 프로세스를 먼저 실행함 ⇒ 새로 들어온 가장 짧은 프로세스가 오자마자 실행될 수 있음
     
2. 단점
   • Starvation : SJF 와 같은 이유로 실행시간이 긴 프로세스가 영원히 CPU 할당받을 수 없음
   • 새로운 프로세스가 올 때마다 스케줄링을 다시하므로, 프로세스의 정확한 CPU Burst Time을 측정할 수 없다

4️⃣ Priority Scheduling

1. 특징

• 우선순위가 높은 프로세스가 CPU를 선점하도록 하는 스케줄링 (우선순위는 숫자가 작을수록 높다)
• 선점, 비선점 스케줄링 방식 모두 사용 가능함
  • 선점형 : 더 높은 우선순위의 프로세스가 도착하면 현재 실행중인 프로세스에게서 CPU를 뺏는다
  • 비선점형 : 더 높은 우선순위의 프로세스가 도착하면 Ready Queue에 넣고 바로 다음에 실행되게 한다

1. 단점
   • Starvation : 우선순위가 낮은 프로세스는 계속해서 우선순위가 높은 프로세스에게 밀려 실행될 수 없음
   • 무기한 봉쇄(Indefinite blocking) : 우선순위가 높은 프로세스가 Blocking 되어있어 CPU가 계속해서 대기해야하는 상황
2. 해결
   • Aging 프로세스의 대기 시간이 증가함에 따라 우선순위를 높여주는 기법 Starvation을 예방할 수 있음
     

5️⃣ Round-Robin

1. 특징
   • 각 프로세스는 동일한 할당 시간 (Time Quantum) 을 가짐
   • CPU를 할당 받고 할당 시간이 지나면 Ready 상태로 돌아가 Ready Queue의 Tail로 들어감
   • 프로세스들이 작업을 완료할 때까지 계속해서 순회한다
2. 장점
   • Response time이 빨라짐
     • n 개의 프로세스가 ready queue 에 있고 할당시간이 q(time quantum)인 경우 각 프로세스는 q 단위로 CPU 시간의 1/n 을 얻는다. 즉, 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다.
   • 모든 프로세스가 공정하게 CPU를 할당받을 수 있음을 보장
3. 주의할 점
   • 설정한 time quantum이 너무 커지면 FCFS와 같아짐
   • 너무 작아지면 Context Switching으로 인한 Overhead가 증가함

6️⃣ 선점형 vs 비선점형

선점형 : RR, SRT

비선점형 : FCFS, SJF

둘다가능 : Priority

참고

https://intrepidgeeks.com/tutorial/cs-interview-1st-week-scheduler

https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/OS#스케줄러

https://coding-factory.tistory.com/309

https://hellouz818.tistory.com/6

https://zzsza.github.io/development/2018/07/29/cpu-scheduling-and-process/

http://blog.skby.net/cpu-스케줄링/