13. 스케줄링 알고리즘

1. 스케줄링 알고리즘 선택 기준

좋은 스케줄링 알고리즘이란 무엇일까? 여러 기준이 있겠지만 가장 많이 사용되는 평가 기준은 아래와 같다.

 

 

CPU 사용률

전체 시스템의 동작 시간 중 CPU가 사용된 시간을 측정하는 방법. 100%가 가장 이상적이지만 실제로는 여러 가지 이유로 90%에도 미치지 못한다.

 

 

처리량

단위 시간당 작업을 마친 프로세스의 수로, 이 수치가 클수록 좋은 알고리즘이다.

 

 

대기 시간

작업을 요청한 프로세스가 작업을 시작하기 전까지 대기하는 시간으로 짧을수록 좋다.

 

 

응답 시간

프로세스 시작 후 첫 번째 출력 또는 반응이 나오기까지 걸린 시간으로 짧을수록 좋다.

 

 

반환 시간

프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반환하는 데까지 걸린시간이다. 반환 시간 = 대기 시간 + 실행 시간이다.

 

CPU 알고리즘을 평가할 때 CPU 사용률과 처리량은 계산하기 어렵기 때문에 주로 대기 시간, 응답 시간, 반환 시간을 기준으로 평가한다. 그 중에서도 주로 모든 프로세스의 대기 시간을 프로세스의 수로 나눈 값인 평균 대기 시간을 많이 본다.

 

하지만 평균 대기 시간이 절대적인 기준은 아니다. 프로세스의 순서에 따라 정말 효율적일 수도, 최악의 효율일 수도 있기 때문이다. 참고용으로만 생각하자.

 

 

 

2. 스케줄링 알고리즘의 종류

FCFS 스케줄링

First Come First Served. 먼저 온 놈 먼저 처리하는 알고리즘이다. 비선점형 방식이고 하나의 큐만 사용한다. 단순하고 공평하지만, 처리 시간이 긴 프로세스로 인해 다른 프로세스들의 대기 시간이 길어질 수 있어 비효율적이다.

 

또한 비선점형(일괄 작업 방식)이기 때문에 입출력을 요청한 프로세스가 입출력이 끝날 때까지 대기하는 시간 동안 CPU는 놀아야 한다.

 

 

SJF 스케줄링

Shortest Job First. 작업 시간이 가장 짧은 놈 먼저 처리하는 방식이다. 비선점형 방식이다. 빨리 끝나는 작업을 먼저 실행하기 때문에 시스템의 효율성도 좋아진다. 하지만 한계가 있다.

 

작업 시간이 가장 짧은 놈이 누군지 가려내기 어렵다. 이 프로세스가 언제 끝날지 운영체제가 어떻게 알겠는가. 또한 작업 시간이 긴 놈은 평생동안 기다려도 실행되지 않을 수도 있다. 불공평하다.

 

 

HRN 스케줄링

Highest Response Ratio Next. 서비스를 받기 위해 기다린 시간과 CPU 사용 시간을 고려하여 스케줄링을 하는 방식이다. 우선 순위 = (대기 시간 + CPU 사용 시간) / CPU 사용 시간. 이 공식을 이용해 프로세스마다 우선순위를 산정한다.

 

대기 시간까지 고려하기 때문에 SJF에 비해서는 공평하다고 볼 수 있다. 하지만 그럼에도 여전히 작업시간이 긴 프로세스는 오래 기다려야 하는 불공평이 발생한다.

 

 

라운드 로빈 스케줄링

한 프로세스가 할당받은 시간(타임 슬라이스)동안 작업을 하다가 완료되지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 선점형 방식이다.

 

라운드 로빈은 타임 슬라이스의 크기에 따라 성능이 달라질 수 있다. 크기가 클수록 FCFS에 가까워지고 크기가 작을수록 문맥 교환으로 인한 오버헤드가 많이 발생한다. 이를 고려하여 적절한 크기의 타임 슬라이스를 설정하는 것이 중요하다.

 

 

SRT 우선 스케줄링

SJF 스케줄링과 라운드 로빈 스케줄링을 혼합한 방식이다. 기본적으로 라운드 로빈 방식으로 돌면서 남아 있는 작업 시간이 가장 적은 프로세스를 할당한다.

 

성능이 나쁘지 않지만 잦은 문맥 교환과 종료 시간을 예측하기 어렵다는 점에서 잘 사용되지 않는다.

 

 

우선순위 스케줄링

프로세스에 임의의 기준으로 우선순위를 부여하여 스케줄링하는 방식이다. 선점형, 비선점형 모두 가능하며 경우에 따라 우선순위가 고정되기도 바뀌기도 한다.

 

우선순위가 높은 프로세스가 무조건 먼저 실행되므로 불공평하고 아사 현상을 일으킬 수 있다. 그럼에도 프로세스의 우선순위는 시스템의 효율성보다도 프로세스의 중요도를 기준으로 결정된다. 중요한 프로세스는 빨리 실행되어야 하기 때문이다.

 

 

다단계 큐 스케줄링

우선순위에 따라 준비 큐를 여러 개 사용하는 방식이다. 우선순위가 높은 큐부터 낮은 큐까지 있으며, 우선순위가 높은 큐가 비워질 때까지 낮은 큐에 있는 프로세스는 실행되지 않는다. 우선순위는 한 번 정해지면 종료될 때까지 변하지 않으며, 라운드 로빈 방식이다.

 

큐의 우선순위에 따라 다른 타임 슬라이스를 줌으로써 우선순위별로 최적의 전략을 사용하는 것도 가능하다. 하지만 우선순위가 높은 프로세스 때문에 낮은 프로세스의 대기 시간이 길어진다는 단점이 있다. 이를 보완한 것이 아래 전략이다.

 

 

다단계 피드백 큐 스케줄링

기본적으로는 다단계 큐 스케줄링과 같지만 한 번 CPU를 할당받아 실행을 마친 프로세스는 한 단계 낮은 우선순위 큐의 끝으로 들어간다. 이를 통해 다단계 큐 스케줄링의 단점을 어느 정도 보완한다. 물론 그렇다고 해서 커널 프로세스가 일반 프로세스 큐로 들어가지는 않는다.

 

그럼에도 우선순위가 낮은 프로세스는 실행 기회를 얻기 쉽지 않기 때문에 우선순위가 낮을수록 큰 타임 슬라이스를 부여한다. 마지막 큐의 타임 슬라이스는 무한대다. 즉, 프로세스는 끝날 때까지 CPU를 계속 차지할 수 있게 되는 것이다.

 

다단계 피드백 큐 스케줄링은 오늘날의 운영체제가 일반적으로 사용하는 방법이다.