REAL-TIME SYSTEMS,
ARCHITECTURE,
SCHEDULING, AND
APPLICATION

Edited by Seyed Morteza Babamir










Real-Time Systems, Architecture, Scheduling, and Application
Edited by Seyed Morteza Babamir


Published by InTech
Janeza Trdine 9, 51000 Rijeka, Croatia

Copyright © 2012 InTech
All chapters are Open Access distributed under the Creative Commons Attribution 3.0
license, which allows users to download, copy and build upon published articles even for
commercial purposes, as long as the author and publisher are properly credited, which
ensures maximum dissemination and a wider impact of our publications. After this work
has been published by InTech, authors have the right to republish it, in whole or part, in
any publication of which they are the author, and to make other personal use of the
work. Any republication, referencing or personal use of the work must explicitly identify

the original source.

As for readers, this license allows users to download, copy and build upon published
chapters even for commercial purposes, as long as the author and publisher are properly
credited, which ensures maximum dissemination and a wider impact of our publications.

Notice
Statements and opinions expressed in the chapters are these of the individual contributors
and not necessarily those of the editors or publisher. No responsibility is accepted for the
accuracy of information contained in the published chapters. The publisher assumes no
responsibility for any damage or injury to persons or property arising out of the use of any
materials, instructions, methods or ideas contained in the book.

Publishing Process Manager Maja Bozicevic
Technical Editor Teodora Smiljanic
Cover Designer InTech Design Team

First published April, 2012
Printed in Croatia

A free online edition of this book is available at www.intechopen.com
Additional hard copies can be obtained from

Real-Time Systems, Architecture, Scheduling, and Application,
Edited by Seyed Morteza Babamir
p. cm.
ISBN 978-953-51-0510-7









Contents

Preface IX
Part 1 Architectures 1
Chapter 1 Networking Applications for Embedded Systems 3
Sorin Zoican
Chapter 2 Dynamics of System Evolution 23
Ashirul Mubin, Rezwanur Rahman and Daniel Ray
Chapter 3 Schedulability Analysis
of Mode Changes with Arbitrary Deadlines 47
Paulo Martins, I. G. Hidalgo, M. A. Carvalho, A. de Angelis,
V.Timóteo, R. Moraes, E. Ursini and Udo Fritzke Jr
Chapter 4 An Efficient Hierarchical Scheduling
Framework for the Automotive Domain 67
Mike Holenderski, Reinder J. Bril and Johan J. Lukkien
Part 2 Specification and Verification 95
Chapter 5 Specification and Validation
of Real-Time Systems Using UML Sequence Diagrams 97
Zbigniew Huzar and Anita Walkowiak
Chapter 6 Construction of Real-Time
Oracle Using Timed Automata 129
Seyed Morteza Babamir and Mehdi Borhani Dehkordi
Part 3 Scheduling 147
Chapter 7 Handling Overload Conditions in Real-Time Systems 149
Giorgio C. Buttazzo

VI Contents

Chapter 8 Real-Time Concurrency Control Protocol
Based on Accessing Temporal Data 173
Qilong Han
Chapter 9 Quality of Service Scheduling
in the Firm Real-Time Systems 191
Audrey Queudet-Marchand and Maryline Chetto
Part 4 Real World Applications 211
Chapter 10 Linearly Time Efficiency
in Unattended Wireless Sensor Networks 213
Faezeh Sadat Babamir and Fattaneh Bayat Babolghani
Chapter 11 Real-Time Algorithms
of Object Detection Using Classifiers 227
Roman Juránek, Pavel Zemˇcík and Michal Hradiš
Chapter 12 Energy Consumption Analysis
of Routing Protocols in Mobile Ad Hoc Networks 249
Ali Norouzi and A. Halim Zaim
Chapter 13 Real-Time Motion Processing
Estimation Methods in Embedded Systems 265
Guillermo Botella and Diego González
Chapter 14 Real Time Radio Frequency Exposure
for Bio-Physical Data Acquisition 293
Alessandra Paffi, Francesca Apollonio, Guglielmo d’Inzeo,
Giorgio A. Lovisolo and Micaela Liberti
Chapter 15 Real–Time Low–Latency Estimation
of the Blinking and EOG Signals 313
Robert Krupi´nski and Przemysław Mazurek










Preface

Real-Time Systems are computing systems that must meet their temporal specification.
In computer science, real-time or reactive computing is the study of hardware and
software systems that are subject to a real-time constraint called deadline, which the
system should respect it in its response to events. Real-time systems, in fact, must
guarantee response within strict time constraints. Real-time systems often appear as
critical systems such as mission critical ones. The anti-lock brakes system on a car, for
instance, is a real-time computing system where the real-time constraint is the brakes
release time to prevent the wheel from locking. Real-time software may use
synchronous programming languages, real-time operating systems and real-time
networks providing essential frameworks for constructing real-time software
applications.
Since correctness of a real-time operation depends not only on its logical correctness
but also on the time in which the operation is carried out, real-time systems are
classified by three types of deadlines: (1) Hard where missing a deadline leads to total
system failure, (2) Firm where missing a deadline is tolerable, but it may degrade
quality of system services and (3) Soft where deadlines are tolerable to be half
extended. Therefore, the goal of a hard real-time system is to ensure that all deadlines
are met; however, that of a soft real-time system is to ensure that a deadline is nearly
met or a subset of deadlines is met. Maximizing the number of met deadlines or
maximizing the number of met deadlines for high priority tasks and minimizing the
lateness of tasks are the concerned goals in the soft real-time systems. Embedded

systems like car engine control system, medical systems (such as heart pacemakers),
industrial process controllers, video game systems and vector graphics are hard real-
time systems having hard requirements. A car engine control system, for instance, is a
hard real-time system where a delayed signal may cause engine failure or damage.
Multitasking systems are another type of real-time systems where the scheduling
policies are a matter of concern. Typical policies are Priority driven or Preemptive
scheduling, Earliest Deadline First and Overlay scheduling, such as Adaptive Partition
Scheduling.
This book stresses architecture, scheduling, specification and verification and real
world applications of real-time systems. It includes a cross-fertilization of ideas and
concepts between the academic and industrial worlds. The book starts with a section
X Preface

(Chapters 1 to 4) on real-time architectures and continues with a section (Chapters 5
and 6) on specification and verification of real-time systems, a section on real-time
scheduling algorithms (Chapters 7 to 9) and ends with a section (Chapters 10 to 15) on
some real world application of real-time systems.
Section 1 consisting of Chapters 1 to 4 deals with architectures of real-time systems.
Chapter 1 presents realizing the networking applications by means of DSP
microcomputer architecture (Blackfin microcomputer) supported by an operating
system kernel (Visual DSP Kernel) and lightweight IP protocol stack (LWIP suite).
Moreover, the chapter provides the frameworks for telecommunications applications
development and for performance evaluation. A VoIP (Voice over IP) system, as a
complex networking application example, is illustrated based on adaptive multi-rate
codec.
Chapter 2 discusses some development efforts to identify general terms and metrics
that are necessary to track a system’s upcoming evolutionary phases. It presents
higher-level analyses of these metrics by examples of several years of systems
development track history and in multiple projects. Based on observations, it tries to
derive a preliminary methodology to formulate system dynamics towards their

evolution.
Chapter 3 elaborates concept of mode and includes a number of current views of
modes and addresses previous work on modes in real-time systems. It extends the
current schedulability analysis associated with mode changes in static priority
preemptive based scheduling. It derives analysis that includes tasks executing across a
mode change with deadlines larger than their period.
Chapter 4 addresses the problem of providing temporal isolation to components in an
integrated system. Temporal isolation allows to develop and verify the components
independently and concurrently and then to integrate them into a system. To provide
true temporal isolation when components execute on a shared processor, this chapter
tries to address this problem by means of a hierarchical scheduling framework (HSF).
HSF provides the means for the integration of independently developed and analyzed
components into a predictable real-time system. A component is defined by a set of
tasks, a local scheduler and a server defining the component’s time budget (i.e. its
share of the processing time) and its replenishment policy.
Section 2 consisting of Chapters 5 and 6 discusses specification and verification issues
in real-time systems. Chapter 5 deals with specification and verification in UML
known as a semiformal language. The chapter presents a formal interpretation of a set
of sequence diagrams with time constraints. The formal interpretation is used to
constructing programming tools for supporting validation of systems behavior
specification and prototyping of the systems. The chapter demonstrates how the set of
scenarios specifying system behavior may be derived from the set of sequence
diagrams and how this set may be analyzed against its consistency and completeness.
Preface XI

Also, this chapter proposes an approach to specify real-time systems having some
features. To this end, it extends the UML sequence diagrams with new kinds of
stereotypes and the notion of monitoring scenarios is introduced. Monitoring
scenarios are also specified by sequence diagrams used to define liveness and safety
properties.

Chapter 6 provides a method for specifying and stating real-time software using Timed
Automata and Real-time Logic respectively. Then, the chapter deals with obtaining the
safety constraints from reachability graph of Timed Automata extracted from the
problem specification and then the constraints are stated in Real-time Logic
propositions. These propositions showing safety constraints are used for verification of
the system behavior. To show the effectiveness of the proposed method, the chapter
sets it forth for a real-time system called Rail Road Crossing Control. This chapter also
includes a brief explanation of Timed Automata and Real-time Logic and a method is
presented to simulate Timed Automata in Real-time logic.
Section 3 consisting of Chapters 7 to 9 deals with scheduling discussion in real-time
systems. Chapter 7 addresses the problem of handling overload conditions in real-time
systems. The conditions are critical situations in which the computational demand
requested by some application exceeds the processor capacity. If not properly handled,
an overload can cause sudden performance degradation or a system crash. The
chapter, in fact, aims to claim that a real-time system should be designed to anticipate
and tolerate unexpected overload situations.
Chapter 8 discusses concurrency control method where transactions access real-time
data. The chapter first reviews concurrency control protocols proposed in real-time
database systems and describes some concurrency control algorithms for accessing
temporal data. Then, it deals with analysing validity of active real-time systems and
effects real-time data on the concurrency control. Based on characteristics of temporal
data, a concurrency control algorithm called “real-time concurrency control algorithm
based on Data-deadline” is put forward.
Chapters 9 discusses hard real-time paradigm. Most scheduling algorithms developed
for soft and firm real-time systems and they lack the ability to enforce constraints on
the upper limit of deadline misses. However, without such enforcement, violation of
time constraint may occur. If consecutive instances of a task fail to complete before
their deadlines, the system will eventually fail. Although firm deadlines can
occasionally be missed, there is normally an upper limit on the number of misses
within a defined interval. The hard real-time paradigm is well established and it has

received considerable attention by researchers and practitioners within academia and
industry.
Section 4 consisting of chapters 10 to 15 proposes applications of real-time systems.
Chapter 10 proposes the security issue in Unmanned Wireless Sensor Networks
(UWSNs) as an application of real-time systems. Such networks should collect small
XII Preface

size and secure data in real-time manner. However, since sensor nodes are small and
low power with low storage, classical algorithms maybe inapplicable and so they
cannot guarantee the security of the data. This problem is very critical in the new
generation of WSNs called UWSNs. Moreover, since disconnected networks in
UWSNs are established in critical or military environments, sink or collector sensors
are unable to gather data in real-time manner. Also, the network may be leaved
unattended and may periodically be visited. This issue is subject to some threats such
as discovering and compromising sensor nodes by adversary without detection or
injection of some invalid data to the network. In such setting the main challenge is
giving an assurance that data survive for long time. This chapter aims to propose a
scheme that shares generated data and encode them to provide confidentiality and
integrity.
Chapter 11 proposes an application of image processing where ensemble statistical
binary classifiers whose function is to make a binary decision on whether an image
region is an object of interest or not. The methods of interest include mainly the
AdaBoost method whose original purpose was to fuse a small number of relatively
well working so-called weak classifiers into one better working, so-called strong
classifier. This approach was further developed into an approach that instead of a
small number of relatively well working weak classifiers took into account a large
number of simple functions and selected a suitable weak classifiers automatically from
these functions. The AdaBoost approach has been further refined and modified to
WaldBoost which was based on Wald’s sequential decision making combined with
AdaBoost.

Chapter 12 proposes the application of energy consumption and performance
evaluation of protocols in an ad hoc network. This chapter is a research where mobile
ad hoc networks are described and some routing protocols are explained. During
simulation, different results are given by changing the selected parameters. In this
chapter, mobile ad Hoc networks are described and some of important routing
protocols are studied. The results obtained from the assessment and comparisons on
energy consumption are shown for some protocols. Based on obtained results, among
others, two protocols show better performance than other.
Chapter 13 proposes the application of real-time motion estimation. Motion estimation
is a low-level vision task managing a number of applications like sport tracking,
surveillance, security, industrial inspection, robotics, navigation and optics. This
chapter introduces different motion estimation systems and their implementation
when real-time is required. Three systems regarding low-level and midlevel vision
domain are explained. Three different case studies of real-time optical flow systems
developed by the authors are presented. Then, the analysis of performance and
resources consumed by each one of three real-time implementations are discussed.
Chapter 14 focuses on description of exposure systems used for data acquisition that is
exposure to radiofrequency electromagnetic fields in bio-electromagnetic
Preface XIII

investigations. Such systems are referred to as real-time and able to generate and
control electromagnetic field and are suitable to be used in experiments where data
acquisition has to be carried out simultaneously with the exposure. In biomedicine, the
real-time concept is applied to both fast calculation of some parameters of biomedical
and the experimental acquisition of physiological data simultaneously. In this chapter,
real-time exposure systems are used to acquire fast biological responses, in
milliseconds in order to study possible health effects due to electromagnetic exposure.
The aim of this chapter is to merge a well-assessed design procedure of
radiofrequency exposure systems with the requirements emerging from real-time
investigations. It is provided that how to adapt the general rules for exposure system

design to real-time systems.
Finally, Chapter 15 proposes a real-time application in fast movement of eye called
saccade. It discusses a wavelets-based technique for the estimation of blinking and
saccade time moments, using continuous wavelet transformation. The estimation of
the blink and Electrooculography bio-signals is important for the real-time human–
computer interaction systems. This chapter is proposed because: (1) previous work
related to the optimization approach using the blinking and eye movement model was
not well fitted for the real-time processing and (2) computation requirements are high.
The reduction of computation time is obtained by the selection of the more efficient
evolutionary operators and it is reduced by reduction of the number of processed
samples. In this chapter, performance analyses of the algorithm and latency behaviour
are considered.

Seyed Morteza Babamir
Assistant Professor of University of Kashan, Kashan,
Iran

Part 1
Architectures