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

Chapter 7 adds aperiodic and sporadic tasks. This post provides the possible solutions for Chapter 6 in Real-Time System by Jane W. S. Liu. The book is available here.

Q.7.1: A system contains three periodic tasks. They are (2.5,1), (4,0.5), (5,0.75), and their total utilization is 0.475.

a) The system also contains a periodic server (2,0.5). The server is scheduled with the periodic tasks rate-monotonically.

1. Suppose that the periodic server is a basic sporadic server. What are the response time of the following two aperiodic jobs: One arrives at 3 and has execution time 0.75, and one arrives at 7.5 and has execution time 0.6.

2. Suppose that the periodic server is a deferrable server. What are the response times of the above two aperiodic jobs.

b) Note that the utilization of the periodic server in part (a) is 0.25. We can give the server different periods while keeping its utilization fixed at 0.25. Repeat (1) and (2) in part (a) if the period of the periodic server is 1.

c) Can we improve the response times by increasing the period of the periodic server?

d) Suppose that as a designer you were given (1) the characteristics of the periodic tasks, that is, (p1,e1), (p2,e2),…..(pn,en), (2) the minimum interval pa between arrivals of aperiodic jobs, and (3) the maximum execution time required to complete any aperiodic job. Suppose that you are asked to choose the execution budget and period of a deferrable server. Suggest a set of good design rules.

Q.7.2: A system contains three periodic tasks. They are (3,1), (4,0.5), (5,0.5).

The task system also contains a sporadic server whose period is 2. The sporadic server is scheduled with the periodic tasks rate-monotonically. Find the maximum utilization of the server if all deadlines of periodic tasks are surely met.

1)Suppose that the server in part (a) is a pure polling server. What are the response time of the following two aperiodic jobs: one arrives at 2.3 and has execution time 0.8 , and one arrives at 12.7 and has execution time 0.6 ?

2) Suppose that the server in part (a) is a basic sporadic server. What are the response time of the above two aperiodic jobs?

Q.7.3: Consider a system containing the following periodic tasks: T1 = (10,2), T2 = (14,3) and T3 = (21,4). A periodic server of period 8 is used to schedule aperiodic jobs.

a) Suppose that the server and the tasks are scheduled rate-monotonically.

1) If the periodic server is a deferrable server, how large can its maximum execution budget be?

2) If the periodic server is a sporadic server, how large can its maximum execution budget be?

b) Suppose that the server and the tasks are scheduled on the EDF basis. Repeat the (a).

Q.7.4: Consider a system that contains two periodic tasks T1 = (7,2) and T2 = (10,3). There is a bandwidth preserving server whose period is 6. suppose that the periodic tasks and the server are scheduled rate-monotonically.

a) Suppose that the server is deferrable server.

1. What is the maximum server size?

2. Consider two aperiodic jobs A1 and A2. The execution times of the jobs are equal to 1.0 and 2.0, respectively. Their arrival times are 2 and 5. What are their response time?

b) Suppose that the server is a simple sporadic or SpSL sporadic server.

1)What is the maximum server size?

2) Find the response times of jobs A1 and A2 in part (a) if the server is a SpSL server.

Q.7.5: Suppose that the periodic tasks in the previous problem are scheduled along with a server on the earliest deadline first basis.

a) What is the maximum server size if the server size if the server is a deferrable server? Is this size a function of the period of the server? If not, why not? If yes, what is the best choice of server size?

b) What is maximum server size if the server is a total bandwidth server?

c) Find the response time of A1 and A2 in problem 7.4 for servers in part (a) and (b).

Q.7.19: Davis et al., suggested a dual priority scheme for scheduling aperiodic jobs in the midst of periodic tasks. According to dual priority scheme, the system keeps three bands of priority, each containing one or more priority levels. The highest band contains real time priorities: they are for hard real time tasks. Real time priorities are assigned to hard real time tasks according to some fixed priority scheme. The middle priority band is for aperiodic jobs. The lowest priority band is also hard real time tasks. Specifically, when jobs Ji,k in a periodic task Ti = (pi, ei, Di) is released , it has a priority in the lowest priority band until its priority promotion time. At its priority promotion time, its priority is raised to its real time priority. Let Wi denote the maximum response time of all jobs in Ti when they execute at the real time priority of the task. The priority promotion time of each job is Yi = Di — Wi from its release time. Since Wi can be computed off line or at admission control time, the release promotion time Yi for jobs in each tasks Ti needs to be computed only once. By delaying as much as possible the scheduling of every hard real time jobs at its real time priority, the scheduler automatically creates slacks for aperiodic jobs.

a) Give an intuitive argument to support the claim that this scheme will not cause any periodic job to miss its deadline if the system of periodic tasks is schedulable.

b) A system contains three periodic task: They are (2.5,0.5), (3,1) and (5,0.5). Compute the priority promotion times for jobs in each of the tasks if the tasks are scheduled rate-monotonically.

c) Suppose that there are two aperiodic jobs. One arrives at 1.9, and the other arrives at 4.8. Their execution times are 2. Compute the response times of these jobs in a dual priority system in which there is only one priority level in the middle priority band one priority level in the lowest priority band. How much improvement is gained over simply scheduling the aperiodic jobs in the background of rate monotonically scheduled periodic tasks?

d) Can the dual priority scheme be modified and used in a system where periodic tasks are scheduled according to the EDF algorithm? If no, briefly explain why; if yes, briefly describe the necessary modification.

Q.7.23: Suppose that the intervals between arrivals of sporadic jobs are known to be in the range (a,b). The execution time of each sporadic job is at most e (<= a) units.
Suppose relative deadlines of sporadic jobs are equal to a. You are asked to design a bandwidth preserving server that will be scheduled rate monotonically with other periodic tasks. Sporadic jobs waiting to be completed are executed on the first in first out basis in the time intervals where the periodic server is scheduled. Choose the period and utilization of this server so that all sporadic jobs will be completed by their deadlines and the utilization of the sporadic server is as small as possible.