Product Design, Manufacturing & Innovation Resources
Home » Rate-Monotonic Scheduling (RMS)

Rate-Monotonic Scheduling (RMS)

1973
  • C. L. Liu
  • James Layland
Computer workstation in a control room analyzing Rate-Monotonic Scheduling for real-time systems.

(generated image for illustration only)

Rate-Monotonic Scheduling (RMS) is a static-priority scheduling algorithm for periodic tasks in a real-time system. It assigns priorities based on task frequency: the shorter a task’s period (the higher its rate), the higher its priority. RMS is an optimal static-priority algorithm, meaning if any static-priority algorithm can schedule a task set, RMS can too. Schedulability can be checked using a utilization-based test. Traveling salesman problem applications also include sequencing jobs, a combinatorial task related to real-time scheduling. Scheduling theory, like the linear programming developed by Dantzig, aims for the best use of limited resources.

Rate-Monotonic Scheduling (RMS) is a cornerstone of real-time systems theory, introduced in a seminal 1973 paper by Liu and Layland. It provides a simple yet powerful method for scheduling a set of independent, preemptible, periodic tasks on a single processor. The core principle is to assign a fixed priority to each task inversely proportional to its period. A task that needs to run every 10ms will have a higher priority than a task that runs every 100ms.

The significance of RMS lies in its optimality and the existence of a simple schedulability test. It is proven to be an optimal static-priority scheduling policy. This means that if a set of tasks can be scheduled by any static-priority algorithm, it can also be scheduled by RMS. The schedulability of a task set under RMS can be determined using a utilization bound test. For a set of ‘n’ tasks, the total processor utilization ‘U’ is the sum of the execution time \(C_i\) divided by the period \(T_i\) for each task ‘i’: \(U = \sum_{i=1}^{n} \frac{C_i}{T_i}\). Liu and Layland proved that if this total utilization is less than or equal to a specific bound, \(U \le n(2^{1/n}-1)\), then the task set is guaranteed to be schedulable (i.e., no deadlines will be missed). As ‘n’ approaches infinity, this bound converges to \(\ln(2) \approx 0.693\). This provides a sufficient, but not necessary, condition for schedulability. A more precise but complex test, called exact analysis or response time analysis, can also be used.

UNESCO Nomenclature: 1203
– Computer science

Type

Software/Algorithm

Disruption

Incremental

Usage

Widespread Use

Precursors

  • queuing theory
  • operations research
  • early work on computer scheduling algorithms
  • development of time-sharing operating systems

Applications

Patents:

NA

Potential Innovations Ideas

  • schedulability analyzers for mixed-criticality systems
  • energy-efficient scheduling algorithms that adapt task rates
  • partitioned scheduling for multi-core real-time systems
  • adaptive rms for tasks with variable execution times in ai applications
  • network packet scheduling in time-sensitive networking (tsn) switches
  • resource reservation protocols for real-time cloud computing
  • compositional analysis frameworks for large-scale distributed real-time systems
  • probabilistic schedulability analysis for systems with uncertain execution times
  • security-aware scheduling to prevent timing-based side-channel attacks
  • co-scheduling of real-time tasks and non-real-time applications on a single processor
Related to: rate-monotonic scheduling, RMS, real-time systems, scheduling algorithm, static priority, periodic tasks, schedulability analysis, utilization bound, liu and layland, optimal scheduling.

Historical Context

Rate-Monotonic Scheduling (RMS)

1970
1970
1970
1973
1980
1980
1980
1970
1970
1970
1970-01-01
1975-06-01
1980
1980
1980

(if date is unknown or not relevant, e.g. "fluid mechanics", a rounded estimation of its notable emergence is provided)

10th year anniversary

Full size images and downloads are only available, 100% free, for registered members.

> Login <