CS244 Introduction to Embedded Systems and Ubiquitous Computing Instructor Eli Bozorgzadeh Computer Science Department UC Irvine Winter 2010 CS244 Lecture 4 Real Time Scheduling Winter 2010 CS 244 2 Embedded Systems Design Hardware Components Hardware Flow Concept Specification HW SW Partitioning Estimation Exploration gn i s De t u ayo L si s e nth y S De sig n C om pil a ti on Software Software Components Winter 2010 CS 244 Validation and Evaluation area power performance 3 Reuse 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 244 4 Software Components Prediction of execution time Scheduling in real time systems Embedded operating systems Classification of scheduling algorithms Aperiodic scheduling Periodic scheduling Real time OS Middleware Winter 2010 CS 244 5 Worst 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 analysis Winter 2010 CS 244 6 Average 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 244 7 Real 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 scheduling Winter 2010 CS 244 8 Classification of Scheduling Algorithms Winter 2010 CS 244 9 Hard 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 244 10 Periodic 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 244 11 Preemptive 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 244 12 Static 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 244 13 Time 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 244 14 Centralized and Distributed Scheduling Centralized and distributed scheduling Mono and multi processor scheduling Multiprocessor scheduling either locally on one or distributed on several processors 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 far Offline scheduling assumes prior knowledge about arrival times execution times and deadlines Winter 2010 CS 244 15 Schedulability A set of tasks is said to be schedulable under a given set of constraints if a schedule exists for that set of tasks and constraints Exact tests are NP hard in many situations Sufficient tests sufficient conditions for guaranteeing a schedule are checked Small probability of false negative Necessary tests checking necessary conditions Can be used to show that no schedule exists Always not possible to prove even if no schedule exists Winter 2010 CS 244 16 Simple Tasks Tasks without any interprocess communication are called simple tasks S tasks S tasks can be either ready or running API of an S task in a TT system Two OS Calls TERMINATE TASK and ERROR The TERMINATE TASK system call is executed whenever the task has reached its termination point In case of an error that cannot be handled within the application task the task terminates its operation with the ERROR system call Kopetz 1997 Winter 2010 CS 244 17 Cost Functions Cost function Different algorithms aim at minimizing different functions Def Maximum lateness is defined as the difference between the completion time and the deadline maximized over all tasks Maximum lateness is negative if all tasks complete before their deadline Winter 2010 CS 244 18 Basic Parameters in Real arrival time a time when a task becomes ready for execution Time Sched computation time C time necessary for completion of a task i i absolute deadline di time before which