Homework assignment #1: Static scheduling of periodic task systems

Consider the following set of implicit-deadline periodic tasks.

1. What is the total processor utilization of this system? The definition of utilization is in 3.3.1. (1 pt)
2. What is the hyperperiod of this system? The definition of hyperperiod is in 3.3.1. (1 pt)
3. Construct a frame-based static cyclic schedule for these tasks, as described in 5.3 of the textbook. (5 pt) Take care that it satisfies all of the following constraints:
   1. the execution of each job fits within a single frame
   2. the frame of a job begins no earlier than the job's release time
   3. the frame of a job ends no later than the job's deadline
   Present your schedule in the form of a Gannt chart, similar to the figures in 5.3.
4. What is the worst-case response time of each task in your schedule above? (2 pt)
5. Suppose we define the a measure of completion-time jitter of a task in this context to be the maximum of the absolute value of the difference between the task period and the actual separation in time between the completion times of each pair of successive jobs of the task. For example, if a job of a given task is released at time 3 and completes at time 10, and the next job of that task is released at time 12 and completes at time 13, the separation in completion times is 13-10 = 3, the period is 9, the difference between 9 and 3 is -6, and so the maximum completion time jitter is at least 6. Compute this measure of completion time jitter for each task in the schedule you produced above. Don't forget the wrap-around case.(2 pt)
6. Suppose the execution time task 2 is increased from 2 to 3. Construct a valid cyclic schedule for the new task system, or argue that it is not possible. (5 pt)
7. The problem above can be solved easily if we relax the requirement that the schedule have equal-sized frames. Construct a valid non-preemptive cyclic schedule for the task system of the above question that can be implemented using an arbitrary interval timer, rather than a periodic timer. (5 pt)
8. Challenge: Prove or disprove that it is an NP-hard problem to determine whether an implicit-deadline periodic task system can be scheduled to meet all deadlines using a static clock-driven schedule that satisfies the constraints above. Do this on your own. That is, you may derive your own reduction to a well-known NP-hard problem, or find a published proof of NP-hardness for this problem, but you may not make use of assistance from another person, share answers, or share references. (10 pt)