ANALYSIS OF A SCHEME FOR INFORMATION ORGANIZATION
AND
RETRIEVAL FROM A DISC FILE
ROSHAN L. SHARMA
Collins Radio Company
Newport Beach, California, U. S. A.
(Presented at the IFIP 68 Congress Held in Edinburgh,
Scotland in August, 1968)
Abstract: Detailed mathematical tools are derived for analyzing the efficiency
of a disc file storage and retrieval technique suitable for a computer-controlled
message switching system. Average time spent on both disc rotations and arm
positioning for any batch size of disc requests can now be easily computed.
This can enable one to compute the number of input messages that can be handled
per hour in a disc-file-limited system.
1. INTRODUCTION
The importance of computer-controlled message switching systems to industry
has been increasing during the last decade or so. Stored program techniques
are essential to message because maximum flexibility can be achieved to meet
different types of customer requirements. A generalized message switching
program scans input channels and accepts bits of information from active
channels, assembles these into characters, for start and end-of-message indicators,
develops message segments, processes these segments for editing and routing
information, develops message tags which are queued for outputs, stores the
processed message segments and tags into a bulk storage such as disc file,
and finally outputs the messages in proper form when the required output
channel is available.
The capacity of a well-designed system is generally determined by the
I/O devices, such a disc files, for two reasons: 1) a sufficient number
of output channels are provided to minimize delays due to queuing, and 2)
processing speeds in computers have increased at a much faster rate than
the read/write rate in the I/O devices.
Keeping in mind the above reasoning, it becomes imperative that the scheme
for organizing the incoming message segments in the storage device and for
retrieving the outgoing message segments from the same storage device must
be analyzed for efficiency in order to compute the system capacity. After
a lengthy study, it was found that a disc file is desirable in a message
switching system for many reasons; such as 1) cost, 2) random access for queued
traffic, and 3) availability of a history journal. However, a disc file presents
many interesting and yet difficult aspects for analyzing its efficiency.
To illustrate, we have to contend with the arm-positioning mechanism, information
density, and latency (and rotation) time. We have to consider also the influence
of Input/Output Control System, batch size (number of message segments to
be handled as a pattern), and the size of a message segment. It is the purpose
of this paper to first develop and then analyze a mathematical model for
a scheme that involves random allocation of disc storage locations to incoming
message segments and random retrievals of message segments for output.
A generalized disc file storage (see Figure 2-1) can be represented in
the form of a circular ring of N buckets – each of dimensions
nc x Nh - where nc
is the number of sectors per cicular track, Nh is the
number of heads in a disc file, and N is the number of arm positions.
In order to analyze the average time spent per each batch of size M
on disc rotations and arm positioning, one can proceed as follows.
1,1 | 1,2 | 1,* | 1, Nc
..............................................
2,1 | 2,2 | 2,* |
2,Nc
..............................................
Figure 2-1 Bucket Dimensions [Nh,Nc]
*,1 | *,2 | *,* | *,Nc
................................................
Nh,1 | Nh,2 | Nh,* | Nh,Nc
2. MATHEMATICAL MODEL FOR COMPUTING THE TIME SPENT ON DISC ROTATIONS
Let us assume that m message segments are to be handled (either read or
write) in a bucket whose dimensions are nc and Nh.
The locations corresponding to a batch of m segments will constitute a pattern.
Let us represent the ith pattern made up of m locations in
a bucket as follows:
{ith pattern} = {j,k,....l}
(2-1)
where j >= k >= ........l
j+k+....l =
m
The pattern {j,k,.....l} signifies the number of locations in each
sector position (or the same column in Figure 2-1) are ordered by magnitude.
The tabulation of all possible patterns that can be formed out of m segment
locations can be esily accomplished by an ordered decompositions of integer
m into integers j >= k >= ........l such that j+k+....l
= m. Due to the fact that the number j is a predominant
factor in determining the actual number of disc rotations required to serve
that particular pattern, the pattern representation as defined by Equation
2-1 is quite efficient. As each pattern is possible , one can compute the
average number rotations required to serve a pattern of m locations in a
given bucket. The resulta are shown in Figure 2-2 as follows:
