Transcription
Machine DesignMachine DesignAgenda (ES1) software development so farIntroduction to Advanced EmbeddedSystems (The Course) The limitations of your current examples. Challenges: concurrency, real-time & resourcesharing. Advanced ES software Embedded & Mechatronics Systems Concurrency & multitasking Real-Time Systems Partial solution: Operating systems Final solution: Real-time operatingsystems Resource sharing (optional) ConclusionMechatronics Lab1Machine DesignMechatronics Lab2Machine DesignYour (ES1) programs so far (ES1) software development so farYou were asked to do examples such as: The EVK1100 is equipped with three pushbuttons and 6 LEDs. Turn on one LED when apush button is pressed Read the value of the photoresistor and turnson all LEDs when there is low light shining onthe photoresistor (covered by the hand), andturns off all LEDs when it’s lighter. Configure a PWM channel, for a givenfrequency and duty cycle. Every 5 seconds,read the PWM value and print it out to thedisplay.Mechatronics Lab3Machine DesignMechatronics Lab4Machine DesignYour (ES1) programs so far But what if ? You can potentially handle moreadvanced functionality. You are to execute these activities withinthe one program? How can you do all these things concurrently(at the same time)? How can you change the same LEDs based onboth (1) the push buttons, (2) as well as thephotoresistor? How can you print different information on thesame display? Yet, the program internal structure issimply a single sequence of actions:While (1) {1.2.3.4.SampleComputeActuateState updateRequirement1: Concurrency / Multitasking}Requirement2: Resource sharingMechatronics Lab5Mechatronics Lab61
Machine DesignMachine DesignHow you might have dealt withconcurrency?Even more, what if ? You need to ensure timing guarantees Of a certain task, irrespective of the othertasks being executed. You need to ensure that the LEDs should lit nolater than 5 ms after the button is pressed. Solution1 Solution2While(1) {While(1) Output2}Requirement3: 2Output1Output2}Is this a scalable solution?How well can you manage this software?Mechatronics Lab7Machine DesignMechatronics Lab8Machine DesignHow you might have dealt withconcurrency?How you might have dealt with realtime requirements? Other solutions You can try to make the execution timefrom sample to actuate as short aspossible? Use interrupts (event & time triggers) Deploy on a distributed computer system (withor without communication network) Deploy on a multicore processorWhile (1) {1.2.3.4.SampleComputeActuateState update}Is it enough to make theexecution as short as possible?Mechatronics Lab9Machine DesignMechatronics Lab10Machine DesignBut cannot solve all problems .The answer is ES2 Timing requirements. A sneak-preview in this lecture How can you guarantee that you can execute your taskwithin X time units? Concurrency. How can you fairly & predictably share the timingbetween multiple tasks.Partial Answer Timing requirements with Concurrency. Operating systemsHow can you guarantee that you can execute yourtask within X time units, given that other independenttasks need also to run?!Complete AnswerReal-time Operating Systems Resource sharing. How can you make sure 2 tasks can light the sameLED predictably? How can you make sure 2 tasks can print outinformation on the display in a controlled way. Need to solve them systematically Why re-invent the wheel?Mechatronics Lab11Mechatronics Lab122
Machine DesignMachine DesignBut first, an introduction to Advanced ES software:Embedded & Mechatronics Systems Advanced ES software Embedded & Mechatronics Systems Concurrency & multitasking Real-Time SystemsMechatronics Lab13Machine DesignMechatronics Lab14Machine DesignA mechatronic module: Scaniadiesel engine and controllerEmbedded & Mechatronics SystemsDomesticrobotPetComponentCarECU connectorson top of the ECUMedicalTough EnvironmentTight integrationReal-timeDependabilityCowbotRobotEngine ECU tasks: control of engine, fan, alternator, engine brake,turbo, and the EGR valve CAN communication, diagnostics, CombustionengineMechatronics Lab15Machine DesignMechatronics Lab16Machine DesignEmbedded & Mechatronics SystemsTypical activities in embedded systems An Embedded system typically requires a number ofactivities to be carried out!Communication Activity examples: hine interfaceControllersTime-triggered activities (such as control loops, etc.)Event-triggered activities (communication, interrupts, etc.)Diagnostics and supervisionCommunication (for example via CAN) Common characteristics of these activitiesSensors A mixture of timing requirements (Time- & event- triggeredactivities)Different modes of operationDiagnosticsConfigurability (on-line parameter change, software upgrade)Connectivity (for example diagnostics via GSM)Leading to the need to support concurrent andreal-time programmingMechatronics Lab17Mechatronics Lab183
Machine DesignMachine DesignA real-life example and analogy ofconcurrency (& scheduling)Advanced ES software:Concurrency & multitasking Task control block: Task state, priority and variables Context switching SchedulingMechatronics Lab19Machine DesignMechatronics Lab20Machine DesignA real-life example and analogy ofconcurrency (& scheduling)Push-button exerciseYou are at home and deeply involved inpreparing for the MF2042 exam!Suddenly the following things happen:- Requirements:1. Once a push-button is pressed, the corresponding led should be litfor 1s.2. The corresponding unit should have a maximum load less than50% over a full cycle3. Led status should be sent over the green bus to the LDI anddisplayed in a meaningful wayThe telephone is ringing.Someone is knocking on the door.The alarm is ringing from the kitchen.You still have not fixed your troubling computer.Design! Event- or clock triggers One or more interrupts Background loop Communication andvariablesMany activities and only one Processor. Scheduling!Scheduling algorithm: FPS, EDF, FIFO, SJF, Managing task states, context switching, etc.Mechatronics Lab21Machine DesignMechatronics Lab22Machine DesignMultiple activities and theirrealization as ”tasks”Concurrent Programming Definition, true and pseudo parallelismMapping activities into tasks1. Multiprogramming: on a single processor2. Multiprocessing: on multiple processors withshared resources3. Distributed processing: independent memories Map all into one sequential task Map each into a separate task Or something in-betweenLogical ConcurrencyUniprocessor ConcurrencyContextSwitchMechatronics Lab23Mechatronics Lab244
Machine DesignMachine DesignDefinition of real-timeAdvanced ES software:Real-Time SystemsCommon definitions: A computer system is a real-time one if itexplicitly manages resources in order to meettiming constraints(Douglas Jensen, 1992) A real-time system is a system where thecorrectness depends not only on the logicalresult of computation but also on the time atwhich the results are produced.(Jack Stankovic, 1988). A system that is synchronous with theinteracting environmentMechatronics Lab25Machine DesignMechatronics Lab26Machine DesignReal-time systemsHard vs. Soft real-time systemsTiming of actions is essential- Compare with juggling, air bag, engine control andmusic Hard real-timeAge of data is essential- Compare with juggling or a weather report: sampledata, compute, actuate - when does the data cease tobe valid? Soft real-time Timing and mission critical High reliability (predictability and determinism) Timing matters, but consequences are notcritical. Larger variations are allowed Notes:- Different consequences depending on context!- Different types of timing requirements- Delays need to be controlled!Can you think of examples of: Hard real-time systems? Soft real-time systems? Requirements on a real-time (computer) system(1) Sufficiently fast (processing, communication, .)(2) Predictable resource sharing and timing!Mechatronics Lab27Machine DesignMechatronics Lab28Machine DesignExamples of real-timeactivities/tasksReal-Time Computing Basics Hard real-time activities/tasks:–––– Time: the correctness of the systemdepends on both time and logic Real: the internal time scale mustmatch the external time scale Real-time: ( real fast) predictable indeterministic or probabilistic timingrequirements, i.e., the deadlineSensory data acquisitionDetection of critical conditionsControl output to actuatorControl of safety critical systems Soft real-time activities/tasks:–––––Mechatronics LabHMIHandling input data from the keyboardDisplaying messages on the screenGUILogging– Hard: missing deadline may causecatastrophic or critical consequence– Soft: meeting deadline is desirable, but notcritical29Mechatronics Lab305
Machine DesignMachine DesignExecution time – an importantparameter!Partial solution: Operating systemsFactors affecting the execution time of a piece ofcode: The number of and types of instructions in aprogram. E.g. floating vs. fixed point computations. Data dependent selections and iterations in aprogram. Varying execution time The compiler and linker libraries (other code)used The hardware speed (CPU itself and memoryaccess) Pipelines & caches increase average throughput butmay cause a varying execution time - beware!Thus in general: Cmin C CmaxMechatronics Lab31Machine DesignMechatronics Lab32Machine DesignWhat is an Operating System (OS)?Concurrent Programming using OS Scheduling of multi-tasks, and Management of memory, I/O, files, etc. Definition An operating system (OS) is software,consisting of programs and data, thatruns on computers and manages thecomputer hardware and providescommon services for efficientexecution of various applicationsoftware. (Wikipedia, 2010)ApplicationprogramsOS providesservices Example OS: Windows (XP, Vista, )LinuxUnixMac OS XHardware perating systemMechatronics Lab33Machine DesignOSMechatronics Lab34Machine DesignImplementation without OSScheduling on one CPU Pre-emption owing to scheduling method Blocked by shared resource or to wait for a time period Background/foreground programming Foreground:creation– Interrupt programming provided by themicrocontroller– Fixed priority provided by hardwaredispatchReady Background: main function, while loopRunningpre-empt Advantages: simple, efficient, small size Drawbacks:termination– Low level programming (interrupts, ports,timers)– Difficult to debug and re-allocate– ComplexMechatronics LabQueue of readythreads sorted byscheduling policy35Mechatronics LabBlocked/Waitingwaiting queuessorted byscheduling policy366
Machine DesignMachine DesignContext Switchcreation ready runningEffects of Schedulesrunning Task A: starts 0, deadline 3, exec. time 2 Task B: starts 0, deadline 2, exec. time 1AreadyThread AOKBpreemptionAThread BOKBterminationdispatch runningABlockedby var.BMechatronics Lab37Machine DesignBadXMechatronics Lab38Machine DesignProcesses vs. ThreadsA Process Has A process is an executable instance of aprogram stored and operating in its ownprotected memory space. (Unit of allocation) A thread is a stream of execution that mayshare memory space with others. (Unit ofexecution) Different methods of communication Code DataSP Stack Execution context– Program counter (PC)– Stack pointer (SP)– Data registersPCStackHeapStatic DataCodeGlobal variableOSMechatronics Lab39Machine DesignMechatronics Lab40Machine DesignA Thread Has Execution context– Program counter(PC)– Stack pointer (SP)– Data registersStack (T2)Stack (T1)SP(T1)Heap 1 process has at least1 threadStatic Data 1 thread must belongCode (T2)to 1 processCode (T1)Mechatronics LabSP(T2)Final solution: Real-time operatingsystemsPC(T2)PC(T1)41Mechatronics Lab427
Machine DesignMachine DesignInsufficiency of General PurposeComputer SystemsReal-Time OS GP computers optimized for highthroughput on the average, but notpredictable Direct memory access (DMA) steals CPUtime Nondeterministic access time of cache Interrupts of I/O devices Unknown blocking of shared resources Memory paging causes significant delay Uncontrollable queues in the kernel(FIFO)Mechatronics Lab Improvement on the limitations of GPcomputers No DMA on the microcontroller or bettercontrol method No cache on the microcontroller orconsider cache effects on WCET Direct access to I/O devices Time bounded access of sharedresources Static memory allocation Flexible scheduling policies43Machine DesignMechatronics Lab44Machine DesignReal-Time KernelCategories of RT Tasks A task is a thread or process A job is an execution instance of a task Periodic, aperiodic, and sporadic (with minimalinterval time) Also called Microkernel Core part of an RTOS Supports concurrent threads andscheduling Task communication and protection ofshared resources Error detection and onics Lab45Machine DesignMechatronics Lab46Machine DesignAn Illustrating ExampleReal-Time SchedulingCruise Control App. Definition: assigning (temporal & spatial) processorsand resources (memory, I/O devices) totasks to complete all tasks under constraintsCruise CntrThreadsref speedSpeedControlMechatronics LabSensor ofVelocityProcess of2 Threads Feasible schedule completes all tasksunder constraints Schedulable task set has at least 1feasible scheduleActuator ofGasProcesses of1 Thread47Mechatronics Lab488
Machine DesignMachine DesignScheduling Algorithm: CyclicExecutiveClassification of Scheduling Algorithms Preemptive: running tasks can beinterrupted Non-preemptive: (More difficult) Static: based on fixed parameters Dynamic: based on dynamic parameters Off line: the execution of all tasks aredetermined before activation (as a table) On line: decisions are made at runtimewhen the task set varies Optimal: minimize a “cost”, or no one isbetter than it Heuristic: no guarantee of the optimalityMechatronics Lab Old fashion Off line, static construction of an executiontable With or without OS support Manual or optimization-based Example: A (exe 0.5, per. 2), B (2, 6) Analysis within a hyperperiod (LCM)AB49Machine Designhyperperiod210426Mechatronics Lab50Machine DesignScheduling Algorithm: Fixed-PrioritySchedulingPros and cons of Cyclic Executive On line, preemptive, static A task has a fixed priority The scheduler dispatches the highestpriority job (and may preempt a lowpriority job) Predominant in RTOS Priorities are represented by integervalues Very efficient implementation usingperiodic timer interrupts and a dispatchtable Simple and relatively deterministic- Manual partition of long tasks- Changes (e.g., new tasks, differentexecution time) can cause completereschedule- Difficult to find a feasible schedule- Assumes a closed environment- Periodic tasks onlyMechatronics LabhighestPriority decreases151Machine Design2Value increasesnMechatronics Lab52Machine DesignScheduling Algorithm: RateMonotonic (RM) SchedulingScheduling Algorithm: DynamicPriority Scheduling Priority is proportional to rate Optimal fixed-priority policy, for periodictasks that On line, preemptive, dynamic Priorities are assigned to individual jobsdynamically The scheduler dispatches the highestpriority job Slightly higher computation overhead Not available in most commercial RTOS– are released at the beginning of a period andmust complete within the period– are independent– have fixed computation time (or upperbound,WCET), less than the period Example A (0.5, 1), B (1, 2)AABB0Mechatronics Lab2X0253Mechatronics Lab549
Machine DesignMachine DesignScheduling Algorithm: EarliestDeadline First (EDF)Resource Sharing (optional) Priorities are assigned inverselyproportional to the absolute deadlines ofthe active jobs Under the same assumption for RM, nperiodic tasks are schedulable if and onlyifU C1/T1 Cn/Tn 1 Optimal among ALL preemptive schedulingalgorithmsAB0Mechatronics Lab255Machine DesignMechatronics Lab56Machine DesignUnprotected Resource SharingUnprotected Resource Sharing A resource is any soft-/hard-ware entityused by a thread to advance its execution Critical section is not atomic Concurrent tasks are pre-emptive Unpredictable value (corrupted data)Thread BThread AWhat is the final value of n?Thread AThread B n: n 1n: n-1 n 5R1R2b2a2 R1 1Critical region (section): a sequence of statements accessingthe shared resourceMechatronics Labb1a1a3n 5b3b1, b2, b3a1, a257Machine Designa3R2-1n 6Mechatronics Lab58Machine DesignImportance of Mutual ExclusionHow to Ensure Mutual Exclusion The resource is shared by at least twopreemptive threads Critical region may be shared globalvariable, non-reentrant code, devices The operations of the critical region isnot atomic (must allow interleaving) Unpredictable, difficult to debug Need mutual exclusion to protect ashared resource from concurrent access The protected resource is mutuallyexclusive resourceMechatronics Lab Disallow pre-emption (by disablinginterrupts or limiting preemption level) Serialize resource access by separatingthe threads that access the samemutually exclusive resource (via offlinescheduling) Utilize OS supported “protectiontechniques”: semaphores, messagequeues, etc.59Mechatronics Lab6010
Machine DesignMachine DesignAn Old Fashioned ApproachA Naïve Approach Use a Boolean free A new shared resource created! Both threads may find (free 1) Disallow ALL pre-emption Negative effect to other important interruptsThread AThread BThread A disableinterrupts;disableinterrupts;while (!free);n: n 1;nenable interrupts; n: n-1;n: n 1enable interrupts; 61Machine Design while (!free);free 0;Mechatronics Labfree 0;nn: n-1;free 1;free 1; Mechatronics Lab62Machine DesignHow to Improve It?Semaphore Checking and locking should be atomic Replace the inefficient polling with “blocking”and “awakening” mechanismThread Awhile (!free); while (!free);free 0;n: n 1 Semaphores: (Sec. 4.2) Invented by Dijkstra in 1965 Common in OS Many variants. We are using binary semaphoresonly in this course and Rubus OS Adopt the improvements Typical system calls: Lock(S) or Wait(S): lock the resource. If it isalready locked, then wait (or is blocked) Unlock(S) or Signal(S): Unlock the resource, andwake up all waiting (or blocked) threadsThread Bfree AtomicThread Bfreefree 0;nn: n-1;free 1;free 1; AtomicMechatronics Lab63Machine DesignMechatronics Lab64Machine DesignBinary SemaphoreExample of Using SemaphoreSemaphore status is managed by OS Two values: Free (1), Locked (0) Must have an initial value Thread A calls Lock(s):s – If s is free (1), then s is locked (0) and Acontinues– If s is already locked (0), then s remainslocked and A is blockedLock(s);n: n 1 Thread A calls Unlock(s):– If s is free (1), then s remains free and Acontinues– If s is blocked (0), then s is free (1), Acontinues, and all threads blocked by sbecomes readyMechatronics LabThread BThread ABA65Mechatronics Labn Lock(s);n: n-1;Unlock(s);Unlock(s); Lock(s), B is blockedLock(s)Unlock(s)Unlock(s)6611
Machine DesignMachine DesignChanging Thread States withSemaphoresDeadlock Caused by SharedResourcescreation Multiple threads “lock” each other and noone can proceed Deadlock occurs when each one (thread)holds one resource (semaphore) and waitsfor the other one Priority inheritance cannot avoid it Starvation: a thread never gets CPU timeto execute, because of overload minationA different threadcalled Unlock(s)Mechatronics LabBlocked/WaitingLock(s) when s isalready locked byanother thread67Machine DesignMechatronics Lab68Machine DesignTerms to keep in mindConclusion You have been introduced to Mechatronics Lab69Mechatronics LabConcurrency & concurrent programmingReal-Time systems & real-time programmingGeneral Operating systemsReal-time operating systemsReal-Time SchedulingResource sharing7012
Introduction to Advanced Embedded Systems (The Course) 2 Machine Design Mechatronics Lab Agenda (ES1) software development so far The limitations of your current examples. Challenges: concurrency, real-time & resource sharing. Advanced ES software Embedded & Mechatronics Systems Concurrency & multitasking Real-Time Systems
