Browse Prior Art Database

Algorithm for Locating and Accessing Data

IP.com Disclosure Number: IPCOM000085109D
Original Publication Date: 1976-Feb-01
Included in the Prior Art Database: 2005-Mar-02
Document File: 2 page(s) / 81K

Publishing Venue

IBM

Related People

Dix, GL: AUTHOR

Abstract

This algorithm addresses the problem of accessing data on a disk file (which may include a plurality of separate magnetic disks) which is part of a virtual storage system, where a virtual address must be translated to a physical location before accessing the data. The disk file has multiple surfaces served by a single head and access mechanism; each surface has multiple tracks and each track has multiple sectors. The algorithm minimizes the time required to locate and access the data.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 2

Algorithm for Locating and Accessing Data

This algorithm addresses the problem of accessing data on a disk file (which may include a plurality of separate magnetic disks) which is part of a virtual storage system, where a virtual address must be translated to a physical location before accessing the data. The disk file has multiple surfaces served by a single head and access mechanism; each surface has multiple tracks and each track has multiple sectors. The algorithm minimizes the time required to locate and access the data.

The algorithm basically consists of "hashing" the virtual address, searching a directory, and accessing the data. Flow chart 1 shows a detailed operation for reading or modifying previously written data. A hash algorithm is used to convert the virtual address (VA) to a surface number. The outer track of that surface is then accessed, and a directory is searched. The directory contains information on each VA that is stored on that surface. Each entry in the directory consists of the VA, a flag indicating information about that VA, and the physical location at which it is stored.

The physical location may be stored explicitly in the directory or may be implied by the position in the directory. The directory is searched for the requested VA; if it is found, it is only necessary to access to the indicated physical location and read or rewrite the record. If the VA is not found, it is then necessary to search an overflow table. Each overflow table entry contains a VA and an alternate surface number. When the requested VA is found in the overflow table, the alternate surface is accessed and its directory is searched as above.

In addition to the above operations, table updates are required...