기존 비례지분의 스케줄링 기법은 공정성의 정확도가 낮거나 또는 높은 공정성을 정확도를 보이는 경우 스케줄링 오버헤드(overhead)가 크다는 문제점을 가지고 있다. 본 논문에서는 높은 공정성의 정확도를 보이는 만족도 지수 기반의 비례지분 스케줄링 알고리즘을 제안한다. 먼저, 태스크 만족도 지수를 정의하고, 만족도 지수가 가장 낮은 태스크를 다음 실행할 태스크로 선택(MSF: Minimum Satisfaction First) 하는 알고리즘을 소개한다. MSF 알고리즘을 기반으로 하여 가상 태스크를 이용하여 O(1)의 스케줄링 오버헤드를 만족하면서 높은 공정성을 갖는 근사화 기법을 제안한다. 모의 실험 결과 제안 기법은 적은 부하로 태스크의 수에 상관없이 또한 지분이 편향되더라도 작은 상수의 공정성 서비스 오차를 가지며, 기존 기법들에 비해 가장 높은 공정성 정확도를 보인다.
Most proportional share scheduling algorithms developed to accurately reflect the required resource allocation lead to a lower degree of fairness or suffer from generating higher scheduling overhead. In this paper, we propose a task satisfaction index-based proportional share scheduling algorithm for multimedia systems. Our experimental results show that our scheme outperforms the several existing scheduling algorithms in terms of fairness service error.
