Aperiodic response time distributions in queues with deadline guarantees for periodic tasks

We find response time distributions for aperiodic tasks that queue for the same server with periodic tasks for which deadlines are guaranteed. The periodic task stream is a sequence of tasks with constant time between adjacent periodic arrivals and constant service times. The periodic tasks have deadlines which are times by which each task must have completed service. Deadlines are equal to the arrival time of the next periodic task. Tasks with deadlines are called hard real-time tasks. The aperiodic task stream is a sequence of tasks with the time between arrivals drawn from an exponential distribution. The service time of each aperiodic task is also drawn from an exponential distribution. Aperiodic tasks are served in fifo order from within the aperiodic stream. The server will preempt the execution of aperiodic tasks to serve periodic tasks and guarantee that every periodic task meets its deadline. We study two different aperiodic service disciplines called background aperiodic service (BGA) and foreground aperiodic service (FGA). BGA, also known as preemptive fixed-priority scheduling, assigns high priority to periodic tasks and low priority to aperiodic tasks. In BGA, any aperiodic tasks in service at the time of a periodic task arrival will be preempted so periodic task execution can begin immediately. FGA, a special case of the slack stealer, assigns aperiodic tasks the highest priority whenever delaying the execution of a periodic task will not result in its deadline being missed. We develop a collection of aperiodic response time distributions. The response times are analyzed separately based on the service discipline (e.g. foreground or background). Within each service discipline, several analytic models are identified, adapted, and/or derived to characterize the response time distribution of the aperiodic task stream. In some cases, the aperiodic system size distribution is also identified or derived. Criteria for model selection is shown to depend on specified and/or observed values of the system configuration (e.g. periodic interarrival and compute times, aperiodic interarrival and service rates, mean blocking time of aperiodics by periodics, etc.). All models and criteria are validated with simulation data.