Operating Systems--Spring 2011

Home | | Schedule | | Assignments | | Lecture Notes

Project 3: CPU Simulator

Part 1: Driver (30 points) due: Thursday, April 7
Part 2: FCFS simulator (40 points) due: Thursday, April 19
Part 3: SRTN simulator (30 points) due: Thursday, May 5

In this project, you'll implement and evaluate the following three different CPU scheduling algorithms using a CPU simulator. You will complete this project in three parts as described below, with 2 weeks allocated for each part of the project.

First Come First Serve (FCFS)
As we know, the first come first serve algorithm is effective in batch type systems. (In time share systems, the algorithm is unfair to processes with short bursts.) In this algorithm, the process at the head of the queue is allowed to execute until it voluntarily leaves the CPU due to either termination or an I/O request. In other words, the first come first serve algorithm is a non-preemptive CPU scheduling algorithm.

Shortest Remaining Time Next (SRTN)
The shortest remaining process next scheduling algorithm is a priority based scheduling algorithm that is preemptive. With this scheduling algorithm, the process in the ready queue with the shortest execution time is chosen to execute. If a "new process" arrives in the ready queue with a CPU service time less than the remaining time of the current process, preempt.

Your Task

Given a set of processes to execute with CPU and I/O requirements, your CPU simulator should simulate the execution of these processes based on a given CPU scheduling policy. Your simulation should collect the following statistics: the CPU utilization (NOT CPU efficiency), the total time required to execute the set of processes, and the service time (or CPU time), I/O time, and turnaround time for each individual process.

Your simulation structure should be a next event simulation. The next event approach to simulation 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 transition of a process state (e.g., when an interrupt occurs due to a time slice, the process moves from running state to ready state).

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.

There is code available in the in the ~csci346/projects/project3 directory which should help you in creating your next event simulation. Specifically, check out nextEvent.cc, nextEvent.h, list.cc, and list.h. You will use these in parts 2 and 3 of the project.

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 FCFS, and SRTN 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 mode is defined in the output format section. The -d, -v, and -a flags may be used separately or together.

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 and the number of CPU execution bursts the process requires; the CPU execution bursts are separated by time the process does I/O.

You should assume an infinite number of I/O devices. In other words, processes do not need to wait to do I/O. Also, no overhead is associated with placing a process on, or removing a process from, an I/O device. Also, you should assume the processes listed in the input file will be in the order that the processes arrive. Since a process must exit from the system while in the executing state, the last task of a process is a CPU burst. All these simulation parameters are integers. Your simulator obtains these parameters from the input file, which is in the following format. You can assume the data in an input file is valid.

   number_of_processes process_switch
   process_number arrival_time  number1
   1   cpu_time io_time
   2   cpu_time io_time
   .
   .
   number1   cpu_time
   process_number arrival_time  number2
   1   cpu_time io_time
   2   cpu_time io_time
   .
   .
   number2   cpu_time
   .
   .
   .
 

The following is an example input file to the CPU simulation:

 
        4 5
        1 0 6
        1 15 400
        2 18 200
        3 15 100
        4 15 400
        5 25 100
        6 240
        2 12 4
        1 4 150
        2 30 50
        3 90 75
        4 15 
        3 27 4
        1 4 400
        2 810 30
        3 376 45
        4 652
        4 28 7
        1 37 100
        2 37 100
        3 37 100
        4 37 100
        5 37 100
        6 37 100
        7 37 

There are several data files in the ~csci346/projects/project3 directory that you may use for testing purposes.

In default mode (i.e., no flags are given), the output of the simulator consists of 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

First Come First Serve:

Total Time required is 269 time units
CPU Utilization is 85%

Shortest Remaining Time Next:

Total Time required is 257 time units
CPU Utilization is 84%

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: FCFS or SRTN. As an example:

$sim -a FCFS < input_file

First Come First Serve:

Total Time required is 269 time units
CPU Utilization is 85%

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, I/O time, turnaround time, and finish time for each process. In the following example, this information is shown for SRTN only. If the scheduling algorithm is not specified, then detailed information should be given for each scheduling algorithm.

$sim -d -a SRTN < input_file

Shortest Remaining Time Next:

Total Time required is 140 units
CPU Utilization is 100%

Process 1:

arrival time: 0
service time: 32 units
I/O time: 3 units
turnaround time: 45 units
finish time: 45 units

Process 2:

arrival time: 5
service time: 102 units
I/O time: 15 units
turnaround time: 135 units
finish time: 140 units

Process 3:

arrival time: 10
service time: 22 units
I/O time: 3 units
turnaround time: 45 units
finish time: 55 units

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} moves from {state} to {state}

Each state transition should be given as above on a separate line. (Be sure to include events that occur at the same time.) Since we do not include swapping in our simulation, the state of a process can only be in one of five states: new, ready, running, blocked, or terminated.

Part 1: Implement the driver and the input module for the whole CPU simulation. This driver should be in one file, named driver.cc and should include the main( ) function for your entire program. The driver, as discussed above, should:

• enable the user to execute ONE scheduling algorithm or BOTH scheduling algorithms based on the given command line.
• set appropriate flags for the type of output desired (default, detailed or verbose). This will be the longest part of this part of the project, because you must take into account all the possible combinations of flags. E.g. if argc is 3 (2 arguments in addition to the program name) it could mean the flags are (-d -v) or (-a algorithm).
• read in the first line of data to determine the number of processes and the switch time.
• read in the rest of the data for each process. You will need to think carefully about what data structure you will use to store the process information. Will you have a process class that has linked lists to hold the information for each CPU and I/O burst time? Will you have statically allocated memory or dynamically allocated memory to hold this information? list.cc and list.h may come in handy here. Remember that you will pass this information to the scheduler by way of parameter passing, so you need to limit the number of separate variables that you need to pass. Also, you will not know in advance how many processes and how many CPU and I/O bursts each process will have.
• call the appropriate scheduling algorithm or algorithms and pass whichever parameters are appropriate (e.g. output flags, number of processes, the data structure(s) containing the process information, etc.) Note that you do not need to implement these functions yet. Simply provide empty function stubs to test your driver (or include cout statements to make sure the correct one is running with the correct flags).

Part 2, Implementation of the FCFS scheduler.

Part 3, Implementation of the SRTN scheduler.

For parts 2 and 3 include:

• A short essay (2-3 paragraphs) that explains how your solution works and any assumptions you made. (If you make any assumption because you think the problem is not well specified, make sure to discuss these assumptions.) Be sure to explain what does not work in your implementation.
• If the driver to your simulation does not function as the specifications above request, then include information to execute each individual scheduling algorithm without using a driver.

You are encouraged to discuss the problem with fellow students. You are not allowed to share code with any other student.

Turning in your project:

Part 1, The driver:

• Turn a hard copy of your driver.cc program by Thursday, April 7 in class.
• If you use any associated files (e.g. list.h and list.cc), note that in the program header of your printout. If the files are not the ones provided in the project3 directory, include printouts of the files you used.
• Before class, submit a soft copy of driver.cc by typing:
  ~csci346/bin/submit csci346 proj3part1
• If you used files other than those provided in the project3 directory or the driver.cc file, check the submit instructions by typing:
  ~csci346/bin/submit -h
  Make sure to submit all your extra files according to the instructions.

Part 2, Implementation of the FCFS scheduler.

Part 3, Implementation of the SRTN scheduler.

Constance Royden--croyden@mathcs.holycross.edu
Computer Science 346--Operating Systems
Date Created: January 9, 2004
Last Modified: March 23, 2011
Page Expires: January 8, 2012