algorithm - 负载均衡排序算法

Question

我正在开发一个为进程设置亲和性的程序。我有预先确定的数据，可以让我计算出进程在程序生命周期的三个阶段中的每个阶段使用的 CPU(或核心)的粗略百分比。每个过程都有这三个相同的阶段，我在这三个阶段的每个阶段都有预先确定的每个过程的数据。我正在尝试确定可以对流程进行排序的最佳算法。关键是我无法单独对每个阶段进行排序。对于过程 X，在与算法中的过程 Y 进行比较时，必须考虑所有三个阶段。以一些虚构的数据为例:

    CPU's currently at the following loads:

    CPU | Stage 1 | Stage 2 | Stage 3
    ---------------------------------
    1   | 25%     | 25%     | 25%
    2   | 50%     | 50%     | 50%
    3   | 75%     | 25%     | 75%
    4   | 50%     | 25%     | 10%

    Process X was pre-determined to take up 
    10% in stage 1, 20% in stage 2, and 30% in stage 3.

到目前为止，我的想法是将进程 X 占用每个 CPU 的预定百分比相加，结果如下:

    CPU | Stage 1 | Stage 2 | Stage 3
    ---------------------------------
    1   | 35%     | 45%     | 55%
    2   | 60%     | 70%     | 80%
    3   | 85%     | 45%     | 105%
    4   | 60%     | 45%     | 40%

并对每个 CPU 的阶段进行排名(赋予相同的值)，这将导致:

    CPU | Stage 1 | Stage 2 | Stage 3
    ---------------------------------
    1   | Rank 1  | Rank 1  | Rank 2
    2   | Rank 2  | Rank 2  | Rank 3
    3   | Rank 3  | Rank 1  | Rank 4
    4   | Rank 2  | Rank 1  | Rank 1

然后根据每个进程在每个阶段使用的数量对排名进行加权，并添加每个阶段的最终排名 * 权重以获得一个整数以确定最佳 CPU 分配。在这个例子中，我会给阶段 3 赋予 3 的权重，因为它是此过程的最高值(value)阶段，阶段 2 的权重为 2，阶段 1 的权重为 1，原因与阶段 3 相同。这将导致:

    CPU | Stage 1 | Stage 2 | Stage 3 | Sum
    -----------------------------------------
    1   | 1       | 2       | 6       | 9
    2   | 2       | 4       | 9       | 15
    3   | 3       | 2       | 12      | 17
    4   | 2       | 2       | 3       | 7

由于 CPU 4 的总和最低，因此它是将进程 X 分配给的最佳候选者。我相信这仍然有一些问题，我认为可能有更好的方法来做到这一点(这就是我问你的原因!)。我只是想我会解释到目前为止我所拥有的，只是为了让您了解我正在使用什么。

编辑:我要补充一点，您不能简单地对每个 CPU 的阶段求和，然后应用排序算法。每个阶段都必须保持在 100% 以下，如果将阶段相加，您可能会无意中将进程分配给没有空间的 CPU。 IE，分配进程Y 90%/20%/30% 被计算(在对阶段求和的假设下)分配给CPU 1 20%/30%/40%。此 CPU 的阶段总和可能小于任何其他 CPU，但将进程 Y 的阶段 1 (90%) 添加到 CPU 1 (20%) 的阶段 1 大于 100%，并且会导致溢出。

应避免在任何地方对阶段求和，因为它隐藏了可能的问题。

我认为这真正归结为...您如何对数据集进行排序？由于每个 CPU 本质上都是一个数据集(第 1 阶段、第 2 阶段、第 3 阶段)，我需要对其进行排序以确定进程分配。

编辑 2:我刚刚结束了我的描述。

Answer 1

所以你是说你想对进程进行排序，以便你可以安排尽可能多的进程在当前的 CPU 平衡负载下运行？

这就像一个 01- knapsack问题，除了有三个维度(阶段)而不是两个(大小，重量)。我想 Knapsack 的解决方案(动态规划或贪婪)也适用于您。