习题和答案ECTE431-ECTE931-Tutorial-2-Solution-Word

1 ECTE431/ECTE931: REAL-TIME COMPUTING Tutorial 2: Priority-driven Scheduling of Periodic Tasks Solution 1. Give two different explanations of why the periodic tasks (2,1), (4,1) and (8,2) are schedulable by the rate-monotonic algorithm. Solution: Using schedulable utilisation test The total utilisation: 1/2 + 1/4 + 2/8 = 1. Because the total utilisation is less than or equal to 1 and this is a “simply periodic” task set, the task set is schedulable with the RM algorithm. Using exhaustive scheduling simulation 2 2. A system consists of three preemptable periodic tasks T1 = (3, 1), T2 = (5, 2) and T3 = (8,3) a) What is the total utilisation? b) Construct the earliest-deadline-first schedule for this system for the time interval 0, 32). Label all missed deadlines. c) Construct a rate-monotonic schedule for this system in the interval 0, 32). Label all missed deadlines. d) Suppose we want to reduce the execution time of task T3 to make the system schedulable with the EDF algorithm. What is the maximum execution time of task T3? d) Suppose we want to reduce the execution time of task T3 to make the system schedulable with the RM algorithm. What is the maximum execution time of task T3 according to the schedulable utilisation test? Solution: a) U = 1/3 + 2/5 + 3/8 = 1.1083 1. Therefore the task set is not schedulable and there will be missed deadlines. b) EDF schedule 3 c) RM schedule d) EDF Maximum utilisation for T3: 1 1/3 2/5 = 0.2667 Maximum execution time for T3: 0.2667 8 = 2.1333 e) RM Maximum utilisation for T3 (given that URM(3) = 0.780) 0.780 - 1/3 2/5 = 0.0467 Maximum execution time for T3: 0.0467 8 = 0.3733 4 3. The periodic tasks (3,1), (4,2), and (6,1) are scheduled according to the rate-monotonic algorithm. Draw the time-demand functions of the tasks. Are the tasks schedulable? Solution: Task 1: 1( ) 1, 0 3w tt= Task 2: 2( ) 21, 0 4 3 t w tt =+ T2. Use the time-demand analysis, determine a) Whether the tasks are schedulable? b) The maximum execution time of task T2 that makes all tasks schedulable? Solution: a) Task T1: 1( ) 1, 0 4w tt= Task T3: 3( ) 31, 0 10 4 t w tt =+ Task T2: 2( ) 313, 0 7 410 tt w tt =+ + 01234567891011 0 1 2 3 4 5 6 7 8 9 10 11 t Time Demand Functions w1(t) w3(t) w2(t) f(t)=t Tasks T1 and T3 are