운영체제(5) - CPU Scheduling Algorithm

CPU 스케줄러는 CPU 스케줄링 알고리즘에 따라 프로세스에서 해야 하는 일을 스레드 단위로 CPU에 할당한다. 이 때 어떤 프로그램에 CPU 소유권을 줄 것인지 결정하는 것이 바로 CPU 스케줄링 알고리즘이다. 

 

CPU 스케줄링 알고리즘은 다음과 같이 나눌 수 있다.

 

 

 

 

1. Non Preemptive (비선점형)

---

비선점형 방식은 프로세스가 스스로 CPU 소유권을 포기하는 방식으로 강제로 프로세스를 중지하지 않는다.

 

1. FCFS (First Come First Served)
   • 큐에 가장 먼저 도착한 순서대로 CPU 할당
   • 실행 시간이 짧은 게 뒤로 가면 평균 대기 시간이 길어짐으로 준비 큐에서 오래 기다리는 현상인 'Convoy Effect' 가 발생한다
2. SJF (Shortest Job First)
   • 수행시간이 가장 짧다고 판단되는 작업을 먼저 수행
   • 수행시간이 긴 프로세스가 실행되지 않는 'Starvation' 이 발생한다.
   • FCFS 보다 평균 대기 시간 감소, 짧은 작업에 유리
   • 실제 실행 시간은 알 수 없음
3. HRN (Hightest Response-ratio Next)
   • 우선순위를 계산하여 점유 불평등을 보완한 방법(SJF의 Starvation 해결)
   • 우선순위 = (대기시간 + 실행시간) / (실행시간)
   • 오래된 작업일수록 우선순위를 높이는 방법인 'Aging'을 통해 단점 보완

 

2. Preemptive (선점형)

---

선점형 방식은 현대 운영체제가 쓰는 방식으로 현재 프로세스를 중단시키고 다른 프로세스에 CPU 소유권을 할당하는 방식을 말한다.

 

 

1. Round Robin
   • 우선순위 스케줄링의 일종으로 동일한 시간을 주고 시간안에 해결되지 않으면 다시 준비 큐의 뒤로가는 알고리즘
   • FCFS에 의해 프로세스들이 보내지면 각 프로세스는 동일한 시간의 Time Quantum 만큼 CPU를 할당 받음
     • Time Quantum or Time Slice : 실행의 최소 단위 시간
   • 할당 시간(Time Quantum)이 크면 FCFS와 같게 되고, 작으면 문맥 교환 (Context Switching) 잦아져서 오버헤드 증가
2. SRF (Shortest Remaining Time First
   • SJF의 선점형 스케줄링 방식
   • 남은 프로세스의 작업보다 더 짧은 작업이 들어오면 프로세스를 중지하고 해당 프로세스를 수행
3. Multilevel-Queue (다단계 큐)
   • 우선순위에 따른 준비 큐를 여러개 사용하고 각 큐마타 RR이나 FCFS등 여러 스케줄링 알고리즘을 적용
   • 우선순위가 낮은 큐들이 실행 못하는 것을 방지하고자 각 큐마가 다른 시간을 할당