Visual RTQT

Real-Time Queueing Theory

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

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.

Lehoczky, J.P.

Lehoczky, J.P.

Lehoczky, J.P.

Doytchinov, B., Lehoczky, J.P. and Shreve, S.