Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Optimal Head Scheduling Rule to Minimize Batched Processing Time in Linear Storage

IP.com Disclosure Number: IPCOM000052463D
Original Publication Date: 1981-Jun-01
Included in the Prior Art Database: 2005-Feb-11
Document File: 2 page(s) / 49K

Publishing Venue

IBM

Related People

Bitner, JR: AUTHOR [+2]

Abstract

A method is described for minimizing the average access time for batche of records in linear store. Here, we consider the accessing of batched requests in linear storage, i.e., processing a fixed number (a batch) of requests at a time. We assume that consecutive accesses are independent and the frequencies are known. Access time is measured by the distance traveled by the read/write head.

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

Page 1 of 2

Optimal Head Scheduling Rule to Minimize Batched Processing Time in Linear Storage

A method is described for minimizing the average access time for batche of records in linear store. Here, we consider the accessing of batched requests in linear storage, i.e., processing a fixed number (a batch) of requests at a time. We assume that consecutive accesses are independent and the frequencies are known. Access time is measured by the distance traveled by the read/write head.

Let the locations of a linear storage be labeled 1,2,...n from left to right. We use a row n-vector to represent the arrangement of records, e.g., (R(1),...,R(n)) means record R(i) is at location i for all i. See original.

The procedure for calculating an optimal rule starts with an arbitrary rule (we choose the nearest rule) and iteratively improves it. At each iteration we assume the current rule will be used to access all batches except the first and then calculate the best rule for accessing the first batch. It can be shown that the asymptotic cost for this rule is less than or equal to that for the original rule. The new rule is then used to the next iteration, and we continue iterating until the new rule and the current rule are identical. The procedure for calculating an optimal rule is given below. 1. Make the nearest rule the "current rule".

2. Calculate f(B) (x) (the cost of accessing B batches with

the head starting at position x) for the current rule.

f(B) (x) is iteratively calculated...