Undergraduate Curricula,
Electrical
& Computer Engineering Department,
Faculty of Engineering,
Real-Time Systems
Info |
Objectives | Syllabus | Prerequisites |
Textbooks | References | Grading | Lectures
Projects | Assignments | Photos | Students | Links
Information:
Course Name: Real
Time Systems
Course Number:
ECE1567
Credits: 3
Semester: Bahman 1379
Room: No. 4
Class Schedule:
Sunday and Tuesday,
Instructor:
Shahab Kalantar, M.Sc. (Machine
Intelligence & Robotics)
Affiliation: Manager, Software systems dept., Automation
division, Fariné Co.,
Robotics Lab., Elect. & Comp.
E-mail: sh.kalantar@farineh.com
kalantar@shafagh.ut.ac.ir
Real-time
Systems are comprised of software/hardware components embedded into larger
systems composed of other sub-systems(both mechanical and electronic). These
systems are fed by input information from the sensors and are supposed to compute control signals for driving the actuators, resulting in a continuous interaction
with the environment.
Real-time
Systems are major ingredients of any R&D effort in robotics, mechatronics, avionics, process control, and many others, where autonomy is an
issue.
In
real-time systems, correctness of operation depends not only on its logical
behaviour, but also the time at which the results are produced. They should
comply with certain timing constraints, imposed not by the capability of the
internal processes in the computing systems, but by the real-world processes in
the surrounding environment, otherwise performance degradation and/or
malfunction results, which can lead to catastrophes in safety-critical systems.
In this
course, we will learn how to characterize, model, analyze, and design such
systems. Due to its multidisciplinary nature, students are challenged to get
involved in various engineering fields.
Syllabus:
Following
is the list of topics I plan to cover. Of course, we can’t expect to cover
everything without sacrificing detail. We will try to cover the main topics.
The list of items in each topic is tentative and may change as the course
proceeds.
Main Topics
1. Basic concepts in real-time systems
Systems and signals, Reactive systems, Definitions of real-time systems, Types of real-time systems, Event-driven and discrete-event
systems, Deterministic and stochastic systems, Embedded systems, Control
systems, Concurrent systems, Distributed systems, Complex systems,
Fault-tolerant systems and reliability, Safety-critical systems, Internal
structure of real-time systems, Performance measures, Examples of real-time
systems and real-world applications, Modeling real-time systems, Designing
real-time systems, Software/hardware co-design
[T1] (Chapter 1), [R1] (Chap. 1, 3, 4, 13, 14), [T3] (Chap. 1,2), [T4] (Chap.
1,2), Handouts
2. Real-time computer hardware and process
interfacing
Central
processing unit, Micro-controllers, Memories, Specialized
processors, Bus structures, Digital signal interfacing, Pulse interfaces,
Analogue signal interfacing, Real-time clock and timers, Interrupts, Direct
memory access, Serial and parallel interfaces, Pipelining, Coprocessors
[T1] (Chapter 3), [T3] (Chap. 4,5), [R1] (Chap. 2), Handouts
3. Real-time computer control systems
Basic concepts and architectures, Examples of processes, Continuous and
discrete time, Linear control systems, Digitizing analogue signals, Sequence control, Loop control, Supervisory
control, Centralized and distributed control, Adaptive and inferential control,
Batch control, Direct digital control, Human-machine interfaces, Programmable
controllers, Simulation
[T1] (Chapter 1,2,4), [T3] (Chap. 1,2,3,4,15), Handouts
4. Real-time kernels and programming
languages
Multi-tasking, Resource sharing, Inter-task communication and
synchronization, Priorities, Drivers, Scheduling, Criteria for programming
languages, CONIC, PAISELY, RT-LINUX, WindowsCE, VxWorks, RTX-DOS, QNX
[T1] (Chap. 5,6,9,10), [R1] (Chap. 3, 6, 7, 8), [T3] (Chap. 7,8,9,16), Handouts
5. Structured design of real-time systems
Structure charts, Data
flow diagrams, State machines, State transition diagrams, Control flow
diagrams, Concurrency issues, State charts, Yourdon methodology, Ward/Mellor
methodology, Hatley/Pirbhai methodology, Warnier-Orr notation, Design tools (SELECT, MASCOT, LACATRE)
[T1] (Chap. 7,8,9), [T2] (Chap. 1,2,3,4,6,8), [T3] (Chap. 11), [R18]
(Chap. 7,11,15), [R1] (Chap. 5), Handouts
State machines, Extended state machines, Communication state machines,
Real-time state machines, Statecharts, Mode charts, Petri nets, Types of Petri
nets, Applications of Petri nets, Reachability and coverability, Synchronized
Petri nets, Timed Petri nets, Timing constrant Petri nets, Safety analysis with
Petri nets, Coloured Petri nets, Grafcet, Temporized Grafcet, GraphChart,
Hierarchical Petri nets, stochastic Petri nets, Modeling tools
Basic concepts, Types of Petri nets, Properties of Petri nets, Reachability
and coverability, Applications of Petri nets, Synchronized Petri nets, Timed
Petri nets, Timing constraint Petri nets, Interpreted Petri nets, Stochastic
Petri nets, Grafcet, Safety analysis using Petri nets
[T1] (Chap. 10), [R6]
(Chap. 1, 2, 4, 5), [R7] (Chap. 11), Handouts
14. Synchronous Programming Languages
Basic concepts, SyncCharts,
SIGNAL,
14. Scheduling in real-time systems
Basic concepts, Rate-monotonic scheduling, Earliest dead-line first
scheduling, IRIS scheduling, Fault tolerant scheduling, Event-driven
scheduling, Static scheduling, Dynamic scheduling, Clock-driven scheduling,
Processor utilization, Preemptive/non-preemptive scheduling, Periodic/sporadic
tasks scheduling, Multiprocessor
scheduling
[T1] (Chap. 10), [T4]
(Chap. 3), Handouts
13. Keeping Time and Clock synchronization
Clocks, Synchronization, Non-fault tolerant synchronization, Impacts of faults,
Hardware synchronizers, Completely connected configuration, sparsely connected
configuration, Multiple faults, Interactive convergence averaging algorithms,
Convergence non-averaging algorithm
Selective Topics
8. Monitoring and debugging real-time
systems
Basic concepts, Monitoring systems, Software monitoring systems, Hardware
monitoring, Hybrid monitoring, Debugging real-time systems, Noninterference
monitoring systems, Graph- based
timing analysis, Visualization and debugging
[R7] (Chap. 1 thru 10), Handouts
7. Fault-tolerant real-time systems
Basic concepts, Causes of failures, Types of failures, Fault detection, Fault
containment, Fault recovery, Redundancy, Byzantine failures
[T1] (Chap. 11), [T4]
(Chap. 7), [R1] (Chap. 11), Handouts
10. Formal specification and verification
Basic concepts, Processes, Temporal logic,
Verification by temporal logic, Extended state machines(ESM), Trajectory generating
systems, Real-time temporal logic(RTTL), Proof systems(PS-RTTL), Verification
using PS-RTTL, Communicating sequential processes, Timed automata, Timed
transition systems, Process algebras, Q-model, Mode charts, Real-time
logic(RTL), Tools(UPPAL, CHARON, CRONOS)
[T3] (Chap. 14), [R3]
(Chap. 1 thru 6), [R14] (Chap. 1,2,3), Handouts
11. Reliability modeling of real-time
systems
Basic concepts, Reliability function, Hazard function, Availability, MTTF,
MTBF, Common life-time models, Model selection and fitting, Reliability of
systems, Fault trees, Voting systems, Redundant systems, Markov modeling,
Markov analysis of redundancy, Repairable systems, Software reliability metrics
[R5] (Chap. 1,2,3,4,6,8), [T4] (Chap. 8), [R1]
(Chap. 10, 11), Handouts
6. Object-oriented design of real-time
systems
Object model, Dynamic model, Functional modeling, Concurrency issues,
UML methodology, Use cases, Activity charts, Interaction diagrams, State
charts, Timing diagrams, OMT
methodology, CODART notation, Design tools (Rhapsody)
[T2] (Chap. 1,2,3,4,6,8), [R13], [R19],
[T3] (Chap. 11), Handouts
12. Distributed real-time systems
Distributed computation, Real-time communication, Network and bus structures, Monitoring and debugging
issues, Communication protocols, synchronization
[R1] (Chap. 12), [R17]
(Chap. 1 thru 4), [T3] (Chap. 6), Handouts
15. Basic concepts in Hybrid control systems
Continuous Petri nets, Hybrid
Petri nets, Definition of hybrid systems,
Applications, Examples, Modeling hybrid systems with state machines, Formal
definition, Modularity and hierarchy, Further examples, Tools (CHARON)
Prerequisites:
Necessary:
·
Practical
experience with a programming language
·
Data
structures and algorithm design
·
Discrete
mathematics
·
Computer
hardware and digital circuits
·
Exposure
to basic ideas in signals and control systems
·
Basic
knowledge of probability and statistics
Helpful but not required:
·
Computer
control systems
·
Mathematical
logic
·
Software
engineering
·
Operating
systems
·
Microprocessor-based
systems
·
Theory
of machines and languages
Textbooks:
No single textbook covers all the topics planned for
this course. Selected texts merely serve as an organizing theme and reflect the
industrial orientation of the course and the instructor. Additional materials
not covered in the textbooks are supplied in the form of handouts and lecture
notes.
[T1] A.C. Shaw, Real-Time Systems and Software, Wiley, 2001.
[T1] R. Bennett, Real-Time Computer Control, Prentice-Hall, 1994.
[T2] J.E. Cooling, Real-Time Software Systems, International Thompson Computer Press, 1997.
[T3] W.A. Halang and K.M. Sacha, Real-Time Systems, World Scientific,
1992.
[T4] C.M. Krishna and K.G. Shin, Real-Time Systems, McGraw-Hill, 1997.
(Excluding chapters 4 and 5)
References:
References supplement the textbooks. Though there is absolutely no need
to obtain them, pursuing one or more specialised topics is highly recommended
for further enrichment.
[R1] P.H. Laplante, Real-Time Systems Design and Analysis, IEEE Press, 1997.
[R2] J. Liu, Real-Time Systems, Prentice-Hall, 2000.
[R3] J.S. Ostroff, Temporal Logic for Real-Time Systems,
Research Studies Press, 1989.
[R4] L. Motus and
M.G. Rodd, Timing Analysis of Real-Time
Software, Pergamon, 1994.
[R5] L.C.
Wolstenholme, Reliability Modeling,
Chapman and Hall, 1999.
[R6] R. David and H.
Alla, Petri Nets and Grafcet,
Prentice-Hall, 1992.
[R7] J.J.P. Tsai, Y.
Bi, S.J.H. Yang, R.A.W. Smith, Distributed
Real-Time Systems, Wiley-Interscience, 1996.
[R8] D. Hatley and
[R9] P.T. Ward and
S.J. Mellor, Structured Development for
Real-Time Systems, Prentice-Hall, 1985.
[R10] S.J. Allworth, Introduction to Real-Time Software Design,
Macmillan Press, 1981.
[R11] J.E. Cooling, Software Design for Real-Time Systems, International Thompson Computer Press, 1991.
[R12] H. Gomaa, Software Design Methods for Concurrent and
Real-Time Systems, Addison-Wesley, 1993.
[R13] B.P. Douglass, Real-Time UML, Addison-Wesley, 2000.
[R14] S. Schneider, Concurrent and Real-Time Systems, Wiley,
2000.
[R17] A.S. Tanenbaum, Distributed
Operating Systems, Prentice-Hall,
1995.
[R18] R.S. Pressman, Software Engineering, McGraw-Hill, 1994.
[R19] B.P. Douglass, Doing Hard Time, Addison-Wesley, 1999.
[R16] CHARON
Language Manual
[R16] LACATRE Reference Guide
Grading:
Ř
Homework
assignments (10%):
One or two per
lecture/topic.
Ř
Project
(40%):
Each student must complete a class project. Most of
the defined projects will be concerned with applying lessons learned from the
lectures to practical applications using the RT-LINUX, VxWorks,
RTXDOS, and QNX real-time operating system.
Depending on students' willingness, hardware projects are also available. Each
project is carried out by a group of at most 3 students. A limited number of
projects can be detailed surveys of real-time operating systems, programming
languages, and development tools.
Ř
Class
participation (10%):
Final grades can be adjusted by as much as 5 points as a reward for
in-class participation, or as much as 10 points in case of unjustified absence
from the classes.
Ř
Mid-term
examination:
There is no
mid-term examination.
Ř
Final
examination (10%):
The final exam will
cover the entire course and will be conducted in a take-home fashion.
Ř
Seminar
(10%):
Each student
should present his or her project work in a seminar. Presentation style is the
prime determinant in grading.
Lectures:
There are a total of 34 regular lectures plus three to four additional
ones to account for insufficient time or additional topics.
We will also have a number of guest lectures covering complementary
materials. Here is a tentative list of topics presented in guest lectures.
Real-time communication
Process interfacing hardware
Real-world applications of Petri nets
Primer on RT_LINUX programming and architecture
Programmable logic controllers
Copyright
© 2001, 2003, Shahab Kalantar. All rights reserved.
Created:
Last modified: