Real Time Scheduling Analysis Rate monotonic Analysis (RMA) is a model for predi
ID: 3687735 • Letter: R
Question
Real Time Scheduling Analysis
Rate monotonic Analysis (RMA) is a model for predicting whether or not a system will meet its timing as well as throughput requirements when the system is operational. To build systems that are reliable and deterministic, the timing behavior of the tasks in a program must be predictable. If the system is predictable, it can be formally analyzed. RMA is one analysis tool that allows the designer to determine ahead of time whether the system will meet its real time requirements.
a) The figures below represent a real system with three multi-threaded tasks. Task A is scheduled every 10 ms and is the highest priority. Task B is scheduled every 20 ms, and Task C scheduled every 40 ms. The execution times for all three tasks in table 1 are WCET. Will this system meet all of its deadlines based on RMA formula calculations? If not, why?
b) What are practical ways for estimating WCET?
RMA cl c2 t t2 Recall a RMS schedule always exists if UExplanation / Answer
C and T represent the execution time and period respectively associated with periodic task . As the number of tasks increases, the scheduling bound converges to ln 2 (69%). We willi refer to this as the basic rate monotonic
A) The utilization will be:
1/10+5/20+10/40 = 0.1+0.25+0.25 = 0.6
The sufficient condition for 3 processes, under which we can conclude that the system is schedulable is:
U = 3(21/3-1) = 0.77976
Since 0.6 < 0.77976 the system is surely schedulable.
b)
The scheduling algorithm you choose depends on your goals. Different algorithms yield different results. Let's suppose you're given ten jobs and each will take a day to finish. In ten days, you will have all of them done. But what if one or more has a deadline? If the ninth task given to you has a deadline in three days, then doing the tasks in the order you receive them will cause you to miss that deadline.
The purpose of a real-time scheduling algorithm is to ensure that critical timing constraints, such as deadlines and response time, are met. When necessary, decisions are made that favor the most critical timing constraints, even at the cost of violating others. Real-time scheduling is also used to allocate processor time between tasks in soft real-time embedded systems
Priority-based scheduling:
Many real-time systems use preemptive multitasking, especially those with an underlying real-time operating system (RTOS). Priorities are assigned to tasks, and the RTOS always executes the ready task with highest priority.
In this case, the scheduling algorithm is the method in which priorities are assigned. Most algorithms are classified as fixed priority, dynamic priority, or mixed priority. A fixed-priority algorithm assigns all priorities at design time, and those priorities remain constant for the lifetime of the task. A dynamic-priority algorithm assigns priorities at runtime, based on execution parameters of tasks, such as upcoming deadlines. A mixed-priority algorithm has both static and dynamic components. Needless to say, fixed-priority algorithms tend to be simpler than algorithms that must compute priorities on the fly.
To demonstrate the importance of a scheduling algorithm, consider a system with only two tasks, which we'll call t1 and t2. Assume these are both periodic tasks with periods T1 and T2, and each has a deadline that is the beginning of its next cycle. Task t1 has T1 = 50ms, and a worst-case execution time of C1 = 25ms. Task t2 has T2 = 100ms and C2 = 40ms. Note that the utilization, Ui, of task ti is Ci/Ti. Thus U1 = 50% and U2 = 40%. This means total requested utilization U = U1 + U2 = 90%. It seems logical that if utilization is less than 100%, there should be enough available CPU time to execute both tasks.
Let's consider a static priority scheduling algorithm. With two tasks, there are only two possibilities:
Case 1: Priority(t1) > Priority(t2)
Case 2: Priority(t1) <>2)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.