A Lattice-Theoretic Formulation for Rate Monotonic Schedulability Analysis
Moonju Park · Mathematics · 2026
Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.
Mathematics · Multidisciplinary Digital Publishing Institute · article · 2026
Abstract
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.
Open the resolved locator · 10.3390/math14101672
Metadata licence: OpenAlex metadata (CC0)