OPTIMAL ANTICIPATORY POSITION OF A DISK ARM FOR QUERIES OF RANDOM LENGTH AND LOCATION

摘要

We wish to identify the best anticipatory position for an idle disk arm which will minimize the expected distance travelled to a file segment of random length and location. Previous work focused primarily on requests of zero length, where the optimal position is the median of the requests' location distribution. However in many scientific, geographical and multi-media database systems, it is typical that large objects must be fetched from disk and displayed in 'real time'. We address such scenarios assuming that after dealing with a request the disk arm usually has sufficient time to return to an anticipatory position. We discuss systems where reads are always from left to right, as well as those in which reads can be performed in both directions (and hence the arm can start at the closer end to its anticipatory position). General analyses and instructive examples are provided.%Nous souhaitons identifier la meilleure position d'anticipation pour un bras de lecture de disque au repos, qui minimisera l'espérance de la distance parcourue pour atteindre un fichier dont l'emplacement et la longueur sont alléatoires. Les travaux antérieurs ont concentré principalement sur demandes de longueur nulle, où la position optimale est la médiane de la distribution de demande d'emplacement. Cependant, dans plusieurs systèmes de données multi-média scientifiques et géographiques, on doit couramment récupérer sur disque de gros fichiers qu'on doit afficher en temps réel. Nous adressons ces scénarios en supposant qu'après l'exécution d'une demande le bras de lecture a suffisament de temps pour retourner à une position d'anticipation. Nous discutons de systèmes où la lecture se fait toujours de gauche à droite, ainsi que de systèmes dont la lecture peut être effectuée dans l'une ou l'autre direction (le bras peut donc commencer du coté le plus prés de la position d'anticipation). Des analyses générales ainsi que des exemples instructifs sont présentés.