Visual RTQT

Installing the Tcl Plugin

In order to run Visual RTQT, you will need to download and install the tcl/tk plug-in from Scriptics.

Real-Time Queueing Theory

Queueing theory and queueing network theory are methodologies which are widely used in the analysis of the performance of computer and communication systems. In spite of the many successes of these methods, they have not been applied with much success to real-time systems. Real-time systems are characterized by the tasks using the system having explicit timing requirements, such as hard deadlines. The performance metrics include the ability of the system to meet those task timing requirements (e.g. ensuring that the fraction of tasks which are late is kept within a limit). Traditional queueing theory methods do not focus on whether individual tasks meet their individual timing requirement. Real-time queueing theory is a new methodology designed to analyze the performance of real-time systems, using real-time system performance metrics.

To track the performance of real-time systems and to implement certain real-time system scheduling policies such as earliest deadline first (edf), one must keep track of the lead-time (time until deadline elapses) for each task in the system. Real-time queueing models are difficult to work with mathematically since the system state is of unbounded dimension. Standard methods used in queueing theory cannot deal with this unbounded dimensionality problem.

To analyze real-time queueing models, we turn to heavy traffic queueing theory, a relatively new collection of methods and results which study the behavior of queueing systems when the traffic intensity approaches 1. These heavy traffic conditions are the most important case for real-time systems. If we can predict and control behavior in heavy traffic, then the behavior in light or moderate conditions will be under control as well.

The commonly used queueing processes such as the queue length process or the workload process may be difficult to characterize exactly under fairly general assumptions. However, in heavy traffic, these centered and scaled versions of these quantities converge to drifted and reflected Brownian motion. This limiting stochastic process is well understood, and most any performance characteristic can be computed directly using facts about Brownian motion.

In heavy traffic, not only do the standard queueing characteristics have well-defined behavior, the lead-time profiles also converge to well-defined forms. These forms depend upon three major factors: (1) the number of tasks currently in the system, (2) the scheduling policy being used (including edf, FIFO and processor sharing scheduling policies) and (3) the initial deadline probability distribution of the arriving tasks.

The theoretical lead-time profiles shown in the Real-Time Queueing Demonstration can be thought of as expected values. The actual empirical profiles will exhibit variability. Confidence limits will be given for the profiles, and the profiles become more and more exact as the number of tasks in the queue increases - the effect of central limit theorem behavior. The results have been generalized to some simple queueing networks, and this will eventually be incorporated into the demonstration.

Visual RTQT

The Visual RTQT applet below shows a simulated process against predicted theoretical lead-time curves. A single queue is assumed with a single source of customer events and a single server. The simulation is controlled using the sliders and buttons on the left-hand side of the applet.

Visual RTQT supports three queueing disciplines. In the EDF (Earliest Deadline First) discipline, the task with the earliest deadline is always serviced first irregardless of the order in which the tasks arrive. In the Processor Sharing discipline, work is distributed equally among the tasks in the queue and the next task to exit is the next task finishing its processing. Finally, in the traditional FIFO (First-In First-Out) discipline, tasks exit in the order in which they arrived. Note that when switching from either the Processor Sharing or FIFO discipline to the EDF discipline, any tasks already in the queue are sorted based on the task deadlines. This means that if the queueing discipline is switched to EDF and then immediately back to the original queueing discipline, the original order of tasks in the queue will be lost.

Distributions for the service time, the customer arrival time and the deadline are set with the button/slider combinations below the queueing discipline select buttons. Each can each be set to one of: uniform, constant or exponential. In the uniform case, time/deadline values are uniformly distributed between zero and the value shown on the slider. In the constant case, the time/deadline values are exactly the value shown on the slider. Finally, in the exponential case time/deadline values are exponentially distributed with the mean value shown on the slider.

The current simulation time is shown on the clock icon. A one twelfth rotation of the long hand corresponds to one simulation time unit (the same units as is displayed in the lead-time graphs). The simulation speed is controlled by the "Simulation Speed" slider, the "Step Type" and the "Pause"/"Single Step" buttons. When the step type is "smooth", the simulation will progress in scaled real time with delay between event updates scaled by the simulation time between events. When the step type is "jump", the real time time between events depends only on the setting of the simulation speed slider. To single step through a simulation, first press the "Pause" button. Then each time the "Single Step" button is pressed, the simulation will advance one event (exit or arrival) and the exact time and type of event will be displayed on the status bar at the bottom of the display. The "Reset" button can be used to restart the simulation and clear any accumulated statistics.

The CDF of the lead-time for tasks in the queue is shown in the upper graph on the right-hand side of the display. The black dots represent individual tasks in queue sorted by lead-time, and the blue curve represents the value predicted by real-time queueing theory. A single task in the queue is highlighted with a red dot. When the highlighted task leaves the queue, the next incoming task will become the new highlighted task. When the simulator is in single step mode, a red "X" will be used to mark the position of exiting tasks, and a green circle will be used to mark arriving tasks. The scale on X-axis can be set dynamically using the slider above the graph.

The pdf of the lead-time for tasks on queue exit is shown as a bar graph in the lower right portion of the display. The bars are accumulating showing the distribution since the last time the "Reset" button was pressed, so if any changes to the queueing policy or customer/service/deadline distributions when made, it is necessary to press "Reset" to get a clean curve. Green bars are displayed for tasks which were serviced before thier deadline, and red bars for tasks which were serviced late. For some combinations of distribution parameters, a predicted lead-time curve is shown in blue, but in general a substantial amount of simulation time is required before the simulated curve will begin to approach the predicted curve.



References

*Lehoczky, J.P.
"Real-time queueing theory"
Proceedings Real-Time Systems Symposium, Dec. 1996, 186-195.
*Lehoczky, J.P.
"Real-time queueing network theory"
Proceedings Real-Time Systems Symposium, December 1997, 58-67.
*Lehoczky, J.P.
"Using real-time queueing theory to control lateness in real-time systems"
Performance Evaluation Review, 25(1), 1997, 158-168.
*Lehoczky, J.P.
"Scheduling communication networks carrying real-time traffic"
Proceedings Real-Time Systems Symposium, December 1998, 470-479.
*Doytchinov, B., Lehoczky, J.P. and Shreve, S.
"Real-time queues in heavy traffic with earliest-deadline-first queue discipline"
Research Report No. 99-CNA-016, Center for Nonlinear Analysis, Carnegie Mellon Univ., August, 1999.

Support

Real-Time Queueing Theory is supported in part by the Office of Naval Research under contract N00014-92-J-1524, and by the Defense Advanced Research Projects Agency under contracts F30602-96-1-0160 and N66001-97-C-8527.
Jeffery Hansen
Last modified: Tue Mar 14 20:18:59 EST 2000