# 单个资源预留的数据结构

1)每个作业都需要机器的k个时间单位。

2)机器一次只能执行一项工作。

3)时间是系统的一部分。未来的工作会在不同的时间来临。仅当在k个时间段内(之后和之前)不存在现有预约时, 才保留将来的工作。

4)每当作业完成时(或其保留时间加k等于当前时间), 就会将其从系统中删除。

``````Let time taken by a job (or k) be = 4

At time 0: Reservation request for a job at time 2 in
future comes in, reservation is done as machine
will be available (no conflicting reservations)
Reservations {2}

At time 3: Reservation requests at times 15, 7, 20 and 3.
Job at 7, 15 and 20 can be reserved, but at 3
cannot be reserved as it conflicts with a
reserved at 2.
Reservations {2, 7, 15, 20}

At time 6: Reservation requests at times 30, 17, 35 and 45
Jobs at 30, 35 and 45 are reserved, but at 17
cannot be reserved as it conflicts with a reserved
at 15.
Reservations {7, 15, 30, 35, 45}.
Note that job at 2 is removed as it must be finished by 6.``````

``````//A BST node to store future reservations
struct node
{
int time ; //reservation time
struct node *left, *right;
};

//A utility function to create a new BST node
struct node *newNode( int item)
{
struct node *temp =
( struct node *) malloc ( sizeof ( struct node));
temp-> time = item;
temp->left = temp->right = NULL;
return temp;
}

/* BST insert to process a new reservation request at
a given time (future time).  This function does
reservation only if there is no existing job within
k time frame of new job  */
struct node* insert( struct node* root, int time , int k)
{
/* If the tree is empty, return a new node */
if (root == NULL) return newNode( time );

//Check if this job conflicts with existing
//reservations
if (( time -k <root-> time ) && ( time +k> root-> time ))
return root;

/* Otherwise, recur down the tree */
if ( time <root-> time )
root->left  = insert(root->left, time , k);
else
root->right = insert(root->right, time , k);

/* return the (unchanged) node pointer */
return root;
}``````

• 回顶