OPERATING SYSTEM LAB MANUAL (BCS-451)

EXPERIMENT NUMBER: 2
Objective: Implement CPU Scheduling Policies.
Content: CPU scheduling is a crucial part of operating systems. It ensures efficient utilization of the
CPU by deciding which process will own the CPU while another process is suspended. The main goal
is to make the system more efficient, faster, and fairer. Various scheduling algorithms, such as First
Come First Serve (FCFS), Shortest Job First (SJF), Priority Scheduling, and Round Robin,
determine the order in which processes are executed.

a) FCFS
Introduction: First-Come, First-Served (FCFS) is a straightforward and intuitive scheduling algorithm
widely used in operating systems and service environments. In FCFS, tasks are executed in the exact
order they arrive, ensuring fairness and simplicity. This method is akin to a queue where the first task
to enter is the first to be processed. While easy to implement and understand, FCFS can lead to
inefficiencies such as the "convoy effect," where shorter tasks are delayed by longer ones, potentially
increasing the overall waiting time for all tasks. Despite its limitations, FCFS remains a fundamental
concept in the study of scheduling algorithms.
#include "stdio.h"
#include "stdlib.h"
struct process
{
int process_id;
int arrival_time;
int burst_time;
int waiting_time;
int turn_around_time;
};
int main()
{
int n,i;
printf("Enter number of processes: ");
scanf("%d",&n);
struct process proc[n];
for(i=0;i<n;i++)
{
printf("\n");
printf("Enter arrival time for process%d: ",i+1);
scanf("%d",&proc[i].arrival_time);
printf("Enter burst time for process%d: ",i+1);
scanf("%d",&proc[i].burst_time);
proc[i].process_id = i+1;
}
int service_time[n];

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

service_time[0]=0;
proc[0].waiting_time=0;
for(i=1;i<n;i++)
{
service_time[i]=service_time[i-1]+proc[i-1].burst_time;
proc[i].waiting_time = service_time[i]-proc[i].arrival_time;

if(proc[i].waiting_time<0)
proc[i].waiting_time=0;
}
for(i=0;i<n;i++)
{
proc[i].turn_around_time = proc[i].burst_time + proc[i].waiting_time;
}
printf("\n\n");
printf("Process\tBurst Time\tArrival Time\tWaiting Time\tTurn-Around Time\tCompletion Time\n");
int total_waiting_time=0,total_turn_around_time=0;
for(i=0;i<n;i++)
{
total_waiting_time+=proc[i].waiting_time;
total_turn_around_time+=proc[i].turn_around_time;
int completion_time=proc[i].turn_around_time + proc[i].arrival_time;
printf("%d\t\t%d\t\t%d\t\t%d\t\t%d\t\t%d\n",proc[i].process_id,proc[i].burst_time,
proc[i].arrival_time, proc[i].waiting_time,proc[i].turn_around_time,completion_time);
}
printf("Average waiting time: %f\n", (float)total_waiting_time/n);
printf("Average turn around time: %f\n",(float)total_turn_around_time/n);
}

OUTPUT

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

b) SJF Non-Preemptive
Introduction: Shortest Job First (SJF) Non-Preemptive is a scheduling algorithm that prioritizes tasks based
on their execution times, selecting the job with the shortest duration to execute next. This approach aims to
minimize the average waiting time and increase overall efficiency, making it optimal for reducing the
turnaround time of processes. Unlike its preemptive counterpart, SJF Non-Preemptive allows a running task to
complete without interruption before moving on to the next shortest job. While highly effective in certain
scenarios, the algorithm requires precise knowledge of job lengths, which can be challenging to predict
accurately. This limitation can affect its practicality in dynamic environments where job durations are not
known beforehand.
#include "stdio.h"
#include "stdlib.h"
struct process
{
int process_id;
int arrival_time;
int burst_time;
int waiting_time;
int turn_around_time;
};
int main()
{
int n,i,j;
int bt=0,k=1,tat=0,sum=0,min;
printf("Enter number of processes: ");
scanf("%d",&n);
struct process proc[n],temp;
for(i=0;i<n;i++)
{
printf("\n");
printf("Enter arrival time for process%d: ",i+1);
scanf("%d",&proc[i].arrival_time);
printf("Enter burst time for process%d: ",i+1);
scanf("%d",&proc[i].burst_time);
proc[i].process_id = i+1;
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(proc[i].arrival_time < proc[j].arrival_time)
{
temp = proc[j];
proc[j] = proc[i];
proc[i] = temp;

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

}
}
}

for(i=0;i<n;i++)
{
bt+=proc[i].burst_time;
min = proc[k].burst_time;
for(j=k;j<n;j++)
{
if(bt>=proc[j].arrival_time && proc[j].burst_time<min)
{
temp=proc[k];
proc[k]=proc[j];
proc[j]=temp;
}
}
k++;
}
proc[0].waiting_time=0;
int wait_time_total=0;
int turn_around_time_total=0;
for(i=1;i<n;i++)
{
sum+=proc[i-1].burst_time;
proc[i].waiting_time = sum-proc[i].arrival_time;
wait_time_total += proc[i].waiting_time;
}
for(i=0;i<n;i++)
{
tat+=proc[i].burst_time;
proc[i].turn_around_time = tat - proc[i].arrival_time;
turn_around_time_total+=proc[i].turn_around_time;
}
printf("Process\tBurst Time\tArrival Time\tWaiting Time\tTurn-Around Time\n");

for(i=0;i<n;i++)
{
printf("%d\t\t%d\t\t%d\t\t%d\t\t%d\n",proc[i].process_id,proc[i].burst_time,
proc[i].arrival_time, proc[i].waiting_time,proc[i].turn_around_time);
}
printf("Average waiting time: %f\n", (float)wait_time_total/n);
printf("Average turn around time: %f\n",(float)turn_around_time_total/n);

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

OUTPUT

c) Priority Non- Preemptive

Introduction: Priority Non-Preemptive is a scheduling algorithm that assigns a priority level to each
task and processes them based on their priority rather than their arrival time or duration. In this
approach, the task with the highest priority is executed first, and once a task begins execution, it runs
to completion without interruption, regardless of any higher-priority tasks arriving in the meantime.
This method ensures that critical tasks receive immediate attention, improving responsiveness for
high-priority processes. However, it can lead to issues such as starvation, where lower-priority tasks
may be indefinitely delayed if high-priority tasks keep arriving. Priority Non-Preemptive scheduling
is effective in environments where task priorities are well-defined and critical tasks must be handled
promptly.

#include "stdio.h"
#include "stdlib.h"
struct process
{
int process_id;
int arrival_time;
int burst_time;
int waiting_time;
int turn_around_time;
int priority;
};
int main()

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

{
int n,i,j;
int bt=0,k=1,tat=0,sum=0,min,mini;
printf("Enter number of processes: ");
scanf("%d",&n);
struct process proc[n],temp;
for(i=0;i<n;i++)
{
printf("\n");
printf("Enter arrival time for process%d: ",i+1);
scanf("%d",&proc[i].arrival_time);
printf("Enter burst time for process%d: ",i+1);
scanf("%d",&proc[i].burst_time);
printf("Enter priority for process%d: ",i+1);
scanf("%d",&proc[i].priority);
proc[i].process_id = i+1;
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(proc[i].arrival_time < proc[j].arrival_time)
{
temp = proc[j];
proc[j] = proc[i];
proc[i] = temp;
}
}
}
for(i=0;i<n;i++)
{
bt+=proc[i].burst_time;
min = proc[k].burst_time;
mini = proc[k].priority;
for(j=k;j<n;j++)
{
if(bt>=proc[j].arrival_time && proc[j].priority<mini)
{
temp=proc[k];
proc[k]=proc[j];
proc[j]=temp;
}}
k++;
}
proc[0].waiting_time=0;

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

int wait_time_total=0;
int turn_around_time_total=0;
for(i=1;i<n;i++)
{
sum+=proc[i-1].burst_time;
proc[i].waiting_time = sum-proc[i].arrival_time;
wait_time_total += proc[i].waiting_time;
}
for(i=0;i<n;i++)
{
tat+=proc[i].burst_time;
proc[i].turn_around_time = tat - proc[i].arrival_time;
turn_around_time_total+=proc[i].turn_around_time;
}
printf("Process\tBurst Time\tArrival Time\tWaiting Time\tTurn-Around Time\n");

for(i=0;i<n;i++)
{
printf("%d\t\t%d\t\t%d\t\t%d\t\t%d\n",proc[i].process_id,proc[i].burst_time,
proc[i].arrival_time, proc[i].waiting_time,proc[i].turn_around_time);
}
printf("Average waiting time: %f\n", (float)wait_time_total/n);
printf("Average turn around time: %f\n",(float)turn_around_time_total/n);
}

OUTPUT

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

d) Priority Preemptive Scheduling

Introduction: Priority Preemptive Scheduling is a dynamic and efficient scheduling algorithm that
prioritizes tasks based on their assigned priority levels, allowing higher-priority tasks to interrupt and
preempt the execution of lower-priority tasks. This approach ensures that critical tasks receive
immediate attention, improving responsiveness and reducing the waiting time for high-priority
processes. By allowing preemption, the system can adapt quickly to changing priorities, making it
suitable for real-time and time-sensitive applications. However, this method can lead to issues such
as starvation, where lower-priority tasks may be repeatedly preempted and delayed indefinitely. To
mitigate this, mechanisms like aging can be implemented to gradually increase the priority of waiting
tasks, ensuring a balanced and fair scheduling system.

#include "stdio.h"
#include "stdlib.h"
struct process
{
int pid;
int at;
int bt;
int wt;
int tat;
int rt;
int ct;
int priority;
};
int main()
{
int n,i,j,tq;
printf("Enter number of processes: ");
scanf("%d",&n);
struct process proc[n];
int burst[n];
for(i=0;i<n;i++)
{
printf("Enter arrival time for process%d: ",i+1 );
scanf("%d",&proc[i].at);
printf("Enter burst time for process%d: ",i+1 );
scanf("%d",&proc[i].bt);
printf("Enter priority for process%d: ",i+1 );
scanf("%d",&proc[i].priority);
proc[i].pid= i+1;
proc[i].rt = proc[i].bt;

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

burst[i]=proc[i].bt;
}
for(i=0;i<n-1;i++)
{
for(j=0;j<n-i-1;j++)
{
if(proc[j].at > proc[j+1].at)
{
struct process temp = proc[j];
proc[j] = proc[j+1];
proc[j+1] = temp;
}
}
}
printf("Enter time quantum: ");
scanf("%d",&tq);
int avgt=0,avgw=0;
int tim=-1,tot=n,mini=1e9,pos=-1;
while(tot)
{
tim++;
mini =1e9;
pos=-1;

//find minimum priority process at time=tim

for(int i=0;i<n;i++)
{
if(mini>proc[i].priority && burst[i] && tim>=proc[i].at)
{
pos=i;
mini=proc[i].priority;
}
}

// if no such process found

if(pos==-1)
continue;

burst[pos]--;
for(int i=0;i<n;i++)
{
if(i!=pos && burst[i] && tim>=proc[i].at)
{
proc[i].wt++;
}

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

if(burst[pos]==0)
{
tot--;
proc[pos].tat = tim - proc[pos].at +1;

avgt+=proc[pos].tat;
avgw+=proc[pos].wt;
}
}
for(i=0;i<n;i++)
{
printf("%d %d %d %d %d
%d\n",proc[i].pid,proc[i].priority,proc[i].at,proc[i].bt,proc[i].bt,proc[i].wt );
}
}
OUTPUT

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

e) Round Robin
Introduction: Round Robin is a widely used preemptive scheduling algorithm designed to ensure
fairness and time-sharing among tasks in a system. Each task is assigned a fixed time slice, or
quantum, during which it can execute. Once its time slice expires, the task is moved to the end of the
queue, and the next task in line gets its turn. This process continues cyclically, ensuring that all tasks
receive equal opportunity to utilize the CPU.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define N 100
struct process
{
int process_id;
int arrival_time;
int burst_time;
int waiting_time;
int turn_around_time;
int remaining_time;
};
int queue[N];
int front = 0, rear = 0;
struct process proc[N];

void push(int process_id)

{
queue[rear] = process_id;
rear = (rear+1)%N;
}
int pop()
{
if(front == rear)
return -1;
int return_position = queue[front];
front = (front +1)%N;
return return_position;
}
int main()
{
float wait_time_total = 0.0, tat = 0.0;
int n,time_quantum;
printf("Enter the number of processes: ");
scanf("%d", &n);
CSE (IOT), GNIOT APPROVED BY
HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

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

{
printf("Enter the arrival time for the process%d: ",i+1);
scanf("%d", &proc[i].arrival_time);
printf("Enter the burst time for the process%d: ",i+1);
scanf("%d", &proc[i].burst_time);
proc[i].process_id = i+1;
proc[i].remaining_time = proc[i].burst_time;
}
printf("Enter time quantum: ");
scanf("%d",&time_quantum);
int time=0;
int processes_left=n;
int position=-1;
int local_time=0;
for(int j=0; j<n; j++)
if(proc[j].arrival_time == time)
push(j);
while(processes_left)
{
if(local_time == 0)
{
if(position != -1)
push(position);
position = pop();
}
for(int i=0; i<n; i++)
{
if(proc[i].arrival_time > time)
continue;
if(i==position)
continue;
if(proc[i].remaining_time == 0)
continue;
proc[i].waiting_time++;
proc[i].turn_around_time++;
}
if(position != -1)
{
proc[position].remaining_time--;
proc[position].turn_around_time++;
if(proc[position].remaining_time == 0)
{
processes_left--;
local_time = -1;
CSE (IOT), GNIOT APPROVED BY
HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

position = -1;
}
}
else
local_time = -1;
time++;
local_time = (local_time +1)%time_quantum;
for(int j=0; j<n; j++)
if(proc[j].arrival_time == time)
push(j);
}
printf("\n");
printf("Process\t\tArrival Time\tBurst Time\tWaiting time\tTurn around time\n");
for(int i=0; i<n; i++)
{
printf("%d\t\t%d\t\t", proc[i].process_id, proc[i].arrival_time);
printf("%d\t\t%d\t\t%d\n", proc[i].burst_time, proc[i].waiting_time,
proc[i].turn_around_time);
tat += proc[i].turn_around_time;
wait_time_total += proc[i].waiting_time;
}
tat = tat/(1.0*n);
wait_time_total = wait_time_total/(1.0*n);

printf("\nAverage waiting time : %f",wait_time_total);

printf("\nAverage turn around time : %f\n", tat);
}

OUTPUT

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

f) SJF-Preemptive
Introduction: Shortest Job First (SJF) Preemptive, also known as Shortest Remaining Time First
(SRTF), is a dynamic scheduling algorithm that selects the task with the shortest remaining execution
time to run next. Unlike its non-preemptive counterpart, SJF Preemptive allows the currently running
task to be interrupted if a new task arrives with a shorter execution time. This approach aims to
minimize the average waiting and turnaround times, making it highly efficient for systems where task
durations are known or can be estimated accurately. However, implementing SJF Preemptive can be
complex due to the need for continuous monitoring and comparison of task lengths, and it may cause
frequent context switching, leading to increased overhead. Despite these challenges, SJF Preemptive
is valued for its potential to optimize process scheduling in environments with highly variable task
durations.

#include "stdio.h"
#include "stdlib.h"
struct process
{
int process_id;
int arrival_time;
int burst_time;
int waiting_time;
int turn_around_time;
int remain_time;
};
int main()
{
int n,i,j;
int bt=0,k=1,tat=0,sum=0,min;
printf("Enter number of processes: ");
scanf("%d",&n);
struct process proc[n],temp;
for(i=0;i<n;i++)
{
printf("\n");
printf("Enter arrival time for process%d: ",i+1);
scanf("%d",&proc[i].arrival_time);
printf("Enter burst time for process%d: ",i+1);
scanf("%d",&proc[i].burst_time);
proc[i].remain_time = proc[i].burst_time;
proc[i].process_id = i+1;
}
int quantum_time,flag=0;
CSE (IOT), GNIOT APPROVED BY
HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

printf("Enter time quantum: ");

scanf("%d",&quantum_time);
int processes_remaining=n;

for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(proc[i].arrival_time < proc[j].arrival_time)
{
temp = proc[j];
proc[j] = proc[i];
proc[i] = temp;
}
}
}
int wait_time_total=0,totalExecutionTime=0,turn_around_time_total=0;
i=0;
while(processes_remaining!=0)
{
if(proc[i].remain_time<=quantum_time && proc[i].remain_time>0)
{
totalExecutionTime+=proc[i].remain_time;
proc[i].remain_time = 0;
flag=1;
}
else if(proc[i].remain_time>0)
{
proc[i].remain_time-=quantum_time;
totalExecutionTime+=quantum_time;
}
if(flag==1 && proc[i].remain_time==0)
{
proc[i].waiting_time=totalExecutionTime-proc[i].arrival_time-proc[i].burst_time;
wait_time_total+=proc[i].waiting_time;

proc[i].turn_around_time=totalExecutionTime-proc[i].arrival_time;
turn_around_time_total+=proc[i].turn_around_time;
flag=0;
processes_remaining--;
}

if(i==n-1)
{
i=0;

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

}
else if(proc[i+1].arrival_time<=totalExecutionTime)
i++;
else
i=0;
}
printf("Process\tBurst Time\tArrival Time\tWaiting Time\tTurn-Around Time\n");

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

printf("%d\t\t%d\t\t%d\t\t%d\t\t%d\n",proc[i].process_id,proc[i].burst_time,
proc[i].arrival_time, proc[i].waiting_time,proc[i].turn_around_time);
}
printf("Average waiting time: %f\n", (float)wait_time_total/n);
printf("Average turn around time: %f\n",(float)turn_around_time_total/n);

OUTPUT

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

EXPERIMENT NUMBER: 3
Objective: Implementation of Banker’s algorithm.
Content: Banker's Algorithm is a resource allocation and deadlock avoidance algorithm devised by
Edsger Dijkstra. It is used in operating systems to manage resource allocation in a way that ensures
the system remains in a safe state, avoiding deadlocks. The algorithm simulates the allocation of
predetermined maximum possible resources to each process and checks if the resulting state is safe,
meaning that there exists a sequence of allocations that allows every process to complete without
causing a deadlock. The name comes from its analogy to a bank lending system where the bank needs
to ensure it never allocates its resources in a way that prevents it from meeting all its clients' demands.

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
int need[100][100],allot[100][100],max[100][100],available[100];
bool isFinished[100];
int sequence[100];
void isSafe(int N,int M)
{
int i,j,work[100],count=0;
for(i=0;i<M;i++)
work[i]=available[i];
for(i=0;i<100;i++)
isFinished[i]=false;
while(count<N)
{
bool canAllot=false;
for(i=0;i<N;i++)
{
if(isFinished[i]==false)
{

for(j=0;j<M;j++)
{
if(work[j]<need[i][j])
{
break;
}
}
if(j==M)
{
for(j=0;j<M;j++)
{
work[j]+=allot[i][j];
}

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

sequence[count++]=i;
isFinished[i]=true;
canAllot=true;
}
}
}
if(canAllot==false)
{
printf("System Is not safe\n");
return ;
}
}
printf("System is in safe state\n");
printf("Safe sequence :");
for(i=0;i<N;i++)
printf("%d ",sequence[i]);
printf("\n");
}
int main()
{
int i,j,N,M;
printf("Enter the number of process and resources :");
scanf("%d %d",&N,&M);
printf("Enter the available resources :\n");
for(i=0;i<M;i++)
scanf("%d",&available[i]);
printf("Enter the Allocation Matrix :\n");
for(i=0;i<N;i++)
for(j=0;j<M;j++)
scanf("%d",&allot[i][j]);
printf("Enter the matrix for maximum demand of each process :\n");
for(i=0;i<N;i++)
for(j=0;j<M;j++)
scanf("%d",&max[i][j]);
//calculation of need matrix
for(i=0;i<N;i++)
for(j=0;j<M;j++)
need[i][j]=max[i][j]-allot[i][j];
isSafe(N,M);
int indx,arr[100];
printf("Enter the process no for resource request :");
scanf("%d",&indx);
printf("Enter the requested instances of Each :");
for(i=0;i<M;i++)
scanf("%d",&arr[i]);
for(i=0;i<M;i++)
{

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

if( need[indx][i]<arr[i] || arr[i]>available[i] )

{
printf("Cannot request\n");
break;
}
}

if(i==M)
{
for(i=0;i<M;i++)
{
allot[indx][i]+=arr[i];
available[i]-=arr[i];
need[indx][i]-=arr[i];
}

isSafe(N,M);
}

OUTPUT

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

EXPERIMENT NUMBER: 4
Objective: Implementation of Disk Scheduling.
Content: Disk scheduling is a crucial aspect of operating system design that manages how read and
write requests are ordered and processed by the disk controller. Efficient disk scheduling algorithms
aim to minimize the overall seek time, which is the time taken for the disk's read/write head to move
to the location where data is to be read or written. Common disk scheduling algorithms include First-
Come, First-Served (FCFS), which processes requests in the order they arrive; Shortest Seek Time
First (SSTF), which selects the request closest to the current head position; and more sophisticated
algorithms like SCAN (or Elevator) and C-SCAN, which move the head across the disk in a
systematic way to reduce seek time variability. These algorithms enhance performance by reducing
latency and improving throughput, ultimately leading to faster and more efficient data access.

a) C-LOOK
Introduction- C-LOOK is a disk scheduling algorithm that enhances the standard LOOK algorithm
by reducing the number of seek operations and improving efficiency. Like LOOK, C-LOOK moves
the disk's read/write head to service requests in one direction until it reaches the last request in that
direction, then reverses. However, instead of reversing immediately, C-LOOK jumps back to the
starting end without servicing any requests on the return trip, similar to the way an elevator skips
floors on its way back to the ground floor. This approach minimizes the total seek time and reduces
the average waiting time for disk I/O operations, making C-LOOK particularly effective in
environments with a high volume of disk access requests.

#include "stdio.h"
#include "stdlib.h"
#include "stdbool.h"

struct request
{
int request_track_number;
bool visited;
};

int main()
{
int i,no_of_requests,initial_head,limit,j,choice,previous_head;
printf("Enter the number of requests: ");
scanf("%d",&no_of_requests);
struct request req[no_of_requests];
printf("Enter the requests: ");
for (i = 0; i < no_of_requests; ++i)
{
scanf("%d",&req[i].request_track_number);
req[i].visited = false;

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

}
printf("Enter initial position of R/W head: ");
scanf("%d",&initial_head);
printf("Enter the previous position of R/W head: ");
scanf("%d",&previous_head);
printf("Enter the cylinder size: ");
scanf("%d",&limit);
if(previous_head - initial_head > 0 )
{
choice = 2;
}
else
choice = 1;
//scanf("%d",&choice);
int seek_time=0;
printf("%d -> ",initial_head );
int cp_initial_head = initial_head;
if(choice == 1)
{
for(i=initial_head;i<limit;i++)
{
for(j=0;j<no_of_requests;j++)
{
if(req[j].request_track_number == i && req[j].visited == false)
{
printf("%d -> ", req[j].request_track_number);
req[j].visited = true;
seek_time += abs(req[j].request_track_number - initial_head);
initial_head = req[j].request_track_number;
}
}
}
initial_head = 0;
for(i=0;i<cp_initial_head;i++)
{
for(j=0;j<no_of_requests;j++)
{
if(req[j].request_track_number == i && req[j].visited == false)
{
printf("%d -> ", req[j].request_track_number);
req[j].visited = true;
seek_time += abs(req[j].request_track_number - initial_head);
initial_head = req[j].request_track_number;
}
}
}
printf("\n");

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

}
else if(choice == 2)
{
for(i=initial_head;i>=0;i--)
{
for(j=0;j<no_of_requests;j++)
{
if(req[j].request_track_number == i && req[j].visited == false)
{
printf("%d -> ", req[j].request_track_number);
req[j].visited = true;
seek_time += abs(req[j].request_track_number - initial_head);
initial_head = req[j].request_track_number;
}
}
}
initial_head = limit-1;
for(i=limit;i>cp_initial_head;i--)
{
for(j=0;j<no_of_requests;j++)
{
if(req[j].request_track_number == i && req[j].visited == false)
{
printf("%d -> ", req[j].request_track_number);
req[j].visited = true;
seek_time += abs(req[j].request_track_number - initial_head);
initial_head = req[j].request_track_number;
}
}
}
printf("\n");
}
printf("Seek Time: %d\n", seek_time);
}

OUTPUT

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

b) C- SCAN
Introduction- C-SCAN (Circular SCAN) is a disk scheduling algorithm that improves upon the
standard SCAN (Elevator) method by providing a more uniform wait time. In C-SCAN, the disk's
read/write head moves in one direction, servicing all pending requests until it reaches the end of the
disk. After reaching the end, the head quickly returns to the beginning without servicing any requests
during the return trip, and then starts servicing requests again in the same direction. This circular
approach ensures that all requests are treated more equally, preventing the problem of starvation seen
in SCAN where requests at the edges of the disk might be serviced less frequently. By maintaining a
consistent direction of service, C-SCAN offers a more predictable and fair performance, especially
beneficial in systems with a high volume of read/write requests.

#include "stdio.h"
#include "stdlib.h"
#include "stdbool.h"

struct request
{
int request_track_number;
bool visited;
};

int main()
{
int i,no_of_requests,initial_head,limit,j,choice,previous_head;
printf("Enter the number of requests: ");
scanf("%d",&no_of_requests);
struct request req[no_of_requests];
printf("Enter the requests: ");
for (i = 0; i < no_of_requests; ++i)
{
scanf("%d",&req[i].request_track_number);
req[i].visited = false;
}
printf("Enter initial position of R/W head: ");
scanf("%d",&initial_head);

printf("Enter the previous position of R/W head: ");

scanf("%d",&previous_head);

printf("Enter the cylinder size: ");

scanf("%d",&limit);

if(previous_head - initial_head > 0 )

CSE (IOT), GNIOT APPROVED BY
HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

{
choice = 2;
}
else
choice = 1;
//scanf("%d",&choice);
int seek_time=0;
printf("%d -> ",initial_head );
int cp_initial_head = initial_head;
if(choice == 1)
{
for(i=initial_head;i<limit;i++)
{
for(j=0;j<no_of_requests;j++)
{
if(req[j].request_track_number == i && req[j].visited == false)
{
printf("%d -> ", req[j].request_track_number);
req[j].visited = true;
seek_time += abs(req[j].request_track_number - initial_head);
initial_head = req[j].request_track_number;
}
}
}
printf("%d -> \n", limit-1);
seek_time += abs(limit-1 - initial_head);
initial_head = 0;
for(i=0;i<cp_initial_head;i++)
{
for(j=0;j<no_of_requests;j++)
{
if(req[j].request_track_number == i && req[j].visited == false)
{
printf("%d -> ", req[j].request_track_number);
req[j].visited = true;
seek_time += abs(req[j].request_track_number - initial_head);
initial_head = req[j].request_track_number;
}
}
}
printf("\n");
}
else if(choice == 2)
{
for(i=initial_head;i>=0;i--)
{
for(j=0;j<no_of_requests;j++)

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

{
if(req[j].request_track_number == i && req[j].visited == false)
{
printf("%d -> ", req[j].request_track_number);
req[j].visited = true;
seek_time += abs(req[j].request_track_number - initial_head);
initial_head = req[j].request_track_number;
}
}
}
printf("%d -> ", 0 );
seek_time += abs(initial_head - 0);
initial_head = limit-1;
for(i=limit;i>cp_initial_head;i--)
{
for(j=0;j<no_of_requests;j++)
{
if(req[j].request_track_number == i && req[j].visited == false)
{
printf("%d -> ", req[j].request_track_number);
req[j].visited = true;
seek_time += abs(req[j].request_track_number - initial_head);
initial_head = req[j].request_track_number;
}
}
}
printf("\n");
}
printf("Seek Time: %d\n", seek_time);
}

OUTPUT

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

c) FCFS
Introduction: First-Come, First-Served (FCFS) is a straightforward disk scheduling algorithm where
disk read and write requests are processed in the order they arrive in the queue. This simplicity ensures
fairness, as each request gets serviced without priority, but it can lead to inefficient performance. For
instance, if a series of requests are located far apart on the disk, the disk arm may have to move back
and forth across the disk frequently, resulting in high seek times and increased latency. Despite its
simplicity and fairness, FCFS is not typically used in high-performance systems due to its potential
for poor optimization of seek time and overall disk throughput.
#include "stdio.h"
#include "stdlib.h"
#include "stdbool.h"
int main()
{
int i,no_of_requests,initial_head;
printf("Enter the number of requests: ");
scanf("%d",&no_of_requests);
int request[no_of_requests];
printf("Enter the requests: ");
for (i = 0; i < no_of_requests; ++i)
{
scanf("%d",&request[i]);
}
printf("Enter initial position of R/W head: ");
scanf("%d",&initial_head);
int seek_time=0;
printf("%d -> ",initial_head );
for(i=0;i<no_of_requests;i++)
{
if(i == no_of_requests-1)
printf("%d\n", request[i] );
else
printf("%d -> ", request[i] );
seek_time += abs(request[i] - initial_head);
initial_head = request[i];
}
printf("Seek Time: %d\n", seek_time);
}
OUTPUT

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

d) LOOK SCAN
Introduction- Disk scheduling using the LOOK algorithm is an optimized version of the SCAN
(Elevator) algorithm. In LOOK, the disk's read/write head moves towards the end of the queue,
servicing all requests in its path, but instead of going all the way to the end of the disk, it "looks"
ahead and reverses direction as soon as it has serviced the farthest request in that direction. This
reduces unnecessary head movement compared to SCAN, which always goes to the edge of the disk
before reversing direction. LOOK improves efficiency by minimizing the seek time and reducing the
overall latency for disk operations, leading to better performance in handling I/O requests.

#include "stdio.h"
#include "stdlib.h"
#include "stdbool.h"

struct request
{
int request_track_number;
bool visited;
};

int main()
{
int i,no_of_requests,initial_head,limit,j,choice,previous_head;
printf("Enter the number of requests: ");
scanf("%d",&no_of_requests);
struct request req[no_of_requests];
printf("Enter the requests: ");
for (i = 0; i < no_of_requests; ++i)
{
scanf("%d",&req[i].request_track_number);
req[i].visited = false;
}
printf("Enter initial position of R/W head: ");
scanf("%d",&initial_head);

printf("Enter the previous position of R/W head: ");

scanf("%d",&previous_head);

printf("Enter the cylinder size: ");

scanf("%d",&limit);

if(previous_head - initial_head > 0 )

{
choice = 2;
CSE (IOT), GNIOT APPROVED BY
HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

}
else
choice = 1;
//scanf("%d",&choice);
int seek_time=0;
printf("%d -> ",initial_head );
if(choice == 1)
{
for(i=initial_head;i<limit;i++)
{
for(j=0;j<no_of_requests;j++)
{
if(req[j].request_track_number == i && req[j].visited == false)
{
printf("%d -> ", req[j].request_track_number);
req[j].visited = true;
seek_time += abs(req[j].request_track_number - initial_head);
initial_head = req[j].request_track_number;
}
}
}
for(i=initial_head;i>=0;i--)
{
for(j=0;j<no_of_requests;j++)
{
if(req[j].request_track_number == i && req[j].visited == false)
{
printf("%d -> ", req[j].request_track_number);
req[j].visited = true;
seek_time += abs(req[j].request_track_number - initial_head);
initial_head = req[j].request_track_number;
}
}
}
printf("\n");
}
else if(choice == 2)
{
for(i=initial_head;i>=0;i--)
{
for(j=0;j<no_of_requests;j++)
{
if(req[j].request_track_number == i && req[j].visited == false)
{
printf("%d -> ", req[j].request_track_number);
req[j].visited = true;
seek_time += abs(req[j].request_track_number - initial_head);

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

initial_head = req[j].request_track_number;
}
}
}
for(i=initial_head;i<limit;i++)
{
for(j=0;j<no_of_requests;j++)
{
if(req[j].request_track_number == i && req[j].visited == false)
{
printf("%d -> ", req[j].request_track_number);
req[j].visited = true;
seek_time += abs(req[j].request_track_number - initial_head);
initial_head = req[j].request_track_number;
}
}
}
printf("\n");
}
printf("Seek Time: %d\n", seek_time);
}

OUTPUT

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

e) SCAN
Introduction- The SCAN algorithm, also known as the Elevator algorithm, is a disk scheduling
technique that optimizes the order of read and write requests to minimize seek time. The algorithm
works by moving the disk's read/write head in one direction, servicing all requests along the way, until
it reaches the end of the disk. Once it hits the end, the head reverses direction and continues servicing
requests in the opposite direction. This back-and-forth movement resembles an elevator's motion,
hence the name. SCAN is effective in reducing the variance in seek time compared to simpler
algorithms like First-Come, First-Served (FCFS) or Shortest Seek Time First (SSTF), leading to
improved overall performance and more predictable response times.

#include "stdio.h"
#include "stdlib.h"
#include "stdbool.h"

struct request
{
int request_track_number;
bool visited;
};

int main()
{
int i,no_of_requests,initial_head,limit,j,choice,previous_head;
printf("Enter the number of requests: ");
scanf("%d",&no_of_requests);
struct request req[no_of_requests];
printf("Enter the requests: ");
for (i = 0; i < no_of_requests; ++i)
{
scanf("%d",&req[i].request_track_number);
req[i].visited = false;
}
printf("Enter initial position of R/W head: ");
scanf("%d",&initial_head);

printf("Enter the previous position of R/W head: ");

scanf("%d",&previous_head);

printf("Enter the cylinder size: ");

scanf("%d",&limit);

if(previous_head - initial_head > 0 )

{
choice = 2;
}

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

else
choice = 1;
//scanf("%d",&choice);
int seek_time=0;
printf("%d -> ",initial_head );
if(choice == 1)
{
for(i=initial_head;i<limit;i++)
{
for(j=0;j<no_of_requests;j++)
{
if(req[j].request_track_number == i && req[j].visited == false)
{
printf("%d -> ", req[j].request_track_number);
req[j].visited = true;
seek_time += abs(req[j].request_track_number - initial_head);
initial_head = req[j].request_track_number;
}
}
}
printf("%d -> ", limit-1);
seek_time += abs(limit-1 - initial_head);
initial_head = limit-1;
for(i=initial_head;i>=0;i--)
{
for(j=0;j<no_of_requests;j++)
{
if(req[j].request_track_number == i && req[j].visited == false)
{
printf("%d -> ", req[j].request_track_number);
req[j].visited = true;
seek_time += abs(req[j].request_track_number - initial_head);
initial_head = req[j].request_track_number;
}
}
}
seek_time += abs(initial_head - 0);
printf("0 \n");
}
else if(choice == 2)
{
for(i=initial_head;i>=0;i--)
{
for(j=0;j<no_of_requests;j++)
{
if(req[j].request_track_number == i && req[j].visited == false)
{

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

printf("%d -> ", req[j].request_track_number);

req[j].visited = true;
seek_time += abs(req[j].request_track_number - initial_head);
initial_head = req[j].request_track_number;
}
}
}
printf("%d -> ", 0);
seek_time += abs(0 - initial_head);
initial_head = 0;
for(i=initial_head;i<limit;i++)
{
for(j=0;j<no_of_requests;j++)
{
if(req[j].request_track_number == i && req[j].visited == false)
{
printf("%d -> ", req[j].request_track_number);
req[j].visited = true;
seek_time += abs(req[j].request_track_number - initial_head);
initial_head = req[j].request_track_number;
}
}
}
seek_time += abs(limit-1 - initial_head );
printf("%d \n", limit-1);

}
printf("Seek Time: %d\n", seek_time);
}

OUTPUT

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

f ) SSTF
Introduction- Shortest Seek Time First (SSTF) is a disk scheduling algorithm that selects the disk
I/O request closest to the current position of the disk's read/write head, minimizing the seek time for
each operation. By always choosing the nearest request, SSTF reduces the average seek time
compared to simpler algorithms like First-Come, First-Served (FCFS). However, SSTF can lead to
the "starvation" problem, where requests that are far from the current head position may experience
significant delays if closer requests continually arrive. Despite this potential drawback, SSTF is often
favored in systems where reducing seek time is a priority, as it typically results in better overall
performance for disk access operations.

#include "stdio.h"
#include "stdlib.h"
#include "stdbool.h"

struct request
{
int request_track_number;
bool visited;
};

int main()
{
int i,no_of_requests,initial_head,limit,j,choice,previous_head;
printf("Enter the number of requests: ");
scanf("%d",&no_of_requests);
struct request req[no_of_requests];
printf("Enter the requests: ");
for (i = 0; i < no_of_requests; ++i)
{
scanf("%d",&req[i].request_track_number);
req[i].visited = false;
}
printf("Enter initial position of R/W head: ");
scanf("%d",&initial_head);

int seek_time=0;
printf("%d -> ",initial_head );
int n = no_of_requests;
CSE (IOT), GNIOT APPROVED BY
HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

while(n)
{
int min = 1e9;
int min_track_number, position;
for(i=0;i<no_of_requests;i++)
{
if(abs(initial_head - req[i].request_track_number) < min &&
req[i].visited == false)
{
min = abs(initial_head - req[i].request_track_number);
min_track_number = req[i].request_track_number;
position = i;
}
}
initial_head = req[position].request_track_number;
req[position].visited = true;
printf("%d ->",min_track_number);
seek_time += min;
n--;
}

printf("\nSeek Time: %d\n", seek_time);

}

OUTPUT

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

EXPERIMENT NUMBER: 5
Objective: Implementation of contiguous allocation techniques.
Content: Contiguous allocation is a memory management technique where each file or process is
assigned a single contiguous block of disk space or memory. This method simplifies access and
management by allowing direct addressing and reducing the overhead of maintaining complex data
structures. However, it can lead to significant issues such as external fragmentation, where free space
is scattered in small, non-contiguous chunks, and the need for compaction to consolidate free space.

a) Best Fit
Introduction- Contiguous allocation with the best fit strategy is a disk allocation technique used in
file systems where each file occupies a contiguous block of disk space. The best fit approach allocates
the smallest available block of space that is sufficient to accommodate the file being stored. This
method helps in minimizing wasted space on the disk by reducing fragmentation—where small gaps
of unusable space exist between allocated blocks.
#include "stdio.h"
#include "stdlib.h"
#include "stdbool.h"

struct process
{
int id;
int memory_required;
int allocated_partition;
int external_fragment;
bool allocated;
};
struct partition
{
int id;
int size;
int internal_fragment;
bool alloted;
};
int main()
{
int memory,no_of_partitions,no_of_processes,i,j,sum=0;
printf("Enter total memory: ");
scanf("%d",&memory);
printf("Enter number of partitions: ");
scanf("%d",&no_of_partitions);
struct partition parti[no_of_partitions];
for(i=0;i<no_of_partitions;i++)
{
CSE (IOT), GNIOT APPROVED BY
HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

printf("Enter memory for partition%d: ",i+1);

scanf("%d",&parti[i].size);
parti[i].id = i+1;
parti[i].alloted=false;

sum+=parti[i].size;
}
if(sum < memory)
{
no_of_partitions++;
parti[i].size = memory - sum;
printf("Size of partition%d: %d\n",i+1,parti[i].size );
parti[i].id = i+1;
parti[i].alloted = false;
}
for(i=0;i<no_of_partitions-1;i++)
{
for(j=0;j<no_of_partitions-1-i;j++)
{
if(parti[j].size>parti[j+1].size)
{
struct partition temp = parti[j];
parti[j] = parti[j+1];
parti[j+1] = temp;
}
}
}
int total_internal_fragment=0, total_external_fragment=0;
printf("Enter number of processes: ");
scanf("%d",&no_of_processes);
struct process proc[no_of_processes];
for (i = 0; i < no_of_processes; ++i)
{
printf("Enter memory required for process%d: ",i+1 );
scanf("%d",&proc[i].memory_required);
proc[i].id = i+1;
proc[i].external_fragment=0;
proc[i].allocated = false;
for(j=0;j<no_of_partitions;j++)
{
if(proc[i].memory_required<=parti[j].size && !parti[j].alloted)
{
proc[i].allocated = true;
proc[i].allocated_partition = parti[j].id;
parti[j].internal_fragment = parti[j].size - proc[i].memory_required;
total_internal_fragment+=parti[j].internal_fragment;
parti[j].alloted=true;

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

break;
}
/*else if(proc[i].memory_required<=parti[j+1].size && !parti[j+1].alloted)
{
proc[i].allocated = true;
proc[i].allocated_partition = parti[j+1].id;
parti[j+1].internal_fragment = parti[j+1].size -
proc[i].memory_required;
total_internal_fragment+=parti[j+1].internal_fragment;
parti[j+1].alloted=true;
break;
}*/
}
for(j=0;j<no_of_partitions;j++)
{
if(parti[j].alloted==false)
{
proc[i].external_fragment+=parti[j].size;
}
}
}
for(j=0;j<no_of_partitions;j++)
{
if(!parti[j].alloted)
{
total_external_fragment+=parti[j].size;
parti[j].internal_fragment = -1;
}
}
printf("ProcessID\tMemory required\tAllocated\tAllocated Partition\n");
for(i=0;i<no_of_processes;i++)
{
if(proc[i].allocated)
{
printf("%d\t\t%d\t\t\tYES\t%d\t\n",proc[i].id, proc[i].memory_required,
proc[i].allocated_partition);
}
else
{
printf("%d\t\t%d\t\t\tNO\t%d\n",proc[i].id, proc[i].memory_required,
proc[i].external_fragment);
}
}
printf("\n");
printf("Internal Fragmentation\n");
for(i=0;i<no_of_partitions;i++)
{

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

if(parti[i].internal_fragment==-1)
{
printf("%d ---\n",parti[i].id);
}
else
printf("%d %d\n",parti[i].id,parti[i].internal_fragment );
}
printf("Total internal Fragmentation: %d\nTotal external Fragmentation:
%d\n",total_internal_fragment, total_external_fragment);
while(1)
{
char choice,dummy;
printf("Do you want to continue? (Y/n) : ");
getchar();
scanf("%c",&choice);
if(choice=='Y')
{
int id,new_memory_required,allocated_partition;
bool allocated;
printf("Enter id of the process leaving: ");
scanf("%d",&id);
printf("Enter memory required for the new processs: ");
scanf("%d",&new_memory_required);
int partition_to_remove = proc[id-1].allocated_partition;
int memory_to_remove = proc[id-1].memory_required;
printf("Partition to remove: %d\n", partition_to_remove);
for(i=0;i<no_of_partitions;i++)
{
if(parti[i].id == partition_to_remove)
{
parti[i].alloted = false;
//parti[i].internal_fragment = parti[i].size;
}
}
//parti[partition_to_remove-1].alloted=false;
//parti[partition_to_remove-1].size;+=memory_to_remove;
allocated = false;
for(j=0;j<no_of_partitions;j++)
{
if(new_memory_required<=parti[j].size && !parti[j].alloted)
{
allocated = true;
allocated_partition = parti[j].id;
parti[j].internal_fragment = parti[j].size -
new_memory_required;
//total_internal_fragment+=parti[j].internal_fragment;
parti[j].alloted=true;

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

break;
}
}
if(allocated)
{
printf("Process allocated in partition: %d\n",allocated_partition );
printf("New internal Fragmentation for the partition =
%d\n",parti[j].internal_fragment );
}
else
{
printf("Process cannot be allocated\n");
}
}
else{
return 0;
}
}
}

OUTPUT

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

b) First Fit
Introduction- Contiguous allocation, specifically the First Fit technique, is a method used in file
allocation where files are stored on disk in contiguous blocks based on their size and availability. The
First Fit approach allocates the first available space on the disk that is large enough to accommodate
the file. This method is efficient in terms of time since it scans the disk sequentially and allocates the
first suitable space it encounters, reducing the search overhead compared to other strategies like Best
Fit or Worst Fit. However, First Fit may lead to fragmentation over time as files are created, modified,
and deleted, leaving small gaps of unused space scattered across the disk. Despite this, First Fit
remains a straightforward and commonly used technique in operating systems for managing disk
storage efficiently.

#include "stdio.h"
#include "stdlib.h"
#include "stdbool.h"
struct process
{
int id;
int memory_required;
int allocated_partition;
int external_fragment;
bool allocated;
};
struct partition
{
int id;
int size;
int internal_fragment;
bool alloted;
};
int main()
{
int memory,no_of_partitions,no_of_processes,i,j,sum=0;
printf("Enter total memory: ");
scanf("%d",&memory);
printf("Enter number of partitions: ");
scanf("%d",&no_of_partitions);
struct partition parti[no_of_partitions];
for(i=0;i<no_of_partitions;i++)
{
printf("Enter memory for partition%d: ",i+1);
scanf("%d",&parti[i].size);
parti[i].id = i+1;
parti[i].alloted=false;

sum+=parti[i].size;
CSE (IOT), GNIOT APPROVED BY
HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

}
if(sum < memory)
{
no_of_partitions++;
parti[i].size = memory - sum;
parti[i].id = i+1;
parti[i].alloted=false;
printf("Size of partition%d: %d\n",i,parti[i].size );
}
int total_internal_fragment=0, total_external_fragment=0;
printf("Enter number of processes: ");
scanf("%d",&no_of_processes);
struct process proc[no_of_processes];
for (i = 0; i < no_of_processes; ++i)
{
printf("Enter memory required for process%d: ",i+1 );
scanf("%d",&proc[i].memory_required);
proc[i].id = i+1;
proc[i].external_fragment=0;
proc[i].allocated = false;
for(j=0;j<no_of_partitions;j++)
{
if(proc[i].memory_required<=parti[j].size && !parti[j].alloted)
{
proc[i].allocated = true;
proc[i].allocated_partition = parti[j].id;
parti[j].internal_fragment = parti[j].size - proc[i].memory_required;
total_internal_fragment+=parti[j].internal_fragment;
parti[j].alloted=true;
break;
}
/*else if(proc[i].memory_required<=parti[j+1].size && !parti[j+1].alloted)
{
proc[i].allocated = true;
proc[i].allocated_partition = parti[j+1].id;
parti[j+1].internal_fragment = parti[j+1].size -
proc[i].memory_required;
total_internal_fragment+=parti[j+1].internal_fragment;
parti[j+1].alloted=true;
break;
}*/
}
for(j=0;j<no_of_partitions;j++)
{
if(parti[j].alloted==false)
{
proc[i].external_fragment+=parti[j].size;

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

}
}
}
for(j=0;j<no_of_partitions;j++)
{
if(!parti[j].alloted)
{
total_external_fragment+=parti[j].size;
parti[j].internal_fragment = -1;
}}
printf("ProcessID\tMemory required\tAllocated\tAllocated Partition\n");
for(i=0;i<no_of_processes;i++)
{
if(proc[i].allocated)
{
printf("%d\t\t%d\t\t\tYES\t%d\t\n",proc[i].id, proc[i].memory_required, proc[i].allocated_partition);
}
else
{
printf("%d\t\t%d\t\t\tNO\t\t%d\n",proc[i].id, proc[i].memory_required, proc[i].external_fragment);
}
}
printf("\n");
printf("Internal Fragmentation\n");
for(i=0;i<no_of_partitions;i++)
{
if(parti[i].internal_fragment==-1)
{
printf("%d ---\n",parti[i].id);
}
else
printf("%d %d\n",parti[i].id,parti[i].internal_fragment );
}
printf("Total internal Fragmentation: %d\nTotal external Fragmentation:
%d\n",total_internal_fragment, total_external_fragment);

}
OUTPUT

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

c) Worst Fit
Introduction- Contiguous allocation is a disk allocation technique where each file occupies a
contiguous set of blocks on the disk. The Worst Fit algorithm is used to allocate space for new files by selecting
the largest available block that can accommodate the file, minimizing fragmentation over time. While it may
seem counterintuitive to choose the largest available block rather than the smallest, Worst Fit aims to leave
larger contiguous free spaces after allocation, reducing the likelihood of future fragmentation and making it
easier to allocate larger files later on. However, this method can lead to inefficient space utilization, as smaller
gaps may remain unused. Despite its drawbacks, Worst Fit can be advantageous in scenarios where maintaining
larger free spaces for future allocations is a priority.

#include "stdio.h"
#include "stdlib.h"
#include "stdbool.h"
struct process
{
int id;
int memory_required;
int allocated_partition;
int external_fragment;
bool allocated;
};
struct partition
{
CSE (IOT), GNIOT APPROVED BY
HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

int id;
int size;
int internal_fragment;
bool alloted;
};
int main()
{
int memory,no_of_partitions,no_of_processes,i,j,sum=0;
printf("Enter total memory: ");
scanf("%d",&memory);
printf("Enter number of partitions: ");
scanf("%d",&no_of_partitions);
struct partition parti[no_of_partitions];
for(i=0;i<no_of_partitions;i++)
{
printf("Enter memory for partition%d: ",i+1);
scanf("%d",&parti[i].size);
parti[i].id = i+1;
parti[i].alloted=false;
sum+=parti[i].size;
}
if(sum < memory)
{
no_of_partitions++;
parti[i].size = memory - sum;
parti[i].id = i+1;
parti[i].alloted=false;
printf("Size of partition%d: %d\n",i+1,parti[i].size );
}
for(i=0;i<no_of_partitions-1;i++)
{
for(j=0;j<no_of_partitions-1-i;j++)
{
if(parti[j].size<parti[j+1].size)
{
struct partition temp = parti[j];
parti[j] = parti[j+1];
parti[j+1] = temp;
}
}
}
/*for(i=0;i<no_of_partitions;i++)
{
printf("%d\n",parti[i].size );
}*/
int total_internal_fragment=0, total_external_fragment=0;
printf("Enter number of processes: ");
scanf("%d",&no_of_processes);
struct process proc[no_of_processes];
for (i = 0; i < no_of_processes; ++i)
{
printf("Enter memory required for process%d: ",i+1 );
CSE (IOT), GNIOT APPROVED BY
HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

scanf("%d",&proc[i].memory_required);
proc[i].id = i+1;
proc[i].external_fragment=0;
proc[i].allocated = false;
for(j=0;j<no_of_partitions;j++)
{
if(proc[i].memory_required<=parti[j].size && !parti[j].alloted)
{
proc[i].allocated = true;
proc[i].allocated_partition = parti[j].id;
parti[j].internal_fragment = parti[j].size - proc[i].memory_required;
total_internal_fragment+=parti[j].internal_fragment;
parti[j].alloted=true;
break;
}
/*else if(proc[i].memory_required<=parti[j+1].size && !parti[j+1].alloted)
{
proc[i].allocated = true;
proc[i].allocated_partition = parti[j+1].id;
parti[j+1].internal_fragment = parti[j+1].size - proc[i].memory_required;
total_internal_fragment+=parti[j+1].internal_fragment;
parti[j+1].alloted=true;
break;
}
else
{
proc[i].allocated = false;
}*/
}
for(j=0;j<no_of_partitions;j++)
{
if(parti[j].alloted==false)
{
proc[i].external_fragment+=parti[j].size;
}
}
}
for(j=0;j<no_of_partitions;j++)
{
if(!parti[j].alloted)
{
total_external_fragment+=parti[j].size;
parti[j].internal_fragment = -1;
}
}
printf("ProcessID\tMemory required\tAllocated\tAllocated Partition\n");
for(i=0;i<no_of_processes;i++)
{
if(proc[i].allocated)
{
printf("%d\t\t%d\t\t\tYES\t%d\t\n",proc[i].id, proc[i].memory_required, proc[i].allocated_partition);
}
CSE (IOT), GNIOT APPROVED BY
HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

else
{
printf("%d\t\t%d\t\t\tNO\t%d\n",proc[i].id, proc[i].memory_required, proc[i].external_fragment);
}
}
printf("\n");
printf("Internal Fragmentation\n");
for(i=0;i<no_of_partitions;i++)
{
if(parti[i].internal_fragment==-1)
{
printf("%d ---\n",parti[i].id);
}
else
printf("%d %d\n",parti[i].id,parti[i].internal_fragment );
}
printf("Total internal Fragmentation: %d\nTotal external Fragmentation:
%d\n",total_internal_fragment, total_external_fragment);
}

OUTPUT

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

EXPERIMENT NUMBER: 6
Objective: Implementation of Page Replacement Algorithms.
Content: Page Replacement Algorithms are crucial components of virtual memory management in
operating systems, specifically for systems that use paging as a memory management scheme. These
algorithms determine which pages should be evicted from the main memory (RAM) when a new page
needs to be loaded but there is no free space available. Popular page replacement algorithms include
Least Recently Used (LRU), which removes the page that has not been accessed for the longest time;
First-In-First-Out (FIFO), which removes the oldest page in memory; and Optimal Page Replacement,
which evicts the page that will not be used for the longest period of time in the future. Each algorithm
balances between simplicity of implementation and efficiency of page utilization, aiming to minimize
page faults and improve overall system performance by optimizing memory usage.

a) FIFO
Introduction- The First-In-First-Out (FIFO) page replacement algorithm is one of the simplest and
most intuitive methods used in virtual memory management within operating systems. It operates on
the principle of evicting the oldest page from main memory when a page fault occurs and needs to be
replaced. FIFO maintains a queue of pages in the order they were brought into memory, with the oldest
page at the front and the newest page at the rear. When a new page needs to be loaded into a full
memory, FIFO replaces the page at the front of the queue, which was first brought in. While FIFO is
easy to implement and avoids the complexity of tracking page usage, it suffers from the "Belady's
anomaly," where increasing the number of frames can unexpectedly increase page faults, leading to
potentially inefficient use of memory resources in some scenarios.

#include "stdio.h"
#include "stdlib.h"
#include "stdbool.h"

int pointer;
int faults ,hits;
void print(int frame_size,int frame[])
{
int i;
//printf("Printing the Frames: ");
for(i=0;i<frame_size;i++)
{
if(frame[i]==-1)
printf("- ");
else
printf("%d ",frame[i]);
}

printf("\n");
CSE (IOT), GNIOT APPROVED BY
HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

void add_reference(int frame_size,int frame[], int reference)

{
int i;
bool alloted = false;
for(i=0;i<frame_size;i++)
{
if(frame[i]==reference)
{
alloted = true;
printf(" Hit for %d | ", reference);
hits++;
break;
}
else if(frame[i]==-1)
{
alloted = true;
frame[i] = reference;
printf("Fault for %d | ", reference);
faults++;
break;
}
}
if(alloted == false)
{
faults++;
printf("Fault for %d | ", reference);
frame[pointer] = reference;
pointer = (pointer+1)%frame_size;
}
print(frame_size, frame);
}

int main()
{
int frame_size,i,number_of_references;
printf("Enter frame size: ");
scanf("%d",&frame_size);
int frame[frame_size];
for(i=0;i<frame_size;i++)
{
frame[i] = -1;
}

print(frame_size,frame);

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

printf("Enter the number of references: ");

scanf("%d",&number_of_references);
int reference[number_of_references];

for(i=0;i<number_of_references;i++)
{
scanf("%d",&reference[i]);
add_reference(frame_size,frame,reference[i]);
}
printf("\nNumber of faults: %d \nNumber of hits: %d\n",faults,hits );
}

OUTPUT

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

b) LRU
Introduction- Least Recently Used (LRU) is a page replacement algorithm used in operating systems
to manage memory efficiently, especially in virtual memory systems. It works on the principle of
replacing the least recently used page when a new page needs to be allocated and the memory is full.
LRU keeps track of the order in which pages are accessed and stores this information in a data
structure such as a queue or a counter. When a page needs to be replaced, LRU identifies the page that
has not been accessed for the longest time and swaps it out, assuming that pages accessed recently are
more likely to be accessed again in the near future (temporal locality). LRU is effective in reducing
the number of page faults and improving overall system performance by maximizing the availability
of frequently accessed pages in the main memory.

#include "stdio.h"
#include "stdlib.h"
#include "stdbool.h"

int pointer;
int faults ,hits;
void print(int frame_size,int frame[])
{
int i;
//printf("Printing the Frames: ");
for(i=0;i<frame_size;i++)
{
if(frame[i]==-1)
printf("- ");
else
printf("%d ",frame[i]);
}

printf("\n");
}
int predict(int reference_length, int references[], int page_no ,int frame_size,int frame[], int start)
{
int pos = -1, farthest = start, i;
for(i=0;i<frame_size;i++)
{
int j;
for(j=start-1;j>=0;j--)
{
if(frame[i]==references[j])
{
if(j<farthest)
{
farthest=j;
pos=i;
CSE (IOT), GNIOT APPROVED BY
HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

}
break;
}
}
if(j==page_no)
return i;
}
if(pos == -1)
return 0;
else
return pos;
}
void add_reference(int frame_size,int frame[], int reference, int current_position,int reference_length,
int references[])
{
int i;
bool allocated=false;
for(i=0;i<frame_size;i++)
{

if(frame[i]==reference)
{
printf(" Hit for %d | ", reference);
hits++;
allocated = true;
break;
}
else if(frame[i]==-1)
{
frame[i] = reference;
printf("Fault for %d | ", reference);
faults++;
allocated = true;
break;
}
}
if(allocated==false)
{
int j =
predict(reference_length, references, current_position,frame_size,frame,current_position+1);
frame[j] = reference;
printf("Fault for %d | ", reference);
faults++;
}
print(frame_size, frame);
}

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

int main()
{
int frame_size,i,number_of_references;
printf("Enter frame size: ");
scanf("%d",&frame_size);
int frame[frame_size];
for(i=0;i<frame_size;i++)
{
frame[i] = -1;
}
print(frame_size,frame);
printf("Enter the number of references: ");
scanf("%d",&number_of_references);
int reference[number_of_references];

for(i=0;i<number_of_references;i++)
{
scanf("%d",&reference[i]);
add_reference(frame_size,frame,reference[i],i,number_of_references,reference);
}
printf("\nNumber of faults: %d \nNumber of hits: %d\n",faults,hits );
}
OUTPUT

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

c) Optimal
Introduction- Optimal page replacement is a theoretical page replacement algorithm used in
operating systems to manage memory. It works on the principle of replacing the page that will not be
used for the longest period of time in the future, thus minimizing the number of page faults—the
instances where a requested page is not found in memory and needs to be fetched from disk. Optimal
page replacement requires knowledge of future memory references, which is generally not feasible in
practical scenarios. Despite its impracticality, Optimal serves as a benchmark for evaluating other
page replacement algorithms like FIFO (First-In-First-Out) and LRU (Least Recently Used),
showcasing the minimum possible number of page faults that can be achieved with perfect knowledge
of future memory accesses.

#include "stdio.h"
#include "stdlib.h"
#include "stdbool.h"
int pointer;
int faults ,hits;
void print(int frame_size,int frame[])
{
int i;
//printf("Printing the Frames: ");
for(i=0;i<frame_size;i++)
{
if(frame[i]==-1)
printf("- ");
else
printf("%d ",frame[i]);
}

printf("\n");
}

int predict(int reference_length, int references[], int page_no ,int frame_size,int frame[], int start)
{
int pos = -1, farthest = start, i;
for(i=0;i<frame_size;i++)
{
int j;
for(j=start;j<reference_length;j++)
{
if(frame[i]==references[j])
{
if(j>farthest)
{
farthest=j;
pos=i;
CSE (IOT), GNIOT APPROVED BY
HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

}
break;
}
}
if(j==page_no)
return i;
}
if(pos == -1)
return 0;
else
return pos;
}
void add_reference(int frame_size,int frame[], int reference, int current_position,int reference_length,
int references[])
{
int i;
bool allocated=false;
for(i=0;i<frame_size;i++)
{

if(frame[i]==reference)
{
printf(" Hit for %d | ", reference);
hits++;
allocated = true;
break;
}
else if(frame[i]==-1)
{
frame[i] = reference;
printf("Fault for %d | ", reference);
faults++;
allocated = true;
break;
}
}
if(allocated==false)
{
int j =
predict(reference_length, references,current_position,frame_size,frame,current_position+1);
frame[j] = reference;
printf("Fault for %d | ", reference);
faults++;
}
print(frame_size, frame);
}
int main()

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

{
int frame_size,i,number_of_references;
printf("Enter frame size: ");
scanf("%d",&frame_size);
int frame[frame_size];
for(i=0;i<frame_size;i++)
{
frame[i] = -1;
}
print(frame_size,frame);
printf("Enter the number of references: ");
scanf("%d",&number_of_references);
int reference[number_of_references];
for(i=0;i<number_of_references;i++)
{
scanf("%d",&reference[i]);
add_reference(frame_size,frame,reference[i],i,number_of_references,reference);
}
printf("\nNumber of faults: %d \nNumber of hits: %d\n",faults,hits );
}

OUTPUT

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

EXPERIMENT NUMBER: 7
Objective: Implementation of Process Synchronization.
Content: Process synchronization is a critical concept in operating systems and concurrent
programming, ensuring that multiple processes or threads coordinate their access to shared resources
in a controlled manner to avoid conflicts and maintain data integrity. It involves techniques and
mechanisms such as locks, semaphores, mutexes, and barriers to manage access to shared variables,
files, or other resources.

a) Dining Philosophers
Introduction: The Dining Philosophers problem is a classic synchronization problem in computer
science that illustrates the challenges of resource allocation among multiple processes. In this
scenario, a number of philosophers sit at a dining table with a bowl of rice and chopsticks between
each pair of adjacent philosophers. To eat, a philosopher must pick up both chopsticks simultaneously,
which leads to potential deadlock if each philosopher picks up one chopstick and waits indefinitely
for the other. Solutions to this problem typically involve protocols like resource hierarchy, where
philosophers are required to acquire resources (chopsticks) in a specific order or use techniques like
semaphore-based mutual exclusion to ensure that philosophers can eat without causing deadlock or
starvation among them.

#include "stdio.h"
#include "stdlib.h"
#include "sys/wait.h"
#include "unistd.h"
#include "pthread.h"

pthread_t philosophers[50];
pthread_mutex_t chopsticks[50];
int n;
void *thinkEatRepeat(int i)
{
printf("%d Thinking ..\n",i+1 );
pthread_mutex_lock(&chopsticks[i]);
pthread_mutex_lock(&chopsticks[(i+1)%n]);
printf("%d eating...\n",i+1 );
sleep(1);
pthread_mutex_unlock(&chopsticks[i]);
pthread_mutex_unlock(&chopsticks[(i+1)%n]);

printf("\t%d Finished eating\n", i+1);

return NULL;
}

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

int main()
{
printf("Enter number of philosophers: ");
scanf("%d",&n);
int i;
for(i=0;i<n;i++)
{
pthread_mutex_init(&chopsticks[i],NULL);
}
for(i=0;i<n;i++)
{
pthread_create(&philosophers[i],NULL,thinkEatRepeat,i);
}
for(i=0;i<n;i++)
{
pthread_join(philosophers[i],NULL);
}
/*for(i=0;i<n;i++)
{
pthread_mutex_destroy(&chopsticks[i]);
}*/
}

OUTPUT

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

b) Producer-Consumer
Introduction: Process synchronization in the context of the Producer-Consumer problem involves
coordinating the interaction between two types of processes: producers, which generate data, and
consumers, which consume that data. The challenge lies in ensuring that producers do not produce
data too quickly for consumers to process, leading to data loss or inefficiency. Various synchronization
mechanisms such as semaphores, mutex locks, and condition variables are employed to achieve
mutual exclusion and coordination between producers and consumers. Typically, producers wait when
the buffer is full, and consumers wait when the buffer is empty, ensuring data integrity and efficient
resource utilization. Proper synchronization ensures that producers and consumers operate efficiently
without conflicts, ensuring data integrity and system stability in concurrent programming
environments.

#include "stdio.h"
#include "stdlib.h"
#include "pthread.h"
#include "semaphore.h"

#define BUFFER_SIZE 16

sem_t fill;
sem_t empty;

pthread_t producerThread[50], consumerThread[50];

int buffer[BUFFER_SIZE];
int counter;

//pthread_mutex_t mutex;
sem_t mutex;

void init()
{
sem_init(&mutex,0,1);
//pthread_mutex_init(&mutex,NULL);
sem_init(&fill,1,0);
sem_init(&empty,1,BUFFER_SIZE);
counter=0;
}

void produce(int item)

{
buffer[counter++]=item;
}

int consume()
{
counter--;

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

return buffer[counter];
}

void *producer(void *param)

{
int item;
item=rand()%5;
sem_wait(&empty);
/*printf("sem_wait = %d\n",wait );
int val;
printf("emptyb=%d\n", sem_getvalue(&empty,&val));
printf("%d\n",val );
printf("emptya=%d\n", sem_getvalue(&empty,&val));
printf("%d\n",val );*/
//pthread_mutex_lock(&mutex);
sem_wait(&mutex);
printf("Produced item: %d\n", item);
produce(item);

//pthread_mutex_unlock(&mutex);
sem_post(&mutex);
sem_post(&fill);
}

void *consumer(void *param)

{
int item;
sem_wait(&fill);
//pthread_mutex_lock(&mutex);
sem_wait(&mutex);
item =consume();
printf("Consumed item: %d\n",item );

sem_post(&mutex);
//pthread_mutex_unlock(&mutex);
sem_post(&fill);
}

int main()
{
int i,number_of_producers,number_of_consumers;
init();

printf("Enter number of producers: ");

scanf("%d",&number_of_producers);

printf("Enter number of consumers: ");

scanf("%d",&number_of_consumers);

for(i=0;i<number_of_producers;i++)
{
pthread_create(&producerThread[i],NULL,producer,NULL);
CSE (IOT), GNIOT APPROVED BY
HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

}
for(i=0;i<number_of_consumers;i++)
{
pthread_create(&consumerThread[i],NULL,consumer,NULL);
}
for(i=0;i<number_of_producers;i++)
{
pthread_join(producerThread[i],NULL);
}
for(i=0;i<number_of_consumers;i++)
{
pthread_join(consumerThread[i],NULL);
}
return 0;
}

OUTPUT

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

c) Readers Writers
Introduction: Process synchronization in the context of readers-writers problem addresses how
concurrent processes (readers and writers) access shared resources like data or files in a controlled
manner to prevent conflicts and ensure data consistency. Readers can access the resource
simultaneously as long as no writer is currently accessing it, enabling multiple processes to read
concurrently. Writers, however, need exclusive access to the resource to maintain data integrity,
meaning no other readers or writers should access the resource while a writer is writing. Various
synchronization mechanisms like semaphores or mutex locks are employed to coordinate access and
ensure that readers and writers do not interfere with each other improperly, thereby preventing issues
such as data corruption or inconsistent reads. Proper implementation of readers-writers
synchronization is crucial for efficient and reliable concurrent processing in operating systems and
multi-threaded applications.

#include "stdio.h"
#include "string.h"
#include "pthread.h"
#include "semaphore.h"
#include "stdlib.h"
#include "unistd.h"
#define BUFFER_SIZE 16

int buffer[BUFFER_SIZE];
sem_t database,mutex;
int counter, readerCount;
pthread_t readerThread[50],writerThread[50];

void init()
{
sem_init(&mutex,0,1);
sem_init(&database,0,1);
counter=0;
readerCount=0;
}

void *writer(void *param)

{
sem_wait(&database);
int item;
item=rand()%5;
buffer[counter]=item;
printf("Data writen by the writer%d is %d\n", (*(int *)param), buffer[counter]);
counter++;
sleep(1);

sem_post(&database);
CSE (IOT), GNIOT APPROVED BY
HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

void *reader(void *param)

{
sem_wait(&mutex);
readerCount++;
if(readerCount==1)
{
sem_wait(&database);
}
sem_post(&mutex);
counter--;
printf("Data read by the reader%d is %d\n", (*(int *) param), buffer[counter]);
sleep(1);

sem_wait(&mutex);
readerCount--;
if(readerCount==0)
{
sem_post(&database);
}
sem_post(&mutex);
}

int main()
{
init();
int no_of_writers,no_of_readers;
printf("Enter number of readers: ");
scanf("%d",&no_of_readers);
printf("Enter number of writers: ");
scanf("%d",&no_of_writers);
int i;
for(i=0;i<no_of_writers;i++)
{
pthread_create(&writerThread[i],NULL,writer,&i);
}
for(i=0;i<no_of_readers;i++)
{
pthread_create(&readerThread[i],NULL,reader, &i);
}
for(i=0;i<no_of_writers;i++)
{
pthread_join(writerThread[i],NULL);
}
for(i=0;i<no_of_readers;i++)
{

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

pthread_join(readerThread[i],NULL);
}
}

OUTPUT

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

d) Sleeping Barber
Introduction: The Sleeping Barber problem is a classic synchronization issue in operating systems
and concurrent programming, illustrating challenges with resource management and mutual
exclusion. In this scenario, a barber operates in a shop with a limited number of chairs for waiting
customers. If a customer arrives and all chairs are occupied, they either leave or wait if there is space.
When the barber finishes cutting hair, they check for waiting customers and continue if present;
otherwise, they sleep until a customer arrives. Synchronization mechanisms like semaphores or
mutexes are used to ensure that the barber and customers access shared resources, like the waiting
chairs, in a controlled manner, preventing issues like race conditions or deadlock. The problem
highlights the need for careful synchronization to avoid scenarios where the barber is idle while there
are waiting customers or where customers are turned away unnecessarily.

#include "stdio.h"
#include "stdlib.h"
#include "unistd.h"
#include "pthread.h"
#include "semaphore.h"
#include "stdbool.h"

sem_t barberReady,accessWRseats,customerReady;
int numberofFreeWRSeats;
int n;
pthread_t customersThread[100];
int no_of_customers;

void *barber(void *params)

{
int haircuts = no_of_customers-1;
while(true)
{
sem_wait(&customerReady);
sem_wait(&accessWRseats);
numberofFreeWRSeats++;
sem_post(&barberReady);
no_of_customers--;
printf("Cutting hair, waiting for next customer\n");
sem_post(&accessWRseats);
printf("Barber: , chairs left=%d\n",numberofFreeWRSeats);
}
printf("Closing shop\n");

void *customer(void *params)

CSE (IOT), GNIOT APPROVED BY
HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

{
int haircuts=1;
while(haircuts>0)
{
sem_wait(&accessWRseats);
if(numberofFreeWRSeats>0)
{
numberofFreeWRSeats--;
printf("Customer taking a seat\n");
sem_post(&customerReady);
haircuts--;
sleep(1);
sem_post(&accessWRseats);
sem_wait(&barberReady);
printf("Customer %d getting haircut\n",*(int *)params );
}
else
{
sem_post(&accessWRseats);
printf("Customer%d couldn't get a haircut,numberofFreeWRSeats=%d\n",*(int
*)params,numberofFreeWRSeats );
}
}
}

void init()
{
sem_init(&barberReady,0,0);
sem_init(&accessWRseats,0,1);
sem_init(&customerReady,0,0);
numberofFreeWRSeats=n;
}

int main()
{
int i;
printf("Enter number of waiting room seats: ");
scanf("%d",&n);
init();
printf("Enter number of customers: ");
scanf("%d",&no_of_customers);
for(i=0;i<no_of_customers;i++)
{
if(i==0)
{
pthread_create(&customersThread[i],NULL,barber,&i);
}
else
CSE (IOT), GNIOT APPROVED BY
HOD CSE (IOT)
 OPERATING SYSTEM LAB MANUAL (BCS-451)

pthread_create(&customersThread[i],NULL,customer,&i);
}
for(i=0;i<no_of_customers;i++)
{
pthread_join(customersThread[i],NULL);
}
}

OUTPUT

CSE (IOT), GNIOT APPROVED BY

HOD CSE (IOT)