Using real-time queueing theory to control lateness in real-time systems
Using real-time queueing theory to control lateness in real-time systems
复制标题
使用实时排队理论来控制实时系统中的延迟
DOI：
10.1145/258612.258685
复制
发表时间：
1997
期刊：
影响因子：
1.2
通讯作者：
J. Lehoczky
中科院分区：
文献类型：
--
作者：
J. Lehoczky
本文介绍了实时排队理论，这是一种新理论，嵌入了实时调度理论确定任务定时要求是否满足排队模型的背景的能力。具体而言，本文将Lehoczky [9]中开发的分析扩展到GI/M/1情况。本文还将这些模型应用于可以控制客户迟到的队列控制策略。到达客户的截止日期是从一般截止日期分发中得出的。排队系统的状态变量必须包括队列中的数字（根据需要创建Markov模型的补充变量）和每个客户的交货时间（截止时间减去当前时间）；因此，状态空间是无限的维度。一个人可以将系统状态表示为真实线上的度量，并可以通过其傅立叶变换来表示该度量。因此，实时排队系统可以被描述为在傅立叶变换的空间上演变的马尔可夫过程，本文介绍了排队中所有客户的瞬时同时提前时间概况的表征。此轮廓很复杂；但是，在繁重的交通情况下，出现了对交货时间概况的简单描述，即，销售时间轮廓的行为就像是布朗尼运动在傅立叶变换的特定流形上演变而来的。歧管取决于队列学科和客户截止日期分布。与模拟相比，此近似值非常准确。实时排队理论的重点是特定队列纪律满足客户时机要求的很好，并专注于动态而不是系统的平衡行为。因此，它提供了研究控制策略的潜力，以确保客户按时完成截止日期。本文说明了某些队列控制策略的分析和绩效评估。讨论了对更复杂的模型和排队网络的概括。
This paper presents real-time queueing theory, a new theory which embeds the ability of real-time scheduling theory to determine whether task timing requirements are met into the context of queueing models. Specifically, this paper extends the analysis developed in Lehoczky [9] to the GI/M/1 case. The paper also applies these models to study queue control strategies which can control customer lateness. Arriving customers have deadlines drawn from a general deadline distribution. The state variable for the queueing system must include the number in the queue (with supplementary variables as needed to create a Markov model) and the lead-time (deadline minus current time) of each customer; thus the state space is infinite dimensional. One can represent the state of the system as a measure on the real line and can represent that measure by its Fourier transform. Thus, a real-time queueing system can be characterized as a Markov process evolving on the space of Fourier transforms, and this paper presents a characterization of the instantaneous simultaneous lead-time profile of all the customers in the queue. This profile is complicated; however, in the heavy traffic case, a simple description of the lead-time profile emerges, namely that the lead-time profile behaves like a Brownian motion evolving on a particular manifold of Fourier transforms; the manifold depending upon the queue discipline and the customer deadline distributions. This approximation is very accurate when compared with simulations. Real-time queueing theory focuses on how well a particular queue discipline meets customer timing requirements, and focuses on the dynamic rather than the equilibrium behavior of the system. As such, it offers the potential to study control strategies to ensure that customers meet their deadlines. This paper illustrates the analysis and performance evaluation for certain queue control strategies. Generalizations to more complicated models and to queueing networks are discussed.