Experiments with Real-Time Scheduling Algorithms

In this project, you will implement several real-time scheduling algorithms and experiment with their use. You will implement a rate-monotonic schedule, earliest deadline first, and either least slack time or shortest completion time schedulers. Run your implementation on QNX on the purplebox targets.

The standard scheduler in QNX is a fixed priority scheduler. At the same priority, the default is non-preemptive scheduling. (Using this scheduler testing a rate-monotonic schedule should be rather straightforward.) You can change this to time-sliced preemptive scheduling within the priority if you need that type of scheduling. Bring up Help -> Help Contents. The sections under getting started with QNX Neutrino have some very helpful information about scheduling and timers.

For the other schedulers, which are dynamic priority schedulers, you will need to do more work. There is no direct access to the QNX scheduling mechanism. You will have to create a task which serves the role of a proxy scheduler. This task has the responsibility to decide which task should run next. This task, which acts as your scheduler, will need to run at a higher priority than any of the tasks being scheduled. You will have to figure out when to run this task, i.e. what is the next scheduling point, and how to get it to execute at that time.

You will need to develop a mechanism to create tasks that have specific compute times and are run at their periodic rate. The compute time must actually use processor cycles and not do a sleep for a period of time. Sleep will not use any processor resources. Once you have a method to spawn tasks with specific characteristics, you will need to build into your scheduler the way to release a specific task for execution when it has the highest priority. For your experiment with the rate-monotonic schedule, the QNX scheduler will do that for you. For the dynamic priority schedulers, your proxy scheduler task will have to do the release.

Note: it is quite common to see the sleep function, or its variants, used in the first real-time programs that developers build. This is a bad habit in the making. Any use of sleep-like functions in your scheduling test fixture must get explicit instructor approval, i.e. be ready to justify why this is the only reasonable way to accomplish what you need to do.

Create several sets of tasks and study the characteristics with each scheduler. Experiment with task sets that pass the schedulability tests and some that do not.

Following are some sample data sets, it is HIGHLY recommended to also create some of your own datasets to be confident in your implementations.

• Set 1: (1,7,7), (2,5,5), (1,8,8), (1,10,10), (2,16,16)
• Set 2: (1,3,3), (2,5,5), (1,10,10)
• Set 3: (1,4,4), (2,5,5), (1,8,8), (1,10,10)

TODO: measure jitter of task burn times, and adjust for that; specify some minimum performance values to analyze so comparisons between teams can be made; how to capture the full set of data using search; provide several task sets to run; provide mechanism for public display of data from standard test sets; description of user events and other time keeping; early submission of data analysis approach.

You will submit a zip file that includes the following items:

1. Experimental report. You will present your experimental results in a report. There are several items that need to be in this report of your experimental results. This report should be a Word or PDF file called Report.doc or Report.pdf. Please place it in the top-level directory of files in the zip file.
   1. A description of your test fixture setup and procedure with particular attention to how you implemented the dynamic priority changing.
   2. Results of your data analysis for each of your task data sets. This should include listing the task characteristics, and the resulting analysis of the data for that data set. An analysis might include number/percent of deadlines met, average computation time, jitter on start and end of computation, jitter on computation time, analysis of QNX overhead, etc.
   3. Analysis of schedulability. Do the theory and experimental results match?
   4. How much overhead does your scheduler add to the system? Brainstorm some ideas for how to improve this. Why would you choose one scheduler over another?
   5. Analysis of failure. How do these schedules react to an unschedulable task set? Real-time systems need to be predictable even in the face of situations that are outside of the system design limits. Can you predict anything about how the system will fail when it is overloaded? Are failures isolated or do they ripple through the entire system?
   6. Other stuff. You will need an introductory section and a section with your conclusions from running this experiment.
2. Raw data. If you analyzed your data in Excel include the spreadsheets with the raw data and your analysis. Use separate worksheets for different data sets or separate Excel workbooks. Identify the columns and add commentary as you think is appropriate. Please place these files in a directory named data.
3. Test fixture code. Submit the C, C++ and include files for your test fixture. Do not include any object files or other QNX project files. Please place these code files in a directory named code.

Before the submission dropbox closes, deposit a zip file in the dropbox. Put your report in the directory at the top-level of this zipfile along with your data and code subdirectories. To facilitate the instructor's processing of your submission, please name this file schedule.zip and record all team member names in the comments section of the submission.

Grading

Your work will be evaluated using this grading rubric.