Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces a state-based scheduling framework to exploit short-run scheduling flexibility while providing long-run, worst-case guarantees for competing flows of unit-sized tasks in a slot-timed, constant-capacity server. The framework models each flow's guarantee as a worst-case service that is updated dynamically, and the scheduler ensures transitions between schedulable states, constraining scheduling flexibility to a polytope of feasible schedules. The authors characterize this polytope and propose methods to reduce computational complexity, including maximizing server capacity slack and using min-plus algebra for a special class of worst-case services called dual-curve services.
Even when guaranteeing worst-case service, significant scheduling flexibility can be unlocked by modeling guarantees as dynamically updated states, opening the door to more efficient resource allocation.
Even when providing long-run, worst-case guarantees to competing flows of unit-sized tasks, a slot-timed, constant-capacity server's scheduler may retain significant, short-run, scheduling flexibility. Existing worst-case scheduling frameworks offer only limited opportunities to characterize and exploit this flexibility. We introduce a state-based framework that overcomes these limitations. Each flow's guarantee is modeled as a worst-case service that can be updated as tasks arrive and are served. Taking all flows'worst-case services as a collective state, a state-based scheduler ensures, from slot to slot, transitions between schedulable states. This constrains its scheduling flexibility to a polytope consisting of all feasible schedules that preserve schedulability. We fully characterize this polytope, enabling scheduling flexibility to be fully exploited. But, as our framework is general, full exploitation is computationally complex. To reduce complexity, we show: that when feasible schedules exist, at least one can be efficiently identified by simply maximizing the server's capacity slack; that a special class of worst-case services, min-plus services, can be efficiently specified and updated using the min-plus algebra; and that efficiency can be further improved by restricting attention to a min-plus service subclass, dual-curve services. This last specialization turns out to be a dynamic extension of service curves that approaches near practical viability while maintaining all features essential to our framework.