Topic 3: SIMULATION: REAL-TIME JOBS SCHEDULING ALGORITHMS COMPARISON

Overview:


In this project, you'll implement and evaluate the following three different real-time jobs scheduling algorithms by writing a REAL-TIME JOBS SCHEDULING simulator.

Rate Monotonic Scheduling Algorithm
The rate-monotonic scheduling algorithm schedules periodic tasks using a static priority policy with preemption. If a lower-priority process is running and a higher-priority process becomes available to run, it will preempt the lower-priority process. For each process, its priority=1/pi(inverse of the period).

Deadline Monotonic Scheduling Algorithm
Deadline Monotonic Scheduling Algorithm schedules periodic tasks or aperiodic tasks using a static priority policy with preemption. For each process, its fixed priority = 1/di(inverse of the relative deadline). That is, the shorter the relative deadline, the higher the priority.

Earliest-Deadline-First Scheduling algorithm
Earliest-Deadline-First scheduling dynamically assigns priorities according to deadline. The earliest the deadline, the higher the priority.
Algorithm: At each moment of time t, schedule the task whose deadline is closest to t. Ties can be resolved arbitrarily.


Your Task

Given a set of periodic processes to be scheduled, your Real-time Jobs Scheduling simulator should simulate the execution of these processes based on a given real-time scheduling algorithm. Your simulation should collect the following statistics: Feasibility(Can you produce a feasible schedule by the algorithm?), at what time scheduling fail, and CPU utilization.

Your simulation structure should be event-driven simulation, which is the most common simulation model. At any given time, the simulation is in a single state. The simulation state can ONLY change at event times, where an event is defined as an occurrence that MAY change the state of the system. Events in this CPU simulation are the following: process arrival and the completion of the current running processrs.

Each event occurs at a specified time. Since the simulation state only changes at an event, the clock can be advanced to the next most recently scheduled event. (Thus the term next event simulation model.)

Events are scheduled via an event queue. The event queue is a sorted queue which contains "future" events; the queue is sorted by the time of these "future" events. The event queue is initialized to contain the arrival of the processes and the first occurrence of the timer interrupt. The main loop of the simulation consists of processing the next event, perhaps adding more future events in the queue as a result, advancing the clock, and so on until all processes terminate.

In the end, you should compare the following scheduling policy:

1. Rate Monotonic Scheduling Algorithm(RM)

2. Deadline Monotonic Scheduling Algorithm(DM)

3. Earliest-Deadline-First Scheduling algorithm(EDF)




Since these processes are periodic tasks, so they won't stop coming. You can set a time limit for your program to run. if the time limit comes, your program will be stopped. You can set this time limit to be a large number, you can also set this time limit to be a time point where the same schedule will repeat. Please refer to your class note for this calculation.

Simulation Execution



Your simulation program will be invoked as: sim [-d] [-v] [-a algorithm] < input_file where -d stands for detailed information, -v stands for verbose mode, and -a stands for the execution of a given algorithm(only RM, DM, EDF should be acceptable input). You can assume only these flags will be used with your program, and that they will appear in the order listed. The output for the default mode (i.e., no flags), the detailed information mode, the verbose mode, and the algorithm is defined in the output format section. The -d, -v, and -a flags may be used separately or together.

Input Format


The simulator input includes the number of processes that require execution, the process switch overhead time (i.e., the number of time units required to switch to a new process), and, for each process, the arrival time, the relative deadline and period



You should assume the processes listed in the input file will be in the order that the processes arrive. All these simulation parameters are integers. Your simulator obtains these parameters from the input file, which is in the following format.

   number_of_processes process_switch
   process_number arrival_time  relative_deadline  period
   process_number arrival_time  relative_deadline  period
   .
   .
   .
 


The following is an example input file to the Real-time Scheduling simulation:

 
        4 0
        1 0 4 6
        2 0 5 10
        3 0 5 12
        4 0 7 20

You should create your own input file. Your program should generate at least 5 processes. You can assume the process switch overhead is 0 and 5 time units respectively. When you compare RM, DM and EDF algorithms, you can assume all the processes arrive at time 0. When you compare DM and EDF algorithm, you can assume all the processes arrive at different time and assume the arrival interval of the processes is exponential distribution with the mean of 20 time units. For each process, the average of CPU burst should be uniformly distributed on 30 to 100 time units; the deadline of each process should be greater than its CPU burst, you can get the deadline by adding the process's CPU burst and a number x, and x is uniformly distributed on 0 to 500; the period of each process should be greater than its relative deadline, you can get the period by adding the process's relative deadline and a number y, and y is uniformly distributed on 0 to 1000.

 

Output Format



In default mode (i.e., no flags are given), the output of the simulator consists of feasibility, the total time required to execute the processes to completion and the CPU utilization for each of the scheduling algorithms. As an example:



$sim < input_file


Rate Monotonic Scheduling Algorithm(RM):
There is no feasible schedule produced.

Deadline Monotonic Scheduling Algorithm(DM):
There is feasible schedule produced.
Total Time required is 2023 time units
Average CPU utilization is 85%


If information on only one scheduling algorithm is desired, then the algorithm flag (i.e., -a) should be given with the name of the scheduling algorithm for which output is desired: RM, DM or EDF. As an example:



$sim -a RM< input_file


Rate Monotonic Scheduling Algorithm(RM):

There is feasible schedule produced
Total Time required is 232 time units
CPU Utilization is 62.5%


In detailed information mode (i.e., -d flag is given), the output of the simulation consists of the total time required to execute the input processes to completion, the CPU utilization, and the arrival time, service time, relative deadline, period for each process. In the following example, this information is shown for DM only. If the scheduling algorithm is not specified, then detailed information should be given for each scheduling algorithm.



$sim -d -a DM < input_file


Deadline Monotonic Scheduling Algorithm(DM):

There is not a feasible schedule. Schedule can be feasible from time 0 to 320 units. At time 320 units, process 1 missed the deadline. from 0 to 320, Total CPU time required is 295 units
CPU Utilization is 92.2%

Process 1:

arrival time: 0
service time: 45 units
relative deadline: 80 units
period: 100 units
finish time: 75 units, 175 units


Process 2:

arrival time: 20 units
service time: 30 units
relative deadline: 50 units
period: 100 units
finish time: 50 units, 150 units, 265 units

Process 3:

arrival time: 200
service time: 35 units
relative deadline: 40 units
period: 120 units
finish time: 235 units

.
.
.  

Process 5:

arrival time: 400
service time: 70 units
relative deadline: 300 units
period: 400 units
finish time:

In verbose mode, the output of the simulation includes the scheduling decisions and the switching of the processes. Specifically, the output includes every event that occurs, the time of the event, and the state transition:


At time X: Process {id} is preempted by process {id}

Be sure to include events that occur at the same time.

Submit:

Write a 2-3 page paper describing your project, what problems you've faced and how you've overcome them. In your opinion, what is the best scheduling algorithm if switch overhead is 0? What is the best scheduling algorithm if switch overhead is not 0? What are practical limitations on that algorithm?

What to submit:

Submit your test data.

Submit ALL source code with detailed instructions on how and where to compile it, and how to make it run. You should submit a Makefile to build your code under GCC, Java, or whatever language you use. Note that Visual C++ also supports Makefiles, so if you use that, you can still export a makefile. I will test some of the code to make sure the numbers are not imagined.

Submit traces of execution (the trace of execution of each algoirthm; each algorithm in separate files, etc.).

Submit your findings about each algorithm; average numbers (CPU utilization, etc.) (in addition to your 2-3 page paper)

Submit your paper describing the project.

Submit a file named: description.txt that describes what and where all the information is stored. (which file does what, which file contains results of which method, etc.). This is mostly so that I don't get lost in your project directory.

Note: All descriptions and text should be in TEXT format. If something "has" to be formated, use PDF.

You may use any language(c, c++ or Java) you wish, but you need to document what language you're using and how to compile code somewhere in your submission. Also comment your code! If I can't read it, it's wrong!

When submitting, you're very likely to have many files. You can compress them into a tar.gz or zip and submit that.

Tips: For many of you, this will be the biggest project you've ever worked on. It helps to organize the code from the start, to document everything, etc. Make the code readable (not just for you, but for me as well). Modularize your code. Work on 1 thing at a time. Start by generating the data and placing it in some file. Then implement basic algorithms and data structures like lists, sorting, etc. Then implement Rate Monotonic Scheduling Algorithm, make sure that works well, then implement Deadline Monotonic Scheduling Algorithm, probably reusing some parts of the Rate Monotonic Scheduling algorithm code, etc.

And most importantly: Organize and design the project and know what you're doing before you start coding. (and don't wait until the last weekend to do it).

Good Luck!