This chapter presents background and motivation for the HLS architecture. It analyzes operating system support for soft real-time applications in terms of the different classes of schedulers that have been described in the literature and their associated programming models. Also, the requirements of several common types of multimedia applications are described in order to understand how applications can be matched with appropriate schedulers.
The set of abstractions and conventions implemented by a particular system that allow soft real-time applications to meet their requirements defines a programming model. A multimedia scheduler must support a programming model that is useful and understandable to the people who develop applications for the system. Furthermore, the scheduler, in conjunction with applications, must meet user expectations and provide understandable behavior in the face of sets of applications that demand resources exceeding the capacity of the system.
For example, SMART [67] and Rialto [40] both offer deadline-based scheduling to applications in the form of time constraints. To use a time constraint, an application requests an amount of CPU time before a deadline (for example, 20 ms of processing during the next 100 ms); the scheduler then notifies the application that the constraint is either accepted or rejected.
Although both systems provide the same basic abstraction, the guarantees they offer are different. Once Rialto informs an application that a requested time constraint is feasible it guarantees that the time for that constraint will have been dedicated to the requesting application no matter what other applications might do. SMART, on the other hand, may invalidate a previously accepted time constraint part way through its execution, taking away its reserved time, if a higher-priority application requests a conflicting time constraint. So, SMART potentially provides faster response time for higher-priority applications that unexpectedly request CPU time, but Rialto supports a programming model in which a developer does not need to worry about the case in which a feasible time constraint is not actually scheduled.
In both cases the designers of the system believed they were making the right decision. How can it be that one man’s features are another man’s bugs? Clearly the authors have not agreed upon either the goals they were trying to achieve or the criteria by which their systems should be judged. Tradeoffs such as the one in this example are important because they affect the basic set of assumptions that programmers can make while implementing multimedia applications.
This chapter analyzes the sets of goals that multimedia schedulers might try to achieve. It creates a taxonomy of the kinds of programming models used to achieve these goals and it characterizes a number of representative systems used to run multimedia applications within this taxonomy. The top-level distinction made by this taxonomy is between high-level algorithms used to respond to changes in application requirements, and low-level algorithms used to make individual scheduling decisions. For each of these two broad classes we present a number of sub-categories, including representative algorithms and their important properties.
The use of this taxonomy is intended to enable: (1) careful comparisons to be made between existing work, (2) the identification of new parts of the design space leading to possible new solutions, and (3) a better understanding of how the needs of several types of multimedia applications are served by (or are not well-served by) the various programming models promoted by important types of multimedia schedulers.
A general-purpose operating system (GPOS) for a PC or workstation must provide fast response time for interactive applications, high throughput for batch applications, and some amount of fairness between applications. Although there is tension between these requirements, the lack of meaningful changes to the design of time-sharing schedulers in recent years would seem to indicate that they are working well enough.
The goal of a hard real-time system is similarly unambiguous: all hard deadlines must be met. The design of the system is dictated by this requirement, although it conflicts to some extent with designing a low-cost system. Despite the conflict, there appears to be a standard engineering practice for building such systems: statically determine resource requirements and then overprovision processor cycles as a hedge against unforeseen situations.
Not surprisingly, there is a large space of systems whose requirements fall between these two extremes. These are soft real-time systems: they need to support a dynamic mix of applications, some of which must perform computations at specific times. Missed deadlines are undesirable, but not catastrophic. In this chapter we are concerned with the requirements placed upon general-purpose operating systems that have been extended with soft real-time schedulers for the purpose of supporting multimedia applications.
We have attempted to identify an uncontroversial set of requirements that the “ideal” multimedia operating system would meet. We do not claim that the HLS architecture can meet all of these requirements, and in fact, it is unlikely that any single system can meet all of these requirements for all types of applications. Even so, the requirements are important because they describe the space within which multimedia systems are designed. A particular set of prioritizations among the requirements will result in a specific set of tradeoffs, and these tradeoffs will constrain the design of the user interface and the application programming model of a system.
R1: Meet the scheduling requirements of coexisting, independently written, possibly misbehaving soft real-time applications.
The CPU requirements of a real-time application are often specified in terms of an amount and period, where the application must receive the amount of CPU time during each period of time. No matter how scheduling requirements are specified, the scheduler must be able to meet them without the benefit of global coordination among application developers--multimedia operating systems are open systems in the sense that applications are written independently.
A misbehaving application (from the point of view of the scheduler) will overrun by attempting to use more CPU time than was allocated to it. Schedulers that provide load isolation guarantee a minimum amount or proportion of CPU time to each multimedia application even if other applications overrun (by entering an infinite loop, for example).
R2: Minimize development effort by providing abstractions and guarantees that are a good match for applications’ requirements.
An important role of the designers of soft real-time systems is to ease application developers into a world where their application gracefully shares machine resources with other applications. We propose the following test: compare the difficulty of writing an application for a given multimedia scheduler to the difficulty of writing the same application if it could assume that it is the highest priority application in the system (thus having the machine logically to itself). If the difference in costs is too high, application developers will assume that contention does not exist. Rather than using features provided by the scheduler, they will force their users to manually eliminate contention.
Getting the programming model right is very important: if a system becomes widely used, the effort expended by application developers will far outweigh the effort required to implement the system. It is therefore possible for small increases in usability to justify even large amounts of implementation complexity and effort. In other words, the programming model matters.
R3: Provide a consistent, intuitive user interface.
Users should be able to easily express their preferences to the system and the system should behave predictably in response to user actions. Also, it should give the user (or software operating on the user’s behalf) feedback about the resource usage of existing applications and, when applicable, the likely effects of future actions.
R4: Run a mix of applications that maximizes overall value.
Unlike hard real-time systems, PCs and workstations cannot overprovision the CPU resource; demanding multimedia applications tend to use all available cycles. The multimedia OS should avoid conservatively rejecting applications that may be feasible. During overload, the multimedia OS should run a mix of applications that maximizes overall value. Value is a subjective measure of the utility of an application, running at a particular time, to a particular user.
The top level of our taxonomy of scheduling support for multimedia applications makes a distinction between low-level algorithms that make individual scheduling decisions, and higher-level algorithms that respond to application mode changes (when an application starts, terminates, or has a change of requirements). The second level of the taxonomy breaks these broad categories into classes of algorithms such as “CPU reservations” and “admission-control.” We identify important features of these classes and place representative schedulers from the literature within them. The key questions that we answer about each category is:
For each scheduler, we provide a brief description, give examples of systems that implement it, and examine which of the requirements from Section 2.2 the scheduler fulfills. These characteristics are summarized in Table 2.1.
|
The uniprocessor real-time scheduling problem has essentially been solved by static priority analysis [4] when the set of applications and their periods and amounts are known in advance, and when applications can be trusted not to overrun. Static priority schedulers maintain the simple invariant that the runnable thread with highest priority is always scheduled. Static-priority scheduling is a generalization of rate monotonic analysis [53]. The core result of rate monotonic analysis is that if a set of independent periodic tasks is scheduled rate monotonically--with the shortest-period task having the highest priority, the second-shortest having the second-highest priority, and so on--then no task will ever miss a deadline as long as the total utilization over all tasks is less than 69%.
Popular general-purpose operating systems such as Linux and Windows 2000 extend their time-sharing schedulers to support static priority threads that have strictly higher priority than any time-sharing thread. Schedulers with this structure exhibit well-known pathologies such as unbounded priority inversion (unless synchronization primitives have been augmented to support priority inheritance) and starvation of time-sharing applications during overload [66]. Furthermore, developers are likely to overestimate the priority at which their applications should run because a poorly performing application reflects negatively on its author. This phenomenon is known as priority inflation.
BeOS has a clever requirement that, if followed, will not only eliminate priority inflation but also achieve an approximate rate-monotonic schedule: static priorities are explicitly tied to thread latency requirements, with higher priorities corresponding to shorter latencies. For example, programmers are encouraged to schedule threads with a 5-10 ms latency sensitivity at priority 110, and threads with a 0.5-1 ms latency sensitivity at priority 120 [60].
Although static priority schedulers are simple, efficient, and well understood, they fail to isolate applications from one another, and optimal priority assignment requires coordination among application developers. Applications can only be guaranteed to receive a certain amount of CPU time if the worst-case execution times of higher-priority applications are known, and this is generally not possible. Still, the static-priority programming model is reasonably intuitive for both users (if an application is starving, there must be overload at higher priorities) and programmers (higher priority applications run first), and it supports legacy applications.
A CPU reservation provides an application with load isolation and periodic execution. For example, a task could reserve 10 ms of CPU time out of every 50 ms; it would then be guaranteed to receive no less than the reserved amount per period. Every implementation of reservations requires an admission test to tell if a new reservation will overload the system, and an enforcement mechanism to prevent applications that exceed their allocations from using up time reserved for other tasks.
The original Spring kernel [81] is an example that represents one end of the reservation spectrum, i.e., it provides precise hard real-time guarantees. To achieve these hard guarantees Spring required significant amounts of a priori information and associated tools to extract that information. For example, the Spring programming language had restrictions placed on it such as capping all loops, no dynamic memory management, etc. Due to the cost of runtime support in this system, this solution is not suitable for continuous media. However, the Spring system was then extended by Kaneko et al. [42] to integrate continuous multimedia streams into this hard guarantee paradigm.
In general-purpose operating systems reservations can be implemented in a variety of ways. Nemesis [49] uses an earliest deadline first (EDF) scheduler in conjunction with an enforcement mechanism, and the portable Resource Kernel [68] uses a rate monotonic scheduler, the scheduler by Lin et al. [50] is driven by a table, and finally, Rialto [40] and Rialto/NT [37] provide reservations by using a tree-based data structure to represent time intervals.
CPU reservations satisfy the requirement of supporting coexisting, possibly misbehaving real-time applications. They eliminate the need for global coordination because application resource requirements are stated in absolute units (time) rather than relative units like priority or share. However, reservation-based schedulers must be told applications’ periods and amounts. The period is easier to determine: the characteristics of a periodic thread, such as its data rates, buffer sizes, and latency requirements typically dictate its period; likewise, applications often implicitly make it available to the operating system by using a timer to awaken each thread every time its period begins. The amount of CPU time that an application requires can be difficult to predict, as it is both platform and data dependent. For some applications a good estimate of future amount can be obtained by averaging previous amounts; other applications such as the notoriously variable MPEG video decoder inherently show wide fluctuations in amount [8, 16]. Underestimates of amounts will sometimes prevent application requirements from being met, and overestimates will result in needless rejection of multimedia applications. Furthermore, determining CPU requirements through measurement begs the question of how to tell when a program is behaving normally and when it is overrunning.
Because reservations provide applications with fairly hard performance guarantees--how hard depends on the particular scheduler and on the characteristics of the operating system--they are best suited for scheduling applications that lose much of their value when their CPU requirements are not met. Reservations can be used to support legacy multimedia applications if the period and amount can be determined from outside the applications and applied to them without requiring modifications.
Chu and Nahrstedt [16] describe CPU service classes, an abstraction for giving statistical CPU reservations to highly variable applications. They give the application a base reservation that is assumed to meet its processing requirements in the common case. An overrun partition, a separate reservation, is shared by all periodic variable processing time (PVRT) applications. When any application in this class overruns its normal reservation, it is assigned CPU time from the overrun partition. The assumption is that since each PVRT application is overrunning a small fraction of the time, demand for the overrun partition will not often collide. In this dissertation reservations based on this idea will be called probabilistic CPU reservations in order to fit in with our reservation naming scheme.
Proportional share schedulers are quantum-based weighted round-robin schedulers that guarantee that an application with N shares will be given at least N/T of the processor time, on average, where T is the total number of shares over all applications. This means that the absolute fraction of the CPU allocated to each application decreases as the total number of shares increases, unless the system recomputes shares each time a new application is admitted. Quantum size is chosen to provide a good balance between allocation error and system overhead.
Other than Lottery scheduling [90], which is a randomized algorithm, all proportional share algorithms appear to be based on a virtual clock--a per-application counter that the scheduler increments in proportion to the amount of real time the application executes and in inverse proportion to the application’s share. At each reschedule, the scheduler dispatches the runnable application with the lowest virtual clock value. The differences between proportional share schedulers come from the details of how virtual times are calculated.
Some proportional share schedulers decouple an application’s share from its latency requirement without actually providing any guarantee. SMART [67] is in this category: it supports a mixed programming model in which applications receiving proportional share scheduling can meet real-time requirements using the deadline-based time constraint abstraction. BVT [20] associates a warp value with each application; non-zero warp values allow a thread to build up credit while blocked, increasing the chances that it will be scheduled when it wakes up.1 Applications with high warp values will, on average, be dispatched more quickly by BVT, but no bound on scheduling latency has been shown. The hybrid lottery scheduler described by Petrou et al. [71] automatically provides improved response time for interactive applications--this is an important specialization for using proportional share schedulers in real situations.
Other proportional share algorithms bound the allocation error of threads that they schedule--this a necessary condition if they are to provide a real-time guarantee. For example, both earliest eligible deadline first (EEVDF) [85] and start-time fair queuing (SFQ) [28] bound allocation error. This, in combination with admission control, allows a proportional share scheduler to provide functionality indistinguishable from a CPU reservation (we will return to this notion and formalize it in Chapter 5). Unfortunately, the period of a reservation provided by a PS scheduler is determined by the scheduler (by its allocation error bound and its quantum size) rather than by the application. So, in general, PS schedulers are best suited to scheduling applications that have latency requirements considerably longer than the scheduling quantum, or that do not require precise real-time scheduling.
EDF is an attractive scheduling discipline because it is optimal in the sense that if there exists any algorithm that can schedule a set of tasks without missing any deadlines, then EDF can also schedule the tasks without missing any deadlines. Soft real-time OSs primarily use EDF to keep track of deadline urgency inside the scheduler; only a few systems have exposed deadline-based scheduling abstractions to application programmers. Rialto and SMART couple deadlines with an admission test (because EDF does not work well during overload) and call the resulting abstraction a time constraint. The open environment for real-time applications [18] and PShED [52] provide applications with a uniformly slower processor (USP) abstraction that ensures they will receive a given share of the processor bandwidth over any time interval specified by the application.
Time constraints present a difficult programming model because they require fine-grained effort: the application programmer must decide which pieces of code to execute within the context of a time constraint in addition to providing the deadline and an estimate of the required processing time. Applications must also be prepared to skip part of their processing if the admission test fails. However, in Rialto, requests for time constraints are guaranteed to succeed for applications that have CPU reservations as long as the total amount of time reserved by time constraints does not exceed the rate and granularity of the reservations. Once a time constraint is accepted, Rialto guarantees the application that it will receive the required CPU time. SMART will sometimes deliver an upcall to applications informing them that a deadline previously thought to be feasible has become infeasible.
The programming model provided by uniformly slower processors is similar to the programming model supported by Rialto reservations and time constraints: each application is granted a fraction of the processor, but must dynamically notify the scheduler of its deadlines in order to meet them. However, Rialto allows time constraints to reserve extra CPU time if there is slack in the schedule, while USPs restrict the total bandwidth that is allocated to each application. Also, while Rialto did not present conditions for guaranteeing the schedulability of applications, a uniformly slower processor guarantees that any application that can be scheduled by a processor of speed s can also be scheduled by that scheduler if it is given a USP with rate s/f on a processor of speed f. For example, assume that a task set is schedulable using an EDF scheduler on a 25 MHz processor. Then, it will also be schedulable on a 250 MHz processor if the EDF scheduler is given a uniformly slower processor with rate 0.1 (because 25/250 = 0.1).
The proximity of a deadline alerts an EDF scheduler to the urgency of a task; SMART decouples urgency from importance, which is assumed to correlate with the value of the task to the user. SMART only considers a subset of the most important tasks when performing EDF scheduling. It gives no guarantee to applications--if an important task with a close deadline appears, other tasks with deadlines that were previously thought to be feasible will not be allocated processor time. Rialto, on the other hand, always allocates the promised processor time to an application once a deadline has been granted; this means the scheduler is not free to allocate this time to a more important task that arrives after a deadline was granted, but it also means that the Rialto programmer need not worry about the case in which a feasible deadline is not actually scheduled. By giving a stronger guarantee to the application Rialto provides an easier programming model, but SMART potentially provides faster response times to important tasks.
Multimedia OSs need to work in situations where total load is difficult to predict and execution times of individual applications vary considerably. To address these problems new approaches based on feedback control have been developed. Feedback control concepts can be applied at admission control and/or as the scheduling algorithm itself.
In the FC-EDF work [56] a feedback controller is used to dynamically adjust CPU utilization in such a manner as to meet a specific set point stated as a deadline miss percentage. FC-EDF is not designed to prevent individual applications from missing their deadlines; rather, it aims for high utilization and low overall deadline miss ratio.
SWiFT [83] uses a feedback mechanism to estimate the amount of CPU time to reserve for applications that are structured as pipelines. The scheduler monitors the status of buffer queues between stages of the pipeline; it attempts to keep queues half full by adjusting the amount of processor time that each stage receives.
Both SWiFT and FC-EDF have the advantage of not requiring estimates of the amount of processing time that applications will need. Both systems require periodic monitoring of the metric that the feedback controller acts on. In general, feedback-based schedulers provide no guarantees to individual applications. Rather, they are designed to achieve high system utilization with few deadline misses over all applications.
Hierarchical (or multi-level) schedulers generalize the traditional role of schedulers (i.e., scheduling threads or processes) by allowing them to allocate CPU time to other schedulers. The root scheduler gives CPU time to a scheduler below it in the hierarchy and so on until a leaf of the scheduling tree--a thread--is reached.
The implementation of a hierarchical scheduler does not need to have a tree structure; for example, the Linux and Windows 2000 schedulers are conceptually hierarchical (the fixed-priority root scheduler always runs the static-priority scheduler if it has any ready threads and the time-sharing scheduler otherwise) but they both have a flat implementation (an array of run queues).
The scheduling hierarchy may either be fixed at system build time or dynamically constructed at run time. CPU inheritance scheduling [24] probably represents an endpoint on the static vs. dynamic axis: it allows arbitrary user-level threads to act as schedulers by donating the CPU to other threads.
Hierarchical scheduling has two important properties. First, it permits multiple programming models to be supported simultaneously, potentially enabling support for applications with diverse requirements. Second, it allows properties that schedulers usually provide to threads to be recursively applied to groups of threads. For example, a fair-share scheduler at the root of the scheduling hierarchy on a multi-user machine with a time-sharing scheduler below it for each user provides load isolation between users that is independent of the number of runnable threads each user has. A single-level time-sharing or fair-share scheduler does not do this.
Resource containers [5] and hierarchical start-time fair queuing (SFQ) [27] provide flexible isolation using hierarchical versions of proportional share schedulers. Deng et al. [18] describe a two-level scheduling hierarchy for Windows NT that has an EDF scheduler at the root of the hierarchy and an appropriate scheduler (rate-monotonic, EDF, etc.) for each real-time application. Furthermore, they developed a schedulability test that takes locally and globally synchronizing applications into account (although it relies on non-preemptive critical sections).
We characterize system behavior during application mode changes by looking at the various kinds of guarantees that the operating system gives applications. The guarantee is an important part of the programming model since it determines what assumptions the programmer can make about the allocation of processor time that an application will receive.
When the OS gives an application a guarantee, it is restricting its future decision making in proportion to the strength of the guarantee. Seen in this light, it is understandable that many systems give applications weak or nonexistent guarantees--there is an inherent tradeoff between providing guarantees and dynamically optimizing value by allocating cycles on the fly in response to unexpected demand.
Best effort systems make no guarantees to applications. Rather than rejecting an application during overload, a best effort system reduces the processor time available to other applications to “make room” for the new one. This works well when application performance degrades gracefully.
Although “best effort” often has a negative connotation, it does not need to imply poor service. Rather, a best-effort system avoids the possibility of needlessly rejecting feasible applications by placing the burden of avoiding overload on the user. The computer and user form a feedback loop, where the user manually reduces system load after observing that applications are performing poorly.
We propose two requirements that applications must meet for “feedback through the user” to work. First, applications must degrade gracefully. Second, application performance must not be hidden from the user, who has to be able to notice degraded performance in order to do something about it. An application that fails both of these criteria is the software controlling a CD burner: it does not degrade gracefully since even a single buffer underrun will ruin a disc, and the user has no way to notice that the burner is running out of buffers supplied by the application.
A system that implements admission control keeps track of some metric of system load, and rejects new applications when load is above a threshold. For systems implementing reservations, system load could be the sum of the processor utilizations of existing reservations. The threshold for EDF-based schedulers is 100%; rate-monotonic systems can either use the worst-case bound of 69% [53] or perform the exact characterization, which has a higher run-time cost but is usually able to achieve higher utilization [48].
Because it can be used to prevent overload, admission control allows a multimedia system to meet the requirements of all admitted applications. It provides a simple programming model: applications are guaranteed to receive the amount of resources that they require until they terminate or are terminated (assuming that CPU requirements can be accurately estimated at the time a program first requests real-time service). Admission control also makes the system designer’s job easy: all that is required is a load metric and a threshold.
Admission control does not serve the user well in the sense that there is no reason to believe that the most recently started application is the one that should be rejected. However, when a valuable application is denied admission the user can manually decrease the load on the system and then attempt to restart the application. Obviously, this feedback loop can fail when the admission controller rejects a job not directly initiated by the user (for example, recording a television show to disk while the user is not at home).
Best effort and admission control are simple heuristics for achieving high overall value in situations where the user can take corrective action when the heuristic is not performing well. Resource management techniques attempt to achieve high overall value with little or no user intervention. They do this by stipulating that guarantees made to applications may be renegotiated to reflect changing conditions. Renegotiation is initiated when the resource manager calculates that there is a way to allocate CPU time that is different from current allocations that would provide higher value to the user. To perform this calculation, the system must have, for each application, some representation of the relationship between the resources granted to the application and the application’s perceived value to the user. The Dynamic QoS Resource Manager [13, 12] and the QoS broker [65] both fall into this category. Oparah [70] describes a resource management system that extends Nemesis; it has the interesting feature that the user can assign positive or negative feedback to decisions made by the resource manager. This is designed to bring the resource manager’s actions more closely into line with user preferences over time.
At the extreme end of resource management is value maximization, where the system understands the exact relationship between service, value, and time for each application and after any mode change chooses settings for each application that maximizes overall value [55].
Adaptive applications support different modes of operation along one or more dimensions. For example, a video player may support several resolutions, frame-rates, and compression methods. Each mode has a set of resource requirements and offers some value to the user. The promise of adaptive applications is that a resource manager will be able to select modes for the running set of applications that provide higher overall value than would have been possible if each application had to be either accepted at its full service rate or rejected outright.
Abdelzaher et al. [1] show that high overall value can be obtained by adapting both the period and execution time of tasks in an aircraft control simulation. The imprecise computation model [30] permits fine-grained adaptation by dividing computations into mandatory and optional parts, where the optional part adds value, if performed.
Assuming that an application already supports different modes, adaptation complicates the application programming model only slightly, by requiring the application to provide the system with a list of supported modes and to change modes asynchronously in response to requests from the system. Adaptive systems also require a more careful specification of what guarantees are being given to applications. For example, is an application asked if it can tolerate degraded service, is it told that it must, or does it simply receive less processor time without being notified? Is renegotiation assumed to be infrequent, or might it happen often?
Adaptation does not appear to make the user’s job, the programmer’s job, or the system designer’s job any easier. Rather, it permits the system to provide more value to the user. A possible drawback of adapting applications is that users will not appreciate the resulting artifacts, such as windows changing size and soundtracks flipping back and forth between stereo and mono. Clearly there is a cost associated with each user-visible adaptation; successful systems will need to take this into account.
Programming models encompass more than high-level abstractions and APIs: any feature (or misfeature) of an operating system that the programmer must understand in order to write effective programs becomes part of the programming model. In this section we explore a few examples of this.
Can applications that block expect to meet their deadlines? Analysis of blocking and synchronization is expected for hard real-time systems; soft real-time programs are usually assumed to not block for long enough to miss their deadlines. Applications that block on calls to servers can only expect the server to complete work on their behalf in a timely [59] way if the operating system propagates the client’s scheduling properties to the server, and if the server internally schedules requests accordingly. Non-threaded servers that do not perform priority queuing of requests can cause priority inversions that delay applications unnecessarily; Ingram [31] describes modifications to the X server that make it more responsive to high priority requests during periods of heavy load.
Does dispatch latency meet application requirements? Dispatch latency is the time between when a thread is scheduled and when it actually runs. It can be caused by the scheduling algorithm or by other factors; for example, in a GPOS a variety of events such as interrupt handling and network protocol processing can delay thread scheduling. Non-preemptive operating systems exacerbate the problem: a high priority thread that wakes up while the kernel is in the middle of a long system call on the behalf of another thread will not be scheduled until the system call completes. Properly configured Windows 2000 [17] and Linux [69] machines have observed worst-case dispatch latencies2 below 10 ms--this meets the latency requirements of virtually all multimedia applications. Unfortunately, their real-time performance is fragile in the sense that it can be broken by any code running in kernel mode. Device drivers are particularly problematic; rigorous testing of driver code is needed in order to reduce the likelihood of latency problems [38]. Hard real-time operating systems keep interrupt latencies very low and prohibit other kinds of unscheduled CPU time; they may have worst-case thread dispatch latencies in the tens of microseconds.
Is the same programming model available to all threads? Very low dispatch latency can be achieved using co-resident operating systems [11, 93]. This approach virtualizes the interrupt controller seen by a general-purpose operating system in order to allow a small real-time kernel to run even when the GPOS has “disabled interrupts.” The GPOS runs in the idle time of the real-time kernel; the two OSs may then communicate through FIFOs that are non-blocking from the real-time side. The programming environment presented by the real-time kernel is sparse (since it cannot easily invoke services provided by the GPOS) and unforgiving (mistakes can easily hang or crash the machine). However, this is a useful approach for highly latency-sensitive applications that can be divided into real-time and non-real-time components.
The real-time requirements imposed on an operating system are driven by the applications that must be supported. This section briefly describes the main characteristics of several important categories of applications; these are summarized in Table 2.2 .
|
Decoding and displaying high-quality full-screen video (such as the MPEG-2 data on a DVD) in software is CPU intensive. Furthermore, the time required to decode an MPEG video stream is highly variable both on short time scales due to different types of frames and long time scales due to varying scene content [8]. Short-term variation can be smoothed over by buffering several decoded frames before displaying them.
Audio processing, on the other hand, is predictable and requires relatively little CPU time on modern processors. The end product of audio processing is a logically continuous stream of data; users are highly intolerant to holes or skips in this stream.
Audio and video applications, live or recorded, can, in principle, be adaptive. However, current applications tend to either not be adaptive, or to be manually adaptive at a coarse granularity. For example, although Winamp, a popular MP3 player, can be manually configured to reduce its CPU usage by disabling stereo sound, it has no mechanism for doing this in response to a shortage of processor cycles.
Stored audio and video: These applications are characterized by the lack of a tight end-to-end latency requirement. Reading from disk (or DVD) and decoding can be pipelined, using large buffers if necessary. The only latency-sensitive part of the process for video is switching the frame that is currently being displayed. Depending on what hardware support is available, there may be no analogous latency-sensitive operation for audio since some sound hardware can retrieve buffers from main memory as it needs them using DMA, awakening a user process only when some low-water mark is reached. Stored audio and video that arrive over the network can be treated in the same way as locally stored audio and video unless the bandwidth of the media is high enough that bursty network protocol processing becomes a problem.
Hard disk video recorders such as TiVo and Replay are dedicated devices that encode incoming television signals as MPEG-2 streams and store them to disk for later viewing. As the TiVo runs Linux and contains only a 66 MHz processor, it could easily be replaced by a PC with an MPEG-2 encoder board3 provided that the PC were able to reserve sufficient processing (and memory and disk) resources to avoid dropping frames while encoding and decoding video. In many ways this application is a perfect motivation for soft real-time services on general-purpose operating systems because reliable real-time processing is required concurrently with, and at random times with respect to, normal PC usage. A software answering machine has similar characteristics.
Distributed live audio and video: Video conferencing and telepresence applications have a tight end-to-end latency requirement that precludes deep buffering--frames must be displayed very shortly after they are received. Network delays will cause frames to arrive in a bursty manner; this has lead to approaches such as rate-based scheduling [33].
Real-time audio: Synthesizing and mixing sounds in real-time using a PC is particularly challenging and requires end-to-end latency of not more than around 20 ms if the PC is to be used as a monitor as well as a recording device [69] (that is, if the sound is to be perceived as being simultaneous with the act of playing it). In professional situations this application is closer to hard than soft real-time because the cost of a dropped sample during a recording session may be large. Since highly reliable fine-grained (small millisecond) real-time is barely within reach of modern general-purpose OSs, this space is currently dominated by dedicated hardware solutions such as Pro Tools from Digidesign and Paris from E-MU/Ensoniq.
The rendering loop in immersive 3D environments and games such as Doom and Quake must display frames that depend on user input with as little delay as possible in order to be convincing and avoid inducing motion sickness. Rendering loops are usually adaptive, using extra CPU cycles to provide as many frames per second as possible, up to the screen refresh rate. These loops are usually CPU-bound since application programmers tend to make virtual environments more complex whenever the hardware appears to be getting to be fast enough.
Running other applications (real-time or not) concurrently with a free-running simulation is a matter of breaking up the time not available to the simulation into chunks small enough that individual frames are not delayed enough to degrade the user experience. For example, if 33 frames/second is an acceptable frame-rate for Quake on a platform that can provide 66 frames/second, then we would expect to be able to run applications other than Quake for 15 ms out of every 30 ms; this could be achieved by giving Quake a reservation of 15 ms / 30 ms and letting other applications use the unreserved time.
The high average-case performance of modern processors and the low profit margins in the PC industry create a powerful incentive for peripheral designers to push functionality into software. For example, software modems contain a bare minimum of hardware support, performing all signal processing tasks in software. This requires code to be reliably scheduled every 3-16 ms [46]; missed deadlines reduce throughput and may cause the connection to drop.
Since the reliable scheduling of threads at granularities of 3-10 ms is barely within the capabilities of most general-purpose operating systems, there is motivation to run soft modem code in a kernel routine (bottom-half handler in Unix or DPC in Windows) or worse, in an interrupt handler. This is “worse” in the sense that because it is usually not possible to enforce a bound on the amount of processor time given to such kernel routines, they become a source of unscheduled time for other applications. In other words, running latency-sensitive code in an interrupt or other kernel context is really only a good idea when the system designers know a priori that there are no other real-time tasks. Jones and Saroiu [41] describe the process of moving software modem driver code into thread context in Windows 2000, with the goal of allowing other real-time applications to coexist with the software modem.
USB speakers move the D/A conversion from the sound card to the speakers themselves, which receive a small sound packet from the USB controller every 1 ms. The USB controller has very little buffering, and will cause an audible skip in the played sound if data is not written to hardware for more than about 20 ms.
A trend opposing the migration of functionality into software is the decreasing size and cost of embedded computers; this makes it inexpensive to perform real-time tasks on special-purpose hardware instead of on general-purpose operating systems. However, the low cost of downloading a software module (compared to acquiring a new embedded device) ensures that users will want to perform real-time tasks on PCs during the foreseeable future. Furthermore, we believe that PCs will continue to have abundant resources compared to special-purpose devices, although PCs often lack dedicated hardware that enables some kinds of tasks to be performed much more easily.
In Section 2.2 we presented several requirements that a good multimedia OS should fulfill; in this section we refocus those requirements into a set of research challenges.
C1: Create user-centric systems. Users tell the system how to provide high value--they start up a set of applications and expect them to work. Resource management systems should respect a user’s preferences when tradeoffs need to be made between applications, and should seek to maximize the utility of the system as perceived by the user. User studies are needed in order to figure out how admission control and adaptation can be used in ways that are intuitive and minimally inconvenient to users.
C2: Create usable programming models. In addition to the usual questions about how effective, novel, and efficient a scheduler is, we believe that the systems research community should be asking:
C3: Provide scheduling support for applications with diverse requirements. We believe that multimedia systems should support at least three types of scheduling: (1) guaranteed rate and granularity scheduling for real-time applications that do not degrade gracefully, (2) best-effort real-time scheduling for real-time applications that degrade gracefully, and (3) time-sharing support for non-real-time applications.
This chapter has provided a framework by which the differing goals of many of the multimedia schedulers in research and production operating systems might be compared and evaluated. It has also shown that the multimedia and other soft real-time applications have different requirements that would be difficult to meet with a single real-time scheduling policy; this motivates the flexible and diverse scheduling that HLS enables.