COSC6384 Real-Time Systems
Assignment 1 (Fall 2005)
Question1.
Does a random scheduler obey the Queue discipline?
Does a random scheduler obey the Stack discipline?
Justify your answer with an example for each of them.
Question2.
Suppose a task consists of n subtasks, Ji each of which has computation time Ci, i=1,...,n. This task requests service at time T and has absolute deadline D. Summarize a formula to compute the latest deadline for completing each subtask such that the deadline of the entire task can be satisfied.
Question3.
Determine whether you can feasibly schedule the following two task setsusing the rate monotonic algorithm. If yes show an RM schedule else check whether it is EDF schedulable and give an EDF schedule if possible. All tasks arrive at time 0.
(a).
TASKPERIODCOMPUTATION TIME
A508
B203
C3515
D102
(b).
TASKPERIODCOMPUTATION TIME
A101
B61
C352
D21
E152
Question4.
Given three preemptive periodic tasks, all read at time 0. Is this task set RM (rate-monotonic)-schedulable? Justify your answer. If yes, show the entire schedule within LCM (periods). If not, show the schedule for the schedulable tasks for the time interval (0, LCM (periods of schedulable tasks))
TASKPERIODCOMPUTATION TIME
A40100
B100350
C40150
If the periods of the tasks in a task set are all multiples of a base unit, let's say 2, is the static priority scheduler as good as the earliest deadline scheduler for this type of task sets? Give a proof or show a counter example.
Question5.
Construct a set of periodic tasks (showing start times, computation times, and periods) which can be scheduled by the EDF algorithm but not by the RM algorithm.
Question6.
Construct a task set that can be scheduled by the RM, EDF and LLF algorithms.
Question7.
Given a task set which is rate monotonic schedulable,will the rate monotonic and earliest deadline first schedule be the same or different? Adjust your answer with examples.
Question8.
Give an LLF schedule for the following task set.
TASKPERIODCOMPUTATION TIME
A242
B363
C52
D142
E41
Question9.
Explain instances where the static and dynamic scheduler would be equivalent and when they would differ.Which is more suitable for an operating system? Justify your answer in detail.
Question10.
Prove that the utilization of any set of tasks must be less than or equal to 1 for a feasible schedule (meeting all deadlines) to exist on a uniprocessor.
Question11.
We have assumed in lectures that context-switching due to preemption incurs no overhead. Now suppose context-switching (from one task to another) requires 'x' time units. Consider a system with n tasks with computation times C1,C2,...,Cn and periods P1, P2,...,Pn (which are equal to their deadlines and PiPi+1). Derive the maximum value of 'x' for which this task set is EDF-schedulable. Show calculations steps.
Question12.
Consider 3 periodic processes A, B, C. The respective periods (=deadlines) and computation times are (100, 30), (5, 1), and (25, 5), all in milliseconds. Assume that A is the most important process, followed by B, then C.
(a).Illustrate the behavior of a priority scheduler if priority is based on importance.
(b).What is the processor utilization?
(c).How should the processes be scheduled so that all deadlines are met?
Question13.
A periodic process must be executed once in every period of the process. A system is schedulable if all the processes can be scheduled as defined. Suppose our system has five processes with periods 30, 50, 75, 200and 300 milliseconds each. These five processes require 5, 10, 15, 35 and 'x' msec of CPU time, respectively. What is the largest value of 'x' for which the system is schedulable? Show calculations and the schedule.
Question14.
Determine whether there is a feasible schedule for the following set of periodic processes. If yes, show the schedule and the steps used to derive it.
T1: c1 = 1, d1 = p1 = 12
T2: c21 = 1, c22 = 2, d2 = 5, p2 = 6
T3: c31 = 2, c32 = 3, d3 = 12, p3 = 12
T2 must rendezvous with T3 after the first scheduling block.
T3 must rendezvous with T2 after the first and second scheduling block.
1