File D:\maven-qcr-plugin-testsunitaires\qcr4java\jenkins-master\target\site\qc\core\src\main\java\hudson\model\queue\BackFiller.java.html

1 package hudson.model.queue;
2
3 import com.google.common.collect.Iterables;
4 import hudson.Extension;
5 import hudson.model.Computer;
6 import hudson.model.Executor;
7 import jenkins.model.Jenkins;
8 import hudson.model.InvisibleAction;
9 import hudson.model.Queue.BuildableItem;
10 import hudson.model.queue.MappingWorksheet.ExecutorChunk;
11 import hudson.model.queue.MappingWorksheet.ExecutorSlot;
12 import hudson.model.queue.MappingWorksheet.Mapping;
13 import hudson.model.queue.MappingWorksheet.WorkChunk;
14 import hudson.util.TimeUnit2;
15
16 import java.util.ArrayList;
17 import java.util.Collections;
18 import java.util.HashMap;
19 import java.util.List;
20 import java.util.Map;
21 import java.util.Map.Entry;
22
23 /**
24 * Experimental.
25 *
26 * @author Kohsuke Kawaguchi
27 */
28 public class BackFiller extends LoadPredictor {
29 private boolean recursion = false;
30
31 @Override
32 public Iterable<FutureLoad> predict(MappingWorksheet plan, Computer computer, long start, long end) {
33 TimeRange timeRange = new TimeRange(start, end - start);
34 List<FutureLoad> loads = new ArrayList<FutureLoad>();
35
36 for (BuildableItem bi : Jenkins.getInstance().getQueue().getBuildableItems()) {
37 TentativePlan tp = bi.getAction(TentativePlan.class);
38 if (tp==null) {// do this even for bi==plan.item ensures that we have FIFO semantics in tentative plans.
39 tp = makeTentativePlan(bi);
40 if (tp==null) continue; // no viable plan.
41 }
42
43 if (tp.isStale()) {
44 // if the tentative plan is stale, just keep on pushing it to the current time
45 // (if we recreate the plan, it'll be put at the end of the queue, whereas this job
46 // should actually get priority over others)
47 tp.range.shiftTo(System.currentTimeMillis());
48 }
49
50 // don't let its own tentative plan count when considering a scheduling for a job
51 if (plan.item==bi) continue;
52
53
54 // no overlap in the time span, meaning this plan is for a distant future
55 if (!timeRange.overlapsWith(tp.range)) continue;
56
57 // if this tentative plan has no baring on this computer, that's ignorable
58 Integer i = tp.footprint.get(computer);
59 if (i==null) continue;
60
61 return Collections.singleton(tp.range.toFutureLoad(i));
62 }
63
64 return loads;
65 }
66
67 private static final class PseudoExecutorSlot extends ExecutorSlot {
68 private Executor executor;
69
70 private PseudoExecutorSlot(Executor executor) {
71 this.executor = executor;
72 }
73
74 @Override
75 public Executor getExecutor() {
76 return executor;
77 }
78
79 @Override
80 public boolean isAvailable() {
81 return true;
82 }
83
84 // this slot isn't executable
85 @Override
86 protected void set(WorkUnit p) {
87 throw new UnsupportedOperationException();
88 }
89 }
90
91 private TentativePlan makeTentativePlan(BuildableItem bi) {
92 if (recursion) return null;
93 recursion = true;
94 try {
95 // pretend for now that all executors are available and decide some assignment that's executable.
96 List<PseudoExecutorSlot> slots = new ArrayList<PseudoExecutorSlot>();
97 for (Computer c : Jenkins.getInstance().getComputers()) {
98 if (c.isOffline()) continue;
99 for (Executor e : c.getExecutors()) {
100 slots.add(new PseudoExecutorSlot(e));
101 }
102 }
103
104 // also ignore all load predictions as we just want to figure out some executable assignment
105 // and we are not trying to figure out if this task is executable right now.
106 MappingWorksheet worksheet = new MappingWorksheet(bi, slots, Collections.<LoadPredictor>emptyList());
107 Mapping m = Jenkins.getInstance().getQueue().getLoadBalancer().map(bi.task, worksheet);
108 if (m==null) return null;
109
110 // figure out how many executors we need on each computer?
111 Map<Computer,Integer> footprint = new HashMap<Computer, Integer>();
112 for (Entry<WorkChunk, ExecutorChunk> e : m.toMap().entrySet()) {
113 Computer c = e.getValue().computer;
114 Integer v = footprint.get(c);
115 if (v==null) v = 0;
116 v += e.getKey().size();
117 footprint.put(c,v);
118 }
119
120 // the point of a tentative plan is to displace other jobs to create a point in time
121 // where this task can start executing. An incorrectly estimated duration is not
122 // a problem in this regard, as we just need enough idle executors in the right moment.
123 // The downside of guessing the duration wrong is that we can end up creating tentative plans
124 // afterward that may be incorrect, but those plans will be rebuilt.
125 long d = bi.task.getEstimatedDuration();
126 if (d<=0) d = TimeUnit2.MINUTES.toMillis(5);
127
128 TimeRange slot = new TimeRange(System.currentTimeMillis(), d);
129
130 // now, based on the real predicted loads, figure out the approximation of when we can
131 // start executing this guy.
132 for (Entry<Computer, Integer> e : footprint.entrySet()) {
133 Computer computer = e.getKey();
134 Timeline timeline = new Timeline();
135 for (LoadPredictor lp : LoadPredictor.all()) {
136 for (FutureLoad fl : Iterables.limit(lp.predict(worksheet, computer, slot.start, slot.end),100)) {
137 timeline.insert(fl.startTime, fl.startTime+fl.duration, fl.numExecutors);
138 }
139 }
140
141 Long x = timeline.fit(slot.start, slot.duration, computer.countExecutors()-e.getValue());
142 // if no suitable range was found in [slot.start,slot.end), slot.end would be a good approximation
143 if (x==null) x = slot.end;
144 slot = slot.shiftTo(x);
145 }
146
147 TentativePlan tp = new TentativePlan(footprint, slot);
148 bi.addAction(tp);
149 return tp;
150 } finally {
151 recursion = false;
152 }
153 }
154
155 /**
156 * Represents a duration in time.
157 */
158 private static final class TimeRange {
159 public final long start;
160 public final long duration;
161 public final long end;
162
163 private TimeRange(long start, long duration) {
164 this.start = start;
165 this.duration = duration;
166 this.end = start+duration;
167 }
168
169 public boolean overlapsWith(TimeRange that) {
170 return (this.start <= that.start && that.start <=this.end)
171 || (that.start <= this.start && this.start <=that.end);
172 }
173
174 public FutureLoad toFutureLoad(int size) {
175 return new FutureLoad(start,duration,size);
176 }
177
178 public TimeRange shiftTo(long newStart) {
179 if (newStart==start) return this;
180 return new TimeRange(newStart,duration);
181 }
182 }
183
184 public static final class TentativePlan extends InvisibleAction {
185 private final Map<Computer,Integer> footprint;
186 public final TimeRange range;
187
188 public TentativePlan(Map<Computer, Integer> footprint, TimeRange range) {
189 this.footprint = footprint;
190 this.range = range;
191 }
192
193 public Object writeReplace() {// don't persist
194 return null;
195 }
196
197 public boolean isStale() {
198 return range.end < System.currentTimeMillis();
199 }
200 }
201
202 /**
203 * Once this feature stabilizes, move it to the heavyjob plugin
204 */
205 @Extension
206 public static BackFiller newInstance() {
207 if (Boolean.getBoolean(BackFiller.class.getName()))
208 return new BackFiller();
209 return null;
210 }
211 }
212