Abstract
Relate a task to a weight = (E/P), where E is its required execution during its period length P. Min-to-Max-Weight Fairness is a fair scheduling issue on multiprocessors, defining each task’s execution as a value within a specified range (implied by its minimum weight and maximum weight). In prior works, this problem was stated as a result rather than a specific problem to solve. No optimal (or near-optimal) scheduling algorithm for Min-to-Max-Weight Fairness was proposed, in the sense of minimizing the difference between tasks’ actual execution time and their maximum bounds. Moreover, tasks were not guaranteed to have the chance to reach their own maximum bounds. In other words, the utmost values of tasks’ actual execution were neither guaranteed nor defined with formal descriptions. In this paper, we formally define Min-to-Max-Weight Fairness, propose a near-optimal scheduling algorithm for it, and provide related proofs. Our algorithm contains three steps: imprecise computation decomposition, network flow graph formulation, and schedule construction. Comprising these three steps, our algorithm always schedule tasks to satisfy Min-to-Max-Weight Fairness, and assure each task of a possible utmost execution time equal to (or 1 unit less than) its maximum bound. Despite this 1-unit limitation, our algorithm optimally minimizes the difference between tasks’ actual execution time and their maximum bounds. In conclusion, we provide a near-optimal algorithm with 1 unit difference at most.