这是用户在 2025-5-6 19:54 为 https://app.immersivetranslate.com/pdf-pro/uploading/ 保存的双语快照页面，由 沉浸式翻译 提供双语支持。了解如何保存？


FCFS 和改进 FCFS 的性能分析 动态实时调度算法 计算机系统 1 1 ^(1){ }^{1}

魏赵
计算机科学系阿德莱德大学阿德莱德，南澳大利亚州 5001澳大利亚

约翰·A·斯坦科维奇
计算机与信息科学系
马萨诸塞大学阿默斯特，马萨诸塞州 01003美国

摘要


我们研究了 FCFS 和改进的 FCFS 调度算法在动态实时计算机系统中的性能，在这些系统中，任务以随机过程到达，每个任务都有一个松弛度，指定任务可以等待服务的最长时间。我们获得了使用 FCFS 或改进的 FCFS 调度算法的 M / M / 1 M / M / 1 M//M//1M / M / 1 系统的通用解。特别是，推导出了 M / M / 1 + M M / M / 1 + M M//M//1+MM / M / 1+M 系统的未完成工作分布、任务丢失率和 CPU 利用率的显式表达式。 M / M / 1 + M M / M / 1 + M M//M//1+M\mathrm{M} / \mathrm{M} / 1+\mathrm{M} 中的最后一个 M 表示任务松弛度呈指数分布。我们表明，这些系统的稳态性能不仅取决于提供的负载 ρ ρ rho\rho （如在非实时领域中），还取决于归一化平均松弛度，即平均松弛度除以平均服务时间。我们的分析还表明，使用我们改进的 FCFS 调度算法比使用原始 FCFS 算法在性能上有显著提升。并且在许多情况下，改进的 FCFS 与已被证明是最优的最小松弛度优先（MLF）算法的性能几乎相同或非常相似。 改进的 FCFS 算法的优点是它需要 O ( 1 ) O ( 1 ) O(1)\mathrm{O}(1) 时间，而 MLF 算法需要 O ( lg ⁡ ( n ) ) O ( lg ⁡ ( n ) ) O(lg(n))\mathrm{O}(\lg (\mathrm{n})) 时间。

1 引言


在过去的几年里，人们对实时计算机系统的设计和分析的兴趣日益增加。新的、复杂的应用正在被构想，例如，空间站、执行海底探测的移动机器人团队，以及将专家系统集成到嵌入式实时应用中，如航空电子设备和过程控制。不幸的是，当前许多实时系统的设计和分析是以临时性的方式进行的。需要新的技术来处理这些新应用。在这方面，许多研究人员现在正试图为实时系统的设计和分析建立一个坚实的科学基础[20]。特别是，实时系统的数学分析一直相当有限。本文扩展了数学分析领域的最新技术水平。

实时计算系统的研究，我们认为，以微小但重要的方式，为这一研究领域奠定了坚实的科学基础。当前技术水平仍远未达到对上述新应用的时间特性进行数学分析的程度。

广泛的系统属于实时计算分类。在本文中，我们关注的是动态实时系统。动态实时计算机系统是指任务在随机时间到达（被调用），并且这些任务具有相关的时间约束。时间约束有多种形式。最常见的两种时间约束类型是：松弛度，它指定任务在执行前可以等待的最大时间；以及截止时间，它定义任务执行必须完成的最新时间。当任务到达时，我们假设一个在线调度算法动态地确定时间约束是否可以得到满足。如果是，任务被接受，否则，任务被丢弃，或者我们说，它丢失了 2 2 ^(2){ }^{2}。

需要注意的是，采用这种调度策略，队列中的所有任务都已确保能够在其截止时间前完成。这种保证概念对于实时计算有许多显著优势，包括：能够在任务截止时间到期之前识别出任务将错过其截止时间，以便采取适当的响应措施，并提高可预测性，例如，始终知道队列中的所有任务都可靠地确保能够在其截止时间前完成。保证概念最早在 Spring 项目中引入。关于保证概念实用性的进一步讨论，请参见 [ 17 , 19 , 24 ] [ 17 , 19 , 24 ] [17,19,24][17,19,24] 。

在本论文中，我们研究了动态实时计算机系统调度算法的性能，其中每个任务的时间约束被表征为松弛度，且 CPU 资源是唯一的可调度资源。当其他资源，如数据结构、文件、缓冲区、端口等也必须被调度时，则需要更复杂的技术，而这种调度不利于数学分析。参见 [ 24 , 18 ] [ 24 , 18 ] [24,18][24,18] ，了解在调度实时任务时考虑一般资源需求的启发式方法及其分析。

系统性能的主要指标是 1）任务丢失的百分比，我们将其表示为 R R RR ，以及 2）

cpu 利用率，我们将其表示为 U U UU 。在设计此类实时系统的关键问题之一是选择一个合适的调度算法，以便在正常操作条件和临时过载情况下都能最小化任务丢失。许多实际的实时系统会经历突发到达，重要的是调度算法在这些所有条件下都能尽可能好地工作，而不仅仅是在正常负载下。因此，在本文中，我们研究了从欠载到严重过载的广泛负载范围。此外，由于调度算法是用于在线的，它必须是计算高效且可预测的。也就是说，强烈倾向于使用一个执行速度快但在最坏情况下时间恒定的调度算法，而不是一个执行时间取决于队列长度的算法。

为了描述我们分析所涉及的系统配置，我们使用以下扩展形式的 Kendall 符号 A / B / m + L + S A / B / m + L + S A//B//m+L+SA / B / m+L+S 。A 描述到达过程， B B BB 描述服务时间需求， m m mm 是服务器的数量。这些与原始 Kendall 符号的含义相同。L 代表任务松弛度的分布函数， S S SS 代表系统使用的调度算法。

莫克和德图佐斯[13]表明，最小松弛度优先（MLF）调度算法在某种意义上是最佳的，即如果任何其他算法可以调度一组任务，它也可以做到 3 3 ^(3){ }^{3} 。潘瓦尔、托斯利和沃尔夫 [ 15 , 16 ] [ 15 , 16 ] [15,16][15,16] 表明，最小松弛度算法最小化了任务丢失。然而，MLF 的缺点是它有 O ( lg ⁡ ( n ) ) O ( lg ⁡ ( n ) ) O(lg(n))O(\lg (n)) 的开销，其中 n n nn 是队列长度 4 4 ^(4){ }^{4} 。也就是说，该算法的在线计算成本取决于系统中当前的队列长度。另一方面，一个常用的调度算法——先来先服务（FCFS）——虽然没有最佳性能，但只有 O ( 1 ) O ( 1 ) O(1)O(1) 的开销，这与当前队列长度无关。我们的目的是展示一个稍加修改的 F C F S F C F S FCFSF C F S 算法性能接近最佳，但成本为 O ( 1 ) O ( 1 ) O(1)O(1) 。

改进版的 FCFS 工作原理如下：当一个任务进入系统时，我们首先尝试将其安排在队列的末尾。如果这次尝试失败，我们再尝试将其安排在队列的倒数第二位。如果成功，我们接着检查被移除的任务是否可以安排在队列的最后一个位置。如果这两个条件都满足，那么新任务被接受，否则

新任务丢失，队列保持其原始形式。显然，在这种调度方案下，任务比在 FCFS 方案中多了一次被调度的机会。然而，调度开销仍然是 O ( 1 ) O ( 1 ) O(1)\mathrm{O}(1) 。我们称这种新方案为改进的先来先服务（FCFSI）算法。在本文中，我们展示了这一非常简单的修改带来了显著的性能提升。

在运筹学和排队论文献中，我们在这项研究中关注的问题被称为具有不耐烦顾客的排队问题。该领域已经有很多研究，但在这里我们仅限于涉及实时计算的那部分工作。Palm 解决了 M / M / 1 + M + F C F S M / M / 1 + M + F C F S M//M//1+M+FCFSM / M / 1+M+F C F S 系统[14]，而 Haugen 和 Skogan 推导了 M / M / m + M + F C F S M / M / m + M + F C F S M//M//m+M+FCFSM / M / m+M+F C F S 系统的等待时间分布[7]。Barrer 研究了 M / M / 1 + D + M / M / 1 + D + M//M//1+D+M / M / 1+D+ 随机[3]和 M / M / 1 + D + F C F S [ 4 ] M / M / 1 + D + F C F S [ 4 ] M//M//1+D+FCFS[4]M / M / 1+D+F C F S[4] 系统。 G I / G / 1 + G + F C F S G I / G / 1 + G + F C F S GI//G//1+G+FCFSG I / G / 1+G+F C F S 模型的理论处理在 [ 21 , 1 , 2 ] [ 21 , 1 , 2 ] [21,1,2][21,1,2] 中进行。文献[21]中的结果包括与 Little 公式 L = λ W L = λ W L=lambda WL=\lambda W 类似的关系。在[1,2]中讨论了稳定性条件以及实际等待时间与虚拟等待时间分布之间的关系。在[6]中，Gnedeko 和 Kovalenko 为 M / M / m + D + F C F S M / M / m + D + F C F S M//M//m+D+FCFSM / M / m+D+F C F S 和 M / M / m + M + F C F S M / M / m + M + F C F S M//M//m+M+FCFSM / M / m+M+F C F S 获得了类似的结果。Gavish 等人[5]研究了一个不同的 M / M / 1 + F C F S M / M / 1 + F C F S M//M//1+FCFSM / M / 1+F C F S 模型，其中顾客的时间约束被特征化为（常数）截止时间而不是松弛度。最近，Hong、Tan 和 Towsley 研究了 M / M / 1 + M + M L F M / M / 1 + M + M L F M//M//1+M+MLFM / M / 1+M+M L F 和 M / M / 1 + M + E D F [ 8 ] M / M / 1 + M + E D F [ 8 ] M//M//1+M+EDF[8]M / M / 1+M+E D F[8] 的性能界限。Kurose 等人解决了 M / G / 1 + D + F C F S M / G / 1 + D + F C F S M//G//1+D+FCFSM / G / 1+D+F C F S 和 M / G / 1 + D + L C F S M / G / 1 + D + L C F S M//G//1+D+LCFSM / G / 1+D+L C F S 模型。

在其中，每个客户具有恒定的松弛度 [ 10 , 11 ] [ 10 , 11 ] [10,11][10,11] ，或者可能具有两种恒定松弛度之一[12]。这些结果也适用于多路访问网络和负载平衡算法的性能分析。Kurose 的工作与之前的工作在另一方面有所不同：它是针对保证调度模型的，而所有其他之前的工作都不是。也就是说，在 Kurose 的工作中，当一个任务到达时，它会立即检查是否能够满足其截止时间。如果可以，它将被添加到队列中。如果不可以，它将被丢弃。这意味着队列中所有任务的执行时间都是已知的。这在实时系统中是合理的。请注意，除了[8]之外的所有这些先前工作都是针对使用 FCFS、LCFS 或 Random 调度算法的系统，这些算法在做出调度决策时不使用时间约束信息。

在进行我们的分析时，我们遵循了[ 10 , 11 , 12 10 , 11 , 12 10,11,1210,11,12 ]中的方法。然而，我们将他们的结果扩展到了任务松弛度可能具有任意分布的情况，并考虑了使用改进的 FCFS 调度算法的情况。因此，我们得到了 M / M / 1 + G + F C F S M / M / 1 + G + F C F S M//M//1+G+FCFSM / M / 1+G+F C F S 和 M / M / 1 + G + F C F S I M / M / 1 + G + F C F S I M//M//1+G+FCFSIM / M / 1+G+F C F S I 系统的通用解决方案。特别是，推导出了 M / M / 1 + M + F C F S M / M / 1 + M + F C F S M//M//1+M+FCFSM / M / 1+M+F C F S 和 M / M / 1 + M + F C F S I M / M / 1 + M + F C F S I M//M//1+M+FCFSIM / M / 1+M+F C F S I 系统的任务丢失和 CPU 利用率的显式表达式。从这一分析中得出的一个有趣观察是，稳态性能不仅取决于提供的负载 ρ ρ rho\rho （如在非实时领域），还取决于归一化平均松弛度，即平均松弛度除以平均服务时间。我们展示了使用 FCFSI 可能会比使用 FCFS 带来显著的性能提升。并且，

在许多情况下，FCFSI 的性能几乎与 MLF 算法相同或非常相似，而 MLF 算法已被证明是最优的。

本文的其余部分组织如下：第 2 节定义了本研究中使用的模型和符号。第 3 节讨论了硬实时系统的两种极端情况（最坏和最好）。这些结果用于界定预期性能的水平，并在全文中绘制在包含数值结果的图表上。在第 4 节中，分析了 M / M / 1 + G + F C F S M / M / 1 + G + F C F S M//M//1+G+FCFSM / M / 1+G+F C F S 系统模型，而在第 5 节中，获得了 M / M / 1 + M + F C F S M / M / 1 + M + F C F S M//M//1+M+FCFSM / M / 1+M+F C F S 的显式解并进行讨论。在第 6 节中，我们使用一种近似方法来分析 M / M / 1 + G + F C F S I M / M / 1 + G + F C F S I M//M//1+G+FCFSIM / M / 1+G+F C F S I 系统。特别是，从近似模型中开发出 M / M / 1 + M + F C F S I M / M / 1 + M + F C F S I M//M//1+M+FCFSIM / M / 1+M+F C F S I 的数值解，并与仿真结果进行比较。通过对 F C F S I F C F S I FCFSIF C F S I 系统分析的近似进行了仿真验证。通过仿真，我们还比较了 FCFS、FCFSI 和 MLF 算法的性能。最后，第 7 节总结了本文的结论。

2 模型与符号


我们考虑一个系统，其中任务到达是一个速率为 λ ( λ > 0 ) λ ( λ > 0 ) lambda(lambda > 0)\lambda(\lambda>0) 的泊松过程，任务的服务时间（即计算时间）服从均值为 1 / μ ( μ > 0 ) 1 / μ ( μ > 0 ) 1//mu(mu > 0)1 / \mu(\mu>0) 的指数分布。每个任务都有一个松弛度，表示其在进入服务前可以等待的最大时间。每个任务的松弛度是一个独立同分布的随机变量，均值为 1 / l ( l > 0 ) 1 / l ( l > 0 ) 1//l(l > 0)1 / l(l>0) 。在本文中，我们假设松弛度分布 L ( x ) L ( x ) L(x)L(x) 具有 L ( 0 ) = 0 L ( 0 ) = 0 L(0)=0L(0)=0 的性质。如果一个任务在到达时，调度器确定其必须等待的时间超过其松弛度才能执行，则该任务将丢失。如果任务丢失，该任务将在到达时被丢弃，因此不会进入队列等待执行。

我们称 ρ = λ / μ ρ = λ / μ rho=lambda//mu\rho=\lambda / \mu 为系统（提供的）负载，称 b = μ / l b = μ / l b=mu//lb=\mu / l 为松弛度的归一化均值。直观地， b b bb 以服务时间均值的单位来衡量松弛度的均值。稍后，我们将看到 ρ ρ rho\rho 和 b b bb 在系统性能中起着重要作用。

让我们定义 F ( w , t ) F ( w , t ) F(w,t)F(w, t) 为在时间 t t tt 时队列中未完成工作（包括正在服务的工作）的分布函数。
F ( w , t ) = P ( at time t , unfinished work < w ) F ( w , t ) = P (  at time  t ,  unfinished work  < w ) F(w,t)=P(" at time "t," unfinished work " < w)F(w, t)=P(\text { at time } t, \text { unfinished work }<w)

定义 F ( w ) F ( w ) F(w)F(w) 为未完成工作的稳态分布。也就是说，
F ( w ) = lim t → ∞ F ( w , t ) F ( w ) = lim t → ∞   F ( w , t ) F(w)=lim_(t rarr oo)F(w,t)F(w)=\lim _{t \rightarrow \infty} F(w, t)

让 f ( w ) f ( w ) f(w)f(w) 成为 F ( w ) F ( w ) F(w)F(w) 的密度函数：
f ( w ) = d F ( w ) d w f ( w ) = d F ( w ) d w f(w)=(dF(w))/(dw)f(w)=\frac{d F(w)}{d w}

使用 F ( w ) F ( w ) F(w)F(w) 和 f ( w ) f ( w ) f(w)f(w) ，我们可以获得感兴趣的绩效指标：CPU 的空闲率等于未完成工作为零的概率，表示为 F ( 0 + ) F 0 + F(0^(+))F\left(0^{+}\right) 。因此，我们有 CPU 利用率为
U = 1 − F ( 0 + ) U = 1 − F 0 + U=1-F(0^(+))U=1-F\left(0^{+}\right)

任务丢失的百分比
R = R + ( 1 − F ( 0 + ) ) R = R + 1 − F 0 + R=R^(+)(1-F(0^(+)))R=R^{+}\left(1-F\left(0^{+}\right)\right)

其中 R + R + R^(+)R^{+} 是在任务到达时 CPU 忙碌的情况下任务丢失的条件概率。乘以 ( 1 − F ( 0 + ) ) 1 − F 0 + (1-F(0^(+)))\left(1-F\left(0^{+}\right)\right) 去除了条件，得到 R R RR 。因此，如果我们能推导出 F ( 0 + ) F 0 + F(0^(+))F\left(0^{+}\right) 和 R + R + R^(+)R^{+} ，那么 U U UU 和 R R RR 也可以获得。另一种计算任务丢失率 R R RR 的方法是
R = ∫ 0 ∞ L ( x ) f ( x ) d x R = ∫ 0 ∞   L ( x ) f ( x ) d x R=int_(0)^(oo)L(x)f(x)dxR=\int_{0}^{\infty} L(x) f(x) d x

其中 L ( x ) f ( x ) d x L ( x ) f ( x ) d x L(x)f(x)dxL(x) f(x) d x 代表任务松弛时间小于 x x xx 的概率，但（在任务到达时）未完成的工作量为 x x xx 。积分考虑了 x x xx 的所有可能值。公式（6）仅适用于 FCFS 系统，但公式（5）没有这一限制。此外，正如我们将看到的，即使对于 FCFS 系统， f ( x ) f ( x ) f(x)f(x) 总是涉及 F ( 0 + ) F 0 + F(0^(+))F\left(0^{+}\right) ，并且 F ( 0 + ) F 0 + F(0^(+))F\left(0^{+}\right) 的计算总是涉及 R + R + R^(+)R^{+} 。因此，使用（5）而不是（6）来计算 R R RR 在计算上更高效。


3 极端情况分析


在本节中，我们分析了一个 M / M / 1 + G M / M / 1 + G M//M//1+GM / M / 1+G 系统的两种极端（最差和最佳）情况。

系统最坏情况发生在每个任务都具有零松弛度时。也就是说，如果一个任务到达时，服务器不空闲，那么该任务就会丢失。在这种情况下，系统变成了一个 M / M / 1 M / M / 1 M//M//1\mathrm{M} / \mathrm{M} / 1 丢失系统，丢失率[9]由以下公式给出
R woret = ρ 1 + ρ R woret  = ρ 1 + ρ R_("woret ")=(rho)/(1+rho)R_{\text {woret }}=\frac{\rho}{1+\rho}

最佳情况是当所有任务的松弛度在极限情况下趋近于无穷大时。在这种情况下，系统性能仅受服务器容量（即 CPU）的限制。因此，如果 ρ < 1 ρ < 1 rho < 1\rho<1 ，
R b e s t = 0 R b e s t = 0 R_(best)=0R_{b e s t}=0
和，如果 ρ ≥ 1 ρ ≥ 1 rho >= 1\rho \geq 1
1 = ρ ( 1 − R b e s t ) 1 = ρ 1 − R b e s t 1=rho(1-R_(best))1=\rho\left(1-R_{b e s t}\right)
即对于 ρ ≥ 1 ρ ≥ 1 rho >= 1\rho \geq 1 ，
R b e a t = 1 − 1 ρ R b e a t = 1 − 1 ρ R_(beat)=1-(1)/(rho)R_{b e a t}=1-\frac{1}{\rho}
注意，对于 ρ ≥ 1 ρ ≥ 1 rho >= 1\rho \geq 1 ，
R w o r a t − R b e s t = 1 ρ ( 1 + ρ ) R w o r a t − R b e s t = 1 ρ ( 1 + ρ ) R_(worat)-R_(best)=(1)/(rho(1+rho))R_{w o r a t}-R_{b e s t}=\frac{1}{\rho(1+\rho)}
因为对于 ρ ≥ 1 ρ ≥ 1 rho >= 1\rho \geq 1 ，
1 2 ρ 2 < 1 ρ ( 1 + ρ ) < 1 ρ 2 1 2 ρ 2 < 1 ρ ( 1 + ρ ) < 1 ρ 2 (1)/(2rho^(2)) < (1)/(rho(1+rho)) < (1)/(rho^(2))\frac{1}{2 \rho^{2}}<\frac{1}{\rho(1+\rho)}<\frac{1}{\rho^{2}}
so
R w o r s t − R b e s t = Θ ( 1 ρ 2 ) R w o r s t − R b e s t = Θ 1 ρ 2 R_(worst)-R_(best)=Theta((1)/(rho^(2)))R_{w o r s t}-R_{b e s t}=\Theta\left(\frac{1}{\rho^{2}}\right)

也就是说，当 ρ → ∞ , R worst − R best → 0 ρ → ∞ , R worst  − R best  → 0 rho rarr oo,R_("worst ")-R_("best ")rarr0\rho \rightarrow \infty, R_{\text {worst }}-R_{\text {best }} \rightarrow 0 与 1 / ρ 2 → 0 1 / ρ 2 → 0 1//rho^(2)rarr01 / \rho^{2} \rightarrow 0 一样快时。图 1 展示了 R worst R worst  R_("worst ")R_{\text {worst }} 和 R best R best  R_("best ")R_{\text {best }} 与系统提供的负载 ρ ρ rho\rho 的关系。从图 1 中，我们看到 R worst R worst  R_("worst ")R_{\text {worst }} 和 R best R best  R_("best ")R_{\text {best }} 在 ρ → ∞ ρ → ∞ rho rarr oo\rho \rightarrow \infty 时趋于一致。实际上，在 ρ = 5 ρ = 5 rho=5\rho=5 之后， R worst R worst  R_("worst ")R_{\text {worst }} 和 R best R best  R_("best ")R_{\text {best }} 之间的差异小于几个百分点。在 ρ = 8 ρ = 8 rho=8\rho=8 之后，差异可以忽略不计。请注意，在实践中，实时系统可能会暂时极度超载。我们这里的观察对于此类实时系统的设计有一定的启示。当系统超载时，任何调度算法在任务丢失率方面的性能几乎相同。设计者或调度控制器（即元级控制器[18]）应选择运行时成本较低的调度算法，而不是选择性能最优或接近最优但运行时成本高的算法。在本文中，我们将分析两种调度算法，FCFS 和 FCFSI，它们都具有极低的运行时成本。

图 1 任务空间边界


4 M / M / 1 + G + F C F S 4 M / M / 1 + G + F C F S 4M//M//1+G+FCFS4 M / M / 1+G+F C F S


按照 [ 22 , 9 , 12 ] [ 22 , 9 , 12 ] [22,9,12][22,9,12] 中的方法，我们可以为 F ( w , t ) ( w > 0 ) F ( w , t ) ( w > 0 ) F(w,t)(w > 0)F(w, t)(w>0) 设置如下方程：
F ( w , t + Δ t ) = ( 1 − λ Δ t ) F ( w + Δ t , t ) + λ Δ t ∫ 0 w ( 1 − L ( x ) ) B ( w − x ) d x F ( x , t ) + λ Δ t ∫ 0 w L ( x ) d x F ( x , t ) F ( w , t + Δ t ) = ( 1 − λ Δ t ) F ( w + Δ t , t ) + λ Δ t ∫ 0 w   ( 1 − L ( x ) ) B ( w − x ) d x F ( x , t ) + λ Δ t ∫ 0 w   L ( x ) d x F ( x , t ) {:[F(w","t+Delta t)=(1-lambda Delta t)F(w+Delta t","t)+],[lambda Delta tint_(0)^(w)(1-L(x))B(w-x)d_(x)F(x","t)+],[lambda Delta tint_(0)^(w)L(x)d_(x)F(x","t)]:}\begin{aligned} F(w, t+\Delta t)= & (1-\lambda \Delta t) F(w+\Delta t, t)+ \\ & \lambda \Delta t \int_{0}^{w}(1-L(x)) B(w-x) d_{x} F(x, t)+ \\ & \lambda \Delta t \int_{0}^{w} L(x) d_{x} F(x, t) \end{aligned}

其中 L ( x ) L ( x ) L(x)L(x) 是任务松弛度分布， B ( x ) B ( x ) B(x)B(x) 是服务时间（计算时间）分布。在上述方程中，左侧是时间 t + Δ t t + Δ t t+Delta tt+\Delta t 时，总未完成工作量小于 w 的概率。右侧第一项是当从时间 t t tt 到 t + Δ t t + Δ t t+Delta tt+\Delta t 没有新到达任务的情况。第二项是当有新任务到达并且任务被调度的情况。最后一项是当新到达的任务无法被调度的情况。

重新排列(14)中的项，并令 Δ t → 0 Δ t → 0 Delta t rarr0\Delta t \rightarrow 0 ，我们得到 Takács 的积分-微分方程对于 F ( w , t ) F ( w , t ) F(w,t)F(w, t) [9] 对于 w > 0 w > 0 w > 0w>0 ：
∂ F ( w , t ) ∂ t − ∂ F ( w , t ) ∂ w = − λ ∫ 0 w ( 1 − L ( x ) ) ( 1 − B ( w − x ) ) d x F ( x , t ) ∂ F ( w , t ) ∂ t − ∂ F ( w , t ) ∂ w = − λ ∫ 0 w   ( 1 − L ( x ) ) ( 1 − B ( w − x ) ) d x F ( x , t ) {:[(del F(w,t))/(del t)-(del F(w,t))/(del w)],[=-lambdaint_(0)^(w)(1-L(x))(1-B(w-x))d_(x)F(x","t)]:}\begin{aligned} \frac{\partial F(w, t)}{\partial t} & -\frac{\partial F(w, t)}{\partial w} \\ & =-\lambda \int_{0}^{w}(1-L(x))(1-B(w-x)) d_{x} F(x, t) \end{aligned}

考虑到当 t → ∞ , ∂ F ( w , t ) ∂ t → 0 t → ∞ , ∂ F ( w , t ) ∂ t → 0 t rarr oo,(del F(w,t))/(del t)rarr0t \rightarrow \infty, \frac{\partial F(w, t)}{\partial t} \rightarrow 0 时，我们得到一个关于 f ( w ) , w > 0 f ( w ) , w > 0 f(w),w > 0f(w), w>0 的方程
f ( w ) = λ ∫ 0 w ( 1 − L ( x ) ) ( 1 − B ( w − x ) ) f ( x ) d x . f ( w ) = λ ∫ 0 w   ( 1 − L ( x ) ) ( 1 − B ( w − x ) ) f ( x ) d x . f(w)=lambdaint_(0)^(w)(1-L(x))(1-B(w-x))f(x)dx.f(w)=\lambda \int_{0}^{w}(1-L(x))(1-B(w-x)) f(x) d x .

我们可以如下求解方程(16)：代入
B ( x ) = 1 − e − μ x B ( x ) = 1 − e − μ x B(x)=1-e^(-mu x)B(x)=1-e^{-\mu x}

代入(16)，并对两边求导，我们得到
d f ( w ) d w = − μ λ ∫ 0 w ( 1 − L ( x ) ) e − μ ( w − x ) f ( x ) d x + λ ( 1 − L ( w ) ) f ( w ) = − μ f ( w ) + λ ( 1 − L ( w ) ) f ( w ) d f ( w ) d w = − μ λ ∫ 0 w   ( 1 − L ( x ) ) e − μ ( w − x ) f ( x ) d x + λ ( 1 − L ( w ) ) f ( w ) = − μ f ( w ) + λ ( 1 − L ( w ) ) f ( w ) {:[(df(w))/(dw)=-mu lambdaint_(0)^(w)(1-L(x))e^(-mu(w-x))f(x)dx],[+lambda(1-L(w))f(w)],[=-mu f(w)+lambda(1-L(w))f(w)]:}\begin{aligned} \frac{d f(w)}{d w}= & -\mu \lambda \int_{0}^{w}(1-L(x)) e^{-\mu(w-x)} f(x) d x \\ & +\lambda(1-L(w)) f(w) \\ = & -\mu f(w)+\lambda(1-L(w)) f(w) \end{aligned}

分离变量后，(18)变为
d f f = ( − μ + λ ( 1 − L ( w ) ) ) d w . d f f = ( − μ + λ ( 1 − L ( w ) ) ) d w . (df)/(f)=(-mu+lambda(1-L(w)))dw.\frac{d f}{f}=(-\mu+\lambda(1-L(w))) d w .

然后，(19)的解为，对于 w > 0 w > 0 w > 0w>0 ，
f ( w ) = A e − μ w + λ ∫ ( 1 − L ( w ) ) d w f ( w ) = A e − μ w + λ ∫ ( 1 − L ( w ) ) d w f(w)=Ae^(-mu w+lambda int(1-L(w))dw)f(w)=A e^{-\mu w+\lambda \int(1-L(w)) d w}

其中 A 是一个待确定的常数。

考虑在 w = 0 , F ( w ) w = 0 , F ( w ) w=0,F(w)w=0, F(w) 应该有一个值 F ( 0 + ) F 0 + F(0^(+))F\left(0^{+}\right) ，对于 f ( w ) f ( w ) f(w)f(w) 的完整通解是，对于 w ≥ 0 w ≥ 0 w >= 0w \geq 0 ，
f ( w ) = u 0 ( w ) F ( 0 + ) + δ ( w ) A e − μ w + λ ∫ ( 1 − L ( w ) ) d w f ( w ) = u 0 ( w ) F 0 + + δ ( w ) A e − μ w + λ ∫ ( 1 − L ( w ) ) d w f(w)=u_(0)(w)F(0^(+))+delta(w)Ae^(-mu w+lambda int(1-L(w))dw)f(w)=u_{0}(w) F\left(0^{+}\right)+\delta(w) A e^{-\mu w+\lambda \int(1-L(w)) d w}

其中 u 0 ( w ) u 0 ( w ) u_(0)(w)u_{0}(w) 是单位冲激函数， δ ( w ) δ ( w ) delta(w)\delta(w) 是单位阶跃函数，如[9]中所定义。

常数 F ( 0 + ) F 0 + F(0^(+))F\left(0^{+}\right) 和 A 可以通过以下边界条件确定：第一个是归一化条件 F ( ∞ ) = 1 F ( ∞ ) = 1 F(oo)=1F(\infty)=1 ，即
1 = F ( ∞ ) = ∫ 0 ∞ f ( w ) d w = ∫ 0 ∞ u 0 ( w ) F ( 0 + ) d w + ∫ 0 ∞ δ ( w ) A e − μ w + λ ∫ ( 1 − L ( w ) ) d w = F ( 0 + ) + A ∫ 0 ∞ e − μ w + λ ∫ ( 1 − L ( w ) ) d w d w 1 = F ( ∞ ) = ∫ 0 ∞   f ( w ) d w = ∫ 0 ∞   u 0 ( w ) F 0 + d w + ∫ 0 ∞   δ ( w ) A e − μ w + λ ∫ ( 1 − L ( w ) ) d w = F 0 + + A ∫ 0 ∞   e − μ w + λ ∫ ( 1 − L ( w ) ) d w d w {:[1=F(oo)],[=int_(0)^(oo)f(w)dw],[=int_(0)^(oo)u_(0)(w)F(0^(+))dw+int_(0)^(oo)delta(w)Ae^(-mu w+lambda)int(1-L(w))dw],[=F(0^(+))+Aint_(0)^(oo)e^(-mu w+lambda)int(1-L(w))dw],[dw]:}\begin{aligned} 1 & =F(\infty) \\ & =\int_{0}^{\infty} f(w) d w \\ & =\int_{0}^{\infty} u_{0}(w) F\left(0^{+}\right) d w+\int_{0}^{\infty} \delta(w) A e^{-\mu w+\lambda} \int(1-L(w)) d w \\ & =F\left(0^{+}\right)+A \int_{0}^{\infty} e^{-\mu w+\lambda} \int(1-L(w)) d w \\ & d w \end{aligned}
因此，
A = 1 − F ( 0 + ) ∫ 0 ∞ e − μ w + λ ∫ ( 1 − L ( w ) ) d w d w A = 1 − F 0 + ∫ 0 ∞   e − μ w + λ ∫ ( 1 − L ( w ) ) d w d w A=(1-F(0^(+)))/(int_(0)^(oo)e^(-mu w+lambda int(1-L(w))dw)dw)A=\frac{1-F\left(0^{+}\right)}{\int_{0}^{\infty} e^{-\mu w+\lambda \int(1-L(w)) d w} d w}

第二个边界条件是流量守恒条件，即
λ = λ R + μ ( 1 − F ( 0 + ) ) λ = λ R + μ 1 − F 0 + lambda=lambda R+mu(1-F(0^(+)))\lambda=\lambda R+\mu\left(1-F\left(0^{+}\right)\right)

在上述方程中，左侧是系统总到达率。右侧第一项是丢失任务的离开率，第二项是已服务（即未丢失）任务的离开率。

将(5)，即 R = ( 1 − F ( 0 + ) ) R + R = 1 − F 0 + R + R=(1-F(0^(+)))R^(+)R=\left(1-F\left(0^{+}\right)\right) R^{+} ，代入(24)并重新排列各项，我们得到
0 = ( 1 − ρ ( 1 − R + ) ) − ( 1 + ρ R + ) F ( 0 + ) 0 = 1 − ρ 1 − R + − 1 + ρ R + F 0 + 0=(1-rho(1-R^(+)))-(1+rhoR^(+))F(0^(+))0=\left(1-\rho\left(1-R^{+}\right)\right)-\left(1+\rho R^{+}\right) F\left(0^{+}\right)
那就是
F ( 0 + ) = 1 − ρ ( 1 − R + ) 1 + ρ R + F 0 + = 1 − ρ 1 − R + 1 + ρ R + F(0^(+))=(1-rho(1-R^(+)))/(1+rhoR^(+))F\left(0^{+}\right)=\frac{1-\rho\left(1-R^{+}\right)}{1+\rho R^{+}}

R + R + R^(+)R^{+} ，当任务到达系统时，如果 CPU 繁忙，则任务丢失的概率可以计算为
R + = ∫ 0 + ∞ L ( x ) f ( x ) d x ∫ 0 + ∞ f ( x ) d x = 1 − ∫ 0 ∞ ( 1 − L ( x ) ) e − μ x + λ ∫ ( 1 − L ( x ) ) d x d x ∫ 0 ∞ e − μ x + λ ∫ ( 1 − L ( x ) ) d x d x R + = ∫ 0 + ∞   L ( x ) f ( x ) d x ∫ 0 + ∞   f ( x ) d x = 1 − ∫ 0 ∞   ( 1 − L ( x ) ) e − μ x + λ ∫ ( 1 − L ( x ) ) d x d x ∫ 0 ∞   e − μ x + λ ∫ ( 1 − L ( x ) ) d x d x {:[R^(+)=(int_(0+)^(oo)L(x)f(x)dx)/(int_(0+)^(oo)f(x)dx)],[=1-(int_(0)^(oo)(1-L(x))e^(-mu x+lambda int(1-L(x))dx)dx)/(int_(0)^(oo)e^(-mu x+lambda int(1-L(x))dx)dx)]:}\begin{aligned} R^{+} & =\frac{\int_{0+}^{\infty} L(x) f(x) d x}{\int_{0+}^{\infty} f(x) d x} \\ & =1-\frac{\int_{0}^{\infty}(1-L(x)) e^{-\mu x+\lambda \int(1-L(x)) d x} d x}{\int_{0}^{\infty} e^{-\mu x+\lambda \int(1-L(x)) d x} d x} \end{aligned}

将(27)和(26)代入(4)和(5)，我们得到了 M / M / 1 + G + F C F S M / M / 1 + G + F C F S M//M//1+G+FCFSM / M / 1+G+F C F S 系统 CPU 利用率和任务丢失率的解。

5 M / M / 1 + M + F C F S 5 M / M / 1 + M + F C F S 5M//M//1+M+FCFS5 M / M / 1+M+F C F S 系统


在本节中，我们使用上一节中推导出的 M / M / 1 + G + F C F S M / M / 1 + G + F C F S M//M//1+G+FCFSM / M / 1+G+F C F S 情况的结果，来获得 f ( w ) , R + , F ( 0 + ) , U f ( w ) , R + , F 0 + , U f(w),R^(+),F(0^(+)),Uf(w), R^{+}, F\left(0^{+}\right), U 和 R R RR 对于 M / M / 1 + M + F C F S M / M / 1 + M + F C F S M//M//1+M+FCFSM / M / 1+M+F C F S 的更简单模型的显式解。


5.1 分析与解决方案


为了计算 f ( w ) f ( w ) f(w)f(w) ，将方程（23）和 L ( w ) = L ( w ) = L(w)=L(w)= 1 − e − l w 1 − e − l w 1-e^(-lw)1-e^{-l w} 代入方程（21）。结果，我们得到了 M / M / 1 + M + M / M / 1 + M + M//M//1+M+M / M / 1+M+ F C F S F C F S FCFSF C F S 系统中未完成工作分布的密度函数。
f ( w ) = u 0 ( w ) F ( 0 + ) + δ ( w ) 1 − F ( 0 + ) ∫ 0 ∞ e − μ w − λ γ − i w d w e − μ w − λ λ e e − t w f ( w ) = u 0 ( w ) F 0 + + δ ( w ) 1 − F 0 + ∫ 0 ∞   e − μ w − λ γ − i w d w e − μ w − λ λ e e − t w f(w)=u_(0)(w)F(0^(+))+delta(w)(1-F(0^(+)))/(int_(0)^(oo)e^(-mu w-(lambda)/(gamma^(-iw))dw))e^(-mu w-(lambda)/(lambda^(e))e^(-tw))f(w)=u_{0}(w) F\left(0^{+}\right)+\delta(w) \frac{1-F\left(0^{+}\right)}{\int_{0}^{\infty} e^{-\mu w-\frac{\lambda}{\gamma^{-i w}} d w}} e^{-\mu w-\frac{\lambda}{\lambda^{e}} e^{-t w}}

同样地，将 L ( x ) = 1 − e − l x L ( x ) = 1 − e − l x L(x)=1-e^(-lx)L(x)=1-e^{-l x} 代入(27)， R + R + R^(+)R^{+} 变为
R + = 1 − ∫ 0 ∞ e − ( μ + 1 ) x − 1 e − 1 x ∫ 0 ∞ e − μ x − 1 e e − l x d x R + = 1 − ∫ 0 ∞   e − ( μ + 1 ) x − 1 e − 1 x ∫ 0 ∞   e − μ x − 1 e e − l x d x R^(+)=1-(int_(0)^(oo)e^(-(mu+1)x-(1)/(e))-1x)/()(int_(0)^(oo)e^(-mu x-(1)/(e))e^(-lx))/(dx)R^{+}=1-\frac{\int_{0}^{\infty} e^{-(\mu+1) x-\frac{1}{e}}-1 x}{} \frac{\int_{0}^{\infty} e^{-\mu x-\frac{1}{e}} e^{-l x}}{d x}

从附录 A 中，我们知道
∫ 0 ∞ e − μ x − λ T e − l x d x = 1 l ( λ l ) − μ l γ ( μ l , λ l ) = 1 l ( ρ b ) − b γ ( b , ρ b ) ∫ 0 ∞   e − μ x − λ T e − l x d x = 1 l λ l − μ l γ μ l , λ l = 1 l ( ρ b ) − b γ ( b , ρ b ) {:[int_(0)^(oo)e^(-mu x-(lambda )/(T)e^(-lx))dx=(1)/(l)((lambda )/(l))^(-(mu )/(l))gamma((mu )/(l),(lambda )/(l))],[=(1)/(l)(rho b)^(-b)gamma(b","rho b)]:}\begin{aligned} \int_{0}^{\infty} e^{-\mu x-\frac{\lambda}{T} e^{-l x}} d x & =\frac{1}{l}\left(\frac{\lambda}{l}\right)^{-\frac{\mu}{l}} \gamma\left(\frac{\mu}{l}, \frac{\lambda}{l}\right) \\ & =\frac{1}{l}(\rho b)^{-b} \gamma(b, \rho b) \end{aligned}

其中 γ ( a , x ) γ ( a , x ) gamma(a,x)\gamma(a, x) 是不完全伽马函数， ρ = λ / μ ρ = λ / μ rho=lambda//mu\rho=\lambda / \mu 是提供的负载， b = μ / l b = μ / l b=mu//lb=\mu / l 是松弛度的归一化均值。因此，(28) 变为
f ( w ) = u 0 ( w ) F ( 0 + ) + δ ( w ) ( 1 − F ( 0 + ) ) l γ ( b , ρ b ) ( ρ b ) b e − μ w − λ e − l w f ( w ) = u 0 ( w ) F 0 + + δ ( w ) 1 − F 0 + l γ ( b , ρ b ) ( ρ b ) b e − μ w − λ e − l w f(w)=u_(0)(w)F(0^(+))+delta(w)((1-F(0^(+)))l)/(gamma(b,rho b))(rho b)^(b)e^(-mu w-lambdae^(-lw))f(w)=u_{0}(w) F\left(0^{+}\right)+\delta(w) \frac{\left(1-F\left(0^{+}\right)\right) l}{\gamma(b, \rho b)}(\rho b)^{b} e^{-\mu w-\lambda e^{-l w}}
并且 (29) 变为
R + = 1 − 1 ρ b γ ( b + 1 , ρ b ) γ ( b , ρ b ) R + = 1 − 1 ρ b γ ( b + 1 , ρ b ) γ ( b , ρ b ) R^(+)=1-(1)/(rho b)(gamma(b+1,rho b))/(gamma(b,rho b))R^{+}=1-\frac{1}{\rho b} \frac{\gamma(b+1, \rho b)}{\gamma(b, \rho b)}

将(32)代入(26)，我们得到
F ( 0 + ) = 1 − γ ( b + 1 , ρ b ) b γ ( b , ρ b ) 1 + ( ρ − γ ( b + 1 , ρ b ) b γ ( b , ρ b ) ) F 0 + = 1 − γ ( b + 1 , ρ b ) b γ ( b , ρ b ) 1 + ρ − γ ( b + 1 , ρ b ) b γ ( b , ρ b ) F(0^(+))=(1-(gamma(b+1,rho b))/(b gamma(b,rho b)))/(1+(rho-(gamma(b+1,rho b))/(b gamma(b,rho b))))F\left(0^{+}\right)=\frac{1-\frac{\gamma(b+1, \rho b)}{b \gamma(b, \rho b)}}{1+\left(\rho-\frac{\gamma(b+1, \rho b)}{b \gamma(b, \rho b)}\right)}

然后，将 R + R + R^(+)R^{+} (32)和 F ( 0 + ) F 0 + F(0^(+))F\left(0^{+}\right) (33)代入(4)和(5)，可以计算出 M / M / 1 + M / M / 1 + M//M//1+M / M / 1+ M + F C F S M + F C F S M+FCFSM+F C F S 的 CPU 利用率和任务丢失率。


5.2 观察与讨论


从上述 F ( 0 + ) F 0 + F(0^(+))F\left(0^{+}\right) 和 R + R + R^(+)R^{+} 的公式中，我们看到 M / M / 1 + M + F C F S M / M / 1 + M + F C F S M//M//1+M+FCFSM / M / 1+M+F C F S 系统的稳态性能取决于 b = μ / l b = μ / l b=mu//lb=\mu / l 和 ρ = λ / μ ρ = λ / μ rho=lambda//mu\rho=\lambda / \mu 。也就是说，三个输入参数 ( λ , μ , l ) ( λ , μ , l ) (lambda,mu,l)(\lambda, \mu, l) 并不独立影响性能。它们的贡献是通过 ( b = μ / l , ρ = λ / μ ) ( b = μ / l , ρ = λ / μ ) (b=mu//l,rho=lambda//mu)(b=\mu / l, \rho=\lambda / \mu) 的组合值对来实现的。因此，我们可以看到 M / M / 1 + M + F C F S M / M / 1 + M + F C F S M//M//1+M+FCFSM / M / 1+M+F C F S 比经典的（即非实时的） M / M / 1 + F C F S M / M / 1 + F C F S M//M//1+FCFSM / M / 1+F C F S 要复杂得多。在 M / M / 1 + F C F S M / M / 1 + F C F S M//M//1+FCFSM / M / 1+F C F S 系统中，系统的稳态性能取决于单一值 ρ = λ / μ ρ = λ / μ rho=lambda//mu\rho=\lambda / \mu ，但在我们的 M / M / 1 + M + F C F S M / M / 1 + M + F C F S M//M//1+M+FCFSM / M / 1+M+F C F S 系统中，稳态性能不仅取决于 ρ ρ rho\rho ，还取决于归一化平均松弛度 b b bb 。事实上， ( b = μ / l , ρ = λ / μ ) ( b = μ / l , ρ = λ / μ ) (b=mu//l,rho=lambda//mu)(b=\mu / l, \rho=\lambda / \mu) 已被用作许多实时系统仿真和分析研究的输入指标，而无需特定的理由 [ 10 , 11 , 12 , 15 , 23 ] [ 10 , 11 , 12 , 15 , 23 ] [10,11,12,15,23][10,11,12,15,23] 。我们的结果在这里证实了这样的输入指标是有效且充分的。

在图 2 中，我们绘制了任务损失与三种不同归一化平均松弛度（b）的提供负载之间的关系。为了比较，我们还绘制了 R worst R worst  R_("worst ")R_{\text {worst }} 和 R beat R beat  R_("beat ")R_{\text {beat }} 的曲线。从图 2 中可以看出，当 b b bb 非常小（ b = 0.1 b = 0.1 b=0.1\mathrm{b}=0.1 ）时，任务损失几乎与 R worst R worst  R_("worst ")R_{\text {worst }} 相同。将 b b bb 增加到 1.0，我们看到性能显著提高。进一步将 b 增加到 10，我们也看到性能有所改善，尽管任务损失并没有随着 b 的增加而成比例减少。在我们展示的案例中，只有当负载非常高（大于 1.5）且松弛度非常大时，任务损失才能接近 R best R best  R_("best ")R_{\text {best }} 的值。

6 M / M / 1 + M + F C F S I 6 M / M / 1 + M + F C F S I 6quad M//M//1+M+FCFSI6 \quad M / M / 1+M+F C F S I 系统


6.1 改进的 FCFS 调度策略


在本节中，我们考虑了一种针对实时计算机系统修改后的 FCFS 调度策略。修改内容如下：

  1. 当任务进入系统时，尝试通过 FCFS 将其调度到队列末尾。如果成功，完成；否则

  2. 尝试将新任务安排在倒数第二个位置，即确定是否可以将其

    总未完成工作量减去最后一个任务的工作量大于新任务的松弛度。如果新任务不能被安排在倒数第二的位置，它就会丢失；否则

  3. 尝试将原本位于队列末尾且临时移除的任务安排在新到达的任务之后。如果成功，则完成；否则，新到达的任务从队列中删除，因此队列保持与新任务到达之前相同。

当然，采用这种策略，任务有更大的机会被调度。系统性能应该比 FCFS 有所改进。因此，我们将新策略称为改进的 FCFS，或简称为 FCFSI。问题是这种简单的修改是否会产生显著的性能影响。正如我们将看到的，答案似乎是肯定的。

6.2 近似分析


对 M / M / 1 + M + F C F S I M / M / 1 + M + F C F S I M//M//1+M+FCFSIM / M / 1+M+F C F S I 系统的精确分析是困难的，因为除了总未完成工作之外，系统状态参数还包括最后一个任务之前的未完成工作以及队列中最后一个任务的剩余松弛度。我们提出以下近似方法，使我们（仍然）只使用总未完成工作作为系统状态的表示。

我们做出的第一个假设是，如果一个任务不能被安排在队列的末尾，那么它具有与原本在队列末尾的任务相同的特性。这一假设的实现是，在上述步骤 2 中，新任务总是可以被安排在队列的倒数第二位。随着任务特性的方差逐渐减小到零，这一假设变得越来越准确。

我们做出的第二个假设是，当一个新的任务被安排在倒数第二个位置时，为了安排在上述步骤 3 中临时移除的任务，我们允许为其重新抽取一个新的松弛度，而不是使用其原始（剩余）的松弛度。

这些假设是为了便于分析而做出的。在本节的后面部分，我们展示了在没有做出这些假设的情况下获得的模拟结果与我们的近似分析预测的结果非常接近——这表明使用这些假设是合理的。

在上述两个假设下，当新任务到达时，以下事件中只能发生一个：

事件 A：新任务被安排在队列的末尾，因此，不需要任何假设。

事件 B：新任务不能被调度到队列的末尾，但可以（根据假设 1）被调度到倒数第二的位置。同时，队列中原本的最后一个任务可以被调度到

队列的末尾。

事件 C：新任务不能被调度到队列的末尾，但可以（根据假设 1）被调度到倒数第二个位置。然而，队列中原本的最后一个任务不能被调度到队列的末尾（因为其新抽取的松弛时间太小）。新任务被丢弃。

基于这些事实，我们得到未完成工作分布函数 F ( w , t ) F ( w , t ) F(w,t)F(w, t) :, 对于 w > 0 w > 0 w > 0w>0 的以下方程
F ( w , t + Δ t ) = ( 1 − λ Δ t ) F ( w + Δ t , t ) + λ Δ t ∫ 0 w ( 1 − L ( x ) ) B ( w − x ) d x F ( x , t ) + λ Δ t ∫ 0 w ( 1 − L ( x ) ) L ( x ) B ( w − x ) d x F ( x , t ) + λ Δ t ∫ 0 w L 2 ( x ) d x F ( x , t ) F ( w , t + Δ t ) = ( 1 − λ Δ t ) F ( w + Δ t , t ) + λ Δ t ∫ 0 w   ( 1 − L ( x ) ) B ( w − x ) d x F ( x , t ) + λ Δ t ∫ 0 w   ( 1 − L ( x ) ) L ( x ) B ( w − x ) d x F ( x , t ) + λ Δ t ∫ 0 w   L 2 ( x ) d x F ( x , t ) {:[F(w","t+Delta t)=(1-lambda Delta t)F(w+Delta t","t)+],[lambda Delta tint_(0)^(w)(1-L(x))B(w-x)d_(x)F(x","t)+],[lambda Delta tint_(0)^(w)(1-L(x))L(x)B(w-x)d_(x)F(x","t)+],[lambda Delta tint_(0)^(w)L^(2)(x)d_(x)F(x","t)]:}\begin{aligned} F(w, t+\Delta t)= & (1-\lambda \Delta t) F(w+\Delta t, t)+ \\ & \lambda \Delta t \int_{0}^{w}(1-L(x)) B(w-x) d_{x} F(x, t)+ \\ & \lambda \Delta t \int_{0}^{w}(1-L(x)) L(x) B(w-x) d_{x} F(x, t)+ \\ & \lambda \Delta t \int_{0}^{w} L^{2}(x) d_{x} F(x, t) \end{aligned}

在（34）中，右侧的第一项表示在时间间隔 ( t , t + Δ t ) ( t , t + Δ t ) (t,t+Delta t)(t, t+\Delta t) 内没有到达事件的情况。第二、第三和第四项分别表示事件 A , B , C A , B , C A,B,C\mathrm{A}, \mathrm{B}, \mathrm{C} 的情况。

同样地，在处理（14）时，重新排列项并令 Δ t → 0 Δ t → 0 Delta t rarr0\Delta t \rightarrow 0 ，（34）变为
f ( w ) = λ ∫ 0 w ( 1 − L 2 ( x ) ) ( 1 − B ( w − x ) ) f ( x ) d x f ( w ) = λ ∫ 0 w   1 − L 2 ( x ) ( 1 − B ( w − x ) ) f ( x ) d x f(w)=lambdaint_(0)^(w)(1-L^(2)(x))(1-B(w-x))f(x)dxf(w)=\lambda \int_{0}^{w}\left(1-L^{2}(x)\right)(1-B(w-x)) f(x) d x

请注意，(35)和(16)之间的唯一区别是(16)中的 L ( x ) L ( x ) L(x)L(x) 项在(35)中被 L 2 ( x ) L 2 ( x ) L^(2)(x)L^{2}(x) 替换。按照解决(16)的类似方法，我们能够获得以下 M / M / 1 + G + F C F S I M / M / 1 + G + F C F S I M//M//1+G+FCFSIM / M / 1+G+F C F S I 系统的解：对于 w ≥ 0 w ≥ 0 w >= 0w \geq 0 ，
f ( w ) = u 0 ( w ) F ( 0 + ) + δ ( w ) A e − μ w + λ ∫ ( 1 − L 2 ( w ) ) d w f ( w ) = u 0 ( w ) F 0 + + δ ( w ) A e − μ w + λ ∫ 1 − L 2 ( w ) d w f(w)=u_(0)(w)F(0^(+))+delta(w)Ae^(-mu w+lambda int(1-L^(2)(w))dw)f(w)=u_{0}(w) F\left(0^{+}\right)+\delta(w) A e^{-\mu w+\lambda \int\left(1-L^{2}(w)\right) d w}
在哪里
F ( 0 + ) = 1 − ρ ( 1 − R + ) 1 + ρ R + A = 1 − F ( 0 + ) ∫ 0 ∞ e − μ x + λ ∫ ( 1 − L 2 ( x ) ) d x d x F 0 + = 1 − ρ 1 − R + 1 + ρ R + A = 1 − F 0 + ∫ 0 ∞   e − μ x + λ ∫ 1 − L 2 ( x ) d x d x {:[F(0^(+))=(1-rho(1-R^(+)))/(1+rhoR^(+))],[A=(1-F(0^(+)))/(int_(0)^(oo)e^(-mu x+lambda int(1-L^(2)(x))dx)dx)]:}\begin{gathered} F\left(0^{+}\right)=\frac{1-\rho\left(1-R^{+}\right)}{1+\rho R^{+}} \\ A=\frac{1-F\left(0^{+}\right)}{\int_{0}^{\infty} e^{-\mu x+\lambda \int\left(1-L^{2}(x)\right) d x} d x} \end{gathered}
和
R + = ∫ 0 + ∞ L 2 ( x ) f ( x ) d x ∫ 0 + ∞ f ( x ) d x = 1 − ∫ 0 + ∞ ( 1 − L 2 ( x ) ) f ( x ) d x ∫ 0 + ∞ f ( x ) d x = 1 − ∫ 0 ∞ ( 1 − L 2 ( x ) ) e − μ x + λ ∫ ( 1 − L 2 ( x ) ) d x ∫ 0 ∞ e − μ x + λ ∫ ( 1 − L 2 ( x ) ) d x d x R + = ∫ 0 + ∞   L 2 ( x ) f ( x ) d x ∫ 0 + ∞   f ( x ) d x = 1 − ∫ 0 + ∞   1 − L 2 ( x ) f ( x ) d x ∫ 0 + ∞   f ( x ) d x = 1 − ∫ 0 ∞   1 − L 2 ( x ) e − μ x + λ ∫ 1 − L 2 ( x ) d x ∫ 0 ∞   e − μ x + λ ∫ 1 − L 2 ( x ) d x d x {:[R^(+)=(int_(0+)^(oo)L^(2)(x)f(x)dx)/(int_(0+)^(oo)f(x)dx)],[=1-(int_(0+)^(oo)(1-L^(2)(x))f(x)dx)/(int_(0+)^(oo)f(x)dx)],[=1-(int_(0)^(oo)(1-L^(2)(x))e^(-mu x+lambda)int(1-L^(2)(x))dx)/(int_(0)^(oo)e^(-mu x+lambda)int(1-L^(2)(x))dx)dx]:}\begin{aligned} R^{+} & =\frac{\int_{0+}^{\infty} L^{2}(x) f(x) d x}{\int_{0+}^{\infty} f(x) d x} \\ & =1-\frac{\int_{0+}^{\infty}\left(1-L^{2}(x)\right) f(x) d x}{\int_{0+}^{\infty} f(x) d x} \\ & =1-\frac{\int_{0}^{\infty}\left(1-L^{2}(x)\right) e^{-\mu x+\lambda} \int\left(1-L^{2}(x)\right) d x}{\int_{0}^{\infty} e^{-\mu x+\lambda} \int\left(1-L^{2}(x)\right) d x} d x \end{aligned}

现在，让我们考虑 M / M / 1 + M + F C F S I M / M / 1 + M + F C F S I M//M//1+M+FCFSIM / M / 1+M+F C F S I 的情况。将 L ( x ) = 1 − e − l x L ( x ) = 1 − e − l x L(x)=1-e^(-lx)L(x)=1-e^{-l x} 代入(39)并使用变量替换 y = l x y = l x y=lxy=l x ，我们得到
R + = 1 − ∫ 0 ∞ ( 2 − e − l x ) e − ( μ + l ) x − 1 4 e − l x ( 2 − 0.5 e − l x ) ∫ 0 ∞ e − μ x − t 4 e − l x ( 2 − 0.5 e − l x ) d x = 1 − ∫ 0 ∞ ( 2 − e − y ) e − ( b + 1 ) y − ρ b e − y ( 2 − 0.5 e − y ) d y ∫ 0 ∞ e − b y − ρ b e − y ( 2 − 0.5 e − y ) d y R + = 1 − ∫ 0 ∞   2 − e − l x e − ( μ + l ) x − 1 4 e − l x 2 − 0.5 e − l x ∫ 0 ∞   e − μ x − t 4 e − l x 2 − 0.5 e − l x d x = 1 − ∫ 0 ∞   2 − e − y e − ( b + 1 ) y − ρ b e − y 2 − 0.5 e − y d y ∫ 0 ∞   e − b y − ρ b e − y 2 − 0.5 e − y d y {:[R^(+)=1-(int_(0)^(oo)(2-e^(-lx))e^(-(mu+l)x-(1)/(4))e^(-lx)(2-0.5e^(-lx)))/(int_(0)^(oo)e^(-mu x-(t)/(4)e^(-lx)(2-0.5e^(-lx)))dx)],[=1-(int_(0)^(oo)(2-e^(-y))e^(-(b+1)y-rho be-y)(2-0.5e^(-y))dy)/(int_(0)^(oo)e^(-by-rho be^(-y)(2-0.5e^(-y))dy))]:}\begin{aligned} & R^{+}=1-\frac{\int_{0}^{\infty}\left(2-e^{-l x}\right) e^{-(\mu+l) x-\frac{1}{4}} \mathrm{e}^{-l x}\left(2-0.5 e^{-l x}\right)}{\int_{0}^{\infty} e^{-\mu x-\frac{t}{4} e^{-l x}\left(2-0.5 e^{-l x}\right)} d x} \\ & =1-\frac{\int_{0}^{\infty}\left(2-e^{-y}\right) e^{-(b+1) y-\rho b e-y}\left(2-0.5 e^{-y}\right) d y}{\int_{0}^{\infty} e^{-b y-\rho b e^{-y}\left(2-0.5 e^{-y}\right) d y}} \end{aligned}

其中 ρ = λ μ ρ = λ μ rho=(lambda )/(mu)\rho=\frac{\lambda}{\mu} 是系统提供的负载，而 b = b = b=b= μ l μ l (mu )/(l)\frac{\mu}{l} 是松弛度的归一化平均值。计算 R + R + R^(+)R^{+}


可以使用常见的数值方法，例如拉格朗日方法。

将(40)代入(37)，我们可以计算 F ( 0 + ) F 0 + F(0^(+))F\left(0^{+}\right) 。然后通过使用(4)和(5)，可以推导出 M / M / 1 + M + F C F S I M / M / 1 + M + F C F S I M//M//1+M+FCFSIM / M / 1+M+F C F S I 系统的 CPU 利用率和任务丢失率。


6.3 观察与讨论


从 R + ( 40 ) R + ( 40 ) R^(+)(40)R^{+}(40) 的表达式中可以清楚地看出，与 M / M / 1 + M + F C F S M / M / 1 + M + F C F S M//M//1+M+FCFSM / M / 1+M+F C F S 系统一样， M / M / 1 + M + F C F S I M / M / 1 + M + F C F S I M//M//1+M+FCFSIM / M / 1+M+F C F S I 系统的性能也完全取决于所提供的负载 ρ ρ rho\rho 以及归一化平均松弛度 b b bb 。

为了验证我们的近似假设，我们实现了一个仿真模型，在该模型中 M / M / 1 + M + FCFSI M / M / 1 + M + FCFSI M//M//1+M+FCFSI\mathrm{M} / \mathrm{M} / 1+\mathrm{M}+\mathrm{FCFSI} 系统被模拟，而未使用近似假设。图 3 展示了仿真结果与我们的近似分析预测值的对比。从图 3 可以看出，仿真结果与近似分析的结果非常一致。大多数情况下，绝对误差小于 1%。最大的误差约为 2.5%，这发生在归一化松弛度的均值非常大（ b = b = b=b= 10）且负载在 0.6 到 1.0 之间时。

为了比较 FCFS 和 FCFSI 与最优策略 MLF（最小松弛度优先），我们对 M / M / 1 + M + M L F M / M / 1 + M + M L F M//M//1+M+MLFM / M / 1+M+M L F 系统进行了另一项模拟研究。图表
图 4 三种政策的比较

4 和 5 展示了结果。在图 4 中，负载 = 0.7 = 0.7 =0.7=0.7 ，在图 5 中，负载 = 1.5 = 1.5 =1.5=1.5 。再次强调，在许多实时系统中，正常和过载条件都是关注的重点。然后，对于这两种情况，我们研究了广泛的松弛度范围，其中，归一化平均松弛度从 0.1 变化到 10.0，采用对数刻度。FCFSI 和 MLF 的性能曲线是通过仿真获得的，而 FCFS 的曲线是基于分析结果绘制的。从图 4 和图 5 中，我们看到 FCFS 的性能比 FCFSI 和 MLF 差。FCFS 的任务丢失率 R 明显高于 FCFSI 和 MLF。然而，当归一化平均松弛度（b）较小时，FCFSI 的性能与 MLF 非常接近，并且始终显著优于 FCFS。请记住，FCFS 和 FCFSI 都是 O ( 1 ) O ( 1 ) O(1)O(1) 算法，即它们对每个任务到达都有固定的成本。然而，MLF 是一个 O ( lg ⁡ ( n ) ) O ( lg ⁡ ( n ) ) O(lg(n))\mathrm{O}(\lg (\mathrm{n})) 算法，其中 n 是队列长度。因此，实现 FCFSI 算法将需要非常低的在线成本，但其性能将接近最优的 MLF 性能。

让我们现在考虑这样一个简单变化从 F C F S F C F S FCFSF C F S 到 F C F S I F C F S I FCFSIF C F S I 导致近乎最优性能背后的直觉。在轻负载下，队列中任务的顺序无关紧要（并且队列中通常很少有任务）。例如，如果负载是 0.5，那么一个正常的 M / M / 1 M / M / 1 M//M//1\mathrm{M} / \mathrm{M} / 1 系统平均队列长度将小于 2。在这种情况下，两种策略都很好且近乎最优，算法执行时间之间的成本差异可以忽略不计。随着负载的增加，队列长度增加，FCFSI 策略能够在任何时刻使最后两个任务交换。


因此，对于给定的队列长度 n n nn ，随着队列增长到大小 n n nn ，最后两个任务可能会进行多次交换。这一系列交换使队列类似于最小松弛度顺序——特别是当后来的到达任务平均而言倾向于有更晚的截止时间时，正如我们的工作所假设的那样。此外，随着平均队列长度的增加（例如，当到达负载为 1.5 时，平均队列长度约为 10），FCFSI 算法的可预测和快速执行时间的优势变得显著。

7 摘要


本文中报告的解析分析和仿真结果在给定调度保证模型的情况下产生了以下结果：

  1. 我们推导了两种极端情况下的任务损失率 R best R best  R_("best ")R_{\text {best }} 和 R worst R worst  R_("worst ")R_{\text {worst }} ：最佳情况是所有任务的松弛度接近无穷大，最差情况是所有任务的松弛度为零。任何系统的性能都应该在 R best R best  R_("best ")R_{\text {best }} 和 R worst R worst  R_("worst ")R_{\text {worst }} 之间。我们还展示了 R warst − R best = Θ ( 1 ρ 2 ) R warst  − R best  = Θ 1 ρ 2 R_("warst ")-R_("best ")=Theta((1)/(rho^(2)))R_{\text {warst }}-R_{\text {best }}=\Theta\left(\frac{1}{\rho^{2}}\right) 。也就是说，当 ρ → ∞ , R worst − R best → 0 ρ → ∞ , R worst  − R best  → 0 rho rarr oo,R_("worst ")-R_("best ")rarr0\rho \rightarrow \infty, R_{\text {worst }}-R_{\text {best }} \rightarrow 0 与 1 / ρ 2 → 0 1 / ρ 2 → 0 1//rho^(2)rarr01 / \rho^{2} \rightarrow 0 一样快时。

  2. 对 M / M / 1 + G + F C F S ( M / M / 1 + G + F C F S I ) M / M / 1 + G + F C F S ( M / M / 1 + G + F C F S I ) M//M//1+G+FCFS(M//M//1+G+FCFSI)M / M / 1+G+F C F S(M / M / 1+G+F C F S I) 系统进行了精确（近似）分析。结果，得到了未完成的一般解。

    已建立的工作分配、任务丢失率和 CPU 利用率是针对这些系统得出的。

  3. 特别是，推导出了 M / M / 1 + M + F C F S ( M / M / 1 + M + F C F S I ) M / M / 1 + M + F C F S ( M / M / 1 + M + F C F S I ) M//M//1+M+FCFS(M//M//1+M+FCFSI)M / M / 1+M+F C F S(M / M / 1+M+F C F S I) 系统任务损失和 CPU 利用率的显式精确（近似）表达式。仿真结果显示，在 M / M / 1 + M + F C F S I M / M / 1 + M + F C F S I M//M//1+M+FCFSIM / M / 1+M+F C F S I 分析中由近似引入的误差在大多数情况下非常小。

  4. 从 M / M / 1 + M + F C F S M / M / 1 + M + F C F S M//M//1+M+FCFSM / M / 1+M+F C F S 和 M / M / 1 + M + F C F S I M / M / 1 + M + F C F S I M//M//1+M+FCFSIM / M / 1+M+F C F S I 系统的解决方案中，我们观察到系统的稳态性能（以任务丢失率和 CPU 利用率衡量）取决于系统提供的负载 ρ = λ / μ ρ = λ / μ rho=lambda//mu\rho=\lambda / \mu 和归一化平均松弛度 b = μ / l b = μ / l b=mu//lb=\mu / l 。这证实了 ρ ρ rho\rho 和 b b bb 是合适的输入指标，因为它们已在许多其他实时系统的仿真和分析研究中使用。

  5. FCFS、FCFSI 和 MLF 的性能进行了比较。发现使用 FCFSI 可能会比使用 FCFS 带来显著的性能提升。并且在许多情况下，FCFSI 的性能几乎与已被证明是最优的 MLF 相同或非常接近。请注意，FCFSI 的开销仅为 O ( 1 ) O ( 1 ) O(1)O(1) ，因此它是一个时间有界算法。FCFSI 的这一优点加上其性能与最优 MLF 算法相似，使得它适合在线用于那些只需考虑 CPU 资源的系统中。

  6. 分析 MLF 策略仍然是一个开放性问题。正如我们所展示的，在许多情况下，FCFSI 的性能接近 MLF 的性能。在当前版本的 FCFSI 中，允许一个任务与队列末尾的任务交换一次。如果我们允许一个任务交换多次（比如两到三次），我们可以预期 FCFSI 与 MLF 之间的差异将进一步缩小。分析这种增强的 FCFSI 应该比直接处理 MLF 更容易。从这个意义上说，FCFSI 提供了一种可能最终导致 MLF 策略（近似）解析解的方法。

致谢


作者们感谢 J. Kurose 和 L. Sha 提供的许多有用的建议和评论。

参考文献

[l] F. Baccelli and G. Hebuterne, “On ueues with Impa-tient Customers”, Performance ‘81,?ed. F. J. Kylstra), North-Holland Publishing Company, 1981.

[2]  F. Baccelli, P. Boyer, and G. Hebuterne,“SingleServer Queue with Impatient Customers”, Advance Appl. Prob-ability, Vol. 16, 1984.

[3]   D. Y. Barrer, “Queueing with Impatient Customers and Indifferent Clerks”, Operations Research, Vol. 5, 1957.

with Impatient Customers and Ordered Service”, hpera-tions Research, Vol. 5, 1957. [4] D. Y. Barrer,“Queuein

[5]  B. Gavish and P. J. Schweitzer,“The Markovian Queue with Bounded Waiting Time”, Management Science, Vol. 23, No. 12, August 1977.

[6]  B. Gnedeko, and L. Kovalenko, Elements of Queuemg Theory, Israel Program for Scientific Research, Jerusalem, 1968.

[7]  R. L. Haugen and E. Skogan, “Queueing Systems with Stochastic Time Out”, IEEE Transactions on Commu-nications, Vol. COM-28, No. 12, December 1980.

[8]    J. Hong, X. Tan, and D. Towsley, “A Perfor-mance Analysis of Minimum Laxity and Earliest Dead-line Scheduling in a Real-Time System,”to apear in IEEE Transactions on Software Engineering.

[9]  L. Kleinrock, Queueing Systems - Volume 1: The-ory, John Wiley and Sons,1975.

[lo] J. Kurose, Time-Constrained Communication in Multiple Access Networks, Ph.D. Dissertation, Columbia University, 1984.

[ll] J. Kurose, et al. “A Study of Quasi-Dynamic Load Sharing in Soft Real-Time Distributed Computer Systems”

, Proc. of IEEE Real-Time Systems Symposium, De-cember 1986.

[12]   J. Kurose, et al. “Load Sharing in Soft Real-Time Distributed Computer Systems”, IEEE Transaction on Computers, Vol. C-36, No. 8, August 1987.

[13]   A. K. Mok and M. L. Dertouzos, “Multiprocessor Scheduling in a Hard Real-Time Environment”, Proc. of the 7th Tesas Conference on Computing Systems, November 1978.

[14]   C. Palm, “Etude des delais d’attente”, Ericsson Technics, Vol. 5, 1937.

[15]  S. S. Panwar, Time Constrained and Multi-Access Communications, Ph.D. Dissertation, University of Mas-sachusetts at Amherst, February 1986.

附录 A


在这里，我们推导出（30）。我们将其重写如下：
∫ 0 ∞ e − μ x − λ l e − l x d x = 1 l ( λ l ) − μ l γ ( μ l , λ l ) ∫ 0 ∞   e − μ x − λ l e − l x d x = 1 l λ l − μ l γ μ l , λ l int_(0)^(oo)e^(-mu x-(lambda )/(l)e^(-lx))dx=(1)/(l)((lambda )/(l))^(-(mu )/(l))gamma((mu )/(l),(lambda )/(l))\int_{0}^{\infty} e^{-\mu x-\frac{\lambda}{l} e^{-l x}} d x=\frac{1}{l}\left(\frac{\lambda}{l}\right)^{-\frac{\mu}{l}} \gamma\left(\frac{\mu}{l}, \frac{\lambda}{l}\right)

考虑使用变量 y = λ l e − l x y = λ l e − l x y=(lambda )/(l)e^(-lx)y=\frac{\lambda}{l} e^{-l x} 的变化
∫ 0 ∞ e − μ x − λ τ e − t x d x ∫ 0 ∞   e − μ x − λ τ e − t x d x int_(0)^(oo)e^(-mu x-(lambda )/(tau)e^(-tx))dx\int_{0}^{\infty} e^{-\mu x-\frac{\lambda}{\tau} e^{-t x}} d x
注意
d y = − λ e − l x d x d y = − λ e − l x d x dy=-lambdae^(-lx)dxd y=-\lambda e^{-l x} d x
即
d x = − 1 λ e − l x d y = − 1 l y − 1 d y d x = − 1 λ e − l x d y = − 1 l y − 1 d y dx=-(1)/(lambdae^(-lx))dy=-(1)/(l)y^(-1)dyd x=-\frac{1}{\lambda e^{-l x}} d y=-\frac{1}{l} y^{-1} d y
进一步，
e − μ x = ( e − l x ) μ T = ( λ l ) − μ h ( λ l e − l x ) μ T = ( λ l ) − μ 4 y L T e − μ x = e − l x μ T = λ l − μ h λ l e − l x μ T = λ l − μ 4 y L T {:[e^(-mu x)=(e^(-lx))^((mu )/(T))],[=((lambda )/(l))^(-(mu )/(h))((lambda )/(l)e^(-lx))^((mu )/(T))],[=((lambda )/(l))^(-(mu)/(4))y^((L)/(T))]:}\begin{aligned} e^{-\mu x} & =\left(e^{-l x}\right)^{\frac{\mu}{T}} \\ & =\left(\frac{\lambda}{l}\right)^{-\frac{\mu}{h}}\left(\frac{\lambda}{l} e^{-l x}\right)^{\frac{\mu}{T}} \\ & =\left(\frac{\lambda}{l}\right)^{-\frac{\mu}{4}} y^{\frac{L}{T}} \end{aligned}

最后，当 x = ∞ , y = 0 x = ∞ , y = 0 x=oo,y=0x=\infty, y=0 ，和 x = 0 , y = λ l x = 0 , y = λ l x=0,y=(lambda )/(l)x=0, y=\frac{\lambda}{l} 。因此，(41)式的右侧变为
∫ 0 ∞ e − μ x − λ τ e − l x d x = ∫ λ l 0 ( λ l ) − μ l y μ ζ e − y ( − 1 l ) y − 1 d y = 1 l ( λ l ) − μ l ∫ 0 λ l y y μ ⊤ − 1 e − y d y = 1 l ( λ l ) − μ ⊤ γ ( μ l , λ l ) ∫ 0 ∞   e − μ x − λ τ e − l x d x = ∫ λ l 0   λ l − μ l y μ ζ e − y − 1 l y − 1 d y = 1 l λ l − μ l ∫ 0 λ l   y y μ ⊤ − 1 e − y d y = 1 l λ l − μ ⊤ γ μ l , λ l {:[int_(0)^(oo)e^(-mu x-(lambda )/(tau)e^(-lx))dx=int_((lambda )/(l))^(0)((lambda )/(l))^(-(mu )/(l))y^((mu )/(zeta))e^(-y)(-(1)/(l))y^(-1)dy],[=(1)/(l)((lambda )/(l))^(-(mu )/(l))int_(0)^((lambda )/(l))yy^((mu )/(TT)-1)e^(-y)dy],[=(1)/(l)((lambda )/(l))^(-(mu )/(TT))gamma((mu )/(l),(lambda )/(l))]:}\begin{aligned} \int_{0}^{\infty} e^{-\mu x-\frac{\lambda}{\tau} e^{-l x}} d x & =\int_{\frac{\lambda}{l}}^{0}\left(\frac{\lambda}{l}\right)^{-\frac{\mu}{l}} y^{\frac{\mu}{\zeta}} e^{-y}\left(-\frac{1}{l}\right) y^{-1} d y \\ & =\frac{1}{l}\left(\frac{\lambda}{l}\right)^{-\frac{\mu}{l}} \int_{0}^{\frac{\lambda}{l}} y y^{\frac{\mu}{\top}-1} e^{-y} d y \\ & =\frac{1}{l}\left(\frac{\lambda}{l}\right)^{-\frac{\mu}{\top}} \gamma\left(\frac{\mu}{l}, \frac{\lambda}{l}\right) \end{aligned}
在哪里
γ ( a , x ) = ∫ 0 x y a − 1 e − y d y γ ( a , x ) = ∫ 0 x   y a − 1 e − y d y gamma(a,x)=int_(0)^(x)y^(a-1)e^(-y)dy\gamma(a, x)=\int_{0}^{x} y^{a-1} e^{-y} d y

是不完全伽马函数。关于其性质的讨论可以在高等微积分教材中找到。

  1. 1 1 ^(1){ }^{1} 这项工作是马萨诸塞大学 Spring 项目的一部分，部分资金由海军研究办公室根据合同 048-716/3-22-85 资助，由国家科学基金会根据拨款 DCR-8500332 资助，以及由澳大利亚研究委员会根据拨款 A48830314 资助。

  2. 2 2 ^(2){ }^{2} 通常情况下，当一个任务丢失时，可能需要采取一些恢复措施。出于本文的目的，当这种情况发生时，恢复措施被简单地视为一个新的独立任务。因此，我们不特别考虑各个任务的恢复措施。

  3. 3 3 ^(3){ }^{3} 众所周知，最小截止时间优先（MDF）调度算法在这方面也是最优的。然而，正如[23]中所展示的，如果任务截止时间是任务松弛度和服务时间之和，且两者都是独立的随机变量，MDF 有一个副作用，即在长期运行中，该算法对计算时间较长的任务存在偏见。也就是说，计算时间较短的任务经常以牺牲计算时间较长的任务为代价而被调度。然而，FCFS 和 MLF 调度算法没有这种偏见。在本文中，我们仅考虑无偏见的调度算法。

    4 4 ^(4){ }^{4} 这基于任务队列被实现为一棵树。如果队列被实现为一个简单的列表，那么插入成本是 O ( n ) O ( n ) O(n)O(n) ，删除成本是 O ( 1 ) O ( 1 ) O(1)O(1) 阶。