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
|
import bisect
|
22
|
import logging
|
23
|
from operator import itemgetter, attrgetter
|
24
|
|
25
|
VMRR_ONLY = False
|
26
|
|
27
|
"""This module provides an in-memory slot table data structure.
|
28
|
|
29
|
A slot table is essentially just a collection of resource reservations, and is
|
30
|
implemented using the classes ResourceTuple, ResourceReservation, Node, and
|
31
|
KeyValueWrapper, and SlotTable. See the documentation in these classes for
|
32
|
additional details.
|
33
|
|
34
|
This module also provides an "availability window" implementation, which provides
|
35
|
easier access to the contents of a slot table (by determining the availability
|
36
|
in each node starting at a given time). The availability window is implemented
|
37
|
in classes ChangepointAvail, ChangepointNodeAvail, AvailEntry, OngoingAvailability,
|
38
|
and AvailabilityWindow.
|
39
|
|
40
|
"""
|
41
|
|
42
|
|
43
|
class ResourceTuple(object):
|
44
|
"""A resource tuple
|
45
|
|
46
|
This is an internal data structure used by the slot table. To
|
47
|
manipulate "quantities of resources" in Haizea, use L{Capacity}
|
48
|
instead.
|
49
|
|
50
|
A resource tuple represents a quantity of resources. For example,
|
51
|
"50% of a CPU and 512 MB of memory" is a resource tuple with two
|
52
|
components (CPU and memory). The purpose of having a class for this
|
53
|
(instead of a simpler structure, like a list or dictionary) is to
|
54
|
be able to perform certain basic operations, like determining whether
|
55
|
one tuple "fits" in another (e.g., the previous tuple fits in
|
56
|
"100% of CPU and 1024 MB of memory", but in "100% of CPU and 256 MB
|
57
|
of memory".
|
58
|
|
59
|
A resource tuple is tightly coupled to a particular slot table. So,
|
60
|
if a slot table defines that each node has "CPUs, memory, and disk space",
|
61
|
the resource tuples will depend on this definition (the specification
|
62
|
of valid resources is not repeated in each resource tuple object).
|
63
|
|
64
|
Resources in a resource tuple can be of two types: single instance and
|
65
|
multi instance. Memory is an example of a single instance resource: there
|
66
|
is only "one" memory in a node (with some capacity). CPUs are an example
|
67
|
of a multi instance resource: there can be multiple CPUs in a single node,
|
68
|
and each CPU can be used to satisfy a requirement for a CPU.
|
69
|
|
70
|
"""
|
71
|
SINGLE_INSTANCE = 1
|
72
|
MULTI_INSTANCE = 2
|
73
|
|
74
|
def __init__(self, slottable, single_instance, multi_instance = None):
|
75
|
"""Constructor. Should only be called from SlotTable.
|
76
|
|
77
|
The constructor is not meant to be called directly and should only
|
78
|
be called from SlotTable.
|
79
|
|
80
|
The res parameter is a list with the quantities of each resource.
|
81
|
The list starts with the single-instance resources, followed
|
82
|
by the multi-instance resources. The slottable contains information
|
83
|
about the layout of this list:
|
84
|
|
85
|
- The mapping of resource to position in the list is contained in attribute
|
86
|
rtuple_restype2pos of the slottable.
|
87
|
- For single-instance resources, the position returned by this mapping contains
|
88
|
the quantity.
|
89
|
- For multi-instance resources, the position returns the
|
90
|
quantity of the first instance. The number of instances of a given resource
|
91
|
is contained in attribute rtuple_nres of the slottable.
|
92
|
- The number of single-instance resources is contained in attribute rtuple_len of
|
93
|
the slottable.
|
94
|
|
95
|
@param slottable: Slot table
|
96
|
@type slottable: L{SlotTable}
|
97
|
@param single_instance: Quantities of single instance resources
|
98
|
@type single_instance: C{list}
|
99
|
@param multi_instance: Quantities of multi instance resources
|
100
|
@type multi_instance: C{dict}
|
101
|
"""
|
102
|
|
103
|
self.slottable = slottable
|
104
|
"""
|
105
|
Slot table
|
106
|
@type: SlotTable
|
107
|
"""
|
108
|
|
109
|
self._single_instance = single_instance
|
110
|
"""
|
111
|
Resource quantities
|
112
|
@type: list
|
113
|
"""
|
114
|
|
115
|
self._multi_instance = multi_instance
|
116
|
"""
|
117
|
Resource quantities
|
118
|
@type: dict
|
119
|
"""
|
120
|
|
121
|
@classmethod
|
122
|
def copy(cls, rt):
|
123
|
"""Creates a deep copy of a resource tuple
|
124
|
|
125
|
@param rt: Resource tuple to copy
|
126
|
@type rt: L{ResourceTuple}
|
127
|
@return: Copy of resource tuple
|
128
|
@rtype: L{ResourceTuple}
|
129
|
"""
|
130
|
if rt.slottable.rtuple_has_multiinst:
|
131
|
return cls(rt.slottable, rt._single_instance[:], dict([(pos,l[:]) for pos, l in rt._multi_instance.items()]))
|
132
|
else:
|
133
|
return cls(rt.slottable, rt._single_instance[:], {})
|
134
|
|
135
|
|
136
|
def fits_in(self, rt):
|
137
|
"""Determines if this resource tuple fits in a given resource tuple
|
138
|
|
139
|
@param rt: Resource tuple
|
140
|
@type rt: L{ResourceTuple}
|
141
|
@return: True if this resource tuple fits in rt. False otherwise.
|
142
|
@rtype: bool
|
143
|
"""
|
144
|
|
145
|
|
146
|
|
147
|
|
148
|
for i in xrange(self.slottable.rtuple_nsingle):
|
149
|
if self._single_instance[i] > rt._single_instance[i]:
|
150
|
return False
|
151
|
|
152
|
|
153
|
|
154
|
|
155
|
|
156
|
if self.slottable.rtuple_has_multiinst:
|
157
|
|
158
|
|
159
|
_multi_instance2 = dict([(i, l[:]) for (i,l) in rt._multi_instance.items()])
|
160
|
for (pos, l) in self._multi_instance.items():
|
161
|
insts = _multi_instance2[pos]
|
162
|
for quantity in l:
|
163
|
fits = False
|
164
|
for i in range(len(insts)):
|
165
|
if quantity <= insts[i]:
|
166
|
fits = True
|
167
|
insts[i] -= quantity
|
168
|
break
|
169
|
if fits == False:
|
170
|
return False
|
171
|
return True
|
172
|
|
173
|
|
174
|
def incr(self, rt):
|
175
|
"""Increases the resource tuple with the amounts in a given resource tuple
|
176
|
|
177
|
@param rt: Resource tuple
|
178
|
@type rt: L{ResourceTuple}
|
179
|
"""
|
180
|
for slottype in xrange(self.slottable.rtuple_nsingle):
|
181
|
self._single_instance[slottype] += rt._single_instance[slottype]
|
182
|
if self.slottable.rtuple_has_multiinst:
|
183
|
for (pos, l) in rt._multi_instance.items():
|
184
|
self._multi_instance[pos] += l[:]
|
185
|
|
186
|
def decr(self, rt):
|
187
|
"""Decreases the resource tuple with the amounts in a given resource tuple
|
188
|
|
189
|
Precondition: rt must be known to fit in the resource tuple (via fits_in)
|
190
|
|
191
|
@param rt: Resource tuple
|
192
|
@type rt: L{ResourceTuple}
|
193
|
"""
|
194
|
for slottype in xrange(self.slottable.rtuple_nsingle):
|
195
|
self._single_instance[slottype] -= rt._single_instance[slottype]
|
196
|
|
197
|
|
198
|
|
199
|
|
200
|
|
201
|
if self.slottable.rtuple_has_multiinst:
|
202
|
for (pos, l) in rt._multi_instance.items():
|
203
|
insts = self._multi_instance[pos]
|
204
|
for quantity in l:
|
205
|
fits = False
|
206
|
for i in range(len(insts)):
|
207
|
if quantity <= insts[i]:
|
208
|
fits = True
|
209
|
insts[i] -= quantity
|
210
|
break
|
211
|
if fits == False:
|
212
|
|
213
|
raise Exception, "Can't decrease"
|
214
|
|
215
|
|
216
|
|
217
|
def get_by_type(self, restype):
|
218
|
"""Gets the amount of a given resource type.
|
219
|
|
220
|
@param restype: Resource type
|
221
|
@type restype: C{str}
|
222
|
@return: For single-instance resources, returns the amount. For multi-instance
|
223
|
resources, returns the sum of all the instances.
|
224
|
@rtype: int
|
225
|
"""
|
226
|
pos = self.slottable.rtuple_restype2pos[restype]
|
227
|
if pos < self.slottable.rtuple_nsingle:
|
228
|
return self._single_instance[pos]
|
229
|
else:
|
230
|
return sum(self._multi_instance[pos])
|
231
|
|
232
|
|
233
|
def any_less(self, rt):
|
234
|
"""Determines if any amount of a resource is less than that in a given resource tuple
|
235
|
|
236
|
In the case of multi-instance resources, this method will only work when both
|
237
|
resource tuples have the same number of instances, and makes the comparison
|
238
|
instance by instance. For example, if a CPU resource has two instances A and B:
|
239
|
___A__B_
|
240
|
R1|75 50
|
241
|
R2|50 75
|
242
|
|
243
|
R2.any_less(R1) returns True. However:
|
244
|
|
245
|
___A__B_
|
246
|
R1|75 50
|
247
|
R2|75 50
|
248
|
|
249
|
R2.any_less(R1) returns False, even though one instance (R2.B) is less than another (R1.A)
|
250
|
|
251
|
@param rt: Resource tuple
|
252
|
@type rt: L{ResourceTuple}
|
253
|
@return: True if these is any resource such that its amount is less than that in rt.
|
254
|
@rtype: int
|
255
|
"""
|
256
|
for i in xrange(self.slottable.rtuple_nsingle):
|
257
|
if self._single_instance[i] < rt._single_instance[i]:
|
258
|
return True
|
259
|
|
260
|
if self.slottable.rtuple_has_multiinst:
|
261
|
for (pos, l) in self._multi_instance.items():
|
262
|
for i, x in enumerate(l):
|
263
|
if l[i] < rt._multi_instance[pos][i]:
|
264
|
return True
|
265
|
|
266
|
return False
|
267
|
|
268
|
def min(self, rt):
|
269
|
"""Modifies the resource amounts to the minimum of the current amount and that in the given resource tuple
|
270
|
|
271
|
As in any_less, for multi-instance resources this method will only work when both
|
272
|
resource tuples have the same number of instances, and makes the change
|
273
|
instance by instance.
|
274
|
|
275
|
@param rt: Resource tuple
|
276
|
@type rt: L{ResourceTuple}
|
277
|
"""
|
278
|
for i in xrange(self.slottable.rtuple_nsingle):
|
279
|
self._single_instance[i] = min(self._single_instance[i], rt._single_instance[i])
|
280
|
|
281
|
if self.slottable.rtuple_has_multiinst:
|
282
|
for (pos, l) in self._multi_instance.items():
|
283
|
for i, x in enumerate(l):
|
284
|
l[i] = min(l[i], rt._multi_instance[pos][i])
|
285
|
|
286
|
|
287
|
def __repr__(self):
|
288
|
"""Creates a string representation of the resource tuple
|
289
|
|
290
|
@return: String representation
|
291
|
@rtype: C{str}
|
292
|
"""
|
293
|
r=""
|
294
|
for i, x in enumerate(self._single_instance):
|
295
|
r += "%s:%i " % (i, x)
|
296
|
if self.slottable.rtuple_has_multiinst:
|
297
|
r+= `self._multi_instance`
|
298
|
return r
|
299
|
|
300
|
def __eq__(self, rt):
|
301
|
"""Determines if the resource tuple is equal to a given resource tuple
|
302
|
|
303
|
@return: True if they equal, False otherwise
|
304
|
@rtype: C{str}
|
305
|
"""
|
306
|
return self._single_instance == rt._single_instance and self._multi_instance == rt._multi_instance
|
307
|
|
308
|
def __getstate__(self):
|
309
|
"""Returns state necessary to unpickle a ResourceTuple object
|
310
|
|
311
|
"""
|
312
|
return (self._single_instance, self._multi_instance)
|
313
|
|
314
|
def __setstate__(self, state):
|
315
|
"""Restores state when unpickling a ResourceTuple object
|
316
|
|
317
|
After unpickling, the object still has to be bound to a slottable.
|
318
|
"""
|
319
|
self.slottable = None
|
320
|
self._single_instance = state[0]
|
321
|
self._multi_instance = state[1]
|
322
|
|
323
|
|
324
|
class ResourceReservation(object):
|
325
|
"""A resource reservation
|
326
|
|
327
|
A resource reservation (or RR) is a data structure representing resources
|
328
|
(represented as a ResourceTuple) reserved across multiple physical nodes.
|
329
|
(each node can have a different resource tuple; e.g., 1 CPU and
|
330
|
512 MB of memory in node 1 and 2 CPUs and 1024 MB of memory in node 2). An RR
|
331
|
has a specific start and end time for all the nodes. Thus, if some nodes are
|
332
|
reserved for an interval of time, and other nodes are reserved for a different
|
333
|
interval (even if these reservations are for the same lease), two separate RRs
|
334
|
would have to be added to the slot table.
|
335
|
|
336
|
This class isn't used by itself but rather serves as the base class for
|
337
|
VM reservations, image transfer reservations, etc.
|
338
|
"""
|
339
|
|
340
|
|
341
|
STATE_SCHEDULED = 0
|
342
|
STATE_ACTIVE = 1
|
343
|
STATE_DONE = 2
|
344
|
|
345
|
|
346
|
state_str = {STATE_SCHEDULED : "Scheduled",
|
347
|
STATE_ACTIVE : "Active",
|
348
|
STATE_DONE : "Done"}
|
349
|
|
350
|
def __init__(self, lease, start, end, res):
|
351
|
"""Constructor
|
352
|
|
353
|
@param lease: Lease this resource reservation belongs to
|
354
|
@type lease: L{Lease}
|
355
|
@param start: Starting time of the reservation
|
356
|
@type start: L{DateTime}
|
357
|
@param end: Ending time of the reservation
|
358
|
@type end: L{DateTime}
|
359
|
@param res: A dictionary mapping physical node ids to ResourceTuple objects
|
360
|
@type res: C{dict}
|
361
|
"""
|
362
|
self.lease = lease
|
363
|
self.start = start
|
364
|
self.end = end
|
365
|
self.state = None
|
366
|
self.resources_in_pnode = res
|
367
|
|
368
|
def print_contents(self, loglevel=constants.LOGLEVEL_VDEBUG):
|
369
|
"""Prints the contents of the RR to the log
|
370
|
|
371
|
@param loglevel: Log level
|
372
|
@type loglevel: C{str}
|
373
|
"""
|
374
|
logger = logging.getLogger("LEASES")
|
375
|
logger.log(loglevel, "Start : %s" % self.start)
|
376
|
logger.log(loglevel, "End : %s" % self.end)
|
377
|
logger.log(loglevel, "State : %s" % ResourceReservation.state_str[self.state])
|
378
|
logger.log(loglevel, "Resources : \n %s" % "\n ".join(["N%i: %s" %(i, x) for i, x in self.resources_in_pnode.items()]))
|
379
|
|
380
|
|
381
|
class SlotTable(object):
|
382
|
"""Slot table
|
383
|
|
384
|
The slot table is one of the main data structures in Haizea (if not *the* main one).
|
385
|
It tracks the capacity of the physical nodes on which leases can be scheduled,
|
386
|
contains the resource reservations of all the leases, and allows efficient access
|
387
|
to them.
|
388
|
|
389
|
However, the information in the slot table is stored in a somewhat 'raw' format
|
390
|
(a collection of L{ResourceReservation}s) which can be hard to use directly. So,
|
391
|
one of the responsabilities of the slot table is to efficiently generate "availability
|
392
|
windows", which are a more convenient abstraction over available resources. See
|
393
|
AvailabilityWindow for more details. When writing a custom mapper, most read-only
|
394
|
interactions with the slot table should be through availability windows, which can
|
395
|
be obtained through the get_availability_window method of SlotTable.
|
396
|
|
397
|
The slot table also depends on classes L{Node} and L{KeyValueWrapper}.
|
398
|
|
399
|
Since querying resource reservations is the most frequent operation in Haizea, the
|
400
|
slot table tries to optimize access to them as much as possible. In particular,
|
401
|
we will often need to quickly access reservations starting or ending at a specific
|
402
|
time (or in an interval of time). The current slot table implementation stores the RRs
|
403
|
in two ordered lists: one by starting time and another by ending time. Access is done by
|
404
|
binary search in O(log n) time using the C{bisect} module. Insertion and removal
|
405
|
require O(n) time, since lists are implemented internally as arrays in CPython.
|
406
|
We could improve these times in the future by using a tree structure (which Python
|
407
|
doesn't have natively, so we'd have to include our own tree implementation), although
|
408
|
slot table accesses far outweight insertion and removal operations.
|
409
|
|
410
|
"""
|
411
|
|
412
|
def __init__(self, resource_types):
|
413
|
"""Constructor
|
414
|
|
415
|
The slot table will be initially empty, without any physical nodes. These have to be added
|
416
|
with add_node.
|
417
|
|
418
|
@param resource_types: A dictionary mapping resource types to ResourceTuple.SINGLE_INSTANCE or
|
419
|
ResourceTuple.MULTI_INSTANCE (depending on whether the resource is single- or multi-instance)
|
420
|
@type resource_types: C{dict}
|
421
|
"""
|
422
|
self.logger = logging.getLogger("SLOT")
|
423
|
self.nodes = {}
|
424
|
self.reservations_by_start = []
|
425
|
self.reservations_by_end = []
|
426
|
self.resource_types = resource_types
|
427
|
self.availabilitycache = {}
|
428
|
self.awcache_time = None
|
429
|
self.awcache = None
|
430
|
self.state_stack = []
|
431
|
self.__dirty()
|
432
|
|
433
|
|
434
|
res_singleinstance = [rt for rt,ninst in resource_types if ninst == ResourceTuple.SINGLE_INSTANCE]
|
435
|
res_multiinstance = [(rt,ResourceTuple.MULTI_INSTANCE) for rt,ninst in resource_types if ninst > 1 ]
|
436
|
self.rtuple_nsingle = len(res_singleinstance)
|
437
|
self.rtuple_nmultiple = len(res_multiinstance)
|
438
|
self.rtuple_has_multiinst = self.rtuple_nmultiple > 0
|
439
|
self.rtuple_restype2pos = dict([(rt,i) for (i,rt) in enumerate(res_singleinstance)])
|
440
|
pos = self.rtuple_nsingle
|
441
|
for rt, ninst in res_multiinstance:
|
442
|
self.rtuple_restype2pos[rt] = pos
|
443
|
pos = pos + 1
|
444
|
|
445
|
def add_node(self, node_id, resourcetuple):
|
446
|
"""Add a new physical node to the slot table
|
447
|
|
448
|
@param node_id: Resource type
|
449
|
@type node_id: C{int}
|
450
|
@param resourcetuple: Resource type
|
451
|
@type resourcetuple: L{ResourceTuple}
|
452
|
"""
|
453
|
self.nodes[node_id] = Node(resourcetuple)
|
454
|
|
455
|
def create_empty_resource_tuple(self):
|
456
|
"""Create an empty resource tuple
|
457
|
|
458
|
@return: Empty resource tuple, single-instance resources set to zero, multi-instance resources
|
459
|
set to zero instances.
|
460
|
@rtype: L{ResourceTuple}
|
461
|
"""
|
462
|
return ResourceTuple(self, [0] * self.rtuple_nsingle, dict((pos,[]) for pos in xrange(self.rtuple_nsingle, self.rtuple_nsingle+self.rtuple_nmultiple)))
|
463
|
|
464
|
def create_resource_tuple_from_capacity(self, capacity):
|
465
|
"""Converts a L{Capacity} object to a L{ResourceTuple}
|
466
|
|
467
|
@param capacity: Resource capacity
|
468
|
@type capacity: L{Capacity}
|
469
|
@return: Resource tuple
|
470
|
@rtype: L{ResourceTuple}
|
471
|
"""
|
472
|
single_instance = [0] * self.rtuple_nsingle
|
473
|
multi_instance = dict([(pos,[]) for pos in xrange(self.rtuple_nsingle, self.rtuple_nsingle+self.rtuple_nmultiple)])
|
474
|
for restype in capacity.get_resource_types():
|
475
|
pos = self.rtuple_restype2pos[restype]
|
476
|
ninst = capacity.ninstances[restype]
|
477
|
if pos < self.rtuple_nsingle:
|
478
|
single_instance[pos] = capacity.get_quantity(restype)
|
479
|
else:
|
480
|
multi_instance[pos] = []
|
481
|
for i in range(ninst):
|
482
|
multi_instance[pos].append(capacity.get_quantity_instance(restype, i))
|
483
|
|
484
|
rt = ResourceTuple(self, single_instance, multi_instance)
|
485
|
|
486
|
return rt
|
487
|
|
488
|
def get_availability_window(self, start):
|
489
|
"""Creates an availability window starting at a given time.
|
490
|
|
491
|
@param start: Start of availability window.
|
492
|
@type start: L{DateTime}
|
493
|
@return: Availability window
|
494
|
@rtype: L{AvailabilityWindow}
|
495
|
"""
|
496
|
|
497
|
|
498
|
|
499
|
|
500
|
|
501
|
|
502
|
|
503
|
if self.awcache == None or start < self.awcache_time or (start >= self.awcache_time and not self.awcache.changepoints.has_key(start)):
|
504
|
if self.awcache != None and start < self.awcache_time:
|
505
|
self.__get_aw_cache_miss(start, include = [self.awcache_time])
|
506
|
else:
|
507
|
self.__get_aw_cache_miss(start)
|
508
|
|
509
|
return self.awcache
|
510
|
|
511
|
def get_availability(self, time, min_capacity=None):
|
512
|
"""Computes the available resources on all nodes at a given time.
|
513
|
|
514
|
@param time: Time at which to determine availability.
|
515
|
@type time: L{DateTime}
|
516
|
@param min_capacity: If not None, only include the nodes that have at least
|
517
|
this minimum capacity.
|
518
|
@type min_capacity: L{ResourceTuple}
|
519
|
@return: A dictionary mapping physical node id to a L{Node} object (which
|
520
|
contains the available capacity of that physical node at the specified time)
|
521
|
@rtype: C{dict}
|
522
|
"""
|
523
|
if not self.availabilitycache.has_key(time):
|
524
|
self.__get_availability_cache_miss(time)
|
525
|
|
526
|
|
527
|
nodes = self.availabilitycache[time]
|
528
|
|
529
|
|
530
|
if min_capacity != None:
|
531
|
newnodes = {}
|
532
|
for n, node in nodes.items():
|
533
|
if min_capacity.fits_in(node.capacity):
|
534
|
newnodes[n]=node
|
535
|
else:
|
536
|
pass
|
537
|
nodes = newnodes
|
538
|
|
539
|
return nodes
|
540
|
|
541
|
def is_empty(self):
|
542
|
"""Determines if the slot table is empty (has no reservations)
|
543
|
|
544
|
@return: True if there are no reservations, False otherwise.
|
545
|
@rtype: C{bool}
|
546
|
"""
|
547
|
return (len(self.reservations_by_start) == 0)
|
548
|
|
549
|
def is_full(self, time, restype):
|
550
|
"""Determines if a resource type is "full" at a specified time.
|
551
|
|
552
|
A resource type is considered to be "full" if its available capacity is zero
|
553
|
in all the physical nodes in the slot table.
|
554
|
|
555
|
@param time: time at which to check for fullness.
|
556
|
@type time: L{DateTime}
|
557
|
@param restype: Resource type
|
558
|
@type restype: C{str}
|
559
|
@return: True if the resource type is full, False otherwise.
|
560
|
@rtype: C{bool}
|
561
|
"""
|
562
|
nodes = self.get_availability(time)
|
563
|
avail = sum([node.capacity.get_by_type(restype) for node in nodes.values()])
|
564
|
return (avail == 0)
|
565
|
|
566
|
def get_total_capacity(self, restype):
|
567
|
"""Determines the aggregate capacity of a given resource type across all nodes.
|
568
|
|
569
|
@param restype: Resource type
|
570
|
@type restype: C{str}
|
571
|
@return: Total capacity
|
572
|
@rtype: C{int}
|
573
|
"""
|
574
|
return sum([n.capacity.get_by_type(restype) for n in self.nodes.values()])
|
575
|
|
576
|
def add_reservation(self, rr):
|
577
|
"""Adds a L{ResourceReservation} to the slot table.
|
578
|
|
579
|
@param rr: Resource reservation
|
580
|
@type rr: L{ResourceReservation}
|
581
|
"""
|
582
|
startitem = KeyValueWrapper(rr.start, rr)
|
583
|
enditem = KeyValueWrapper(rr.end, rr)
|
584
|
bisect.insort(self.reservations_by_start, startitem)
|
585
|
bisect.insort(self.reservations_by_end, enditem)
|
586
|
self.__dirty()
|
587
|
|
588
|
|
589
|
def update_reservation(self, rr, old_start, old_end):
|
590
|
"""Update a L{ResourceReservation} to the slot table.
|
591
|
|
592
|
Since the start and end time are used to index the reservations,
|
593
|
the old times have to be provided so we can find the old reservation
|
594
|
and make the changes.
|
595
|
|
596
|
@param rr: Resource reservation with updated values (including potentially new start and/or end times)
|
597
|
@type rr: L{ResourceReservation}
|
598
|
@param old_start: Start time of reservation before update.
|
599
|
@type old_start: L{DateTime}
|
600
|
@param old_end: End time of reservation before update.
|
601
|
@type old_end: L{DateTime}
|
602
|
"""
|
603
|
|
604
|
self.__remove_reservation(rr, old_start, old_end)
|
605
|
self.add_reservation(rr)
|
606
|
self.__dirty()
|
607
|
|
608
|
|
609
|
def remove_reservation(self, rr):
|
610
|
"""Remove a L{ResourceReservation} from the slot table.
|
611
|
|
612
|
@param rr: Resource reservation
|
613
|
@type rr: L{ResourceReservation}
|
614
|
"""
|
615
|
self.__remove_reservation(rr, rr.start, rr.end)
|
616
|
|
617
|
|
618
|
def get_reservations_at(self, time):
|
619
|
"""Get all reservations at a specified time
|
620
|
|
621
|
@param time: Time
|
622
|
@type time: L{DateTime}
|
623
|
@return: Resource reservations
|
624
|
@rtype: C{list} of L{ResourceReservation}s
|
625
|
"""
|
626
|
item = KeyValueWrapper(time, None)
|
627
|
startpos = bisect.bisect_right(self.reservations_by_start, item)
|
628
|
bystart = set([x.value for x in self.reservations_by_start[:startpos]])
|
629
|
endpos = bisect.bisect_right(self.reservations_by_end, item)
|
630
|
byend = set([x.value for x in self.reservations_by_end[endpos:]])
|
631
|
res = bystart & byend
|
632
|
return list(res)
|
633
|
|
634
|
def get_reservations_starting_between(self, start, end):
|
635
|
"""Get all reservations starting in a specified interval.
|
636
|
|
637
|
The interval is closed: it includes the starting time and the ending time.
|
638
|
|
639
|
@param start: Start of interval
|
640
|
@type start: L{DateTime}
|
641
|
@param end: End of interval
|
642
|
@type end: L{DateTime}
|
643
|
@return: Resource reservations
|
644
|
@rtype: C{list} of L{ResourceReservation}s
|
645
|
"""
|
646
|
startitem = KeyValueWrapper(start, None)
|
647
|
enditem = KeyValueWrapper(end, None)
|
648
|
startpos = bisect.bisect_left(self.reservations_by_start, startitem)
|
649
|
endpos = bisect.bisect_right(self.reservations_by_start, enditem)
|
650
|
res = [x.value for x in self.reservations_by_start[startpos:endpos]]
|
651
|
return res
|
652
|
|
653
|
def get_reservations_ending_between(self, start, end):
|
654
|
"""Get all reservations ending in a specified interval.
|
655
|
|
656
|
The interval is closed: it includes the starting time and the ending time.
|
657
|
|
658
|
@param start: Start of interval
|
659
|
@type start: L{DateTime}
|
660
|
@param end: End of interval
|
661
|
@type end: L{DateTime}
|
662
|
@return: Resource reservations
|
663
|
@rtype: C{list} of L{ResourceReservation}s
|
664
|
"""
|
665
|
startitem = KeyValueWrapper(start, None)
|
666
|
enditem = KeyValueWrapper(end, None)
|
667
|
startpos = bisect.bisect_left(self.reservations_by_end, startitem)
|
668
|
endpos = bisect.bisect_right(self.reservations_by_end, enditem)
|
669
|
res = [x.value for x in self.reservations_by_end[startpos:endpos]]
|
670
|
return res
|
671
|
|
672
|
def get_reservations_starting_after(self, start):
|
673
|
"""Get all reservations starting after (but not on) a specified time
|
674
|
|
675
|
@param start: Time
|
676
|
@type start: L{DateTime}
|
677
|
@return: Resource reservations
|
678
|
@rtype: C{list} of L{ResourceReservation}s
|
679
|
"""
|
680
|
startitem = KeyValueWrapper(start, None)
|
681
|
startpos = bisect.bisect_right(self.reservations_by_start, startitem)
|
682
|
res = [x.value for x in self.reservations_by_start[startpos:]]
|
683
|
return res
|
684
|
|
685
|
def get_reservations_ending_after(self, end):
|
686
|
"""Get all reservations ending after (but not on) a specified time
|
687
|
|
688
|
@param end: Time
|
689
|
@type end: L{DateTime}
|
690
|
@return: Resource reservations
|
691
|
@rtype: C{list} of L{ResourceReservation}s
|
692
|
"""
|
693
|
startitem = KeyValueWrapper(end, None)
|
694
|
startpos = bisect.bisect_right(self.reservations_by_end, startitem)
|
695
|
res = [x.value for x in self.reservations_by_end[startpos:]]
|
696
|
return res
|
697
|
|
698
|
def get_reservations_starting_on_or_after(self, start):
|
699
|
"""Get all reservations starting on or after a specified time
|
700
|
|
701
|
@param start: Time
|
702
|
@type start: L{DateTime}
|
703
|
@return: Resource reservations
|
704
|
@rtype: C{list} of L{ResourceReservation}s
|
705
|
"""
|
706
|
startitem = KeyValueWrapper(start, None)
|
707
|
startpos = bisect.bisect_left(self.reservations_by_start, startitem)
|
708
|
res = [x.value for x in self.reservations_by_start[startpos:]]
|
709
|
return res
|
710
|
|
711
|
def get_reservations_ending_on_or_after(self, end):
|
712
|
"""Get all reservations ending on or after a specified time
|
713
|
|
714
|
@param end: Time
|
715
|
@type end: L{DateTime}
|
716
|
@return: Resource reservations
|
717
|
@rtype: C{list} of L{ResourceReservation}s
|
718
|
"""
|
719
|
startitem = KeyValueWrapper(end, None)
|
720
|
startpos = bisect.bisect_left(self.reservations_by_end, startitem)
|
721
|
res = [x.value for x in self.reservations_by_end[startpos:]]
|
722
|
return res
|
723
|
|
724
|
|
725
|
def get_reservations_starting_at(self, time):
|
726
|
"""Get all reservations starting at a specified time
|
727
|
|
728
|
@param time: Time
|
729
|
@type time: L{DateTime}
|
730
|
@return: Resource reservations
|
731
|
@rtype: C{list} of L{ResourceReservation}s
|
732
|
"""
|
733
|
return self.get_reservations_starting_between(time, time)
|
734
|
|
735
|
def get_reservations_ending_at(self, time):
|
736
|
"""Get all reservations ending at a specified time
|
737
|
|
738
|
@param time: Time
|
739
|
@type time: L{DateTime}
|
740
|
@return: Resource reservations
|
741
|
@rtype: C{list} of L{ResourceReservation}s
|
742
|
"""
|
743
|
return self.get_reservations_ending_between(time, time)
|
744
|
|
745
|
def get_reservations_after(self, time):
|
746
|
"""Get all reservations that take place after (but not on) a
|
747
|
specified time. i.e., all reservations starting or ending after that time.
|
748
|
|
749
|
@param time: Time
|
750
|
@type time: L{DateTime}
|
751
|
@return: Resource reservations
|
752
|
@rtype: C{list} of L{ResourceReservation}s
|
753
|
"""
|
754
|
bystart = set(self.get_reservations_starting_after(time))
|
755
|
byend = set(self.get_reservations_ending_after(time))
|
756
|
return list(bystart | byend)
|
757
|
|
758
|
def get_reservations_on_or_after(self, time):
|
759
|
"""Get all reservations that take place on or after a
|
760
|
specified time. i.e., all reservations starting or ending after that time.
|
761
|
|
762
|
@param time: Time
|
763
|
@type time: L{DateTime}
|
764
|
@return: Resource reservations
|
765
|
@rtype: C{list} of L{ResourceReservation}s
|
766
|
"""
|
767
|
bystart = set(self.get_reservations_starting_on_or_after(time))
|
768
|
byend = set(self.get_reservations_ending_on_or_after(time))
|
769
|
return list(bystart | byend)
|
770
|
|
771
|
def get_changepoints_after(self, after, until=None, nodes=None):
|
772
|
"""Get all the changepoints after a given time.
|
773
|
|
774
|
A changepoint is any time anything is scheduled to change in the
|
775
|
slottable (a reservation starting or ending).
|
776
|
|
777
|
@param after: Time
|
778
|
@type after: L{DateTime}
|
779
|
@param until: If not None, only include changepoints until this time.
|
780
|
@type until: L{DateTime}
|
781
|
@param nodes: If not None, only include changepoints affecting these nodes.
|
782
|
@type nodes: C{list} of C{int}s
|
783
|
@return: Changepoints
|
784
|
@rtype: C{list} of L{DateTime}s
|
785
|
"""
|
786
|
changepoints = set()
|
787
|
res = self.get_reservations_after(after)
|
788
|
if VMRR_ONLY:
|
789
|
from haizea.core.scheduler.vm_scheduler import VMResourceReservation, SuspensionResourceReservation, ResumptionResourceReservation, ShutdownResourceReservation
|
790
|
vmrrs = set([r for r in res if isinstance(r, VMResourceReservation)])
|
791
|
vmrrs = vmrrs.union([r.vmrr for r in res if isinstance(r, SuspensionResourceReservation)
|
792
|
or isinstance(r, ResumptionResourceReservation)
|
793
|
or isinstance(r, ShutdownResourceReservation)
|
794
|
])
|
795
|
res = list(vmrrs)
|
796
|
for rr in res:
|
797
|
if VMRR_ONLY:
|
798
|
start = rr.get_first_start()
|
799
|
end = rr.get_final_end()
|
800
|
else:
|
801
|
start = rr.start
|
802
|
end = rr.end
|
803
|
if nodes == None or (nodes != None and len(set(rr.resources_in_pnode.keys()) & set(nodes)) > 0):
|
804
|
if start > after:
|
805
|
changepoints.add(start)
|
806
|
if end > after:
|
807
|
changepoints.add(end)
|
808
|
changepoints = list(changepoints)
|
809
|
if until != None:
|
810
|
changepoints = [c for c in changepoints if c < until]
|
811
|
changepoints.sort()
|
812
|
return changepoints
|
813
|
|
814
|
def get_next_changepoint(self, time):
|
815
|
"""Get the first changepoint after a given time.
|
816
|
|
817
|
@param time: Time
|
818
|
@type time: L{DateTime}
|
819
|
@return: Changepoints
|
820
|
@rtype: L{DateTime}
|
821
|
"""
|
822
|
item = KeyValueWrapper(time, None)
|
823
|
|
824
|
startpos = bisect.bisect_right(self.reservations_by_start, item)
|
825
|
if startpos == len(self.reservations_by_start):
|
826
|
time1 = None
|
827
|
else:
|
828
|
time1 = self.reservations_by_start[startpos].value.start
|
829
|
|
830
|
endpos = bisect.bisect_right(self.reservations_by_end, item)
|
831
|
if endpos == len(self.reservations_by_end):
|
832
|
time2 = None
|
833
|
else:
|
834
|
time2 = self.reservations_by_end[endpos].value.end
|
835
|
|
836
|
if time1==None and time2==None:
|
837
|
return None
|
838
|
elif time1==None:
|
839
|
return time2
|
840
|
elif time2==None:
|
841
|
return time1
|
842
|
else:
|
843
|
return min(time1, time2)
|
844
|
|
845
|
|
846
|
|
847
|
def get_next_premature_end(self, after):
|
848
|
"""Get the first premature end time after a given time. ONLY FOR SIMULATION.
|
849
|
|
850
|
In simulation, some reservations can end prematurely, and this information
|
851
|
is stored in the slot table (in real life, this information is not
|
852
|
known a priori).
|
853
|
|
854
|
@param after: Time
|
855
|
@type after: L{DateTime}
|
856
|
@return: Next premature end
|
857
|
@rtype: L{DateTime}
|
858
|
"""
|
859
|
from haizea.core.scheduler.vm_scheduler import VMResourceReservation
|
860
|
|
861
|
res = [i.value for i in self.reservations_by_end if isinstance(i.value, VMResourceReservation) and i.value.prematureend > after]
|
862
|
if len(res) > 0:
|
863
|
prematureends = [r.prematureend for r in res]
|
864
|
prematureends.sort()
|
865
|
return prematureends[0]
|
866
|
else:
|
867
|
return None
|
868
|
|
869
|
|
870
|
def get_prematurely_ending_res(self, time):
|
871
|
"""Gets all the L{ResourceReservation}s that are set to end prematurely at a given time. ONLY FOR SIMULATION
|
872
|
|
873
|
@param time: Time
|
874
|
@type time: L{DateTime}
|
875
|
@return: Resource reservations
|
876
|
@rtype: C{list} of L{ResourceReservation}s
|
877
|
"""
|
878
|
from haizea.core.scheduler.vm_scheduler import VMResourceReservation
|
879
|
return [i.value for i in self.reservations_by_end if isinstance(i.value, VMResourceReservation) and i.value.prematureend == time]
|
880
|
|
881
|
def push_state(self, leases = []):
|
882
|
self.logger.debug("Saving slottable state, and leases %s" % [l.id for l in leases])
|
883
|
reservations_by_start = self.reservations_by_start[:]
|
884
|
reservations_by_end = self.reservations_by_end[:]
|
885
|
|
886
|
orig_lease_data = dict([(l,l.get_state()) for l in leases])
|
887
|
orig_vmrrs = dict([(l,l.vm_rrs[:]) for l in leases])
|
888
|
orig_vmrrs_data = {}
|
889
|
for orig_vmrr in orig_vmrrs.values():
|
890
|
for vmrr in orig_vmrr:
|
891
|
orig_vmrrs_data[vmrr] = (vmrr.start, vmrr.end, vmrr.prematureend, vmrr.pre_rrs[:], vmrr.post_rrs[:])
|
892
|
|
893
|
self.state_stack.append((reservations_by_start, reservations_by_end, orig_lease_data, orig_vmrrs, orig_vmrrs_data))
|
894
|
|
895
|
|
896
|
def pop_state(self, discard = False):
|
897
|
reservations_by_start, reservations_by_end, orig_lease_data, orig_vmrrs, orig_vmrrs_data = self.state_stack.pop()
|
898
|
|
899
|
if not discard:
|
900
|
self.logger.debug("Popping slottable state, and leases %s" % [l.id for l in orig_vmrrs.keys()])
|
901
|
self.reservations_by_start = reservations_by_start
|
902
|
self.reservations_by_end = reservations_by_end
|
903
|
|
904
|
for l in orig_lease_data:
|
905
|
l.state_machine.state = orig_lease_data[l]
|
906
|
|
907
|
for l in orig_vmrrs:
|
908
|
l.vm_rrs = orig_vmrrs[l]
|
909
|
for vm_rr in l.vm_rrs:
|
910
|
vm_rr.start = orig_vmrrs_data[vm_rr][0]
|
911
|
vm_rr.end = orig_vmrrs_data[vm_rr][1]
|
912
|
vm_rr.prematureend = orig_vmrrs_data[vm_rr][2]
|
913
|
vm_rr.pre_rrs = orig_vmrrs_data[vm_rr][3]
|
914
|
vm_rr.post_rrs = orig_vmrrs_data[vm_rr][4]
|
915
|
|
916
|
self.__dirty()
|
917
|
else:
|
918
|
self.logger.debug("Popping (but NOT restoring) slottable state, and leases %s" % [l.id for l in orig_vmrrs.keys()])
|
919
|
|
920
|
|
921
|
|
922
|
def __remove_reservation(self, rr, start=None, end=None):
|
923
|
"""Remove a L{ResourceReservation} from the slot table.
|
924
|
|
925
|
@param rr: Resource reservation
|
926
|
@type rr: L{ResourceReservation}
|
927
|
@param start: Start time under which the reservation is indexed, in cases where the RR
|
928
|
has changed (this parameter is only used when calling this method from update_reservation)
|
929
|
@type start: L{DateTime}
|
930
|
@param end: Same as start, but for the end time for the RR.
|
931
|
@type end: L{DateTime}
|
932
|
"""
|
933
|
if start == None:
|
934
|
start = rr.start
|
935
|
if end == None:
|
936
|
end = rr.end
|
937
|
posstart = self.__get_reservation_index(self.reservations_by_start, rr, start)
|
938
|
posend = self.__get_reservation_index(self.reservations_by_end, rr, end)
|
939
|
del self.reservations_by_start[posstart]
|
940
|
del self.reservations_by_end[posend]
|
941
|
self.__dirty()
|
942
|
|
943
|
|
944
|
def __get_availability_cache_miss(self, time):
|
945
|
"""Computes availability at a given time, and caches it.
|
946
|
|
947
|
Called when get_availability can't use availabilities in the cache.
|
948
|
|
949
|
@param time: Time at which to determine availability.
|
950
|
@type time: L{DateTime}
|
951
|
"""
|
952
|
allnodes = set(self.nodes.keys())
|
953
|
nodes = {}
|
954
|
reservations = self.get_reservations_at(time)
|
955
|
|
956
|
|
957
|
for r in reservations:
|
958
|
for node in r.resources_in_pnode:
|
959
|
if not nodes.has_key(node):
|
960
|
n = self.nodes[node]
|
961
|
nodes[node] = Node(n.capacity)
|
962
|
nodes[node].capacity.decr(r.resources_in_pnode[node])
|
963
|
|
964
|
|
965
|
missing = allnodes - set(nodes.keys())
|
966
|
for node in missing:
|
967
|
nodes[node] = self.nodes[node]
|
968
|
|
969
|
self.availabilitycache[time] = nodes
|
970
|
|
971
|
def __get_aw_cache_miss(self, time, include = []):
|
972
|
"""Computes availability window at a given time, and caches it.
|
973
|
|
974
|
Called when get_availability_window can't use the cached availability window.
|
975
|
|
976
|
@param time: Start of availability window.
|
977
|
@type time: L{DateTime}
|
978
|
"""
|
979
|
self.awcache = AvailabilityWindow(self, time, include)
|
980
|
self.awcache_time = time
|
981
|
|
982
|
def __dirty(self):
|
983
|
"""Empties the caches.
|
984
|
|
985
|
Should be called whenever the caches become dirty (e.g., when a reservation
|
986
|
is added to the slot table).
|
987
|
|
988
|
"""
|
989
|
|
990
|
|
991
|
self.availabilitycache = {}
|
992
|
self.awcache_time = None
|
993
|
self.awcache = None
|
994
|
|
995
|
def __get_reservation_index(self, rlist, rr, time):
|
996
|
"""Find the index of a resource reservation in one of the internal reservation lists
|
997
|
|
998
|
@param rlist: Resource reservation
|
999
|
@type rlist: C{list} of L{ResourceReservation}s
|
1000
|
@param rr: Resource reservation to look up
|
1001
|
@type rr: L{ResourceReservation}
|
1002
|
@param time: time the reservation is indexed under
|
1003
|
@type time: L{DateTime}
|
1004
|
"""
|
1005
|
item = KeyValueWrapper(time, None)
|
1006
|
pos = bisect.bisect_left(rlist, item)
|
1007
|
found = False
|
1008
|
while not found:
|
1009
|
if id(rlist[pos].value) == id(rr):
|
1010
|
found = True
|
1011
|
else:
|
1012
|
pos += 1
|
1013
|
return pos
|
1014
|
|
1015
|
def sanity_check(self, only_at = None):
|
1016
|
"""Verifies the slot table is consistent. Used by unit tests.
|
1017
|
|
1018
|
@return: Returns a tuple, the first item being True if the slot table
|
1019
|
is in a consistent state, and False otherwise. If the slot table is not
|
1020
|
in a consistent state, the remaining values in the tuple are the
|
1021
|
offending node, the offending changepoint, and the available resources
|
1022
|
in the node at the changepoint.
|
1023
|
@rtype: (C{bool},
|
1024
|
"""
|
1025
|
|
1026
|
if only_at != None:
|
1027
|
changepoints = [only_at]
|
1028
|
else:
|
1029
|
changepoints = set()
|
1030
|
for rr in [x.value for x in self.reservations_by_start]:
|
1031
|
changepoints.add(rr.start)
|
1032
|
changepoints.add(rr.end)
|
1033
|
changepoints = list(changepoints)
|
1034
|
changepoints.sort()
|
1035
|
|
1036
|
for cp in changepoints:
|
1037
|
avail = self.get_availability(cp)
|
1038
|
for node in avail:
|
1039
|
for resource in avail[node].capacity._single_instance:
|
1040
|
if resource < 0:
|
1041
|
return False, node, cp, avail[node].capacity
|
1042
|
|
1043
|
return True, None, None, None
|
1044
|
|
1045
|
|
1046
|
|
1047
|
class Node(object):
|
1048
|
"""A physical node in the slot table."""
|
1049
|
|
1050
|
def __init__(self, capacity):
|
1051
|
"""Constructor
|
1052
|
|
1053
|
@param capacity: Capacity of the node
|
1054
|
@type capacity: L{ResourceTuple}
|
1055
|
"""
|
1056
|
self.capacity = ResourceTuple.copy(capacity)
|
1057
|
|
1058
|
|
1059
|
class KeyValueWrapper(object):
|
1060
|
"""A wrapper around L{ResourceReservations} so we can use the bisect module
|
1061
|
to manage ordered lists of reservations."""
|
1062
|
|
1063
|
def __init__(self, key, value):
|
1064
|
"""Constructor
|
1065
|
|
1066
|
@param key: Time under which the reservation should be indexed
|
1067
|
@type key: L{DateTime}
|
1068
|
@param value: Resource reservation
|
1069
|
@type value: L{ResourceReservation}
|
1070
|
"""
|
1071
|
self.key = key
|
1072
|
self.value = value
|
1073
|
|
1074
|
def __cmp__(self, other):
|
1075
|
return cmp(self.key, other.key)
|
1076
|
|
1077
|
|
1078
|
class AvailabilityWindow(object):
|
1079
|
"""An availability window
|
1080
|
|
1081
|
A particularly important operation with the slot table is determining the
|
1082
|
"availability window" of resources starting at a given time. In a nutshell,
|
1083
|
an availability window provides a convenient abstraction over the slot table,
|
1084
|
with methods to answer questions like "If I want to start a least at time T,
|
1085
|
are there enough resources available to start the lease?" "Will those resources
|
1086
|
be available until time T+t?" "If not, what's the longest period of time those
|
1087
|
resources will be available?" etc.
|
1088
|
|
1089
|
AvailabilityWindow objects are not meant to be created directly, and should be
|
1090
|
created through the SlotTable's get_availability_window method.
|
1091
|
|
1092
|
"""
|
1093
|
def __init__(self, slottable, time, include):
|
1094
|
"""Constructor
|
1095
|
|
1096
|
An availability window starts at a specific time, provided to the constructor.
|
1097
|
|
1098
|
@param slottable: Slot table the availability window is based upon.
|
1099
|
@type slottable: L{SlotTable}
|
1100
|
@param time: Starting time of the availability window.
|
1101
|
@type time: L{DateTime}
|
1102
|
"""
|
1103
|
self.slottable = slottable
|
1104
|
self.logger = logging.getLogger("SLOTTABLE.WIN")
|
1105
|
self.time = time
|
1106
|
self.leases = set()
|
1107
|
|
1108
|
self.cp_list = list(set([self.time] + self.slottable.get_changepoints_after(time) + include))
|
1109
|
self.cp_list.sort()
|
1110
|
|
1111
|
|
1112
|
|
1113
|
|
1114
|
|
1115
|
|
1116
|
|
1117
|
|
1118
|
|
1119
|
|
1120
|
|
1121
|
|
1122
|
|
1123
|
|
1124
|
self.changepoints = dict([(cp,ChangepointAvail()) for cp in self.cp_list])
|
1125
|
|
1126
|
|
1127
|
for cp in self.changepoints.values():
|
1128
|
for node_id, node in self.slottable.nodes.items():
|
1129
|
cp.add_node(node_id, node.capacity)
|
1130
|
|
1131
|
|
1132
|
rrs = self.slottable.get_reservations_after(time)
|
1133
|
if VMRR_ONLY:
|
1134
|
from haizea.core.scheduler.vm_scheduler import VMResourceReservation, SuspensionResourceReservation, ResumptionResourceReservation, ShutdownResourceReservation
|
1135
|
vmrrs = set([r for r in rrs if isinstance(r, VMResourceReservation)])
|
1136
|
vmrrs = vmrrs.union([r.vmrr for r in rrs if isinstance(r, SuspensionResourceReservation)
|
1137
|
or isinstance(r, ResumptionResourceReservation)
|
1138
|
or isinstance(r, ShutdownResourceReservation)
|
1139
|
])
|
1140
|
rrs = list(vmrrs)
|
1141
|
rrs = [(r.get_first_start(), r) for r in rrs]
|
1142
|
rrs.sort(key=itemgetter(0))
|
1143
|
rrs = [r for s, r in rrs]
|
1144
|
else:
|
1145
|
rrs.sort(key=attrgetter("start"))
|
1146
|
|
1147
|
|
1148
|
pos = 0
|
1149
|
|
1150
|
|
1151
|
|
1152
|
|
1153
|
|
1154
|
for rr in rrs:
|
1155
|
|
1156
|
if rr.start == rr.end:
|
1157
|
continue
|
1158
|
|
1159
|
if VMRR_ONLY:
|
1160
|
start = rr.get_first_start()
|
1161
|
end = rr.get_final_end()
|
1162
|
else:
|
1163
|
start = rr.start
|
1164
|
end = rr.end
|
1165
|
|
1166
|
|
1167
|
while start >= self.time and self.cp_list[pos] != start:
|
1168
|
pos += 1
|
1169
|
|
1170
|
|
1171
|
lease = rr.lease
|
1172
|
self.leases.add(lease)
|
1173
|
|
1174
|
|
1175
|
|
1176
|
|
1177
|
if start >= self.time:
|
1178
|
start_cp = self.changepoints[start]
|
1179
|
else:
|
1180
|
start_cp = self.changepoints[self.time]
|
1181
|
|
1182
|
|
1183
|
start_cp.leases.add(lease)
|
1184
|
|
1185
|
|
1186
|
for node in rr.resources_in_pnode:
|
1187
|
start_cp.nodes[node].decr(rr.resources_in_pnode[node])
|
1188
|
start_cp.nodes[node].add_lease(lease, rr.resources_in_pnode[node])
|
1189
|
|
1190
|
|
1191
|
pos2 = pos + 1
|
1192
|
|
1193
|
while self.cp_list[pos2] < end:
|
1194
|
cp = self.changepoints[self.cp_list[pos2]]
|
1195
|
cp.leases.add(lease)
|
1196
|
for node in rr.resources_in_pnode:
|
1197
|
cp.nodes[node].decr(rr.resources_in_pnode[node])
|
1198
|
cp.nodes[node].add_lease(lease, rr.resources_in_pnode[node])
|
1199
|
|
1200
|
pos2 += 1
|
1201
|
|
1202
|
|
1203
|
|
1204
|
|
1205
|
|
1206
|
|
1207
|
prev_nodeavail = {}
|
1208
|
for node_id, node in self.changepoints[self.time].nodes.items():
|
1209
|
prev_nodeavail[node_id] = [node]
|
1210
|
|
1211
|
for cp in self.cp_list[1:]:
|
1212
|
for node_id, node in self.changepoints[cp].nodes.items():
|
1213
|
prev_nodes = prev_nodeavail[node_id]
|
1214
|
if prev_nodes[-1].available == node.available and prev_nodes[-1].leases == node.leases:
|
1215
|
prev_nodes.append(node)
|
1216
|
else:
|
1217
|
for prev_node in prev_nodes:
|
1218
|
prev_node.next_cp = cp
|
1219
|
prev_node.next_nodeavail = node
|
1220
|
prev_nodeavail[node_id] = [node]
|
1221
|
|
1222
|
|
1223
|
def get_availability(self, time, node):
|
1224
|
"""Determines the available capacity at a given time and node
|
1225
|
|
1226
|
@param time: Time
|
1227
|
@type time: L{DateTime}
|
1228
|
@param node: Node id
|
1229
|
@type node: C{int}
|
1230
|
@return: Available capacity
|
1231
|
@rtype: L{ResourceTuple}
|
1232
|
"""
|
1233
|
return self.changepoints[time].nodes[node].available
|
1234
|
|
1235
|
|
1236
|
def get_ongoing_availability(self, time, node, preempted_leases = []):
|
1237
|
"""Determines the available capacity from a given time onwards.
|
1238
|
|
1239
|
This method returns an L{OngoingAvailability} object (see that class's
|
1240
|
documentation for more details)
|
1241
|
|
1242
|
@param time: Time
|
1243
|
@type time: L{DateTime}
|
1244
|
@param node: Node id
|
1245
|
@type node: C{int}
|
1246
|
@param preempted_leases: List of leases that can be preempted.
|
1247
|
@type preempted_leases: C{list} of L{Lease}s
|
1248
|
@return: Ongoing availability (see L{OngoingAvailability} documentation for more details)
|
1249
|
@rtype: L{OngoingAvailability}
|
1250
|
"""
|
1251
|
return OngoingAvailability(self.changepoints[time].nodes[node], preempted_leases)
|
1252
|
|
1253
|
|
1254
|
def get_nodes_at(self, time):
|
1255
|
"""Get all the nodes at a given time.
|
1256
|
|
1257
|
@param time: Time
|
1258
|
@type time: L{DateTime}
|
1259
|
@return: Node ids
|
1260
|
@rtype: C{list} of C{int}
|
1261
|
"""
|
1262
|
return self.changepoints[time].nodes.keys()
|
1263
|
|
1264
|
def get_leases_at(self, node, time):
|
1265
|
"""Get leases scheduled on a node at a given time.
|
1266
|
|
1267
|
@param node: Node id
|
1268
|
@type node: C{int}
|
1269
|
@param time: Time
|
1270
|
@type time: L{DateTime}
|
1271
|
"""
|
1272
|
return self.changepoints[time].nodes[node].leases
|
1273
|
|
1274
|
def get_leases_between(self, from_time, until_time):
|
1275
|
"""Get all the leases scheduled in an interval.
|
1276
|
|
1277
|
This interval is semi-closed: It includes the start time but not the
|
1278
|
end time of the interval.
|
1279
|
|
1280
|
@param from_time: Start of interval
|
1281
|
@type from_time: L{DateTime}
|
1282
|
@param until_time: End of interval
|
1283
|
@type until_time: L{DateTime}
|
1284
|
@return: Leases
|
1285
|
@rtype: C{list} of L{Lease}s
|
1286
|
"""
|
1287
|
leases = set()
|
1288
|
for cp in self.cp_list:
|
1289
|
if cp < from_time:
|
1290
|
continue
|
1291
|
if cp >= until_time:
|
1292
|
break
|
1293
|
leases.update(self.changepoints[cp].leases)
|
1294
|
return list(leases)
|
1295
|
|
1296
|
def get_capacity_duration(self, node, time):
|
1297
|
"""Determine how much longer the capacity in a node will
|
1298
|
last, starting at a given time.
|
1299
|
|
1300
|
@param node: Node id
|
1301
|
@type node: C{int}
|
1302
|
@param time: Time
|
1303
|
@type time: L{DateTime}
|
1304
|
@return: Duration the capacity will last. If it will last indefinitely,
|
1305
|
None is returned.
|
1306
|
@rtype: L{DateTimeDelta}
|
1307
|
"""
|
1308
|
next_cp = self.changepoints[time].nodes[node].next_cp
|
1309
|
if next_cp == None:
|
1310
|
return None
|
1311
|
else:
|
1312
|
return next_cp - time
|
1313
|
|
1314
|
|
1315
|
class OngoingAvailability(object):
|
1316
|
"""Information about ongoing availability in a node
|
1317
|
|
1318
|
An OngoingAvailability object contains information not just about
|
1319
|
the availability starting at a given time, but also how that availability
|
1320
|
diminishes over time. Thus, it the object to use when determining
|
1321
|
if, starting at a given time, it is possible to fit some capacity
|
1322
|
up to a certain time (with or without preempting other leases).
|
1323
|
|
1324
|
Typically, you will want to create an OngoingAvailability object using
|
1325
|
the get_ongoing_availability method in L{AvailabilityWindow}
|
1326
|
"""
|
1327
|
|
1328
|
def __init__(self, node, preempted_leases):
|
1329
|
"""Constructor
|
1330
|
|
1331
|
@param node: Node and time from which to start determing availability, represented
|
1332
|
by a valid L{ChangepointNodeAvail} object from the L{AvailabilityWindow}.
|
1333
|
@type node: L{ChangepointNodeAvail}
|
1334
|
@param preempted_leases: List of leases that can be preempted.
|
1335
|
@type preempted_leases: C{list} of L{Lease}s
|
1336
|
"""
|
1337
|
avails = []
|
1338
|
prev_avail = None
|
1339
|
prev_node = None
|
1340
|
|
1341
|
|
1342
|
while node != None:
|
1343
|
if len(preempted_leases) == 0:
|
1344
|
available = ResourceTuple.copy(node.available)
|
1345
|
else:
|
1346
|
available = node.get_avail_withpreemption(preempted_leases)
|
1347
|
|
1348
|
if prev_avail != None and available.any_less(prev_avail.available):
|
1349
|
available.min(prev_avail.available)
|
1350
|
availentry = AvailEntry(available, None)
|
1351
|
avails.append(availentry)
|
1352
|
prev_avail.until = prev_node.next_cp
|
1353
|
prev_avail = availentry
|
1354
|
elif prev_avail == None:
|
1355
|
availentry = AvailEntry(available, None)
|
1356
|
avails.append(availentry)
|
1357
|
prev_avail = availentry
|
1358
|
|
1359
|
prev_node = node
|
1360
|
node = node.next_nodeavail
|
1361
|
|
1362
|
self.avail_list = avails
|
1363
|
|
1364
|
|
1365
|
def fits(self, capacity, until):
|
1366
|
"""Determine if there is enough capacity until a given time.
|
1367
|
|
1368
|
@param capacity: Capacity
|
1369
|
@type capacity: L{ResourceTuple}
|
1370
|
@param until: Time
|
1371
|
@type until: L{DateTime}
|
1372
|
@return: True if the given capacity can fit until the given time. False otherwise.
|
1373
|
@rtype: C{bool}
|
1374
|
"""
|
1375
|
for avail in self.avail_list:
|
1376
|
if avail.until == None or avail.until >= until:
|
1377
|
return capacity.fits_in(avail.available)
|
1378
|
|
1379
|
def latest_fit(self, capacity):
|
1380
|
"""Determine for how long we can fit a given capacity.
|
1381
|
|
1382
|
@param capacity: Capacity
|
1383
|
@type capacity: L{ResourceTuple}
|
1384
|
@return: The latest time at which the given capacity fits in the node.
|
1385
|
@rtype: L{DateTime}
|
1386
|
"""
|
1387
|
prev = None
|
1388
|
for avail in self.avail_list:
|
1389
|
if not capacity.fits_in(avail.available):
|
1390
|
return prev
|
1391
|
else:
|
1392
|
prev = avail.until
|
1393
|
|
1394
|
|
1395
|
|
1396
|
|
1397
|
|
1398
|
|
1399
|
class AvailEntry(object):
|
1400
|
def __init__(self, available, until):
|
1401
|
self.available = available
|
1402
|
self.until = until
|
1403
|
|
1404
|
class ChangepointAvail(object):
|
1405
|
def __init__(self):
|
1406
|
self.nodes = {}
|
1407
|
self.leases = set()
|
1408
|
|
1409
|
def add_node(self, node, capacity):
|
1410
|
self.nodes[node] = ChangepointNodeAvail(capacity)
|
1411
|
|
1412
|
class ChangepointNodeAvail(object):
|
1413
|
def __init__(self, capacity):
|
1414
|
self.capacity = capacity
|
1415
|
self.available = capacity
|
1416
|
self.leases = set()
|
1417
|
self.available_if_preempting = {}
|
1418
|
self.next_cp = None
|
1419
|
self.next_nodeavail = None
|
1420
|
|
1421
|
def decr(self, capacity):
|
1422
|
if self.capacity == self.available:
|
1423
|
self.available = ResourceTuple.copy(self.capacity)
|
1424
|
self.available.decr(capacity)
|
1425
|
|
1426
|
def add_lease(self, lease, capacity):
|
1427
|
if not lease in self.leases:
|
1428
|
self.leases.add(lease)
|
1429
|
self.available_if_preempting[lease] = ResourceTuple.copy(capacity)
|
1430
|
else:
|
1431
|
self.available_if_preempting[lease].incr(capacity)
|
1432
|
|
1433
|
def get_avail_withpreemption(self, leases):
|
1434
|
avail = ResourceTuple.copy(self.capacity)
|
1435
|
for l in self.available_if_preempting:
|
1436
|
if not l in leases:
|
1437
|
avail.decr(self.available_if_preempting[l])
|
1438
|
return avail
|
1439
|
|
1440
|
|
1441
|
|
1442
|
|
1443
|
|