Information Technology Reference
In-Depth Information
2.3
The OWeiST algorithm
This algorithm (optimal weighted service time) is different from the
previous ones since it can be considered into a category of algorithms that
can be denominated 'mixed' [8]. They combine information that is avail-
able to the server and the disk, producing a single criterion of scheduling.
The obvious motivation to study these algorithms is to determine if the
single criterion of scheduling can lead to higher performance than those of
the mechanisms that simply combine separate algorithms for scheduling
of the disk and the server node. This algorithm tries to improve the
performance of the selection process, using the information derived from
the queue server and the disk. As we shall see, the research data on disk
is different from the C-LOOK and becomes more beneficial as more
extensive groups of requests are taken into consideration. Let us suppose to
have a number of requests queued to the server, and
K
is a natural number
constant and characterizing the ubiquitous node.
Besides, let Sstart be the last data taken from the disk. The algorithm
takes into account all the possible
K
-uple (
r
1
,
r
2
, …,
r
K
) of requests in the
waiting list. Each
r
i
element of the
K
-uple refers to the request of a particular
data object
S
i
on the disk, required by
R
i
clients. Besides, for the
K
-uple
(
r
1
,
r
2
, …,
r
K
), data on disk are supposed to be taken in the respective order
S
1
,
S
2
, …,
S
K
, given that the starting position of the head is Sstart. For each
K
-uple, varying the elements that constitute it and their service order, the
time with which information
S
1
,
S
2
, …,
S
K
are taken from the disk varies.
The OWeiST algorithm must, therefore, calculate almost all the
possible
K
-uple and it is the one which shows the least sum of products
R
i
x
T
i
,
i
−1
, where
T
i
,
i
−1
is the time equal to the shift of the head from the
position
S
i
−1
to the position
S
i
on disk. The access time
T
i
,
i
−1
takes into
consideration the positioning time from the cylinder of the
i
−1th set to the
cylinder of the
i
th set, and the rotational latency necessary for positioning
the head on the object
i
, once the cylinder is reached. The algorithm
calculates for every possible permutation of
K
the above-required sum.
On identifying the best
K
-uple, the requests contained in it will be sent to
the queue entry in the disk to be met. After the service for the
K
-uple
is finished, the algorithm is again applied to select a new group of
K
requests. This process continues until the elements present in the waiting
queue are exhausted. Note that if
m
<
K
requests queued to the server
were present, the algorithm will order them with the same procedure,
forming however an
m
-uple instead of a
K
-uple. Obviously, by limiting
the value of the parameter
K
, we can control the overhead introduced in
the search for the best
K
-uple [7].
