Rate-monotonic Scheduling Website Links For
Scheduling 		 

Information About

Rate-monotonic Scheduling
  CATEGORIES ABOUT RATE-MONOTONIC SCHEDULING
   
scheduling algorithms
   
real-time computing
   
APPAREL
BABY
BEAUTY
BOOKS
CAR TOYS
CELL PHONES
DVD'S
ELECTRONICS
GOURMET FOOD
GROCERIES
HEALTH & PERSONAL
HOME & GARDEN
JEWELRY
MUSIC
MUSIC INSTRUMENTS
OFFICE PRODUCTS
SOFTWARE
SPORTING GOODS
TOOLS & HARDWARE
TOYS
VIDEO GAMES
SHOPPING HOME
MORE SHOPPING...



In Computer Science , rate-monotonic scheduling is an optimal Preemptive static-priority Scheduling Algorithm used in Real-time Operating System s. The inputs to the algorithm are processes (tasks, threads) with:

  • No resource sharing (processes do not share resources, e.g. a Hardware resource, a queue, or a Semaphore )

  • Deterministic deadlines exactly equal to periods

  • Static priorities (whenever a processor is free or a new task period begins, the task with the highest static priority is selected to preempt all other tasks)

  • Static priorities assigned according to the ''rate monotonic'' principle (tasks with shorter periods/deadlines are given higher priorities)


In 1973 , Liu and Layland 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:

:U = \sum_{i=1}^{n} C_i / T_i \leq n(\sqrt {Link without Title} {2} - 1)

Where C_i is the computation time, and T_i is the release period (with deadline one period later.) For example U \leq 0.8284 for n = 2\,. When the number of processes tends towards Infinity this expression will tend towards:

:\lim_{n ightarrow \infty} n(\sqrt {Link without Title} {2} - 1) = \ln 2 \approx 0.693147\ldots

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) and 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 in the situation where periods and deadlines are identical, in fact in this case the algorithms are identical; in addition, deadline monotonic scheduling is also optimal when deadlines are less than periods .

An optimal static-priority scheduling algorithm when deadlines are greater than periods is an '' Open Problem ''.


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 solved by introducing Priority Inheritance .

Examples of priority inheritance algorithms include (from simplest to most complex):

  • The OSIntEnter() and OSIntExit() primitives that lock CPU interrupts in a real-time kernel ( UC-OS II kernel),

  • The splx() family of primitives which nest the locking of device interrupts (Linux kernel),

  • The ''Highest Locker protocol'' which requires off-line analysis of all task conflicts to find a "ceiling priority" (see below),

  • The ''Basic Priority Inheritance Protocol'' which waits until a high priority task requests a lock held by a low-priority task, and then boosts the low priority task priority up to the high priority level until the lock is released, and

  • The ''Priority Ceiling Protocol'' which is an enhancement of Basic Priority Inheritance which assigns a "ceiling priority" to each semaphore, which is the priority of the highest job that will ever access that semaphore. A job then cannot preempt a lower priority critical section if its priority is lower than the ceiling priority for that section.


Priority inheritance algorithms can be characterized by two parameters. First, is the inheritance lazy (only when essential) or immediate (boost priority before there is a conflict). Second is the inheritance optimistic (boost a minimum amount) or pessimistic (boost by more than the minimum amount):

In practice there is no mathematical difference (in terms of the Liu-Layland system utilization bound) between the lazy and immediate algorithms, and the immediate algorithms are more efficient to implement, and so they are the ones used by most practical systems.

The ''Basic Priority Inheritance protocol'' can produce ''chained blocking'', i.e. an almost arbitrarily long delay from the time a high priority task requests a critical section, until it is served. The other protocols guarantee that at most one lower priority critical section must finish before the high priority task gets its critical section.

The ''Priority Ceiling Protocol'' is available in the VxWorks real-time kernel but is seldom enabled.

An example of usage of the ''Basic Priority Inheritance'' is related to the " Mars Pathfinder Bug " which was fixed on Mars by changing the creation flags for the semaphore so as to enable the priority inheritance.


EXAMPLE


The utilization will be:

: rac{1}{8} + rac{2}{5} + rac{2}{10} = 0.725

The theoretical limit for 3\, processes will be:

:U = 3(2^ rac{1}{3} - 1) = 0.77976\ldots

Since 0.725 < 0.77976\ldots the system is schedulable!


SEE ALSO




REFERENCES


  • C. L. Liu and J. Layland. Scheduling algorithms for multiprogramming in a hard real-time environment, ''Journal of the ACM'', 10(1), 1973.

  • M. Joseph and P. Pandya. Finding Response times in Real-time systems, ''BCS Computer Journal'', 29(5), pp. 390-395, October 1986.

  • J. Lehoczky, L. Sha and Y. Ding, The Rate monotonic scheduling algorithm: exact characterization and average case behavior, ''IEEE Real-Time Systems Symposium'', pp. 166-171, December 1989.

  • J. Y. Leung and J. Whitehead. On the complexity of fixed-priority scheduling of periodic, real-time tasks. ''Performance Evaluation'', 2(4):237--250, December 1982.

  • B.W. Lampson, and D. D. Redell. Experience with Processes and Monitors in Mesa. Communications of the ACM, Vol. 23, No. 2 (Feb 1980), pp. 105-117.

  • L. Sha, R. Rajkumar and J. P. Lehoczky, Priority inheritance protocols: an approach to real-time synchronization, IEEE Transactions on Computers, vol. 39 no. 9, September 1990, pp. 1175-1185.



EXTERNAL LINKS


  • http://www.netrino.com/Publications/Glossary/RMA.html - Introduction to Rate Monotonic Scheduling

  • http://research.microsoft.com/~mbj/Mars_Pathfinder/Authoritative_Account.html - The Mars Pathfinder Bug

  • http://www.cs.berkeley.edu/~brewer/cs262/PriorityInversion.html - Priority Inversion explained via the Mars Pathfinder Bug