CPU 스케줄러
FCFS 스케줄링
FCFS 스케줄링은 준비 큐에 도착한 수선대로 CPU를 할당하는 비선점형 방식으로 선입선출 스케줄링이라고도 한다. 초기 일관 작업 시스템에서 사용되었던 FCFS 스케줄링은 프로세스가 큐에 도착한 순서대로 실행, 비선점형 방식이기에 프로세스가 끝나야 다음 프로세스가 실행할 수 있다. 게다가 큐가 하나라 모든 프로세스는 우선순위가 동일하다.
프로세스 P1은 도착하자마자 실행되고, 프로세스 P2는 3밀리초에 도착하여 27밀리초를 기다린 후 실행, 프로세스 P3은 6밀리초 뒤에 도착하여 42밀리초를 기다린후 실행 된다. 평균 대기 시간은 (0+27+42) / 3 = 23밀리초 이다.
FCFS 스케줄링 평가
단순하고 공평하지만, 처리 시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스는 기다려 시스템의 효율이 떨어지는 문제가 발생, 이를 콘보이 효과 또는 호위 효과라 한다.
또 다른 단점은 현재 작업 중인 프로세스가 입출력 작업을 요청하면 CPU가 작업하지 않고 쉬는 시간이 많아져 효율이 떨어진다.
SJF 스케줄링
SJF 스케줄링은 준비 큐에 있는 프로세스 중 실행 시간이 짧은 작업부터 CPU를 할당하는 비선점형 방식으로 최단 작업 우선 스케줄링이라고도 한다.
프로세스 P1은 도착하자마자 실행되고, 두 프로세스 중 P3가 작업 짧기 때문에 프로세스 P3는 24밀리초를 기다린 후 실행, 프로세스 P2은 36밀리초를 기다린후 실행 된다. 평균 대기 시간은 (0+24+36) / 3 = 20밀리초 이다.
SJF 스케줄링 평가
FCFS 스케줄링보다 평균 대기 시간이 줄어 시스템의 효율성은 높아지나 다음과 같은 이유 때문에 사용하기 힘들다.
-
운영체제가 프로세스의 종료 시간을 정확히 예측하기 어렵다.
과거 일괄 작업 프로세스는 실행 중 사용자의 입력을 기다리는 상호작용을 하지 않았다. 하지만 현대의 프로세스는 빈번하게 발생하기 때문에 프로그램 종료 시간을 파악하기 어렵다. -
공평하지 못하다.
만약 P3 같은 작은 작업이 계속 준비 큐에 들어오면 프로세스 P2의 작업이 연기되어 아사현상 또는 무한 봉쇄 현상이 발생한다.HRN 스케줄링
HRN 스케줄링은 SJF 스케줄링에서 발생할 수 있는 아사 현상을 해결하기 위한 비선점형 알고리즘으로 최고 응답률 우선 스케줄링이라고도 한다. HRN 스케줄링은 서비스를 받기 위해 기다린 시간과 CPU 사용 시간을 고려한 스케줄링 방식이다.
우선순위 = (대기 시간 + CPU 사용 시간) / CPU 사용 시간이다.
프로세스 P1은 도착하자마자 실행되고, P2는 27밀리초 기다려 우선순위가 (27+18)/18=2.5이고, P3은 24밀리초 동안 기다려 (24+9)/9=3.67이다. 따라서 P3가 실행된 후 P2가 실행된다. 평균 대기 시간은 (0+24+36) / 3 = 20밀리초 이다.
HRN 스케줄링 평가
우선순위를 높게 설정하면서 대기 시간을 고려하여 아사 현상을 완화했다. 그러나 여전히 공평성이 위배되어 많이 사용되지 않는다.
라운드 로빈 스케줄링
한 프로세스가 할당받은 시간 동안 작업하다 완료하지 못하면 준비 큐의 뒤로 가서 자기 차례를 기다리는 방식이다. 선점형 알고리즘의 가장 단순하고, 대표적인 방식이다.
타임 슬라이스가 10밀리초인 시스템이다. 프로세스 P1은 도착하자 실행되므로 대기 시간이 0밀리초이다. P2는 3밀리초 후에 도착하여 7밀리초를 기다렸다 10밀리초 실행된다. P3는 6밀리초 후에 도착하여 14밀리초를 기다렸다 9밀리초 실행된다. P1은 19밀리초 후에 작업을 다시 시작한다. 10밀리초 동안 실행된 후 큐 맨 뒤로 가고, P2가 8밀리초 실행되어 작업을 마치며 마지막으로 P1이 10밀리초 동안 실행되어 작업을 마친다. 총 대기 시간은 (0+7+14+19+19+8) / 3 = 22.33밀리초 이다.
타임 슬라이스의 크기와 문맥 교환
FCFS 스케줄링과 라운드 로빈 스케줄링을 비교해보면 23밀리초, 22.33밀리초로 미세하게 라운드 로빈 스케줄링이 앞선다. 이때 P1, P2의 도착 시간을 바꾸면 FCFS 스케줄링의 총 대기 시간은 15+42 = 57밀리초, 타임 슬라이스가 10밀리초인 라운드 로빈 스케줄링 방식도 57밀리초로 똑같다.
이처럼 라운드 로빈 스케줄링과 FCFS 스케줄링의 평균 대기 시간이 같다면 라운드 로빈 스케줄링이 더 비효율적인 알고리즘이다. 라운드 로빈 스케줄링은 문맥 교환 시간이 추가되기 때문이다. 문맥 교환 시간을 고려하여 산출하면 앞의 계산보다 크게 나온다.
-
타임 슬라이스가 큰 경우
타임 슬라이스가 너무 크면 하나의 작업이 끝난 뒤 다음 작업을 시작하므로 FCFS 스케줄링과 다를 게 없다. -
타임 슬라이스가 작은 경우
타임 슬라이스를 너무 작게 설정하면 시스템 전반적으로 성능이 떨어진다. 너무 자주 문맥 교환 때문에 작업 시간 큰 문맥 교환 시간으로 시간을 낭비하기 때문이다.
결론적으로 타임 슬라이스는 문맥 교환 시간을 고려하여 적당한 크기로 하는 것이 중요하다.
SRT 우선 스케줄링
SJF 스케줄링과 라운드 로빈 스케줄링을 혼합한 방식으로 최소 잔류 시간 우선 스케줄링이라고도 한다. 기본적으로 라운드 로빈 스케줄링을 사용하지만 CPU를 할당받을 프로셋 선택은 남은 작업 시간이 가장 적은 프로세스를 선택한다.
프로세스 P1은 도착하자마자 실행되고, P3의 작업 시간이 짧기 때문에 P3이 먼저 9밀리초 실행된다. 그리고 P1, P2의 남은 작업 시간을 비교하여 작업 시간이 짧은 P2를 연달아 2번 실행 후 P1의 남은 작업을 마친다.
총 대기 시간은 (0 + 4 + 16 + 27) / 3 = 15.66밀리초 이다.
SRT 스케줄링의 평가
SRT 스케줄링은 좋은 알고리즘이 아니다. 실행 중인 프로세스와 큐에 있는 프로세스의 남은 시간을 주기적으로 계산, 남은 시간이 더 적은 프로세스와 문맥 교환 해야 하므로 작업이 추가도니다. 또한 운영체제가 프로세스의 종료 시간을 예측하기 어렵고 아사 현상이 일어나기 때문에 잘 사용하지 않는다.
우선순위 스케줄링
프로세스의 중요도에 따라 우선순위를 반영한 스케줄링 알고리즘이다. 예를 들어 작업 시간이 짧은 프로세스의 우선순위를 높게 설정했다고 하자.
P1은 대기하지 않고 바로 실행, P2, P3 중 P3의 우선순위가 높기 때문에 먼저 실행되고 , P3의 작업이 이어서 실행된다. 총 대기 시간과 평균 대기 시간은 SJF 스케줄링과 같다.
우선순위는 비선점형 방식과 선점형 방식 모두 적용할 수 있다.
-
(비선점형 방식) SJF 스케줄링: 작업 시간이 짧은 프로세스에 높은 우선순위 부여
-
(비선점형 방식) HRN 스케줄링: 작업 시간이 짧거나 대기 시간이 긴 프로세스에 우선순위 부여
-
(선점형 방식) SRT 스케줄링: 남은 시간이 짧은 프로세스에 우선순위 부여
우선순위 스케줄링은 선점형 혹은 비선점형 방식으로 구현이 가능하다. -
고정 우선순위 알고리즘: 한 번 우선순위를 부여하면 종료될 때까지 고정된다. 단순하게 구현할 수 있지만 시시가가 변하는 시스템의 상황을 반영 못해 효율성이 떨어진다.
-
변동 우선순위 알고리즘: 일정 시간마다 우선순위가 변한다. 일정 시간마다 우선순위를 계산하고 반영하기에 시스템이 복잡하지만 상황을 반영하여 효율적인 운영이 가능하다.
우선순위 스케줄링의 평가
우선순위 스케줄링은 우선순위가 높은 프로세스에 먼저 CPU를 할당하므로 공평성을 위배하고 아사 현상을 일으킨다는 것이 문제이다. 또한 준비 큐의 순서를 무시하고 프로세스의 우선순위를 매번 바꿔야 하기 때문에 오버헤드가 발생하여 시스템의 효율성이 떨어진다.
만약 커널 프로세스와 일반 프로세스가 같은 우선순위라 할때 커널 프로세스가 제 역할을 못할 수 있다. 따라서 우선순위는 시스템의 효율성보다 프로세스의 중요도에 따라 정해지는 것이다.
다단계 큐 스케줄링
다단계 큐 스케줄링은 우선순위에 따라 준비 큐를 여러 개 사용하는 방식이다.
라운드 로빈 방식으로 운영되는 큐는 우선순위에 따라 다단계로 큐에 삽입되는 것만으로 우선순위가 결정된다. 우선순위는 고정형 우선순위를 사용하며, 상단 큐에 있는 모든 프로세스의 작업이 끝나야 다음 큐의 작업이 시작된다.
우선순위가 높은 프로세스가 우선순위가 낮은 프로세스보다 먼저 작동할 뿐 아니라 우선순위에 따라 타임 슬라이스를 조절하여 작업 효율을 높일 수 있다. 예를 들면 전면 프로세스는 타임 슬라이스를 작게하고, 후면 프로세스는 사용자와의 상호작용이 없으므로 FCFS 방식으로 처리한다. 우선순위가 높은 큐의 작업이 다 끝날 때까지 우선순위가 낮은 프로세스의 작업이 연기된다. 문제 해결을 하기 위해 제안된 것이 다단계 피드백 큐 스케줄링이다.
다단계 피드백 큐 스케줄링
다단계 피드백 큐 스케줄링은 우선순위가 낮은 프로세스에 불리한 다단계 큐 스케줄링의 문제점을 보완한 방식이다.
다단계 피드백 큐 스케줄링은 CPU를 사용하고 난 프로세스의 우선순위가 낮아진다. CPU를 사용하고 난 프로세스는 우선순위가 하나 낮은 큐의 끝으로 들어간다. 우선순위를 낮춤으로써 다단계 큐에서 우선순위가 낮은 프로세스의 실행 연기되는 문제를 완화한다. 물론 커널 프로세스가 일반 프로세스의 큐에 삽입되지는 않는다.
또 다른 특징은 우선순위에 따라 타임 슬라이스의 크기가 다르다. 우선순위가 낮을수록 타임 슬라이스가 커진다. 우선순위가 낮은 프로세스가 어렵게 얻은 CPU를 좀 더 오랫동안 사용할 수 있도록 타임 슬라이스를 크게 설정한다. 결국 마지막 큐에 있는 프로세스는 무한대의 타임 슬라이스를 얻는다. 그러므로 다단계 피드백 큐 스케줄링에서 마지막 큐는 들어온 순서대로 작업을 마치는 FCFS 스케줄링 방식으로 동작한다.
