Database Reference
In-Depth Information
Available space
Used space
Initial queue:
6
5
4
3
2
1
First fit:
5
4
2
6
3
1
Largest fit:
6
5
3
1
4
2
53
6
Smallest fit:
4
2
1
Best fit:
36
2
5
4
1
Data placement job queue
Storage space at destination
Figure 4.1
Storage space management: different techniques.
other interfaces without using the data placement scheduler. In this case, the
data placement scheduler at least assures that it does not overcommit the
available storage space, and it will manage the space eciently if there are no
external effects.
Figure 4.1 shows how the scheduler changes the order of the previously
scheduled jobs to meet the space requirements at the destination storage sys-
tem. In this example, four different techniques are used to determine in which
order to execute the data transfer request without overcommitting the avail-
able storage space at the destination:
first fit
,
largest fit
,
smallest fit
, and
best fit
.
First Fit:
In this technique, if the next transfer job in the queue is for data
that will not fit in the available space, it is skipped for that scheduling
cycle, and the next available transfer job with data size less than or
equal to the available space is executed instead. It is important to point
out that a complete reordering is not performed according to the space
requirements. The initial scheduling order is preserved, but only requests
that will not satisfy the storage space requirements are skipped, since
they would fail anyway and also would prevent other jobs in the queue
from being executed.
Largest Fit and Smallest Fit:
These techniques reorder all of the transfer
requests in the queue and then select and execute the transfer request
for the file with the largest, or the smallest, file size. Both techniques
have a higher complexity compared with the
first fit
technique, although
they do not guarantee better utilization of the remote storage space.
