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

스케줄링은 크게 선점형, 비선점형으로 나뉜다.

 

1 비선점형 스케줄링

 

FCFS 스케줄링

FCFS는 First Come First Served의 약자로 준비 큐에 도착한 순서대로 CPU를 할당하는 방식이다. 선입선출 스케줄링이라고도 한다. 프로세스가 큐에 도착한 순서대로 실행되며 한번 실행되면 종료될때까지 실행한다.

 

FCFS 스케줄링은 단순하고 공평하지만 처리 시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스들이 하염없이 기다려 시스템의 효율성이 떨어지는 문제가 있는데, 이를 콘보이 효과라고 한다.

 

SJF 스케줄링

Shortest Job First의 줄임말로 준비 큐에 있는 프로세스 중에 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 방식이다.

SJF 스케줄링은 작은 작업을 먼저 실행하므로 시스템의 효율성이 좋아진다. 그러나 다음의 이유로 사용하기가 힘들다.

운영체제가 프로세스의 종료 시간을 정확하게 예측하기 힘들다. 사용자와의 상호작용이 빈번히 발생하는 현대의 프로세스는 프로그램의 종료 시간을 파악하기 어렵다. 

또한 공평하지 못하다. 만약 작업 시간이 작은 프로세스가 계속 큐에 들어오면, 작업 시간이 긴 프로세스가 무한히 연기되는 경우가 있는데 이를 아사 현상 또는 무한 봉쇄 현상이라고 한다.

 

HRN 스케줄링

Highest Response Ratio Next 스케줄링은 아사 현상을 해결하기 위한 스케줄링으로, 최고 응답률 우선 스케줄링이라고도 한다. 서비스를 받기 위해 기다린 시간과 CPU 사용 시간을 고려하여 우선순위를 결정한다.

우선순위 = (대기시간 + CPU 사용시간) / CPU 사용시간 으로 계산되어 아사 현상을 완화한다.

 

2. 선점형 스케줄링

 

RR 스케줄링

Round Robin 스케줄링은 한 프로세스가 할당받은 시간 동안 작업을 하다가 작업을 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식이다. 가장 단순하고 대표적인 방식이다.

FCFS와 유사하지만 일정 타임 슬라이스 내에 작업이 끝나지 않으면 다시 큐에 삽입되는 것이 차이이다.

이 타임 슬라이스 크기가 매우 크다면 FCFS와 같아지고, 작은 경우 Context Switching 이 자주 발생하므로 시스템의 전반적인 성능이 떨어진다.

 

SRT 스케줄링

Shortest Remaining Time 스케줄링은 최소 잔류 시간 우선 스케줄링이라고도 한다. CPU를 할당받을 프로세스를 선택할 때 남아 있는 작업 시간이 가장 적은 프로세스를 선택한다.

그러나 남은 시간을 주기적으로 계산하고 Context Switching이 자주 발생하기 때문에 잘 사용하지 않는다.

 

3 우선순위 스케줄링

우선순위 스케줄링은 프로세스의 중요도에 따라 부여받은 우선순위를 반영한 스케줄링 알고리즘이다.

시스템의 효율성은 마찬가지로 떨어질 수 있으나, 커널 프로세스와 같은 중요한 프로세스를 위해 효율성보다 프로세스의 중요도를 생각해서 구현한다.

 

다단계 큐 스케줄링

Multilevel Queue 스케줄링은 우선순위에 따라 준비 큐를 여러개 사용하는 방식이다. 우선순위가 높은 큐에 있는 프로세스가 모두 끝나야 다음 우선순위의 작업이 시작된다.

이 스케줄링은 선점형 방식으로 고정형 우선순위를 사용한다. 

우선순위가 높은 프로세스의 작업이 끝나기 전엔 낮은 프로세스의 작업을 할 수 없는데, 이런 문제를 해결하기 위해 다단계 피드백 큐 스케줄링이 등장한다.

 

다당계 피드백 큐 스케줄링

Multilevel Feedback Queue 스케줄링은 CPU를 사용하고 난 프로세스의 우선순위가 낮아진다. CPU를 사용한 뒤 원래 큐가 아닌 우선순위가 하나 낮은 큐의 끝으로 들어가는 것이다. 또한 우선순위마다 타임 슬라이스의 크기가 다르므로, 우선순위가 낮은 프로세스들이 어렵게 얻은 CPU를 좀 더 오래동안 사용할 수 있도록 조정한다.