This thesis presents a proportional-share CPU scheduler for multimedia applications in a general-purpose workstation environment. Our scheduler is based on the stride scheduler, which may be adequate to conventional tasks, but is insufficient for multimedia applications.
In order to support multimedia applications as well as conventional tasks, we have extended and revised the stride scheduler. New scheduling parameters are introduced to specify timing requirements of multimedia applications. Through the use of the rate regulator, the accuracy error of the revised scheduler is reduced to O(1) while that of the stride scheduler is O(N), where N is the number of runnable tasks. The concept of Adaptable-share Group and Fixed-share Group is proposed to represent both an absolute share and a relative share efficiently.
The proposed scheduler is compared and evaluated using a simulation study. We carried out some experiments in underload and overload situations. The simulation results show that the proposed scheduler achieves improved accuracy, flexibility and adaptability, so successfully accommodates both multimedia applications and conventional tasks.
일반 워크스테이션 환경에서도 멀티미디어 성격을 갖는 애플리케이션들이 점차 늘어가고 있다. 이들은 기존의 애플리케션들과는 달리 실시간(real-time) 성격을 같고 있어, 기존 일반 운용 체제에서 효과적으로 수용하는데 많은 어려움이 있다. 실시간 작업의 적시성(timeliness)을 보장해야 할 뿐 아니라, 동시에 기존 작업들 역시 이로 인해 과도하게 지체되서는 안되기 때문이다.
본 연구에서는 기존의 애플리케이션들을 위한 공정성과 유연성을 제공하는 동시에 실시간 애플리케이션들을 위한 적시성을 보장하기 위해 비례 지분(proportional-share) 방식의 스케쥴러를 제안하였다. 기존 비례 지분 방식 스케쥴러중 대표적인 stride 알고리즘을 소개하고, 이 알고리즘을 멀티미디어 애플리케이션들을 지원하기 위해 개선하였다. 우선 멀티미디어 애플리케이션들의 실시간 요구 사항을 표현할 수 있는 새로은 파라미터를 도입하였으며, 상대 지분과 절대 지분을 효율적으로 표현하고 비교하기 위해, 고정(fixed) 및 가변(adaptable) 그룹의 개념을 제안하였다. 또한 기존 stride 알고리즘이 정확도에 있어서, 작업들 개수가 N일때, O(N)의 오차를 가져 멀티미디어 애플리케이션들에 부적합한데 반해, 제안된 알고리즘에서는 자원 할당 비율을 그 작업의 요구 사항에 따라 조절하는 비율 조절기(rate regulator)을 통해 작업들 개수와 상관없이 O(1)의 오차를 갖게 되었다. 따라서, 어떤 상황속에서도 사용자가 요구한 일정 비율로 자원을 할당할 수 있는 정확도를 갖게 되었다.
제안된 스케쥴러의 성능을 측정하고 비교하기 위해 모의실험을 수행하였다. 이 실험 결과를 통해 상대 지분 및 절대 지분의 효율적인 표현, 동적환경 지원의 용이함, 그리고 향상된 정확도를 확인할 수 있었다. 또한 향상된 정확도가 바탕이 된, 과부하 상태에서의 점진적 성능감소(graceful degradation)를 지원함으로써, 전체 시스템 활용도가 향상됨을 살펴보았다.
