Fall 2001

EE249 Design of Embedded Systems

Homework 3

Prof. Alberto Sangiovanni-Vincentelli

TA: Claudio Pinello

Suggestions from: various sources

Due in class, Nov 27th, Tuesday, 10% off for up to 1 week late

Problem 1 (20 points)

Consider the following Synchronous Dataflow Graph:

Problem 2 (20 points)

Problem 3 (20 points)

We shall consider a set of periodically activated tasks. Each task is characterized by a triple of parameters:

  • Ci : computation time,
  • Pi: activation period,
  • Di: relative deadline.

Every task is assumed to be activated at time k Pi, k=0, 1, …..

Upon each activation a task executes a job requiring Ci CPU time units and it has to terminate before kPi + Di.

All tasks share the same CPU and, hence, a scheduling algorithm has to be applied. A scheduling algorithm is called preemptive if it permits to interrupt the execution of a task before it terminates a job and non-preemptive otherwise.

Preemptive real-time scheduling algorithms make scheduling decisions according to priorities assigned to tasks. Priority can be assigned statically or changed dynamically (e.g. upon the arrival of a new job request for a task).

The result of the application of a scheduling algorithm is a function assigning each time slot of the CPU to a task. Such a function is defined schedule.

A schedule is said feasible if each job terminates before its assigned deadline. A set of tasks for which a feasible schedule exists under some algorithm is said schedulable.

Part 1.

For the following task sets verify if a feasible schedule exists based on
a) non preemptive algorithms,
b) preemptive algorithms with static priorities,
c) preemptive algorithms with dynamic priorities.

3.1.1)

Ci / Pi / Di
Task 1 / 3 / 5 / 4
Task 2 / 1 / 4 / 2
Task 3 / 3 / 20 / 20
Ci / Pi / Di
Task 1 / 3 / 4 / 4
Task 2 / 3 / 12 / 12

3.1.2)

3.1.3)

Ci / Pi / Di
Task 1 / 6 / 15 / 12
Task 2 / 5 / 20 / 20
Task 3 / 3 / 10 / 5

Part 2.

A large part of the results described in the literature deals with independent tasks. Let’s consider here a different case for the following task set.

3.2.1)

Ci / Pi / Di
Task 1 / 1 / 9 / 1
Task 2 / 5 / 36 / 15
Task 3 / 5 / 18 / 18

Let tasks 1 and 3 share some common resource, in example a same memory buffer to interact with special peripherals. Both tasks lock the resource at the beginning of a job and release it at the end of it. When one of the two is using the resource, the other cannot start execution until the resource is released (in the example above the mutual exclusion lock prevents cross corruption of data in the buffer). Task 2 is independent of the other two, so in principle it can be preempted by and can preempt any of them.

Verify if a feasible schedule exists for 3.2.1) using

a)Rate Monotonic scheduling

b)Earliest Deadline First scheduling

Part 3.

For the following task sets deadlines are assumed to be equal to periods. Verify if the following task sets are schedulable using Rate Monotonic and EDF using conditions and algorithms shown in class and validate results constructing the schedule.

3.3.1)

Ci / Pi
Task 1 / 1 / 3
Task 2 / 1 / 2
Task 3 / 2 / 9

3.3.2)

Ci / Pi
Task 1 / 4 / 15
Task 2 / 4 / 20
Task 3 / 4 / 10