Homework Assignment 3

• 4% of your final grade
• Individual work, no collaboration is allowed!
• Check out our Academic Integrity policy here.  If two or more students' lab assignments are very similar, all will receive a minimum penalty of a zero on the given lab assignment. 
• HW3 is due on 11/4 before class. Email your work to the TA.

Question 1: Why using EDF incurs higher overhead? List all the possible factors that could incur such overhead. (Hint: there could be multiple factors that account for such overhead).

Question 2: For the following sets of tasks, determine whether they are schedulable with the 1) RMS and 2) EDF scheduling algorithms. If yes, explain why. If not, explain what modifications can be made so that they can be schedulable.

1) T1 = (8, 15), T2 = (12, 20)

2) T1 = (8, 16), T2 = (10, 20)

3) T1 = (8, 20), T2 = (10, 25)

Question 3: In class, we demonstrated priority inversion between a high-priority task (T1) and a low-priority task (T4), when they access the same shared resource. Now, please further extend the situation, and consider the case with three tasks T1, T3 and T4 (priorities: T1>T3>T4). T1 and T4 access a shared resource R1, and T3 and T4 access another shared resouce R2. Demonstrate the priority inversion in this case. (Hint: there may be more than one priority inversion).

Question 4: Consider the following set of tasks being deployed over two processors (P1 and P2): T1 = (3, 6), T2 = (3,8)->(3,8), T3 = (4, 10). If we use the greedy algorithm for scheduling, will any of the tasks miss their dealine? If not, explain why. If so, could adding a release guard solve the problem?