1 Objectives

This programming project is to simulate a few CPU scheduling policies discussed in the class. You will

write a program in C to implement a simulator with different scheduling algorithms. The

simulator selects a task to run from ready queue based on the scheduling algorithm. Since the project intends

to simulate a CPU scheduler, so it does not require any actual process creation or execution. When a task

is scheduled, the simulator will simply print out what task is selected to run at a time. It outputs the way

similar to Gantt chart style.

2 Description

The selected scheduling algorithms to implement in this project are 1) First Come First Serve (FCFS), 2)

Round Robin (RR), and 3) Shortest Remaining Time First (SRTF). The detailed algorithms are already

described in class slides and textbook Chapter 6.

2.1 Task Information

The task information will be read from an input file. The format is

pid arrival time burst time

All of fields are integer type where

pid is a unique numeric process ID

arrival time is the time when the task arrives in the unit of milliseconds

burst time the is the CPU time requested by a task, in the unit of milliseconds

The time unit for arrival time, burst time and interval is millisecond.

2.2 Command-line Usage and Examples

Usage: proj2 input file [FCFS|RR|SRTF] [time quantum]

where input file is the file name with task information. FCFS, RR, and SRTF are names of scheduling

algorithms. The time quantum only applies to RR. FCFS is nonpreemptive, while RR and SRTF are all

preemptive. The last argument is needed only for RR. (See following table for more examples)

1

Examples Description

proj2 input.1 FCFS FCFS scheduling with the data file input.1

proj2 input.1 RR 2 Simulate RR scheduling with time quantum 2 milliseconds (4th

parameter is required even for quantum 1 millisecond) with the

data file input.1

proj2 input.1 SRTF Simulate SRTF scheduling with the data file input.1

2.3 Sample Inputs and Outputs

Sample input files and expected outputs are shown in Appendix. You can use it to verify your results.

3 Requirements

The project requires to simulate FCFS, RR, and SRTF scheduling for given tasks and to compute the average

waiting time, response time, turnaround time and overall CPU usage. You can find their definitions in

textbook.

1. Implement scheduling algorithm for FCFS, RR, and SRTF. The program should schedule tasks and

print progress of task every unit time (millisecond) as shown in sample outputs.

2. Print statistical information. As soon as all tasks are completed, the program should compute and

print 1) average waiting time, 2) average response time, 3) average turnaround time and 4) overall

CPU usage.

Note: if you use static array to implement ready queue structure, you can assume the maximum queue

length is 20.

4 Suggested Methodology

1. Implement one scheduling algorithm at each step

2. You can use circular linked list as a queue structure

3. You can use a data structure similar to PCB for each task, though it will be much simpler

7. Appendix: about input file and output information by CPU scheduling simulator

for FCFS, RR, and SRTF

% more input.1

1 0 10

2 0 9

3 3 5

4 7 4

5 10 6

6 10 7

% proj2

Usage: proj2 input_file FCFS|RR|SRJF [quantum]

% proj2 input.1 FCFS

Schdeuling algorithm: FCFS

Total 6 tasks are read from "input.1". press 'enter' to start...

==================================================================

process 1 is running

process 1 is running

process 1 is running

process 1 is running

process 1 is running

process 1 is running

process 1 is running

process 1 is running

process 1 is running

process 1 is running

process 1 is finished.......

process 2 is running

process 2 is running

process 2 is running

process 2 is running

process 2 is running

process 2 is running

process 2 is running

process 2 is running

process 2 is running

process 2 is finished.......

process 3 is running

process 3 is running

process 3 is running

process 3 is running

process 3 is running

process 3 is finished.......

process 4 is running

process 4 is running

process 4 is running

process 4 is running

process 4 is finished.......

process 5 is running

process 5 is running

process 5 is running

process 5 is running

process 5 is running

process 5 is running

process 5 is finished.......

process 6 is running

process 6 is running

process 6 is running

process 6 is running

process 6 is running

process 6 is running

process 6 is running

process 6 is finished.......

All processes finish ....................

============================================================

Avarage cpu usage : 100.00 %

Avarage waiting time : 14.17

Avarage response time : 14.17

Avarage turnaround time: 21.00

============================================================

% proj2 input.1 RR 2

Schdeuling algorithm: RR

Total 6 tasks are read from "input.1". press 'enter' to start...

==================================================================

process 1 is running

process 1 is running

process 2 is running

process 2 is running

process 1 is running

process 1 is running

process 3 is running

process 3 is running

process 2 is running

process 2 is running

process 1 is running

process 1 is running

process 4 is running

process 4 is running

process 3 is running

process 3 is running

process 5 is running

process 5 is running

process 6 is running

process 6 is running

process 2 is running

process 2 is running

process 1 is running

process 1 is running

process 4 is running

process 4 is running

process 4 is finished.......

process 3 is running

process 3 is finished.......

process 5 is running

process 5 is running

process 6 is running

process 6 is running

process 2 is running

process 2 is running

process 1 is running

process 1 is running

process 1 is finished.......

process 5 is running

process 5 is running

process 5 is finished.......

process 6 is running

process 6 is running

process 2 is running

process 2 is finished.......

process 6 is running

process 6 is finished.......

All processes finish ....................

============================================================

Avarage cpu usage : 100.00 %

Avarage waiting time : 22.50

Avarage response time : 4.00

Avarage turnaround time: 29.33

============================================================

% proj2 input.1 SRTF

Schdeuling algorithm: SRTF

Total 6 tasks are read from "input.1". press 'enter' to start...

==================================================================

process 2 is running

process 2 is running

process 2 is running

process 3 is running

process 3 is running

process 3 is running

process 3 is running

process 3 is running

process 3 is finished.......

process 4 is running

process 4 is running

process 4 is running

process 4 is running

process 4 is finished.......

process 2 is running

process 2 is running

process 2 is running

process 2 is running

process 2 is running

process 2 is running

process 2 is finished.......

process 5 is running

process 5 is running

process 5 is running

process 5 is running

process 5 is running

process 5 is running

process 5 is finished.......

process 6 is running

process 6 is running

process 6 is running

process 6 is running

process 6 is running

process 6 is running

process 6 is running

process 6 is finished.......

process 1 is running

process 1 is running

process 1 is running

process 1 is running

process 1 is running

process 1 is running

process 1 is running

process 1 is running

process 1 is running

process 1 is running

process 1 is finished.......

All processes finish ....................

============================================================

Avarage cpu usage : 100.00 %

Avarage waiting time : 10.50

Avarage response time : 9.00

Avarage turnaround time: 17.33

============================================================