스케줄링 알고리즘

스케줄링 알고리즘 평가 기준

기준	설명
CPU 사용률	전체 시스템 동작 시간 중 CPU가 사용된 시간
처리량	단위 시간당 작업을 마친 프로세스의 수
대기 시간	작업을 요청한 프로세스가 작업을 시작하기 전까지 대기하는 시간
응답 시간	프로세스 시작 후 첫번째 출력 또는 반응이 나올 때 까지 걸리는 시간
실행 시간	프로세스가 실제로 실행된 시간
반환 시간	프로세스가 생성된 후 종료될 때까지 걸리는 시간 (대기 시간 + 실행 시간)

CPU 사용률, 처리량은 계산이 어렵기 때문에 나머지 4가지 기준을 계산한다. 그리고 알고리즘 성능 평가에는 주로 평균 대기 시간을 이용한다. 그러나 이 기준도 알고리즘의 절대적인 성능을 보여주는 지표는 아니다.\

알고리즘 평가용 예시

도착 순서	도착 시간	작업 시간
P1	0	30
P2	3	18
P3	6	9

비선점형 알고리즘

FIFO(First In First Out) 스케줄링

준비 큐에 도작한 순서대로 CPU를 할당하는 방식이다. 큐가 하나라 모든 프로세스의 우선순위가 동일하다.

성능

위의 예시를 실행한 결과는 아래 그림과 같다. 평균 대기 시간은 (0 + 27 + 42) / 3 = 23이다.

장점

단순하고 공평하다.

단점

처리 시간이 긴 프로세스가 CPU를 차지할 때 다른 프로세스들이 오래 대기하여 시스템의 효율성이 떨어진다. 이를 콘보이 효과(convoy effect)라 한다.

SJF(Shortest Job First) 스케줄링

준비 큐에서 실행 시간이 가장 짧은 프로세스부터 CPU를 할당하는 방식이다.

성능

위의 예시를 실행한 결과는 아래 그림과 같다. 평균 대기 시간은 (0 + 24 + 36) / 3 = 20이다.

장점

처리 시간이 짧은 작업을 먼저 실행하기 때문에 효율적이다. 콘보이 효과가 해결된다.

단점1. 운영체제가 프로세스의 종료 시간을 예측하기 어렵다.

*현대 프로세스의 경우 사용자와의 상호작용이 빈번하여 종료 시간을 파악하기 어렵고, 따라서 작업 길이를 추정하는 것이 어렵다.

단점2. 공평하지 못하다.

짧은 프로세스가 계속 준비 큐에 들어오는 경우 긴 프로세스의 작업이 계속 연기되는데, 이를 아사(starvation) 현상이라 한다.

HRN(Highest Response Ratio Next) 스케줄링

서비스를 받기 위해 기다린 시간(대기 시간)과 CPU 사용 시간을 고려하여 우선순위를 계산하고, 스케줄링을 하는 방식이다. 우선순위는 다음과 같이 계산한다.

우선순위 = (대기 시간 + CPU 사용 시간)/(CPU 사용 시간)

성능

위 예시를 실행한 결과는 아래 그림과 같다. 더 높은 우선순위를 가지는 P3가 먼저 실행된다.

평가

실행 시간이 짧은 프로세스의 우선순위를 높게 설정하면서도 대기 시간을 고려하기 때문에 아사 현상이 완화된다. 그러나 여전히 공평성이 위배되어 잘 사용되지는 않는다.

선점형 알고리즘

라운드 로빈(Round Robin) 스케줄링

각 프로세스를 일정한 시간(타임 슬라이스) 만큼 실행하고 작업을 완료하지 못하면 준비 큐의 맨 뒤로 들어가는 방식이다.

성능

타임 슬라이스가 10일 때, 위 예시에 대한 실행결과는 아래 그림과 같다.

우선 가장 먼저 도착한 P1이 타임 슬라이스만큼 실행된다. 이후 준비 큐의 뒤로 들어간다. 그 다음 두번째로 도착한 P2가 타임 슬라이스만큼 실행되고, 준비 큐의 맨 뒤로 들어간다. 그 다음 P3는 전체 실행 시간이 타임 슬라이스보다 짧으므로 실행을 완전히 마친다.

그 다음 P1이 실행된 후 준비 큐의 맨 뒤로 들어가고, P2가 8만큼 실행하여 실행을 완전히 마친다. 그 다음 P1도 나머지 시간만큼 실행하여 실행을 완전히 마친다.

전체 대기 시간은 67이고, 평균 대기 시간은 67 / 3 = 22.33이다.

타임 슬라이스의 크기와 문맥 교환

위 예시를 실행했을 때 평균 대기 시간을 비교하면 FIFO가 23, 라운드 로빈이 22.33으로 라운드 로빈이 약간 우세하다. 그러나 라운드 로빈이 더 효율적이라고 결론지을 수는 없다. 선점형 알고리즘의 경우 프로세스의 일부만 실행한 다음 다른 프로세스를 실행하므로 문맥 교환이 필요하기 때문이다. 문맥 교환 시간까지 고려하면 라운드 로빈이 더 비효율적일 수도 있다.

또한 타임 슬라이스의 크기가 프로세스의 반응 시간과 시스템 성능에 영향을 끼칠 수 있다. 타임 슬라이스가 큰 경우, FCFS 스케줄링과 큰 차이가 없게 된다. 따라서 문맥 교환이 거의 없어 시스템 성능은 괜찮지만, 프로세스의 반응 속도가 느려질 것이다. 반면 타임 슬라이스가 작은 경우, 문맥 교환이 너무 자주 일어나 시스템 성능이 떨어지고, 문맥 교환에 걸리는 시간이 실제 작업 시간보다 커지게 된다.

따라서 반응 속도를 위해 타임 슬라이스를 되도록 작게 설정하되 문맥 교환에 걸리는 시간이 과도하게 길어지지 않도록 해야 한다.

SRT(Shortest Remaining Time) 스케줄링

각 프로세스를 타임 슬라이스 만큼 실행한 다음, 다음 실행할 프로세스를 선택할 때 남은 실행 시간이 가장 짧은 프로세스부터 실행하는 방식이다.

성능

위 예시에 대한 실행 결과는 아래 그림과 같다.

우선 P1이 타임 슬라이스만큼 실행되고, 큐에 들어간다. 그 다음 3개 프로세스 중 남은 실행 시간이 9로 가장 짧은 P3가 먼저 실행되고, 타임 슬라이스 안에 실행을 모두 마친다. 그 다음 남은 시간이 적은 P2가 타임 슬라이스만큼 실행되고, 또 P2가 다시 실행되고 실행을 완전히 마친다. 그 다음 P1이 타임 슬라이스 단위로 끊기면서 실행된다.

전체 대기 시간은 47이고, 평균 대기 시간은 47 / 3 = 15.66이다.

평가

SJF 스케줄링보다 평균 대기 시간이 짧지만, 효율적이라고 결론 짓기는 어렵다. 현재 실행 중인 프로세스와 큐에 있는 프로세스의 남은 시간을 주기적으로 계산해야 하기 때문이다. 또한 프로세스의 종료 시간을 예측하기 어렵고 아사 현상이 일어나기 때문에 잘 사용하지 않는다.

다단계 큐(multi-level queue) 스케줄링

우선순위에 따라 준비 큐를 여러 개 사용하는 방식으로, 고정형 우선순위를 사용한다. 그리고 라운드 로빈으로 스케줄링을 하며, 높은 우선순위의 큐에 있는 모든 프로세스를 실행해야 다음 우선순위 큐의 프로세스를 실행할 수 있다.

우선순위에 따라 타임 슬라이스를 조절하여 작업 효율을 높일 수도 있다. 예를 들어 전면 프로세스는 빠른 반응 속도를 위해 타임 슬라이스를 작게 하고, 후면 프로세스는 타임 슬라이스를 무한대로 하여 FCFS로 처리할 수 있다.

그러나 무조건 우선순위가 높은 프로세스부터 실행되기 때문에 우선순위가 낮은 프로세스에게 아사 현상이 일어날 수 있다.

다단계 큐(multi-level feedback queue) 스케줄링

다단계 큐처럼 우선순위 별로 큐를 사용하고, 라운드 로빈 방식을 사용하며, 높은 우선순위의 큐가 비어 있어야 다음 우선순위 큐의 프로세스를 실행할 수 있다. 그러나 다단계 큐와의 차이점이 있는데, 바로 CPU를 사용한 이후 프로세스의 우선순위가 낮아지는 것이다. 프로세스는 타임 슬라이스만큼 실행된 후 원래 큐에 돌아가지 않고, 우선순위가 하나 낮은 큐의 맨 뒤로 들어간다. 이를 통해 우선순위가 낮은 프로세스의 실행이 연기되는 문제를 해결할 수 있다. 커널 프로세스가 일반 프로세스의 큐에 들어가지는 않는다.

또 다른 특징은 우선순위가 낮을수록 타임 슬라이스가 길어지는 것이다. 이를 통해 우선순위가 낮은 프로세스가 어렵게 CPU를 얻은 경우 좀 더 오랫동안 사용할 수 있게 한다. 가장 낮은 우선순위 큐의 경우, 타임 슬라이스를 무한대로 하여 FCFS로 처리한다. 다단계 피드백 큐 스케줄링은 오늘날의 운영체제가 일반적으로 사용하는 스케줄링 방식이다.

Reference

쉽게 배우는 운영체제