University of Virginia Department of
    Computer Science



CS 591

University of Virginia

Fall 1998

Real-time computing has become an important subdiscipline of Computer Science and Computer Engineering. Many interesting applications require real-time computing such as avionics, air traffic control, robotics, factory automation, nuclear power plants, process control, automated highways, intensive care monitoring, space travel, financial transactions, telecommunications, mobile computing, and multimedia. One major study has indicated that by the year 2000, 50% of all software development will be for real-time embedded systems. The course presents the underlying theory, concepts, and practice for such systems. The goals of the course include: introducing the unique problems that arise when time constraints are imposed on systems, identifying basic theory and the boundary between what is known today and what is still research, stressing a systems integration viewpoint in the sense of showing how everything fits together rather than presenting a collection of isolated solutions, and addressing multiprocessing and distributed systems. One main value to this course is how it brings together material that students have had in other courses such as architecture, operating systems, programming languages and software engineering. Other values include introducing multiprocessing, networking and simulation.

With the explosion of the Internet capabilities and the ability to transmit real-time audio and video streams, real-time computing is now ubiquitous. This course also presents some of the basic results from what might be called the classical technology of real-time computing and presents that in the context of new applications of this technology in distributed real-time multimedia and real-time multimedia databases. Applications that can take advantage of these new capabilities include: enhanced version of classic real-time applications as well as distributed simulation, distance learning, global business enterprise computing, entertainment, and distributed medicine.

Topics Include

Main topics in the course include an introduction to what real-time systems are and are not, real-time scheduling, real-time operating systems (kernels) including multiprocessor kernels, real-time networking and architectures, real-time requirements and design languages, real-time programming languages, multimedia, and distributed multimedia databases.


Prof. John (Jack) Stankovic
Dept of Computer Science
University of Virginia
Charlottesville, VA 22903

Phone: 804-982-2275

FAX 804-982-2214

OFFICE HOURS: to be announced in class

Required Text

None. Papers will be handed out. Reading assignments will include various papers from the literature.

Recommended Text

Advances in Real-Time Systems
John A. Stankovic and Krithi Ramamritham
IEEE Computer Society Press
ISBN 0-8186-3792-7

Course Requirements
Grading is based on 4 laboratory/programming exercises (10% each), homeworks (10%), a mid term exam (20%) and final exam (30%).


Undergraduate courses in computer architecture and operating systems are required. Knowledge of C or C++ is also required.

Outline of Course

Introduction - 2 lectures

  1. examples of applications
  2. important characteristics of these applications
  3. what is a real-time system and definitions
  4. what isn't a real-time system
  5. common misconceptions
  6. overview of science of real-time systems and examples of research problems

Real-Time Scheduling - 8 lectures

  1. classification of the problem and metrics
  2. classical scheduling results (Jackson's rule, Smith's rule, Moore's rule, McNaughton's theorem, Mok's theorem, concept of competitiveness and bounds analysis; NP-hardness; implications of classical scheduling results for real-time computing)
  3. off-line scheduling for static real-time systems
  4. on-line (ED and RM algorithms and their extensions)
  5. multiprocessor scheduling (RM and Spring algorithm; Richard's anomalies)
  6. distributed scheduling
  7. overload and resource reclaiming

Real-Time Kernels - 2 lectures

  1. commercial proprietary kernels - VxWorks
  2. RT-UNIX and RT-MACH

Real-Time Multiprocessor Kernels - 5 lectures

  1. process (and thread) management, memory management, IPC, implementation issues for scheduling, shared segments, distributed shared memory; other multiprocessor support;
  2. multiprocessor architectures, real-time architecture issues
  3. data acquisition and control

Real-Time Networking - 2 lectures

  1. predictable networking (fiber optic rings) using reflective memory
  2. overview of capabilities of current networks with respect to transmitting audio and video
  3. quality of service guarantees for multimedia using ATM networks
  4. OS/scheduling/admission control

Real-Time Requirements and Design - 2 lectures

  1. specification languages
  2. design and analysis tools

Real-Time Programming Languages - 2 lectures

  1. concepts and examples from various languages including RT-Euclid, Flex, Pearl, ADA, RT-Concurrent C and Spring C.

System Integration - 2 lectures

  1. using Spring SDL; Spring C; Spring Kernel and SpringNet
  2. using the MARS distributed system

Real-Time Distributed Multimedia Databases (2 lectures)

  1. definitions
  2. real-time concurrency control and transaction cpu scheduling
  3. protocols for data with temporal validity intervals
  4. global, virtual, multimedia databases
  5. integrated solutions (real-time, fault tolerance, QoS and security)
  6. will Java and JDBC be usable for RTDBs?