Solutions for Real-Time System by Jane W. S. Liu (Chapter 8)
This post provides the possible solutions for Chapter 8in Real-Time System by Jane W. S. Liu. The book is available here.
Q.8.1: A system contains five jobs. There are three resources X, Y and Z. The resources required of the jobs are listed below.
J1: [X;2]
J2 : NONE
J3 : [Y;1]
J4 : [X;3 [Z;1]]
J5 : [Y;4 [Z;2]]
The priority Ji is higher than the priority of Jj for i < j. What are the maximum blocking times of the jobs under the non-preemptable critical section protocol and under the priority ceiling protocol?
Q.8.2: A system contains the following four periodic tasks. The tasks are scheduled by the rate monotonic algorithm and the priority ceiling protocol.
T1 = (3,0.75) b1 = 0.9
T2 = (3.5,1.5) b2 = 0.75
T3 = (6,0.6) b3 = 0.9
T4 = (10,1)
bi is the blocking time of Ti. Are the tasks schedulable? Explain your answer.
Q.8.3: Consider a fixed priority system in which there are five tasks Ti, for i = 1, 2, 3, 4 and 5, with decreasing priorities. There are two resources X and Y. The critical sections of T1,T2, T4 and T5 are [Y;3], [X;4], [Y;5 [X;2]] and [X;10] respectively. (Note that T3 does not require any resource.) Find the blocking time bi(rc) of the tasks.
Sol: Priority Ceiling (with Blocking time)
Q.8.7: A system contains the following five periodic tasks. The tasks are scheduled rate monotonically.
T1 = (6, 3, [X;2])
T2 = (20, 5, [Y;2])
T3 = (200, 5, [X;3 [Z;1]])
T4 = (210, 6, [Z;5 [Y;4]])
Compare the schedulability of the system when the priority ceiling protocol is used versus the NPCS protocol.
Q.8.10: Given a system consisting of the following tasks whose periods, execution times and resource requirements are given below.
T1 = (2, 0.4, [X, 3; 0.3])
T2 = (3, 0.75, [X, 1; 0.3][Y, 1; 0.4])
T3 = (6, 1.0, [Y, 1; 0.4][Z, 1; 0.5 [X, 1; 0.4]])
T4 = (8, 1.0, [X, 1; 0.5][Y, 2; 0.1] [Z, 1; 0.4])
There are 3 units of X, 2 units of Y and 1 unit of Z. The tasks are scheduled by EDF algorithm and the stack based protocol.
a) Find the preemption ceiling of each resource and the maximum blocking time for each task.
Sol: Preemption Ceilings
b) Are the tasks schedulable according to the earliest deadline first algorithm? Why?
