Rate-monotonic Scheduling

• 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)

$U\; \backslash leq\; m(\backslash sqrtm\{2\}\; -\; 1)$

$\backslash lim\_\{m\; \backslash rightarrow\; \backslash infty\}\; m(\backslash sqrtm\{2\}\; -\; 1)\; =\; \backslash ln\; 2\; \backslash approx\; 0.693147\backslash ldots$

Resource preemption, priority inheritance

• 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 (UNIX/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 Lampson80 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 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.

Example

$\backslash frac\{1\}\{8\}\; +\; \backslash frac\{2\}\{5\}\; +\; \backslash frac\{2\}\{10\}\; =\; 0.725$

$U\; =\; 3(2^\backslash frac\{1\}\{3\}\; -\; 1)\; =\; 0.77976\backslash ldots$

See also

• Scheduling
• Earliest deadline first scheduling
• Dynamic priority scheduling

References

• C. L. Liu and J. Layland. Scheduling algorithms for multiprogramming in a hard real-time 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 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.

<< Previous Word Browser Next >>
prestige (sociology) shallow chai wan christopher locke st. paul's college, hong kong reputation optimistic concurrency control absurdism pga mozilla browser renal sinus	pin grid array zip zig zag in line package dob jean baptiste klber energie cottbus eugenio corini cubic foot wood warbler cubic yard vasile miriuta	hong tianguifu french revolutionary wars blight hms plym (k271) chiefs of state and cabinet members of foreign governments river plym liang fa round robin pulse detonation engine round robin scheduling monte bello islands, western australia	bruno akrapovic burn leslie wexner trainspotting (novel) sablecc pva polyvinyl acetate radio control the eustace diamonds anna of the five towns the old wives' tale