Browse Prior Art Database

Bidirectional Minimum Seek

IP.com Disclosure Number: IPCOM000079804D
Original Publication Date: 1973-Sep-01
Included in the Prior Art Database: 2005-Feb-26
Document File: 3 page(s) / 43K

Publishing Venue

IBM

Related People

Larson, LE: AUTHOR [+2]

Abstract

Bidirectional Minimum Seek (BDMS) is a queuing algorithm for movable head devices. It is designed to minimize the time delay in servicing requests caused by access arm movement (seek time).

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 56% of the total text.

Page 1 of 3

Bidirectional Minimum Seek

Bidirectional Minimum Seek (BDMS) is a queuing algorithm for movable head devices. It is designed to minimize the time delay in servicing requests caused by access arm movement (seek time).

BDMS accomplishes this optimization through the calculation of seek distances within a request queue and queuing by shortest seek distance. PROGRAM DESCRIPTIONS

The addressing scheme on movable head devices involves a three part address: 1) cylinder (CC) 2) head (HH) 3) record (R)

Associated with the three part address are two types of mechanical delay: 1) seek delay 2) search delay It is the seek time that BDMS attempts to minimize. Consider the following three disk addresses: A=CC(1)HH(1)R B=CC(2)HH(2)R(2) C=CC(3)HH(3)R(3). Assuming that the access arm is at A, the following is true: 1) The seek distance from A to B is CC(1) - CC(2). 2) The seek distance from A to C is CC(1) - CC(3).

Note that seek distance is measured using the CC portion of a disk address only.

In an operating system environment, all requests for I/O operations to a disk device cannot be satisfied at the time the request is received. Nevertheless, the request does have to be satisfied at some time. The way most operating systems handle this situation is to queue the request and start it at a later time. BDMS is a method of queuing when a request cannot be immediately satisfied. It queues by minimizing seek distances on a disk device through calculation.

Consider the following procedure: STEP 1 - Determine if the current request can be started immediately. If yes, start it.

STEP 2 - Else, determine if there is more than one request pending.

If only one request is pending, queue the current

request behind that one.

STEP 3 - Else, set N = 1.

STEP 4 - Calculate the absolute seek distance (ASD ) between the Nth and N + 1st request in the queue.

ASD(1) = /CC(N) - CC(N+1)/

STEP 5 - Calculate ASD(2) between the Nth and the current request. ASD(2) = /CC(N) - CC(CURRENT)/

STEP 6 - Compare these distances, if the ASD between the Nth and current req...