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.

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

  • satellite control systems
  • automotive control applications
  • avionics and flight control systems
  • industrial automation and robotics
  • real-time signal processing

Patents:

NA

Potential Innovations Ideas

Due to scrapping bot traffic, currently more than 40k per day, this content is reserved to community members.
> Login < or > Register < (100% free) to access this, so as all other restricted content and tools.

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)

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

> Login <