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].