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

Q.6.15: A system consists of three periodic tasks: (3, 1), (5, 2), and (8, 3).

1. What is the total utilization?
   
   
   Sol: U = 1/3 + 2/5 + 3/8 ≈ 1.11
   
   
   
   
2. Construct an earliest-deadline-first schedule of this system in the interval (0, 32). Label any missed deadlines.
   
   

   Sol:
   

                    

   
   

   Yellow stripes indicates missed deadlines.
   

   
   

   
   
3. Suppose we want to reduce the execution time of the task with period 3 in order to make mthe task system schedulable according to the earliest-deadline-first algoorithm. What is the minimum amount of reduction mecessary for the system to be schedulable by the earliest-deadline-first algorithm?
   
   
   Sol:
                    
   
   Yellow stripes indicates missed deadlines.
   

   
   

   
   
4. Suppose we want to reduce the execution time of the task with period 3 in order to make the task system schedulable according to the earliest-deadline-first algoirthm. What is the minimum amount of reduction necessary for the system to be schedulable by the earliest-deadline-first algorithm?
   
   Sol:        U = (1-x)/3 + 2/5 + 3/8 ≤ 1
                 x ≥ 0.325
   
   
   

   Utilization Bounds for EDF Scheduling

           The utilization bound for Earliest Deadline First scheduling is extended 

   from uniprocessors to homogeneous multiprocessor systems with partitioning strategies. First results are provided for a basic task model, which includes periodic and independent tasks with deadlines equal to periods. n bounds depend on the allocation algorithm, different allocation algorithms have been considered, ranging from simple heuristics to optimal allocation algorithms.

           As multiprocessor utilization bounds for EDF scheduling depend strongly on task sizes, all these bounds have been obtained as a function of a parameter which takes task sizes into account.Theoretically, the utilization bounds for multiprocessor EDF scheduling can be considered a partial solution to the bin-packing problem, which is known to be NP-complete. The basic task model is extended to include resource sharing release jitter, deadlines less than periods, aperiodic tasks, non-preemptive sections, context switches and mode changes.

   
   

   
   
   

   Next Topic:

   Q.6.21: a) Use the time-demand analysis method to show that the set of periodic tasks {(5, 1), (8, 2), (14, 4)} is schedulable according to the rate-monotonic algorithm.

   b)    Suppose that we want to make the first x units of each request in the task (8,2) nonpreemptable.  What is the maximum value of x so that the system remains schedulable according to the rate-monotonic algorithm?
   SOLUTION

   
   

   
   Previous Topic:

   Q.6.13: Find the length of an in-phase level-3 busy interval of the following fixed-priority tasks:
   T₁ = (5, 1), T₂ = (3,1), T₃ = (8, 1.6), and T₄ = (18, 3.5)

   SOLUTION