c++ - 您将如何在调度程序中实现此自适应 'fudge factor'？

Question

我有一个调度程序，无休止地执行 n 个操作。每个 Action 都安排在 x 秒后。当一个 Action 完成时，它会被重新安排到另一个 x 秒到之前安排的时间之后。每隔 1 秒，调度程序“滴答”一次，最多执行 25 个应触发的操作。操作可能需要一秒钟左右的时间才能完成(尽管这个值应该被认为是可变的和不可预测的)。

假设 x 是 60 秒。由于最多同时执行 25 个 Action 的限制，当 n 变大时，可以想象调度程序将没有时间在一个时间内执行所有 n 个 Action 60 秒窗口，随着时间的推移， Action 将越来越晚地执行。这是不可取的，因为在每个滴答 上都会执行一些操作，这会增加我的系统负载。对我而言，保持 x 完全恒定不如降低负载重要。

所以我希望实现一个自适应的“障碍”，一个自动应用的软糖因素h，当大多数 Action “延迟”执行时增加它，并减少它(将它缩小到它的默认值为零)当它们看起来并且始终如一地准时时。然后，调度程序将被安排为 x+h 秒的时间安排操作，而不是 x。

在高层次上，您将如何处理这个问题？您将如何定义“大多数操作‘延迟’执行”以及您将如何在 C++03 代码中表示/检测它？

更好的是，是否存在客观“有效”的现有知名方法？

Answer 1

明确地说，您的目标是避免在有任务的情况下持续高负载每个滴答声，而不是旨在最小化调度延迟。相应地，你在考虑软糖时应该考虑的指标因素是负载，而不是迟到。

如果你对系统有充分的了解——任务的数量，他们的重新安排间隔，它们的执行时间分布——原则上你可以精确地解决一个让分值给你繁忙时的平均目标负载，或者说仅超过目标负载10% 的时间在忙碌时，等等。

另一方面，如果此信息不可用或不可预测，您将需要一种适应性方法。

这类事情的一般理论是 control theory , 可以得到相当参与。从广义上讲，启发式是:如果负载小于阈值，我们有正让分，降低让分；如果负载是超过阈值，增加障碍。

差点应该是成比例的，而不是额外的:例如，如果，我们知道我们一直重载 10%，那么如果我们在作业调度上应用了 10% 的比例延迟。也就是说，我们是希望应用障碍因素 h 以便将工作安排在xh秒时间而不是 x。系数 1 对应于没有障碍。

当我们重载但不是最大重载时，响应是线性的在日志中:log(h) = log(load) - log(load_target)。所以最简单的方法会是:

load = get_current_load();
if (load>load_target) h = load/load_target;
else h = 1.0;

不幸的是，有一个最大的测量负载，线性度下降这里。可以扩展线性模型以包含累积的与目标负载的偏差，以及负载的变化率。这对应于 proportional-integral-derivative controller .由于这是一个嘈杂的环境( Action 有变化执行时间)，避开导数位可能是明智的该模型的一部分，并坚持使用比例积分 (PI) 部分。当这个模型被离散化时，我们得到 log(h) 的表达式与电流(对数)过载成正比，加上一个术语捕捉到我们做得有多糟糕:

load = get_current_load();
deviation = load > load_target ? log(load/load_target) : 0;
accum += p1 * deviation;

log_h = p2 * deviation + accum;
h = log_h < 0 ? 1.0 : exp(log_h);

除了，我们没有对称问题:当我们在下方时负载目标，但累积误差项仍然很高。我们可以通过累积负偏差来解决它同样，但将累积误差限制为至少非负的，所以一段合理的低负荷不给我们以后的免费通行证:

load = get_current_load();
if (load > 0) {
    deviation = log(load/load_target);
    accum += p1 * deviation;
    if (accum < 0) accum = 0;
    if (deviation < 0) deviation = 0;
}
else {
    accum = 0;
    deviation = 0;
}

log_h = p2 * deviation + accum;
h = log_h < 0 ? 1.0 : exp(log_h);

p2 的值将(大致)介于 0.5 和 0.9 之间，为累积误差的影响留出一些空间。p1 的一个好的值可能是大约 0.3 到 0.5 倍滞后时间的倒数，变化所需的步数在 h 中将其自身呈现为负载的变化。这个可以估计通过 Action 的平均重新安排时间。

您可以尝试使用这些参数来获得你想要的回应，或者你可以做一个更忠实的数学调度问题的模型，然后对其进行数学计算!参数本身也可以自适应地修改时间，基于观察到的对负载变化的响应。

(警告，我实际上并没有在模拟调度程序中尝试过这些片段!)