1
|
|
2
|
|
3
|
|
4
|
|
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)
|
733
|
|