[운영체제] CPU 스케줄링 알고리즘

이 글은 "면접을 위한 CS 전공지식 노트(주홍철 저)" 를 읽고 정리한 글 입니다.

면접을 위한 CS 전공지식 노트 - YES24

 

CPU 스케줄링 알고리즘은 OS가 프로세스의 CPU 점유를 강제로 뺏을 수 있는 지의 여부에 따라 비선점형 방식 / 선점형 방식 으로 나뉜다.

 

비선점형 CPU 스케줄링

FCFS (First Come First Served)

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

 

장점

• 구현이 쉽다.

단점

• 길게 수행되는 프로세스 때문에 준비 큐에서 오래 기다리는 현상(convoy effect) 발생

SJF (Shortest Job First)

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

 

장점

• 평균 대기 시간이 가장 짧다.

단점

• 기아(starvation) 현상(=무한히 기다리는 현상)이 나타날 수 있다.
• 실제로는 실행시간을 알 수 없기 때문에 과거에 실행했던 시간을 토대로 추측 => 완벽한 구현 어렵다.

우선순위 (Priority Scheduling)

기존 SJF 방식에서 기아 현상을 보완한 알고리즘

 

장점

• 기아현상 해결 (실행시간이 긴 프로세스에 대한 기아현상 해결)

단점

• 기아현상 발생 (우선순위가 낮은 프로세스에서 기아현상 발생)

선점형 CPU 스케줄링

라운드 로빈 (RR)

각 프로세스에 동일한 할당시간을 주고 그 시간안에 끝나지 않으면 다시 준비 큐로 넣는 알고리즘.

 

SRF (Shortest Remaining Time First)

실시간으로 가장 짧은 수행시간의 프로세스를 실행하는 알고리즘.

 

다단계 큐

우선순위에 따른 준비 큐를 여러개 사용하고, 큐마다 다른 스케줄링 알고리즘을 적용하는 것

스케줄링 부담은 적다

다만, 큐 간의 프로세스 이동은 안됨. => 유연성이 떨어진다.