EXAM 1 Flashcards
Hard RTS
- Must meet its deadline with zero flexibility ( or near-zero degree of flexibility)
- Result is useless if computed after the dealine
- If the deadline is missed, it can be catastrophic, costly, may involve human life or entire system damage
Soft RTS
- There is a level of flexibility in meeting the deadline
- Applied when
- > Does not involve catastrophic failures
- > It is still acceptable ( within a frame of tolerance)
- > Can be somehow corrected by approximation, etc.
- Occasional soft or permanent soft RTS
RTS Requirement
Computation must be finished before reaching a given deadline
Differentiation of Hard vs. Soft
- Hard RTS – at deadline you have a deterministic value/action
- Soft RTS – the value can be an estimation
Corrections for Hard and Soft
- Hard systems make every effort in predicting if a pending deadline might be missed
- > Anticipation of a missed deadline
- > Envelope of deadline ‘safety zone’
- > Able to apply corrective actions before a catastrophe
- > Compensate by computing estimations forward instead relying on precise values
- Soft systems may have recovery actions after the deadline is missed – think about resynchronization
Deterministic Character
- In RTS, timing correctness complements functional correctness – they coexist
- You work with functional and timing issues, and moreover, you synchronize functions by means of accepting/issuing timing events
- RTS have substantial knowledge of the controlled environment as well as the controlled system itself
- RTS have deterministic character
- > Because the response time to a dedicated event is bonded
- -> Fixed bonding
- -> Flexible bonding
- > Actions are taken in response to an event as known a-priori
- > They are less adaptable to the changing environment
- -> Dedication to a mission
- -> Because of lack of adaptation they can be less robust
- > Levels of determinism and robustness can be balanced (some form of adaptation may be permitted)
- > This balancing is application specific
Round Robin Scheduling
Tasks all get an equal amount of time, sharing the processing unit equally. Typically, there is a variation of scheduling algorithms used, such as preemptive attributes allow a round robin scheduler to have higher priority task interrupt a task execution.
Preemptive Priority Scheduling
Tasks are executed based of priority. This is often used in conjunction with another algorithm, such as round robin.
Objects
- Special constructs that are the building blocks for application development for RTOS
- > Tasks - concurrent and independent threads of execution that can compete for CPU execution time
- > Semaphores - are token-like objects that can be incremented/decremented by tasks for synchronization or mutual exclusion
- > Message queues - are buffer-like data structures that can be used for synchronization, mutual exclusion, and data exchange by passing messages between tasks.
- Developers can combine these objects (and others) to solve common real-time problems such as concurrency, activity synchronization, and data communication
Services
- Help developers to create applications
- They comprise sets of API calls to kernel objects, or in general to facilitate timer management, interrupt handling, device I/O, and memory management
The five key characteristics of an RTOS
- Reliability
- Predictability
- Performance
- Compactness
- Scalability
Reliability
- One of the most important characteristics
- Must need to operate for long periods of time without human intervention
- Some may allow reset, others will not allow due to consequences
- Reliability is influenced by all components (hardware and software)
Predictability
- Meeting time requirements
- Deterministic - must have predictable behavior
- Measuring:
- > Testing time responses in different situations
- > Computing the variance of the response times for each type of system call
Performance
- How fast deadlines are met
- Measuring:
- > MCU MIPS
- > Throughput - measure overall system performance
- -> The rate at which a system can generate outputs based on inputs coming in
- -> The amount of data transferred divided by the time taken (bps)
- > Call-by-call
- -> Use of timestamps to indicate when a system call started and when finished
Compactness (plus weight and software size)
- Physical size (final product)
- Resources taken (understanding memory requirements is very important
Scalability
- RTOS should scale-up (or scale-down) to meet a wide variety of applications
- Depends on a number of functionalities used
- Ability to add extra modules/services
Tasks
An independent thread of execution, which it can compete with other tasks for execution.
Idle task
- This is a system task of lowest priority executing an endless loop
- Executed when no other task can run
- It can be a user supplied routine
Task execution states
- Ready state
- Blocked state
- Running state
Task states must be maintained by a kernel.
Task in Running state
- Task switching will need to swap register content
- involved in task control execution
- holding local variables/pointers
- No need to swap global variables/pointers
- A running task can move to the blocked state
- By making a call that requests an unavailable resource
- By making a call that requires to wait for an event to occur
- By making a call to delay the task for some duration
- In non-RTOS systems, you will need to have a register/memory model
Task in Blocked state
- Without being blocked by resources - it means, a lower priority task could not run (CPU starvation)
- Blocking conditions include:
- A semaphore token for which a task is waiting
- A message, on which a task is waiting
- A time delay imposed on the task
Task creation and deletion
- In non-RTOS systems, you want tasks to be in memory as static objects
- Static memory allocation for data is preferred
- Dynamic memory allocation will add a lot of complications
- Creating a task is simply initializing it and moving to the Ready state
Task Scheduling
- In non-RTOS systems, there is a lot of freedom in designing a task scheduling algorithm
- rule of thumb: simple approach first, then complicate later
- include objects involved in blocking (semaphores/tokens, message queues)
- preemption lock - used when a task is in a critical section of code, which cannot be preemted by other tasks ( also known as an atomic operation)
- a mechanism is needed to support this feature
- task completion
- run-to-completion tasks vs. endless-loop tasks
- An oversight is needed to detect and escape scheduler misbehavior
- Use FSM approach to model the scheduler
Semaphores and the types
A kernel object that one or more threads of execution can acquire or release for the purpose of synchronizaiton or mutual exclusion (token)
- Allows a task to carry out some operations or access a reasource
types:
- Binary semaphore
- Counting semaphore
-Mutual exclusion semaphore (Mutex)
Binary semaphore
- Can have a value {0-unavailable, 1-available}
- Treated as global resources (shared among all tasks that need them)
Counting semaphore
- Allows for issuing multiple tokens
- uses a count to allow it to be acquired or released multiple times.
- Limited use
Mutual Exclusion (Mutex) semaphores
- Special binary semaphore that supports ownership, resource access, etc. for avoiding problems inherent to mutual exclusion (use with resources)
- holds task-ID
- It can be released only by a task which acquired it.
Semaphore use
- Wait-and-signal semaphore
- communication between two tasks for the purpose of synchronization without exchanging data (execution flow control)
- tWaitTask can have higher priority
- Multiple-task wait-and-signal semaphore
- Sensor -> multiple_action
- can be used with a counting semaphore
- credit-tracking synchronization
- single shared-resource-access synchronization
Message Queue
A buffer-like object through which tasks and ISRs send and receive messages to communicate and synchronize with data.
- Temporarily holds messages from a send until the intended receiver is ready to read them
- Temporary decoupling of sending and receiving task (it frees the tasks from having to send and receive messages simultaneously)
Message Queue states
- Empty
- Not empty
- Full
Message queue content
- a temperature value
- a bitmap to draw on a display
- a text message to print on LCD
- a keyboard event
- a data packet to send over the network
Why message queue vs. pointers to data
- Keep copying to a minimum - copying data is expensive in embedded systems
- allocate separate memory locations for a queue
- use a concept of private buffers to communicate between task in a simple way
Message queue design considerations
Size Organization Access controls Handling exceptions Message order - FIFO - LIFO
Message queue use
- Non-interlocked, one-way data communication
- simplest scenario: loosely-coupled
- typically tSinkTask has higher priority
- ISR use for tSourceTask
- Interlocked, one-way data communication
- communication requiring a handshake protocol
- Use of a binary semaphore
- Sender waits for confirmation
- Blocking and non-blocking approach
- A need for a FSM model of the protocol
- Interlocked, two-way data communication
- Bidirectional data flow; e.g., like a procedure call, or client/server
- Broadcast communication
- Sending to multiple tasks
- Issue of message removal (detect of all tasks blocked situation)
Event registers
Approach
- processing is triggered by occurrence of events
- event register associated with each task; and consists of a group of binary event flags to track the occurrence of specific events
- There can be a global event register
- Events are combined into a condition (logical function)
Exception
An exception is any event that disrupts the normal execution of the processor and forces the processor into execution of special instructions in a privilege state
- Synchronous:
- For example: Division by zero; alignment problem w/ memory addressing
Interrupt
An interrupt is an external asynchronous exception triggered by an event that an external hardware device generates
- Asynchronous
- external to current computing
- For example: System reset; Data received by a subsystem
Programmable Interrupt Controllers (PIC)
- Low-pin MCU have one INT input; high-pin MCUs have more INT inputs, but this is frequently not enough
- Interrupt control processing is handled externally by PIC
- Implementations differ but provide two main functionalities:
- Prioritization of multiple interrupt sources and flagging one of the highest priority
- Offloading the core MCU from determining an interrupt source
- They are programmable
- Each interrupt request line has a priority assigned to it (mostly through software, but can be through hardware)
- Support nested interrupts
- Can be cascaded to allow for a large number of interrupt sources
general exceptions
- classification of exceptions
- Asynchronous - non - maskable
- Asynchronous - maskable
- Synchronous - precise (instruction causing a problem is determined through program counter register)
- Synchronous - imprecise (multiple causes exist due to pipelining, etc.)
- Many MCUs have additional non-maskable interrupt input line (NMI)
- Knowing the reason/source of exception helps to determine how the system is to recover from exception, if it is possible anyway
- Priorities Highest to lowest
- Asynchronous - non - maskable (system reset)
- Synchronous - precise
- Synchronous - imprecise
- Asynchronous - maskable
- External interrupts (except NMI) are the only exceptions that can be disabled by software
Stack overflow
When data is copied onto the stack past the statically defined limits. This causes corruption.
Exception timing
Interrupt response time
- Interrupt latency
– Time between interrupt signal and the ISR begins to execute
– includes interrupt acknowledgment and initial organization for processing
– influenced by a higher priority interrupt being executed at the time
– Influenced by time over the interrupt system is disabled and then later re-enabled by software
Split processing time
- interrupt processing can be split into two parts: necessary one (under masked interrupt system) and a dedicated daemon task that can be interrupted
- in such a case, an interrupt serves as a ‘semaphore’ for a daemon task
- Disadvantages
– total response time expands
– Daemon task may not run if there are other higher priority tasks waiting
Hard timer
- implemented by hardware
- high-precision events
- invokes an interrupt service
- one of them can be used by a scheduler
- Often limited number of hardware timers
Soft timer
- Scheduled through software activity
- Non-high-precision mechanism
- Should be used for timeout implementation
Types of of multitasking schedulers
- Cooperative Multitasking
- Preemptive Multitasking
- Time-Sharing Multitasking
- Event driven
Cooperative Multitasking
An inexpensive alternative to time-sharing multitasking
In a simple form - implements passing execution from one task to the scheduler when:
- certain number of instructions was executed ( similar to tick estimation for time-sharing multitasking
- Nothing important is to be done next by this task
- has to wait and there is hurry
- Scheduler decides to execute another task or get back to the original one
- non-preemptive; although preemptive concept can be added as well
Example: Each task has multiple leave-points to the scheduler i.e. call, goto, return, or return-from-int
Preemptive Multitasking
Software decomposed into :
- one background task
- Multiple ISRs
Interrupts
- Hardware - external
- Hardware - internal (timers)
- Software (through INT instructions)
- Software-Hardware interrupt (non-conventional tricks depend on architecture)
– using output_pin to input_pin connection to create interrupt
– using logical high input and interrupt masking bit
- External interrupts require a hardware-based PIC
– an excellent approach to handle external interrupts
- resolves priority conflicts
- requires an ID passing protocol; INT-INTACK protocol
Time-Sharing Multitasking
- Full-scale multitasking
- Scheduler is a super task - meaning it activates other application tasks
- Scheduler is always activated by its own timer
- Requires full task swapping and elimination of recursions (by design)
- ISRs can be added as additional higher-priority routines
- Task priorities are
- Mostly fixed
- Variable for a truly advanced scheduler
- Scheduler jobs: update tasks states - decide which one to run - Pass execution
- Task sequencing
- all task have the same priority
- based on different priority
- task priority adjustment
Event-Driven scheduler
Interrupt-drive systems
- system waits for interrupts ( similar to preemptive multitasking)
Energy sensitive applications
- System goes to sleep as frequently as possible to save energy
- MCUs with nano-Watt technology have many sleep levels
- system clock frequency change can also be used to decrease power consumption
– Higher-frequency clock operations are for time sensitive (main) threads/tasks
– low-frequency clock operations are reserved for background threads/tasks
- System awaits a tick or event to wake up and process
- in summary, MCU executes only when the application has something to do.
