回填（backfilling）被認為可以提高系統利用率並且已在幾種排程軟體中實現。回填的工作原理是通過發現存在於2D圖表中的“洞”，將較小的、能“進洞”的任務提前處理。
基本介紹
- 中文名：回填技術
- 外文名：backfilling
- 工作原理：通過“洞”，將較小的任務處理
- 回填方式：保守的和積極的
- 作用：可以提高系統利用率
並行任務排程通常被看作是一張2維圖表：一個軸代表時間，另一個代表所需處理器的數量。每個任務可以被想像成一個長方形，高是用戶期望值（時間）而寬是所需處理器數。並行排程策略在過去已被廣泛地研究過。最簡單的排程方法莫過於使用先來先服務策略（FCFS）。但這種方法會使系統利用率低下。
常見的回填有兩種，保守的和積極的。在保守的回填中，每個任務在進入系統時都會被賦予一個保留值。當不會造成前面的任務延遲時，一個較小的任務才會被提前。 在積極的回填中，只有隊首的任務才會被賦予保留值。只要它不影響處於隊首的任務，一個較小的任務就會被提前處理。在FCFS策略下，一個任務的優先權是它的等待時間（wait time）。其它的優先權策略如最短任務優先（SF），擴展因素（XF）也可以被使用。在SF下，一個任務的優先權與其用戶期望值（user estimated run time）成反比。在XF下，任務的優先權為由以下公式定義的XFactor（擴展因素）
XFactor = (Wait time + Estimated Run time) / Estimated Run time
最常見的用以衡量排程方案效果的指標是平均完成時間和平均總體延遲（average bounded slowdown）在我們的研究中也採用了這些指標。一個任務的總體延遲被如下定義：
Bounded Slowdown = (Wait time + Max(Run time, 10))/ Max(Run time, 10)
門限值10用於限制耗時極短的任務對於觀測指標的影響。
