CS244-Introduction to Embedded Systems and Ubiquitous ComputingCS244 – Lecture 4Embedded Systems Design FlowReuse of standard software componentsSoftware ComponentsWorst Case Execution TimeAverage Execution TimeReal-Time SchedulingClassification of Scheduling AlgorithmsHard and soft deadlinesPeriodic and aperiodic tasksPreemptive and Non-preemptive SchedulingStatic and dynamic schedulingTime-Triggered SystemsCentralized and Distributed SchedulingSchedulabilitySimple TasksCost FunctionsBasic Parameters in Real Time Sched.Uniprocessor with Equal Arrival TimesEarliest Deadline First (EDF)Slide 22Scheduling with no Precedence ConstraintsLeast laxity, Least Slack Time FirstLL/LSF PropertiesPeriodic SchedulingPeriodic schedulingAccumulated UtilizationRate Monotonic (RM) SchedulingSlide 30Slide 31Example: RM-generated scheduleCase of failing RM schedulingProperties of RM SchedulingEDFComparison EDF/RMSEDF: PropertiesScheduling without PreemptionScheduling with Precedence ConstraintsSynchronous Arrival TimesAsynchronous Arrival TimesDependent TasksSporadic TasksSummaryCS244-Introduction to Embedded Systems and Ubiquitous ComputingInstructor: Eli BozorgzadehComputer Science DepartmentUC IrvineWinter 2010Winter 2010- CS 2442CS244 – Lecture 4Real Time SchedulingWinter 2010- CS 2443Embedded Systems Design Flow ConceptConceptSpecificationSpecificationHW/SWHW/SWPartitioningPartitioningHardware ComponentsHardware ComponentsSoftware ComponentsSoftware ComponentsEstimation -Estimation -ExplorationExplorationHardwareHardwareSoftwareSoftwareDesignDesign(Synthesis, Layout, …)(Synthesis, Layout, …)DesignDesign(Compilation, …)(Compilation, …)Validation and Evaluation (area, power, performance, …)Validation and Evaluation (area, power, performance, …)Winter 2010- CS 2444Reuse of standard software componentsKnowledge from previous designs to be made available in the form of intellectual property (IP, for SW & HW). Operating systems Middleware Real-time data bases Standard software (MPEG-x, GSM-kernel, …)Includes standard approaches for scheduling (requires knowledge about execution times).Winter 2010- CS 2445Software ComponentsPrediction of execution timeScheduling in real-time systems Classification of scheduling algorithms Aperiodic scheduling Periodic schedulingEmbedded operating systems Real-time OSMiddlewareWinter 2010- CS 2446Worst Case Execution TimeDef.: The worst case execution time (WCET) is an upper bound on the execution times of tasks. Computing such a bound is undecidable Possible for programs without recursion and finite loopsPipeline hazards, interrupts, caches  serious overestimatesApproaches:  for hardware: typically requires hardware synthesis for software: requires availability of machine programs; complex analysisWinter 2010- CS 2447Average Execution TimeEstimated cost and performance values Difficult to generate sufficiently precise estimates;Balance between run-time and precisionAccurate cost and performance values Can be done with normal tools (such as compilers). As precise as the input data is.Winter 2010- CS 2448Real-Time Scheduling Assume that we have a task graph G=(V,E). A schedule of G is a mapping, V  T, of a set of tasks V to start times from domain T. Schedules have to respect a set of constraints, such as resource, dependency, and deadlines. Scheduling is the process of finding such a mapping. During the design of embedded systems, scheduling has to be performed several times early rough scheduling as well as late precise schedulingWinter 2010- CS 2449Classification of Scheduling AlgorithmsWinter 2010- CS 24410Hard and soft deadlines Def.: A time-constraint (deadline) is called hard if not meeting that constraint could result in a catastrophe [Kopetz, 1997]. All other time constraints are called soft.  We will focus on hard deadlines.Winter 2010- CS 24411Periodic and aperiodic tasks Def.: Tasks which must be executed once every p units of time are called periodic tasks. p is called their period. Each execution of a periodic task is called a job. All other tasks are called aperiodic. Def.: Aperiodic tasks requesting the processor at unpredictable times are called sporadic, if there is a minimum separation between the times at which they request the processor.Winter 2010- CS 24412Preemptive and Non-preemptive SchedulingPreemptive and non-preemptive scheduling: Non-preemptive schedulers are based on the assumption that tasks are executed until they are done. As a result the response time for external events may be quite long if some tasks have a large execution time.Preemptive schedulers have to be used if some tasks have long execution times or if the response time for external events is required to be short.Winter 2010- CS 24413Static and dynamic scheduling Dynamic scheduling: Processor allocation decisions (scheduling) done at run-time. Static scheduling: Processor allocation decisions (scheduling) done at design-time.Dispatcher allocates processor when interrupted by a timer. The timer is controlled by a table generated at design time.Winter 2010- CS 24414Time-Triggered Systems Entirely time-triggered system the temporal control structure of all tasks is established a priori by off-line support-tools. Temporal control structure is encoded in a Task-Descriptor List (TDL) that contains the cyclic schedule for all activities of the node. This schedule considers the required precedence and mutual exclusion relationships among the tasks such that an explicit coordination of the tasks by the operating system at run time is not necessary. .. The dispatcher is activated by the synchronized clock tick. It looks at the TDL, and then performs the action that has been planned for this instant. [Kopetz]The only practical means of providing predictability. It can be easily checked if timing constraints are met. Response to sporadic events may be poor.Winter 2010- CS 24415Centralized and Distributed Scheduling Centralized and distributed scheduling Multiprocessor scheduling either locally on one or distributed on several processors Mono- and multi-processor schedulingSimple scheduling algorithms handle single processors, more complex algorithms handle multiple processors. Online- and offline scheduling:Online scheduling is done at run-time based on the information about the tasks arrived so