Biased Virtual Finishing Time

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.

Principles of Operations

It is the scheduler’s objective to deliver the behavior expected by the user in a manner that maximizes the overall value of the system to its users. We have reduced this objective to the following six principles of operations:

—Priority.

The system should not degrade the performance of a high priority application in the presence of a low priority application.

—Proportional sharing among real-time and conventional applications in the same priority class.

Proportional sharing applies only if the scheduler cannot satisfy all the requests in the system. The system will fully satisfy the requests of all applications requesting less than their proportional share. The resources left over after satisfying these requests are distributed proportionally among tasks that can use the excess. While it is relatively easy to control the execution rate of conventional applications, the execution rate of a real-time application is controlled by selectively shedding computations in as even a rate as possible.

—Graceful transitions between fluctuations in load.

The system load varies dynamically, new applications come and go, and the resource demand of each application may also fluctuate. The system must be able to adapt to the changes gracefully, particularly by being able to effectively utilize available resources when the system is heavily loaded.

—Satisfying real-time constraints and fast interactive response time in underload.

If real-time and interactive tasks request less than their proportional share, their time constraints should be honored when possible, and the interactive response time should be short.

—Trading off instantaneous fairness for better real-time and interactive response time.

While it is necessary that the allocation is fair on average, insisting on being fair instantaneously at all times can cause many more deadlines to be missed and deliver poor response time to short running tasks. We will tolerate some instantaneous unfairness so long as the extent of the

unfairness is bounded. For example, a long-running batch application can tolerate some extra short-term delay without any noticeable loss in overall performance to allow a real-time application to meet its immediate deadline. This is the same motivation behind the design of multi-level feedback schedulers to improve the response time of interactive tasks.

—Notification of resource availability.

SMART allows applications to specify if and when they wish to be notified if it is unlikely that their computations will be able to complete before their given deadlines.

Interface Design

Fundamental to the design of SMART is the separation of importance information as expressed by user preferences from the urgency information as expressed by the time constraints of the applications. Prematurely collapsing urgency and importance information into a single priority value, as is the case with standard UNIX SVR4 real-time scheduling, results in a significant loss

of information and denies the scheduler the necessary knowledge to perform its job effectively. By providing both dimensions of information, the scheduler can do a better job of sequencing the resource requests in meeting the time constraints, while ensuring that even if not all time constraints can be met, the more important applications will at least meet their time constraints.

While SMART accounts for both application and user information in managing resources, it in no way imposes demands on either application developers or end users for information they cannot or choose not to provide. The design provides reasonable default behavior as well as incrementally better results for incrementally more information. By default, an end user can just run an application as he would today and obtain fair behavior. If he desires that more resources should be allocated to a given application, SMART provides simple controls that can be used to express that to the scheduler. Similarly, an application developer need not use any of SMART’s real-time programming constructs unless he desires such functionality. Alternatively, he might choose to use only time constraints, in which case he need not know about notifications or availabilities. When the functionality is not needed, the information need not be provided. When the real-time programming support is desired, as is often the case with multimedia applications, SMART has the ability to provide it.

End User Support

Different users may have different preferences for how processing time should be allocated among a set of applications. Not all applications are always of equal importance to a user. For example, a user may want to ensure that an important video teleconference be played at the highest image and sound quality possible, at the sacrifice if need be of the quality of a television program that the user was just watching to pass the time. However, current practice, as typified by UNIX, provides little in the way of predictable controls to bias the allocation of resources in accordance with user preferences. For instance, in UNIX timesharing, all that a user is given is a nice knob whose setting is poorly correlated to the scheduler’s externally observable behavior .

As users may have different preferences for how processing time should be allocated among a set of applications, SMART provides two parameters to predictably control processor allocation: priority and share. These parameters can be used to bias the allocation of resources to provide the best performance for those applications which are more important to the user. The user can specify that applications have different priorities, meaning that the application with the higher priority is favored whenever there is contention for resources. The system will not degrade the performance of a higher priority application to execute a lower priority application. For instance, suppose we have two real-time applications, one with higher priority than the other, and

the lower priority application has a computation with a more stringent time constraint. If the lower priority application needs to execute first in order to meet its time constraint, the system will allow it to do so as long as its execution does not cause the higher priority application to miss its time constraint.

Among applications at the same priority, the user can specify the share of each application, resulting in each application receiving an allocation of resources in proportion to its respective share whenever there is contention for resources. Shares only affect the allocation of resources among applications with equal priorities.

THE SMART INTERFACE AND USAGE MODEL

The SMART interface provides two kinds of support for multimedia applications. One is to support the developers of multimedia applications that are faced with writing applications that have dynamic and adaptive real-time requirements. The other is to support the end users of multimedia applications, each of whom may have different preferences for how a given mix of applications should run. For the application developer, SMART provides time constraints and notifications for supporting applications with real-time computations. For the user of applications, SMART provides priorities and shares for predictable control over the allocation of resources. An overview of the interface is presented here. A more detailed description can be found in Nieh and Lam .

Application Developer Support

Multimedia application developers are faced with the problem of writing applications with real-time requirements. They know the time constraints that should be met in these applications and know how to allow them to adapt and degrade gracefully when not all time constraints can be met. The problem is that current operating system practice, as typified by UNIX, does not

provide an adequate amount of functionality for supporting these applications. For example, in dealing with time in UNIX time-sharing, an application can obtain simple timing information such as elapsed wall clock time and accumulated execution time during its computations. An application can also tell the scheduler to delay the start of a computation by “sleeping” for a duration of time. But it is not possible for an application to ask the scheduler to complete

a computation within certain time constraints, nor can it obtain feedback from the scheduler on whether or not it is possible for a computation to complete within the desired time constraints. The application ends up finding out only after the fact that its efforts were wasted on results that could not be delivered on time. The lack of system support exacerbates the difficulty of writing

applications with real-time requirements and results in poor application performance.

Demands of Multimedia Applications on Processor Scheduling

To understand the requirements imposed by multimedia applications on processor scheduling, we first describe the salient features of these applications and their special demands that distinguish them from the conventional (nonreal- time) applications that current operating systems are designed for:

—Soft real-time constraints.

Real-time applications have application-specific timing requirements that need to be met [Northcutt 1987]. For example in the case of video, time constraints arise due to the need to display video in a smooth and synchronized way, often synchronized with audio. Time constraints may be periodic or aperiodic in nature. Unlike conventional applications,

tardy results are often of little value; it is often preferable to skip a computation than to execute it late. Unlike hard real-time environments, missing a deadline only diminishes the quality of the results and does not lead to catastrophic failures.

—High resource demands and frequent overload.

Multimedia applications can present very high demands for resources. Today, video applications are often limited to simple VCR-like functions as opposed to delivering richer video processing functionality, and video playback windows are often tiny at full display rate because of computing resources insufficient to keep up with high fidelity resolution. Since applications such as real-time video are highly resource intensive and can consume the resources of an entire machine, resources are commonly overloaded, with resource demand often exceeding its

availability.

—Dynamically adaptive applications.

When resources are overloaded and not all time constraints can be met, multimedia applications are often able to adapt and degrade gracefully by offering a different quality of service

. For example, a video application may choose to skip some frames or display at a lower image quality when not all frames can be processed in time. Because not all multimedia applications

are written with adaptive capabilities, adaptive and non-adaptive multimedia applications must be able to co-exist.

—Co-existence with conventional computations.

Real-time applications must share the desktop with already existing conventional applications, such as word processors, compilers, and so on. Real-time tasks should not always be

allowed to run in preference to all other tasks because they may starve out important conventional activities, such as those required to keep the system running. Moreover, users would like to be able to combine real-time and conventional computations in new applications, such as multimedia documents, which mix text and graphics as well as audio and video. In no way should the capabilities of a multiprogrammed workstation be reduced to a single function

commodity television set in order to meet the demands of multimedia applications.

—Dynamic environment.

Unlike static embedded real-time environments, workstation users run an often changing mix of applications, resulting in dynamically varying loads.

—User preferences.

Different users may have different preferences, for example, in regard to trading off the speed of a compilation versus the display quality of a video, depending on whether the video is part of an important teleconferencing session or just a television show being watched while waiting for an important computational application to complete.

A SMART Scheduler for Multimedia Applications

The workload on computers is rapidly changing. In the past, computers were used in automating tasks around the work place, such as word and accounts processing in offices, and design automation in engineering environments. The human-computer interface has been primarily textual, with some limited amount of graphical input and display. With the phenomenal improvement in hardware technology in recent years, even highly affordable personal computers are capable of supporting much richer interfaces. Images, video, audio, and

interactive graphics have become common place. A growing number of multimedia applications are available, ranging from video games and movie players, to sophisticated distributed simulation and virtual reality environments. In anticipation of a wider adoption of multimedia in applications in the future, there has been much research and development activity in computer architecture for multimedia applications. Not only is there a proliferation of processors that are

built for accelerating the execution of multimedia applications, even general purpose microprocessors have incorporated special instructions to speed their execution

While hardware has advanced to meet the special demands of multimedia applications, software environments have not. In particular, multimedia applications have real-time constraints which are not handled well by today’s general-purpose operating systems. The problems experienced by users of multimedia on these machines include video jitter, poor “lip-synchronization” between audio and video, and slow interactive response while running video applications. Commercial operating systems such as UNIX SVR4 attempt to address these problems by providing a real-time scheduler in addition to a standard time-sharing scheduler. However, such hybrid schemes lead to experimentally demonstrated unacceptable behavior, allowing runaway realtime activities to cause basic system services to lock up, and the user to lose control over the machine .

This paper argues for the need to design a new processor scheduling algorithm that can handle the mix of applications we see today. We present a scheduling algorithm that we have implemented in the Solaris UNIX operating system [Eykholt et al. 1992], and demonstrate its improved performance over existing schedulers in research and practice on real applications. In particular, we have quantitatively compared it against the popular weighted fair queueing and UNIX SVR4 schedulers in supporting multimedia applications in a realistic workstation environment.