COMP 737: Real-Time Systems

Projects

Each student must complete a class project. You are responsible for defining your own project. Your project can be either an experimental investigation or a survey or research paper. The project must be a fairly significant piece of work. Students are encouraged to take on projects that involve experimental efforts or proving new results (or both). Survey papers should be considered an option of last resort --- if you take this option, your survey paper should be fairly extensive. It would also be much preferable to survey research that is more "cutting edge" rather than work from 10 or 20 years ago. As an example, I would consider a paper that discusses to what extent existing timing analysis results can be applied on newly available (and proposed) multicore platforms as quite interesting.

It is prefectly fine to use research from an RA position as the basis for your class project. However, your project may not be based on work from another course without the permission of me and the instructor for that course (permission will be granted only if the total work involved is commensurate with the amount of effort expected in both courses combined). Two-person projects may be permitted, provided the total work involved is about twice that of the typical single-person project.

Project Proposals

You must have your project approved. The process is as follows.

1. Email me a one- or two-paragraph description of your proposed project.
2. If approved, go to step 3. Otherwise, go to step 1.
3. Write a short proposal (about 3-5 pages) that provides more detail. This document will serve as our "contract" for the project.
4. Conduct your research or implement your project.
5. Write a technical report (about 15 pages, though it may be longer) describing your research or project and the results you obtained.

Step 1 (approved) should be completed by March 1 (the last class before spring break). Step 3 should be completed by March 27. If possible, you should try to complete Step 3 earlier than this, as it leaves more time for getting all the work done. Your final report is due on April 24 (our last day of class). Steve Goddard has put together a nice webpage on paper formats. Please have a look at this webpage before writing your proposal or final report. I'm quite picky about writing and will grade accordingly.

Projects Ideas

I encourage you to come up with your own project ideas. However, for those of you panicking because you cannot come up with a project idea, here are some projects you might consider.

• Solve one of the open problems in the intractability notes.
• Devise tight (as possible) scheduling conditions for tasks that self-suspend. Consider special-case task sets like harmonic tasks. Factor into the analysis contention for resources (like disks) that occur during suspensions. Identify those variants of the problem that are intractable.
• Conduct a simulation study to compare the various scheduling schemes we've considered in class when real system overheads are considered. Base your overhead parameters (e.g., context-switch times) on measurements taken on real systems. Factor in every conceivable overhead you can think of. Develop "rules of thumb" that indicate which scheduling scheme is preferable under which conditions.
• Implement some fair scheduling algorithms on a multiprocessor system and conduct experiments to assess the degree of fairness ensured in practice.
• Convert a real-time graphics application implemented using a single control loop to a real-time task set and compare the two implementations.
• Implement various approaches for implementing shared resources on a multiprocessor. Experimentally determine which approach is best under various conditions.
• Build a simulator environment that can generate random task sets and simulate task executions under a variety of scheduling algorithms. Consider doing this for multiprocessor scheduling algorithms as well. It would be great if the simulator could graphically depict schedules and allow the user to step through them.
• Implement one or more of the approaches discussed in class for mixing real-time and non-real-time applications. Conduct experiments to determine if real-time guarantees are met, and compare the various approaches to see if there is any real difference in non-real-time response times.
• Consider issues that might arise in embedded systems in which available memory is very restricted. How does this affect how shared resources are implemented? Can you derive bounds on how much memory an application uses? Does one scheduling discipline require less memory than another? Consider also system-on-a-chip multiprocessors.
• Implement a multimedia application using various real-time scheduling disciplines. Determine the advantages and shortcomings of each discipline.
• Conduct a comprehensive comparison of preemptive and non-preemptive schemes that factors in differences in executions costs with and without preemption. Conclude by producing definitive statements regarding when each approach will work best. Consider investigating multiprocessor scheduling schemes as well, and also systems with non-independent tasks.
• Devise useful benchmark applications or task sets for testing real-time scheduling schemes. You will need to defend that your applications exhibit a range of interesting behaviors. Devise benchmarks for both uniprocessor and multiprocessor systems, for both hard and soft real-time systems, and for systems that also may have non-real-time components. It would be especially interesting to know what would be a "typical" range for execution costs on modern processors. Determining this would involve looking at and thinking about some real applications.