[CPU 스케줄링 알고리즘]

CPU 스케줄링은 CPU 스케줄링 알고리즘에 따라 프로세스에서 해야 하는 일을 스레드 단위로 CPU에 할당한다. 프로그램이 실행될 때는 어떤 프로그램에 CPU 소유권을 줄 것인지 결정한다. 알고리즘은 CPU 이용률은 높게 하면서 주어진 시간에 많은 일을 수행하는 것이 목표이다. 즉, Ready Queue에 있는 프로세스를 적게, 응답 시간은 짧게 설정하는 것이 목표이다. CPU 스케줄링 알고리즘은 비선점형 방식과 선점형 방식으로 나뉜다.

 

비선점형 방식

비선점형 방식은 프로세스가 CPU 소유권을 스스로 포기하며, 강제로 프로세스를 중지하지 않는다. 따라서 컨텍스트 스위칭으로 인한 부하를 줄일 수 있다는 장점이 있다. 대표적으로 FCFS, SJF 그리고 우선순위 알고리즘이 있다.

1) FCFS (Fist Come, First Served)

가장 먼저 들어온 것을 가장 먼저 처리하는 알고리즘이다.

• 작업 완료 시간을 예측하기 용이하다.
• 중요한 작업이 Ready Queue 에서 오래 기다리는 현상(convoy effect)이 발생하는 단점이 있다.
  EX) CPU 처리시간이 길지만 덜 중요한 작업이, CPU 처리 시간이 짧고 더 중요한 작업을 기다리게 할 수도 있다.

2) SJF (Shortest Job First)

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

• 평균 대기 시간이 가장 짧다.
• 콘보이 효과 완화
• 긴 처리 시간을 가진 프로세스가 실행되지 않는 현상(starvation)이 발생하는 단점이 있다.

3) 우선순위

대기중인 프로세스에게 우선순위를 부여해 우선순위가 높은 프로세스에게 CPU를 먼저 할당하는 알고리즘

우선순위가 같은 프로세스는 FCFS로 스케줄된다.

• 선점형 또는 비선점형이 될 수 있다.
• 대기시간이 늘어날수록 프로세스의 우선순위를 높이는 방법인 aging을 통해 SJF의 기아 현상을 보완한다.

 

선점형 방식

CPU를 사용하고 있는 프로세스를 알고리즘에 의해 중단시켜 버리고 강제로 다른 프로세스에 CPU 소유권을 할당할 수 있는 방식이다. 현대 운영체제가 쓰는 방식이다. 대표적으로 라운드 로빈, SRF, 다단계 큐 알고리즘이 있다.

1) 라운드 로빈 (RR, Round Robin)

우선순위 스케줄링의 일종으로 각 프로세스에게 동일한 할당 시간을 주고 그 시간이 끝나면 다시 준비 큐의 뒤로 가는 알고리즘이다

• 모든 프로세스가 최초 응답 시간을 빠르게 보장받을 수 있다. 자연스럽게 콘보이 효과도 줄어든다.
• 적당한 할당 시간(Time Quantum)을 설정하는 것이 중요하다. 보통 10~100ms로 설정한다.
  EX) 할당 시간이 너무 크면 FCFS가 되고 너무 짧으면 컨텍스트 스위칭이 잦아져서 오버헤드, 즉 비용이 커진다.
• 일반적으로 전체 작업 시간이 길어진다.

2) SRF (Shortest Remaining Time First) 

SJF의 선점형 스케줄링 방식이다. SJF는 중간에 실행 시간이 더 짧은 작업이 들어와도 기존의 작업을 모두 수행하고 그다음 작업을 이어나가지만, SRF는 중간에 더 짧은 작업이 들어오면 수행하던 프로세스를 중지하고 해당 프로세스를 수행하는 알고리즘이다.

• 긴 처리 시간을 가진 프로세스가 실행되지 않는 현상(starvation)이 발생하는 단점이 있다.
• 새로운 프로세스가 들어올 때마다 스케줄링이 변경되므로 CPU 사용시간(burst time)을 정확히 예측하기 어렵다.

3) 다단계 큐 (MLQ, Multi Level Queue)

우선순위에 따라 준비 큐를 여러 개 사용하고, 큐마다 다른 스케줄링 알고리즘을 적용한 것을 말한다. 우선순위가 낮은 큐에서 작업 실행 중이다가도 상위 단계의 큐에 프로세스가 도착하면 CPU 소유권을 빼앗는다.

• 큐들 간의 프로세스 이동이 불가하기 때문에 스케줄링 부담이 적지만 유연성이 떨어진다.
• 우선순위가 낮은 프로레스에서 기아 현상(starvation)이 발생할 수 있다.