1 |
632
|
borja
|
|
2 |
641
|
borja
|
|
3 |
|
|
|
4 |
632
|
borja
|
|
5 |
|
|
|
6 |
|
|
|
7 |
|
|
|
8 |
|
|
|
9 |
|
|
|
10 |
|
|
|
11 |
|
|
|
12 |
|
|
|
13 |
|
|
|
14 |
|
|
|
15 |
|
|
|
16 |
|
|
|
17 |
|
|
|
18 |
|
|
|
19 |
|
|
import haizea.common.constants as constants
|
20 |
|
|
from haizea.common.utils import xmlrpc_marshall_singlevalue
|
21 |
|
|
from math import floor
|
22 |
|
|
import bisect
|
23 |
|
|
import logging
|
24 |
|
|
from operator import attrgetter
|
25 |
|
|
|
26 |
|
|
"""This module provides an in-memory slot table data structure.
|
27 |
|
|
|
28 |
|
|
A slot table is essentially just a collection of resource reservations.
|
29 |
|
|
See the documentation for ResourceReservation, SlotTable, and AvailabilityWindow
|
30 |
|
|
for additional implementation details.
|
31 |
|
|
|
32 |
|
|
|
33 |
|
|
|
34 |
|
|
|
35 |
|
|
"""
|
36 |
|
|
|
37 |
|
|
|
38 |
|
|
class ResourceTuple(object):
|
39 |
|
|
"""A resource tuple
|
40 |
|
|
|
41 |
|
|
This class ...
|
42 |
|
|
|
43 |
|
|
"""
|
44 |
|
|
SINGLE_INSTANCE = 1
|
45 |
|
|
MULTI_INSTANCE = 2
|
46 |
|
|
|
47 |
|
|
def __init__(self, slottable, res):
|
48 |
|
|
self.slottable = slottable
|
49 |
|
|
self._res = res
|
50 |
|
|
if self.slottable.has_multiinst:
|
51 |
|
|
self.multiinst = dict([(i,[]) for i in range(self.slottable.rtuple_len, self.slottable.rtuple_nres)])
|
52 |
|
|
|
53 |
|
|
@classmethod
|
54 |
|
|
def copy(cls, rt):
|
55 |
|
|
rt2 = cls(rt.slottable, rt._res[:])
|
56 |
|
|
if rt.slottable.has_multiinst:
|
57 |
|
|
rt2.multiinst = dict([(i, l[:]) for (i,l) in rt.multiinst.items()])
|
58 |
|
|
return rt2
|
59 |
|
|
|
60 |
|
|
def fits_in(self, res2):
|
61 |
|
|
for i in xrange(self.slottable.rtuple_len):
|
62 |
|
|
if self._res[i] > res2._res[i]:
|
63 |
|
|
return False
|
64 |
|
|
if self.slottable.has_multiinst:
|
65 |
|
|
multiinst2 = dict([(i, l[:]) for (i,l) in res2.multiinst.items()])
|
66 |
|
|
for (pos, l) in self.multiinst.items():
|
67 |
|
|
insts = multiinst2[pos]
|
68 |
|
|
for quantity in l:
|
69 |
|
|
fits = False
|
70 |
|
|
for i in range(len(insts)):
|
71 |
|
|
if quantity <= insts[i]:
|
72 |
|
|
fits = True
|
73 |
|
|
insts[i] -= quantity
|
74 |
|
|
break
|
75 |
|
|
if fits == False:
|
76 |
|
|
return False
|
77 |
|
|
return True
|
78 |
|
|
|
79 |
|
|
def any_less(self, res2):
|
80 |
|
|
for i in xrange(self.slottable.rtuple_len):
|
81 |
|
|
if self._res[i] < res2._res[i]:
|
82 |
|
|
return True
|
83 |
|
|
return False
|
84 |
|
|
|
85 |
|
|
def min(self, res2):
|
86 |
|
|
for i in xrange(self.slottable.rtuple_len):
|
87 |
|
|
self._res[i] = min(self._res[i], res2._res[i])
|
88 |
|
|
|
89 |
|
|
def decr(self, res2):
|
90 |
|
|
for slottype in xrange(self.slottable.rtuple_len):
|
91 |
|
|
self._res[slottype] -= res2._res[slottype]
|
92 |
|
|
if self.slottable.has_multiinst:
|
93 |
|
|
for (pos, l) in res2.multiinst.items():
|
94 |
|
|
insts = self.multiinst[pos]
|
95 |
|
|
for quantity in l:
|
96 |
|
|
fits = False
|
97 |
|
|
for i in range(len(insts)):
|
98 |
|
|
if quantity <= insts[i]:
|
99 |
|
|
fits = True
|
100 |
|
|
insts[i] -= quantity
|
101 |
|
|
break
|
102 |
|
|
if fits == False:
|
103 |
|
|
raise Exception, "Can't decrease"
|
104 |
|
|
|
105 |
|
|
def incr(self, res2):
|
106 |
|
|
for slottype in xrange(self.slottable.rtuple_len):
|
107 |
|
|
self._res[slottype] += res2._res[slottype]
|
108 |
|
|
if self.slottable.has_multiinst:
|
109 |
|
|
for (pos, l) in res2.multiinst.items():
|
110 |
|
|
self.multiinst[pos] += l[:]
|
111 |
|
|
|
112 |
|
|
def get_by_type(self, restype):
|
113 |
|
|
return self._res[self.slottable.rtuple_restype2pos[restype]]
|
114 |
|
|
|
115 |
|
|
def is_zero_or_less(self):
|
116 |
|
|
return sum([v for v in self._res]) <= 0
|
117 |
|
|
|
118 |
|
|
def __repr__(self):
|
119 |
|
|
r=""
|
120 |
|
|
for i, x in enumerate(self._res):
|
121 |
|
|
r += "%s:%i " % (i, x)
|
122 |
|
|
if self.slottable.has_multiinst:
|
123 |
|
|
r+= `self.multiinst`
|
124 |
|
|
return r
|
125 |
|
|
|
126 |
|
|
def __eq__(self, res2):
|
127 |
|
|
return self._res == res2._res
|
128 |
|
|
|
129 |
|
|
def __cmp__(self, res2):
|
130 |
|
|
return cmp(self._res, res2._res)
|
131 |
|
|
|
132 |
|
|
class ResourceReservation(object):
|
133 |
|
|
"""A resource reservation
|
134 |
|
|
|
135 |
|
|
A resource reservation (or RR) is a data structure specifying that a certain
|
136 |
|
|
quantities of resources (represented as a ResourceTuple) are reserved across
|
137 |
|
|
several nodes (each node can have a different resource tuple; e.g., 1 CPU and
|
138 |
|
|
512 MB of memory in node 1 and 2 CPUs and 1024 MB of memory in node 2). An RR
|
139 |
|
|
has a specific start and end time for all the nodes. Thus, if some nodes are
|
140 |
|
|
reserved for an interval of time, and other nodes are reserved for a different
|
141 |
|
|
interval (even if these reservations are for the same lease), two separate RRs
|
142 |
|
|
would have to be added to the slot table.
|
143 |
|
|
|
144 |
|
|
"""
|
145 |
|
|
|
146 |
|
|
|
147 |
|
|
STATE_SCHEDULED = 0
|
148 |
|
|
STATE_ACTIVE = 1
|
149 |
|
|
STATE_DONE = 2
|
150 |
|
|
|
151 |
|
|
|
152 |
|
|
state_str = {STATE_SCHEDULED : "Scheduled",
|
153 |
|
|
STATE_ACTIVE : "Active",
|
154 |
|
|
STATE_DONE : "Done"}
|
155 |
|
|
|
156 |
|
|
def __init__(self, lease, start, end, res):
|
157 |
|
|
self.lease = lease
|
158 |
|
|
self.start = start
|
159 |
|
|
self.end = end
|
160 |
|
|
self.state = None
|
161 |
|
|
self.resources_in_pnode = res
|
162 |
|
|
self.logger = logging.getLogger("LEASES")
|
163 |
|
|
|
164 |
|
|
def print_contents(self, loglevel=constants.LOGLEVEL_VDEBUG):
|
165 |
|
|
self.logger.log(loglevel, "Start : %s" % self.start)
|
166 |
|
|
self.logger.log(loglevel, "End : %s" % self.end)
|
167 |
|
|
self.logger.log(loglevel, "State : %s" % ResourceReservation.state_str[self.state])
|
168 |
|
|
self.logger.log(loglevel, "Resources : \n %s" % "\n ".join(["N%i: %s" %(i, x) for i, x in self.resources_in_pnode.items()]))
|
169 |
|
|
|
170 |
|
|
def xmlrpc_marshall(self):
|
171 |
|
|
|
172 |
|
|
rr = {}
|
173 |
|
|
rr["start"] = xmlrpc_marshall_singlevalue(self.start)
|
174 |
|
|
rr["end"] = xmlrpc_marshall_singlevalue(self.end)
|
175 |
|
|
rr["state"] = self.state
|
176 |
|
|
return rr
|
177 |
|
|
|
178 |
|
|
class Node(object):
|
179 |
|
|
def __init__(self, capacity):
|
180 |
|
|
self.capacity = ResourceTuple.copy(capacity)
|
181 |
|
|
|
182 |
|
|
|
183 |
|
|
class KeyValueWrapper(object):
|
184 |
|
|
def __init__(self, key, value):
|
185 |
|
|
self.key = key
|
186 |
|
|
self.value = value
|
187 |
|
|
|
188 |
|
|
def __cmp__(self, other):
|
189 |
|
|
return cmp(self.key, other.key)
|
190 |
|
|
|
191 |
|
|
|
192 |
|
|
class SlotTable(object):
|
193 |
|
|
"""Slot Table
|
194 |
|
|
|
195 |
|
|
The slot table is, by far, the most used data structure in Haizea, we need to
|
196 |
|
|
optimize access to these reservations. In particular, we will often need to quickly
|
197 |
|
|
access reservations starting or ending at a specific time (or in an interval of time).
|
198 |
|
|
The current slot table implementation stores the RRs in two ordered lists: one
|
199 |
|
|
by starting time and another by ending time. Access is done by binary search in O(log n)
|
200 |
|
|
time. Insertion and removal require O(n) time, since lists are implemented internally
|
201 |
|
|
as arrays in CPython. We could improve these times in the future by using a
|
202 |
|
|
tree structure (which Python doesn't have natively, so we'd have to include
|
203 |
|
|
our own tree implementation), although slot table accesses far outweight insertion
|
204 |
|
|
and removal operations. The slot table is implemented with classes SlotTable,
|
205 |
|
|
Node, NodeList, and KeyValueWrapper.
|
206 |
|
|
|
207 |
|
|
"""
|
208 |
|
|
|
209 |
|
|
def __init__(self, resource_types):
|
210 |
|
|
self.logger = logging.getLogger("SLOT")
|
211 |
|
|
self.nodes = {}
|
212 |
|
|
self.resource_types = resource_types
|
213 |
|
|
self.reservations_by_start = []
|
214 |
|
|
self.reservations_by_end = []
|
215 |
|
|
self.__dirty()
|
216 |
|
|
|
217 |
|
|
|
218 |
|
|
res_singleinstance = [rt for rt,ninst in resource_types if ninst == ResourceTuple.SINGLE_INSTANCE]
|
219 |
|
|
self.rtuple_len = len(res_singleinstance)
|
220 |
|
|
self.rtuple_nres = len(resource_types)
|
221 |
|
|
res_multiinstance = [(rt,ninst) for rt,ninst in resource_types if ninst == ResourceTuple.MULTI_INSTANCE]
|
222 |
|
|
self.has_multiinst = len(res_multiinstance) > 0
|
223 |
|
|
self.rtuple_restype2pos = dict([(rt,i) for (i,rt) in enumerate(res_singleinstance)])
|
224 |
|
|
pos = self.rtuple_len
|
225 |
|
|
for rt, ninst in res_multiinstance:
|
226 |
|
|
self.rtuple_restype2pos[rt] = pos
|
227 |
|
|
pos = pos + 1
|
228 |
|
|
|
229 |
|
|
def add_node(self, node_id, resourcetuple):
|
230 |
|
|
self.nodes[node_id] = Node(resourcetuple)
|
231 |
|
|
|
232 |
|
|
def create_empty_resource_tuple(self):
|
233 |
|
|
return ResourceTuple(self, [0] * self.rtuple_len)
|
234 |
|
|
|
235 |
|
|
def create_resource_tuple_from_capacity(self, capacity):
|
236 |
|
|
rt = ResourceTuple(self, [0] * self.rtuple_len)
|
237 |
|
|
for restype in capacity.get_resource_types():
|
238 |
|
|
pos = self.rtuple_restype2pos[restype]
|
239 |
|
|
if pos < self.rtuple_len:
|
240 |
|
|
rt._res[pos] = capacity.get_quantity(restype)
|
241 |
|
|
else:
|
242 |
|
|
ninst = capacity.ninstances[restype]
|
243 |
|
|
for i in range(ninst):
|
244 |
|
|
rt.multiinst[pos].append(capacity.get_quantity_instance(restype, i))
|
245 |
|
|
|
246 |
|
|
return rt
|
247 |
|
|
|
248 |
|
|
def is_empty(self):
|
249 |
|
|
return (len(self.reservations_by_start) == 0)
|
250 |
|
|
|
251 |
|
|
def is_full(self, time, restype):
|
252 |
|
|
nodes = self.get_availability(time)
|
253 |
|
|
avail = sum([node.capacity.get_by_type(restype) for node in nodes.values()])
|
254 |
|
|
return (avail == 0)
|
255 |
|
|
|
256 |
|
|
def get_total_capacity(self, restype):
|
257 |
|
|
return sum([n.capacity.get_by_type(restype) for n in self.nodes.values()])
|
258 |
|
|
|
259 |
|
|
def get_reservations_at(self, time):
|
260 |
|
|
item = KeyValueWrapper(time, None)
|
261 |
|
|
startpos = bisect.bisect_right(self.reservations_by_start, item)
|
262 |
|
|
bystart = set([x.value for x in self.reservations_by_start[:startpos]])
|
263 |
|
|
endpos = bisect.bisect_right(self.reservations_by_end, item)
|
264 |
|
|
byend = set([x.value for x in self.reservations_by_end[endpos:]])
|
265 |
|
|
res = bystart & byend
|
266 |
|
|
return list(res)
|
267 |
|
|
|
268 |
|
|
def get_reservations_starting_between(self, start, end):
|
269 |
|
|
startitem = KeyValueWrapper(start, None)
|
270 |
|
|
enditem = KeyValueWrapper(end, None)
|
271 |
|
|
startpos = bisect.bisect_left(self.reservations_by_start, startitem)
|
272 |
|
|
endpos = bisect.bisect_right(self.reservations_by_start, enditem)
|
273 |
|
|
res = [x.value for x in self.reservations_by_start[startpos:endpos]]
|
274 |
|
|
return res
|
275 |
|
|
|
276 |
|
|
def get_reservations_starting_after(self, start):
|
277 |
|
|
startitem = KeyValueWrapper(start, None)
|
278 |
|
|
startpos = bisect.bisect_right(self.reservations_by_start, startitem)
|
279 |
|
|
res = [x.value for x in self.reservations_by_start[startpos:]]
|
280 |
|
|
return res
|
281 |
|
|
|
282 |
|
|
def get_reservations_ending_after(self, end):
|
283 |
|
|
startitem = KeyValueWrapper(end, None)
|
284 |
|
|
startpos = bisect.bisect_right(self.reservations_by_end, startitem)
|
285 |
|
|
res = [x.value for x in self.reservations_by_end[startpos:]]
|
286 |
|
|
return res
|
287 |
|
|
|
288 |
|
|
def get_reservations_starting_on_or_after(self, start):
|
289 |
|
|
startitem = KeyValueWrapper(start, None)
|
290 |
|
|
startpos = bisect.bisect_left(self.reservations_by_start, startitem)
|
291 |
|
|
res = [x.value for x in self.reservations_by_start[startpos:]]
|
292 |
|
|
return res
|
293 |
|
|
|
294 |
|
|
def get_reservations_ending_on_or_after(self, end):
|
295 |
|
|
startitem = KeyValueWrapper(end, None)
|
296 |
|
|
startpos = bisect.bisect_left(self.reservations_by_end, startitem)
|
297 |
|
|
res = [x.value for x in self.reservations_by_end[startpos:]]
|
298 |
|
|
return res
|
299 |
|
|
|
300 |
|
|
def get_reservations_ending_between(self, start, end):
|
301 |
|
|
startitem = KeyValueWrapper(start, None)
|
302 |
|
|
enditem = KeyValueWrapper(end, None)
|
303 |
|
|
startpos = bisect.bisect_left(self.reservations_by_end, startitem)
|
304 |
|
|
endpos = bisect.bisect_right(self.reservations_by_end, enditem)
|
305 |
|
|
res = [x.value for x in self.reservations_by_end[startpos:endpos]]
|
306 |
|
|
return res
|
307 |
|
|
|
308 |
|
|
def get_reservations_starting_at(self, time):
|
309 |
|
|
return self.get_reservations_starting_between(time, time)
|
310 |
|
|
|
311 |
|
|
def get_reservations_ending_at(self, time):
|
312 |
|
|
return self.get_reservations_ending_between(time, time)
|
313 |
|
|
|
314 |
|
|
def get_reservations_after(self, time):
|
315 |
|
|
bystart = set(self.get_reservations_starting_after(time))
|
316 |
|
|
byend = set(self.get_reservations_ending_after(time))
|
317 |
|
|
return list(bystart | byend)
|
318 |
|
|
|
319 |
|
|
def get_reservations_on_or_after(self, time):
|
320 |
|
|
bystart = set(self.get_reservations_starting_on_or_after(time))
|
321 |
|
|
byend = set(self.get_reservations_ending_on_or_after(time))
|
322 |
|
|
return list(bystart | byend)
|
323 |
|
|
|
324 |
|
|
def get_changepoints_after(self, after, until=None, nodes=None):
|
325 |
|
|
changepoints = set()
|
326 |
|
|
res = self.get_reservations_after(after)
|
327 |
|
|
for rr in res:
|
328 |
|
|
if nodes == None or (nodes != None and len(set(rr.resources_in_pnode.keys()) & set(nodes)) > 0):
|
329 |
|
|
if rr.start > after:
|
330 |
|
|
changepoints.add(rr.start)
|
331 |
|
|
if rr.end > after:
|
332 |
|
|
changepoints.add(rr.end)
|
333 |
|
|
changepoints = list(changepoints)
|
334 |
|
|
if until != None:
|
335 |
|
|
changepoints = [c for c in changepoints if c < until]
|
336 |
|
|
changepoints.sort()
|
337 |
|
|
return changepoints
|
338 |
|
|
|
339 |
|
|
def add_reservation(self, rr):
|
340 |
|
|
startitem = KeyValueWrapper(rr.start, rr)
|
341 |
|
|
enditem = KeyValueWrapper(rr.end, rr)
|
342 |
|
|
bisect.insort(self.reservations_by_start, startitem)
|
343 |
|
|
bisect.insort(self.reservations_by_end, enditem)
|
344 |
|
|
self.__dirty()
|
345 |
|
|
|
346 |
|
|
|
347 |
|
|
|
348 |
|
|
def update_reservation(self, rr):
|
349 |
|
|
|
350 |
|
|
self.remove_reservation(rr)
|
351 |
|
|
self.add_reservation(rr)
|
352 |
|
|
self.__dirty()
|
353 |
|
|
|
354 |
|
|
|
355 |
|
|
|
356 |
|
|
|
357 |
|
|
def update_reservation_with_key_change(self, rr, old_start, old_end):
|
358 |
|
|
|
359 |
|
|
self.remove_reservation(rr, old_start, old_end)
|
360 |
|
|
self.add_reservation(rr)
|
361 |
|
|
self.__dirty()
|
362 |
|
|
|
363 |
|
|
def remove_reservation(self, rr, start=None, end=None):
|
364 |
|
|
if start == None:
|
365 |
|
|
start = rr.start
|
366 |
|
|
if end == None:
|
367 |
|
|
end = rr.end
|
368 |
|
|
posstart = self.__get_reservation_index(self.reservations_by_start, rr, start)
|
369 |
|
|
posend = self.__get_reservation_index(self.reservations_by_end, rr, end)
|
370 |
|
|
self.reservations_by_start.pop(posstart)
|
371 |
|
|
self.reservations_by_end.pop(posend)
|
372 |
|
|
self.__dirty()
|
373 |
|
|
|
374 |
|
|
def get_availability(self, time, min_capacity=None):
|
375 |
|
|
if not self.availabilitycache.has_key(time):
|
376 |
|
|
self.__get_availability_cache_miss(time)
|
377 |
|
|
|
378 |
|
|
|
379 |
|
|
nodes = self.availabilitycache[time]
|
380 |
|
|
|
381 |
|
|
|
382 |
|
|
if min_capacity != None:
|
383 |
|
|
newnodes = {}
|
384 |
|
|
for n, node in nodes.items():
|
385 |
|
|
if min_capacity.fits_in(node.capacity):
|
386 |
|
|
newnodes[n]=node
|
387 |
|
|
else:
|
388 |
|
|
pass
|
389 |
|
|
nodes = newnodes
|
390 |
|
|
|
391 |
|
|
return nodes
|
392 |
|
|
|
393 |
|
|
def get_next_reservations_in_nodes(self, time, nodes, rr_type=None, immediately_next = False):
|
394 |
|
|
nodes = set(nodes)
|
395 |
|
|
rrs_in_nodes = []
|
396 |
|
|
earliest_end_time = {}
|
397 |
|
|
rrs = self.get_reservations_starting_after(time)
|
398 |
|
|
if rr_type != None:
|
399 |
|
|
rrs = [rr for rr in rrs if isinstance(rr, rr_type)]
|
400 |
|
|
|
401 |
|
|
|
402 |
|
|
for rr in rrs:
|
403 |
|
|
rr_nodes = set(rr.resources_in_pnode.keys())
|
404 |
|
|
if len(nodes & rr_nodes) > 0:
|
405 |
|
|
rrs_in_nodes.append(rr)
|
406 |
|
|
end = rr.end
|
407 |
|
|
for n in rr_nodes:
|
408 |
|
|
if not earliest_end_time.has_key(n):
|
409 |
|
|
earliest_end_time[n] = end
|
410 |
|
|
else:
|
411 |
|
|
if end < earliest_end_time[n]:
|
412 |
|
|
earliest_end_time[n] = end
|
413 |
|
|
|
414 |
|
|
if immediately_next:
|
415 |
|
|
|
416 |
|
|
|
417 |
|
|
rr_nodes_excl = set()
|
418 |
|
|
for n in nodes:
|
419 |
|
|
if earliest_end_time.has_key(n):
|
420 |
|
|
end = earliest_end_time[n]
|
421 |
|
|
rrs = [rr for rr in rrs_in_nodes if n in rr.resources_in_pnode.keys() and rr.start < end]
|
422 |
|
|
rr_nodes_excl.update(rrs)
|
423 |
|
|
rrs_in_nodes = list(rr_nodes_excl)
|
424 |
|
|
|
425 |
|
|
return rrs_in_nodes
|
426 |
|
|
|
427 |
|
|
def get_next_changepoint(self, time):
|
428 |
|
|
item = KeyValueWrapper(time, None)
|
429 |
|
|
|
430 |
|
|
startpos = bisect.bisect_right(self.reservations_by_start, item)
|
431 |
|
|
if startpos == len(self.reservations_by_start):
|
432 |
|
|
time1 = None
|
433 |
|
|
else:
|
434 |
|
|
time1 = self.reservations_by_start[startpos].value.start
|
435 |
|
|
|
436 |
|
|
endpos = bisect.bisect_right(self.reservations_by_end, item)
|
437 |
|
|
if endpos == len(self.reservations_by_end):
|
438 |
|
|
time2 = None
|
439 |
|
|
else:
|
440 |
|
|
time2 = self.reservations_by_end[endpos].value.end
|
441 |
|
|
|
442 |
|
|
if time1==None and time2==None:
|
443 |
|
|
return None
|
444 |
|
|
elif time1==None:
|
445 |
|
|
return time2
|
446 |
|
|
elif time2==None:
|
447 |
|
|
return time1
|
448 |
|
|
else:
|
449 |
|
|
return min(time1, time2)
|
450 |
|
|
|
451 |
|
|
def get_availability_window(self, start):
|
452 |
|
|
if self.awcache == None or start < self.awcache_time or (start >= self.awcache_time and not self.awcache.changepoints.has_key(start)):
|
453 |
|
|
self.__get_aw_cache_miss(start)
|
454 |
|
|
return self.awcache
|
455 |
|
|
|
456 |
|
|
def sanity_check(self):
|
457 |
|
|
|
458 |
|
|
changepoints = set()
|
459 |
|
|
for rr in [x.value for x in self.reservations_by_start]:
|
460 |
|
|
changepoints.add(rr.start)
|
461 |
|
|
changepoints.add(rr.end)
|
462 |
|
|
changepoints = list(changepoints)
|
463 |
|
|
changepoints.sort()
|
464 |
|
|
|
465 |
|
|
offending_node = None
|
466 |
|
|
offending_cp = None
|
467 |
|
|
offending_capacity = None
|
468 |
|
|
|
469 |
|
|
for cp in changepoints:
|
470 |
|
|
avail = self.get_availability(cp)
|
471 |
|
|
for node in avail:
|
472 |
|
|
for resource in avail[node].capacity._res:
|
473 |
|
|
if resource < 0:
|
474 |
|
|
return False, node, cp, avail[node].capacity
|
475 |
|
|
|
476 |
|
|
return True, None, None, None
|
477 |
|
|
|
478 |
|
|
|
479 |
|
|
def get_next_premature_end(self, after):
|
480 |
|
|
from haizea.core.scheduler.vm_scheduler import VMResourceReservation
|
481 |
|
|
|
482 |
|
|
res = [i.value for i in self.reservations_by_end if isinstance(i.value, VMResourceReservation) and i.value.prematureend > after]
|
483 |
|
|
if len(res) > 0:
|
484 |
|
|
prematureends = [r.prematureend for r in res]
|
485 |
|
|
prematureends.sort()
|
486 |
|
|
return prematureends[0]
|
487 |
|
|
else:
|
488 |
|
|
return None
|
489 |
|
|
|
490 |
|
|
|
491 |
|
|
def get_prematurely_ending_res(self, t):
|
492 |
|
|
from haizea.core.scheduler.vm_scheduler import VMResourceReservation
|
493 |
|
|
return [i.value for i in self.reservations_by_end if isinstance(i.value, VMResourceReservation) and i.value.prematureend == t]
|
494 |
|
|
|
495 |
|
|
|
496 |
|
|
def __get_reservation_index(self, rlist, rr, key):
|
497 |
|
|
item = KeyValueWrapper(key, None)
|
498 |
|
|
pos = bisect.bisect_left(rlist, item)
|
499 |
|
|
found = False
|
500 |
|
|
while not found:
|
501 |
|
|
if rlist[pos].value == rr:
|
502 |
|
|
found = True
|
503 |
|
|
else:
|
504 |
|
|
pos += 1
|
505 |
|
|
return pos
|
506 |
|
|
|
507 |
|
|
|
508 |
|
|
def __get_availability_cache_miss(self, time):
|
509 |
|
|
allnodes = set(self.nodes.keys())
|
510 |
|
|
nodes = {}
|
511 |
|
|
reservations = self.get_reservations_at(time)
|
512 |
|
|
|
513 |
|
|
|
514 |
|
|
for r in reservations:
|
515 |
|
|
for node in r.resources_in_pnode:
|
516 |
|
|
if not nodes.has_key(node):
|
517 |
|
|
n = self.nodes[node]
|
518 |
|
|
nodes[node] = Node(n.capacity)
|
519 |
|
|
nodes[node].capacity.decr(r.resources_in_pnode[node])
|
520 |
|
|
|
521 |
|
|
|
522 |
|
|
missing = allnodes - set(nodes.keys())
|
523 |
|
|
for node in missing:
|
524 |
|
|
nodes[node] = self.nodes[node]
|
525 |
|
|
|
526 |
|
|
self.availabilitycache[time] = nodes
|
527 |
|
|
|
528 |
|
|
def __get_aw_cache_miss(self, time):
|
529 |
|
|
self.awcache = AvailabilityWindow(self, time)
|
530 |
|
|
self.awcache_time = time
|
531 |
|
|
|
532 |
|
|
def __dirty(self):
|
533 |
|
|
|
534 |
|
|
|
535 |
|
|
self.availabilitycache = {}
|
536 |
|
|
self.awcache_time = None
|
537 |
|
|
self.awcache = None
|
538 |
|
|
|
539 |
|
|
|
540 |
|
|
|
541 |
|
|
|
542 |
|
|
|
543 |
|
|
class ChangepointAvail(object):
|
544 |
|
|
def __init__(self):
|
545 |
|
|
self.nodes = {}
|
546 |
|
|
self.leases = set()
|
547 |
|
|
|
548 |
|
|
def add_node(self, node, capacity):
|
549 |
|
|
self.nodes[node] = ChangepointNodeAvail(capacity)
|
550 |
|
|
|
551 |
|
|
class ChangepointNodeAvail(object):
|
552 |
|
|
def __init__(self, capacity):
|
553 |
|
|
self.capacity = capacity
|
554 |
|
|
self.available = ResourceTuple.copy(capacity)
|
555 |
|
|
self.leases = set()
|
556 |
|
|
self.available_if_preempting = {}
|
557 |
|
|
self.next_cp = None
|
558 |
|
|
self.next_nodeavail = None
|
559 |
|
|
|
560 |
|
|
def decr(self, capacity):
|
561 |
|
|
self.available.decr(capacity)
|
562 |
|
|
|
563 |
|
|
def add_lease(self, lease, capacity):
|
564 |
|
|
if not lease in self.leases:
|
565 |
|
|
self.leases.add(lease)
|
566 |
|
|
self.available_if_preempting[lease] = ResourceTuple.copy(capacity)
|
567 |
|
|
else:
|
568 |
|
|
self.available_if_preempting[lease].incr(capacity)
|
569 |
|
|
|
570 |
|
|
def get_avail_withpreemption(self, leases):
|
571 |
|
|
avail = ResourceTuple.copy(self.capacity)
|
572 |
|
|
for l in self.available_if_preempting:
|
573 |
|
|
if not l in leases:
|
574 |
|
|
avail.decr(self.available_if_preempting[l])
|
575 |
|
|
return avail
|
576 |
|
|
|
577 |
|
|
class AvailEntry(object):
|
578 |
|
|
def __init__(self, available, until):
|
579 |
|
|
self.available = available
|
580 |
|
|
self.until = until
|
581 |
|
|
|
582 |
|
|
class AvailabilityInNode(object):
|
583 |
|
|
def __init__(self, avail_list):
|
584 |
|
|
self.avail_list = avail_list
|
585 |
|
|
|
586 |
|
|
def fits(self, capacity, until):
|
587 |
|
|
for avail in self.avail_list:
|
588 |
|
|
if avail.until == None or avail.until >= until:
|
589 |
|
|
return capacity.fits_in(avail.available)
|
590 |
|
|
|
591 |
|
|
def latest_fit(self, capacity):
|
592 |
|
|
prev = None
|
593 |
|
|
for avail in self.avail_list:
|
594 |
|
|
if not capacity.fits_in(avail.available):
|
595 |
|
|
return prev
|
596 |
|
|
else:
|
597 |
|
|
prev = avail.until
|
598 |
|
|
|
599 |
|
|
def get_avail_at_end(self):
|
600 |
|
|
return self.avail_list[-1]
|
601 |
|
|
|
602 |
|
|
class AvailabilityWindow(object):
|
603 |
|
|
"""An availability window
|
604 |
|
|
|
605 |
|
|
A particularly important operation with the slot table is determining the
|
606 |
|
|
"availability window" of resources starting at a given time. In a nutshell,
|
607 |
|
|
an availability window provides a convenient abstraction over the slot table,
|
608 |
|
|
with methods to answer questions like "If I want to start a least at time T,
|
609 |
|
|
are there enough resources available to start the lease?" "Will those resources
|
610 |
|
|
be available until time T+t?" "If not, what's the longest period of time those
|
611 |
|
|
resources will be available?"
|
612 |
|
|
|
613 |
|
|
"""
|
614 |
|
|
def __init__(self, slottable, time):
|
615 |
|
|
self.slottable = slottable
|
616 |
|
|
self.logger = logging.getLogger("SLOTTABLE.WIN")
|
617 |
|
|
self.time = time
|
618 |
|
|
self.leases = set()
|
619 |
|
|
|
620 |
|
|
self.cp_list = [self.time] + self.slottable.get_changepoints_after(time)
|
621 |
|
|
|
622 |
|
|
|
623 |
|
|
self.changepoints = dict([(cp,ChangepointAvail()) for cp in self.cp_list])
|
624 |
|
|
|
625 |
|
|
for cp in self.changepoints.values():
|
626 |
|
|
for node_id, node in self.slottable.nodes.items():
|
627 |
|
|
cp.add_node(node_id, node.capacity)
|
628 |
|
|
|
629 |
|
|
rrs = self.slottable.get_reservations_after(time)
|
630 |
|
|
rrs.sort(key=attrgetter("start"))
|
631 |
|
|
pos = 0
|
632 |
|
|
|
633 |
|
|
|
634 |
|
|
for rr in rrs:
|
635 |
|
|
|
636 |
|
|
if rr.start == rr.end:
|
637 |
|
|
continue
|
638 |
|
|
|
639 |
|
|
while rr.start >= self.time and self.cp_list[pos] != rr.start:
|
640 |
|
|
pos += 1
|
641 |
|
|
lease = rr.lease
|
642 |
|
|
|
643 |
|
|
self.leases.add(lease)
|
644 |
|
|
|
645 |
|
|
if rr.start >= self.time:
|
646 |
|
|
start_cp = self.changepoints[rr.start]
|
647 |
|
|
else:
|
648 |
|
|
start_cp = self.changepoints[self.time]
|
649 |
|
|
|
650 |
|
|
start_cp.leases.add(lease)
|
651 |
|
|
for node in rr.resources_in_pnode:
|
652 |
|
|
start_cp.nodes[node].decr(rr.resources_in_pnode[node])
|
653 |
|
|
start_cp.nodes[node].add_lease(lease, rr.resources_in_pnode[node])
|
654 |
|
|
|
655 |
|
|
pos2 = pos + 1
|
656 |
|
|
|
657 |
|
|
while self.cp_list[pos2] < rr.end:
|
658 |
|
|
cp = self.changepoints[self.cp_list[pos2]]
|
659 |
|
|
cp.leases.add(lease)
|
660 |
|
|
for node in rr.resources_in_pnode:
|
661 |
|
|
cp.nodes[node].decr(rr.resources_in_pnode[node])
|
662 |
|
|
cp.nodes[node].add_lease(lease, rr.resources_in_pnode[node])
|
663 |
|
|
|
664 |
|
|
pos2 += 1
|
665 |
|
|
|
666 |
|
|
prev_nodeavail = {}
|
667 |
|
|
for node_id, node in self.changepoints[self.time].nodes.items():
|
668 |
|
|
prev_nodeavail[node_id] = [node]
|
669 |
|
|
|
670 |
|
|
|
671 |
|
|
for cp in self.cp_list[1:]:
|
672 |
|
|
for node_id, node in self.changepoints[cp].nodes.items():
|
673 |
|
|
prev_nodes = prev_nodeavail[node_id]
|
674 |
|
|
if prev_nodes[-1].available == node.available and prev_nodes[-1].leases == node.leases:
|
675 |
|
|
prev_nodes.append(node)
|
676 |
|
|
else:
|
677 |
|
|
for prev_node in prev_nodes:
|
678 |
|
|
prev_node.next_cp = cp
|
679 |
|
|
prev_node.next_nodeavail = node
|
680 |
|
|
prev_nodeavail[node_id] = [node]
|
681 |
|
|
|
682 |
|
|
|
683 |
|
|
def get_availability_at_node(self, time, node, preempted_leases = []):
|
684 |
|
|
avails = []
|
685 |
|
|
node = self.changepoints[time].nodes[node]
|
686 |
|
|
prev_avail = None
|
687 |
|
|
prev_node = None
|
688 |
|
|
while node != None:
|
689 |
|
|
if len(preempted_leases) == None:
|
690 |
|
|
available = ResourceTuple.copy(node.available)
|
691 |
|
|
else:
|
692 |
|
|
available = node.get_avail_withpreemption(preempted_leases)
|
693 |
|
|
|
694 |
|
|
if prev_avail != None and available.any_less(prev_avail.available):
|
695 |
|
|
available.min(prev_avail.available)
|
696 |
|
|
availentry = AvailEntry(available, None)
|
697 |
|
|
avails.append(availentry)
|
698 |
|
|
prev_avail.until = prev_node.next_cp
|
699 |
|
|
prev_avail = availentry
|
700 |
|
|
elif prev_avail == None:
|
701 |
|
|
availentry = AvailEntry(available, None)
|
702 |
|
|
avails.append(availentry)
|
703 |
|
|
prev_avail = availentry
|
704 |
|
|
|
705 |
|
|
prev_node = node
|
706 |
|
|
node = node.next_nodeavail
|
707 |
|
|
|
708 |
|
|
return AvailabilityInNode(avails)
|
709 |
|
|
|
710 |
|
|
def get_nodes_at(self, time):
|
711 |
|
|
return self.changepoints[time].nodes.keys()
|
712 |
|
|
|
713 |
|
|
def get_leases_at(self, node, time):
|
714 |
|
|
return self.changepoints[time].nodes[node].leases
|
715 |
|
|
|
716 |
|
|
def get_availability_at(self, node, time):
|
717 |
|
|
return self.changepoints[time].nodes[node].available
|
718 |
|
|
|
719 |
|
|
def get_capacity_interval(self, node, time):
|
720 |
|
|
next_cp = self.changepoints[time].nodes[node].next_cp
|
721 |
|
|
if next_cp == None:
|
722 |
|
|
return None
|
723 |
|
|
else:
|
724 |
|
|
return next_cp - time
|
725 |
|
|
|
726 |
|
|
def get_leases_until(self, until):
|
727 |
|
|
leases = set()
|
728 |
|
|
for cp in self.cp_list:
|
729 |
|
|
if until <= cp:
|
730 |
|
|
break
|
731 |
|
|
leases.update(self.changepoints[cp].leases)
|
732 |
|
|
return list(leases)
|