Preprint
Worst-Case Services and State-Based Scheduling
ArXiv.org
08/13/2021
Abstract
In this paper, we shed new light on a classical scheduling problem: given a slot-timed, constant-capacity server, what short-run scheduling decisions must be made to provide long-run service guarantees to competing flows of unit-sized tasks? We model the flows' long-run guarantees as worst-case services that map each arrival vector recording a flow's cumulative task arrivals to a worst-case acceptable departure vector lower-bounding its cumulative task departures. We show that these services are states that can be updated as tasks arrive and depart, introduce state-based scheduling, and find the schedulability condition that must be preserved to maintain all flows' long-run guarantees. We then use this condition to identify, in each slot, all short-run scheduling decisions that preserve schedulability. To illustrate how scheduling complexity can be reduced, we additionally show that special schedules can be efficiently identified by maximizing the server's capacity slack, and that special services can be efficiently specified and updated using properties of the min-plus algebra.
Details
- Title: Subtitle
- Worst-Case Services and State-Based Scheduling
- Creators
- Yike XuMark S Andersland
- Resource Type
- Preprint
- Publication Details
- ArXiv.org
- ISSN
- 2331-8422
- Language
- English
- Date posted
- 08/13/2021
- Academic Unit
- Electrical and Computer Engineering
- Record Identifier
- 9984197921502771
Metrics
10 Record Views