CES 520 - WEEK 3 September 5, 2006 -- Software for embedded systems

Interrupts

• Used for asynchronous events, triggered by hardware, either internal or external. For example:
• Typically internal
• Serial port
• Timer
• Typically external
• Front-panel button or control
• Alarm
• Measurement sensor
• Interrupt causes microprocessor to branch to the Interrupt Service Routine (ISR)
• Typically happens at the end of the currently-executing instruction (if interrupt is not disabled)
• Microprocessor hardware saves the program counter (PC) on the stack (sometimes other registers as well)
• The first thing the ISR does is push onto the stack any registers used by the ISR (Save the context)
• Some processors have a hardware stack. On others, stack must be implemented in software.
• This is done automatically in C
• Must be programmed explicitly in assembly
• At the end of the ISR values are popped back into the proper registers (Restore the context)
• Maskable interrupts
• May be masked one at a time or all interrupts may be disabled
• Nonmaskable interrupt
• Typically used for brown-out power failure or other fatal system errors
• Prioritized interrupts
• Each interrupt is assigned a priority
• The program can specify the lowest priority interrupt it will accept at any given time
• In many processors, the priority can automatically change when an interrupt occurs, e.g.
• Disable all interrupts
• Disable all interrupts of the same or lower priority (e.g. Rabbit 3000)
• Disabled interupts will execute when interrupts are enabled again, in priority order
• The Rabbit has 4 processor priorities (0-3) and three interrupt priorities (1-3)
• Interrupts with priority <= processor priority are blocked
• Upon interrupt, processor priority is set to interrupt priority
• On the Rabbit 3000, the interrupt priority must be restored at the end of the ISR
• This is done automatically in C
• Must be programmed explicitly in assembly (using IPRES instruction)
• Nested interrupts
• Reduces worst-case interrupt response time - don't need to wait for previous ISR to finish
• Interrupts must be (re)enabled at the beginning of the ISR.
• Must save context of each interrupt when it is interrupted
• Stack size can be an issue
• The Rabbit has a 4-level hardware interrupt stack to store interrupt priorities.
• Interrupt vectors
• Addresses of ISRs are located in a table, one entry for each hardware interrupt input
• Many embedded-system processors simply jump to a hard-coded memory location for each interrupt.
• 16 addresses for each interrupt (like Rabbit 3000) may be enough for short ISRs.
• If ISR is more than 16 instructions, you have to put a jump instruction to another spot in memory.
• Edge-sensitive interrupts
• CPU latches in the interrupt and services it whenever it can
• Useful for interrupts that don't wait for the processor to respond. e.g. timers
• Normally edge-sensitive interrupts can't share an input
• Level-sensitive interrupts
• If interrupt gets stuck active, the ISR will run over and over forever
• Be sure if power fails to the external device, the interrupt is inactive
• The device needs a mechanism for the CPU to reset the interrupt request before exiting the ISR
• If interrupt goes away before the CPU responds, the interrupt will be lost
• Useful for multiple devices to share an interrupt line: CPU services interrupts in priority order
• Each device must use the same polarity interrupt
• The processor reads the interrupt inputs to determine which device to service
• Each device must hold its line active long enough for the ISR to read it
• The first device to assert an interrupt blocks the others until it is released
• If the ISR runs longer than the time between interrupts, the devices must store interrupt requests
• Most of these issues are taken care of when the processor has separate interrupt inputs for each device
• The shared-data problem
• An ISR can change shared data while some other routine is in the middle of using it
• May not be a problem if the other routine reads the data with a single machine-language instruction and doesn't depend on the value remaining the same subsequently
• But most C statements result in several machine-language instructions (i.e. not atomic)
• If this is important, you should examine the assembly-language output of the C compiler.
• Optimizing compilers may give different results on different compilations.
• The problem may occur very rarely, which makes the bug difficult to find.
• Solution: Disable interrupts during the other routine's critical section (while using shared data)
• It's up to the programmer to make sure that no cases are missed
• Increases interrupt latency
• Solution: Certain Rabbit instructions are privileged
• Interrupts are automatically disabled until the following instruction is finished executing
• For example, instructions that manipulate the stack, instruction pointer, and extended-memory register
• Much less overhead than explicitly disabling/enabling interrupts
• Solution: Place all code that uses the data in the ISR itself.
• Not always possible
• Longer ISR - increases latency of lower-priority interrupts
• Other solutions tend to be dangerous if not implemented carefully
• Worst-case interrupt latency includes
• 1. Maximum time the interrupt is disabled by a higher-priority interrupt or task
• 2. Maximum length of an instruction
• On CISC machines (such as the Rabbit) different instructions are different lengths
• 3. Hardware interrupt response time
• 4. Note that no useful work gets done until the ISR finishes saving the context on the stack
• On Rabbit 3000, maximum for 2 + 3 is 29 clock cycles
• What should go in the interrupt service routine?
• Normally as little as possible, to reduce latency for other interrupts
• Measurement system: Interrupt should trigger (or be triggered by) the measurement.
• ISR inputs the data.
• Then, a lower-priority task analyzes the data.
• Control system: Interrupt should trigger the control output.
• ISR outputs pre-calculated data.
• Then, a lower-priority task starts calculating data for the next interrupt.
• Only time-critical operations are performed in the ISR.
• So-called software interrupts
• Really a special type of CALL instruction. Synchronous event initiated by the processor.
• Typically uses same interrupt vector table as hardware interrupts
• Commonly used to implement breakpoints and operating system entry points.
• Typically executes faster than a CALL instruction.
• Polling is an alternative to using interrupts
• Processor accesses the hardware under program control, not in response to an interrupt
• This is considered a synchronous event
• Generally slower response time - used for non-time-sensitive functions
• Processor can't "go to sleep" to save power
• Simpler to implement
• The processor always knows exactly when an event will occur
• No context saving required
• No shared-data problem
• Multiple interrupts can not hog 100% of processing time (e.g. "stuck" interrupt)
• Most systems use a combination of interrupts and polling
• General rule: Use polling whenever possible; use interrupts only when required.
• Rabbit interrupts
• 16-bit interrupt vectors
• Lower 8 bits are unique to each hardware interrupt
• Upper 8 bits are specified by IIR register (internal interrupts) or EIR register (external interrupts)
• Example: Rabbit external interrupts
• Each interrupt has one or two control/status registers, for example External 1 uses I0CR

Real-time systems

• Real-Time System (RTS) = "A computer system in which correct operation is defined not only by the correctness of controller actions but also by the time at which actions are produced."
• A desktop computer typically doesn't qualify because, although one wants the response to be "fast", there are no specific timing requirements.
• Hard RTS has strict timing requirements
• Soft RTS allows occasional timing failures
• Real-time systems require "predictable" timing. That does not necessarily imply "fast".
• Many embedded systems are RTSs.
• Timing may be estimated by
• First calculate the minimum and maximum execution time of each task
• One method is to add up the instruction execution times in the data book
• Can also run the task and measure the execution time
• Use an internal timer
• Output a pulse at beginning and end of routine and measure with an oscilloscope
• Then use path analysis to determine the best case and worst-case sequence of tasks
• Include best and worst-case interrupt latency
• Some features increase average speed but degrade predictability.
• Interrupts
• Direct memory access (DMA)
• Cache memory
• Instruction prefetch mechanisms, such as pipelining
• Instructions whose execution time can depend on the data

Multitasking

• Tasks are sequential pieces of code with different timing properties.
• A multitasking system assigns each task it's own complete context.
• Context means the combination of all CPU resources, in the proper state for the task.
• Each task "thinks" it has exclusive use of CPU resources.
• Normally associated with real-time operating systems.
• Advantages of multitasking
• Allows better-structured code.
• Easier to understand and debug.
• It's as though all tasks are running simultaneously.
• Each task "thinks" its context is the only one.
• But you still need to be careful about tasks sharing hardware resources.
• Each hardware device can be serviced by a separate task, simplifying the design.
• Different tasks can be developed by different programmers.
• Multitasking lends itself to fast task response.
• Otherwise-wasted idle time can be used by tasks other than the one waiting.
• Real-time operating systems are organized by task.

Real-time scheduling

• Preemptive vs non-preemptive
• Non-preemptive (also called cooperative): Task gives up control voluntarily.
• The simplest method is for each task to execute to completion.
• Long tasks should give up control at "convenient" breakpoints.
• More time-consuming to design: Each task must be designed to "cooperate".
• Can be a problem with multi-programmer teams.
• Easier to debug.
• Tasks are synchronous - shared data problems are easy to avoid.
• Less formal communication required between tasks.
• Requires fewer CPU cycles (faster execution but slower task response)
• Preemptive: Tasks can interrupt each other, based on priority.
• Switching tasks is handled by some kind of scheduler, typically a real-time operating system.
• Task switches are initiated by interrupts.
• Timer interrupts are frequently used to give each task a specified amount of time.
• Tasks may be prioritized.
• Predictable latency
• Timing properties
• Periodic (time-trigered) - specified time between task executions
• Often used in safety-critical systems
• Aperiodic (event-triggered) - Trigggered by interrupts
• Easier to design, more flexible, lower computational overhead
• Sporadic - like aperiodic, but with known minimum time between tasks
• Round-Robin scheduling
• Each task executes in order, each task executes to completion
• Latency of each task equals the total execution time of all tasks
• No shared-data problem: best scheme for simple systems
• Round-Robin with interrupts
• Any time-critical code is put in the interrupt service routines
• Time-critical tasks are prioritized using hardware interrupt priorities
• Potential shared-data problems
• Function-Queue scheduling
• Interrupt routines add function pointers to a queue that are then called by main()
• Each function (task) executes to completion
• Tasks can be prioritized in the queue - doesn't have to be first-in, first-out
• Real-time operating system (RTOS)
• Communication between ISR and task code is handled by the RTOS
• RTOS can suspend a task to run a higher-priority task (based on new information from an ISR)
• All scheduling is done by the RTOS
• Most RTOSs are preemptive - one task can interrupt another
• Priority-based schedulers
• Fixed-Priority Scheduling (FPS)
• Static priorities. Usually table-driven. Table is generated before the system is started (offline)
• First-in first-out (FIFO) within each priority class
• When a thread is pre-empted, it moves to the head of the list
• When a thread blocks (is waiting for a resource to become free), it moves to the end of the list
• In periodic systems, the run-time dispatcher causes tasks to execute in pre-determined time slots
• Inflexible. Any system changes require re-calculating the schedule.
• Rate-monotonic scheduling: Shortest tasks have highest priority
• Optimal static scheduling mechanism
• Earliest Deadline First (EDF)
• Dynamic priorities: scheduler executes task with earliest deadline.
• Optimum scheme for simple task models on single processor.
• Can be computationally expensive, especially when combined with FPS.
• Poor performance under overload conditions.
• Other more-complicated dynamic priority schemes exist

Principles of good coding for embedded systems

• Component-based design
• Each component encapsulates some functionality
• Functionality only accessed through the interface of the component
• This prevents multiple tasks accessing the same hardware at the same time
• Introspective interfaces
• Specify non-functional attributes such as memory usage, execution times, etc.
• May be used offline, during component assembly phase
• Example of online usage: admission control for new system components (plug and play)
• Don't put everything in main()
• All possible errors must be trapped and handled without human intervention
• A real-time system handles asynchronous external events. All possible timing combinations must be analyzed.
• READ THE DATA SHEETS of all peripheral devices. Check for subtle timing and other requirements.
• Code should be understandable
• Well-structured - hide details in functions.
• Don't optimize first. Optimize only when necessary.
• Judicious use of comments.
• Descriptive function and variable names. Hungarian notation is useful:
• Capitalize name preceded by lower-case letters to indicate the data type
• "byName" is byte, "iName" is int, etc.
• Precede with "p_" or "a_" for pointers and arrays
• a_chName is an array of characters
• Documentation
• Software specifications are important for:
• Ensuring compatibility with hardware specifications
• Future software maintenance
• Coordination of multi-programmer projects
• Design reviews
• Documenting functionality (e.g. user interface)
• Typical specifications outline:
• Suggested design procedure:
• First write requirements in English, including interfaces to other software components
• Generate high-level pseudocode
• Make the pseudocode more detailed
• Start adding actual code, with pseudocode as placeholders for parts not yet implemented
• The pseudocode becomes comments in the final source code
• Conventional flowcharts often not very useful for RT systems - don't show preemption or interrupts well
• Data flow diagram
• Each task is drawn as a block
• Arrows between blocks show data flow
• State diagram
• Each possible state is drawn as a block
• Input arrows show signals that can cause a change in state
• Output arrows show possible transitions to a new state
• Complex systems may not fit on a reasonable number of pages
• Suggested C coding standards

Assignments:

• Read An Embedded Software Primer, Chapters 4 and 5
• Read Embedded Systems Design, Chapter 8, pp 288-304
• Lab 2: Write a test program and library file. (Due in 1 week)