DOC PREVIEW
UT EE 382C - Rate Monotonic Theory

This preview shows page 1-2-3 out of 8 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Rate Monotonic TheoryA literature survey by Nate FormanIntroductionNobody likes missing deadlines. That kind of behavior can do horrible things to aclass grade or cause trouble in the office. However, when dealing with hard deadlines inreal-time systems, the consequences can be much more severe. If a hard real-time systemmisses its deadline, it can mean safety problems for patients at hospitals, thousands ofdollars of lost product at a factory, or even failure for a multi-million dollar spacemission. These consequences make scheduling in hard real-time systems a very relevantarea of study. This survey discusses rate monotonic theory (analysis and scheduling), amodel that allows schedulability analysis for real-time systems.Basic PremisesThe term rate monotonic derives from a method of assigning priorities to a set ofprocesses as a monotonic function of their rates. [4] While rate monotonic schedulingsystems use rate monotonic theory for actually scheduling sets of tasks, rate monotonicanalysis can be used on tasks scheduled by many different systems to reason aboutschedulablility. We say that a task is schedulable if the sum of its preemption, execution,and blocking is less than its deadline.[2] A system is schedulable if all tasks meet theirdeadlines. Rate monotonic analysis provides a mathematical and scientific model forreasoning about schedulability.AssumptionsReasoning with rate monotonic analysis requires the presence of the followingassumptions [4]:• Task switching is instantaneous.• Tasks account for all execution time.• Task interactions are not allowed.• Tasks become ready to execute precisely at the beginning of their periods andrelinquish the CPU only when execution is complete.• Task deadlines are always at the start of the next period.• Tasks with shorter periods are assigned higher priorities; the criticality oftasks is not considered.• Task execution is always consistent with its rate monotonic priority: a lowerpriority task never executes when a higher priority task is ready to execute.It is immediately obvious that some of these assumptions do not completelyconform to actual systems. However, extensions to broaden these assumptions will bediscussed later. The importance of these assumptions is that they allow reasoning withcertainty about whether or not a set of tasks can be scheduled.BenefitsGiven certain information about a particular set of tasks, under rate monotonicconditions, one can evaluate certain tests to understand whether or not those tasks can allmeet their deadlines in a real time system. Because these values are known at design timeand are monotonic, any analysis and scheduling can be done statically. Static schedulingis one advantage that the industry has a strong preference for in hard real-timeapplications. [4] This subsection will examine two schedulability tests that can be usedunder rate-monotonic assumptions.Given the computation time, Ci, and period, Ti, for task i, its CPU utilization canbe calculated with the following equation:Ui = Ci/TiFor rate monotonic scheduling, the processor utilization for n tasks has been shown to bethe following:U(n) = n(21/n – 1)U(n) asymptotically converges to ln(2) or 69%, which is less efficient than some runtimeschedulers such as earliest deadline, but again, there is a strong preference for staticscheduling. [4] The utilization bound (UB) test allows schedulability analysis bycomparing the calculated utilization for a set of tasks and comparing that total to thetheoretical utilization for that number of tasks:C1/T1 + … + Cn/Tn <= U(n) = n(21/n – 1)If this equality is satisfied, all of the tasks will always meet their deadlines. If the totalutilization calculates to greater than 100%, the system will have scheduling problems.However, if the total utilization is between the utilization bound and 100%, the UB test isinconclusive and a more precise test must be used.The response time (RT) test allows analysis of schedulability based upon thefollowing theorem:For a set of independent periodic tasks, if each task meets its deadline withworst case task phasing, the deadline will always be met. [2]The RT test requires computation of the response time of each task in the system. Basedon the above theorem if each response time is less than its corresponding period, thesystem is schedulable. The following is the calculation for an or the response time of taski:The test terminates when an+1 = an. The system is schedulable if each response timefinishes before its deadline.ExtensionsThe interplay between research and application has resulted in the extension ofrate monotonic theory from its original form of scheduling independent periodic tasks toscheduling both periodic and aperiodic tasks with synchronization requirements andmode change requirements. [4] These extensions have greatly enhanced the usability ofthe model while maintaining its desirable property of allowing mathematical reasoningabout schedulability. The following subsections discuss some of these extensions.Sporadic ServerMost systems are not limited to periodic tasks that happen regularly andmonotonically, but also include aperiodic tasks. These tasks can be included in the modelby the addition of one or more aperiodic servers. An aperiodic server is a conceptual taskthat is endowed with an execution budget and a replenishment period. An aperiodicserver will handle randomly arriving requests at its assigned priority (determined by theRM algorithm based on its replenishment period) as long as the budget is available. [4]jijjninCTaCa∑−=++=111∑==ijjCa10Several versions of the aperiodic server were developed before a suitable one wasfound. That algorithm is the sporadic server algorithm. The sporadic server, like itspredecessors, allocates a computation budget and a replenishment period to the executionof aperiodic tasks. However, with the sporadic server, the aperiodic task budget is notreplenished periodically, but is replenished only after a period in which it was completelyconsumed. This implementation avoids a subtle violation of the rate monotonicassumptions, known as the deferred execution effect, that troubled earlier versions withdifferent replenishment techniques. With this violation eliminated, the sporadic server isan aperiodic server that is equivalent to any periodic task under the rate monotonicassumptions.Priority Ceiling ProtocolThe NASA Mars Lander project was subject to hard


View Full Document

UT EE 382C - Rate Monotonic Theory

Documents in this Course
Load more
Download Rate Monotonic Theory
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Rate Monotonic Theory and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Rate Monotonic Theory 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?