MAHARASHTRA STATE BOARD OF TECHNICAL

EDUCATION
GOVERNMENT POLYTECHNIC, JALGAON
(0018)

Program Name and Code: Information Technology ( IF5I )

Course Name and Code: OSY (22516)
Academic Year : 2021-2022
Semester : 5th

A MICRO PROJECT
On
Implementation of FCFS and SJF scheduling algorithm

Submitted by the group of 4 students

Sr. Roll Enrollment Seat

Name
No No. No. No.
1 8 Himanshu Nitin Bhangale 1900180064 195144

2 9 Akshay Nivrutti Bramhankar 1900180065 195145

3 17 Satyam Rajendra Brahmankar 1900180073 195153

4 65 Chaitali Bhagawat Sali 1900180395 195201

Project Guide
Mr. A. P. CHAUDHARI (Lecturer in IT)

1
 CERTIFICATE

This is to certify that Roll No. 8, 9, 17, 65 of 5th Semester of Diploma in

Information Technology of Institute, Government Polytechnic, Jalgaon
(Code:0018) has completed the MicroProject satisfactorily in the subject OSY for the
Academic Year 2021- 2022 as prescribed in the curriculum.

Place: Jalgaon Enrollment No: 1900180064

Date: 1900180065
1900180073
1900180395

Subject Teacher Head of Department Principal

Seal of
Institution

2
 GOVERNMENT POLYTECHNIC JALGAON

-SUBMISSION-

We are the students of 5th Semester of the Programme Information

Technology humbly submit that we have completed from time to time the Micro-
Project work as described in this report by our own skills and study in academic year
2021 -2022 as per instructions/guidance of Mr. A. P. CHAUDHARI.
And those following students were associated with me for this work however,
quantum of our contribution has been approved by the Lecturer.
And that we have not copied the report on its any appreciable part from any
other literature in contravention of the academic ethics.

Date: Signature of Students

Himanshu Nitin Bhangale

Akshay Nivrutti Bramhankar
Satyam Rajendra Brahmankar
Chaitali Bhagwat Sali

3
 AKNWLDGMENT

This micro project would not have been possible without considerable
guidance and support. So, we would like to thank to those who have enable us to
complete this project.
Firstly, we would like to thank our project guide Mr. A.P.CHAUDHARI
(Lecturer in IT Dept , Government Polytechnic Jalgaon) and Head of IT
Department Mr. H. K. Nemade for providing the guideline with continuous
advice and feedback throughout the duration of finishing this project. We also
thank to the Dr. P.M. Patil (principal of Government Polytechnic Jalgaon) for
providing us the opportunity to embark on this project.
Secondly, we would also like to thank all other staff members of IT
Department that we may call upon for assistance since the genesis of this project
their opinion and suggestions have helped us in a realizing these projects.

4
 INDEX

Sr. Index Page

No. No.
1. Introduction 6

2. Algorithm 8

3. Program and Output 11

4. Advantage and Disadvantage 26

5. Conclusion 27

6. References 28

5
 INTRODUCTION

1.Introduction to First Come First served:-

First Come First Serve (FCFS) is an operating system scheduling algorithm

that automatically executes queued requests and processes in order of their arrival. It
is the easiest and simplest CPU scheduling algorithm. In this type of algorithm,
processes which requests the CPU first get the CPU allocation first. This is managed
with a FIFO queue. The full form of FCFS is First Come First Serve.
As the process enters the ready queue, its PCB (Process Control Block) is
linked with the tail of the queue and, when the CPU becomes free, it should be
assigned to the process at the beginning of the queue.

Characteristics of FSCS:-

• It supports non pre-emptive and pre-emptive scheduling algorithm.

• Jobs are always executed on a first-come, first-serve basis.
• It is easy to implement and use.
• This method is poor in performance, and the general wait time is quite high.

2.Introduction to Shortest Job First:-

Shortest Job First (SJF) is an algorithm in which the process having

the smallest execution time is chosen for the next execution. This scheduling
method can be pre-emptive or non-pre-emptive. It significantly reduces the
average waiting time for other processes awaiting execution. The full form
of SJF is Shortest Job First.
Shortest Job First scheduling works on the process with the shortest
burst time or duration first.
• This is the best approach to minimize waiting time.
• This is used in Batch Systems.
• It is of two types:
1. Non Pre-emptive
2. Pre-emptive

6
 • To successfully implement it, the burst time/duration time of the
processes should be known to the processor in advance, which is
practically not feasible all the time.
• This scheduling algorithm is optimal if all the jobs/processes are
available at the same time. (either Arrival time is 0 for all, or Arrival
time is same for all)

Characteristics of SJF Scheduling : -

• It is associated with each job as a unit of time to complete.

• This algorithm method is helpful for batch-type processing,
where waiting for jobs to complete is not critical.
• It can improve process throughput by making sure that shorter
jobs are executed first, hence possibly have a short turnaround
time.
It improves job output by offering shorter jobs, which should be executed first, which
mostly have a shorter turnaround time.

7
 ALGORITHM

First Come First Served : -

Implementation : -

1- Input the processes along with their burst time (bt).

2- Find waiting time (wt) for all processes.
3- As first process that comes need not to wait so
waiting time for process 1 will be 0 i.e. wt[0] = 0.
4- Find waiting time for all other processes i.e. for
process i ->
wt[i] = bt[i-1] + wt[i-1] .
5- Find turnaround time = waiting_time + burst_time
for all processes.
6- Find average waiting time =
total_waiting_time / no_of_processes.
7- Similarly, find average turnaround time =
total_turn_around_time / no_of_processes.

8
Shortest Job First ( Non - Preemptive ): -

Implementation : -

1 - Sort all the process according to the arrival time.

2 - Then select that process which has minimum arrival time and minimum Burst time.
3 - After completion of process make a pool of process which after till the completion
of previous process and select that process among the pool which is having minimum
Burst time.

9
Shortest Job First ( Preemptive ): -

Implementation : -

1- Traverse until all process gets completely executed.

a) Find process with minimum remaining time at every single time lap.
b) Reduce its time by 1.
c) Check if its remaining time becomes 0
d) Increment the counter of process completion.
e) Completion time of current process = current_time +1;
f) Calculate waiting time for each completed process.
wt[i]= Completion time - arrival_time-burst_time
g)Increment time lap by one.
2- Find turnaround time (waiting_time+burst_time).
10
 PROGRAM AND OUTPUT

First Come First Served : -

// C++ program for implementation of FCFS

// scheduling
#include<iostream>
using namespace std;

// Function to find the waiting time for all

// processes
void findWaitingTime(int processes[], int n,
int bt[], int wt[])
{
// waiting time for first process is 0
wt[0] = 0;

// calculating waiting time

for (int i = 1; i < n ; i++ )
wt[i] = bt[i-1] + wt[i-1] ;
}

// Function to calculate turn around time

void findTurnAroundTime( int processes[], int n,
int bt[], int wt[], int tat[])
{
// calculating turnaround time by adding
// bt[i] + wt[i]
for (int i = 0; i < n ; i++)
tat[i] = bt[i] + wt[i];
}

//Function to calculate average time

void findavgTime( int processes[], int n, int bt[])
11
{
int wt[n], tat[n], total_wt = 0, total_tat = 0;

//Function to find waiting time of all processes

findWaitingTime(processes, n, bt, wt);

//Function to find turn around time for all processes

findTurnAroundTime(processes, n, bt, wt, tat);

//Display processes along with all details

cout << "Processes "<< " Burst time "
<< " Waiting time " << " Turn around time\n";

// Calculate total waiting time and total turn

// around time
for (int i=0; i<n; i++)
{
total_wt = total_wt + wt[i];
total_tat = total_tat + tat[i];
cout << " " << i+1 << "\t\t" << bt[i] <<"\t "
<< wt[i] <<"\t\t " << tat[i] <<endl;
}

cout << "Average waiting time = "

<< (float)total_wt / (float)n;
cout << "\nAverage turn around time = "
<< (float)total_tat / (float)n;
}

// Driver code
int main()
{
//process id's
int processes[] = { 1, 2, 3};
int n = sizeof processes / sizeof processes[0];

//Burst time of all processes

12
 int burst_time[] = {10, 5, 8};

findavgTime(processes, n, burst_time);
return 0;
}

13
Shortest Job First ( Non - Preemptive ): -

#include <iostream>

using namespace std;

int mat[10][6];

void swap(int* a, int* b)

{

int temp = *a;

*a = *b;

*b = temp;
}

void arrangeArrival(int num, int mat[][6])

{

for (int i = 0; i < num; i++) {

for (int j = 0; j < num - i - 1; j++) {

if (mat[j][1] > mat[j + 1][1]) {

for (int k = 0; k < 5; k++) {

swap(mat[j][k], mat[j + 1][k]);

}
14
 }

}
}

void completionTime(int num, int mat[][6])

{

int temp, val;

mat[0][3] = mat[0][1] + mat[0][2];

mat[0][5] = mat[0][3] - mat[0][1];

mat[0][4] = mat[0][5] - mat[0][2];

for (int i = 1; i < num; i++) {

temp = mat[i - 1][3];

int low = mat[i][2];

for (int j = i; j < num; j++) {

if (temp >= mat[j][1] && low >= mat[j][2]) {

low = mat[j][2];

val = j;

15
 mat[val][3] = temp + mat[val][2];

mat[val][5] = mat[val][3] - mat[val][1];

mat[val][4] = mat[val][5] - mat[val][2];

for (int k = 0; k < 6; k++) {

swap(mat[val][k], mat[i][k]);

}
}

int main()
{

int num, temp;

cout << "Enter number of Process: ";

cin >> num;

cout << "...Enter the process ID...\n";

for (int i = 0; i < num; i++) {

cout << "...Process " << i + 1 << "...\n";

cout << "Enter Process Id: ";

cin >> mat[i][0];

16
 cout << "Enter Arrival Time: ";

cin >> mat[i][1];

cout << "Enter Burst Time: ";

cin >> mat[i][2];

cout << "Before Arrange...\n";

cout << "Process ID\tArrival Time\tBurst Time\n";

for (int i = 0; i < num; i++) {

cout << mat[i][0] << "\t\t" << mat[i][1] << "\t\t"

<< mat[i][2] << "\n";

arrangeArrival(num, mat);

completionTime(num, mat);

cout << "Final Result...\n";

cout << "Process ID\tArrival Time\tBurst Time\tWaiting "

"Time\tTurnaround Time\n";

for (int i = 0; i < num; i++) {

cout << mat[i][0] << "\t\t" << mat[i][1] << "\t\t"

17
 << mat[i][2] << "\t\t" << mat[i][4] << "\t\t"

<< mat[i][5] << "\n";

}
}

18
Shortest Job First ( Preemptive ): -

#include <iostream>

using namespace std;

struct Process {

int pid; // Process ID

int bt; // Burst Time

int art; // Arrival Time

};

// Function to find the waiting time for all

// processes

void findWaitingTime(Process proc[], int n,

int wt[])
{

int rt[n];

// Copy the burst time into rt[]

for (int i = 0; i < n; i++)

rt[i] = proc[i].bt;

int complete = 0, t = 0, minm = INT_MAX;

19
int shortest = 0, finish_time;

bool check = false;

// Process until all processes gets

// completed

while (complete != n) {

// Find process with minimum

// remaining time among the

// processes that arrives till the

// current time`

for (int j = 0; j < n; j++) {

if ((proc[j].art <= t) &&

(rt[j] < minm) && rt[j] > 0) {

minm = rt[j];

shortest = j;

check = true;

20
if (check == false) {

t++;

continue;

// Reduce remaining time by one

rt[shortest]--;

// Update minimum

minm = rt[shortest];

if (minm == 0)

minm = INT_MAX;

// If a process gets completely

// executed

if (rt[shortest] == 0) {

// Increment complete

complete++;

check = false;

21
 // Find finish time of current

// process

finish_time = t + 1;

// Calculate waiting time

wt[shortest] = finish_time -

proc[shortest].bt -

proc[shortest].art;

if (wt[shortest] < 0)

wt[shortest] = 0;

// Increment time

t++;

}
}

// Function to calculate turn around time

void findTurnAroundTime(Process proc[], int n,

int wt[], int tat[])

{

// calculating turnaround time by adding

22
 // bt[i] + wt[i]

for (int i = 0; i < n; i++)

tat[i] = proc[i].bt + wt[i];

}

// Function to calculate average time

void findavgTime(Process proc[], int n)

{

int wt[n], tat[n], total_wt = 0,

total_tat = 0;

// Function to find waiting time of all

// processes

findWaitingTime(proc, n, wt);

// Function to find turn around time for

// all processes

findTurnAroundTime(proc, n, wt, tat);

// Display processes along with all

// details

cout << "Processes "

23
 << " Burst time "

<< " Waiting time "

<< " Turn around time\n";

// Calculate total waiting time and

// total turnaround time

for (int i = 0; i < n; i++) {

total_wt = total_wt + wt[i];

total_tat = total_tat + tat[i];

cout << " " << proc[i].pid << "\t\t"

<< proc[i].bt << "\t\t " << wt[i]

<< "\t\t " << tat[i] << endl;

cout << "\nAverage waiting time = "

<< (float)total_wt / (float)n;

cout << "\nAverage turn around time = "

<< (float)total_tat / (float)n;

}

// Driver code
24
int main()
{

Process proc[] = { { 1, 6, 1 }, { 2, 8, 1 },

{ 3, 7, 2 }, { 4, 3, 3 } };

int n = sizeof(proc) / sizeof(proc[0]);

findavgTime(proc, n);

return 0;
}

25
 ADVANTAGE AND DISADVANTAGE

1.First Come First Serve (FCFS):

Advantages : -
1. It is simple and easy to understand.
Disadvantages : -
1. The process with less execution time suffer i.e. waiting time
is often quite long.
2. Favors CPU Bound process then I / O bound process.

2. Shortest Job First (SJF) [Preemptive and Non-Prememptive]:

Advantages -
1. Shortest jobs are favored.
2. It is provably optimal, in that it gives the minimum average waiting time for a
given set of processes.
Disadvantages -
1. SJF may cause starvation, if shorter processes keep coming. This problem is
solved by aging.
2. It cannot be implemented at the level of short term CPU scheduling.

26
 CONCLUSION

In this project we successfully implemented the First Come First Served

(FCFS) algorithm, Shortest Job First with non preemptive and pre-emptive(Shortest
Remaining Time First) algorithm. We understand the basic concepts of CPU
scheduling algorithms. How this algorithms works?, fundamentals of CPU
Scheduling. We understand the basic advantage and disadvantage of scheduling
algorithms.

27
 REFERENCES

• https://www.geeksforgeeks.org/program-for-fcfs-cpu-scheduling-set-1/

• https://www.geeksforgeeks.org/program-for-shortest-job-first-or-sjf-cpu-

scheduling-set-1-non-preemptive/?ref=lbp

• https://www.geeksforgeeks.org/program-for-shortest-job-first-sjf-scheduling-

set-2-preemptive/?ref=lbp

• https://www.wikipedia.org/

• https://www.google.co.in/

• https://www.geeksforgeeks.org/advantages-and-disadvantages-of-various-cpu-

scheduling-algorithms/

28