A Lattice-Theoretic Formulation for Rate Monotonic Schedulability Analysis
Mathematics · 2026-05-14 · 14 (10) · 1672
DOI: 10.3390/math14101672 ↗At a glance
Journal article in Mathematics, published online on 2026-05-14. Written by Moonju Park. 16 references. The full text is freely available (open access, CC BY 4.0). Funded by: Incheon National University.
Abstract (original language)
Fixed-priority schedulability analysis for uniprocessor real-time systems is computationally difficult, and exact Rate Monotonic (RM) analysis is weakly NP-complete. This paper develops an exact lattice-theoretic formulation for the family of weighted feasibility problems induced by the exact RM schedulability test. For each candidate period, the corresponding weighted feasibility instance is mapped to a lattice embedding in which feasible values correspond to unique canonical lattice vectors, feasibility is characterized exactly by membership in an explicit constrained region, and candidate interactions satisfy exact carry/borrow correction identities. A determinant-based normalization of the embedding scale is also derived. The results provide an exact structural description of the RM weighted feasibility family together with an empirically informative candidate mechanism.
Funding
- Incheon National University
Cite
APA
Park, M. (2026). A Lattice-Theoretic Formulation for Rate Monotonic Schedulability Analysis. Mathematics, 14(10), 1672. https://doi.org/10.3390/math14101672
Vancouver
Park M. A Lattice-Theoretic Formulation for Rate Monotonic Schedulability Analysis. Mathematics. 2026;14(10):1672. doi:10.3390/math14101672
BibTeX
@article{Park2026,
author = {Park, Moonju},
title = {A Lattice-Theoretic Formulation for Rate Monotonic Schedulability Analysis},
journal = {Mathematics},
year = {2026},
volume = {14},
number = {10},
pages = {1672},
doi = {10.3390/math14101672}
}
EUVIMED