Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2000-09-14
2002-07-09
Yoo, Do Hyun (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S133000, C711S138000, C711S159000, C710S043000
Reexamination Certificate
active
06418510
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to methods for improving performance of direct access storage devices (DASD) such as disk drives. More particularly, it relates to a disk drive cache management scheme that combines the cache and queuing algorithms according to a rotational positioning optimization (RPO) algorithm used in existing DASDs. Decisions are thus made with the goal of optimizing performance by considering both cache and queue structure.
BACKGROUND ART
Direct access storage devices (DASD) are commonly used in computers and network servers to store large quantities of digital information. Magnetic disk drives contain a number of flat, round, rotating disks, each of which has two surfaces coated with magnetic material organized into concentric tracks. Data is read from and written to the disks by a transducer or head connected to an actuator that moves the head to a desired track and maintains it over the track during read and write operations. In general, each surface is provided with its own read/write head, and all heads are connected to a common actuator. A typical disk surface
10
containing a number of concentric tracks
12
is illustrated in FIG.
1
. Data is stored within a track in sectors
14
containing blocks of fixed size, usually 512 bytes, plus header and trailer information such as error correction data. The location of each sector is uniquely identified by its head, track (on a single surface) or cylinder (vertically aligned tracks of multiple surfaces), and sector. This geometric position is mapped to a logical block address (LBA), an indexing system for the drive. A read/write head
16
is formed on the end of an air-bearing slider
18
and suspended above surface
10
during data transfer. In response to a read or write command sent by a host computer, the actuator
20
moves the read/write head
16
to the proper track and sector defined by the logical block address.
Recently, both computer processor speeds and the volume of information capable of being stored on a hard drive have increased dramatically. As a result, the random input/output performance of disk drives, which has not increased at a comparably high rate, remains a limiting factor in many applications. A variety of metrics are used to describe the performance of disk drives. One important metric is the data access time, a measure of the time to position a read/write head over a particular track and locate the sector or sectors of interest within the track for reading or writing. Data access time is a measure of mechanical performance, i.e., the performance of mechanical functions that are controlled electronically, and thus typically the actual time to transfer data between the head and the disk, known as the data transfer rate, can be neglected. Data access time, measured in milliseconds, is a combination of two factors: seek time and rotational latency.
Seek time denotes the actuator movement time required to reposition the read/write head over the track or cylinder containing the first sector requested by the command. Seek time is a nonlinear function of the number of tracks to be traversed. Average seek times, defined as the time to position the read/write heads between two randomly selected tracks, currently range from 4 to 6 milliseconds.
Once the head is positioned over the appropriate track, it must wait for the sector requested by the command to rotate under it before data transfer can begin. The elapsed time for rotation is known as the rotational latency, which depends upon the disk's rotational speed. In the worst case scenario, the head reaches the desired sector just after the sector rotates past the head location, in which case the head must wait almost a full rotation before the desired sector is accessed. On average (in a non-RPO environment), the disk must spin one-half rotation before the desired sector is under the head. Average rotational latencies vary from 8.3 milliseconds for a rotational speed of 3600 RPM to 2 milliseconds for a rotational speed of 15,000 RPM. Note that for non-random disk accesses, rotational latencies are significantly lower.
A variety of methods have been employed to reduce the total data access time for a sequence of read and write commands. One method, known as command queue reordering, divides reception of the command sequence from the host controller and execution in the disk drive into two asynchronous processes. Commands are temporarily held in a command queue, where they can be reordered. Each command in the queue contains the instruction for the disk drive to read or write the data to a particular LBA on the disk. Commands consist of the operation type (read or write), starting LBA, and size of command in number of blocks. Commands are uniquely identified by a label, allowing them to be performed in a different order than the one in which they arrive at the controller. The idea behind command reordering is to reorder the commands in the queue to minimize the path length that the mechanical actuator must travel.
In the past, command reordering algorithms aimed to reduce only seek time. For example, the shortest seek time-first ordering algorithm examines all commands in the queue and selects the command with the shortest seek time, in either direction, from the end of the last sector of the currently executed command. The problem with this algorithm is that it completely ignores rotational latency, a significant portion of the data access time. The head might arrive at the next command track, only to find that the required sector had just spun past, requiring the head to stay in position until the next rotation of the disk.
Current command reordering techniques follow a rotational positioning optimization (RPO) algorithm, described in U.S. Pat. No. 5,729,718, issued to Au, and U.S. Pat. No. 5,991,825, issued to Ng. The RPO algorithm takes into account both seek time and rotational latency in reordering the command queue. The total access time for each command in the queue is computed with respect to the ending LBA of the command currently being executed, and the command having the shortest access time is moved to the front of the queue. The access time is calculated as the sum of the maximum of the seek time and head switch time, plus the rotational latency from the arrival point at the new command track to the desired sector location. The RPO algorithm therefore anticipates the above-described problem of arriving at the track just after the desired sector has spun past. RPO algorithms have been shown to increase the overall data throughput of the drive by about 20%.
Another way of improving disk drive performance is by employing a cache buffer memory array (“cache”) in the disk controller. The cache provides temporary and limited storage of data blocks in transit between the host computer and storage locations on the disks. The purpose of the cache is to reduce the relatively long access time (e.g., milliseconds) associated with obtaining data from the storage device by maintaining the data in a higher speed memory, which has microsecond access times. The advantage of cache arises from the tendency of applications to make repeated references to the same or adjacent data. A disk drive cache typically has a selectable number of cache slots that are dynamically allocated as either read cache or write cache. When a read data command is executed, the data is both read into the read cache and transferred to the host computer. Subsequent requests for the same data may be fulfilled by the cache, saving significant amounts of time. In the case of write caching, data is stored in the cache before being written to the storage device, allowing parallel host-to-cache and cache-to-disk transfers. When the host computer issues a write command, and the data can be written to the cache, it will be transferred immediately, and the command does not need to enter the command queue. Data accumulated in the cache are subsequently written to the disk in clusters rather than individually, requiring less actuator movement in order
Dinh Ngoe
International Business Machines - Corporation
Lumen Intellectual Property Services
Yoo Do Hyun
LandOfFree
Cooperative cache and rotational positioning optimization... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Cooperative cache and rotational positioning optimization..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cooperative cache and rotational positioning optimization... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2832984