Syllabus

• Instructor Contact Information
• On-Campus Meetings
• Catalog Description
• Prerequisites
• Objectives
• Topics
• Materials
• Assignments
• Grading
• Academic Honor Policy
• Accommodation for Disabilities
• Communication

• Instructor: Ted Baker
• URL: http://www.cs.fsu.edu/~baker/realtime
• Office hours: MWF 11:00AM-12:00Noon (except when preempted by department meetings), and by e-mail and appointment
• Office location: 207A LOV
• Phone: 644-5452
• e-mail:

I will hold "floating" office hours immediately following the class meetings. I will start out in the class meeting room. If there are any students who have problems that they want to demonstrate on the equipment in the 016 Love lab, I will go there and stay until all questions are answered. I will then move on to my office in 207A Love.

In addition, there may be some specially scheduled class meetings (to be arranged) in which students will demonstrate their projects.

"Survey of the issues in the design and implementation of real time computer systems. Topics include: the use of computers for controlling real time processes, the use of Ada in embedded computer systems, and implementation of a real time computer system." [FSU Bulletin]

This course is for advanced undergraduate and beginning graduate students. The undergraduate course, COP 4613, meets together with a section of the graduate course, COP 5642. Graduate students will be expected to do all the work assigned to undergraduate students, but will be generally held to a higher standard of performance. There will be also be a final assignment that will be required of graduate student. (Undergraduates will be allowed to also do this assignment, for extra credit.)

The emphasis of the course will be primarily on abstract models of timed computation and the analysis of scheduling algorithms. In order to connect this theory to practice students will also do a series of hands-on real-time programming exercises, involving real-time control of a physical device, using C threads and a real-time variant of the Linux operating system.

The aim of the course is to bring students up to a point that they understand the motivation, theoretical background, and some of the work that has been done in the field of real-time systems. A student leaving the course should be able to apply some of the simpler techniques, such as rate monotonic analysis, to practical problems without any further study, and prepared to understand the literature if they choose to follow the course with further readings and individual study.

This term we will not cover the Ada programming language, in order to be able to go into more depth on other topics.

The formal prerequisite for this course are COP4610 Operating Systems. That course implies a collection of other prerequisites.

The following are the specific capabilities you will need from the prerequisite courses:

• use basic UNIX programming tools, including
  • a shell (normally bash)
  • a text editor (pico, vi (better), or emacs (best))
  • the gcc compiler
  • the make utility
  • a debugger (gdb or one of the graphical wrappers for it, such as ddd)
• use the C programming language (or the C-like subset of C++) to write and debug programs using all features of the language
• implement and use priority queue data structures
• write programs using POSIX threads
• use and understand the concepts and terminology of computer hardware, including:
  • fetch-execute cycle
  • program/instruction counter
  • operand registers
  • runtime stack
  • call and return processing
  • CPU-level hardware interrupt processing, and masking
  • interrrupt controller, outside of the CPU
  • memory bus and I/O bus
  • memory cache
  • paged virtual memory
  • hardware timers
• use and understand the concepts of concurrent programming, including:
  • concurrent programming constructs (threads, processes)
  • signals, signal masking, and signal handlers
  • race conditions
  • critical sections
  • resource allocation
  • preemption
  • mutual exclusion (semaphores, mutexes, condition variables)
  • deadlock, and methods for dealing with it
  • synchronization
  • CPU scheduling policies, e.g., priority preemptive scheduling, EDF
• to follow some of the proofs used in this course (though not required to pass the examinations or do the programming exercises) you will also need the level of mathematical training required of undergraduate students at FSU, including:
  • recursive definition
  • analysis by cases
  • proof by induction
  • probabliity, including distribution functions, expected value, variance
  • differential calculus, including minimization of a function by finding the point at which all partial derivatives are zero
  • recurrence relations, including finding and verifying a solution (fixed point)

The course is a survey of issues in the design and implementation of real time computer systems. It is intended to give students a balanced view of theory and practice. In order to pass this course, you will need to demonstrate that you have learned to:

• correctly and precisely reason about times, events, and action
• list and reason about the sources of error and inexactitude in time interval measurement, execution time prediction, and scheduling
• empirically estimate the accuracy of a real time clock
• measure the execution time of a piece of code
• empirically estimate the accuracy and overhead of a real-time scheduler
• describe and apply commonly used abstract models and terminology for real-time scheduling and resource management
• recognize, classify, and formulate the hard and soft timing requirements of a software system
• select an appropriate software architecture and combination of scheduling techniques to satisfy a set of timing requirements
• understand and apply the proofs of the fundamental theorems of deadline and fixed priority real-time scheduling
• carry out schedulability analysis using deadline and fixed-priority approaches
• implement a set of tasks with periodic and aperiodic timing requirements, using C threads and a real-time variant of the Linux operating system
• evaluate the suitability of an operating system for real-time applications

As time permits, we will also look briefly at other aspects of real-time systems, including real-time programming languages (e.g., the Ada programming language), real-time operating systems, real-time data communications, etc.

Textbook

Author: Jane Liu

Title: Real-Time Systems ($80 at amazon.com)

Publisher: Prentice Hall

Table of Contents:

1. Typical Real-Time Applications
2. Hard Versus Soft Real-Time Systems
3. A Reference Model of Real-Time Systems
4. Commonly Used Approaches to Hard Real-Time Scheduling
5. Clock-Driven Scheduling
6. Priority-Driven Scheduling of Periodic Tasks
7. Scheduling Aperiodic and Sporadic Jobs in Priority-Driven Systems
8. Resources and Resource Access Control
9. Multiprocessor Scheduling and Resource Access Control
10. Scheduling Flexible Computations and Tasks with Temporal Distance Constraints
11. Real-Time Communications
12. Operating Systems

We will be using a subset of the above chapters in this course. The book is also a good reference to keep.

Other References

Class notes, assignments, and other information you need to read for the course will be provided on the Web, as the term progresses. Links to such information (direct or indirect) will be provided from the Course Home Page. You are expected to read it all.

Regarding the class notes: Initial versions of the on-line notes may sometimes be provided before class, but they will not be static. Expect them to be updated shortly before or after the corresponding class meetings.

If you don't already own one, it would be good to have a compact reference on ANSI C, such as Kernighan & Ritchie's The C Programming Language, or Harbison & Steel's C: A Reference Manual.

Readings.You will be assigned readings in the textbook. However, what we cover in class will not correspond exactly to the book. In class we will go into more depth on some things, and less depth on others.

Class Participation. The study of much of Computer Science is cumulative (i.e., understanding earlier material well is necessary to grasp later material. Do not allow yourself to fall behind, by postponing studying, and then figure you will jump ahead to catch up with the rest of the class.

Experience has shown a high correlation between absenteeism and low grades. Therefore, you are required to attend all class meetings. Attendance may be checked at random times throughout the term. You will be allowed three (3) absences without question or justification. If you have a documented religious holiday or emergency, additional absences may be excused.

Examinations.There will be a midterm examination and a final examination. These examinations will be "closed book". That is, no books or reference materials will be allowed in the examination room. These are the main check on how much you have learned from the course.

Examples of some questions from prior terms will be provided on the Web, with answers, so that you are prepared for the format of the exam and have a chance to review by taking a practice exam. You will also find the quizzes (see below) are helpful in preparation for the exams. (Please don't assume the examination will be limited to the sample questions!)

You will be expected to take the examinations at the scheduled time, shown on the course calendar.

If you know in advance of a reason you will not be able to take a scheduled examination you are responsible for making arrangements in advance with me. If you make prior arrangements, or have a documented last-minute emergency conflict -- such as a medical emergency or your employer requires you to make an out-of-town trip -- I will attempt to accommodate you. However, under no circumstances will a student be allowed to take an examination before the rest of the class. Also, it must be understood that we cannot give the same examination, and because of time constraints, I may administer a makeup examination of an entirely different format. In the past, most students who have missed midterm examinations have chosen not to take a makeup examination. Instead, they relied on a course policy that the midterm examination scores is replaced by the final examination score if the final examination is higher.

Quizzes/Homework. Short quizzes may be given occasionally, with or without advance warning. Occasional homework exercises may also be given, to which you may be asked to present a solution in class. They will both count toward your class participation score.

Programming assignments. There will be several programming assignments, using the C programming language and the Linux operating system. The objectives of the assignments will be to give you practice implementing some of the ideas and techniques you are reading about, and at the same time improve your programming skills. Besides code, some assignments may also include a written analytical component and/or report.

To do the assignments, you will be provided access to a collection of Linux sytems on which you will have the "root" password, in room 016 Love. You will also be provided access to some special hardware devices, which we call "gizmos".

Some assignments will be done individually and some will be done in teams.

For assignments that do not require access to special hardware you may use computers outside the 016 Love lab, as your own personal computer, provided you are willing and able to install Linux and RT Linux on them. (You might also try building your own gizmo, though no one has yet done that. More information on this topic is provided in separate on-line notes about the gizmos.) However, keep in mind that you will be required to demonstrate your work in the 016 Love lab. That means if you use another computer and gizmo you will need to bring them in for demonstrations.

More details on the assignments will be posted as the term progresses, on the assignments Web page.

You will learn better if you concentrate on understanding an doing, and do not worry too much about grades. Therefore, I hope you will not dwell on all the details in this section of the syllabus. I just give all these details because some students feel they must know.

Your final grade should reflect how much you learned from the course. Since you should be learning right up to the last minute, the final word on what you have learned should be the examination given at the end of the term. On the other hand, there are good reasons to mark other work you do during the term, and for all your work to play a role in the determination of your final grade. On reason is that I would like to motivate you to study every week, and to put in your best effort on all the programming exercises. I would also like for you to find out about any gaps in your learning before the end of the term, so you can fill them in.

In order for you to learn from your errors without losing motivation, the grading policies incorporate a certain amount of forgiveness. Specifically, if the final examination score is higher than the midterm examination score, it will replace the midterm examination score. For programs, though, I normally don't feel any forgiveness is called for. You have the opportunity to find and correct any serious errors you turn in your work, by executing tests. However, I reserve the right to offer additional forms of grade forgiveness for weak grades on work done early in the course if there is solid evidence that the student has mastered the material by the end.

Every piece of graded work will be assigned a score in the range 0 to 100. At the end of the term these numeric grades will be averaged to compute your final grade for the term, using the following table:

Percent Letter 91- 100 A  [4.00] 89-90 A- [3.75]

Percent Letter 85-88 B+ [3.25] 81-84 B  [3.00] 79-80 B- [2.75]

Percent Letter 75-78 C+ [2.25] 71-74 C  [2.00] 69-70 C- [1.75]

Percent Letter 64-68 D+ [1.25] 61-63 D  [1.00] 59-60 D- [0.75]

Percent Letter 0- 58 F  [0.00]

The following are the items that will be graded, and the weights they will be given:

Some of the assignments will probably be broken into installments, each due several days apart.

If the Final Examination grade is higher than the midterm examination average, the midterm examinations will be thrown out and the final examination score will be used to replace it.

This rule is based on the fact that the final examination is comprehensive, and is intended to motivate students who do not perform well on earlier exams to persevere and overcome those setbacks by further study. It also solves the problem of occasional emergencies which may cause a student to miss a midterm examination.

All graded work will be returned in class. Students who miss class are responsible for picking up their papers no later than one week after the start of the next semester. Work that is not picked up by then may be discarded. The one exception are final examinations. The University requires that the original copies of all final examinations be retained in the Department for two years.

Do not expect forgiveness for lateness. Whether to accept any late turn-ins of assignments will be entirely at my discretion. If a late assignment is accepted, the score may be reduced. The amount of the reduction will be entirely at my discretion, and may depend on how late the assignment is. In any case, no work will be accepted for grading after a solution is discussed or handed out, either in the class or on the Web.

You are required to read the FSU Academic Honor Policy (http://dof.fsu.edu/honorpolicy.htm) and abide by it. Take note that this policy not only puts you on your honor not to cheat. It requires that you report any cheating that you observe. First violations will result in lowering of the final course grade by one whole letter. Repeat violations will result in a grade of F with no provision for retaking the course.

I have learned that a few students need the following additional explanation, to clarify what is allowed and what is not allowed with respect to the kind of cheating that gives us the most trouble in CS courses, i.e., plagiarism.

I know that nearly all students are honest, have a well developed ethical sense, and don't need to be given such detailed instructions on what is allowed and what is not. However, because of University policy and a few past experience with students who tried to excuse cheating by complaining that the rules were not stated clearly enough, I have gradually been forced to draw sharper lines and go into more detail.

By turning in work for a grade in this course you are representing it as being entirely your own individual work. Unless otherwise specified in writing, all graded work (including all programming assignments) is expected to be done individually. If an assignment permits teamwork, it will be explicitly stated so in the assignment, and then the work is required to be only the work of the people on the team.

You may well ask "What does `individual work' mean? Shouldn't I make sensible use of references and prior art?". When a person has a question or a problem it is normal to search publications (including the Web) for information, ideas, and sometimes even code. However, there are intellectual property laws and academic ethics that restrict what you can do with the work of other people, and some still stronger restrictions on what you can do for assignments for this course. The following paragraphs are intended to explain these restrictions. However, I understand that I am dealing with distinctions that can sometimes appear to be fuzzy. If, after reading this section, you are still in doubt about whether something you are considering doing would be a violation of intellectual property law, academic standards, or the rules of the course, you should either refrain from doing it, or consult me for a ruling. Likewise, if you are unsure whether something you have observed is allowed, please do not hesitate to ask me.

It is important for all citizens, especially future writers and software development professionals, to understand the basics of intellectual property law. Computer software is subject to both copyright and patent law. Copyright law protects the representation of a written work, whether it be a photograph, drawing, diagram, text, or computer code. Copyright law says that all such works start out as owned by the original author and cannot be copied legally without permission of the owner. If you have permission to copy, you generally required to give credit to the copyright holder and a note saying that the work is reproduced with her/his permission. There is an exception for copying small amounts of text without permission, if you identify such quotations and give credit to the author, under a vaguely defined principle called "fair use". Patent law protects the ideas behind a work. It restricts what you can do with ideas you get from other people. If an idea is patented, you cannot use it at all without a license.

Unfortunately, simple statements about law -- like the ones above -- always turn out to be oversimplifications. That is the nature of the legal system. The laws are complex and are continually being modified by the actions of legislatures and courts. Every lawyer I've ever asked for legal advice has ended by saying he cannot predict the outcome if a case comes to trial, since the ultimate decisions are in the hands of the specific judge or jury. So, what should a person do? Do your best to gradually become better informed of the law. For example, you could read one or more of several intellectual property law tutorial's on the Web. Then, you should exercise conservative judgment. If you are in doubt about whether what you are about to do would be a violation of intellectual property law, you should either refrain from doing it, or consult a lawyer to get clarification.

Scholarly ethics start with the law, and go further. Academic ethics require that if you use information or ideas obtained from the work of another person you must at least give proper credit to the original author, identifying what you have used, where you obtained it, and who is the person to whom credit is due. Failure to give proper credit or properly indicate uses of someone else's work is plagiarism, which is a violation of the Academic Honor Policy. Giving credit means citing the source of the information in the body of the paper (or program) at the point where it is used, and then including a full citation for the source in a list of references at the end of the paper (or program). Further, if any material -- and this includes diagrams and computer code, as well as text -- is used verbatim, it must be clearly identified as quoted text, with a citation of the original source. Normal practice is to use quote-marks around the quoted text in a paper (special delimiting comments for code), with a number or abbreviation for the in-line citation, referring to an entry in a list of the full citations at the end of the document. For a more detailed explanation of plagiarism, I suggest you read FSU Political Science Professor Dr. Paul Hensel's Web page on plagiarism and proper citation practices http://garnet.acns.fsu.edu/~phensel/citation.html.

In the context of this course -- because assignments are used to assess what you have learned, and because even a few lines of code may represent a great deal of creative thought -- we must adhere to a higher standard for originality and independence of assignments than you may have found for the work in some other courses.

• For individual assignments in this course, you are required to design and write your own solutions. You are not allowed to show your solution to an assignment to another person or to read the solution of another person other than myself (the instructor of this course). For team assignments, the same applies to anyone outside your team.

• You may not put more than two (2) lines of material (code or text) from a solution to an assignment in any public message (e.g., discussion forum or chat room).

• You are responsible for taking steps to protect your work, including setting the permission bits on the directory containing your work (code or text) to make unreadable to anyone except yourself, not leaving a workstation where you are logged in unattended (someone might step up and read your work or print out a copy), and not leaving printouts of your work in the printer or a public wastebasket. This also means you cannot send all or part of your solution to an assignment to another student by e-mail, or post them on a discussion group. If another student leans over your workstation to read what you are doing, tell them to back off, and contact the lab monitor if they persist in trying to read what you are doing.

• The only material written by another person that you may reuse in a program, homework, or other paper that you turn in for grade are the following:

  1. Material that I provide for students in this course, this term, in a public forum, provided you clearly identify the material that is quoted and where it came from. (Material quoted from other courses, or prior offerings of this course may not be used.)

  2. Code you found in a textbook used in a course you have taken, provided you clearly identify the code as reused and include a citation of the textbook in your comments.

  3. Material you found published on the Internet, provided you mark it clearly as reused, include the URL in a comment, and the Web site where you found it has a clear statement giving permission for anyone to reuse the material.

• If you reuse material of type (2) above, limit yourself to comparatively short blocks of quoted material. Excessively long quotations from a textbook may violate the "fair use" provision of the copyright law, and in any case are considered poor academic practice. The same is true of excessively long quotations of text in a research paper. Moreover, the purpose of the assignments in this course is for you to practice your own writing and programming skills. Therefore, you will not get credit for a product that relies on an excessive amount of quoted material.

• The only libraries you may link in with programs you turn in are standard libraries provided with Linux, which are available on the systems provided by the CS Department for you to do your assignments.

Failure to follow these rules will be considered a violation of the Academic Honor Policy. The first detected violation will result in a negative score, of -100% A second detected violation will result in a grade of "F" for the course, with no possibility of taking the course for grade forgiveness.

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
874 Traditions Way
108 Student Services Building
Florida State University
Tallahassee, FL 32306-4167

e-mail: sdrc@admin.fsu.edu
http://www.disabilitycenter.fsu.edu
phone: (850) 644-9566 (voice)
phone: (850) 644-8504 (TDD)

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.

You are required to verify that your e-mail address is included in the class e-mail list. I will send everyone a message at the start of the term. If you don't get that first message, make sure you are added to the list.

Check regularly for electronic mail sent to you containing information about this course. You are also encouraged to use e-mail to ask questions and report problems. As a student in Computer Science you have at least two computer and e-mail accounts at FSU:

• A general FSU student login, good on "garnet.fsu.edu" and "mailer.fsu.edu".
• A CS Department login, good on most computers inside the department.

Because of past problems with impersonation, I may not reply to e-mails related to this course from other e-mail addresses.

So that you receive all e-mail promptly, you should have set up automatic e-mail forwarding from one of these accounts to the other, or from both of them to whatever other place you normally read e-mail.

This syllabus and other information, such as course announcements, assignments, lecture notes, and some useful links to other Web sites, will be posted on the CS Department's Web site for the course, which is located at http://www.cs.fsu.edu/~baker/realtime. Access to most of the materials on that site will require a special login name and password, which will I will provide to you via e-mail.