Advanced Rate-Monotonic Schedulability Test (grad students)

For rate-monotonic scheduling, two simple schedulability tests are usually used. One of them is necessary but not sufficient. The second is sufficient but not necessary. There is a third schedulability test that is more complex but has the advantage of being necessary and sufficient to prove that a rate-monotonic schedule is feasible. The third test passes task data sets which use a higher percentage of the processor than allowed by the second test.

Details of the third test are in the paper contained in the myCourses Content section. The test is detailed on page 12 as RMS Theorem 2.

An exercise for the graduate students will be to write a program that performs the three schedulability tests on a set of tasks. Each task in the set should have three characteristics specified: compute time, period, and deadline. With the assumptions that we are making, the period and deadline will always be the same. Input for your program should come from standard input. The output should show the results of each schedulability test. You can specify the format for the input data. You can write the program in whatever language you would like as long as it can run on the machines in the classroom.

Once you have written the program, you will develop "interesting" task data sets for the scheduling experiments. An "interesting" data set is one that fails the second rate-monotonic schedulability test (sufficient but not necessary) but passes the third schedulability test (necessary and sufficient). Create a minimum of three diverse task data sets.

Create a zip file called rma.zip which includes the following:

• The source files for your program
• An executable version, i.e. .exe or .jar, of your program if one is needed.
• A set of instructions for how to run your program, and how to rebuild it if it is compiled.
• A text file with your data sets. Introduce each task data set with a line of the format:

Data set #: number time-unit

where # is a number identifying the data set, number indicates the number of tasks in the data set, and time-unit indicates the units for the task times, i.e. seconds, milliseconds, or microseconds. Each following line defines one of the tasks in the data set. Define each task with three numbers: compute, period, and deadline. Put a blank line between each data set. TODO: This can use adjusting: time-unit is mostly irrelevant, don't need period and deadline since they are equal; for each data set indicate the result of the three tests; for the first two provide the utilization and the comparison value for test 2; indicate the reulst of each test and the overall schedulability of the tasks;

Submit this zip file in the Advanced Rate-Monotonic Schedulability Test dropbox in myCourses before the due time.

Note: undergraduate students can complete this assignment for 3 points of extra credit.