优先级队列

Question

在阅读数据结构和算法中关于优先级队列的主题时，我看到了以下段落.

支持短进程但不锁定长进程的一种可能方法是给予流程P一个优先级100 t(used)-t(init)，其中t(used)是进程占用的时间，t(init)是进程启动的时间，从某些time 0中度量。请注意，100是一个神奇的数字，因为它被选中要比我们期望一次活动的进程数量多一些。读者可能会注意到，如果我们总是选择优先级最小的进程，并且混合进程中没有太多的短进程，那么从长远来看，一个进程如果不能快速完成，将得到处理器时间的1%。

有人能解释一下这一过程占1%的原因吗？如果你能从数学上得出这个结果，那就太好了。

Answer 1

当然，所以最初任何时候进程都有一个负优先级值。它是什么并不重要，只是它是消极的和基于当前的时间，但这是被代表的。为了简单起见，让我们假设它只是一个整数值。

进程A以0的优先级开始(假设我们在t=0)。它执行10个时间单位，但还没有完成，因此需要排队以便在将来的某个时间点继续处理。所以，优先考虑的是，根据公式

priority = priority + 100*(endtime - starttime)

priorityA = 0 + 100*(10-0)
priorityA = 1000

进程B的初始优先级在t= 5处初始化，因此是-5。它是队列中两个优先级中最低的，所以它也会有一些时间。假设它也运行了10个时间单位。在完成之后，B将优先考虑：

priorityB = -5 + 100*(20-10)
priorityB = 995

所以它会再次排队。让我们假设它再次运行10个单元。随着时间的推移，新的优先事项将是：

priorityB = 995 + 100*(30-20)
priorityB = 1995

因此，这将在优先级队列中在A之后重新定位B。然后运行，但这次只运行5次单位。新的优先事项是：

priorityA = 1000 + 100*(35-30)
priorityA = 1500

进程A将再次位于队列的顶端，并引起注意。假设它再次运行5个时间单元，那么它的新优先级是：

priorityA = 1500 + 100(40-35)
priorityA = 2000

它会在进程B之后定位，所以B会得到一些处理器的时间。假设这一次它使用5个时间单位。

priorityB = 1995 + 100(45-40)
priorityB = 2495

现在又轮到A了。看看这两个进程是如何有效地得到处理器50%的关注的？如果我们将第三个长时间运行的进程(A和B都是“长运行”，即它们没有运行10个单元，然后完成，而是被请求)添加到混合中，那么这些进程很可能会得到处理器时间的33%左右，因为每次运行和不完成时，都会根据运行时间的长短来调整优先级。在这种情况下，新进程总是首先运行，因为它们具有负优先级值，并且它们实际上会在一段时间内获得更高(较低的数值)优先级。然而，这不会永远持续下去--新的进程将开始获得越来越大的优先级值。

但是，由于我们已经根据为本书的例子所做的假设，在任何时候都有大约100个进程等待某个处理时间，而且假设没有太多短运行的进程，通常会有大约100个进程争相获得处理器的注意，所以每个进程都会得到大约相同的时间，很快它们的相对数字优先级值就会聚集在一起(这意味着与优先级最高的进程和优先级最低的进程没有太大的区别)，所以在“顶级”进程运行之后，它将获得足够多的优先级，将其推到底部(或接近底部)。漂洗和重复，你基本上可以得到一个循环的东西，假设他们都使用了大约相同的时间，每走一圈。在任何时候都有大约100个进程，因此，同样地，假设很少有短时间运行的进程存在，每个进程都会得到处理器1/100的关注。