Determining rate monotonic schedulability of real-time periodic tasks using continued fractions

Moonju Park, Hyeongboo Baek

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


Fixed-priority scheduling algorithms are widely used for real-time systems with a single processor because of their implementation simplicity and relatively low run-time overheads. However, determining whether a task set is schedulable by a fixed-priority scheduling algorithm has been shown to be NP-hard. There are few exact schedulability test methods such as the time demand analysis or the worst-case response time analysis for Rate Monotonic scheduling, while much research has been done to find a tighter sufficient condition for the fixed-priority schedulability. In this paper, a new approach to analyze the schedulability of fixed-priority scheduling using well-known mathematical tool called continued fractions is presented. With continued fractions, a new schedulability test for Rate Monotonic algorithm is derived. The schedulability test condition is an exact condition that can be applied tasks with total utilization less than 1.

Original languageEnglish
Article number106296
JournalInformation Processing Letters
StatePublished - Jan 2023


  • Continued fraction
  • Fixed-priority
  • Rate Monotonic
  • Real-time systems
  • Schedulability


Dive into the research topics of 'Determining rate monotonic schedulability of real-time periodic tasks using continued fractions'. Together they form a unique fingerprint.

Cite this