운영체제가 잡들을 스케줄링한다는 것은, cpu를 할당해줌으로써 해당 잡이 실행되게 한다는 뜻이기 때문에, 여러 잡들을 하나의 cpu 가지고 문제 없이 실행시키기 위해서 운영체제는 주도면밀하게 스케줄링할 필요가 있다.

여기서 어떻게 해야 더 잘 스케줄링 되었는지를 평가하는 기준들에는 여러가지가 있는데, 그 중 성능 측면에서 turnaround time(반환 시간)이라는 값이 있다.

이는 해당 잡의 처리가 종료된 시점과 잡이 요청된 시점의 차이로, 예를 들어 10초에 요청된 뒤 15초에 처리가 완료될 경우 반환시간은 5초인 것이다.

이외에도 response time(응답 시간)은, 잡이 요청된 뒤 처음 cpu를 할당 받아서 사용한 시점까지 걸린 시간이다.

10초에 요청된 뒤 12초에 실행되어서 16초에 종료된 경우, 응답시간은 2초이며 반환시간은 6초이다.

여러가지 잡들이 있을 때, 해당 잡들이 cpu를 사용하는 시간이 동일하며, 모두 동시에 도착했으며, 한번 시작하면 해당 프로세스가 종료될 때 까지 cpu를 사용하는 non-preemtive 한 상황이라고 하자.

또한 현실적으로 말은 안되지만, 잡이 완료되기까지 걸리는 소요 시간을 알고 있다고 가정한 뒤 여러가지 스케줄링 방법들에 대해 비교해보자.

FIFO

First In First Out 으로, 먼저 들어온 잡들에 대해 먼저 처리해준다는 아주 널리 알려져 있는 방식이다.

3개의 잡 A,B,C가 0초에 도착했고, 셋 다 모두 완료되기까지 10초가 걸리는 잡들이라고 할 경우, 동시에 들어왔기 때문에 그냥 순서대로 실행 시 반환시간의 평균값은 20초가 된다.

A는 0초에서 10초까지, B는 10초에서 20초까지, C는 20초에서 30초까지 cpu를 사용해서 처리했는데, 모두 0초에 요청되었기 때문이다.

그러나 만약 소요시간이 동일하지 않을 경우, 예를 들어 A의 소요시간이 100초가 된다면 평균적인 반환시간은 굉장히 커지게 된다.

순서대로 스케줄링하며, non-preemtive하기 때문에 중간에 끊을수도 없으므로 먼저 들어온 A가 종료될때까지 실행하며, B와 C 같은 경우는 cpu를 10초만 사용하면 되는데도 불구하고 A를 기다려야하기 때문이다.

이 경우 A의 반환시간은 100초, B는 110초, C는 120초가 되어 굉장히 비효율적임을 확인할 수 있다.

마치 편의점 계산대에서 바로 앞사람이 너무 물건을 많이 사서 바코드 찍는데만 1시간이 걸리면, 나는 껌 하나를 사기 위해 그만큼을 기다려야하는 상황과 비슷하다.

이러한 문제를 해결하기 위해 다른 스케줄링 정책을 생각해볼 수 있다.

SJF / STCF

SJF는 Shortest Job First 의 약어로, 잡의 총 소요시간이 짧은 잡을 먼저 스케줄링하는 것이다.

비현실적이긴해도 각 잡들의 소요시간을 알고 있는 상태라고 가정하고 있기 때문에 가능한 방식인데, 이는 반환시간이라는 메트릭 기준으로는 가장 효율적인 방식이다.

앞서 A가 100초 걸리는 상황에서, SJF 방식을 택할 경우에는 B와 C를 먼저 처리한 뒤 A를 처리하기 때문에 반환시간의 평균값은 (10+20+120)/3 = 50초로 굉장히 줄어들게 된다.

그러나 동시에 도착하지 않는 상황이 된다면 또다시 문제가 발생한다.

100초짜리 잡 A가 0초에 혼자 도착했고, 다른 잡이 없기 때문에 cpu는 100초가 A를 위해 일을 하는데, 10초에 B와 C가 도착하는 것이다.

B와 C는 둘 다 10초밖에 걸리지 않기 때문에 이들을 먼저 처리하는 것이 효율적이지만, 이미 실행중이던 A를 중간에 끊을 수 없기 때문에(non-preemtive) 100초를 대기해야하며, 이로 인해 반환시간이 다시 늘어나게 된다.

이런 문제를 해결하기 위해, SJF 방식에서 preemtive하게 개선된 정책이 STCF이다.

STCF는 Shortes Time to Completion First의 약어로, 스케줄러가 현재 상황을 딱 보고 현시점에서 가장 일찍 끝날 것 같은 잡을 먼저 스케줄링하는 방식이다.

다른 말로 PSJF라고도 부르는데, 이는 preemtive한 SJF라는 뜻이다.

어떤 잡을 처리하고 있다가도, 새로운 잡이 들어올 경우 남은 시간을 확인한 뒤 종료시간이 더 짧으면 문맥교환을 발생시켜 프로세스를 스위칭한다.

앞선 예시에서 0초부터 10초까지는 A를 처리하다가, B와 C가 새로 들어온 경우 A의 남은 시간은 90초이기 때문에, A 대신 B에게 할당해주고, B가 처리된 뒤에도 역시 C는 10초, A는 90초가 남았기 때문에 C에게 할당해주는 것이다.

이렇게 잡의 종료 시간을 기준으로 스케줄링하는 정책들은 반환 시간 면에서는 옵티멀하지만, 응답 시간 측면에서는 엉망진창이다.

심한 경우에 어떤 프로세스는 자기보다 짧은 잡들이 계속 들어옴으로써 영원히 실행되지 않을 수도 있는데(starvation), 이를 위해 라운드로빈 방식을 생각해볼 수 있다.

Round Robin

라운드로빈은 각 잡들을 일정 주기로 잘게잘게 쪼갠 뒤(preemtive), 쪼개진 잡들을 순서대로 나눠가면서 실행하는 방식이며, 타이머를 통해 주기적으로 인터럽트 걸어서 스위치 시키는 것이다.

예를 들어 잡 A를 a1,a2,a3로 나누고, B와 C 역시 각각 3개씩 나눈 뒤, a1-b1-c1-a2-b2-c2-a3-b3-c3 순서대로 cpu를 할당해준다고 보면 된다.

이 경우에는 응답 시간이 굉장히 개선되는데, 당연히 각 잡들을 쪼개서 적더라도 실행은 시켰으니 응답 시간이 그만큼 줄어드는 것이다.

물론 이 때 타이머의 간격(쪼개는 크기)을 작게 만들면 만들수록 그만큼 응답시간은 더 빨라지지만, 잡들이 변경되는(컨텍스트 스위치) 과정에서 발생하는 오버헤드 역시 그만큼 많아지기 때문에 무조건적으로 유리한 것이 아니다.

이 오버헤드에는 단순히 트랩에 대한 처리나 cpu의 상태를 보존/복원하는 것 뿐만이 아니라 메모리에 캐싱/페이징 되어있던 현재 프로세스의 값들 역시 사용하지 못하게 됨으로써 발생하는 비용도 포함되기 때문에 부담이 크다고 볼 수 있다.

아무튼 그렇기 때문에 라운드로빈 방식은 starvation이 발생할 수 있는 SJF 등과는 다르게 공정한 방식이다.

그러나 반환 시간 측면에서는 유리하지 않기 때문에, 이를 고려하여 필요에 맞게 유리한 방식을 선택해야 한다.