Go backward to Conclusion and Future Research Directions
Go up to Top
Go forward to References

Admission Control with GSS

This appendix details the implementation of the Scheduler's admission policy with GSS. A building component is a function, termed seek(#cyl), that estimates the disk seek time. Its input is the number of cylinders traversed by the seek operation. Its output is an estimate of the time required to perform the seek operation using the models of [GSZ95]. Assuming CYL cylinders for the disk and n displays assigned to a group G_i, we assume that the n blocks are (CYL)/(n) cylinders apart.

The Scheduler maintains the amount of idle time left for each group G_i. With a new request for object X, the scheduler retrieves from the catalog the record corresponding to X to determine its media type, M_X. Next, it retrieves from the catalog the record corresponding to media type M_X to determine B(M_X). Starting with the current group G_i, the Scheduler compares the idle time of G_i with the disk service time to retrieve a block of size B(M_X). The disk service time with G_i is:

S_disk(G_i)=(B(M_X))/(R_D) + max rotational latency + seek(CYL)

It assumes the maximum seek time (i.e., seek(CYL)) because the blocks to be retrieved during G_i have already been scheduled and the new request cannot benefit from the scan policy. Assuming that G_i is servicing n-1 requests and its idle time can accommodate S_disk(G_i), its idle time is reduced by S_disk(G_i). Prior to initiating the retrieval of blocks that belong to group G_i+1, the scheduler adjusts the idle time of group G_i to reflect that the active active requests can benefit from the scan policy. Thus, the idle time of G_i is adjusted as follows:

idle(G_i) = idle(G_i) - [seek(CYL)+(n-1) ×seek((CYL)/(n-1))]+[n ×seek((CYL)/(n))]

The subtracted portion reflects the maximum seek time of the request that was just scheduled and the seek time of n-1 other active requests. The added portion reflects the n seeks incurred during the next time period by this group with each (CYL)/(n) cylinders apart.

If current group G_i has insufficient idle time, the Scheduler proceeds to check the idle time of other groups G_j where j=(i+1) mod g, 0 < j < g and j !=i. Assuming that G_j is servicing n-1 active requests, the disk service time with G_j is:

S_disk(G_j)=(B(M_X))/(R_D) + max rotational latency + [n ×seek((CYL)/(n))] - [(n-1) ×seek((CYL)/(n-1))]

If the idle time of G_j is greater than S_disk(G_j), then the new request is assigned to G_j and its idle time is subtracted by S_disk(G_j).