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 b 7 2 6 1 a 1 1 6 7 d 5 5 1 3 5 6 7 c e 2 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 3 5 4 Task 1 1 4 2 Task 2 3 20 20 Task 3 3 1 2 Task 1 Task 2 Ci 3 3 Pi 4 12 Di 4 12 Ci 6 5 3 Pi 15 20 10 Di 12 20 5 3 1 3 Task 1 Task 2 Task 3 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 1 9 1 Task 1 5 36 15 Task 2 5 18 18 Task 3 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 Task 1 Task 2 Task 3 Ci 1 1 2 Pi 3 2 9 3 3 2 Task 1 Task 2 Task 3 Ci 4 4 4 Pi 15 20 10
View Full Document
Unlocking...