M. Hamdaoui et P. Ramanathan, A DYNAMIC PRIORITY ASSIGNMENT TECHNIQUE FOR STREAMS WITH (M,K)-FIRM DEADLINES, I.E.E.E. transactions on computers, 44(12), 1995, pp. 1443-1451
The problem of scheduling multiple streams of realtime customers, is a
ddressed in this paper, The paper first introduces the notion of (m, k
)-firm deadlines to better characterize the timing constraints of real
-time streams. More specifically, a stream is said to have (m, k)-firm
deadlines if at least m out of any k consecutive customers must meet
their deadlines, A stream with (m, k)-firm deadlines experiences a dyn
amic failure if fewer than m out of any k consecutive customers meet t
heir deadlines. The paper then proposes a priority-based policy for sc
heduling N such streams on a single server to reduce the probability o
f dynamic failure. The basic idea is to assign higher priorities to cu
stomers from streams that are closer to a dynamic failure so as to imp
rove their chances of meeting their deadlines. The paper proposes a he
uristic for assigning these priorities. The effectiveness of this appr
oach is evaluated through simulation under various customer arrival an
d service patterns. The scheme is compared to a conventional scheme wh
ere all customers are serviced at the same priority level and to an im
precise computation model approach, The evaluation shows that substant
ial reductions in the probability of dynamic failure are achieved when
the proposed policy is used.