New version page

Berkeley EE 249 - Scheduling for Embedded Real-Time Systems

Upgrade to remove ads
Upgrade to remove ads
Unformatted text preview:

Scheduling for Embedded Real-Time SystemsOverviewReal-Time SystemsScheduling problem in Real-Time SystemsSlide 5Static Scheduling PoliciesStatic Scheduling Policies (contd.)Dynamic Scheduling PoliciesDynamic Scheduling Policies (contd.)Schedulability AnalysisWCRT analysis for realistic real-time embedded systemsSynchronous SchedulingSynchronous Scheduling (contd.)Slide 14Dataflow SystemsSDFResearch Issues in SDF schedulingConclusionsScheduling for Embedded Real-Time SystemsAmit Mahajan and HaiboOverview •Real-Time Systems•Scheduling problem in Real-Time Systems•Control Dominated Systems•Dataflow Systems•ConclusionsReal-Time Systems•Are composed of several distinct cooperating tasks•Are usually non-terminating•React faster than the rate of the environment i.e. the composing tasks have tight timing constraintsScheduling problem in Real-Time SystemsGiven –A set processing units with “known” processing capabilities–A set of tasks with “known” characteristics and constraints on the completion time Derive an order of execution of these tasksOverview •Real-Time Systems•Scheduling problem in Real-Time Systems•Control Dominated Systems•Dataflow Systems•ConclusionsStatic Scheduling Policies•Tasks execute in a fixed order determined offline•Suited best to the cases where the time when the tasks become enabled are known well in advance•Easy to debug but usually give low processor usageStatic Scheduling Policies (contd.)•Round Robin–Tasks checked for readiness in a predetermined order and executed immediately if they are ready–Easy to give bounds on the time between a request for an execution and the corresponding execution•Cyclic Scheduling–Like round robin except that tasks may appear more than once in one cycle–Used in dataflow systemsDynamic Scheduling Policies•Order of task execution decided at runtime•Usually based on some sort of priority of tasks•May or may not be pre-emptive •Suited for systems with irregular task activations•High processor usage but difficult to debugDynamic Scheduling Policies (contd.)•Work by Liu and Layland. Under strict assumptions –RMS •Static priorities•Priority of a task is proportional to its rate–EDF •Dynamic priorities•Priority of a task is inversely proportional to the time remaining to its deadline •Under a set of relaxed conditions, Audsley et al. proposed an optimal priority assignment algorithm for static priority schedulingSchedulability Analysis•To determine if a set of tasks meets its timing constraints•Common approach – worst case response time (WCRT) analysis–Once WCRT is computed, checking whether a task meets its deadline is trivial in many cases•With Liu and Layland assumptions of preemptive static priority scheduling and independent periodic tasks with fixed runtimes, WCRT analysis is easyWCRT analysis for realistic real-time embedded systems•Real-time embedded systems frequently flout the Liu layland assumptions–state- dependent run-times, dependency between tasks and non-periodic events in the environment•Balarin and Sangiovanni proposed a conservative extension to WCRT analysis for systems in which–Scheduling is either preemptive or nonpreemptive static priority –The environment only needs to respect the timing between successive occurrences of eventsFOR MOST SYSTEMS WITH STATE AND INPUT DEPENDENT RUNTIMES, TRACTABLE WCRT ANALYSIS IS A MYSTERY!Synchronous Scheduling•E.g Esterel•Synchronous assumption–Given a set of communicating tasks, each represented by a FSM, the computation of the output as well as the communication among the FSMs takes place in zero time •The synchronicity hypothesis reduces the set of FSMs to a single product machine•For synchronous systems, the structure of the product machine is equivalent to the static scheduling of the component FSMsSynchronous Scheduling (contd.)•Advantages–Deterministic response–Ease of debugging and verification•Problems–May lead to inefficient execution time as compared to task-based scheduling–Some tasks in a system may not be representable as FSM –Undelayed feedback loops are a cause of great troubleOverview •Real-Time Systems•Scheduling problem in Real-Time Systems•Control Dominated Systems•Dataflow Systems•ConclusionsDataflow Systems•Dataflow graphs used for scheduling purposes in DSP systems•Explicit representation of interaction between tasks•More emphasis on the throughput of the system•Two types of dataflow models–SDF  static compile time scheduling possible–DDF or control DFmore powerful than SDF but require some dynamic schedulingMost DSP algorithms don’t require much decision making – SDF is a good enough modelSDF•Used in many block-diagram based rapid prototyping and code generation for programmable DSPs•For uniprocessor scheduling–Code generator steps through the schedule and generates a sequence of actor invocations–In-line code used instead of sub-routine calls–Loops used to prevent explosion in code size due to multiple appearances of an actor in a scheduleResearch Issues in SDF scheduling•Minimize code and buffer size used for actors. Approaches are –Minimizing for one of the criterions. Among the existing solutions, choosing the solution that minimizes the second criterion–Exploring solutions that optimize based on a tradeoff between the two constraints i.e. avoiding the extremes•Minimizing activation schedulesConclusions•Dataflow systems–Regularity of inputs and control lends itself well to static scheduling–Good techniques exist scheduling on one or several processors with tradeoff between code-size, buffer size, execution time etc•Control-dominated systems–Efficient scheduling schemes known for a very small class of systems–Lack of a good model to capture inter-task dependencies–Lack of good techniques to determine the WCRT on complex processors without making unrealistic


View Full Document
Download Scheduling for Embedded Real-Time Systems
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Scheduling for Embedded Real-Time Systems and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Scheduling for Embedded Real-Time Systems 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?