운영체제 - CPU 스케줄링

CPU 스케줄링이란?

CPU 스케줄러는 CPU 스케줄링 알고리즘에 따라 프로세스에서 해야 하는 일을 스레드 단위로 CPU에 할당한다. 다중 프로그래밍의 목적은 CPU 이용률을 최대화하기 위해 항상 실행 중인 프로세스를 가지게 하는데 있다. 어떤 프로세스가 대기해야 할 경우, 운영체제는 CPU를 그 프로세스로부터 회수해 다른 프로세스에 할당한다. 즉, CPU 이용률을 최대화 하는 것은 다중 프로세서 운영체제 설계의 핵심이다.

 

CPU - I/O 버스트 사이클 (CPU - I/O Burst Cycle)

프로세스 실행은 CPU 실행과 I/O 대기의 사이클로 구성된다.
프로세스의 실행은 CPU Burst로 시작된다. 뒤이어 I/O Burst가 발생하고, 그 뒤를 이어 또 다른 CPU Burst가 발생하며, 이어 또 다른 I/O Burst 등등으로 진행된다. 결국 아래의 그림처럼 마지막 CPU Burst는 실행을 종료하기 위한 시스템 요청과 함께 끝난다.

 

 

CPU 스케줄링 알고리즘 종류

1. 비선점형 방식

비선점형 방식은 프로세스가 스스로 CPU 소유권을 포기하는 방식이며, 강제로 프로세스를 중지하지 않는다. 따라서 컨텍스트 스위칭으로 인한 부하가 적다.

 

1-1. FCFS(First Come, First Served)

FCFS는 가장 먼저 온 것을 가장 먼저 처리하는 알고리즘이다. 일단 CPU가 한 프로세스에 할당되면, 그 프로세스가 종료하거나 I/O 처리를 요구할 때까지 CPU를 점유한다.

 

길게 수행되는 프로세스 때문에 '준비 큐에서 오래 기다리는 현상(convoy effect)'이 발생하는 단점이 있다.

Convoy Effect (호위 효과)란?
Convoy Effect는 CPU 작업 시간이 긴 프로세스가 먼저 실행되면, 뒤따르는 짧은 프로세스들이 오랫동안 기다려야 하는 현상.

 

1-2. SJF(Shortest Job First)

SJF는 실행 시간이 가장 짧은 프로세스를 가장 먼저 실행하는 알고리즘이다. 긴 시간을 가진 프로세스가 실행되지 않은 현상(starvation)이 일어나며, 평균 대기 시간이 가장 짧다. 하지만 실제로는 실행 시간을 알 수 없기 때문에 과거의 실행했던 시간을 토대로 추측해서 사용한다.

Starvation(기아 현상)이란?
Starvation(기아 현상)은 우선순위 기반 스케줄링에서 우선순위가 낮은 프로세스가 CPU를 할당받지 못하고 계속 대기하는 현상

 

1-3. 우선순위(Priority Scheduling)

기존 SJF 스케줄링의 경우 긴 시간을 가진 프로세스가 실행되지 않는 현상이 있었다. 이는 오래된 작업일수록 '우선순위를 높이는 방법(aging)'을 통해 단점을 보완한 알고리즘을 말한다.

에이징(Aging)은 오랫동안 대기한 프로세스의 우선순위를 점진적으로 증가시키는 방식이다.

 

2. 선점형 방식

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

 

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

라운드 로빈은 현대 컴퓨터가 쓰는 스케줄링인 우선순위 스케줄링의 일종으로, 각 프로세스는 동일한 할당 시간을 주고 그 시간 안에 끝나지 않으면 다시 준비 큐의 뒤로 가는 알고리즘이다.

예를 들어, q만큼의 할당 시간이 부여되었고 N개의 프로세스가 운영된다고 하면 (N-1)*q 시간이 지나면 자기 차례가 오게 된다. 할당 시간이 너무 크면 FCFS가 되고 짧으면 컨텍스트 스위칭이 잦아져서 오버헤드, 즉 비용이 커진다. 일반적으로 전체 작업 시간은 길어지지만 평균 응답 시간은 짧아진다는 특징이 있다. 

또한, 이 알고리즘은 로드밸런서에서 트래픽 분산 알고리즘으로도 쓰인다.

 

2-2. SRF

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

 

2-3. 다단계 큐

다단계 큐는 우선순위의 따른 준비 큐를 여러 개 사용하고, 큐마다 라운드 로빈이나 FCFS 등 다른 스케줄링 알고리즘을 적용한 것을 말한다. 큐 간의 프로세스 이동이 안 되므로 스케줄링 부담이 적지만 유연성이 떨어지는 특징이 있다.

 

 

[참고]

https://prao.tistory.com/entry/%EC%89%BD%EA%B2%8C-%EB%B0%B0%EC%9A%B0%EB%8A%94-%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-4-CPU-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81

[쉽게 배우는 운영체제] 4. CPU 스케줄링

https://imbf.github.io/computer-science(cs)/2020/10/18/CPU-Scheduling.html

[Operating System - Chapter 5] CPU 스케줄링