This is a closed-book examination. You are not allowed to use any notes or other references during the exam. You will have 50 minutes to answer all the questions. Answer on the blank paper I provide you. Answer all the questions. In scoring, each question will be given the weights indicated.

Comments and solutions to questions are shown in green font. This exam was very similar to the sample exam, so reference is made to that for solutions to some questions. Likewise, for questions that could be answered directly from the textbook or notes you should see the textbook and notes for the answers.

Several questions refer to the task set described by the following table:

1. (15 pt essay) Suppose you have a procedure that you would like to execute periodically, as a real-time periodic task. You need to find the worst-case execution time of this procedure, in order to determine whether it can be scheduled feasibly in a system with other real-time tasks. How would you find the worst-case execution time? Describe the methods you know, with their pro's and con's.

   (Limit your answer to a maximum of two sides of one sheet of paper.)

See the class notes and textbook.

2. (5 pt) What is the utilization of this task set?

1/3 + 3/10 + 1/3 ∼ 0.97

3. (10 pt) Draw a Gantt chart (i.e., timeline) showing the preemptive Earliest Deadline First (EDF) schedule. Assume all tasks are released together at time zero. Show the schedule up through time 30.



4. (5 pt) What advantage(s) does EDF scheduling have over Rate Monotone scheduling?

See the solutions to the 1998 Midterm exam.

5. (10 pt) Draw a Gantt chart (i.e., timeline) showing the preemptive Rate Monotonic (RM) schedule. Assume all tasks are released together at time zero. Show the schedule up through the end of the critical zone for task 3.



6. (5 pt) What advantage(s) does RM scheduling have over EDF scheduling?

See the solutions to the 1998 Midterm exam.

7. (5 pt) State the Critical Zone Theorem.

See the class notes, or textbook.

8. (5 pt) State the Utilization Bound Theorem for Rate Monotonic scheduling.

See the class notes, or textbook.

9. (5 pt) Apply the Utilization Bound (UB) test to this task set. Which tasks does it say are schedulable? (Use the values U(1) = 1, U(2) = 0.828, and U(3) = 0.779.)

2/6 = 1/3 < U(1) = 1, so τ₁ is feasible
2/6 + 3/10 = 1/3 + 0.3 ∼ 0.63333... < U(2) = 0.828, so τ₂ is feasible
U(3) < 2/6 + 3/10 + 5/15 ∼ 0.966666... < 1, so τ₃ might not be feasible

10. (5 pt) Apply the Response Time (RT) test to determine the schedulability of any tasks for which the UB test cannot determine schedulability.

The only task in question is task τ₃. For this we have:

W₀ = 2 + 3 + 5 = 10
W₁ = 2*2 + 3 + 5 = 12
W₂ = 2*2 + 3*2 + 5 = 15
W₃ = 2*3 + 3*2 + 5 = 17
W₄ = 2*3 + 3*2 + 5 = 17

The response time of task τ₃ is 17, which is beyond its deadline of 15, so this task is not schedulable. We did not have to complete the calculation to see this. Once we saw that it did not converge at or before 15, we could tell that the task would not complete within its deadline.

11. (5 pt) Choose execution times for the set of task periods used in the preceding two questions so as to minimize the utilization and still ``fully utilizes'' the processor in the sense that no task's execution time can be increased without causing an overflow. (Hint: Recall the reasoning behing the Liu & Layland utilization bound theorem, and note that the periods of these tasks do not differ by more than a ratio of 1/2. The task set you get should have total utilization U(3).)

This question was thrown out, because the periods given differ by more than a ratio of 1/2, contrary to the statement in the hint. However, for any set of periods there is an assignment of execution times that minimizes the utilization and still fully utilizes the processor. The difficulty is in determining what this execution time assignment is, outside of the case covered in the proof of the utlization bound theorem. In this case, I think the breakdown utilization may be minimized by the times given by the following table:

task	period	exec. time
1	6	0
2	10	5
3	15	5



Because the periods differ by more than a factor of 1/2, I don't think we can reach the value U(3). The total utilization in this example is 1/3 + 1/2 = 5/6 = 0.8333333..., which is very close to 2(2^1/2-1) = 0.82842712474... .

To see that giving τ₁ nonzero execution time would not reduce the breakdown utilization, consider the figure below.



The total utilization is 3/6 + 2/10 + 2/15 = 5/6 = 0.833333... .

12. (10 pt) Draw the Gantt chart for a static (cyclic executive) schedule, based on the concept of minor cycle and major cycle, for the task set in the table above. Clearly indicate which task(s), if any, need to be split up into subtasks. Indicate what is the major cycle length and what is the minor cycle length.



The major cycle length is LCM{6,10,15} = 30, and the minor cycle length is 3. We need to split task τ₃ into three sub-tasks, of execution times 1, 1, and 3.

13. (5 pt) What advantages(s) does static scheduling have over EDF and RM on-line scheduling?

See the class notes.

14. (5 pt) What disadvantages(s) does static scheduling have as compared to EDF and RM on-line scheduling?

See class notes.

15. (5 pt) Give an example showing that EDF scheduling is not optimal for a system with two processors.

This example was given in class. See the class notes on EDF scheduling.