Optimal Fixed Priority Scheduling in Multi-Stage Multi-Resource Distributed Real-Time Systems
<|reference_start|>Optimal Fixed Priority Scheduling in Multi-Stage Multi-Resource Distributed Real-Time Systems: This work studies fixed priority (FP) scheduling of real-time jobs with end-to-end deadlines in a distributed system. Specifically, given a multi-stage pipeline with multiple heterogeneous resources of the same type at each stage, the problem is to assign priorities to a set of real-time jobs with different release times to access a resource at each stage of the pipeline subject to the end-to-end deadline constraints. Note, in such a system, jobs may compete with different sets of jobs at different stages of the pipeline depending on the job-to-resource mapping. To this end, following are the two major contributions of this work. We show that an OPA-compatible schedulability test based on the delay composition algebra can be constructed, which we then use with an optimal priority assignment algorithm to compute a priority ordering. Further, we establish the versatility of pairwise priority assignment in such a multi-stage multi-resource system, compared to a total priority ordering. In particular, we show that a pairwise priority assignment may be feasible even if a priority ordering does not exist. We propose an integer linear programming formulation and a scalable heuristic to compute a pairwise priority assignment. We also show through simulation experiments that the proposed approaches can be used for the holistic scheduling of real-time jobs in edge computing systems.<|reference_end|>
@article{kumar2024optimal,
    title={Optimal Fixed Priority Scheduling in Multi-Stage Multi-Resource
  Distributed Real-Time Systems},
    author={Niraj Kumar, Chuanchao Gao, and Arvind Easwaran},
    journal={arXiv preprint arXiv:2403.13411},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.13411},
    primaryClass={cs.DC}
}