词条 | Rate-monotonic scheduling | |||||||||||||||||||
释义 |
In computer science, rate-monotonic scheduling (RMS)[1] is a priority assignment algorithm used in real-time operating systems (RTOS) with a static-priority scheduling class.[2] The static priorities are assigned according to the cycle duration of the job, so a shorter cycle duration results in a higher job priority. These operating systems are generally preemptive and have deterministic guarantees with regard to response times. Rate monotonic analysis is used in conjunction with those systems to provide scheduling guarantees for a particular application. IntroductionA simple version of rate-monotonic analysis assumes that threads have the following properties:
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. {{harvtxt|Liu|Layland|1973}} proved that for a set of {{mvar|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 {{mvar|Ci}} is the computation time, {{mvar|Ti}} is the release period (with deadline one period later), and {{mvar|n}} is the number of processes to be scheduled. For example, {{mvar|U ≤ 0.8284}} for two processes. When the number of processes tends towards infinity, this expression will tend towards: Therefore, a rough estimate is that RMS can meet all of the deadlines if CPU utilization is less than 69.32%. 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,[3] however this fact depends on knowing the exact task statistics (periods, deadlines) which cannot be guaranteed for all task sets. The hyperbolic bound[4] is a tighter sufficient condition for schedulability than the one presented by Liu and Layland: , where {{mvar|Ui}} is the CPU utilization for each task. 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.[5] For the task model in which deadlines can be greater than periods, Audsley's algorithm endowed with an exact schedulability test for this model finds an optimal priority assignment.[6] Avoiding priority inversionIn 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 disabling preemption or by priority inheritance. Alternative methods are to use lock free algorithms or avoid the sharing of a mutex/semaphore across threads with different priorities. This is so that resource conflicts cannot result in the first place. Disabling of preemption
Priority inheritance
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.{{Citation needed|date=October 2007}} An example of usage of basic priority inheritance is related to the "Mars Pathfinder reset bug" [12][13] 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: The sufficient condition for processes, under which we can conclude that the system is schedulable is: Since the system is surely schedulable. But remember, this condition is not a necessary one. So we cannot say that a system with higher utilization is not schedulable with this scheduling algorithm. See also
References1. ^{{citation|first1=C. L.|last1=Liu|authorlink1=Chung Laung Liu|first2=J.|last2=Layland|title=Scheduling algorithms for multiprogramming in a hard real-time environment|journal=Journal of the ACM|volume=20|issue=1|year=1973|pages=46–61|doi=10.1145/321738.321743|citeseerx=10.1.1.36.8216}}. 2. ^{{citation|first1=Daniel P.|last1=Bovet|first2=Marco|last2=Cesati|title=Understanding the Linux Kernel}}, http://oreilly.com/catalog/linuxkernel/chapter/ch10.html#85347 {{webarchive|url=https://web.archive.org/web/20140921000832/http://oreilly.com/catalog/linuxkernel/chapter/ch10.html |date=2014-09-21 }}. 3. ^{{citation|first1=J.|last1=Lehoczky|first2=L.|last2=Sha|first3=Y.|last3=Ding|contribution=The rate monotonic scheduling algorithm: exact characterization and average case behavior|title=IEEE Real-Time Systems Symposium|pages=166–171|year=1989|doi=10.1109/REAL.1989.63567|isbn=978-0-8186-2004-1}}. 4. ^{{citation|authors=Enrico Bini, Giorgio C. Buttazzo and Giuseppe M. Buttazzo|title=Rate Monotonic Analysis: the Hyperbolic Bound|journal=IEEE Transactions on Computers|year=2003|volume=52|issue=7|pages=933–942|doi=10.1109/TC.2003.1214341}} 5. ^{{citation|first1=J. Y.|last1=Leung|first2=J.|last2=Whitehead|title=On the complexity of fixed-priority scheduling of periodic, real-time tasks|journal=Performance Evaluation|volume=2|issue=4|pages=237–250|year=1982|doi=10.1016/0166-5316(82)90024-4}}. 6. ^{{citation|author=Alan Burns and Andy Wellings|title=Real-Time Systems and Programming Languages|year=2009|publisher=Addison-Wesley|edition=4th|isbn=978-0-321-41745-9|pages=391,397}} 7. ^{{citation|first1=B. W.|last1=Lampson|authorlink1=Butler Lampson|first2=D. D.|last2=Redell|title=Experience with processes and monitors in Mesa|journal=Communications of the ACM|volume=23|issue=2|year=1980|pages=105–117|doi=10.1145/358818.358824|citeseerx=10.1.1.46.7240}}. 8. ^{{citation|last=Buttazzo|first=Giorgio|title=Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications|publisher=Springer|location=New York, NY|year=2011|edition=Third|page=225}} 9. ^{{cite web | url = https://rt.wiki.kernel.org/index.php/Frequently_Asked_Questions#How_does_the_CONFIG_PREEMPT_RT_patch_work.3F | title = Real-Time Linux Wiki | date = 2008-03-26 | accessdate = 2014-03-14 | publisher = kernel.org}} 10. ^{{citation|first1=L.|last1=Sha|first2=R.|last2=Rajkumar|first3=J. P.|last3=Lehoczky|title=Priority inheritance protocols: an approach to real-time synchronization|journal=IEEE Transactions on Computers|volume=39|issue=9|year=1990|pages=1175–1185|doi=10.1109/12.57058}}. 11. ^{{citation|last=Buttazzo|first=Giorgio|title=Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications|publisher=Springer|location=New York, NY|year=2011|edition=Third|page=212}} 12. ^http://research.microsoft.com/~mbj/Mars_Pathfinder/ 13. ^http://anthology.spacemonkeys.ca/archives/770-Mars-Pathfinder-Reset-Bug.html Further reading
External links
2 : Processor scheduling algorithms|Real-time computing |
|||||||||||||||||||
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。