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.

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.)

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

3. (10 pt) Draw a Gannt 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?

5. (10 pt) Draw a Gannt 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?

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

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

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.)

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

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).)

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.

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

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

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