Terminology and Notation

Definitions related to a system

• • Embedded System: is a computing component integrated into a larger system with the purpose of managing its resources and monitoring/controlling its functions using special hardware devices.

• • Real-Time System: is a computing system whose correct behavior depends not only on the value of the computation but also on the time at which outputs are produced.

• • Functional requirements: specify the functions a system is supposed to accomplish defined in terms of inputs, behavior, and outputs. Functional requirements specify particular results of a system, such as calculations, technical details, data manipulation, and processing.

• • Extra- (or Non-) functional requirements: (also called performance or quality requirements) specify constraints on the design or implementation, such as performance requirements, timing constraints, security, cost, energy consumption, lifetime, or reliability.

• • Schedule: A particular execution sequence of the task set composing the application on a given computing platform.

• • Feasible schedule: A schedule in which all tasks are executed within the specified constraints.

• • Feasible task set: A task set for which there exists a feasible schedule for it on a particular computing platform.

• • Schedulable task set: A task set is said to be schedulable by a specific algorithm A if A generates a feasible schedule for the task set.

• • Overload: a condition in which the total computation requested by a task set in an interval of time exceeds the length of the interval, so it is not possible to find a feasible schedule.

• • Predictability: capability of predicting the system behavior through proper analysis techniques. In a real-time system, predictability refers to the capability of predicting timing properties, such as tasks worst-case execution times and worst-case response times.

• • Adaptivity: capability of a system of modifying its internal strategies to achieve its design objectives even when the design assumptions are not fully satisfied.

• • Robustness: capability of a system of achieving its design objectives even when the design assumptions are not fully satisfied, without modifying its internal strategies.

• • Dependability: a collective property of a computing system related to the trust placed on its service. Dependability includes a number of attributes:
    • Availability – readiness for correct service;
    • Reliability – continuity of correct service;
    • Safety – absence of catastrophic consequences on the user(s) and the environment;
    • Integrity – absence of improper system alteration;
    • Maintainability – ability for a process to undergo modifications and repairs.

• • • Dependability can be jeopardized by three possible causes (called threats):

• • • • Fault: is a defect in a system (e.g., a software bug). The presence of a fault in a system may or may not lead to a failure. For instance, although a system may contain a fault, its input and state conditions may never cause this fault to be executed so that an error occurs and thus never exhibits as a failure.

• • • • Error: An error is a discrepancy between the intended behavior of a system and its actual behavior inside the system boundary. Errors occur at runtime when some part of the system enters an unexpected state due to the activation of a fault. Since errors are generated from invalid states, they are hard to observe without special mechanisms, such as debuggers or event tracers.

• • • • Failure: A failure is an instance in time when a system displays behavior that is contrary to its specification. An error may not necessarily cause a failure. For instance, an exception may be raised by the system in response of an error, which then may be caught and handled using fault tolerance techniques so the overall operation of the system will conform to the specification.

Dependability can be increased by using four different techniques:

• • • • Fault Prevention consists of preventing faults being incorporated into a system, by using proper development methodologies and implementation techniques.

• • • • Fault Removal can be divided into two sub-categories: Removal During Development and Removal During Use. Removal during development requires verification so that faults can be detected and removed before a system is put into production. Once systems have been put into production a system is needed to record failures and remove them via a maintenance cycle.

• • • • Fault Forecasting consists of predicting likely faults so that they can be removed or their effects can be circumvented.

• • • • Fault Tolerance deals with putting mechanisms in place that will allow a system to still deliver the required service in the presence of faults, although that service may be at a degraded level.

Definitions related to a computation

• • Task: a sequence of instructions that, in the absence of other activities, is continuously executed by the processor until completion. A task is typically activated several times on different input data, generating a sequence of task instances, called jobs.

• • Job: an instance of a task executed on a specific input data.

• • Thread: a task sharing a common memory space with other tasks.

• • Process: a task with its private memory space, potentially generating different threads sharing the same memory space.

• • A task is characterized by properties, requirements, derived values, and exceptions.
    • • Properties depends on the specific implementation of the task and on the architecture on which the task is executed.
    • • Requirements are features requested by the designer to satisfy performance constraints.
    • • Derived values are performance variables measured during or after the execution of a task. They depend on the task properties and on the scheduling policy adopted by the system.
    • • Exceptions define violations of requirements.

• Typical properties of a task include:
  • • Worst-Case Execution Time: the longest execution time needed by a processor to complete the task without interruption over all possible input data.
  • • Best-Case Execution Time: the shortest execution time needed by a processor to complete the task without interruption over all possible input data.
  • • Execution Time Distribution: probability distribution of task execution times over all possible input data.
  • • Memory Footprint: maximum memory space required to run the task.
  • • Priority: a number expressing the relative importance of a task with respect to the other tasks in the system.
  • Preemptive execution: possibility of interrupting the execution of a task (in favor of another computational activity) and resume it at a later time.
    • • Fully preemptive: a task is fully preemptive if it can be interrupted anytime and anywhere during its execution.
    • • Non preemptive: a task is non preemptive if it cannot be interrupted during its execution.
    • • Partially preemptive: a task is partially preemptive if it can be interrupted only in specific locations (preemption points) or it contains specific sections of code (non-preemptive regions) that cannot be interrupted.
  • Criticality: a property specifying the consequence for the whole system of missing the task timing constraints. This property is typically specified as a set of task classes:
    • • Hard: a task is said to be hard if missing the timing constraint of any of its job may jeopardize the correct behavior of the entire system.
    • • Firm: a task is said to be firm if missing a timing constraint does not jeopardize the correct system behavior but it is completely useless for the system.
    • • Soft: a task is said to be soft if missing a timing constraint does not jeopardize the correct system behavior and has a still a reduced value for the system.
  • Typical requirements that can be specified on a task include:
    • • Activation pattern: a requirement specifying the relation between the activation times of subsequent jobs. The activation pattern determines different types of tasks:
        • • Periodic Task: a task in which jobs are activated at regular intervals of time, such that the activation of consecutive jobs is separated by a fixed interval of time, called the task period.
        • • Aperiodic Task: a task in which jobs may be activated at arbitrary time intervals.
        • • Sporadic Task: a task in which the activation of consecutive jobs is separated at least by a minimum interarrival time.
      • Phase (for a periodic task): the time at which the first job is activated.
    • • Period (for a periodic task): fixed separation interval between the activation of any two consecutive jobs.
    • • Minimum Interarrival Time (for a sporadic task): minimum separation interval between the activation of consecutive jobs.
    • • Relative Deadline: the longest interval of time within which any job should complete its execution.
    • • Absolute Deadline (of a job): the time at which a specific job should complete its execution.
    • • Precedence relation: a constraint specifying the order of execution between two or more tasks.
  • Typical derived parameters that can be computed on a scheduled job are:
    • • Activation time (release time or request time): the time at which the job is activated, that is, becomes ready for execution;
    • • Start time: the time at which the processor starts executing the first instruction of the job;
    • • Finishing time: the time at which the processor completes the last instruction of the job;
    • • Execution time: the time needed by the processor to execute the job without interruption;
    • • Completion time: the interval of time between the job start time and the job finishing time;
    • • Response time: the interval of time between the job activation time and the job finishing time;
    • • Lateness: the difference between the job finishing time and its absolute deadline;
    • • Current slack: the difference between the job absolute deadline and its predicted worst-case finishing time.
  • Typical derived parameters that can be computed on a scheduled task are:
    • • Maximum completion time: the maximum completion time among all possible jobs.
    • • Maximum response time: the maximum response time among all possible jobs.
    • • Maximum lateness: the maximum lateness among all possible jobs.
    • • Start time jitter: the maximum deviation between the starts times of consecutive jobs.
    • • Finishing time jitter: the maximum deviation between the finishing times of consecutive jobs.
    • • Completion time jitter (or Input-Output jitter): the maximum deviation between the completion times of consecutive jobs.
  • Typical exceptions that can be detected during task execution are:
    • • Deadline miss: a condition in which, at the current time t, the job is active and t is greater than the job absolute deadline.
    • • Overrun: a condition in which a job requests more computation time than expected in a given interval of time. An execution overrun occurs when a job exceeds its expected worst-case execution time. An activation overrun occurs when a sporadic job is activated before its expected minimum interarrival time. A job overrun may not necessarily cause a deadline miss.

Common Acronyms

• RM: Rate Monotonic
• DM: Deadline Monotonic
• FPS: Fixed Priority Scheduling
• TTP: Time-Triggered Protocol
• EDF: Earliest Deadline First
• LLF: Least Laxity First
• PIP: Priority Inheritance Protocol
• PCP: Priority Ceiling Protocol
• SRP: Stack Resource Policy
• IPCP: Immediate Priority Ceiling Protocol
• RTA: Response Time Analysis
• PDC: Processor Demand Criterion
• dbf: demand bound function
• TBS: Total Bandwidth Server
• CBS: Constant Bandwidth Server

Common Notation (PDF)