The application scenarios in this chapter present complex but plausible combinations of applications that expose weaknesses of current scheduling techniques and motivate flexible scheduling in general-purpose operating systems. It is essential to look at mixes of real applications since the subtleties of real applications, their requirements, and the ways that they are used have a large impact on whether or not a particular method of scheduling them is workable or not. Chapter 7 shows how each of the scheduling challenges in the application scenarios can be solved using hierarchical scheduling.
The first application scenario involves a workstation that is being used to provide several virtual servers. A virtual server is a portion of a physical server that appears, at some level, to be a dedicated server. For example, virtual web servers for the domains foo.com and bar.org could reside on the same physical server.
Most web servers are designed to provide as much throughput as possible, rather than providing bounded delay to clients. Implementing virtual servers requires hierarchical load isolation to provide guaranteed performance to each server regardless of the CPU utilization of other virtual servers running on the same machine. For example, if foo.com runs many CPU-intensive database queries, this should not affect the level of service offered to bar.org’s users. Furthermore, virtual servers may want to subdivide resources internally in order to accommodate different classes of users, or to avoid have CPU-intensive dynamic web pages interfere with the timely serving of static content.
The scheduler for a virtual server must provide hierarchical load isolation and achieve high overall throughput on a multiprocessor machine.
The second application scenario is a fast personal computer that belongs to a sophisticated user.
We characterize each part of the workload for this machine along two axes: foreground and background, and real-time and non-real-time. The distinction between foreground and background applications is important because although a personal computer is usually used for only one foreground application at a time, it may be used for many background tasks at once. This means that if real-time applications all fall into the foreground category, then there is little or no real need for sophisticated real-time scheduling since threads in the single real-time application can be run at high priority, eliminating contention with other applications. However, as we will see, this is not the case.
The foreground, non-real-time workload consists mainly of traditional interactive applications such as a web browser, a spreadsheet, an email application, and a word processor. Usually, all of these applications will be blocked waiting for user input, but they occasionally require bursts of CPU time.
The background, non-real-time workload consists of jobs such as: printing a document, converting the contents of a music CD into a compressed digital music format, downloading files, indexing the contents of the hard drive, and serving files to other computers over a home network.
The foreground, real-time workload for a home computer includes jobs such as playing computer games and playing stored digital video from a digital video camera, from the network, or from a DVD.
Background, real-time tasks potentially include playing music, mixing application-generated sound streams together and performing associated signal processing (to adjust the relative volumes of different streams, for example) before delivering audio buffers to sound hardware, performing voice recognition to provide input for another application such as a spreadsheet or a game, recording a television show as MPEG-2 video using a television interface card, running a software modem, burning a CD-ROM, and (eventually) using computer vision software to determine where the user is looking based on the output of a camera mounted on the monitor.
To successfully support the workload on a home computer, the scheduler must meet the scheduling requirements of any one foreground application in addition to any combination of background applications that does not overload the processor (most home computers have only a single processor).
The non-real-time workload for a home computer, both foreground and background, can be scheduled by a traditional time sharing scheduler, which was specifically designed to disambiguate interactive and batch applications, preferentially scheduling interactive applications in order to keep them responsive to user input. In a hierarchical environment, the time-sharing scheduler should receive a reserved fraction of the CPU, and should not be starved for more than about 100 ms, in order to keep interactive applications, administrative applications, and the windowing system responsive to user input. As Nieh et al. [66] observe, it is particularly important that the user interface not be starved--if it is, the user will be unable to kill the application that is causing the starvation.
The requirements of the real-time workload vary. Some applications, such as the CD burner, the software modem, the music player, and the video recorder provide little or no value if their full requirements are not met. Consequently, they should receive a reserved fraction of the CPU. Other applications such as voice recognition and vision need to be scheduled often, but do not necessarily require a reserved fraction of the processor since they continue to function correctly when they receive too little CPU time (albeit with increased delay). A third class of applications such as playing stored video and playing a game may fall into either category depending on the preferences of the user--their performance degrades gracefully, but the user may not consider any degradation to be acceptable.
A minimum share of the CPU must be reserved for CPU-bound real-time applications such as games or immersive 3-D environments. In the absence of real-time scheduling, there is no good assignment of priorities that allows these applications to make progress at the desired rate while also allowing background activity to take place on the machine. For example, if a priority-based scheduler is used to run the CPU-bound task at a higher priority than background applications, the background work will be completely starved. If the CPU-bound task is at the same priority as the background work, it will not receive processor cycles in a timely way since time-sharing schedulers enforce fairness between CPU-bound applications only in a coarse-grained manner. If the CPU-bound task runs at a lower priority than background work, it will be starved until the background work completes.
A final scheduling challenge for the home machine is to isolate the CPU utilization of untrusted applications, or of applications such as a Java virtual machine that runs untrusted applications. Isolating these applications prevents them from unfairly using more than their share of the CPU, no matter how many threads they create.
The third application scenario involves a powerful computer (for example, a 4-processor server with several network interfaces, running Linux or Windows 2000). This machine supports several dozen users running thin clients. Thin clients are the modern equivalent of dumb terminals--they run a dedicated operating system that sends user input (from the keyboard and mouse) to the terminal server, and updates the display in response to commands coming from the server. All applications run on the server, which means that the client need not have a disk, much memory, or much processing power. This kind of system has advantages over giving each user a full-fledged desktop computer: system administration tasks such as software upgrades and security auditing can be centralized, and hardware is used more efficiently since a powerful machine is statistically multiplexed among many users whose peak resource requirements will not often coincide.
The workload for the terminal server is a subset of the applications run on a home computer, but multiplied by several dozen simultaneous users. Users run interactive applications, processor-intensive background jobs with no latency requirements, and real-time tasks such as playing audio and video. Demanding real-time tasks like voice recognition may be performed, but are less likely when each user does not have a processor to herself.
The terminal server must support multiple simultaneous non-real-time foreground and background applications. Again, a standard time sharing scheduler can accomplish this. The terminal server must also support a potentially large number of concurrent real-time tasks, and it must ensure fair scheduling across different users regardless of the number of threads each user creates. Furthermore, hierarchical load isolation may be required at other levels. For example, a development group may have large aggregate processing needs due to compilation of large jobs; it may be desirable to isolate them from non-development workers.
Users have managed to use general-purpose operating systems for a long time without having access to specially tailored schedulers. It is worth examining techniques that have evolved to cope with the inflexible schedulers in GPOSs, in order to understand the benefits of flexible scheduling. Methods of coping include:
The common theme among all of these solutions is that, at least in some situations, they have an associated cost. For example, when a machine is used to run only one real-time application at a time, the cost is the lost opportunity to run other real-time applications. When extra hardware is purchased to provide physical load isolation, the cost is the price of the equipment in addition to any extra administrative costs.
Hierarchical scheduling can give a general-purpose operating system the flexibility that is required to provide scheduling behaviors and implement scheduling policies that make most or all of the workarounds listed above unnecessary.