Soft Scheduling - Scalable Continuous Media Streaming Systems - page 69

If the worst-case residual service time does not exceed the service round end time t due , then
this new request can be admitted into this round as if it had arrived before the round starts. We
can check for the overflow condition simply by

max {} + t new ≤ t due (4.15)

Otherwise, the new request will have to wait for service in the next round.
On the other hand, if the media block for the new stream is located in an upstream location
where the disk head has already scanned past, then the disk scheduler has two options: it can
proceed to retrieve data blocks for existing streams first and then come back to retrieve data
block for the new request - non-preemptive schedule ; or it can backtrack to retrieve data block
for the new request first before proceeding with the rest of the existing streams - preemptive
schedule .
We can compute the residual service time for non-preemptive schedule from

f seek (

u − 1

Q
r j + 1 +

t j + 1
latency

nps = v j + 1 − v j ) +

j = w

Q
r u + 1 +

t u + 1
latency

+ f seek ( v u − v u + 1 ) + (4.16)

+ f seek ( N − v u + 1 ) + t residual

where the first term is the time to retrieve data blocks for the existing streams; the second term
is the time to retrieve data block for the new stream; the third term is the head-repositioning
time; and the last term is the time to complete retrieving the current data block .

Similarly, we can compute the residual service time for preemptive schedule from

w

Q
r u + 1 +

t u + 1
latency

ps = f seek ( v w − v u + 1 ) +

Q
r w + 1 +

t w + 1
latency

+ f seek ( v w + 1 − v u + 1 ) +

(4.17)

f seek (

u − 1

Q
r j + 1 +

t j + 1
latency

+ v j + 1 − v j ) +

j = w + 1

+ f seek ( N − v u ) + t residual

where the first term is the time to backtrack and retrieve data block for the new stream; the
second term is the time to retrieve data block for stream ( 1); the third term is the time to

retrieve data blocks for the remaining streams; the fourth term is the head-repositioning time;
and the last term is the time to complete retrieving the current data block

w +

w .

, the scheduler can choose the method with shorter
delay and then check for overflow using method similar to Eqs. (4.14) and (4.15). If the
round does not overflow, then the new stream can be admitted into the current round, thereby
shortening the scheduling delay by one complete service round of T r seconds.

By comparing max { nps } with max { ps }