Please work on this homework independently. Homework is due September 10th in class. Please note that the homework itself is a way to learn more about real-time systems. In other words, while some problems are from the slides, others are designed to help you understand and discover additional properties not explicitly mentioned in class. What's the point? The point is that when you discover them yourself, you are much less likely to forget them than if someone simply mentions them to you. With that in mind, I hope you enjoy the voyage of discovery.

1. Prove that EDF is the optimal scheduling policy for independent preemptible periodic tasks with relative deadlines equal to periods.

2. Present a system of three periodic tasks that has the lowest critically schedulable utilization under rate-monotonic scheduling.

3. In a system of N independent preemptible tasks, scheduled in a rate monotonic fashion, where each task Ti has computation time Ci and period Pi equal to its relative deadline, what is the maximum number of times that a given task can be preempted?

4. Consider a system of two periodic tasks, T1 and T2. Let the period of T2 be n times that of T1, where n is an integer. Assume that the first invocation of each task arrive together. Find an example, if one exists, of a period and execution time for each of T1 and T2, such that EDF finds a feasible schedule for the task set (i.e., one that meets all deadlines) whereas rate monotonic does not. If no example can be found that satisfies the above, please prove that it is impossible.

5. Let a context switch time be the extra time needed for the CPU to switch from one task to another (or between an idle and a busy state). Show mathematically, how you can account for context switch times in utilization-bound-based schedulability analysis.