Home | | Schedule | | Assignments | | Lecture Notes
Part 1: Driver (30 points) due: Friday, April 1
Part 2: FCFS simulator (40 points) due: Friday, April 15
Part 3: SRTN simulator (30 points) due: Friday, April 29
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:Input Formatsim [-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.Output Format
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: 0Process 2:
service time: 32 units
I/O time: 3 units
turnaround time: 45 units
finish time: 45 units
arrival time: 5Process 3:
service time: 102 units
I/O time: 15 units
turnaround time: 135 units
finish time: 140 units
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:
Part 2, Implementation of the FCFS scheduler.
Part 3, Implementation of the SRTN scheduler.
For parts 2 and 3 include:
You are encouraged to discuss the problem with fellow students.
You are not allowed to share code with any other student.
Part 1, The driver:
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: February 10, 2005
Page Expires: January 8, 2006