CS6235 - Introduction to Real-Time System Concepts and Implementation

Spring 2003

Location: CCB 102
Time: 12:05-13:25 (Tuesday, Thursday)

Instructor: Calton Pu ( calton@cc )
Office: 269 CCB Bldg.
Office hrs.: by appointment.

Instructor: Karsten Schwan ( schwan@cc )
Office: 216 CCB Bldg.
Office hrs.: by appointment.

TA: David Buttler ( buttler@cc )
Office: CCB commons area
Office hours: by appointment


Course Description

CS6235 (Real-Time Systems) This course covers the principles of real-time and embedded systems inherent in many hardware platforms and applications being developed for engineering and science as well as for ubiquitous systems, including robotics and manufacturing, interactive and multimedia, immersive and omnipresent applications. As part of this course, students will learn about real-time and quality of service system principles, understand real-time operating systems and the resource management and quality of service issues that arise, and construct sample applications on representative platforms. Platforms range from handheld and mobile computers to media and real-time server systems. Platforms may also include specialized systems used in application-specific contexts, such as autonomous robotics, smart sensors, and others.

Homework
All students must submit written abstracts for at least 75% of the papers studied in class, before each paper's presentation. These abstracts must summarize the main points of the paper. Abstracts should not be simple cut and paste from the papers  -- they should display some understanding of the material and criticism of the work (both pros and cons).  Abstracts must be emailed to the TA (buttler@cc) with the subject "CS6235 -- summary".

Projects
 Class projects will use the Unix Solaris and Linux operating systems, both of which offer some facilities for construction and control of real-time systems. Class members have access to selected real-time devices and ubiquitous systems, including smart sensors (skiff boards running Linux), possibly including Lego robots (if there is class interest), including handheld devices and portable PCs (Linux-based PCs and PalmOS/Linux-based handhelds and/or wearables), including camera and other video-based sensors on PCs running Windows or Linux, and they can have access to the commercially most prevalent real-time operating system kernel, called Vxworks, running on Pentium and Sparc machines.

Sample applications available to students include multimedia codes (video and audio), distributed games, sensor processing codes, image processing codes, location identification (if there is class interest) and possibly, distributed virtual environments (again, given class interest).


Course Outline

(subject to update)
Weeks 1 and 2: Basic Concepts

  1. (1/7) (Karsten Schwan) Introduction
  2. (1/9) (Christian Poellabauer) A. Burns, A. Wellings, "Real-Time Systems and Their Programming Languages", Chapter 1: Introduction to Real-time Systems, (handout)
    (1/9) P. Laplante, "Real-Time Systems Design and Analysis: An Engineer's Handbook", Chapter 1: Basic Real-time Concepts, IEEE Press, (handout) (PPT slides, PDF slides)
  3. (1/14) J. Stankovic, "Misconceptions about Real-Time Computing", IEEE Computer, Oct. 1988 (handout)
    (1/14) J. Stankovic, K. Ramamritham, "What is Predictability for Real-Time Systems?", IEEE Press, 1990. Abstract required.
  4. (1/16) Ashvin Goel, Luca Abeni, Charles Krasic, Jim Snow, and Jonathan Walpole. Supporting time-sensitive applications on general-purpose operating systems. In Proceedings of the Fifth USENIX Symposium on Operating Systems Design and Implementation, Dec 2002. (Abstract Required)
Weeks 3 and 4: Sample Real-time Applications
Robotics and Manufacturing, from Plant Control to Autonomous Systems
  1. (1/21) K. Schwan, T. Bihari, B.W. Weide, G. Taulbee, " High-Performance Operating System Primitives for Robotics and Real-Time Control Systems", IEEE Press, 1988, editor: J. Stankovic (Abstract Required)
Multimedia, Virtual Environments and Collaborative Applications
  1. (1/21) D. James Gemmell, Harrick M. Vin, Dilip D. Kandlur, P. Venkat Rangan, and Lawrence A. Rowe, "Multimedia Storage Servers: A Tutorial and Survey", IEEE Computer, May 1995. (brief overview given in class.)(pdf)
  2. (1/23) (Himanshu Raj ) Shahabi, Zimmermann, Fu, and Yao.  "Yima: A Second-Generation Continuous Media Server", IEEE Computer Magazine, June 2002.

Quality of Service
  1. (1/23) "QoS Scalability for Streamed Media Delivery", OGI/CSE Tech Report No. 99-011 (Abstract required).
    (1/28) SPEG Example: Lecture Slides
  2. (1/28) J. Walpole, C. Krasic, L. Liu, D. Maier, C. Pu, D. McNamee, and D. Steere, "Quality of Service Semantics for Multimedia Database Systems", Proceedings of IFIP Data Semantics 8 Working Conference on Semantics Issues in Multimedia Systems, New Zealand, January 1999. (Abstract Required)
    (1/28) QoS Semantics: Old Lecture Slides
Mobile and Ubiquitous Computing
  1. (1/30) Anind Dey, Danial Salber, Gregory Abowd, Masayasu Futakawa, " The Conference Assistant: Combining Context-Awareness with Wearable Computing" Abstract required.
    (1/30) Ubiquitous Computing: Lecture Slides
  2. (1/30) Albrecht Schmidt, Kofi Asante Aidoo, Antti Takaluoma, Urpo Tuomela, Kristof Van Laerhoven, Walter Van de Velde, "Advanced Interaction in Context", University of Karlsruhe, Germany
  3. (2/4) (Alfred Park, Ross Piasecki) M. Weiser, "Some Computer Science Issues in Ubiquitous Computing", CACM, July 1993 (ppt slides)
  4. (2/4) G. Forman, J. Zahorjan, "The Challenges of Mobile Computing", UW CSE Tech Report No. 99-11-03, March 9, 1994. Abstract required. (ppt slides)
Real-Time Benchmarks
  1. (2/6) (Raj Krishnamurthy) "Introduction to Real-Time Computing", textbook excerpt on benchmarks
  2. (2/6) Rabindra P. Kar, "Implementing Rhealstone Real-Time Benchmark", Dr. Dobb's Journal, April 1990
  3. (2/6) Nelson H. Weiderman, Nick I. Kamenoff, "Hartstone Uniprocessor Benchmark: Definition and Experiments for Real-Time Systems.", the Journal of Real-Time Systems, 1992
  4. (2/6) Nick I. Kamenoff, Nelson H. Weiderman, " Hartstone Distributed Benchmark: Requirements and Definitions", Twelfth Real-Time Systems Symposium, 1991.
  5. (2/6) Zuerndorfer, Shaw, " SAR Processing for the RASSP Application"
  6. (2/6) "Real-Time Benchmarking: Methodology and Applications"
Real-Time Issues in Computer Hardware
  1. (2/11) Lundqvist, Stenstrom, "Timing Anomalies in Dynamically Scheduled Microprocessors", Real-Time Systems Symposium, 1999. Proceedings. The 20th IEEE , 1999 Page(s): 12-21. Abstract required.
  2. (2/11) Narasimhan and Nilsen, " Portable Execution Time Analysis for RISC Processors", Abstract required.
  3. (2/13) Malcolm and Zhao, " Hard Real-Time Communication in Multiple-Access Networks", Journal of Real-Time Systems, Vol. 8, No. 1, Jan 1994, pp 35 -- 77.
  4. (2/13) B.K. Choi, D. Xuan, C. Li, R. Bettati, and Wei Zhao, " Utilization-Based Admission Control for Scalable Real-Time Communications", Journal of Real-Time Systems, Oct. 2000. Abstract required.
  5. (2/13) Network Scheduling: Lecture Slides
Real-Time Operating Systems and Scheduling
  1. (2/18) Kaushik Ghosh, Bodhisattwa Mukherjee, Karsten Schwan, "A Survey of Real-Time Operating Systems", 1994
  2. (2/18) K. Schwan, H. Zhou, and A. Gheith, " Real-time Threads", ACM Operating Systems Review, vol. 25, pp. 35-46, Oct. 1991. (note: pages are in reverse order)
  3. (2/18) S. Oikawa and H. Tokuda, " User-level Real-Time Threads", Proceedings of the 11th IEEE Workshop on Real-Time Operating Systems and Software, Seattle, WA, May 1994. Comparative abstract for #2 and #3 required.

  4. (2/20) Lui Sha, J.B. Goodenough, " Real-Time Scheduling Theory and Ada", Computer, Vol. 23, Issue 4, April 1990
  5. (2/20) J. Lehoczky, L. Sha, Y. Ding, " The Rate Monotonic Scheduling Algorithm - Exact Characterization and Average Case Behavior", Proceedings of the Real-Time Systems Symposium, 1989.  Abstract required.
  6. (2/20) Rate Monotonic Scheduler: Lecture Slides

  7. (2/25) Lu, C.; Stankovic, J.A.; Tao, G.; Son, S.H., " Design and evaluation of a feedback control EDF scheduling algorithm", Real-Time Systems Symposium, 1999. Proceedings. The 20th IEEE , 1999.  Abstract required.
  8. (2/25) Feedback-Based EDF: Lecture Slides
  9. (2/25) David C. Steere, Ashvin Goel, Joshua Gruenberg, Dylan McNamee, Calton Pu, and Jonathan Walpole, " A Feedback-Driven Proportion Allocator for Real-Rate Scheduling", Operating System Design and Implementation (OSDI), February, 1999.  Abstract required.
  10. (2/25) A Feedback-Driven Proportion Allocator for Real-Rate Scheduling: Lecture Slides

  11. (2/27) M. Jones, D. Rosu and M. Rosu, " CPU Reservations and Time Constraints: Efficient, Predictable Scheduling of Independent Activities", (.pdf version) Proceedings of the 16th ACM Symposium on Operating System Principles, St.Malo, France, pp. 198-211, Oct. 1997

  12. 3/3-7 SPRING BREAK

  13. (3/11) Zhang, Deering, Estrin, Shenker, Zappala, " RSVP: A New Reservation Protocol, old link The 8th IEEE Workshop on Computer Communications, 1993
  14. (3/11) Richard West, Karsten Schwan and Christian Poellabauer, " Scalable Scheduling Support for Loss and Delay Constrained Media Streams",
Advanced Topics in Resource Management -- Adaptive and Open Systems
Open Systems
  1. (3/13) Deng, Z.; Liu, J.W.-S., " Scheduling Real-Time Applications in an Open Environment", Real-Time Systems Symposium, 1997. Proceedings., The 18th IEEE , 1997
  2. (3/13) Tei-Wei Kuo; Ching-Hui Li, " A Fixed Priority-Driven Open System Architecture for Real-Time Applications", Real-Time Systems Symposium, 1999. Proceedings. The 20th IEEE , 1999
    (Abstract required for one of the two papers)

  3. (3/18) J.A. Zinky, D.E. Bakken and R.E. Schantz, " Architectural Support for Quality of Service for CORBA Objects", Theory and Practice of Object Systems, April, 1997. Original w/ figures (See also: Quality Objects)
  4. (3/18) (Lenin) Vanegas R, Zinky JA, Loyall JP, Karr DA, Schantz RE, Bakken DE. " QuO's Runtime Support for Quality of Service in Distributed Objects", Proceedings of the IFIP International Conference on Distributed Systems Platforms and Open Distributed Processing (Middleware'98), 15-18 September 1998. (Presentation Slides)
    (Abstract required for one of the two papers)

  5. (3/20) (Young ) P. Pal, J. Loyall, R. Schantz, J. Zinky, R. Shapiro, J. Megquier, " Using QDL to Specify QoS Aware Distributed (QuO) Application Configuration", ISORC, March 2000.
  6. (3/20) Richard E. Schantz, Joseph P. Loyall, Douglas C. Schmidt, Craig Rodrigues, Yamuna Krishnamurthy, and Irfan Pyarali. " Flexible and Adaptive QoS Control for Distributed Real-time and Embedded Middleware", Middleware 2003, 4th IFIP/ACM/USENIX International Conference on Distributed Systems Platforms, June 16-20, 2003, Rio de Janeiro, Brazil. (Local copy)
    (Abstract required for one of the two papers)

  7. (3/25) (Kang Li) Kang Li, J. Walpole, Dylan McNamee, Calton Pu and David C. Steere, " A Rate-Matching Packet Scheduler for Real-Rate Applications", Multimedia Computing and Networking (MMCN'01), January 2001. (abstract required)

  8. (3/27) (Kang Li) Kang Li, Molly H. Shor, Jonathan Walpole, Calton Pu, David Steere, " Modeling the Effect of Short-term Rate Variations on TCP-Friendly Congestion Control Behavior", (.ps version) to appear in the Proceedings of the 2001 American Control Conference (ACC), June 2001. (abstract required)
    (3/27) Lecture Slides

  9. (4/1) Lui Sha, Xue Liu, Ying Lu, Tarek Abdelzaher Queueing Model Based Network Server Performance Control Proceedings of the 23rd IEEE Real-Time Systems Symposium (RTSS'02)
  10. (4/1) Tarek F. Abdelzaher and Kang G. Shin, " End-host Architecture for QoS-Adaptive Communication", IEEE Real-Time Technology and Applications Symposium, Denver, Colorado, June 1998 
    (Abstract required for one of the two papers)

  11. (4/3) Luca Abeni, Luigi Palopoli, Giuseppe Lipari, Jonathan Walpole " Analysis of a Reservation-Based Feedback Scheduler", Proceedings of the 23rd IEEE Real-Time Systems Symposium (RTSS'02)
  12. (4/3) Pau Marti, Josep M. Fuertes, Gerhard Fohler, Krithi Ramamritham " Improving Quality-of-Control using Flexible Timing Constraints: Metric and Scheduling Issues
    (Abstract required for one of the two papers)

  13. (4/8) Kyoung-Don Kang, Sang H. Son, John A. Stankovic " STAR: Secure Real-Time Transaction Processing with Timeliness Guarantees", Proceedings of the 23rd IEEE Real-Time Systems Symposium (RTSS'02)
    (abstract required)

  14. (4/10) Brandt, S.; Nutt, G.; Berk, T.; Mankovich, J., " A Dynamic Quality of Service Middleware Agent for Mediating Application Resource Usage", Real-Time Systems Symposium, 1998. Proceedings. The 19th IEEE , 1998
  15. (4/10) Baochun Li and Klara Nahrstedt, " A Control-based Middleware Framework for Quality of Service Adaptations", IEEE Journal of Selected Areas in Communication, Special Issue on Service Enabling Platforms, 1999, Vol. 17, No. 9, September 1999.
    (Abstract required for one of the two papers)

  16. (4/15) (Maciej Bajkowski) Angelo Corsaro and Douglas C. Schmidt. " Evaluating Real-Time Java Features and Performance for Real-time Embedded Systems", Proceedings of the 8th IEEE Real-Time Technology and Applications Symposium, San Jose, CA, September 2002. (Local copy)
  17. (4/15) (Fabian Sturm) Frank Mehnert, Michael Hohmuth, Hermann Hartig " Cost and benefit of separate address spaces in real-time operating systems", Proceedings of the 23rd IEEE Real-Time Systems Symposium (RTSS'02)
    (Abstract required for one of the two papers)

Student Project Presentations

(Detailed Schedule)
  1. (4/17) Student project presentations
  2. (4/22) Student project presentations
  3. (4/24) Student project presentations

Additional, Possible Class Topics:


Structuring and describing real-time software Performance Evaluation Further issues in Real-Time Systems

Note:

This class is taught only once every two years due to CoC resource constraints. It is suitable for both CoC and non-CoC majors, in part because grades are based on project work, where one smaller project is predefined and the main course project is defined jointly by the instructor and students. The intent is to ensure some basic skills on the part of each student and also to match both student interests/background and course objectives.

Grading

Each student (or team) will present one course topic in class and also complete the class projects. Maximum team size is 3 students. In addition, as part of class homework, all students must submit written abstracts for at least 75% of the papers studied in class, before each paper's presentation. These abstracts must summarize the main points of the paper.
  1. 60% 2 Projects
  2. 20% Abstracts/Class Participation
  3. 20% Student Presentations

Useful Links:

Real-time Systems Reading List
Boston University: CS835 Reading List
Computer Science Research Paper Search Engine
Real-Time Resources
Ubiquitous Computing Links
Postscript(R) to PDF Converter
Monitor this page for changes