Syllabus

Contents

1. Instructor Contact Information
2. On-Campus Meetings
3. Course Description
4. Prerequisites
5. Readings
6. Assignments & Grading
7. Academic Honor Code
8. Accommodation for Disabilities
9. Communication

Instructor Contact Information

• Instructor: Ted Baker
• URL: http://www.cs.fsu.edu/~baker/cis6930.S04
• Office hours: TBA, and by e-mail and appointment
• Office location: 207A LOV
• Phone: 644-5452
• e-mail:

Class Meetings

Course Description

This course is intended for students who already have a general knowledge of real time systems at the level of COP 4613. It will go into depth on a set of recent research papers, on active research topics. It will be organized along the lines of a seminar. There will be a set of papers assigned for the group to read. All students will be expected to read all the papers. Individual students will be assigned specific research papers to present to the group. The instructor will start the term by presenting talks on some of the papers, while the students prepare their own presentations. The students will then present the papers they have prepared to the entire group.

The course objectives are to bring students up to a point that they have a knowledge of recent research on some topics in real time systems, are able to read and think critically about a research paper, are able to assimilate and orally communicate the content of a research paper, and are prepared, if they are interested, to continue with individual readinds and research.

This term the central topic will be multiprocessor real-time scheduling and resource management. We may also look into real-time device driver architectures.

Prerequisites

The formal prerequisite for this course is COP 4613 Real Time Systems, or a similar introductory course in Real Time Systems.

Readings

The actual set of readings will be chosen after the next meeting of the IEEE Real Time Systems Symposium, which is held in the first week of December, so that we can read some of the papers presented at that conference. In addition, we will cover some of the following papers, which are related to the current research interests of the instructor and other FSU faculty members in real time systems.

• S. Aggarwal, C. Chraibi, ``Hyperperiodic Tasks: A New Model for Hard Real-Time Systems'', Proceedings of the Real-Time Mini-Symposium, 12th IFAC World Congress, Sydney, Australia (1993) 325-328.
• S. Aggarwal, C. Chraibi, ``On the Scheduling of Hyperperiodic Tasks'', Proceedings of the 5th EuroMicro Workshop on Real-Time Systems, Oulu, Finland, IEEE Computer Society Press (1993) 112-117.
• S. Aggarwal, C. Chraibi, ``On the Combined Scheduling of Hyperperiodic, Periodic, and Aperiodic Tasks'', Proceedings of the First Conference on Performability in Computing Systems (July 1996).
• S. Aggarwal, C. Chraibi, ``Scheduling Hyperperiodic Tasks in a Multiprocessor Environment'', Proceedings of the 2nd ISSAT Conference on Reliability and Quality in Design, Orlando, FL (1995) 88-92.
Bjorn Andersson, Static-priority scheduling on multiprocessros, Doctoral Dissertation, Department of Computer Engineering, Chalmers University of Technology, Goteborg, Sweden (2003).
• B. Andersson, J. Jonsson, ``Fixed-priority preemptive multiprocessor scheduling: to partition or not to partition'', Proceedings of the International Conference on Real-Time Computing Systems and Applications, Cheju Island, Korea (December 2000).
• B. Andersson, S. Baruah, J. Jonsson, ``Static-priority scheduling on multiprocessors'', Proceedings of the IEEE Real-Time Systems Symposium, London, England (December 2001).
• B. Andersson, J. Jonsson, ``Fixed-priority preemptive multiprocessor scheduling: to partition or not to partition'', Proceedings of the International Conference on Real-Time Computing Systems and Applications, Cheju Island, Korea (December 2000).
• T.P. Baker, ``Stack-based scheduling of real-time processes'', The Real-Time Systems Journal 3,1 (March 1991) 67-100. (Reprinted in Advances in Real-Time Systems, IEEE Computer Society Press (1993) 64-96).
• T.P. Baker, ``Multiprocessor EDF and Deadline Monotonic Schedulability Analysis'' technical report TR-030401, Department of Computer Science, Florida State University, Tallahassee, FL 32306 (April 2003)
• T.P. Baker, ``An Analysis of EDF Schedulability on a Multiprocessor'' technical report TR-030202, Department of Computer Science, Florida State University, Tallahassee, FL 32306 (February 2003) -- revised April 2003
• T.P. Baker, ``An Analysis of Deadline-Monotonic Schedulability on a Multiprocessor'', technical report TR-030301, Department of Computer Science, Florida State University, Tallahassee, FL 32306 (March 2003) -- revised in April 2003.
• S. Baruah, Joel Goossens, ``Rate-monotonic scheduling on uniform multiprocessors'', UNC-CS TR02-025, University of North Carolina Department of Computer Science (May 2002).
• A. Burchard, J. Liebeherr, Y. Oh, S. H. Son, ``New strategies for assigning real-time tasks to multiprocessor systems'', IEEE Transactions on Computers 44 (1995), 1429-1442.
• Dhall, S.K. ``Scheduling Periodic-Time-Critical Jobs on Single Processor and Multiprocessor Computing Systems'', Ph.D. dissertation, University of Illinois, Urbana, 1977.
• Dhall, S.K. and Liu, C.L. ``On a Real-Time Scheduling Problem'', Operations Research 26.1, February 1979, pp.\ 127--140.
• J. Goossens, S. Funk, S. Baruah, ``Priority-driven scheduling of periodic task systems on multiprocessors'', technical report UNC-CS TR01-024, University of North Carolina Computer Science Department, Real Time Systems, Kluwer, (to appear).
• R. Ha, ``Validating timing constraints in multiprocessor and distributed systems'', Ph.D. thesis, technical report UIUCDCS-R-95-1907, Department of Computer Science, University of Illinois at Urbana-Champaign (1995).
• R. Ha, J.W.S. Liu, ``Validating timing constraints in multiprocessor and distributed real-time systems'', technical report UIUCDCS-R-93-1833 , Department of Computer Science, University of Illinois at Urbana-Champaign, (October 1993).
• R. Ha, J.W.S. Liu, ``Validating timing constraints in multiprocessor and distributed real-time systems'', Proceedings of the 14th IEEE International Conference on Distributed Computing Systems, IEEE Computer Society Press (June 1994).
• Oh, D.I., and Baker, T.P. ``Utilization Bounds for $N$-Processor Rate Monotone Scheduling with Stable Processor Assignment'', Real Time Systems Journal, 15,1, September 1998.\ 183--193.
• J.M. L\'opez, M. Garc\'ia, J.L. D\'iaz, and D.F. Garc\'ia, ``Worst-case utilization bound for EDF scheduling on real-time multiprocessor systems'', Proceedings of the 12th Euromicro Conference on Real-Time Systems (2000) 25-33.
• C.A. Phillips, C. Stein, E. Torng, J Wein, ``Optimal time-critical scheduling via resource augmentation'', Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing (El Paso, Texas, 1997) 140-149.
• A. Srinivasan, S. Baruah, ``Deadline-based scheduling of periodic task systems on multiprocessors'', Information Processing Letters 84 (2002) 93-98.

Assignments & Grading

Students in the course will be expected to read the assigned papers, at a rate of one to three papers per week (depending on the length and difficulty of the papers), deliver prepared presentations (with PowerPoint or other visual aids), contribute to discussions of the papers, and write short (one or two pages) evaluative summaries of the papers. The number of papers presented by each student will depend on the number of students participating in the class.

Each paper summary will identify strengths and weaknesses of the paper, along with ideas for further research raised by the paper. It should represent the analytical thoughts of the student on the paper. Mere compilation of quotations or paraphrasing of the paper will not suffice. (Extra credit will be granted for any student who goes beyond these summary requirements, and develops an original research idea based on the papers in the course.)

Grading will be based on the quality of daily class participation (30%), individual presentations and supporting visual aids (40%), and the paper summaries (30%).

Academic Honor Code

Like other courses at FSU, in this course the FSU Academic Honor Code applies. I this course, students are encouraged to discuss the papers with other students, both in and out of class, but the preparation of presentations and the paper summaries is expected to be done individually. In particular, plagiarism of paper summaries will not be tolerated.

Accommodation for Disabilities

Students with disabilities needing academic accommodations should:

1. Register with and provide documentation to the Student Disability Resource Center (SDRC).
2. Bring a letter to the me from the SDRC indicating you need academic accommodations. This should be done within the first week of class.

This syllabus and other class materials are available in alternative format upon request.

For more information about services available to FSU students with disabilities, contact the Assistant Dean of Students:

Student Disability Resource Center
08 Kellum Hall
Florida State University
Tallahassee, FL 32306-4066

e-mail: sdrc@admin.fsu.edu
phone: (850) 644-9566.

Communication

If you are experiencing difficulty or are concerned about your progress, please contact me right away. Problems are usually easier to solve when they are addressed early.