Encyclopedia > Rate-monotonic scheduling

  Article Content

Rate-monotonic scheduling

Rate-monotonic scheduling is a scheduling principle employed in real-time operating systems. The basic principle is that if all processes (tasks, threads) to be scheduled has:

  • Strict deadlines
  • No data dependencies (process x does not transmit data to process y which y are in turn dependent of)
  • No resource sharing (processes x and y will not try to use the same resource, e.g. a hardware resource)
  • Deterministic periodicity
  • Statically scheduled (priorities does not change during execution)

And the swithcing of tasks takes no (zero) time, then by assigning the process with the shortest period (highest frequency) the highest priority, the task with the next shortest period the next highest priority and so on, then all processes can be proven to meet their deadlines. The CPU utilization can be proven to be:

<math>U = m(2^\frac{1}{m} - 1)</math>

Which will be for example <math>0.8284</math> for <math>m = 2</math>. When the number of processes tends towards infinity this expression will tend towards:

<math>\lim_{m \rightarrow \infty} m(2^\frac{1}{m} -1) = \ln 2 \approx 0.693147\ldots</math>

So a rough estimate is that RMS in the general case only utilize <math>69\%</math> of the CPU. Thus, no more than this amount of the CPU shall be allocated to processes, or the system may fail.

Resource preemption, priority inheritance

In many practical applications, resources are shared and the unmodified RMS will be subject to priority inversion[?] and deadlock hazards. In practice, this is mostly solved by introducing priority inheritance.

The principle of priority inheritance is that a shared resource will be tied to the accessing processes, and if one process with a lower priority than the currently running process holds this resource, and the currently running process needs it, the current process will be preempted[?], and the process holding the resource will be raised to the priority of the currently running process until it releases the resource, and at that time it will be preempted and assigned it's previously held priority.

Example

Process Period Execution time
P1 8 1
P2 5 2
P3 10 3

The utilization will be:

<math>\frac{1}{8} + \frac{2}{5} + \frac{2}{10} = 0.725</math>

The teoretical limit for 3 processes will be:

<math>U = 3(2^\frac{1}{3} - 1) = 0.77976\ldots</math>

Since <math>0.725 < 0.77976...</math> the system is schedulable!

See Also



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Karl Benz

... of a man, Gottlieb Daimler, who was working on a four wheeled vehicle. Daimler inspired Karl and he started working on his own "motor carriage", with a four-stroke engine. ...