• CMPE 117 Spring 2008
• Scheduling homework 2

Scheduling Homework 2

Due Monday April 27 in class

Problem 1

Consider three periodic processes J1 J2 J3 with the computation times and periods given in the following table:

• Are J1 J2 J3 schedulable by the Rate Monotonic algorithm?
• Assume now that the processes J1 J2 J3 have periodic deadlines D1 = 3, D2 = 8, and D3 = 9, respectively. Are the processes schedulable by the Deadline Monotonic algorithm? Are the processes schedulable at all? Explain.

Problem 2

Consider two periodic processes J1 J2 with computation times and periods given as follows:

• Are the above periodic processes schedulable by EDF?
• Consider now the cases where the processes have periodic deadlines D1 = 3 and D2 = 5. Are the processes schedulable via EDF?

Problem 3

Consider four periodic processes J1 J2 J3 J4 with periods, computation times, and periodic deadlines as follows:

Assume also that J2 and J3 can start only after J1 terminates, and that J4 can start after both J2, J3 terminate.

• Are the processes schedulable? If so, give a schedule and explain how you obtained it. If not, explain why.

Problem 4

Give a scheduling problem where the following algorithms behave in different ways:

1. Normal resource management
2. Priority inheritance
3. Priority ceiling

To specify a scheduling problem, you need to provide the following:

• A set of processes, each with a base priority.
• The length of time the processes spend in, and out, of critical sections.
• When the processes become available for execution.
• Which mutexes guard the critical regions of each process.

For instance, you can say something similar to the following:

• Process 1 has a first part of 5 time units, followed by 3 time units of critical section protected by lock A, followed by 2 more time units. It can start executing at time 23.

Draw schedules for each of the three algorithms demonstrating the different executions that result.