Validating Timing Constraints

in Multiprocessor and Distributed Real-Time Systems ?

Rhan Ha and Jane W. S. Liu

frhanha, janeliug@cs.uiuc.edu

Department of Computer Science

University of Illinois

Urbana, Illinois 61801

Abstract

In multiprocessor and distributed real-time systems, scheduling jobs dynamically on processors is likely to achieve better performance. However, analytical and efficient validation methods to determine whether all the timing constraints are met do not exist for systems using modern dynamic scheduling strategies, and exhaustive simulation and testing are unreliable and expensive. This paper describes several worst-case bounds and efficient algorithms for validating systems in which jobs have arbitrary timing constraints and variable execution times and are scheduled on processors dynamically in a priority-driven manner. The special cases of the validation problem considered here are concerned with independent jobs that are (1) preemptable and migratable, or (2) preemptable and nonmigratable, or (3) nonpreemptable.

1 Introduction

In recent years, many real-time load balancing and scheduling algorithms that dynamically dispatch and schedule jobs on processors have been developed. Examples include algorithms described in [1-3]. These algorithms are likely to make better use of the processors and achieve a higher responsiveness than the traditional approach to scheduling real-time jobs in multiprocessor and distributed environments. According to the traditional approach, jobs are first statically assigned and bound to processors, and then a uniprocessor scheduling algorithm is used to schedule the jobs on each processor [4-9]. Here, the term job refers to a basic unit of work to be scheduled. A job may be the formatting of a text file, the processing of a query, the transmission of a message, etc. To execute, it requires a CPU, a database server, or a data link, respectively; they are all modelled abstractly as pro-

?This work has been partially supported by ONR Contract Nos. N00014-89-J-1181 and N000-92-J-1815 and NASA Grant No. NAG 1-1613.

cessors. (In queuing theory literature, a processor is called a server.) A real-time job Ji has a release time ri and a deadline di. The release time is the point in time after which the job can begin execution whenever its constraints due to data and control dependencies are met. The deadline is the point in time by which the job is required to complete. We say that a job meets its timing constraint if it executes only at or after its release time and completes by its deadline.

The validation of a system containing real-time jobs involves validating not only that the results produced by all jobs are functionally correct but also that all jobs meet their timing constraints. By statically binding jobs to processors, the traditional approach allows timing constraints to be validated using analytical methods or by efficient algorithms [4, 10]. In contrast, such validation methods do not exist for systems using modern dynamic scheduling strategies, and exhaustive simulation and testing are unreliable and expensive. Until reliable and efficient validation methods become available, the modern approaches to scheduling can not be used in real-life, safety-critical systems.

To illustrate the difficulties we are likely to encounter, we consider a replicated database system. Time-critical queries arriving at the communication server are queued and dispatched to identical database servers in a greedy manner in an attempt to produce all responses on time. Specifically, in the simple system shown in Figure 1, there are two database servers; they are modelled abstractly as processors P1 and P2. There are 6 queries; each is a job. These jobs are independent, that is, they can execute in any order. Jobs are assigned priorities, and those ready for execution are placed in a common queue ordered by their priorities. Scheduling decisions are made when jobs are released and completed. At each scheduling decision time, the priority of the job at the head of the queue is compared with the priorities of the jobs executing on the processors. If the priority of the job is higher