Ratemonotonic scheduling
From Academic Kids

In computer science, ratemonotonic scheduling [Liu73] is an optimal preemptive staticpriority scheduling algorithm used in realtime operating systems. The inputs to the algorithm are processes (tasks, threads) with :
 No resource sharing (processes x and y do not share resource, 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 Leyland proved that the for a set of <math>m<math> periodic tasks, a feasible schedule that will always meet deadlines exists if the CPU utilization is:
 <math>U = \sum_{i=1}^{m} c_i / p_i \leq m(\sqrt[m]{2}  1)<math>
Where <math>p_i<math> is the cycle time, or period and <math>c_i<math> is the computation time. For example <math>U = 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(\sqrt[m]{2}  1) = \ln 2 \approx 0.693147\ldots<math>
So a rough estimate is that RMS in the general case can meet all the deadlines if CPU utilization is <math>69.3\%<math>. The other <math>30.7\%<math> of the CPU can be dedicated to lowerpriority non realtime tasks. It is known that a randomly generated periodic task system will meet all deadlines when the utilization is <math>85\%<math> or less [Lehoczky89], 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 algorithm is also optimal in the situation where periods and deadlines are identical, in the fact the algorithms are identical, and in addition, deadline monotonic scheduling is optimal when deadlines are less than periods [Leung80].
An optimal staticpriority scheduling algorithm when deadlines are greater than periods is an open problem.
Contents 
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 realtime kernel (uCOS II kernel),
 The splx() family of primitives which nest the locking of device interrupts (UNIX/Linux kernel),
 The Highest Locker protocol which requires offline analysis of all task conflicts to find a "ceiling priority" (see below),
 The Basic Priority Inheritance Protocol [Lampson80] which waits until a high priority task requests a lock held by a lowpriority 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 [Sha90] 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) ?
pessimistic  optimistic 

immediate 
OSIntEnter/Exit() 
splx(), Highest Locker 
lazy 
Priority Ceiling Protocol Basic Priority Inheritance Protocol 
In practice there is no mathematical difference (in terms of the LiuLayland 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 is not useful because it 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 realtime kernel but is seldom enabled. A notable exception is "The Mars Pathfinder Bug" which was fixed on the way to Mars by enabling Priority Ceiling Protocol Semaphores in the Mars Pathfinder Spacecraft vehicle. See The Mars Pathfinder Bug (http://research.microsoft.com/~mbj/Mars_Pathfinder/Authoritative_Account.html) at Microsoft Research for details.
Example
Process  Execution Time  Period 
P1  1  8 
P2  2  5 
P3  2  10 
The utilization will be:
 <math>\frac{1}{8} + \frac{2}{5} + \frac{2}{10} = 0.725<math>
The theoretical 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
References
 C. L. Liu and J. Layland. Scheduling algorithms for multiprogramming in a hard realtime environment, Journal of the ACM, 10(1), 1973.
 J. Lehoczky, L. Sha and Y. Ding, The Rate monotonic scheduling algorithm: exact characterization and average case behavior, IEEE RealTime Systems Symposium, pp. 166171, December 1989.
 J. Y. Leung and J. Whitehead. On the complexity of fixedpriority scheduling of periodic, realtime tasks. Performance Evaluation, 2(4):237250, 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. 105117.
 L. Sha, R. Rajkumar and J. P. Lehoczky, Priority inheritance protocols: an approach to realtime synchronization, IEEE Transactions on Computers, vol. 39 no. 9, September 1990, pp. 11751185.
External Links
 Introduction to Rate Monotonic Scheduling (http://www.netrino.com/Publications/Glossary/RMA.html)