COSC6384 Real-Time Systems

COSC6384 Real-Time Systems

Assignment 1 (Fall 2010)

Question1.

Explain the difference between preemptive and non-preemptive scheduling. Discuss the difference between priority-driven and time-driven, static and dynamic, on-line and off-line scheduling algorithms.

Question2.

In real-time systems, one of the most dangerous phenomena caused by a transient overload is referred to the situation in which the arrival of a new task causes all previously guaranteed tasks to miss their deadlines. Assume all SINGLE instance tasks are independent with their own (a, d, c), in which a is the arrival time, d is the deadline and c is the computation time. Provide an example: in a previously feasible set of three single instance tasks, all tasks are missing the deadline caused by the arrival of a new task Jnew. You can use any scheduling algorithm.

Question3.

(a) Give two different explanations of why the periodic tasks (Period, Computation time), (2, 1), (4, 1) and (8, 2) are schedulable by the rate-monotonic algorithm.

(b) Give two different explanations of why the periodic tasks (Period, Computation time), (3, 1), (5, 1) and (11, 2) are schedulable by the rate-monotonic algorithm.

(c) Suppose that we add one more task into the task set in (b) where the new task’s utilization is 0.1. Is the new task set schedulable by the rate-monotonic algorithm? Be sure to explain your answer.

Question4.

A system consists of three periodic tasks: (3, 1), (5, 2) and (8, 3).

(a) What is the total utilization?

(b) Construct an EDF schedule of this system in the interval (0, 32). Label any missed deadlines.

Question5.

Consider the following four algorithms, the rate monotonic (RM), the deadline monotonic (DM), the earliest deadline first (EDF) and the least laxity first (LLF). Consider a task set composed of the following three periodic tasks all arriving at time 0:

C D T

1 3 3

1 4 4

2 3 8

Where C is the computation time, D is the RELATIVE deadline, and T is the period.

Build the schedule of the task set under the four scheduling algorithms RM, DM, EDF, and LLF.

Question6.

We call the density of a task T, C/min(D, P), where C is the computation time, D is the relative deadline, and P is the period.

Prove: A system of independent, preemptable tasks can be feasibly scheduled on one processor if its density is equal to or less than 1.

Question7.

Consider a set of n independent tasks. All tasks arrive at t = 0. Each task Ti is characterized by its computation time Ci and deadline Di.

Prove that EDF is optimal for both preemptive AND non-preemptive cases.

Question8

Prove the RM algorithm is an optimal static-priority algorithm for uniprocessors with the same conditions in Question 7.

Question9.

Consider a two-task system where each preemption has an overload of x. Given C1, C2, P1, P2, obtain the maximum value of x for which the task set is RM-schedulable.

Question10.

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: c11 = 1, c12 = 3, c13 = 2, d1 = 22, p1 = 24

T2: c21 = 2, c22 = 3, d2 = 8, p2 = 8

T3: c3 = 2, d3 = p3 = 24

T1 must rendezvous with T2 after the first, second, and third scheduling blocks.

T2 must rendezvous with T1 after the first scheduling block.