两个工人比一个工人好得多

一种常见的体系结构模式是“任务队列”：任务进入有序队列，工作器弹出任务并处理它们。从分布式系统到线程池，这种模式无处不在。它同样适用于人类系统，就像在超市或银行排队一样。任务队列很受欢迎，因为它们简单、易于理解，并且具有很好的伸缩性。

任务队列有两个主要性能指标。吞吐量是指每个时间单位处理的任务数。延迟是指任务在处理之前在队列中等待的时间。吞吐量的扩展符合您的预期(2倍的工作进程≈2倍的吞吐量)，但延迟不那么直观。尽管它们很受欢迎，但我们并不抽象地对任务队列的属性进行建模。我们有工具来实现它们，也有工具来跟踪/度量它们，但是我们不使用理论模型来抽象地理解我们的系统。在本文中，我们将对一个简单的任务队列进行建模，并展示延迟是如何对初始参数高度敏感的。

我们将使用PRISM对这个问题进行建模。棱镜是一种概率模型检查器，这意味着它可以进行软件设计，并计算出各种结果的可能性有多大。我以前谈过PRISM，并批评它的限制性语法。但在这里，它是适合这项工作的工具，我们可以用一些聪明的方法让它闪耀光芒。这篇文章不会假设你对PRISM有任何先验知识。我们开始吧。

棱镜支持多种不同类型的概率模型。其中最简单的是离散时间马尔可夫过程(DTMC)。在这种情况下，时间一次按离散的一步前进，所有事情都以已知的概率发生。您可以将其视为在状态机的状态之间随机移动，其中一步就是一次转换。这一步是一个抽象的时间量。虽然你可以在假设每一步都是固定的时间(比如5秒)的情况下进行设计，但我们不需要在这里这样做。

我们将假设有N个任务，并且它们是独立的。这意味着处理一项任务所需的时间与之前有多少任务以及之后有多少任务无关。但是，不同的任务需要不同的处理时间。我们可以效仿这一点，把它翻转过来，说每个工人每一步只有一定的机会完成一项任务。如果我们说机会是50%，那么一半的任务将在恰好一步内完成，四分之一将在恰好两步内完成，以此类推。总的来说，工人将大约每两步完成一项任务。

棱镜的表现力不足以让我们单独跟踪每项任务。幸运的是，我们拥有的所有任务都是可以互换的：虽然有些任务需要比其他任务更长的时间来处理，但这在概率上是抽象的。相反，我们可以说，有一个整数表示剩余任务的数量，其中工人有机会在每个步骤中递减该数字。然后，如果需要四个步骤才能减少左边，我们就可以说工人正在做一项复杂的任务。

Dtmc//模型类型const int N；//任务模块工作者数//待处理任务数//剩余0到N之间的数字：[0..N]init N；

我们需要发出一个命令来代表工人完成一项任务。首先是完整的命令，然后是它的工作原理：

命令有三个部分：标签、保护和更新。我们先从最新消息说起。我们可以说，这只是意味着我们减少了左侧。在PRISM语法中，我们说Left的新值为Left-1。

但它的成功率只有50%。另外50%的时候什么都不会发生。我们可以写Queue'；=Queue，或者我们可以使用简写True：

下一位是警卫。只有当守卫为真时，才能进行更新。这里我们需要的明显防范措施是，如果没有任何剩余的任务，我们就不能处理任务。这样就只剩下标签了，这是我们为命令指定的一个可选名称。

最好在最后保留一个“卡顿状态”，这样模型就不会死锁。所以，如果我们没有任务，我们就说是真的。

[Worker](Left>；0)->；0.5：(Left'；=Left-1)+0.5：True；[](Left=0)->；True；endModule。

Dtmcconst int N；//剩余的任务模块工作线程数：[0..N]init N；[Worker](Left>；0)->；0.5：(Left'；=Left-1)+0.5：True；[](Left=0)->；True；End模块//参见下一节奖励"；Total_Time&34；[]Left>；0：1；End Rewards。

在程序中，我们有一个级别的编码：程序本身。在规格方面，我们有两个层次。我们先编写规格，然后再编写有关规格的属性。在PRISM中，我们还可以编写属性作为系统上的查询，并让模型检查器告诉我们期望值是什么。

我们的第一个属性是处理所有任务所用的总时间。为了跟踪这一点，我们需要对我们的规范做一个小小的更改。奖励函数是我们在系统演化过程中分配给每个连续状态的值。当我们需要对延迟进行建模时，这将变得更加重要，但目前我们可以使用一个非常简单的奖励函数：

如果队列中还有任何任务，我们会将该行为的总奖励加1。1总奖励是完成所有任务所采取的步骤数。

接下来，我们需要一个在我们用完任务时获得奖励的属性。它看起来像这样：

奖励将取决于我们开始的任务(或N)的数量。我们可以进行一个实验，测试一组N的属性，并将结果绘制成图表。下面是N从10到100的吞吐量，以10为单位：

这给了我们吞吐量。但是我们的模型还不能告诉我们任何关于延迟的信息，因为我们假设所有的任务都是从队列开始的。这是一个批处理过程的模型，而不是随着时间的推移进入并等待轮到它们的任务。

这就是延迟变得非常重要的地方。除了处理任务需要多长时间外，我们还需要考虑任务在处理之前等待了多长时间。在加入这个之前，我们的模型是不完整的。

我们说，不是所有的任务都可以立即投入工作，而是随着时间的推移才能完成。我们添加了一个新变量Queue来表示队列中实际存在的任务数。我们还添加了一个入队命令，如果队列中还有未完成的任务，该命令会将任务添加到队列中。这将以与员工处理任务相同的“速率”发生。2个。

Queue：[0..N]init 0；[enQueue](Queue<；Left)->；0.5：(Queue'；=Queue+1)+0.5：TRUE；

只有在队列非空的情况下，工作人员才能处理任务。当它处理一项任务时，它将同时从剩余总数和队列中递减。

[Worker](Left>；0&；Queue>；0)->；0.5：(Left'；=Left-1)&；(Queue'；=Queue-1)+0.5：TRUE；

我们的两个命令并不是独占的：当0<；队列<；离开时，[enQueue]和[Worker]都是有效命令。在这种情况下，所有的可能性都被加权在一起。在这里，这意味着有四种可能性相等的可能性：

(3)和(4)具有相同的结果，但在建模目的上有所不同。在我的心理模型中，工作者命令比入队命令建模的时间跨度更长。工作人员需要时间来处理任务，而向队列添加任务是瞬间的。由于我们正在计算所用的总时间，因此我们只想在时间流逝时计算Worker命令的数量。我们可以通过向奖励函数添加标签来实现这一点：

Dtmcconst int N；//剩余任务模块工作线程数：[0..N]init N；队列：[0..N]init 0；[enQueue](队列<；左)->；0.5：(队列'；=队列+1)+0.5：真；[工人](左>；0&；队列>；0)->；0.5：(左'；=左-1)&；(队列&#。=队列-1)+0.5：真；[](左=0)->；真；结束模块//查看下一节奖励"；等待时间"；[工人]队列&>1：队列-1；结束奖励"；总计_时间"；[工人]左&>0：1；结束奖励。

首先，让我们检查一下是否没有更改吞吐量。由于我们只对带有Worker命令的时间进行建模，因此我们的新模型应该不会更改总时间。以下是我们得到的信息：

一模一样，很好。但我们来这里也是为了模拟延迟。延迟是指任务在处理之前在队列中等待的时间。因为我们没有方法来挑选单个任务，所以我们可以查看所有任务总共等待了多长时间，这是一个关联值。

奖励函数类似于TOTAL_TIME，不同之处在于不是将奖励递增1，而是递增Queue-1。我们减1是因为如果队列非空，则队列中的一个任务正在被处理。

增长速度是平方的！如果我们有10个任务，他们总共要等待30个步骤。如果我们有100个人，他们总共要等1300多步。音量增加10倍，总延迟增加40倍！

当许多人第一次看到它时，这让他们大吃一惊。棱镜提供了一个模拟器视图，可以帮助您逐步查看可能的时间线并查看正在发生的情况。不幸的是，它不太适合静态文本，所以这里有一个非正式的解释。

假设我们有4个随机顺序的任务，间隔一步。我们还知道其中三个任务需要一个步骤来完成，而最后一个任务需要五个步骤。我们可以肯定地知道，我们将在八个步骤中完成所有四个任务，但延迟取决于它们进入的顺序。最好的情况是1115。我们在前三步中完成前三个任务。当大型任务到来时，它是队列中唯一不计入延迟的任务，总等待时间为零。

最坏的情况是511。到了第四步，所有四个任务都在队列中，但我们还没有完成第一个任务。我们只在第五步完成了第一项任务，到那时我们的等待时间已经是9次了。我们最后的等待时间是12次。

现在改为尝试2 2 2。总时间相同，但现在最后一个任务在我们开始处理它之前只在队列中等待了3个步骤。我们的等待时间是6.3。

然后，延迟峰值来自两个方面：第一，任务越多，长任务堵塞队列的可能性就越大。其次，如果队列被阻塞，可能会有更多任务堆积在队列后面，从而增加延迟。

现在终于到了增加两名工人的时候了。显而易见的方法是只需添加另一个命令，如下所示：

[工作器2](Left>；0&；Queue>；0)->；0.5：(Left'；=Left-1)&；(Queue'；=Queue-1)+0.5：TRUE；

但这不管用。工人或工人2都会发生，但它们不可能同时发生。它们都修改了Left和Queue，每个变量每一步只能修改一次。相反，我们必须变得聪明起来。由于这两个工人是独立的，我们将同时“模拟”这两个工人作为单个命令的一部分。请考虑下表：

每种组合的可能性都是相等的，所以恰好有50%的人在处理一项任务，25%的可能性两个人都在处理一项任务，两个人都失败的可能性为25%。这将导致以下命令：

[Worker](Left>；1&；Queue>；1)->；0.25：(Left'；=Left-2)&；(Queue'；=Queue-2)+0.5：(Left'；=Left-1)&；(Queue'；=Queue-1)+0.25：真；

只有当队列中至少有两个任务时，这才起作用。否则，一个工人不得不空闲，而另一个工人在处理它。如果队列中只有一个任务，那么我们就假装只有一个工人。

[Worker](Left>；=1&；Queue=1)->；0.5：(Left'；=Left-1)&；(Queue'；=Queue-1)+0.5：TRUE；

我们还需要改变我们的奖励功能。我们只将队列中前两个任务之后的任务视为正在等待。

Dtmcconst int N；//剩余任务模块工作线程数：[0..N]init N；Queue：[0..N]init 0；[enQueue](Queue<；Left)->；0.5：(Queue'；=Queue+1)+0.5：TRUE；[Worker](Left>；=1&；Queue=1)->；0.5：(Left'；=Left-1)&；(Queue'；=Queue-1)+0.5：TRUE；[Worker](Left>；1&；Queue>；1)->；0.25：(Left'；=Left-2)&；(Queue'；=Queue-2)+0.5：(Left'；=Queue-1)&；(Queue'；=Queue-1)+0.25：TRUE；[](Left=0)->；TRUE；End Moderewards"；WAIT_TIME"；[Worker]队列&>2：队列-2；End_rewards"；Total_Time"；[Worker]Left>；0：1；End Rewards。

你可能认为完成所有任务需要一半的时间，但实际上接近2/3。只有当队列长度至少为2时，我们才能同时使用这两个工作进程，因此在每次运行的大部分时间里，我们都浪费了一个工作进程。如果我们通过使入站速率更高来使队列饱和，那么总时间将收敛到一个工作者总时间的一半。

对于一名员工来说，等待时间几乎是二次曲线，而这是次线性的。只有当两名员工都熄火时，排队才会拥堵，而这种情况发生的可能性要小得多。回到我们的511案例，当第一个工人完成第一个任务时，第二个工人已经处理了其他三个任务。

我们的模型只覆盖了状态空间的一小部分。我们对入站概率、出站概率和工作人员数量进行了硬编码。特别是，我不喜欢我们在排队和出队时使用相同的概率。据我们所知，这会导致病理结果。一个好的规范应该可以帮助我们探索不同的参数，而不必重写它。

第一个更改是最简单的：更改入站费率。PRISM允许我们在保护子句中使用表达式，因此通过添加一个P_REQUEST常量，我们可以改变每一步的入站概率。所有更新概率的总和必须为1，这在这里很简单。

Const Double P_Request；//in[0，1]//...[EnQueue](Queue<；Left&；Left<；=N)->；P_Request：(Queue'；=Queue+1)+(1-P_Request)：TRUE；

改变任务处理速率更为复杂。假设一个工人处理一项任务的概率是P。如果有两个工人，有四种可能性：

你可以检查所有的可能性加起来是否为1。

1*p²(1-p)⁰：QUEUE'；=QUEUE-22*p？(1-p)？：QUEUE'；=QUEUE-11*p⁰(1-P)²：QUEUE'；=QUEUE-0。

这可能会让您想起代数1：(a+b)²=a²+2ab+b²。用一点组合学的知识，我们可以证明它们是一样的。这只是二项展开！4 3个工人的相应概率是：

我们不仅可以用它来概括任务处理速度，还可以用它来扩展到任意数量的工作人员。不幸的是，手工操作太单调乏味了。那么我做的是什么呢？

然后我让一个Python脚本为我写了它。您可以在这个要点中获得模板和脚本。

Dtmcconst int N；//Max Tasksconst Double P_Request；//In[0，1]Const Double P_Worker；//In[0，1]Const int K；//[1，]模块队列左侧：[0..N]init N；Queue：[0..N]init 0；[Worker](Left>；=1&；((Queue>；=1&；K=1)|(Queue=1&；K。1*POW(P_Worker，0)*POW(1-P_Worker，1)：(Left'；=Left-0)&；(Queue'；=Queue-0)+1*Power(P_Worker，1)*Power(1-P_Worker，0)：(Left'；=Left-1)&；(Queue'；=Queue-1)；[Worker](Left&>=2&；(Queue&>。K=2)|(Queue=2&；K&>2))->1*power(P_Worker，0)*power(1-P_Worker，2)：(Left'；=Left-0)&；(Queue'；=Queue-0)+2*Power(P_Worker，1)*Power(1-P_Worker，1)：(Left'；=Left-1)&；(Queue'；=Queue&39；=队列-1)+1*POW(P_Worker，2)*POW(1-P_Worker，0)：(Left'；=Left-2)&；(Queue'；=Queue-2)；[Worker](Left&>；=3&；K=3)|(Queue=3&；K&>3))-&>。1*power(P_Worker，0)*power(1-P_Worker，3)：(Left'；=Left-0)&；(队列'；=队列-0)+3*power(P_Worker，1)*power(1-P_Worker，2)：(Left'；=Left-1)&；(队列#39；=队列-1)+3*power(P_Worker，2)*power(1-P_Worker，2)。=Left-2)&；(队列'；=队列-2)+1*power(P_Worker，3)*power(1-P_Worker，0)：(Left'；=Left-3)&；(队列'；=队列-3)；[Worker](Left&>=4&；K=4)|(Queue=4&；K&>4))-&G。1*power(P_Worker，0)*power(1-P_Worker，4)：(Left'；=Left-0)&；(队列'；=队列-0)+4*power(P_Worker，1)*power(1-P_Worker，3)：(Left'；=Left-1)&；(队列#39；=队列-1)+6*power(P_Worker，2)*power(1-P_Worker，3)。=Left-2)&；(队列#39；=队列-2)+4*power(P_Worker，3)*power(1-P_Worker，1)：(Left'；=Left-3)&；(队列'；=队列-3)+1*Power(P_Worker，4)*power(1-P_Worker，0)：(Left'；=Left-4)&；(Queue'；=Queue-4)；[](Left=0)->；true；[enQueue](Queue<；Left&；Left<；=N)->；P_Request：(Queue'；=Queue+1)+(1-P_Request)：TRUE；End模块转发"；Wait_Time"；[Worker]队列&>K：Queue-K；End rewardsrewards"；Total_Time"；[Worker]Left&。

我偷偷地加入了另一个更改：我修改了Guard子句，使用了一个新的常量K。我不喜欢我硬编码我们使用的工人数量的方式，所以现在K就是我们拥有的工人数量。这样，如果你想自己玩它，你就不需要修改规格来在1或2(或3或4)个工人之间切换。

这是一个简单的任务队列模型。我们没有涵盖优先级、错误处理、多个队列等。尽管如此，该规范还是很好地展示了延迟的非线性，以及添加更多工作线程会产生多么显著的影响。

如果你对PRISM感兴趣，你可以在这里下载。如果需要，我很乐意回答简单的问题或提供建议。如果您对任务队列的更广泛的数学理论感兴趣，那么您将希望研究排队理论。

我在我的时事通讯上分享了这篇文章的初稿。如果你喜欢我的作品，为什么不订阅呢？

在这里，我们把它当做成本，而不是奖励。但由于它们在操作上是相同的，所以PRISM只有奖励函数的语法。[返回]。

等等，如果这个步骤是时间的抽象模型，它怎么可能是相同的进出站速率呢？问得好。在本例中，我以一种精确的方式建立了模型，以确保它能正常工作。在实践中，您需要以一种“通用”的方式编写您的PRISM规范，这种方式更难阅读，但更容易正确设计。我使用了“更优雅”的规范来保持对任务队列的关注。 [返回]

如果我们进行奖励(队列)而不是(队列-1)，数字略有不同，但趋势是相同的。 [返回]。

给定N个工人，有N个选择K种不同的方式让K个工人在给定的时间内处理一个任务，并且每种情况的概率为p^K*(1-p)^(N-K)。[返回]