Information Technology Reference
In-Depth Information
(e)
F
IG
. 40. Continued.
The POS algorithm runs in O
(N
2
M)
time—all of the required sets and functions
except
next
(e.g.,
R
j
,
E
,
freeright
,
First
,
Start
) can be computed in O
(N M)
time.
If we pre-compute these once, then any use of them during the algorithm requires
just constant time. The function
next
takes O
(N )
time since the size of
L
(the number
of access lines) will be at most
N
. The algorithm consists of an outer loop iterated
M −
1 times. The algorithm contains three inner loops each iterated at most
N
times
(since the sizes of
L
and
A
are bounded by
N
). The first and third inner loop bodies
take constant time while the second inner loop body takes O
(N )
time due to the call
to
next
.
Figure 40
is a running example that shows the behavior of the POS algorithm in
finding the optimal number of the access lines for the requested objects (numbers
in the captions refer to the line number in the POS algorithm) when applied to the
request shown in
Fig. 36
. In this request, refer to
Definitions 9 and 10
,
MAX
_
cut
is 3,
MAX
_
total
is 4 and at least 3 passes with at least 4 channel switches are required to
retrieve the requested objects.
As a result, three passes are required to retrieve the requested objects. In one pass,
objects 1, 2, 3, and 7 are retrieved. In the second pass, objects 4, 5, 13, 14, and 15
are retrieved. Finally, in the third pass, objects 8, 9, 10, 6, 11, and 12 are retrieved.
8 . 2 S e r i a l E m p t y S c a n
The Serial Empty Scan (SES) which examines empty blocks. The basic idea be-
hind the algorithm is as follows. We construct (
MAX
_
total
−
MAX
_
cut
) paths that
scan only empty blocks (empty paths). As we do this we also compress the requested
objects into
MAX
_
cut
channels. Each of these resulting “logical” channels describes
the sequence of requested objects that an access line reads. The action of com-
pressing (copying objects from one channel to another) simulates a switch during
a scan.
