Variable Rate Resource Allocation for

Mixed Real-Time/Non-Real-Time Systems

Steve Goddard

Computer Science & Engineering
University of Nebraska - Lincoln
Lincoln, NE 68588-0115
goddard@cse.unl.edu

Introduction. Mixed systems combine two traditionally separate domains of computing: real-time and non-real-time. Real-time systems respond to external events within a bounded interval of time (timeliness), and are often classified as hard real-time or soft real-time. Hard real-time systems require a guarantee that all processing is completed within a given time constraint every time. A late response may result in catastrophic consequences. Thus, timeliness is a primary measure of correctness in a real-time system. Common examples of hard real-time systems include nuclear power plants, avionics control systems, embedded braking systems for automobiles or trains, and signal processing systems employed by the Department of Defense. Soft real-time systems have a less rigorous notion of temporal correctness and the consequences of a late response are not catastrophic. Examples of soft real-time systems include telephone switches, on-line transaction systems, and electronic games.

Non-real-time systems also have a notion of temporal correctness, but the response time is very subjective and seldom specified. Most non-real-time systems strive for good average-case performance and tolerate occasional slow response times. Examples of non-real-time systems include desktop computers, workstations, information kiosks, and accounting systems.

There are, of course, many systems that fit somewhere between the broad spectrum of hard real-time systems and non real-time systems. Examples of these systems include video conferencing systems and network servers such as Web Service Providers (WSPs), Application Service Providers (ASPs), and those that support e-commerce. These systems do not have traditional real-time temporal constraints, yet they require better than the best-effort level of service traditionally provided by non-real-time operating systems and networks. In the last 5 years, the term firm real-time has been used to describe applications (such as these) that require deterministic performance but not hard guarantees of performance.

In the future, the traditional lines between real-time and non-real-time will become increasingly blurred. Indeed, these two computing paradigms appear to be converging to the point that application correctness will regularly be evaluated in terms of its functional correctness and its ability to meet certain performance criteria. Such criteria may be a hard response time or a certain number of requests serviced in an interval of time. Computer systems will be expected to support applications that require only best effort level of service as well as those with more deterministic levels of performance. That is, future computer systems will be mixed: required to support hard real-time, firm real-time, and non-real-time applications simultaneously. The following example describes a mixed system of the future and some of the unique problems it will pose.

Example 1. The U.S. Navy is in the process of developing its first 21^st Century Land Attack DD 21 Destroyer—named the USS Zumwalt by President Clinton on July 4, 2000. The USS Zumwalt is scheduled for fleet introduction in 2009, but defense contractors have been working on its design since 1997. In 1998, I was hired as a consultant for the Blue Team competing to win the contract to design and build 32 DD 21-class destroyers. An important goal of the DD 21 project is a 70% reduction in support and manning costs from the DDG 51-class destroyer. One of the strategies for achieving this goal is “Total Ship Computing (TSC)—a commercially based, open-system computing environment distributed shipwide for both tactical and non-tactical use”.

Fully implementing the TSC concept will require workstations to host both real-time and non-real-time applications. Ignoring secure data classification problems, imagine a TSC workstation hosting target acquisition and tracking software, maintenance videos, ship-board video conferencing programs, word processors, and email clients with any number of these being active simultaneously. A significant problem with implementing the TSC concept is efficiently allocating computing resources so that resources not needed by hard real-time applications can be utilized by firm and non-real-time applications. Traditional implementation methods partition the processing so that hard-real-time applications are executed on dedicated hardware. Firm real-time and non-real-time applications are occasionally mixed, but usually even these types of applications are partitioned according to their response time needs. The cost reduction goals of the DD 21 preclude the traditional method of resource allocation based on dedicated hardware, and require the support of mixed systems to better utilize available computing resources.

Approach. Mixed systems will require a new approach to the allocation of resources such as the CPU, network bandwidth, transaction processing (for a network server), and Web pages or CGI requests (for a Web server). Temporal correctness and the rate at which resources are requested must become primary properties of any resource allocation model that attempts to support mixed system. Traditional real-time resource allocation models have always been differentiated from non-real-time resource allocation models in the way they treat temporal correctness. However, traditional real-time scheduling theory uses a very strict rate definition—one based on periodic execution. A much more general form of rate-based resource allocation is needed to support firm and non-real-time applications.

Jeffay and I proposed a rate-based execution (RBE) model for the execution of a real-time process in which timing requirements are specified with an expected (or average) execution rate of x times every y time units. The current RBE model only applies to single-processor, hard real-time systems. However, its general notion of an execution rate will provide the foundation for a new variable rate resource allocation model called VRA that supports mixed systems. The VRA model will allow resources to be used more efficiently than resource allocation models available today and can form the foundation for future quality of service middleware frameworks in which applications negotiate their rate of service.