Embedded System S/W Organization & Static SchedulingReading List for This LectureCourse Project Proposal Due Friday Oct 12Real-time Implementation in Software on a Single ProcessorExampleSingle Program ApproachAnother ExampleObservations on the Single Program ApproachObservations on the Single Program Approach (contd.)Handling Periodic Tasks with Multiple and Variable RatesHandling Event-driven TasksEvent-driven Tasks (contd.)Handling Simple Periodic ActionsSoftware TimersForeground/Background SystemsMulti-tasking ApproachTask CharacteristicsPreemptionHow to organize multiple tasks?How to schedule multiple tasks? (contd.)Performance Characteristics to Evaluate Scheduling AlgorithmsCyclic Executive, or Static Table-driven SchedulingMechanics of Cyclic ExecutivePriority-based Preemptive SchedulingSlide 25Some Priority-based Preemptive Scheduling ApproachesDispatching CostDynamic Planning-Based ApproachesDynamic Best Effort ApproachesOther Scheduling IssuesScheduling with Fault-tolerance ConstraintsScheduling with Resource ReclaimingImprecise ComputationImplementation in Real-time OSsComparison of Various RTOS Organizations: Cyclic ExecutiveComparison of Various RTOS Organizations: Monolithic KernelComparison of Various RTOS Organizations: MicrokernelStatic SchedulingSynchronous Data Flow GraphsUsed of SDFGs in Signal ProcessingWhat does “Synchronous” mean in a DFG?ExamplesFor the adventurous… SDFGs are:Buffering of Data Samples & Scheduling in SDFGsStatic Scheduling of SDFGsSDFG Compiler[Lee87]: Assumptions & GoalsConstructing a PASSTopology Matrix of SDFGTopology Matrix of SDFG (contd.)Buffer Size VectorMore on b(n)Relationship between b(n) and Handling “Delays”Slide 55Existence of PASSExistence of PASS (contd.)Slide 58Slide 59Slide 60Slide 61What does the theorem tell us?Slide 63Slide 64Slide 65Slide 66Sufficient Condition & Algorithm for finding PASSSufficient Condition & Algorithm for finding PASS (contd.)Slide 69Slide 70Slide 71Slide 72Slide 73What does Theorem 3 mean practically?Examples: SDFGs with Consistent Sample Rates but no Admissible SchedulesSelecting qSelecting q (contd.)Slide 78Slide 79Slide 80Slide 81Slide 82Slide 83Practically Speaking...Simple Algorithm to Find PASSWhich PASS?What about PAPS?Slide 88Scheduling on Two Processors“Unfolding” Once and Scheduling on Two ProcessorsLimitations of the SDFG (Static Scheduling) ModelMani SrivastavaUCLA - EE DepartmentRoom: 7702-B Boelter HallEmail: [email protected]: 310-267-2098WWW: http://www.ee.ucla.edu/~mbsCopyright 2001  Mani SrivastavaEmbedded System S/W Organization & Static SchedulingEE202A (Fall 2001): Lecture #32Copyright 2001  Mani SrivastavaReading List for This LectureRequired[Melkonian00] Melkonian, Michael. Get by without an RTOS. Embedded Systems Programming, September 2000.http://www.embedded.com/2000/0009/0009feat4.htm[Lee87] Lee, E.A.; Messerschmitt, D.G. Static scheduling of synchronous data flow programs for digital signal processing. IEEE Trans. on Computers, vol.C-36, (no.1), Jan. 1987. p.24-35.Others[Bhattacharyya99] Bhattacharyya, S.S.; Murthy, P.K.; Lee, E.A. Synthesis of embedded software from synchronous dataflow specifications. Journal of VLSI Signal Processing Systems for Signal, Image, and Video Technology, vol.21, (no.2), Kluwer Academic Publishers, June 1999. p.151-66.http://ptolemy.eecs.berkeley.edu/publications/papers/99/synthesis/3Copyright 2001  Mani SrivastavaCourse Project Proposal Due Friday Oct 12One page proposal describing the proposed project, and listing reference materialtalk to me for suggestionsIndividually or groups of twoProject may cover any topic of interest in embedded and real-time systemsneed not be on a topic covered in lecturesties with your research are acceptableA conference-style report and a project presentation on your results will be due at the end of the quarterSubmit as proj1.zip or proj1.tgz4Copyright 2001  Mani SrivastavaReal-time Implementation in Software on a Single ProcessorTypical implementation approachesSynchronous–single programAsynchronous–foreground/background system–multi-tasking5Copyright 2001  Mani SrivastavaExampleA process controller with following modulesa clock tick comes every 20 ms when a clock module must runa control module must run every 40 msthree modules with soft constraints–operator display update–operator input–management information logs6Copyright 2001  Mani SrivastavaSingle Program Approachwhile (1) {wait for clock;do clock module;if (time for control) do control;else if (time for display update) do display;else if (time for operator input) do operator input;else if (time for mgmnt. request) do mgmnt. output;}Must have t1 + max(t2, t3, t4, t5)  20 msmay require splitting tasks… gets complex!7Copyright 2001  Mani SrivastavaAnother Exampleint main(void) {Init_All();for (;;) {IO_Scan();IO_ProcessOutputs();KBD_Scan();PRN_Print();LCD_Update();RS232_Receive();RS232_Send();TMR_Process();}// should never ever get here// can put some error handling here, just in casereturn (0); // will keep most compilers happy}8Copyright 2001  Mani SrivastavaObservations on the Single Program ApproachEach function called in the infinite loop represents an independent task Each of these tasks must return in a reasonable time, no matter what thread of code is being executed We have no idea at what frequency our main loop runs.In fact, the frequency is not constant and can significantly change with the changes in system status (as we are printing a long document or displaying a large bitmap, for example)Mix of periodic and event-driven tasksMost tasks are event drivene.g. IO_ProcessOutputs is an event-driven taskdedicated input event queue associated with them•e.g. IO_ProcessOutputs receives events from IO_Scan, RS232_Receive, and KBD_Scan when an output needs to be turned onOthers are periodicNo trigger event, but may have different periods, and may need to change their period over time9Copyright 2001  Mani SrivastavaObservations on the Single Program Approach (contd.)Need some simple means of inter-task communicationse.g. may want to stop scanning the inputs after a particular keypad entry and restart the scanning after another entryrequire a call from a keypad scanner to stop the I/O scanner taske.g. may also want to slow down the execution of some tasks depending on the