스케쥴링 개요
워크로드에 대한 가정
스케쥴링에 대해 알아보기 전에, 프로세스가 실행되는 과정인 워크로드(workload)에 대한 몇가지 가정을 소개하겠다. 그리고 상황을 이상적으로 만드는 이러한 가정을 하나씩 완화시켜가며 현실적인 스케쥴링을 하나씩 알아보겠다.
2. 스케쥴링 평가 기준1 : 반환 시간(turnaround time)
스케쥴링 정책을 평가하기 위해서는 기준이 필요하다. 먼저 반환시간 이라는 평가기준을 이용하겠다. 작업이 완료된 시간에서 작업이 시스템에 도착한 시각을 뺀 시간으로 정의된다. 반환시간은 성능 측면에서 평가하는 기준이다. (성능 이외에 공정성을 평가할 수도 있다. 이는 성능과 서로 상충된다.)
2.1 FIFO (First In First Out) : 선입선출
말그대로 먼저 시스템에 도착한 프로세스를 먼저 실행시키는 것이다. 지금까지의 워크로드 가정에 의하면 매우 잘 동작한다.
1번 가정을 완화시킬 경우 문제점 발생 모든 작업의 실행시간이 같지 않다면?
Convoy effect (짧은 시간동안 자원을 사용할 프로세스가 오랫동안 자원을 사용하는 프로세스의 종료를 기다리는 현상) 발생
2.2 SJF(Shortest Job First) : 최단 작업 우선
위 문제를 해결하기 위해서 최단 작업 우선 스케쥴링을 이용한다. 내용은 간단하다. 자원 사용 시간이 가장 짧은 프로세스부터 실행시켜, Convoy effect를 해소하는 것이다. 지금까지의 가정 조건에서 최적이다.
2번 가정을 완화시킬 경우 문제점 발생 모든 작업이 동시에 도착하지 않는다면?
자원 사용시간이 짧은 프로세스가 조금 늦게 도착하여, 자원 사용이 긴 프로세스에게 이미 자리를 뺏겨버린 경우다. 이 역시 Convoy effect가 발생한다.
이를 해결하기 위해서는 가정 3번을 완화시켜야 한다. 따라서 앞으로는 선점형(preemptive) 스케줄러가 등장한다.
3번 가정 완화 : 작업은 끝날때까지 계속 실행되지 않을 수도 있다.
2.3 STCF(Shortest Time-to-Completion First) : 최소 잔여시간 우선
언제든 새로운 작업이 시스템에 들어오면, 진행중이던 작업과 새로운 작업의 잔여시간을 계산하고 그 중 가장 적은 작여시간을 가진 작업을 스케줄한다. 이 또한 지금까지의 가정과 평가기준에서 optimal이다. 하지만 현실적인 가정으로 완화시켜감에 따라 평가 기준도 변경되어야 한다.
3. 스케쥴링 평가 기준2 : 응답 시간 (response time)
반환시간도 스케쥴을 평가하기 위한 중요한 기준이었지만, 사람들이 대화형 인터페이스를 중요하게 여기게 됨에 따라 응답 시간이라는 평가 기준도 중요 기준이 되었다. 응답 시간의 정의는 _작업이 도착한 후 처음 스케줄 될 때까지의 시간_이다.
응답 시간을 기준으로 하면, STCF는 좋은 스케줄러라고 할 수 없다. 작업시간이 비슷한 3개의 스케줄러가 동시에 도착하면 세번째 스케줄러는 2개의 스케줄러가 다 끝날때까지 기다려야 하기 때문이다.
3.1 RR (Round Robin) : 라운드 로빈
응답 시간이라는 기준을 만족시키기 위한 스케줄러이다. 작업 하나가 모두 끝날때까지 기다리는 것이 아니라, 일정 시간 동안 실행한 후 실행 큐의 다음 작업으로 전환한다. 이때 일정 시간 을 타임 슬라이스 혹은 스케줄링 퀀텀 이라고 부른다. 이때 타임 슬라이스는 타이머 인터럽트 주기의 배수여야 한다.
이 타임 슬라이스가 짧다면, 응답 시간 기준으로 성능이 좋아진다. 하지만 너무 짧게하면 문맥 교환 비용이 전체 성능에 큰 영향을 미치게 되어 좋은 스케줄러가 될 수 없다.
또한 라운드 로빈은 반환 시간을 평가기준으로 할 경우 매우 좋지 않은 스케줄러가 된다. 위에 언급했드시 성능과 공정성은 서로 상충되는 평가 기준이기 때문이다.
Last updated