Real-time Systems Scheduling 1 E-Book
139,99 €
Mehr erfahren.
- Herausgeber: John Wiley & Sons
- Kategorie: Wissenschaft und neue Technologien
- Serie: ISTE
- Sprache: Englisch
Real-time systems are used in a wide range of applications, including control, sensing, multimedia, etc. Scheduling is a central problem for these computing/communication systems since responsible of software execution in a timely manner. This book provides state of knowledge in this domain with special emphasis on the key results obtained within the last decade. This book addresses foundations as well as the latest advances and findings in Real-Time Scheduling, giving all references to important papers. But nevertheless the chapters will be short and not overloaded with confusing details. Coverage includes scheduling approaches for mono-core as well as multi-core platforms, dependent tasks, networks, and notably very tremendous recent advances in scheduling of energy constrained embedded systems. Other sophisticated issues such as feedback control scheduling and timing analysis of critical applications are also addressed. This volume can serve as a textbook for courses on the topic in bachelor and in more advanced master programs. It also provides a reference for computer scientists and engineers involved in the design or the development of Cyber-Physical Systems which require up-to-date real-time scheduling solutions.
Sie lesen das E-Book in den Legimi-Apps auf:
Seitenzahl: 351
Veröffentlichungsjahr: 2014
Ähnliche
Contents
Preface
List of Figures
List of Tables
1 Introduction to Real-Time Scheduling
1.1. Real-time systems
1.2. Material architectures
1.3. Operating systems
1.4. Scheduling
1.5. Real-time application modeling and analysis
1.6. System architecture and schedulability
2 Uniprocessor Architecture Solutions
2.1. Introduction
2.2. Characterization of a scheduling problem
2.3. Scheduling algorithms/optimality
2.4. Busy periods and worst-case scenarios
2.5. Feasibility conditions
2.6. Sensitivity analysis
2.7. Conclusion
2.8. Bibliography
3 Multiprocessor Architecture Solutions
3.1. Introduction
3.2. Scheduler classification
3.3. Properties of schedulers
3.4. Partitioned scheduling
3.5. Global scheduling
3.6. Conclusion
3.7. Bibliography
4 Synchronizations: Shared Resource Access Protocols
4.1. Introduction
4.2. Terminology and notations
4.3. Synchronization problems
4.4. Calculating the blocking factor
4.5. Conclusion
4.6. Bibliography
5 Estimation of Execution Time and Delays
5.1. Worst-case execution time analysis: an example
5.2. Going further
5.3. Conclusion
5.4. Bibliography
6 Optimization of Energy Consumption
6.1. Introduction
6.2. State of the art
6.3. Modeling consumption
6.4. Low consumption scheduling
6.5. Experimental results
6.6. Conclusion
6.7. Bibliography
List of Authors
Index
Summary of Volume 2
First published 2014 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc.
Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:
ISTE Ltd
27-37 St George’s Road
London SW19 4EU
UK
www.iste.co.uk
John Wiley & Sons, Inc.
111 River Street
Hoboken, NJ 07030
USA
www.wiley.com
© ISTE Ltd 2014
The rights of Maryline Chetto to be identified as the author of this work have been asserted by her in accordance with the Copyright, Designs and Patents Act 1988.
Library of Congress Control Number: 2014946161
British Library Cataloguing-in-Publication DataA CIP record for this book is available from the British LibraryISBN 978-1-84821-665-5
Preface
We refer to a system as real-time when it has to meet deadlines when reacting to stimuli produced by an external environment. Punctuality therefore constitutes the most important quality of a real-time computer system, which, moreover, distinguishes it from conventional computer systems. We refer to a system as embedded when it is physically integrated into a physical device whose control and command it ensures, which have a particular impact on its sizing and the selection of its components.
The rapid evolution of microelectronic techniques and communication infrastructures in recent years has led to the emergence of often-miniaturized interconnected embedded systems (wireless nodes processing data coming from sensors), leading to the birth of the concept of the “Internet of things”. The real-time qualifier therefore remains relevant for all these autonomous and intelligent objects as it was in the 1970s with the advent of microcomputers, when this qualifier was restricted to industrial process controlling systems.
The large variety of appliances in which real-time systems are now integrated requires increasingly strict constraints to be taken into account in terms of physical size, computational power, memory capacity, energy storage capacity and so on, in their design. It is therefore in this direction that research efforts have turned for several years.
Every piece of software with real-time application is composed of tasks, programs whose execution requires a concurrent access to shared resources limited in number (processor, memory, communication medium). This raises the central issue of scheduling whose solution leads to a planning of tasks that respects the time constraints.
Since the early 1970s, in particular following the publication of the crucial article by Liu and Layland, research activity in the field of real-time scheduling, both through its theoretical results and integration in operating systems, has allowed us to overcome numerous technological barriers.
Real-Time Systems Scheduling constitutes a learning support regarding real-time scheduling intended for instructors, master’s degree students and engineering students. It also aims to describe the latest major progress in research and development for scientists and engineers. The book groups together around 30 years of expertise from French and Belgian universities specialized in real-time scheduling. It was originally published in French and has now been translated into English.
This book is composed of two volumes with a total of 13 chapters.
Volume 1 entitled Fundamentals is composed of six chapters and should be of interest as a general course on scheduling in real-time systems. Reading the chapters in order, from 1 through to 6, is recommended but not necessary. Volume 1 is structured as follows: Chapter 1 constitutes a conceptual introduction to real-time scheduling. Chapters 2 and 3, respectively, deal with uniprocessor and multiprocessor real-time scheduling. Chapter 4 discusses results on scheduling tasks with resource requirements. Chapter 5 relates to the scheduling issue in energy-constrained systems. Chapter 6 presents the techniques of computing the worst-case execution time (WCET) for tasks.
Volume 2 entitled Focuses is composed of seven chapters. This volume aims at collecting knowledge on specific topics and discussing the recent advances for some of them. After reading Chapter 1 of Volume 1, a reader can move to any chapters of Volume 2 in any order. Volume 2 is structured as follows: Chapter 1 highlights the newer scheduling issues raised by the so-called energy-autonomous real-time systems. In Chapter 2, the authors consider a probabilistic modelization of the WCET in order to tackle the scheduling problem. In Chapter 3, the authors show how automatic control can benefit real-time scheduling. Chapter 4 deals with the synchronous approach for scheduling. In Chapter 5, the authors focus on the optimization of the Quality-of-Service in routed networks. Chapter 6 is devoted to the scheduling of messages in industrial networks. Finally, Chapter 7 pertains specifically to resolution techniques used in avionic networks such as AFDX.
Maryline CHETTO
July 2014
List of Figures
List ofTables
1
Introduction to Real-time Scheduling
Emmanuel Grolleau
The aim of this chapter is to introduce real-time scheduling. To do this, after a presentation of the context, we focus on material and software architectures commonly employed in the programming of real-time systems. Next, from a few examples of programs, classical task models are introduced. The techniques implemented to validate these models are developed throughout the chapters of this book.
1.1. Real-time systems
Real-time systems are very extensively used: from wide-consumption technological products (smartphones, games) to terrestrial transport systems (trains and cars) as well as aerial (aeroplanes) and spatial (satellites, shuttles and rockets) transport systems, through non-embedded critical systems such as power plant control, factory machinery control, or bank transaction systems. These are computer programs subject to temporal constraints. Non-compliance with the temporal constraints can lead to a discomfort of use for some programs referred to as soft real-time constraint programs (games, vehicle comfort functionalities such as air conditioning), or it can have catastrophic consequences for strict real-time constraint programs (such as the braking system of a vehicle or the control functionality of an aeroplane).
A real-time system can be either embedded or not: an embedded system embeds its own computing hardware and its own energy source. The energy sources can be electrical batteries, motors fed by fuel, ambient energy such as solar power, or even a combination of several sources. Embedded systems are characterized by low energy consumption computing capabilities in favor of autonomy, small size compared to non-embedded computing capabilities in order to reduce the footprint and the weight of the control system.
In the remainder of the chapter, we will call the global entity system, for instance, the control system of a vehicle. A system provides various functionalities, such as, for example in the case of a vehicle, braking, controlling the on-board radio, autonomous parking, and so on. The functionalities are generally ensured, on complex systems, by subsystems, which can be distributed over several CPUs and networks.
The functionalities and systems can be subject to temporal constraints. We can distinguish between local constraints and end-to-end constraints: an end-to-end constraint is typically derived from high-level requirements on the functionalities. A requirement describes what a functionality has to perform (functional requirement), or what properties it has to have (non-functional requirement). Generally, temporal constraints are considered non-functional since they characterize the response time the functionality has to have. A very widespread requirement in critical systems is segregation, which enforces two implementations of a same functionality to use different computing and communication resources.
EXAMPLE 1.1 (Braking and steering control system).– The following example, taken from a vehicle case study, illustrates the concepts of system, functionality, subsystem and requirements.
We consider a subset of the braking and steering correction functionalities on a passenger vehicle. Figure 1.1 represents different CPUs (called ECU for electronic control units in this context) as well as the main sensors and actuators, and the communication bus allowing the calculators to exchange information. The antilock braking system (ABS) functionality consists of measuring the speed of the various wheels and calculating a slip ratio. Above a certain value, the ABS control unit has to act on the hydraulic pressure regulating valve in order to reduce the exerted pressure, thus allowing the skidding wheels to regain traction, and therefore to reduce the braking distance. A non-functional requirement concerning this functionality could be that the maximum delay between the moment when the wheels skid and the moment when the pressure is reduced to be lower than 50 ms. In a simplified view, we could envision that the ABS functionality is performed by the subsystem that is running on the ABS control unit.
Let us now consider the steering correction functionality. This has to take into account the driver’s intent (the angle of the steering wheel), as well as the speed of the vehicle, and can use gyro meters (measuring the angular speed) or an inertial unit (measuring the attitude using the measures of angular speed, heading and acceleration) in order to measure the rotational speed of the vehicle. Depending on the speed of the vehicle, the difference between the command attitude (angle of the steering wheel) and the rotational angle of the vehicle the extra sensory perception (ESP) control unit is able to determine whether the vehicle is in oversteer (the vehicle starts to go into a spin since the rear is drifting) or understeer (the front has a tendency to skid and the vehicle continues forward instead of following the curve). The outputs of the ESP control unit, interpreted by the ABS control unit, are translated as a braking of the front outside wheel in order to compensate an oversteer, or the rear inside wheel for an understeer. We can thus see that the ESP functionality is distributed over several subsystems, running on several ECUs. The ESP can also be subject to end-to-end temporal constraints, which will be translated as local temporal constraints on the ECUs and communication buses involved in the functionality.
Figure 1.1. Distributed system ensuring the braking and steering correction functionalities
Some temporal constraints can be purely local: the pieces of information circulating in a network are typically cut up into frames (series of bytes). Embedded CPUs typically do not have a memory of more than a single received frame. Consequently, a requirement that we could expect to have would be for a CPU to be able to read and memorize a frame before the reception of the next frame, under penalty of losing a frame.
On each subsystem running on a CPU, the requirements are mirrored by temporal constraints. A temporal constraint is a time frame in which a process must always be executed in its entirety.
1.2. Material architectures
From example 1.1, we have an overview of the main material elements composing a real-time system: CPUs, communication networks, sensors and actuators.
1.2.1. CPUs
In this section, we consider central processing units (CPUs) based on a Van Neumann or Harvard architecture, in other words CPUs that separate the memory and calculation units. Most of the CPUs in use since the invention of computing are indeed based on one of these architectures.
A CPU is a processor allowing the execution of programs. A program, while running, has its instructions copied into memory: it then becomes a process. A process can be composed of several algorithms that need to be run in parallel, these are tasks. A task is composed of a series of instructions to be executed sequentially. An instruction can be arithmetical and logical, a conditional or unconditional jump, movements between the memory and the registers, access to an input/output device, etc.
CPUs can be single- or multi-core: each computing core allows the execution of a task at a given time. A process is thus parallelizable since several tasks of the same process can be run simultaneously, on the other hand we generally consider tasks not to be parallelizable. This means that a task cannot simultaneously be run on several cores.
The execution of an instruction consists of loading the instruction from memory, decoding it and running it. The time-stepping of the execution of the instructions is ensured by a clock, used as a time reference called the cycle, in the cores.
If all these operations were executed sequentially, then the processor cores would be underutilized. Indeed, the circuits specialized in the processing of instructions are available during the loading and decoding of the instruction. Moreover, the memory could be slower to respond than the execution time of an instruction. This is called a memory bottleneck, since the processor can be led to wait several cycles before the instruction arrives from memory. CPUs can therefore integrate local optimizations, or have particular architectures allowing, on average, the acceleration of certain processes. For instance, cache memory allows the storage of central memory data in rapid-access memories. These memories are closer to the processor and faster, but are of smaller size than the central memory and can therefore only memorize a part of the data. The working principle is that when the processor wants to read from an address in memory, the cache, if it has stored the content of that address, sends the content to the processor, which then does not have to wait for the central memory. When the requested address is not present in the cache, the cache stores it for an ulterior use. If it is full, a cache-managing strategy has to be used to decide which content will be replaced. This optimization brings, on the architectures on which it is employed, very significant increases in performance. This is due to the locality principle: a program often contains loops and manipulates the same data, consequently when the processor has to load an instruction or a piece of data, it is often to be found in cache memory. On newer architectures, there are several levels of cache memory depending on the size and the speed. Moreover, on multi-core architectures, certain levels of cache memory can be shared by certain cores. In consequence, the parallel execution by several cores has an effect on the shared cache memory.
A CPU can be associated with specific circuits (application specific integrated circuit (ASIC)) allowing it to be relieved from time-costly functions, such as for example polling the arriving data on a communication bus, or computing the attitude (pitch angles, roll and heading) depending on the sensors of an inertial unit.
When an input/output device needs to communicate an event to the processor, as, for example, pressing a key on a keyboard or the arrival of a message on a communication bus, a hardware interrupt is triggered. After processing each instruction, a processor has to check whether a hardware interrupt has occurred. If this is the case, it has to process the interrupt. It stops the current processing, and executes the instructions of an interrupt handler routine.
From a real-time point of view, a CPU is thus a computing resource that runs tasks. The execution of each instruction takes time, expressed in cycles. Though the execution is sequential, numerous factors (material optimizations, interrupts) interfering with the execution of a task complicate the study of the duration of these processes. The field of study of the duration of tasks is called timing analysis.
1.2.2. Communication networks
A communication network is a medium allowing CPUs to communicate by sending each other data. The communication networks used in critical real-time systems have to be able to give guarantees regarding maximum delays in the transmission of messages. We therefore use deterministic networks, generally with a decentralized arbitration (no CPU is indispensable for the network to work). This is the case of a controller area network (CAN), which is a synchronous deterministic network used mainly in vehicles and aeroplanes, or a switched Ethernet such as avionics full duplex (AFDX) employed in civil avionics that enables us to reach high throughputs.
From a general point of view, CPUs connected by communication networks transmit, on a physical level, frames (i.e. a series of bytes). From a real-time point of view, a transmission medium is seen as a frame-transmitting resource, the transmission time of a frame is obtained simply from the throughput and the length of the medium. The main difficulty, from a message transmission point of view, is to take into account the utilization of the shared media (see Chapter 6, Volume 2), or the wait in queues in the case of a switched network (see Chapter 7, Volume 2). We consider that the emission of a frame cannot be interrupted.
With the recent emergence of multi-core and manycore CPUs (we refer to several tens or hundreds of cores as manycores) a new kind of communication network has appeared: networks on chip (NoC). These networks connect computing cores. As it is not physically possible to directly connect all the cores, we could consider that the cores are the vertices of a two-dimensional grid, and that communication media (the NoC) connect a core to its four neighbors. In order to facilitate the integration on a single chip, this grid can have more than two dimensions, and constitute a cube or a hypercube. In this case, the transmitted packets are relatively small in size in order for them to be easily stored in the cores, which will then work as routers transferring the frames from one source core to a destination core.
1.2.3. Sensors and actuators
A sensor is a device capable of reading a physical quantity (temperature, pressure, speed, etc.). There is a very large variety of sensors, their common feature is that in order to interface with a computer system, they have to offer at least a digital or analog interface, or have a communication bus interface. A digital or analog interface uses an electric quantity to represent the measured physical quantity. A communication bus interface allows the sensor to transmit frames containing measures in a binary format.
An actuator is a device which allows us to control a physical element (flight control surfaces, solenoid valves, engines, etc.). Just like a sensor, it has to have a digital or analog interface or a bus.
It may be noted that digital and analog inputs as well as buses that can be found on CPUs can be of two types: polling and interrupt-based. Polling inputs allow a program to read the binary representation of an electrical signal in input. Interrupt-based inputs trigger, on certain events, a hardware interrupt on the CPU, which will then have to execute an interrupt handler routine.
1.3. Operating systems
To facilitate the exploitation of material resources (CPUs, networks, memories, etc.) by an application, the operating system provides services and primitives that ease the programming. The aim of this section is to present the general aspects of operating systems and to characterize what makes an operating system real-time. It also aims to present the primitives that can be found in real-time applications.
1.3.1. Generalities
An operating system can be broken down into three layers:
Since this book deals with real-time scheduling, we will focus, in the following, on the functioning of the operating system kernel. A kernel provides the necessary primitives for the creation of tasks and for communication and synchronization. If it is a multi-process kernel, it also provides the corresponding primitives for the processes. Kernels in embedded systems, which represent a large part of critical real-time systems deal, for the most, with only one process, and consequently, we will mainly focus on the handling of tasks.
1.3.2. Real-time operating systems
Operating systems can be generalist or real-time. A generalist operating system prioritizes flexibility, ease of use and average processing speed. It has to be noted that accelerating the average processing speed using local optimizations can cause instances of tasks whose processing time would be longer than without any optimization. For instance, the principle of instruction preloading will preload and pre-decode the next instructions during the processing of an instruction. However, if the next instruction depends on the result of an operation (conditional jump), the next preloaded instruction could correspond to the wrong operational branch. In this case, which happens rarely for well-designed prediction algorithms, the length of the instructions in time without any optimization could be shorter than the length of instructions with preloading optimization. Moreover, the determinism of the processing time is very much affected by the optimizations. This is the same for devices that prioritize flexibility (for example virtual memory, with the exchange mechanism between central memory and mass storage), or ease of use (for example the automatic update which will use up resources at moments difficult or impossible to predict).
The two most widespread generalist operating systems are Microsoft Windows and Unix. Both of these occupy a large disk space (around a gigabyte) and have a significant (several hundreds of megabytes) memory footprint (central memory usage).
Embedded CPUs, usually having a small amount of memory (a few kilobytes to a few megabytes of central memory) and a limited computing power (a few megahertz to a few hundreds of megahertz), for a mass storage round one gigabyte, real-time operating systems (RTOS) prioritize memory footprint and simplicity. Moreover, as we will see throughout this book, real-time is not fast, it is deterministic. Indeed, with a few exceptions, the temporal validation methods are conservative: when the system is validated, it is validated for the worst case. Indeed, an important metric characterizing an RTOS is kernel latency: this duration describes the worst delay in time that can elapse between a task-release event and when it is effectively being taken into account by the kernel. The internal architecture of an RTOS is designed to minimize this delay; to the detriment of the average processing speed.
There is a very large number of RTOSs and numerous standards defining RTOSs, implemented in various operating systems. We can point to the portable operating system interface (POSIX) standard pthreads 1003.1, which defines generalist RTOSs, the Ada standard that is very well adapted to very critical applications such as those which can be found in military and aerospace avionics, the OSEK standard developed by a consortium of European vehicle manufacturers, characterized by a very small memory footprint and a low increase in cost, and proprietary RTOSs such as VxWorks of WindRiver, or real-time executive for multiprocessor systems (RTEMS), which define their own primitives and provide a POSIX 1003.1-compliant interface.
1.3.3. Primitives provided by the kernel
Regardless of the generalist or real-time operating system, a certain number of primitives are provided for the management of parallelism. Since most RTOSs are monoprocess, we will focus on the management of tasks. Figure 1.2 represents the possible states of a task such as they are perceived by the kernel. Only the ready tasks compete for the acquisition of computing resources, in other words for a core of a CPU.
Figure 1.2. Possible states for a task
1.4. Scheduling
Scheduling, given a set of ready tasks, consists of choosing, on each core, at most one task to run.
1.4.1. Online and offline scheduling
Scheduling is based on a strategy of choice, which can be static or be based on an algorithm.
In the static case, we use a table in which we have predefined the allocation times of the tasks to the cores, the scheduler is then called a sequencer since it merely follows an established sequence; we then refer to offline scheduling. This type of scheduling is only possible when the times the tasks will be ready are known beforehand, in other words the sequence-creation algorithm has to be clairvoyant.
When we use a selection algorithm on the task(s) to be executed based on the immediate state of the system, we refer to online scheduling. Online schedulers consider the set of ready tasks at certain moments of time in order to choose between them the allocation of the computing resources. No matter the method used to design the online strategy, it has to be resource-efficient. Indeed, the time spent by the computing resources for the scheduler to execute its strategy is called the processor overhead, since it does not directly contribute to the execution of the functionalities of the system. The computational complexity of schedulers must be linear, or even quadratic, in the worst case, depending on the number of tasks.
The moments when the scheduler has to make a choice correspond either to the moments when a task changes state (wakeup, blocking), in other words when there is a change of state in a task of the system, or to moments that are fixed by a time quantum. In the second case, the scheduler is activated at each time quantum and makes a decision depending on the immediate state of the tasks.
In RTOSs, most proposed scheduling algorithms are based on priorities. As we will see later, these priorities can be fixed-task (assigned to a task once and for all its jobs), fixed-job (assigned to a job once it is released) or dynamic.
A scheduling sequence can be represented on a Gantt diagram, such as in Figure 1.3. The time is in abscissa, each line represents the execution of a task, an ascending arrow represents the activation of a task whereas a descending arrow represents a deadline. In this figure, we consider two tasks τ1 and τ2 executed once on a processor, with respective durations of 2 and 3 units of time. τ1 is woken up at time 1 and τ2 at time 0. We assume that the strategy of the scheduler is based on priorities, and that τ1 is of higher priority than τ2. Thus, at time 0, only τ1 is ready and is given a processor. When τ1 is woken up, the scheduler preempts τ2, since the set of ready tasks is {τ1, τ2} with τ1 of higher priority than τ2. At the termination of τ1, the only ready task is τ2, it therefore obtains the processor. At time 4, τ2 misses its deadline.
Figure 1.3. Gantt diagram
1.4.2. Task characterization
In a real-time system, most processing is recurrent, or even periodic. Each recurrent execution is called an instance or a job. Thus, in example 1.1, the reading of the gyro meter will presumably be periodic. Ideally, this would happen continuously, but since we are using a processor, our only choice is to discretize the process. The same applies to most of the input rhythms of the system, which are either periodic when the system needs to scan the state of a sensor, or triggered by the arrival of a message on the network or by another external event.
Each job of each task executes instructions, and consequently, uses up time on the computing resources. A task is therefore characterized by the duration of its jobs. Given that there could be loops with a number of iterations depending on the data, conditional paths, more or less efficient material optimizations determined by the execution time or the data values, etc., the duration of the jobs of a task cannot be considered fixed. In a real-time context, it will be characterized by a worst-case execution time (WCET). The techniques used to determine the WCET are presented in Chapter 5.
Compliance with time-related requirements is mirrored on tasks by deadlines. In most models, each job is given a deadline that it has to comply with. Since every task can generate a potentially infinite number of jobs, each with a deadline, the temporal constraints are generally represented on a task τi by a relative deadline, often denoted by Di. The relative deadline represents the size of the temporal window in which a job has to be executed from its activation.
Following their activation types, we distinguish between three kinds of tasks:
When an external event is periodic, before declaring a task triggered by this event as periodic, it has to be ensured that the timebase (material clock) used by every periodic task of the system is identical. Indeed, let us assume that a task run by a CPU is activated by a periodic message coming from another distant CPU, even if the sending of the message is completely regular from the point of view of the distant CPU, there is a drift, even a small one, which undermines the periodicity hypothesis. Indeed, as we go along, the effective release times of the task woken up by these messages will be more and more offset with respect to a periodic release.
The typical implementation of a periodic task on a RTOS is given in Figure 1.4, and that of a sporadic or aperiodic task is given in Figure 1.5. In the sporadic or aperiodic case, the trigger event is typically indicated by the occurrence of a hardware interrupt, for example, the arrival of a frame on an input/output bus or on a communication network. The distinction between sporadic and aperiodic comes from what characterizes the event expected by the wake-up of the task. In certain cases, the trigger event is characterized by a minimal delay between two successive activations. In case that the minimal delay between two successive activations cannot be determined, the task is aperiodic.
Figure 1.4.Typical implementation of a periodic task
In the case of periodic tasks, the initial release time is usually known, and we then refer to concrete tasks, whereas in the sporadic and aperiodic cases, the trigger event often being external, it is difficult to know in advance the moment when the first job is triggered. We then refer to non-concrete tasks.
Figure 1.5.Typical implementation of a sporadic task and an aperiodic task
For periodic or sporadic tasks, the relationship between period and relative deadline is of great importance in the temporal study of the systems. We therefore distinguish between three cases for a task τi:
– Constrained deadline (i, Di < Ti): the deadline of a job precedes the activation of the next job. In this case and in the implicit deadline case+, two jobs of the task τi can never be in competition for the computing resources.
– Arbitrary deadline (τ i, Di > Ti): jobs of τi can potentially be in competition for a processor. However, in general, we consider that a job has to be completely terminated before the next job can be executed. We refer, in this case, to the nonreentrance of tasks. Most RTOSs implicitly offer the principle of non-reentrance. For example, on Figure 1.4, a job, which corresponds to an iteration of the “While true” loop, cannot be executed before the end of the preceding job (iteration).
1.4.3. Criticality
In most temporal analyses, tasks are considered to have strict constraints, in other words in no circumstance can a deadline be violated. Various studies have, however, been carried out on systems with fewer constraint tasks. For instance, the model (m, k) – firm considers that m deadlines out of k have to be respected. More recently, the multi-criticality model was inspired by the criticality levels in civil avionics proposed by the DO178B/C. These levels of criticality represent the cohabitation of more or less strict-constraint tasks in a system of tasks.
1.4.4. Metrics related to scheduling
The main problem dealt with in the temporal study of an application concerns the deadline-compliance of the tasks, but several other metrics are of interest. In order to illustrate a few typical metrics used to describe a scheduling process, Figure 1.6 represents a fixed-task priority scheduling (the priority is assigned to the tasks, each job of a task is given the priority of the task). Considering the system of tasks, S, is composed of three periodic tasks with implicit deadlines (deadline equal to the period) τ1, τ2, τ3 with respective WCETs of 3, 3, 3, with respective periods of 6, 9, 18 and with respective release times of 0, 1, 2. Given a system execution log, which can be called a scheduling sequence, we could characterize for example:
