First Midterm Examination COP 4613 - Real Time Systems Fall 2008
your name: ___________________________________________________________

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. Except where I have provided grids for Gantt charts, you should answer on the blank paper I provide you. In scoring, each question will be given the weight indicated. No partial credit will be given for a wrong answer unless you explain how you obtained it and I can see from the explanation where you went astray.

Several questions refer to the following task set.
taskperiodexec. time
141
262
3104
Answer all of questions 1-14.

  1. (5 pt) What is the utilization of the task set above?

  2. (5 pt) What is the hyper-period of the task set above?

  3. (10 pt) Fill in the Gantt below showing the preemptive rate monotonic schedule, just from the critical instant to the end of the critical zone for task 3. Label the graph to show the critical instant, the critical zone and the completion time of task 3.



  4. (10 pt) Define what it means for a scheduling algorithm to be completion-time predictable.

  5. (5 pt) Explain why completion-time predictability is important.

  6. (5 pt) Give an example of a scheduling algorithm that is completion-time predictable for independent periodic task sets on a single processor.

  7. (10 pt) State the Critical Zone Theorem. Be sure to mention the class of scheduling algorithms and task sets to which it applies.

  8. (10 pt) Give the recursive response-time equation for fixed task-priority scheduling.

  9. (10 pt) Apply the respone-time equation to compute the worst-case response time for task 3.

  10. (10 pt) State the Utilization Bound Theorem for rate monotonic scheduling.

  11. (5 pt) What does the Utilization Bound Theorem tell us about the schedulability of the task set above? (Hint: U(3) ~= 0.779.)

  12. (5 pt) What does it mean for the periods of a task set to be harmonic?

  13. (5 pt) What is the rate monotonic utilization bound for period task sets with harmonic periods?

  14. (5 pt) What advantages does preemptive scheduling have over non-preemptive scheduling?

The following questions are optional. By answering them you can earn points to make up for any missed questions above.

  1. (5 pt bonus) What advantages does non-preemptive scheduling have over preemptive scheduling?

  2. (5 pt bonus) Draw a Gantt chart showing the non-preemptive EDF schedule for the task set above, starting with all tasks intially released at time zero and continuing through time 20. Indicate any missed deadlines.