Homework assignment #1: Static scheduling of periodic task systems (solutions)

Beware that there are multiple correct answers to most of the questions, since there are multiple correct schedules and multiple ways of giving proofs.

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/6 + 2/8 + 3/12 = 0.333... + 0.250 + 0.250 = 0.833...

2. What is the hyperperiod of this system? The definition of hyperperiod is in 3.3.1. (1 pt)

   LCM (2 x 3, 2 x 2 x 2, 2 x 2 x 4) = 2 x 2 x 2 x 3 = 24

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.
   

   The following solution uses a frame size of 4. The brackets above the line indicate the frames. The arcs indicate the task release times, which are also deadlines.

   
4. What is the worst-case response time of each task in your schedule above? (2 pt)

   TASK	WCRT	Note
   1	6	second period
   2	8	third period
   3	8	both periods

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)

   TASK	WC Jitter	Note
   1	4	(12-2)-6 = 4 : first two jobs
   2	6	(24-10)-8 = 6 : last two jobs
   3	0	same for all

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)

   We only have a small number of valid frame sizes, that are greater than or equal to all the execution times, divide the hyperperiod, and are less than or equal to all of the deadllines. They are: 3, 4, 6.

   The frame size of 6 will not work, because we cannot enforce the release time and deadline of the second period of task 2. (See the modular contraint in the textbook.)

   If we increase the execution time of task 2 to 3, we have a total utilization requirement 95.666... percent; that is, only one free time slot in the hyperperiod. By examining each of the two remaining potential frame sizes we can see that they all leave more than one free time slot. If we cannot preempt, there is no solution.

   With a frame size of 3, jobs of task 1 would leave one empty slot per frame. With 4 jobs in the hyperperiod, we would need four empty time slots.

   With a frame size of 4, jobs of tasks 2 and 3 would leave one empty slot per frame. With more than one job per hyperperiod, we would again need more than one empty time slot.

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)