backfilling

先描述两种常规的 backfilling 方法，这些方法的大致思想是：如果之后达到的 query 不影响之前的 query，那么就把它提前执行。Backfill 主要是为了解决资源利用中的空洞问题，按照 FCFS 的调度可能导致资源没有用满，先到的任务由于资源不足无法调度，可以调度的任务又被先到的任务挡住。

这两种方法将任务抽象为一个矩形，长为估算的运行时间，宽为需要的资源。整个任务的调度可以看作在一个二维坐标系中安排这些矩形：

Conservative Backfilling

对于每一个到达的 query

1. 寻找可以_开始的时间_：扫描已经在运行的任务，获取它们占用的资源和估算的结束时间，找到一个可以放下当前 query 的空间
2. 如果不能放下，则放在所有任务之后
3. 如果可以放下，则当时间到达_开始的时间_后开始被调度执行

job3 是一次成功的 backfill，它跨过了比它更早到达的 job1 和 job2, 找到了合适的运行位置，并不会影响到 job1 和 job2

Easy Backfilling

Easy 更为激进，只要不影响队列中的第一个 query，它就可以进行 backfill

1. 寻找第一个 query 可以开始的时间
   1. 寻找一个可以放下当前 query 的空间，开始的时间记录为 shadow time
   2. 这个时间点如果除了第一个任务所用的资源，还有剩余的资源，记录为 extra res
2. 寻找后面的 query 是否可以 backfill
   1. 按照到达时间的顺序遍历后续的 query
   2. 第一个满足以下两个条件的 query 可以被 backfill
      1. 在 shadow time 之前结束，并且其资源消耗小于当前可用资源
      2. 资源小于当前可用资源并且小于 extra res

下面这种情况显示了两种方法的不同，注意到 job3 延迟了 job2 调度，在 Easy 方法中，只要不延迟队列中的第一个 job，并且资源满足，就可以 backfill，因此相比于 Conservation, 会更容易 backfill，更充分地利用资源，但是这个例子也说明了 Easy 对时间短资源多类型的 query 不友好，这种类型因为资源多无法 backfill, 又因为 Easy，导致其他 query 可以推迟它的执行。