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

OS는 CPU 스케줄링을 통해 Ready Queue에 존재하는 프로세스를 선택하여 CPU를 할당합니다.

이 때 어떤 프로세스를 할당한 것인지 결정하는 알고리즘을 'CPU 스케줄링 알고리즘'이라고 합니다.

 

CPU 스케줄링 알고리즘 종류

먼저 스케줄링 알고리즘은 '선점형'과 '비선점형'으로 나눌 수 있습니다.

• 선점형은 하나의 프로세스가 CPU를 차지하고 있는 프로세스를 대신하여 CPU를 점유할 수 있는 방식.
• 비선점형은 선점형과 반대로 하나의 프로세스가 CPU를 점유하고 있다면, 이 프로세스가 종료될 때 까지 다른 프로세스는 CPU를 사용할 수 없는 방식입니다.
• 선점형, 비선점형의 차이를 헷갈리지 않도록 주의
  • 선점하여 다른 프로세스가 선점할 수 없다고 해서 '선점형'이 아니고, 레디 큐에 존재하는 프로세스 관점에서 '선점할 수 있다'는 의미로 '선점형', '선점할 수 없다'는 의미 '비선점형' 로 알아둡시다. 

비선점형 방식은 CPU를 점유하고 있는 다른 프로세스가 종료될 때 까지 할당을 기다리기 때문에, 강제로 프로세스를 중단하지 않으므로 , 인터럽트가 발생하지 않고 따라서 Context Switching으로 인한 부하가 발생하지 않습니다.

 

비선점형 알고리즘에는 대표적으로 FCFS, SJF, 우선순위 알고리즘이 있습니다.

선점형 알고리즘에는 RR, SRF, 다단계 큐 알고리즘이 있습니다.

 

비선점형 알고리즘 - FCFS (First Come First Service)

FCFS

• FCFS는 알고리즘 이름에서 방식을 유추할 수 있습니다. 말 그대로 먼저 들어온 프로세스에 먼저 CPU를 할당해주는 방식입니다.
• FIFO Queue를 통해 프로세스를 관리하여 먼저 들어온 프로세스에 먼저 자원을 할당해줍니다.
• FCFS 알고리즘은 Convoy Effect가 발생할 수 있음.

Convoy Effect : 한 프로세스가 오랫동안 CPU 자원을 점유하여 그 뒤에 들어오는 자원 사용 시간이 짧은 프로세스들의 대기시간이 길어져 전체적인 프로세스의 성능이 저하되는 현상

 

Convoy Effect

 

 

비선점형 알고리즘 - SJF (Shortest Job First)

• 각 프로세스의 Burst Time(자원 사용 시간)을 비교하여 짧은 순서대로 CPU를 할당하는 방식
• 이 때 두 프로세스의 Burst Time이 같다면, 선입선출 스케줄링을 적용.
• SJF 방식은 Starvation 현상이 발생할 수 있음.

Starvation : 긴 시간을 가진 프로세스가 우선순위에서 자꾸 밀려나 실행되지 않는 현상

 

+ 실제 프로세스가 얼만큼 실행되는지 알 수 없기 때문에, 과거 실행시간을 토대로 추측해서 Burst Time을 예측하여 할당하는데, 이조차도 정확하지 않다는 한계가 있습니다.

 

 

비선점형 알고리즘 - 우선순위 

• 기존 SJF에서 발생하는 Starvation의 문제를 해결하기 위한 방식.
  • 오래된 작업일수록 우선순위를 높이는 방법(Aging)을 통해 SJF의 단점을 보완한 알고리즘입니다.
  • 여기서 우선순위는 aging 뿐만 아니라 작업의 시간, 프로세스의 메모리 요구사항, 열린 파일 수, 평균 CPU 사용량 등을 종합한 복합적인 요소를 통해 결정됩니다.
• 우선순위 알고리즘은 "SJF + 우선순위"를 말하는 것 뿐만 아니라 "FCFS + 우선순위"를 활용하여 만들기도 하고, CPU 자원을 점유하고 있는 프로세스를 중단시키고 우선순위에 의거한 프로세스가 기존 프로세스를 중단시키고 선점하도록 하는 선점형 방식도 있습니다.
  • ex) "SJF + 우선순위 + 선점형" = SRTF(Shortest Remaining Time First) 알고리즘 : 새로운 프로세스가 현재 실행중인 프로세스의 남은 시간보다 Burst Time이 짧은 경우 인터럽트를 발생시켜 프로세스를 중단하고 Context Switching을 일으켜 새로운 프로세스를 할당.

 

선점형 알고리즘 - RR (Round Robin)

RR

현대 운영체제가 사용하는 방식인 선점형 방식은 현재 실행중인 프로세스를 알고리즘에 의해 중단시켜버리고 강제로 다른 프로세스에게 CPU 소유권을 할당하는 방식입니다.

 

먼저 Round Robin 방식이 있습니다.

• 각 프로세스에게 "CPU를 점유할 수 있는 동일한 할당 시간"을 주고 그 시간안에 프로세스가 끝나지 않으면 다시 준비 큐의 뒤에 들어가는 알고리즘
• 만약 할당한 시간안에 프로세스가 끝나는 경우 준비 큐에 제일 앞에 있는 다음 프로세스에게 CPU 점유권을 넘깁니다.
• 로드밸런서에서 트래픽 분산 알고리즘으로 사용.

RR의 성능

• 성능이 할당 시간에 매우 많은 영향을 받습니다.
• "할당 시간"이 너무 큼 >  (한 타임 퀀텀 동안 프로세스의 실행이 완료됨) > 먼저 들어온 프로세스가 먼저 자원을 선점하는 FCFS로 이어질 가능성 큼. 
• "할당 시간"이 너무 짧음 > 잦은 Context Switching 발생 > 성능 저하, 비용 증가
• 일반적으로 전체 작업시간은 길어지지만 평균 응답시간은 짧아진다는 특징이 있습니다.

 

선점형 알고리즘 - SRTF ( Shortest Remaining Time First )

• 앞서 말한 "우선순위 + SJF + 선점형" 방식의 알고리즘
• 짧은 버스트 타임을 우선적으로 할당하되, Aging을 통한 우선순위도 함께 부여하여 긴 버스트 타임의 프로세스가 실행되지 않는 단점을 보완할 수 있는 알고리즘.
• 긴 프로세스가 오랫동안 실행되지 않고 있으면 현재 실행되고 있는 프로세스를 중단시켜 선점하도록 함.

 

선점형 알고리즘 - 다단계 큐

• 우선순위마다 별도의 큐를 여러 개 사용하여, 큐마다 Round Robin, FCFS 등 다른 스케줄링 알고리즘을 적용한 방식.
• 큐와 큐 간의 프로세스 이동이 안되고 프로세스들이 시스템 진입 시 영구적으로 하나의 큐에 할당.
• 만약 한 프로세스가 실행하던 도중 인터럽트가 발생하여 준비 큐로 돌아왔다고 했을 때, 기존 수행중이던 프로세스가 있는 큐보다 높은 단계의 큐에 프로세스가 하나라도 있다면 그 프로세스에 CPU를 할당하는 기법. 

 

선점형 알고리즘 - 다단계 피드백 큐

• 다단계 큐와 달리 프로세스가 큐들 사이를 이동하는 것을 허용하는 다단계 피드백 큐 스케줄링 방식.
• 타임 퀀텀 초과 : 프로세스가 할당된 시간 내에 작업을 완료하지 못하면, 다음 우선순위가 낮은 큐로 이동합니다.
• 타임 퀀텀 내 완료 : 프로세스가 할당된 시간 내에 작업을 완료하면, Ready Queue로 프로세스를 이동
• CPU Burst는 낮은 우선순위의 큐, I/O Burst는 높은 우선순위의 큐에 배치
• 단계가 내려갈수록 퀀텀량이 증가하며, 가장 하위 큐는 FCFS 스케줄링을 사용.
• 맨 아래 큐에서 너무 오래 대기하면 다시 상위 큐로 이동.

 

 

<참고 자료>

CPU 스케줄링 알고리즘 (CPU Scheduling Algorithms)

 

[Chapter 5. CPU 스케줄링] 스케줄링 알고리즘(라운드 로빈, 다단계 큐, 다단계 피드백 큐)