Real Time System by Jane W. S. Liu Chapter 6.7 Solution

Q.6.7: This problem is concerned with the performance an behavior of rate-monotonic an earliest-deadline-first algorithms.

1. Construct the initial segments in the time interval (0, 750) of a rate-monotonic schedule and an earliest-deadline-first schedule of the periodic tasks (100, 20) (150, 50), and (250, 100) whose total utilization is 0.93.

   
   

   Sol:

   
   

   RM

   
   

   

   
   

   Note, the third task (the blue one) runs past its deadline from t = 250 to t = 260.

   
   

   EDF

   
   

   

   
   

   There are no missed deadlines in this schedule.
   

   
   

2. Construct the initial segments in the time interval (0, 750) of a rate-monotonic schedule and an earliest-deadline-first schedule of the periodic tasks (100, 20) (150, 50), and (250, 120) whose total utilization is 1.01.

   Sol: 

   
   

   RM

   
   

   

   
   The third task (the blue one) runs past its deadline from 250 to 280 and from 520 to 560. The third task will continue to be backlogged farther and farther each time a new job in the task is released, but the first and second task are not affected.

   
   

   EDF

   
   

   

   
   Task 2 eventually misses its deadline. Once jobs start missing deadlines, almost every job is going to miss its deadline.
   
   
   
   
   

   Rate Monotonic vs. EDF

   Since the first results published in 1973 by Liu and Layland on the Rate Monotonic (RM) and Earliest Deadline First (EDF) algorithms, a lot of progress has been made in the schedulability analysis of periodic task sets. Unfortunately, many misconceptions still exist about the properties of these two scheduling methods, which usually tend to favor RM more than EDF. Typical wrong statements often heard in technical conferences and even in research papers claim that RM is easier to analyze than EDF, it introduces less runtime overhead, it is more predictable in overload conditions, and causes less jitter in task execution. Since the above statements are either wrong, or not precise, it is time to clarify these issues in a systematic fashion, because the use of EDF allows a better exploitation of the available resources and significantly improves system’s performance.

   Most commercial RTOSes are based on RM. RM is simpler to implement on top of commercial (fixed priority) kernels.

   EDF requires explicit kernel support for deadline scheduling, but gives other advantages. 

   Less overhead due to preemptions. 

   More uniform jitter control

   Better aperiodic responsiveness.

   Two different types of overhead:

   Overhead for job release

   EDF has more than RM, because the absolute deadline must be updated at each job activation

   Overhead for context switch

   RM has more than EDF because of the higher number of preemptions

   
   

   Resource access protocols:
   

   For RM

   Non Preemptive Protocol (NPP)

   Highest Locker Priority (HLP)

   Priority Inheritance (PIP)

   Priority Ceiling (PCP)

   Under EDF

   Non Preemptive Protocol (NPP)

   Dynamic Priority Inheritance (D-PIP)

   Dynamic Priority Ceiling (D-PCP)

   Stack Resource Policy (SRP)

   
   

   
   

   
   

   Next Topic:

   Q.6.9: The Periodic Tasks (3,1), (4,2), (6,1) are scheduled according to the rate-monotonic algorithm.

   a)  Draw Time Demand Function of the tasks   

   b)  Are the tasks schedulable? Why or why not ?

   c)  Can this graph be used to determine whether the tasks are schedulable according to an arbitrary priority-driven algorithm?

   SOLUTION

   
   

   
   

   Previous Topic:

   
   

   Q.6.6: Give two different explanation of why the periodic tasks (2,1), (4,1) and (8,2) are schedulable by the rate monotonic algorithm.

   SOLUTION