PUB - Publikationen an der Universität Bielefeld

Barabasi has shown that the priority-based scheduling rules in single-stage queuing systems (QS) generate fat tail behavior for the task waiting time distributions (WTD). These fat tails are induced by the waiting times of very low priority tasks that stay unserved almost forever as the task priority indices are "frozen in time" (i.e., a task priority is assigned once for all to each incoming task). Here, we study the new dynamic behavior expected when the priority of each incoming task is time-dependent (i.e., "aging mechanisms" are allowed). For two classes of models, namely a population-type model with an age structure and a QS with deadlines assigned to the incoming tasks, which is operated under the "earliest-deadline-first" policy, we are able to extract analytically some relevant characteristics of the task waiting time distribution. As the aging mechanism ultimately assigns high priority to any long waiting tasks, fat tails in the WTD cannot find their origin in the scheduling rule alone, thus showing a fundamental difference between our approach and Barabasi's class of models.