[ 쉽게 배우는 운영체제 ] 4-4. 스케줄링 알고리즘

스케줄링 알고리즘의 종류

비선점형 알고리즘 non-preemptive algorism	프로세스가 CPU를 할당받으면 작업이 끝날 때까지 CPU를 놓지 않기때문에 효율이 떨어진다. 대표적으로 FCFS 스케줄링, SJF 스케줄링, HRN 스케줄링이 있다.
선점형 알고리즘 preemptive algorism	시분할 시스템을 고려하여 만들어진 알고리즘으로, 어떤 프로세스가 CPU를 할당받아 실행중이라도 운영체제가 CPU를 강제로 빼았을수 있다. 대표적으로 라운드 로빈 스케줄링, SRT 스케줄링, 다단계 큐 스케줄링, 다단계 피드백 큐 스케줄링이 있다.
둘 다 가능	우선순위 스케줄링

---

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

• CPU 사용률 : 전체 시스템의 동작 시간 중 CPU가 사용된 시간을 측정하는 방법이다. 
• 처리량 : 처리량은 단위 시간당 작업을 마친 프로세스의 수로, 이 수치가 클수록 좋은 알고리즘이다.
• 대기 시간 : 대기 시간은 작업을 요청한 프로세스가 작업을 시작하기 전까지 대기하는 시간으로, 이 시간이 짧을수록 좋다.
• 응답 시간 : 대화형 시스템에서는 사용자의 요구에 따라 얼마 만에 반응하는지가 중요한데, 응답 시간은 프로세스 시작 후 첫 번째 출력 또는 반응이 나올 때까지 걸리는 시간이다. 대기시간과 마찬가지로 이 시간이 짧을수록 좋다.
• 반환 시간 : 프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반환하는데 까지 걸리는 시간이다. 

CPU 알고리즘의 효율성을 평가할 때 주로 대기시간, 응답 시간, 반환시간을 계산하여 평가한다.

 

* 대기시간, 응답시간, 실행시간, 반환시간의 관계

• 대기시간 : 프로세스가 생성된 후 실행되기 전까지 대기하는 시간
• 응답시간 : 첫 작업을 시작한 후 첫 번째 출력(반응)이 나오기까지의 시간
• 실행시간 : 프로세스 작업이 시작된 후 종료되기까지의 시간
• 반환시간 : 대기 시간을 포함하여 실행이 종료될 때까지의 시간

스케줄링 알고리즘의 성능을 비교할 때는 주로 평균 대기 시간을 본다. 평균 대기 시간은 모든 프로세스의 대기시간을 합한 뒤 프로세스의 수로 나눈 값이다.

---

FCFS 스케줄링

FCFS 스케줄링의 동작 방식

FCFS(First Come First Served) 스케줄링은 준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 방식으로, 선입선출 스케줄링이라고도 한다.

초기의 일괄 작업 시스템에서 사용되었던 FCFS 스케줄링은 프로세스가 큐에 도착한 순서대로 실행되며, 비선점형 방식이기 때문에 한 번 실행되면 그 프로세스가 끝나야만 다음 프로세스를 실행할 수 있고, 큐가 하나이기 때문에 모든 프로세스는 우선순위가 동일하다. 

FIFO(First In First Out)라고도 하는데, 일반적으로 FIFO는 큐를 가리키는 말이기 때문에 이와 구분하기 위해 스케줄링 알고리즘에서는 FCFS라고 부른다. FIFO와 대응되는 FILO(First In Last Out)는 스택을 가리킨다.

 

FCFS 스케줄링의 성능

평균 대기 시간으로 평가한다.

 

* 평균 대기 시간

작업이 시작할 때까지 전체 프로세스가 대기한 시간의 평균값으로, 시스템의 모든 프로세스가 작업을 요청하여 실제로 작업이 시작할 때까지 기다린 시간을 합한 후 프로세스의 수로 나누어 구한다.

FCFS 스케줄링의 성능 평가

프로세스 P1은 도착하자마자 실행되므로 대기시간이 0밀리초, 작업시간이 30초이다.
프로세스 P2는 3밀리초 뒤에 도착하여 대기시간은 27밀리초(30-3)이며, 18밀리초 동안 실행된다.
프로세스 P3는 6밀리초 뒤에 도착하여 대기시간은 42밀리초(48-6)이며, 9밀리초 동안 실행된다.

3개 프로세스의 평균 대기시간은 (0 + 27 + 42) / 3 = 23밀리초이다.

 

FCFS 스케줄링의 평가

FCFS 스케줄링 알고리즘은 단순하고 공평하지만, 처리 기간이 긴 프로세스가 CPU를 차지하면 다른 프로세스는 하염없이 기다리게 돼 시스템의 효율성이 떨어지는 문제가 발생한다. 이를 콘보이 효과(convoy effect) 또는 호위 효과라고 한다.

 

FCFS 스케줄링의 또 다른 단점은 현재 작업 중인 프로세스가 입출력 작업을 요청하는 경우 CPU가 작업하지 않고 쉬는 시간이 많아져 작업 효율이 떨어진다는 것이다.

---

SJF 스케줄링

SJF 스케줄링의 동작 방식

SJF(Shortest Job First) 스케줄링은 준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식으로, 최단 작업 우선 스케줄링이라고도 한다.

SJF 스케줄링은 프로세스에 CPU를 배정할 때 시간이 오래 걸리는 작업이 앞에 있고 간단한 작업이 뒤에 있으면 그 순서를 바꾸어 실행한다. FCFS 스케줄링의 콘보이 효과를 완화해 시스템의 효율성을 높인다. 

 

SJF 스케줄링은 SPF(Shortest Process First) 또는 최단 프로세스 우선 스케줄링이라고도 한다. 

SJF 스케줄링의 성능

SJF 스케줄링

시작 시점에는 프로세스 P1 뿐이므로 P1은 대기하지 않고 바로 실행된다. P1이 30밀리초 동안 작업을 하면 큐에 프로세스 P2와 P3이 기다리고 있다.
두 프로세스 중 P3의 작업이 짧기 때문에 P3가 먼저 실행된다. 따라서 P3이 24밀리초(30-6)를 기다린 후 9밀리초 동안 실행된다.
마지막으로 P2가 36밀리초(39-3)를 기다린 후 18밀리초 동안 실행된다.

3개 프로세스의 평균 대기시간은 (0+24+36) / 3 = 20밀리초이다.

 

SJF 스케줄링의 평가

작은 작업을 먼저 실행하기 때문에 평균 대기시간이 줄어들어 시스템의 효율성이 좋아지지만 다음과 같은 이유로 사용하기 어렵다.

• 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어렵다.

과거의 일괄 작업 프로세스는 실행되는 중에 사용자의 입력을 기다리는 것과 같은 상호작용을 하지 않아 종료 시간을 추정할 수 있었으나, 현대의 프로세스는 사용자와의 상호작용이 빈번하게 발생하기 때문에 프로그램 종료 시간을 파악하기 어렵다.

• 공평하지 못하다.

실행시간이 짧은 작업이 계속 준비 큐에 들어오면 그보다 실행시간이 긴 작업의 경우 계속 연기된다. 이를 아사 starvation 현상 또는 무한 봉쇄 infinite blocking 현상이라고 한다.

 

위의 두 문제의 해결방법은 다음과 같다.

• 첫 번째 문제는 프로세스가 자신의 작업 시간을 운영체제에 알려주어 해결할 수 있다. 하지만 프로세스가 자신의 작업 시간을 정확히 알기 어려울 뿐만 아니라, 일부 악의적인 프로세스가 작업 시간을 속인다면 시스템의 효율성이 나빠질 것이다.
• 두 번째 문제는 에이징 aging으로 완화할 수 있다. 에이징은 프로세스가 양보할 수 있는 상한선을 정하는 방식이다. 하지만 에이징 값을 어떤 기준으로 정할 것인지가 문제라 에이징에도 한계가 있다.

결론적으로 SJF 스케줄링은 프로세스의 종료 시간을 파악하기 어렵고 아사 현상이 일어나기 때문에 잘 사용하지 않는다.

---

HRN 스케줄링

HRN 스케줄링의 동작 방식

HRN(Highest Response Ration Next) 스케줄링은 SJF 스케줄링에서 발생할 수 있는 아사 현상을 해결하기 위해 만들어진 비선점형 알고리즘으로, 최고 응답률 우선 스케줄링이라고 한다.

HRN 스케줄링은 서비스를 받기 위해 기다린 시간과 CPU 사용시간을 고려하여 스케줄링을 하는 방식으로 HRN 스케줄링에서 프로세스의 우선순위를 결정하는 기준은 다음과 같다.

 

HRN 스케줄링은 우선순위를 정할 때 대기시간을 고려함으로써 아사 현상을 완화한다. 즉, 스케줄링 방식에 에이징을 구현한 셈으로 숫자가 클수록 우선순위가 높다.

HRN 스케줄링

프로세스 P1이 30초 동안 제일 먼저 실행되며,  준비 큐에 있는 프로세스 P2와 P3의 우선순위를 계산한다.
P2는 27밀리초 동안 기다렸으므로 우선순위가 (27 + 18) / 18 = 2.5이고, P3은 24밀리초 동안 기다렸으므로 우선순위가 (24 + 9) / 9 = 3.67이다.
HRN 스케줄링에서는 숫자가 클수록 우선순위가 높기 때문에 P3가 먼저 실행된 후 P2가 실행된다. 

평균 대기시간은 (0+24+36) / 3 = 20밀리초이다.

 

HRN 스케줄링의 평가

HRN 스케줄링은 실행 시간이 짧은 프로세스의 우선순위를 높게 설정하면서도 대기 시간이 긴 프로세스의 우선순위를 높임으로써 아사 현상을 완화한다. 그러나 여전히 공평성이 위배되어 많이 사용되지 않는다.

---

라운드 로빈 스케줄링

라운드 로빈 스케줄링의 동작 방식

라운드 로빈(Round Robin; RR) 방식은 순서 순환 방식이라고도 하며 한 프로세스가 할당받은 시간(타임슬라이스) 동안 작업을 하다가 작업을 완료하지 못하며 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식이다.

우선순위가 적용되지 않은 선점형 알고리즘 중 가장 단순하고 대표적인 방식으로, 프로세스들이 작업을 완료할 때까지 계속 순환하면서 실행된다.

 

FCFS 스케줄링과 유사한데 라운드 로반 방식은 각 프로세스마다 CPU를 사용할 수 있는 최대 시간, 즉 타임슬라이스가 있다는 것이 FCFS 스케줄링과의 차이점이다.

프로세스는 자신에게 주어진 타임슬라이스 동안만 작업할 수 있으며, 작업이 다 끝나지 않으면 큐의 뒤쪽 tail에 다시 삽입된다.

 

라운드 로빈 스케줄링의 성능

라운드 로빈 스케줄링

프로세스 P1은 도착하자마자 실행되므로 P1의 대기시간은 0밀리초이다. P1은 자신에게 주어진 작업 시간인 10밀리초 동안 실행된 후 큐의 맨 뒤로 이동한다.
프로세스 P2는 3밀리초 후에 도착하여 7밀리초를 기다리고 10밀리초 동안 실행된 후 큐의 맨 뒤로 이동한다.
프로세스 P3은 6밀리초 후에 도착하여 14밀리초를 기다렸다가 9초 동안 실행되어 작업을 마친다.

프로세스P1은 29밀리초 후에 작업을 다시 시작한다. 앞에서 10밀리초 동안 실행되었기때문에 실제 대기시간은 19밀리초이다.
프로세스 P1이 10밀리초동안 실행된 후 큐의 맨 뒤로 이동하면 P2가 8밀리초 동안 실행되어 남은 작업을 마치며, 마지막으로 P1이 10밀리초동안 실행되어 작업을 마친다.

이 세 프로세스의 총 대기시간은 (0+7+14+19+19+8) = 67밀리초이고, 평균대기사간은 67 / 3 = 22.33밀리초이다.

 

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

라운드 로빈과 FCFS 스케줄링의 평균 대기시간이 같다면 라운드 로빈 스케줄링이 더 비효울적인 알고리즘이다.

라운드 로빈 스케줄링 같은 선점형 방식에서는 문맥 교환시간이 추가되기 때문이다. 

 

라운드 로빈 스케줄링이 효과적으로 작동하려면 문맥 교환에 따른 추가 시간을 고려하여 타임슬라이스를 적절히 설정해야 한다. 타임 슬라이스의 크기는 프로세스의 반응 시간에 영향을 미칠 뿐만 아니라 시스템 전체의 성능에도 영향을 미친다.

 

• 타임 슬라이스가 큰 경우

타임 슬라이스가 너무 크면 하나의 작업이 끝난뒤 다음 작업이 시작되는것처럼 보이다. 이 경우 FCFS 스케줄링과 다를게 없는데, 실제로 라운드로빈 스케줄링에서 타임슬라이스가 무한대이면 FCFS 스케줄링이 된다.

• 타임 슬라이스가 작은 경우

타임 슬라이스를 너무 작게 설정하면 문맥교환이 너무 자주 일어나 문맥교환에 걸리는 시간이 실제 작업 시간보다 상대적으로 커지고 많은 시간을 낭비하여 실제 작업을 못하는 문제가 발생한다. 

 

결론적으로 타임 슬라이스는 되도록 작게 설정하되 문맥 교환에 걸리는 시간을 고려하여 적당한 크기로 하는것이 중요하다.

---

SRT 우선 스케줄링

SRT 스케줄링의 동작 방식

STR(Shortest Remaining Time) 스케줄링은 SJF스케줄링과 라운드 로빈 스케줄링을 혼합한 방식으로, 최소 잔류 시간 우선 스케줄링이라고도 한다.  (SJF스케줄링의 선점형 버전)

기본적으로 라운드 로빈 스케줄링을 사용하지만, 남은 작업시간이 가장 적은 프로세스를 선택한다.

 

SRT 스케줄링의 방식

SRT 스케줄링

프로세스 P1은 도착하자마자 실행되므로 대기 시간이 0밀리초이며, P1은 자신에게 주어지 작업시간인 10밀리초동안 실행 된 후 큐의 맨 뒤로 이동한다.
프로세스 P2는 3밀리초 후에 도착하고, P3은 6밀리초 후에 도착하지만 P3의 작업시간이 짧기때문에 P3이 먼저 실행되어 9밀리초 후에 작업을 마친다.
그리고 프로세스 P1의 남은 작업 시간과 P2의 작업 시간 중 P2의 작업시간이 짧기때문에 P2가 연달아 두번 실행되며, 그 후에 P1이 남은 작업을 마친다.

이 세 프로세스의 총 대기시간은 0 + 4 + 16 + 27  = 47 밀리초이고, 평균 대기시간은 47 / 3 = 15.66 밀리초이다.

 

SRT 스케줄링의 평가

현재 실행 중인 프로세스와 큐에 있는 프로세스의 남은 시간을 주기적으로 계산하고, 남은 시간이 더 적은 프로세스와 문맥교환을 해야 하므로 SJF 스케줄링에는 없는 작업이 추가된다. 또한, SJF 스케줄링과 마찬가지로 운영체제가 프로세스의 종료 시간을 예측하기 어렵고 아사 현상이 일어나기 때문에 잘 사용하지 않는다. 

---

우선순위 스케줄링

우선순위 스케줄링의 동작 방식

프로세스는 중요도에 따라 우선순위priority를 갖는데 이러한 우선순위를 반영한 스케줄링 알고리즘이 우선순위 스케줄링이다. 우선순위 스케줄링은 어떤 기준으로 우선순위를 정하느냐에따라 다양하게 구현할 수 있다. 

우선순위 스케줄링

우선순위를 다음과 같이 설정했을때, 시작 지점에는 프로세스 P1뿐이므로 P1은 대기하지 않고 바로 실행된다. P1이 작업을 마치면 준비큐에서 기다리고 있는 P2와 P3중 P3의 우선순위가 P2보다 높기때문에 P3이 먼저 실행되고 이어서 P2가 실행된다. 

이 경우 대기 시간과 평균 대기시간은 SJF 스케줄링과 같다.
( 대기시간 = 0 + 24 + 36 = 60 | 평균 대기시간 = 60 / 3 = 20 )

우선순위는 비선점형 방식과 선점형 방식 모두에 적용할 수 있다.

• (비선점형 방식) SJF 스케줄링 :  작업시간이 짧은 프로세스에 우선순위를 부여한다. 
• (비선점형 방식) HRN 스케줄링 : 작업시간이 짧거나 대기 시간이 긴 프로세스에 높은 우선순위를 부여한다.
• (선점형 방식) SRT 스케줄링 : 남은 시간이 짧은 프로세스에 우선 순위를 부여한다. 

우선순위 알고리즘은 고정 우선순위 알고리즘과 변동 우선순위 알고리즘으로 나뉜다. 

• 고정 우선순위 알고리즘 : 한번 우선순위를 부여받으면 종료될때 까지 우선순위가 고정된다. 단순하게 구현할 수 있지만 시시각각 변하는 시스템의 상황을 반영하지 못해 효율성이 떨어진다.
• 변동 우선순위 알고리즘 : 일정 시간마다 우선순위가 변한다. 일정시간마다 우선순위를 새로 계산하고 이를 반영하기때문에 시스템이 복잡하지만 시스템의 상황을 반영한 효율적인 운영이 가능하다.

우선순위 스케줄링의 평가

준비큐에 있는 프로세스의 순서를 무시하고 우선순위가 높은 프로세스에 먼저 CPU를 할당하므로 공평성을 위배하고 아사현상을 일으킨다는것이 문제이다.

또한, 준비 큐에 있는 프로세스의 순서를 무시하고 우선순위를 계속해서 바꿔야 하기때문에 오버헤드가 발생하여 시스템의 효율성을 떨어트린다.

하지만 효율성을 기준으로 결정한다면 중요한 프로세스가 제 역할을 못할수 있기때문에 우선순위는 프로세스의 중요도에따라 정해진다.

---

다단계 큐 스케줄링

다단계 큐(multilevel queue) 스케줄링은 우선순위에 따라 준비 큐를 여러개 사용하는 방식이다.

우선순위는 고정형 우선순위를 사용하며, 상단의 큐에 있는 모든 프로세스의 작업이 끝나야 다음 우선순위 큐의 작업이 시작된다.

 

다단계 큐 스케줄링은 우선순위에 따라 다양한 스케줄링이 가능한 선점형 방식으로, 프로세스의 우선순위와 작업 형태를 고려하여 스케줄링을 할 수 있다.

 

다단계 큐 스케줄링은 우선순위가 높은 상위 큐 프로세스의 작업이 끝나기 전에는 하위 큐 프로세스의 작업을 할 수 없다. 

---

다단계 피드백 큐 스케줄링

다단계 피드백 큐(multilevel feedback queue) 스케줄링은 우선순위가 낮은 프로세스에 불리한 다단계 큐 스케줄링의 문제점을 보완한 방식으로, 다단계 큐 스케줄링과 기본적인 형태가 같아 우선순위를 가진 여러개의 큐를 사용하지만 CPU를 사용하고 난 프로세스의 우선순위가 낮아진다. CPU를 사용하고 난 프로세스는 원래의 큐로 돌아가지않고 우선순위가 하나 낮은 큐의 끝으로 돌아간다.

 

다단계 피드백 큐 스케줄링은 프로세스가 CPU를 한 번씩 할당 받아 실행될때마다 프로세스의 우선순위를 낮춤으로써, 다단게 큐에서 우선순위가 낮은 프로세스의 실행이 연기되는 문제를 완화한다. 프로세스의 우선순위가 낮아진다고 하더라도 커널프로세스가 일반 프로세스의 큐에 삽입되지는 않는다.

 

다단계 피드백 큐 스케줄링의 또 다른 특징은 우선순위에 따라 타임슬라이스의 크기가 다르다는것이다. 

다단계 피드백 큐 스케줄링은 우선순위가 낮은 프로세스의 실행기회를 확대하려 하지만 우선순위가 높은 프로세스보다 CPU를 얻을 확률이 낮기때문에 우선순위가 낮은 큐의 타임슬라이스를 크게 설정해 CPU를 조금 더 오랫동안 사용할수 있도록 한다. 

따라서 다단계 피드백 큐 스케줄링에서 마지막 큐는 들어온 순서대로 작업을 마치는 FCFS 스케줄링 방식으로 동작한다.

 

다단계 피드백 큐 스케줄링은 오늘날의 운영체제가 CPU 스케줄링을 위해 일반적으로 사용하는 방식으로, 변동 우선순위 알고리즘의 전형적인 예이다.