Just How Bad is the FIFO Discipline for Handling Randomly Arriving Time-Critical Messages ?

摘要

This paper proposes an evaluation of the deadline miss probability for randomly arriving real-time tasks (messages), as a function of their individual deadline constraints and the overall system (network) load. The goal of this study consists in providing upper-bounds for load level and time constraints for servicing, by using the FIFO (First-In-First-Out) scheduling discipline, soft real-time tasks with an acceptable deadline miss probability. Technically speaking, we have derived closed-form formulas for M/M/1 and M/D/1 queues to evaluate the miss probability. The formula for M/M/1 is a simple application of the Pollaczek-Khinchin formula for M/G/1 queues. The formula for M/D/1 is obtained by solving a recurrent differential equation, the latter is obtained from Takacs's integrod-ifferential equation for unfinished work. Simulation results are in very good convergence with the theoretical predictions made by our formulas. The latter suggests that FIFO, which is the simplest and the most used scheduling discipline, can still be effectively suitable for many soft real-time applications. The evaluation we propose thus helps to make a tradeoff between the desired QoS (Quality-of-Service) and the implementation complexity.