Shortest Job First scheduler with Gantt Chart in C++

By Abdullah Jamal

Shortest Job First (SJF) cpu scheduler which prints gantt, cpu, input and output chart along with calculating total and average for turn around, waiting and response time for each process.

Shortest job first (SJF) scheduler

Shortest job first is a cpu scheduling technique in which processes with the smallest CPU burst time are executed first.

It Provides an optimal scheduling in terms of average turnaround time and average waiting time.

C++ program to implement Shortest Job First scheduler with gantt chart

Input format :

[number of processes]
[pid] [arrival time] [priority] [share] C [burst] I/O [burst] C [burst] ........... -1
....
[pid] [arrival time] [priority] [share] C [burst] I/O [burst] C [burst] .......... -1

First line describes number of processes.

Then Each of the next N lines describe : -

[pid] : process id.

[arrival time] : time this process was put into ready queue.

[priority] : priority assigned to a process. A lower value means higher priority (Note: this is not used in SJF)

[share] : % of tickets assigned in lottery (proportional share) scheduling. (Note: SJF does not depend on this)

This is followed by sequence of bursts. Before each burst interval, there is a character indicating type of burst.

C : stands for CPU

I : stands for Input

O : stands for output device

-1 : indicates end of trace file

We are assuming one CPU, one Input device and one output device.

Input/output devices follow first come first serve policy i.e. if a process is assigned an input/output device, this device can not be assigned to any other process till its burst is over.

Input ( process.dat)

 

3
1   0   2   1   C   2   I     2   C   3   -1
2   2   0   2   C   4   O     2   C   4   -1
3   0   1   1   C   6   I     4   C   2   -1 

 

Output :

Use g++ sjf.cpp to compile and ./a.out to run on linux 

aj@LAPTOP-I1I0Q1GH:~/os/schedulers/sjf_$ g++ sjf.cpp
aj@LAPTOP-I1I0Q1GH:~/os/schedulers/sjf_$ ./a.out

SJF
Gantt Chart
0   1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24
p1  p1  I1  I1          p1  p1  p1
        p2  p2  p2  p2  O2  O2      p2  p2   p2   p2
                                                       p3   p3   p3   p3   p3   p3   I3   I3   I3   I3   p3   p3

CPU Chart :
0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24
1  1  2  2  2  2  1  1  1  2  2   2   2   3   3   3   3   3   3                   3   3

Input Chart :
0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24
      1  1                                                        3   3   3   3

Output Chart :
0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24
                  2  2

P1 turn around time : 8
P2 turn around time : 10
P3 turn around time : 24
 total turn around time :42
 average turn around time :14.00

P1 waiting time : 2
P2 waiting time : 1
P3 waiting time : 13
 total waiting time :16
 average waiting time :5.33

P1 response time : 0
P2 response time : 0
P3 response time : 13
 total response time :13
 average response time :4.33

 File description :

sjf_scheduler_codespeedy
├── Process.h    ( header file containing helper methods)
├── process.dat  ( input file )
├── sjf.cpp         ( C++ sjf scheduler program )
└── sjf_output.PNG  ( screenshot of output)

0 directories, 4 files

Requirements: 

C++ 11 or later