The notion of a virtual finishing time (VFT), which measures the degree to which the task has been allotted its proportional share of resources, has been previously used in describing fair queueing algorithms [Bennett and Zhang 1996; Demers et al. 1989; Parekh and Gallager 1993; Stoica et al. 1996; Waldspurger 1995]. These proportional sharing algorithms associate aVFTwith each activity as a way to measure the degree to which an activity has received its proportional allocation of resources. We augment this basic notion in the following ways. First, our use of virtual finishing times incorporates tasks with different priorities. Second, we add to the virtual finishing time a bias, which is a bounded offset used to measure the ability of conventional tasks to tolerate longer and more varied service delays. The biased virtual finishing time allows us to provide better interactive and real-time response without compromising fairness.
Finally and most importantly, fair queueing algorithms such as weighted fair queueing (WFQ) execute the activity with the earliest virtual finishing time to provide proportional sharing. SMART only uses the biased virtual finishing time in the selection of the candidates for scheduling—real-time constraints are also considered in the choice of the application to run. This modification enables SMART to handle applications with aperiodic constraints and overloaded
conditions. Our algorithm organizes all the tasks into queues, one for each priority. The
tasks in each queue are ordered in increasing BVFT values. Each task has a virtual time, which advances at a rate proportional to the amount of processing time it consumes divided by its share. Correspondingly, each queue has a queue virtual time, which advances only if any of its member tasks is executing. The rate of advance is proportional to the amount of processing time spent on the task divided by total number of shares of all tasks on the queue. To be more precise, where Sa represents the share of application a, and AP is the set of applications
on the queue with priority P.Previous work in the domain of packet switching provides a theoretical basis for using the difference between the virtual time of a task and the queue virtual time as a measure of whether the respective task has consumed its proportional allocation of resources . If a task’s virtual time is equal to the queue virtual time, it is considered to have received its proportional allocation of resources. An earlier virtual time indicates that the task has less than its proportional share, and, similarly, a later virtual time indicates that it has more than its proportional share. Since the queue virtual time advances at the same rate for all tasks
on the queue, the relative magnitudes of the virtual times provide a measure of the degree to which each task has received its proportional share of resources.
