/ref> It is used when a resource is shared among many users (for example bandwidth in a telecommunication link, or
disk capacity
Computer data storage is a technology consisting of computer components and recording media that are used to retain digital data. It is a core function and fundamental component of computers.
The central processing unit (CPU) of a computer ...
in a large data center
A data center (American English) or data centre (British English)See spelling differences. is a building, a dedicated space within a building, or a group of buildings used to house computer systems and associated components, such as telecommunic ...
).
The algorithm allows users to:
* check if an amount of resource is available during a specific period of time,
* reserve an amount of resource for a specific period of time,
* delete a previous reservation,
* move the calendar forward (the calendar covers a defined duration, and it must be moved forward as time goes by).
Principle
The calendar is stored as abinary tree
In computer science, a binary tree is a k-ary k = 2 tree data structure in which each node has at most two children, which are referred to as the ' and the '. A recursive definition using just set theory notions is that a (non-empty) binary t ...
where leaves represent elementary time periods. Other nodes represent the period of time covered by all their descendants.
The period of time covered by a reservation is represented by a set of "top-nodes". This set is the minimal set of nodes that exactly cover the reservation period of time.
A node of the binary tree
In computer science, a binary tree is a k-ary k = 2 tree data structure in which each node has at most two children, which are referred to as the ' and the '. A recursive definition using just set theory notions is that a (non-empty) binary t ...
is a "top-node" for a given reservation if
* all its descendants are inside the reservation period of time, and
* it is the root node, or at least one descendant of the parent node is outside of the reservation period of time.
The following value is stored in each node:
q(node) = max(q(left child), q(right child))
+ total amount of reserved resource for all reservations having this node as a "top-node"
(for code optimization, the two parts of this sum are usually stored separately.)
Performance
The advantage of this algorithm is that the time to register a new resource reservation depends only on the calendar size (it does not depend on the total number of reservations). Let be the number of elementary periods in the calendar. The maximal number of "top-nodes" for a given reservation is 2.log n. * to check if an amount of resource is available during a specific period of time : ''O''(log ''n'') * to reserve an amount of resource for a specific period of time : ''O''(log ''n'') * to delete a previous reservation : ''O''(log ''n'') * to move the calendar forward : ''O''(log ''n'' + M.log n) where is the number of reservations that are active during the added calendar periods. ( = 0 if reservations are not allowed after the end of the calendar.)References
External links
* {{in lang, fr}C source code
Scheduling algorithms