[OS] CPU 스케줄링 알고리즘

CPU 스케줄링이란?

 

프로세스는 생성된 후 여러 상태를 거침 (생성, 준비, 실행, 완료, 대기 상태)

이때, 운영체제의 CPU 스케줄러는 준비 상태의 프로세스 중에서 어떤 프로세스에게 CPU를 할당할지 결정해야함!

이 과정을 CPU 스케줄링이라 함

 

➡️ CPU 스케줄링 알고리즘에 따라서 프로세스에서 해야 하는 일을 스레드 단위로 CPU에 할당

 

CPU 스케줄링 알고리즘의 목표

: CPU 이용률은 높게, 주어진 시간에 많은 일을 하게, 준비 큐에 있는 프로세스는 적게, 응답시간은 짧게 설정하는 것

 

CPU 스케줄링 알고리즘의 종류

 

 

CPU 스케줄러는 언제 스케줄링을 결정할까?

 

1) 실행상태에서 대기상태로 전환될 때

2) 실행상태에서 준비상태로 전환될 때

3) 대기상태에서 준비상태로 전환될 때

4) 종료될 때

 

1번과 4번 상황에서만 스케줄링이 발생하는 것을 비선점형(non-preemptive) 스케줄링

이외의 모든 스케줄링은 선점형(preemptive) 스케줄링

 

---

비선점형(non-preemptive) 스케줄링

 

비선점형 방식은 프로세스가 스스로 CPU 소유권을 포기하는 방식

→ 어떤 프로세스가 CPU를 점유하고 있다면 뺏을 수 없음

• 강제로 프로세스를 중지하지 않음
• 컨텍스트 스위칭으로 인한 부하가 적음
  • 컨텍스트 스위칭 (문맥 교환): 여러개의 프로세스가 실행되고 있을 때 기존에 실행되던 프로세스를 중단하고 다른 프로세스를 실행하는 것
• 프로세스의 배치에 따라서 효율성 차이가 많이 나게 됨

 

비선점형 스케줄링의 종류

 

FCFS (First Come, First Served)

: 가장 먼저 온 것을 가장 먼저 처리하는 알고리즘

• 길게 수행되는 프로세스 때문에 Convoy effect가 발생한다는 단점이 있음
  • Convoy effect(호위 효과): 몇 개의 시간이 오래 걸리는 프로세스로 인해 전체 OS가 느려지는 현상

 

 

SJF (Shortest Job First)

: 실행 시간이 가장 짧은 프로세스를 가장 먼저 실행하는 알고리즘

• 실제로는 프로세스의 CPU 실행 시간을 예측하는 것이 어렵다는 문제가 있음
• 긴 시간을 필요로 하는 프로세스가 우선순위가 계속 밀리면서 실행되지 못하고 무기한으로 대기하는 기아 현상(Starvation)이 일어남

 

 

우선순위 (Priority)

: 각각의 프로세스에 우선순위 넘버가 있는 알고리즘

• 긴 시간을 가진 프로세스가 실행되지 않는 현상이 일어나는 SJF 스케줄링의 단점을 보완함
  • 오래된 작업의 우선순위를 높여주는 식

 

---

선점형(preemptive) 스케줄링

 

선점형 방식은 현대 운영체제가 쓰는 방식으로 지금 사용하고 있는 프로세스를 알고리즘에 의해 중단시켜 버리고 강제로 다른 프로세스에 CPU 소유권을 할당하는 방식

• 처리 시간이 매우 긴 프로세스의 CPU 사용 독점을 막을 수 있어 효율적인 운영이 가능
  • 잦은 컨텍스트 스위칭으로 인해 오버헤드(Overhead)가 커질 수 있다는 단점이 있음
  • 오버헤드(Overhead): 어떤 처리를 하기 위해 들어가는 간접적인 처리 시간 · 메모리 등을 말함

 

선점형 스케줄링의 종류

 

라운드 로빈 (RR, Round Robin)

: 현대 컴퓨터가 쓰는 스케줄링의 우선순위 스케줄링의 일종으로 각각의 프로세스에 동일한 할당 시간을 부여해서 해당 시간 동안만 CPU를 이용하게 함

• 할당 시간 내에 처리를 완료하지 못하면 강제 중단 후 다음 작업으로 넘어가므로 선점형 방식
  • 시간 안에 처리를 못하면 다시 준비 큐의 뒤로 돌아가는 것
• 응답 시간을 빠르게 할 수 있다는 장점을 가짐
  • 일반적으로 전체 작업 시간은 길어지지만 평균 응답 시간은 짧아진다는 특징이 있음

ex) q만큼의 할당 시간이 부여되고 N개의 프로세스가 운영시 (N-1)*q 시간이 지나면 자기 차례가 오게됨

할당 시간이 너무 크면 FCFS가 되고 짧으면 컨텍스트 스위칭이 잦아져서 오버헤드 → 비용 증가

 

 

SRF (Shortest Remaining Time First)

: 현재 실행되고 있는 프로세스의 남은 시간보다 더 빨리 끝날 수 있는 짧은 프로세스가 들어오면 현재 실행되는 프로세스를 중단하고 짧은 프로세스를 실행하도록 바꿈

• 중간에 실행 시간이 더 짧은 작업이 들어와도 기존 짧은 작업을 모두 수행하고 그 다음 짧은 작업을 이어나가는비선점형 스케줄링인 SJF와 다름
• 평균 대기 시간을 줄일 수 있지만 역시 다음 프로세스의 CPU burst time을 예측하는 것이 어렵다는 문제가 존재함

 

 

다단계 큐 (Multilevel Queue)

: 우선순위에 따른 준비 큐를 여러 개 사용하고, 큐마다 라운드 로빈이나 FCFS 등 다른 스케줄링 알고리즘을 적용한 것

• 큐 간의 프로세스 이동이 안 되므로 스케줄링 부담이 적지만 유연성이 떨어지는 특징이 있음
• 우선순위가 높은 큐부터 처리되기 때문에 낮은 큐의 프로세스가 처리가 안되는 기아(Starvation)현상이 나타날 수도 있음