优先队列
在阅读数据结构和算法中有关优先级队列的主题时，我遇到了以下段落...
一种支持短流程但不锁定长流程的可能方法 是给进程 P 一个优先级
100 t(used)-t(init)其中t(used)是进程所花费的时间，t(init)是进程启动的时间 进程已启动，从某个时间 0开始测量。请注意，100 是 幻数，因为它被选择为比最大的要大一些 我们期望同时处于活动状态的进程数。读者可以 观察到，如果我们总是选择优先级最低的进程 数量并且混合中没有太多短流程，那么 从长远来看，无法快速完成的流程将获得 1% 处理器的时间。
谁能解释一下这个过程如何占据1%？如果你能从数学上得出结果那就太好了。
While reading the topic on priority queues in Data Structures And Algorithms I came across the following paragraph...
one possible way to favour short processes yet not lock the long ones
is to give process P a priority100 t(used)-t(init)wheret(used)
is the time taken by a process andt(init)is the time at which the
process initiated , measured from sometime 0. Note that 100 is a
magic number as it is selected to be somewhat larger than the largest
number of processes we expect to be active at once. The reader may
observe that if we always pick the process with the smallest priority
number and there are not too many short processes in the mix, then in
the long run a process that does not finish quickly will receive 1%
of the processor's time.
can anyone explain how the process takes up 1%? it would be good if you could derive the result mathematically.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
当然，所以最初进程的优先级值为负。它是什么并不重要，重要的是它是负数并且基于当前时间，无论它如何表示。为简单起见，我们假设它只是一个整数值。
进程 A 以优先级 0 开始（假设我们处于 t=0）。它执行了例如 10 个时间单位，但尚未完成，因此需要排队以便在将来的某个时间点继续处理。因此，根据公式，
进程 B 的初始优先级在 t = 5 时初始化，因此优先级为 -5。它在队列中具有两个优先级中最低的，因此它也会获得一些时间。假设它也运行 10 个时间单位。完成后，B 的优先级将为：
，因此它会再次排队。我们假设它再次运行 10 个单位。在它的时间片之后，新的优先级将是：
因此，这将在优先级队列中将 B 重新定位在 A 之后。然后A运行，但这次只运行了5个时间单位。它的新优先级是：
进程 A 将再次位于队列顶部并受到关注。假设它再次运行 5 个时间单位，它的新优先级是：
这会将其定位在进程 B 之后，因此 B 将获得一些处理器时间。我们假设这次使用 5 个时间单位。
现在又轮到A了。看看这两个进程如何有效地分别获得处理器 50% 的注意力？如果我们添加第三个长时间运行的进程（“长时间运行”，就像 A 和 B 都是“长时间运行”，因为它们没有运行 10 个单位然后完成，而是重新排队）到混合中，这些进程每个进程可能会占用大约 33% 的处理器时间，因为每次运行但未完成时，它的优先级都会根据运行时间进行调整。在这种情况下，新进程总是首先运行，因为它们具有负优先级值，并且实际上最终会获得更高（更低的数值）优先级
一阵子。然而，这种情况不会永远持续下去——新进程将开始获得越来越大的优先级值。
但是，根据对本书示例所做的假设，由于我们在任何时间都有大约 100 个进程等待一定的处理时间，并且假设没有太多短期运行的进程，因此通常会有大约100 个进程争夺处理器的注意力，因此每个进程都会获得大约相同的时间，很快它们的相对数字优先级值将全部聚集在一起（这意味着具有最高优先级的进程和具有最高优先级的进程在数字上没有太大差异）最低优先级），因此在“顶部”进程运行后，它将获得足够的优先级以将其推到底部（或接近底部）。冲洗并重复，你基本上就得到了一个循环的事情，假设它们每次循环都使用大约相同的时间。任何时候大约有 100 个进程，因此，再次假设存在很少的短时间运行的进程，每个进程都会获得处理器注意力的 1/100。
Sure, so initially ever process has a negative priority value. It doesn't matter what it is, only that it is negative and based on current time, however that is represented. For simplicity, let's assume it's just an integer value.
Process A starts with a priority of 0 (assume we are at t=0). It executes for, say 10 time units but isn't finished, hence it needs to be queued to continue processing at some future point. So the priority will be, based on the formula
Process B's initial priority is initialized at t = 5, so it is -5. It's got the lowest of the two priorities in the queue so it will get some time too. Assume that it also runs for 10 time units. After it is done, B will have a priority of:
and so it'll get queued up again. And let's assume it again runs for 10 units. Following it's timeslice it's new priority will be:
So that'll reposition B after A in the priority queue. A then runs but only runs for 5 time units this time. It's new priority is:
And process A will again be at the top of the queue and get attention. Suppose it runs for 5 time units again, it's new priority is:
which will position it after process B and so B will get some processor time. Let's assume it uses 5 time units this time.
Now it it is A's turn again. See how these two process effectively get 50% of the processor's attention each? If we add a third long-running process ("long running" like both A and B are "long running" in the sense that they didn't run for 10 units and then finish but rather were requeued) to the mix, those processes will each likely get roughly 33% of the processor's time since each time one runs and doesn't finish, it get's its priority adjusted based on how long it spent running. New processes always run first in this scenario because they come in with a negative priority value and they'll actually end up with a higher (lower numeric value) priority
for awhile. However, that won't last forever - the new processes will start to get a larger and larger priority value.
But since we've got, based on the assumptions made for the book's example, around 100 processes at any one time awaiting some processing time and also the assumption is that there aren't too many short-running processes, there will generally be about 100 processes vying for processor attention and so each one will get about the same amount of time and soon enough their relative numeric priority values will all cluster around each other (meaning there's not much difference numerically from the one with the highest priority and the one with the lowest priority) and so after the "top" process runs, it'll get enough added to its priority to push it to the bottom (or near the bottom). Rinse and repeat and you essentially get a round-robin thing going, assuming they all use about the same amount of time each go around. There's about 100 at any one time so, again assuming few short-running processes exist, each one gets 1/100 of the processor's attention.