Solutions for Real-Time System by Jane W. S. Liu (Chapter 6)

Chapter 6 starts with workloads consisting solely of independent periodic tasks that do not require any resource other than a processor. This post provides the possible solutions for Chapter 6 in Real-Time System by Jane W. S. Liu. The book is available here.

Q.6.4: A system T contains for periodic tasks, (8, 1), (15, 3), (20, 4), and (22, 6). Its total utilization is 0.80. Construct the initial segment in the time interval (0, 50) of a rate-monotonic schedule of the system.

Q.6.5: Which of the following systems of periodic tasks are schedulable by the rate-monotonic algorithm? By the earliest-deadline-first algorithm? Explain your answer.

  1. T = {(8, 3), (9, 3), (15, 3)}

2. T = {(8, 4), (12, 4), (20, 4)}

3. T = {(8, 4), (10, 2), (12, 3)}

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.

Q.6.8: a) Use the time demand analysis method to show that the rate-monotonic algorithm will produce a feasible schedule of the tasks (6,1), (8,2) and (15,6).

b) Change the period of one of the tasks in part (a) to yield a set of tasks with the maximal total utilization which is feasible when scheduled using the rate-monotonic algorithm. (Consider only integer values for the period)

c) Change the execution time of one of the tasks in part (a) to yield a set of tasks with the maximum total utilization which is feasible when scheduled using the rate-monotonic algorithm. (Consider only register values for the execution time).

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?

Q.6.10: Which of the following fixed-priority task is not schedulable? Explain your answer.

T1(5,1) T2(3,1) T3(7,2.5) T4(16,1)

Q.6.11: Find the maximum possible response time of tasks T4 in the following fixed-priority system by solving the equation w4(t) = t, iteratively

T1 = (5,1), T2 = (3,1), T3 = (8,1.6), and T4 = (18,3.5)

Q.6.13: Find the length of an in-phase level-3 busy interval of the following fixed-priority tasks:

T1 = (5, 1), T2 = (3,1), T3 = (8, 1.6), and T4 = (18, 3.5)

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) non-preemptable. What is the maximum value of x so that the system remains schedulable according to the rate-monotonic algorithm?

Q.6.23: A system contains tasks T1 = (10,3), T2 = (16,4), T3 = (40,10) and T4 = (50,5). The total blocking due to all factors of the tasks are b1 = 5, b2 = 1, b3 = 4 and b4 = 10, respectively. These tasks are scheduled on the EDF basis. Which tasks (or task) are (or is) schedulable? Explain your answer.

Q.6.31: Interrupts typically arrive sporadically. When an interrupt arrives, interrupt handling is serviced (i.e., executed on the processor) immediately and in a non-preemptable fashion. The effect of interrupt handling on the schedulability of periodic tasks can be accounted for in the same manner as blocking time. To illustrate this, consider a system of four tasks: T1 = (2.5, 0.5), T2 = (4, 1), T3 = (10, 1), and T4 = (30, 6). Suppose that there are two streams of interrupts. The inter-release time of interrupts in one stream is never less than 9, and that of the other stream is never less than 25. Suppose that it takes at most 0.2 units of time to service each interrupt. Like the periodic tasks interrupt handling tasks (i.e., the stream of interrupt handling jobs) are given fixed priorities. They have higher priorities than the periodic tasks, and the one with a higher rate (i.e., shorter minimum inter-release time) has a higher priority.

a) What is the maximum amount of time each job in each periodic task may be delayed from completion by interrupts?

b) Let the maximum delay suffered by each job in Ti in part (a) be bi, for i = 1, 2, 3, and 4. Compute the time-demand functions of the tasks and use the time-demand analysis method to determine whether every periodic task Ti can meet all its deadlines if Di is equal to pi.

c) In one or two sentences, explain why the answer you obtained in (b) about the schedulability of the periodic tasks is correct and the method you use works not only for this system but also for all independent preemptive periodic tasks.

Researcher in Data Sciences

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store