BN.com Gift Guide

Real-Time Systems: Scheduling, Analysis, and Verification / Edition 1

Hardcover (Print)
Buy New
Buy New from BN.com
$148.45
Used and New from Other Sellers
Used and New from Other Sellers
from $63.60
Usually ships in 1-2 business days
(Save 63%)
Other sellers (Hardcover)
  • All (14) from $63.60   
  • New (7) from $111.45   
  • Used (7) from $63.60   

Overview

The first book to provide a comprehensive overview of the subject rather than a collection of papers.

  • The author is a recognized authority in the field as well as an outstanding teacher lauded for his ability to convey these concepts clearly to many different audiences.
  • A handy reference for practitioners in the field.
Read More Show Less

Editorial Reviews

From the Publisher
"The author provides a substantial, up-to-date overview of the verification and validation process…" (Computer Magazine, November 2004)

"The unifying discussion on the formal analysis and verification methods are especially valuable and enlightening, both for graduate students and researchers." (International Journal of General Systems, December 2003)

From The Critics
This textbook introduces several approaches to the formal analysis and verification of real-time systems. Cheng (University of Houston) describes model checking of finite state system, visual formalism with statecharts, real-time logic, the Modechart specification, verification using time automata, and timed Petri nets. The final three chapters deal with rule-based expert systems. Annotation c. Book News, Inc., Portland, OR
Read More Show Less

Product Details

  • ISBN-13: 9780471184065
  • Publisher: Wiley
  • Publication date: 8/12/2002
  • Edition description: New Edition
  • Edition number: 1
  • Pages: 552
  • Product dimensions: 6.52 (w) x 9.47 (h) x 1.70 (d)

Meet the Author

ALBERT M. K. CHENG, PhD, received his doctorate in computer science from the University of Texas at Austin, where he held a GTE Foundation Doctoral Fellowship. He is currently an associate professor in the department of computer science at the University of Houston, where he is the founding director of the Real-Time Systems Laboratory. He is the author and coauthor of over sixty refereed publications, and has received numerous awards, including the NSF Career award. He has served as a technical consultant for several organizations, including IBM, and has served on the program committees of many conferences.

Read More Show Less

Read an Excerpt

Real-Time Systems

Scheduling, Analysis, and Verification
By Albert M. K. Cheng

John Wiley & Sons

ISBN: 0-471-18406-3


Chapter One

INTRODUCTION

The correctness of many systems and devices in our modern society depends not only on the effects or results they produce but also on the time at which these results are produced. These real-time systems range from the anti-lock braking controller in automobiles to the vital-sign monitor in hospital intensive-care units. For example, when the driver of a car applies the brake, the anti-lock braking controller analyzes the environment in which the controller is embedded (car speed, road surface, direction of travel) and activates the brake with the appropriate frequency within fractions of a second. Both the result (brake activation) and the time at which the result is produced are important in ensuring the safety of the car, its driver, and passengers.

Recently, computer hardware and software are increasingly embedded in a majority of these real-time systems to monitor and control their operations. These computer systems are called embedded systems, real-time computer systems, or simply real-time systems. Unlike conventional, non-real-time computer systems, real-time computer systems are closely coupled with the environment being monitored and controlled. Examples of real-time systems include computerized versions of the braking controller and the vital-sign monitor, the new generation of airplane and spacecraft avionics, the planned Space Station control software, high-performance network and telephone switching systems, multimedia tools, virtual reality systems, robotic controllers, battery-powered instruments, wireless communication devices (such as cellular phones and PDAs), astronomical telescopes with adaptive-optics systems, and many safety-critical industrial applications. These embedded systems must satisfy stringent timing and reliability constraints in addition to functional correctness requirements.

Figure 1.1 shows a model of a real-time system. A real-time system has a decision component that interacts with the external environment (in which the decision component is embedded) by taking sensor readings and computing control decisions based on sensor readings and stored state information. We can characterize this real-time system model with seven components:

1. A sensor vector [bar.x] [member of] X,

2. A decision vector [bar.y] [member of] Y,

3. A system state vector [bar.s] [member of] S,

4. A set of environmental constraints A,

5. A decision map D, D : S x X [right arrow] S x Y,

6. A set of timing constraints T, and

7. A set of integrity constraints I.

In this model, X is the space of sensor input values, Y is the space of decision values, and S is the space of system state values. Let [bar.x](t) denote the value of the sensor input [bar.x] at time t, and so on.

The environmental constraints A are relations over X, Y, S and are assertions about the effect of a control decision on the external world which in turn affect future sensor input values. Environmental constraints are usually imposed by the physical environment in which the real-time decision system functions.

The decision map D relates [bar.y](t + 1), [bar.s](t + 1) to [bar.x](t), [bar.s](t), that is, given the current system state and sensor input, D determines the next decisions and system state values. Decision maps can be implemented by computer hardware and software components. A decision system need not be centralized, and may consist of a network of coordinating, distributed monitoring/decision-making components.

The decisions specified by D must conform to a set of integrity (safety) constraints I. Integrity constraints are relations over X, S, Y and are assertions that the decision map D must satisfy to ensure safe operation of the physical system under control. The implementation of the decision map D is subject to a set of timing constraints T, which are assertions about how fast the map D has to be performed. In addition, timing constraints exist on the environment (external to the decision system) that must be satisfied for the correct functioning of this environment.

There are two ways to ensure system safety and reliability. One way is to employ engineering (both software and hardware) techniques, such as structured programming principles, to minimize implementation errors and then utilize testing techniques to uncover errors in the implementation. The other way is to use formal analysis and verification techniques to ensure that the implemented system satisfy the required safety constraints under all conditions given a set of assumptions. In a real-time system, we need to not only satisfy stringent timing requirements but also guard against an imperfect execution environment, which may violate pre-runtime design assumptions. The first approach can only increase the confidence level we have on the correctness of the system because testing cannot guarantee that the system is error-free [Dahl, Dijkstra, and Hoare, 1972]. The second approach can guarantee that a verified system always satisfies the checked safety properties, and is the focus of this text.

However, state-of-the-art techniques, which have been demonstrated in pedagogic systems, are often difficult to understand and to apply to realistic systems. Furthermore, it is often difficult to determine how practical a proposed technique is from the large number of mathematical notations used. The objective of this book is to provide a more readable introduction to formal techniques that are practical for actual use. These theoretical foundations are followed by practical exercises in employing these advanced techniques to build, analyze, and verify different modules of real-time systems. Available specification analysis and verification tools are also described to help design and analyze real-time systems.

1.1 WHAT IS TIME?

Time is an essential concept in real-time systems, and keeping time using accurate clocks is thus required to ensure the correct operations of these systems. The master source for time is Paris's International Atomic Time (TAI), an average of several laboratory atomic clocks in the world. Since the earth's rotational rate slows by a few milliseconds each day, another master time source called the Universal Coordinated Time (UTC) performs leap corrections to the time provided by TAI while maintaining TAI's accuracy, making the time length of every natural solar day constant [Allan, Ashby, and Hodge, 1998].

UTC is used as the world time, and UTC time signals are sent from the National Institute of Standards and Technology (NIST) radio station, WWVB, in Fort Collins, Colorado, and other UTC radio stations to specialized receivers. Selected radios, receiver-clocks, some phone-answering systems, and even some VCRs have the capability to receive these UTC signals to maintain accurate clocks. Some computers have receivers to receive these UTC signals and thus the time provided by their internal clocks is as accurate as UTC. Note that depending on the location of the receiver-clock, there is a delay in receiving the UTC signal. For instance, it takes around 5 ms for WWVB's UTC signal to get from Fort Collins to a receiver-clock in my Real-Time Systems Laboratory in Houston, Texas.

For computers whose time is kept by quartz-based computer clocks, we must ensure that these clocks are periodically synchronized such that they maintain a bounded drift relative to UTC. Software or logical clocks can be derived from computer clocks [Lamport, 1978]. In this text, when we refer to wall clock or absolute time, we refer to the standard time provided by a bounded-drift computer clock or UTC. Thus there is a mapping Clock: real time [right arrow] standard clock time.

1.2 SIMULATION

Simulation consists of constructing a model of an existing system to be studied or a system to be built and then executing actions allowed in this model. The model can be a physical entity like a scale clay model of an airplane or a computer representation. A computer model is often less costly than a physical model and can represent a non-computer entity such as an airplane or its components as well as a computer entity such as a computer system or a program. A computer model also can represent a system with both computer and non-computer components like an automobile with embedded computer systems to control its transmission and brakes.

This physical or computer model is called the simulator of the actual system. A simulator can carry out simulated executions of the simulated system and display the outcomes of these executions. A physical model of an airplane in a wind tunnel shows the aerodynamics of the simulated plane that is close to the actual plane. A software simulator on a single-processor system shows the performance of a network of personal computer workstations under a heavy network traffic condition. A software simulator can also be designed to simulate the behavior of an automobile crashing into a concrete barrier, showing its effects on the automobile's simulated occupants. Sometimes a simulator refers to a tool that can be programmed or directed without programming to mimic the events and actions in different systems. This simulator can be either computer-based (software, hardware, or both) or non-computer-based.

Simulation is an inexpensive way to study the behavior of the simulated system and to study different ways to implement the actual system. If we detect behavior or events that are inconsistent with the specification and safety assertions, we can revise the model and thus the actual system to be built. In the case in which we consider several models as possible ways to implement the actual system, we can select the model that best satisfies the specification and safety assertions through the simulation and then implement it as the actual system.

Different levels of details of the actual system, also called the target system, can be modeled and its events simulated by a simulator. This makes it possible to study and observe only the relevant parts of the target system. For example, when designing and simulating the cockpit of an aircraft, we can restrict attention to that particular component by simulating only the cockpit with inputs and outputs to the other aircraft components, without simulating the behavior of the entire aircraft. In the design and simulation of a real-time multimedia communication system, we can simulate the traffic pattern between workstations but need not simulate the low-level signal processing involved in the coding and transmission processes if the performance is not affected by these low-level processes. The ability to simulate a target system at different detail levels or only a subset of its components reduces the resources needed for the simulation and decreases the complexity of the analysis of the simulation.

There are several simulation techniques in use, such as real-time-event simulation and discrete-event simulation. A real-time-event simulator like a physical scale model of an automobile performs its actions in real-time and the observable events are recorded in real-time. An example is the crash testing of the physical model of an automobile. Such a simulator requires recording instruments capable of recording events in real-time. When the physical model is actually an implemented target system, this is no longer a simulation but rather a testing of the actual system, as discussed below.

A discrete-event simulator, on the other hand, uses a logical clock(s) and is usually software-based. The variety of systems that can be represented by such a simulator is not limited by the speed at which the hardware executes the simulator since the simulated actions and events do not occur in real-time. Rather, they take place according to the speed of the simulator hardware and the instructions in the simulator program. Examples include the simulation of a network of computers in a single-processor system or the simulation of a faster microprocessor in a slower processor as in the design of popular next-generation personal computer microprocessors. Here, the appropriate actions and events "occur" at a particular logical time (representing real-time in the target system) depending on previous and current simulated actions and events. Entire books have been written that are devoted to discrete-event simulation.

Variations of simulation include the hybrid simulation approach, in which the simulator works with a partial implementation of the target system by acting as the non-implemented part. As in the case of using only a simulator, the simulator here makes it possible to predict the performance and behavior of the target system once it is completely implemented.

One main disadvantage of simulation as a technique to analyze and verify real-time systems and other systems is that it is not able to model all possible event-action sequences in the target system where the domain of possible sequences of observable events is infinite. Even when this domain is finite, the number of possible events is so large that the most powerful computer resources or physical instruments may not be able to trace through all possible sequences of events in the simulated target system.

1.3 TESTING

Testing is perhaps the oldest technique for detecting errors or problems in implemented software, hardware, or non-computer systems. It consists of executing or operating (in the case of a non-computer system) the system to be tested using a finite set of inputs and then checking to see if the corresponding outputs or behavior are correct with respect to the specifications. To test a real-time system, the values as well as the timing of the inputs are important. Similarly, both the output values and the time at which they are produced must be checked for correctness.

Many approaches have been developed for testing software, hardware, and non-computer systems. The simplest technique is of course to perform an exhaustive test run of the system with every possible input and then to check if the corresponding output is correct. This approach is not practical except for small systems with limited input space. For larger systems, the time needed to test is prohibitively long. For systems with an infinite number of possible inputs, this approach is of course not viable. Since relatively little training is required on the part of the testing personnel, testing has been and will continue to be used extensively in industry.

There are three common techniques for software testing in the current state-of-the-practice: functional testing, structural testing, and code reading.

Continues...


Excerpted from Real-Time Systems by Albert M. K. Cheng Excerpted by permission.
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.

Read More Show Less

Table of Contents

PREFACE.

LIST OF FIGURES.

1 INTRODUCTION.

1.1 What Is Time?

1.2 Simulation.

1.3 Testing.

1.4 Verification.

1.5 Run-Time Monitoring.

1.6 Useful Resources.

2 ANALYSIS AND VERIFICATION OF NON-REAL-TIME SYSTEMS.

2.1 Symbolic Logic.

2.2 Automata and Languages.

2.3 Historical Perspective and Related Work.

2.4 Summary.

Exercises.

3 REAL-TIME SCHEDULING AND SCHEDULABILITY ANALYSIS.

3.1 Determining Computation Time.

3.2 Uniprocessor Scheduling.

3.3 Multiprocessor Scheduling.

3.4 Available Scheduling Tools.

3.5 Available Real-Time Operating Systems.

3.6 Historical Perspective and Related Work.

3.7 Summary.

Exercises.

4 MODEL CHECKING OF FINITE-STATE SYSTEMS.

4.1 System Specification.

4.2 Clarke-Emerson-Sistla Model Checker.

4.3 Extensions to CTL.

4.4 Applications.

4.5 Complete CTL Model Checker in C.

4.6 Symbolic Model Checking.

4.7 Real-Time CTL.

4.8 Available Tools.

4.9 Historical Perspective and Related Work.

4.10 Summary.

Exercises.

5 VISUAL FORMALISM, STATECHARTS, AND STATEMATE.

5.1 Statecharts.

5.2 Activity-Charts.

5.3 Module-Charts.

5.4 STATEMATE.

5.5 Available Tools.

5.6 Historical Perspective and Related Work.

5.7 Summary.

Exercises.

6 REAL-TIME LOGIC, GRAPH-THEORETIC ANALYSIS, AND MODECHART.

6.1 Specification and Safety Assertions.

6.2 Event-Action Model.

6.3 Real-Time Logic.

6.4 Restricted RTL Formulas.

6.5 Checking for Unsatisfiability.

6.6 Efficient Unsatisfiability Check.

6.7 Industrial Example: NASA X-38 Crew Return Vehicle.

6.8 Modechart Specification Language.

6.9 Verifying Timing Properties of Modechart Specifications.

6.10 Available Tools.

6.11 Historical Perspective and Related Work.

6.12 Summary.

Exercises.

7 VERIFICATION USING TIMED AUTOMATA.

7.1 Lynch-Vaandrager Automata-Theoretic Approach.

7.2 Alur-Dill Automata-Theoretic Approach.

7.3 Alur-Dill Region Automaton and Verification.

7.4 Available Tools.

7.5 Historical Perspective and Related Work.

7.6 Summary.

Exercises.

8 TIMED PETRI NETS.

8.1 Untimed Petri Nets.

8.2 Petri Nets with Time Extensions.

8.3 Time ER Nets.

8.4 Properties of High-Level Petri Nets.

8.5 Berthomieu-Diaz Analysis Algorithm for TPNs.

8.6 Milano Group's Approach to HLTPN Analysis.

8.7 Practicality: Available Tools.

8.8 Historical Perspective and Related Work.

8.9 Summary.

Exercises.

9 PROCESS ALGEBRA.

9.1 Untimed Process Algebras.

9.2 Milner's Calculus of Communicating Systems.

9.3 Timed Process Algebras.

9.4 Algebra of Communicating Shared Resources.

9.5 Analysis and Verification.

9.6 Relationships to Other Approaches.

9.7 Available Tools.

9.8 Historical Perspective and Related Work.

9.9 Summary.

Exercises.

10 DESIGN AND ANALYSIS OF PROPOSITIONAL-LOGIC RULE-BASED SYSTEMS.

10.1 Real-Time Decision Systems.

10.2 Real-Time Expert Systems.

10.3 Propositional-Logic Rule-Based Programs: the EQL Language.

10.4 State-Space Representation.

10.5 Computer-Aided Design Tools.

10.6 The Analysis Problem.

10.7 Industrial Example: Analysis of the Cryogenic Hydrogen Pressure Malfunction Procedure of the Space Shuttle Vehicle Pressure Control System.

10.8 The Synthesis Problem.

10.9 Specifying Termination Conditions in Estella.

10.10 Two Industrial Examples.

10.11 The Estella-General Analysis Tool.

10.12 Quantitative Timing Analysis Algorithms.

10.13 Historical Perspective and Related Work.

10.14 Summary.

Exercises.

11 TIMING ANALYSIS OF PREDICATE-LOGIC RULE-BASED SYSTEMS.

11.1 The OPS5 Language.

11.2 Cheng-Tsai Timing Analysis Methodology.

11.3 Cheng-Chen Timing Analysis Methodology.

11.4 Historical Perspective and Related Work.

11.5 Summary.

Exercises.

12 OPTIMIZATION OF RULE-BASED SYSTEMS.

12.1 Introduction.

12.2 Background.

12.3 Basic Definitions.

12.4 Optimization Algorithm.

12.5 Experimental Evaluation.

12.6 Comments on Optimization Methods.

12.7 Historical Perspective and Related Work.

12.8 Summary.

Exercises.

BIBLIOGRAPHY.

INDEX.

Read More Show Less

Customer Reviews

Be the first to write a review
( 0 )
Rating Distribution

5 Star

(0)

4 Star

(0)

3 Star

(0)

2 Star

(0)

1 Star

(0)

Your Rating:

Your Name: Create a Pen Name or

Barnes & Noble.com Review Rules

Our reader reviews allow you to share your comments on titles you liked, or didn't, with others. By submitting an online review, you are representing to Barnes & Noble.com that all information contained in your review is original and accurate in all respects, and that the submission of such content by you and the posting of such content by Barnes & Noble.com does not and will not violate the rights of any third party. Please follow the rules below to help ensure that your review can be posted.

Reviews by Our Customers Under the Age of 13

We highly value and respect everyone's opinion concerning the titles we offer. However, we cannot allow persons under the age of 13 to have accounts at BN.com or to post customer reviews. Please see our Terms of Use for more details.

What to exclude from your review:

Please do not write about reviews, commentary, or information posted on the product page. If you see any errors in the information on the product page, please send us an email.

Reviews should not contain any of the following:

  • - HTML tags, profanity, obscenities, vulgarities, or comments that defame anyone
  • - Time-sensitive information such as tour dates, signings, lectures, etc.
  • - Single-word reviews. Other people will read your review to discover why you liked or didn't like the title. Be descriptive.
  • - Comments focusing on the author or that may ruin the ending for others
  • - Phone numbers, addresses, URLs
  • - Pricing and availability information or alternative ordering information
  • - Advertisements or commercial solicitation

Reminder:

  • - By submitting a review, you grant to Barnes & Noble.com and its sublicensees the royalty-free, perpetual, irrevocable right and license to use the review in accordance with the Barnes & Noble.com Terms of Use.
  • - Barnes & Noble.com reserves the right not to post any review -- particularly those that do not follow the terms and conditions of these Rules. Barnes & Noble.com also reserves the right to remove any review at any time without notice.
  • - See Terms of Use for other conditions and disclaimers.
Search for Products You'd Like to Recommend

Recommend other products that relate to your review. Just search for them below and share!

Create a Pen Name

Your Pen Name is your unique identity on BN.com. It will appear on the reviews you write and other website activities. Your Pen Name cannot be edited, changed or deleted once submitted.

 
Your Pen Name can be any combination of alphanumeric characters (plus - and _), and must be at least two characters long.

Continue Anonymously
Sort by: Showing 1 Customer Reviews
  • Anonymous

    Posted January 5, 2004

    A great book for learning about real-time systems.

    This book does a good job of teaching the fundamentals of real-time systems, including what a real-time system is, where they are used, etc. It quickly gets you to understanding different scheduling algorithms (like the rate-monotonic scheduler VxWorks uses), their benefits, and being able to determine if the hardware can keep up with the timing requirements. The book contains a lot of interesting examples, starting slow with air conditioning/heating unit examples, to smart traffic lights, and on to more complicated ones such as NASA's Mars Odyssey, NASA's X-38 crew return vehicle avionics, and the Space Shuttle Orbital Maneuvernig and Reaction Control Systems. The author does a good job of explaining complicated concepts.

    Was this review helpful? Yes  No   Report this review
Sort by: Showing 1 Customer Reviews

If you find inappropriate content, please report it to Barnes & Noble
Why is this product inappropriate?
Comments (optional)