Rate-monotonic Scheduling - Introduction


A simple version of rate-monotonic analysis assumes that threads have the following properties:

  • No resource sharing (processes do not share resources, e.g. a hardware resource, a queue, or any kind of semaphore blocking or non-blocking (busy-waits))
  • Deterministic deadlines are exactly equal to periods
  • Static priorities (the task with the highest static priority that is runnable immediately preempts all other tasks)
  • Static priorities assigned according to the rate monotonic conventions (tasks with shorter periods/deadlines are given higher priorities)
  • Context switch times and other thread operations are free and have no impact on the model

It is a mathematical model that contains a calculated simulation of periods in a closed system, where round-robin and time-sharing schedulers fail to meet the scheduling needs otherwise. Rate monotonic scheduling looks at a run modeling of all threads in the system and determines how much time is needed to meet the guarantees for the set of threads in question.

Liu & Layland (1973) proved that for a set of n periodic tasks with unique periods, a feasible schedule that will always meet deadlines exists if the CPU utilization is below a specific bound (depending on the number of tasks). The schedulability test for RMS is:

where Ci is the computation time, Ti is the release period (with deadline one period later), and n is the number of processes to be scheduled. For example U ≤ 0.8284 for n = 2. When the number of processes tends towards infinity this expression will tend towards:

So a rough estimate is that RMS in the general case can meet all the deadlines if CPU utilization is 69.3%. The other 30.7% of the CPU can be dedicated to lower-priority non real-time tasks. It is known that a randomly generated periodic task system will meet all deadlines when the utilization is 85% or less, however this fact depends on knowing the exact task statistics (periods, deadlines) which cannot be guaranteed for all task sets.

The rate monotonic priority assignment is optimal meaning that if any static priority scheduling algorithm can meet all the deadlines, then the rate monotonic algorithm can too. The deadline-monotonic scheduling algorithm is also optimal with equal periods and deadlines, in fact in this case the algorithms are identical; in addition, deadline monotonic scheduling is optimal when deadlines are less than periods.

An optimal static-priority scheduling algorithm when deadlines are greater than periods is an open problem.

Read more about this topic:  Rate-monotonic Scheduling

Other articles related to "introduction":

Introduction - Music - Songs and Tracks
... Introduction", by Chicago from The Chicago Transit Authority "Introduction", by Hood from Outside Closer "Introduction", by Kajagoogoo from White ...
Introduction To Metaphysics
... An Introduction to Metaphysics (Introduction à la Métaphysique) is a 1903 essay by Henri Bergson that explores the concept of reality ...
China Miéville - Bibliography - Nonfiction - Introductions To Fiction By Other Authors
... The Borribles An Introduction, 2001 ... Things That Never Happen An Introduction, 2002 ... Wizardry and Wild An Introduction, 2004 ...
John Frame (theologian) - Selected Works
... Introduction to Presuppositional Apologetics Part 2 ... Van Til The Theologian, 1976 ISBN 0-916034-02-X Medical Ethics, 1988 ISBN 0-87552-261-0 Perspectives on the Word of ...

Famous quotes containing the word introduction:

    We used chamber-pots a good deal.... My mother ... loved to repeat: “When did the queen reign over China?” This whimsical and harmless scatological pun was my first introduction to the wonderful world of verbal transformations, and also a first perception that a joke need not be funny to give pleasure.
    Angela Carter (1940–1992)

    Do you suppose I could buy back my introduction to you?
    S.J. Perelman, U.S. screenwriter, Arthur Sheekman, Will Johnstone, and Norman Z. McLeod. Groucho Marx, Monkey Business, a wisecrack made to his fellow stowaway Chico Marx (1931)

    The role of the stepmother is the most difficult of all, because you can’t ever just be. You’re constantly being tested—by the children, the neighbors, your husband, the relatives, old friends who knew the children’s parents in their first marriage, and by yourself.
    —Anonymous Stepparent. Making It as a Stepparent, by Claire Berman, introduction (1980, repr. 1986)