CPU 스케쥴링

CPU 스케쥴링은 멀티태스킹 환경에서 여러 프로세스들이 CPU를 사용하는 방식을 관리하는 것이다. 다양한 알고리즘들이 존재하며 준비 큐(Ready Queue)에서 대기하는 프로세스들을 대상으로 진행된다.

스케쥴링 기준

그렇다면 효율적인 스케쥴링 알고리즘을 선택하는 기준은 무엇일까? 아래 기준들을 고려하며 선택한다.

• CPU 이용률 (utilization)

• 처리량 (throughput)

• ⭐️ 총처리 시간 (turnaround time)

  • 대기시간을 포함한 I/O 시간, CPU 실행 시간을 합친 모든 시간

• ⭐️ 대기 시간 (waiting time)

  • 준비 큐에서 대기한 총시간

• 응답 시간 (response time)

CPU 이용률과 처리량이 최대이고 시간들을 줄일 수 있다면 최적의 알고리즘이겠지만 보통 총처리 시간 과 대기 시간 을 얼마나 줄일 수 있는지에 대해 고민한다.

CPU 스케쥴링 알고리즘 종류

FCFS(First - Come - First - Served)

개념

FCFS (First-Come-First-Serve) 스케쥴링 알고리즘은 도착한 순서대로 프로세스를 실행하는 가장 기본적인 알고리즘이다. 즉, 먼저 도착한 프로세스가 먼저 실행된다. 이 알고리즘은 구현이 간단하고 공정한 스케쥴링이 가능하다.

문제점

• 호의 효과 (convoy effect)

  실행 시간이 긴 프로세스가 먼저 도착하면 대기 시간이 길어지는 문제가 있습니다. 이를 해결하기 위해 SJF 스케쥴링 알고리즘 등이 개발됐다.

SJF(Shortest - Job - First)

개념

Shortest-Job-First (SJF) 스케쥴링 알고리즘은 실행 시간(CPU burst)이 가장 짧은 프로세스를 먼저 실행하는 방식이다. 앞선 convoy effect를 완전히 해소 시킬 수 있는 알고리즘이다.

문제점

• 실행 시간을 미리 알 수 없는 상황에서는 사용이 어렵다.

  프로세스들의 실행 시간을 미리 정확하게 예측하는 방법이 불가능하기에 사용이 어렵다.

• starvation

  SJF는 극단적으로 CPU 사용이 짧은 job을 선호하기에 사용시간이 긴 프로세스는 거의 영원히 CPU를 할당받을 수 없는 문제가 생긴다.

해결책

• 다음 CPU burst 시간 근사값 추정

  일반적으로 측정된 이전의 CPU 버스트들의 길이를 지수 평균한 것으로 예측한다.

• RR이나 다른 알고리즘을 활용해 모든 프로세스가 CPU에 할당할 수 있도록 해준다.

선점형 스케쥴링 vs 비선점형 스케쥴링 (preemptive vs Non-preemptive)

여태까지 설명한 스케쥴링은 비선점형 스케쥴링이다. CPU 스케쥴링엔 크게 두가지 유형인 선점형과 비선점형이 존재한다. 아래는 각각의 개념을 적어봤다.

• 선점형 스케쥴링 현재 실행 중인 프로세스를 중단시키고, 다른 프로세스가 CPU를 사용할 수 있도록 하는 방식이다. 선점형 스케쥴링 알고리즘에는 Round Robin, Priority-based Scheduling 등이 있습니다.

• 비선점형 스케쥴링

  현재 실행 중인 프로세스가 종료되거나 입출력 등의 이유로 대기 상태로 들어갈 때까지 CPU를 계속 사용한다. 비선점형 스케쥴링 알고리즘에는 First-Come-First-Serve, Shortest-Job-First 등이 있다.

SRTF (Shortest Remaining Time First)

개념

SRTF는 실행중인 프로세스 중에 남은 실행 시간이 가장 짧은 프로세스를 먼저 실행하는 선점형 스케줄링 알고리즘이다. 프로세스의 도착 시간, 실행 시간, 남은 실행 시간을 고려하여 다음 실행할 프로세스를 결정한다. 만약 실행 중인 프로세스보다 더 짧은 실행 시간을 가진 새로운 프로세스가 도착하면, 실행 중인 프로세스를 중단하고 새로운 프로세스를 실행한다. SRTF는 SJF 알고리즘의 선점형 버전이라고 생각할 수 있다.

문제점

• starvation

  SRTF도 마찬가지로 SJF와 같은 문제점을 공유한다.

• CPU 사용시간(CPU burst time)을 측정할 수 없다.

  새로운 프로세스가 올 때마다 스케쥴링을 다시하기 때문이다.

Round Robin

개념

Round Robin은 각 프로세스에 일정한 시간할당량(time quantum)이 순환적으로 할당되는 선점형 스케줄링 알고리즘이며 가장 현대적인 스케쥴링 기법이다.

특징

• 각 프로세스는 정해진 시간할당량만큼 CPU를 사용할 수 있다.

• 시간 안에 다 끝내지 못한 프로세스는 ready queue의 제일 뒤에서 다시 대기한다.

• CPU 사용시간이 랜덤한 프로세스들이 있을 때 효율적이다.

• RR이 가능한 이유는 프로세스의 context를 save할 수 있기 때문이다.

장점

• Response time이 빨라진다.

  준비 큐에 n개의 프로세스가 있고 시간 할당량 q이면, 각 프로세스는 최대 q 시간 단위로 CPU시간을 1 / n 을 얻는다. 각 프로세스는 자신의 다음 시간 할당량이 할당될 때까지 (n-1) X q 시간 이상을 기다리지 않는다.

• 프로세스가 기다리는 시간이 CPU를 사용할 만큼 증가한다.

주의할 점

• 적당한 시간 할당량 크기 설정을 해줘야한다.

  시간 할당량을 너무 크게 설정할 시에 FCFS와 같은 성능이 나오게 된다.

  그렇다고 시간할당량을 너무 작게 줄시에 Context Switch가 많이 일어나서 overhead가 발생하며 오히려 성능이 더 낮아진다.

우선순위 기반 스케쥴링 (Priority - based Scheduling)

개념

우선순위 기반 스케줄링은 각 프로세스에 우선순위를 할당하여 우선순위가 높은 프로세스가 먼저 실행되도록 하는 방식이다. 이 우선순위는 프로세스의 중요도, 긴급성, 처리 시간 등에 따라 결정된다.

예를 들어, 우선순위가 높은 프로세스는 CPU를 먼저 할당받으며, 우선순위가 낮은 프로세스는 CPU를 할당받기까지 대기해야 한다. 이 알고리즘은 시스템의 응답 시간을 빠르게 하기 위해 사용할 수 있으며, 실시간 시스템에서도 사용될 수 있습니다.

특징

• 선점형 스케쥴링 방식

  더 높은 우선순위의 프로세스가 도착하면 실행중인 프로세스를 멈추고 CPU 를 선점한다.

• 비선점형 스케쥴링 방식

  더 높은 우선순위의 프로세스가 도착하면 Ready Queue 의 Head 에 넣는다.****

문제점

• starvation

• 무기한 봉쇄(Indefinite blocking)

  실행 준비는 되어있으나 CPU 를 사용못하는 프로세스를 CPU 가 무기한 대기하는 상태

해결책

• aging

  아무리 우선순위가 낮은 프로세스라도 오래 기다리면 우선순위를 높여준다.

참고 자료

• https://github.com/JaeYeopHan/Interview_Question_for_Beginner/

• 운영체제 Operating System Concepts 10판(퍼스트북, 2020)