ITU324-Data Structures and Algorithms Laboratory
Practical No-7
AIM:- First Come First Served Scheduling Algorithm: Application of Queue
THEORY :-
Queue:-Queue an abstract data structure, a queue is open at both its ends. One end is
always used to insert data (REAR) and the other is used to remove data (FRONT). Queue
follows First-In-First-Out methodology, i.e., the data item stored first will be accessed first.
Priority Queue:- Priority Queue is an extension of queue with following properties.
1. Every item has a priority associated with it.
2. An element with high priority is dequeued before an element with low priority.
3. If two elements have the same priority, they are served according to their order in the
queue.
Queues in Computer Science
Operating systems:
queue of print jobs to send to the printer
queue of programs / processes to be run
queue of network data packets to send
Programming:
modeling a line of customers or clients
storing a queue of computations to be performed in order
First Come First Served (FCFS) is the simplest and non-preemptive scheduling
algorithm. In First Come First Served (FCFS), the process is allocated to the CPU in the order of
their arrival. A queue data structure is used to implement the FCFS scheduling algorithm. The
process which is at the head of the ready queue is allocated to the CPU, when CPU is free. Then
the process which is running is removed from the queue. When a new process enters into the
ready queue, it is placed onto the tail of the ready queue.
Given n processes with their burst times, the task is to find average waiting time and average turn
around time using FCFS scheduling algorithm.
First in, first out (FIFO), also known as first come, first served (FCFS), is the simplest
Department of Information Technology, GCoE, Amravati Winter 2022
ITU324-Data Structures and Algorithms Laboratory
scheduling algorithm. FIFO simply queues processes in the order that they arrive in the ready
queue. In this, the process that comes first will be executed first and next process starts only after
the previous gets fully executed. Here we are considering that arrival time for all processes is 0.
Sample Output:-Processes with priority
Processes with Burst time Waiting Turn around
priority time time
1 (3) 10 33 43
2 (2) 5 8 13
3 (1) 8 0 8
4 (2) 20 13 33
Average Waiting time = 13.5
Average turnaround time= 24.25
Sample Output:-Processes without priority
Processes Burst time Waiting Turn around
without priority time time
1 10 0 10
2 5 10 15
3 8 15 23
4 20 23 43
Average Waiting time = 12
Average turnaround time= 22.75
Department of Information Technology, GCoE, Amravati Winter 2022
ITU324-Data Structures and Algorithms Laboratory
Source code:- Process without Priority
#include <stdio.h>
#include <stdlib.h>
// Process
struct Process
{
int burstTime;
struct Process *next;
};
// Function prototypes
void enqueue(struct Process **head, int burstTime);
struct Process *dequeue(struct Process **head);
void fcfs(struct Process *head);
void printTable(int, int, int, int);
int argc = 0;
int main()
{
int i;
printf("\nEnter how many process you want to enter : ");
scanf("%d", &argc);
struct Process *queue = NULL;
for (i = 0; i < argc; i++)
{
int burstTime;
printf("\nEnter Burst Time(in ns) for Process %d : ", i + 1);
scanf("%d", &burstTime);
enqueue(&queue, burstTime);
}
fcfs(queue);
return 0;
}
// Function to add a process to the queue
Department of Information Technology, GCoE, Amravati Winter 2022
ITU324-Data Structures and Algorithms Laboratory
void enqueue(struct Process **head, int burstTime)
{
struct Process *newProcess = (struct Process *)malloc(sizeof(struct
Process));
if (newProcess == NULL)
{
printf("Error\n");
exit(1);
}
newProcess->burstTime = burstTime;
newProcess->next = NULL;
// Finding last process
struct Process *last = *head;
if (*head == NULL)
{
*head = newProcess;
return;
}
while (last->next != NULL)
{
last = last->next;
}
last->next = newProcess;
}
// Function to remove a process from the front of the queue
struct Process *dequeue(struct Process **head)
{
// Check if the queue is empty
if (*head == NULL)
{
return NULL;
}
struct Process *first = *head;
*head = first->next;
return first;
}
void fcfs(struct Process *head)
{
int totalWaitTime = 0;
int totalTurnaroundTime = 0;
struct Process *currentProcess = head;
Department of Information Technology, GCoE, Amravati Winter 2022
ITU324-Data Structures and Algorithms Laboratory
int waitTime = 0;
int i = 0;
while (currentProcess != NULL)
{
i++;
// Calculate the turnaround time
int turnaroundTime = currentProcess->burstTime + waitTime;
totalWaitTime += waitTime;
totalTurnaroundTime += turnaroundTime;
printTable(i, currentProcess->burstTime, waitTime, turnaroundTime);
waitTime += currentProcess->burstTime;
head = dequeue(&head);
currentProcess = currentProcess->next;
}
float averageWaitTime = (float)totalWaitTime / argc;
float averageTurnaroundTime = (float)totalTurnaroundTime / argc;
printf("\n\nAverage wait time: %.2f ns\n", averageWaitTime);
printf("\nAverage turnaround time: %.2f ns\n", averageTurnaroundTime);
}
void printTable(int c, int bt, int wt, int tat)
{
if (c == 1)
{
printf("\n--------------------------------------------------");
printf("\n| Process | Burst | Waiting | Turn Around |");
printf("\n| without | Time | Time | Time |");
printf("\n| priority | (in ns) | (in ns) | (in ns) |");
printf("\n--------------------------------------------------");
}
printf("\n|%6d |%6d |%6d |%8d |", c, bt, wt, tat);
if (c == argc)
{
printf("\n--------------------------------------------------");
}
}
Department of Information Technology, GCoE, Amravati Winter 2022
ITU324-Data Structures and Algorithms Laboratory
Source code:- Process with Priority
#include<stdio.h>
#include<stdlib.h>
// Process
struct Process
{
int burstTime;
int priority;
int roll;
struct Process *next;
};
// Function prototypes
void enqueue(struct Process **head, int burstTime, int priority, int roll);
struct Process *dequeue(struct Process **head);
void sortqueue(struct Process *head);
void swap(struct Process *a, struct Process *b);
void fcfs(struct Process *head);
void printTable(int,int,int,int,int,int);
int argc = 0;
int main()
{
int i,priority;
printf("\nEnter how many process you want to enter : ");
scanf("%d",&argc);
struct Process *queue = NULL;
for (i = 0; i < argc; i++)
{
int burstTime;
printf("\nEnter Burst Time(in ns) for Process %d and its priority: ",
i+1);
scanf("%d %d", &burstTime, &priority);
enqueue(&queue, burstTime, priority,i+1);
}
sortqueue(queue);
fcfs(queue);
return 0;
Department of Information Technology, GCoE, Amravati Winter 2022
ITU324-Data Structures and Algorithms Laboratory
// Function to add a process to the queue
void enqueue(struct Process **head, int burstTime, int priority, int roll)
{
struct Process *newProcess = (struct Process*)malloc(sizeof(struct
Process));
if(newProcess == NULL)
{
printf("Error\n");
exit(1);
}
newProcess->burstTime = burstTime;
newProcess->priority = priority;
newProcess->roll = roll;
newProcess->next = NULL;
//Finding last process
struct Process *last = *head;
if (*head == NULL)
{
*head = newProcess;
return;
}
while (last->next != NULL)
{
last = last->next;
}
last->next = newProcess;
}
// Function to remove a process from the front of the queue
struct Process *dequeue(struct Process **head)
{
// Check if the queue is empty
if (*head == NULL)
{
return NULL;
}
struct Process *first = *head;
*head = first->next;
return first;
}
Department of Information Technology, GCoE, Amravati Winter 2022
ITU324-Data Structures and Algorithms Laboratory
void sortqueue(struct Process *head)
{
int swapped, i;
struct Process *ptr1;
struct Process *lptr = NULL;
if (head == NULL)
return;
do
{
swapped = 0;
ptr1 = head;
while(ptr1->next != lptr)
{
if (ptr1->priority > ptr1->next->priority)
{
swap(ptr1, ptr1->next);
swapped = 1;
}
ptr1 = ptr1->next;
}
lptr = ptr1;
}
while(swapped);
}
void swap(struct Process *a, struct Process *b)
{
int temp = a->burstTime;
a->burstTime = b->burstTime;
b->burstTime = temp;
temp = a->priority;
a->priority = b->priority;
b->priority = temp;
temp = a->roll;
a->roll = b->roll;
b->roll = temp;
}
void fcfs(struct Process *head)
Department of Information Technology, GCoE, Amravati Winter 2022
ITU324-Data Structures and Algorithms Laboratory
{
int totalWaitTime = 0;
int totalTurnaroundTime = 0;
struct Process *currentProcess = head;
int waitTime = 0;
int i=0;
while (currentProcess != NULL)
{
i++;
// Calculate the turnaround time
int turnaroundTime = currentProcess->burstTime + waitTime;
totalWaitTime += waitTime;
totalTurnaroundTime += turnaroundTime;
printTable(i,currentProcess->roll,currentProcess-
>priority,currentProcess->burstTime,waitTime,turnaroundTime);
//printf("\nProcess %d burst time: %d ns, Wait time: %d ns, Turnaround
time: %d ns\n", i,currentProcess->burstTime, waitTime, turnaroundTime);
waitTime += currentProcess->burstTime;
head=dequeue(&head);
currentProcess = currentProcess->next;
}
float averageWaitTime = (float) totalWaitTime / argc;
float averageTurnaroundTime = (float) totalTurnaroundTime / argc;
printf("\n\nAverage wait time: %.2f ns\n", averageWaitTime);
printf("\nAverage turnaround time: %.2f ns\n", averageTurnaroundTime);
}
void printTable(int c, int r, int p, int bt, int wt, int tat)
{
if(c==1)
{
printf("\n--------------------------------------------------");
printf("\n| Process | Burst | Waiting | Turn Around |");
printf("\n| with | Time | Time | Time |");
printf("\n| priority | (in ns) | (in ns) | (in ns) |");
printf("\n--------------------------------------------------");
}
printf("\n|%4d (%2d) |%6d |%6d |%8d |",r,p,bt,wt,tat);
if(c==argc)
{
printf("\n--------------------------------------------------");
}
Department of Information Technology, GCoE, Amravati Winter 2022
ITU324-Data Structures and Algorithms Laboratory
Output:- Process without Priority
Department of Information Technology, GCoE, Amravati Winter 2022
ITU324-Data Structures and Algorithms Laboratory
Output:- Process with Priority
Department of Information Technology, GCoE, Amravati Winter 2022
