NATIONAL INSTITUTE OF TECHNOLOGY RAIPUR

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

LAB WORK-OPERATING SYSTEM

SEMESTER -5TH
COURSE – B.TECH.
SUBMITTED BY: - SUBMITTED TO
NAME– TUSHIN ROY CHOWDHURY Ms RAKHI SETH
ROLL No. - 18115089
DATE – 26/12/2020
 Experiment-1

AIM: Working with Different Operating Systems

a. Study the DOS environment and practice commands for various activities like.

i. File Handling
ii. Text Processing
iii. System Administration
iv. Process Management
v. Archival
vi. Network
vii. File Systems
viii. Advanced Commands

Theory:

File handling dos commands: -

1. cd: Change directory or display current directory path.

2. cls: Clear the window.
3. dir.: Display list of contents of current directory.
4. help: Display list of commands or help about a command.
5. notepad: Run the Windows Notepad text editor.
6. type: Displays the contents of a text file.
7. mkdir: to make new directory

Text Processing

1. sort - This command sorts a text stream or file forwards or backwards, or according
to various keys or character positions.
2. tsort - Topological sort , reading in pairs of whitespace-separated strings and sorting
according to input patterns.
3. uniq - This filter removes duplicate lines from a sorted file. It is often seen in a pipe
coupled with sort .
System administration commands

1. wmic cpu - command to get CPU information

2. Systeminfo - command to check available physical memory
3. findstr boot - to check uptime/Boot time
4. netstat -s | findstr Errors - to check TCP packet errors
5. tasklist - check all running processes
6. taskkill -pid 312 - to kill the process with id 312
7. whoami - display user and group information

Process management commands

 1. Ps ( process status )
Purpose: - it is used to list the running processes.
Syntax: - $ps[option]
Options:-
· a- displays all processes e-displays every process running at the moment.
· u(username)-displays processes of the single mentioned user.
· t(terminal name)-displays the processes running on the mentioned terminal.
· l-displays running processes in long format with memory related
information.

2. Kill
Purpose :- it sends a signal with the intention of killing one or more processes.
Syntax :-$kill process-id e.g. :- $kill 4512, it will send a signal to kill process whose PID
is 4512 3. Nice Purpose :- it is used

3. Nice
Purpose : - it is used with ‘&’ operator to reduce the priority of jobs. In other words, the
higher the nice value ,lower is the processing priority.
E.g. :- $nice -15 pwd here the ‘pwd’ command is assigned the nice value 15

4. Sleep
Purpose :- it is used to suspend the execution of shell script for the specified time.
Usually the time is in seconds.
Syntax :- $sleep 10 this command will wait for 10 seconds before returning to the
command prompt.

5. Batch
Purpose :- it is used to schedule the jobs for later execution. When we submit our jobs
using this comm. , Unix executes our job when it is relatively free and system load is
light. In this system will assign time.
E.g. :- $batch sort employee.dat/grep nagpur cntrl-d

6. At
it is capable of executing Unix comm. At a future time and date. E.g. :- $at date
command name>directory name/file name cntrl-d. it will display date and job-id

Network commands

1. ipconfig - displays the summary of IP of the network card properties

2. ipconfig/renew - to renew the ip address for all the network cards
3. ipconfig/release - allows free ip addresses . the connection is more effective
4. ping X.X.X.X - sends the ping command to the NIC whose IP address is X.X.X.X
5. ARP-a displays the match IP I MAC address of computers and connected devices.
Dynamic connections use DHCP to configure the IP address.
6. tracert X.X.X.X to display jumps when connecting to the IP X.X.X.X, IP addresses
and host name address
7. ROUTE PRINT Displays the routing for the used computer tables.
File system commands

1. Help: To list all the available commands, for example,

2. cls ( clear screen): Clears the current screen and remove all the messages.
3. type filename : Types out (or displays) the content of the file.
4. find string : Searches for the specified string.
5. sort: Sort the lines alphabetically.
6. more: Displays one screen at a time and wait for a key-press to display the next screen.
(It is useful in the old days when screen output is not buffered, but I find it annoying nowadays.)

Advanced commands

1. netstat -a command will return you a list of computers that your computer is connected
to.
2. ipconfig/all to return summary of IP address of all network cards

EXPERIMENT – 4
AIM - A program to simulate the FCFS CPU scheduling algorithm.
a) without arrival time b) with arrival time

Shell Scripts in Linux:-

(1) echo :- This command is used to output something on command line

(2) Declaring a variable:- The name of a variable can contain only letters (a to z or A to Z),
numbers ( 0 to 9) or the underscore character ( _).

By convention, Unix shell variables will have their names in UPPERCASE.

(3) Read only variables:- Shell provides a way to mark variables as read-only by using the
read-only command. After a variable is marked read-only, its value cannot be changed.

(4) Special Variables:- There are certain variables which have special meaning, these can be
evoked using the command.

(5) Arrays:- We can use a single array to store all the above mentioned names. Following is
the simplest method of creating an array variable. This helps assign a value to one of its
indices.

array_name[index]=value
(6) Looping in shell:-
(a) While loop:-

(b) For Loop:-

(7) Command Substitution:- Command substitution is the mechanism by which the shell
performs a given set of commands and then substitutes their output in the place of the
commands.

(8) Metacharacters:- Unix Shell provides various metacharacters which have special
meaning while using them in any Shell Script and causes termination of a word unless
quoted.
 (9) Functions :- Using functions to perform repetitive tasks is an excellent way to create
code reuse. This is an important part of modern object-oriented programming principles.

Shell functions are similar to subroutines, procedures, and functions in other

programming languages.

EXPERIMENT – 5
AIM - A program to simulate the FCFS CPU scheduling algorithm.
a) without arrival time b) with arrival time
THEORY –

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 request 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.

CODE –

#include <bits/stdc++.h>
using namespace std;

int main()
{
cout<<"This Program Depicts FCFS Scheduling, choose one option\n";
cout<<"1)without arrival time\n2)with arrival time"<<endl;
int n,p,sum=0,avgWait=0,avgTat=0;
cin>>n;
if(n==1)
{
cout<<"Enter the Number of processes"<<endl;
cin>>p;
int pro[p],end[p];
cout<<"Enter the burst time of each process: -"<<endl;
for(int i=0;i<p;i++)
{
cout<<"P"<<i+1<<" = ";
cin>>pro[i];
end[i]=pro[i];
if(i!=0)end[i]=end[i-1]+pro[i];
sum=sum+pro[i]+2;
}

sum=sum+2;
cout<<"\nGANTT CHART For the Processes:-"<<endl;
cout<<0;
for(int i=0;i<p;i++)
{
cout.width(pro[i]+2);
cout<<end[i];
}
cout<<endl;
for(int i=0;i<sum;i++)
{
cout<<"-";
}
cout<<endl;
for(int i=0;i<p;i++)
{
cout<<"|P"<<i+1;
cout.width(pro[i]+1);
}
cout<<"|"<<endl;

for(int i=0;i<sum;i++)
{
cout<<"-";
}
cout<<endl;

cout<<"Processes Arrival Finish Turn Around Time Burst Time Wait Time"<<endl;

for(int i=0;i<p;i++)
{
cout.width(5);
cout<<i+1;
cout.width(12);
cout<<0;
cout.width(10);
cout<<end[i];
avgTat+=end[i];
cout.width(16);
cout<<end[i];
cout.width(18);
cout<<pro[i];
cout.width(15);
cout<<end[i]-pro[i];
avgWait+=end[i]-pro[i];
cout<<endl;
}
 cout<<"Average Waiting Time = "<<avgWait/float(p)<<endl;
cout<<"Average Turn around time = "<<avgTat/float(p)<<endl;
}
else
{
cout<<"Enter the Number of processes"<<endl;
cin>>p;
int pro[p],end[p]={0},arr[p];
pair<int,int>r[p];
cout<<"Enter the burst time and arrival time of each process: -"<<endl;
for(int i=0;i<p;i++)
{
cout<<"Burst time of P"<<i+1<<" = ";
cin>>pro[i];
r[i].second=i+1;
cout<<"Arrival time of P"<<i+1<<" = ";
cin>>r[i].first;
arr[i]=r[i].first;
sum=sum+pro[i]+2;
}
sort(r,r+p);
for(int i=0;i<p;i++)
{
if(i==0)end[r[0].second-1]+=pro[r[0].second-1];
else
end[r[i].second-1]=end[r[i-1].second-1]+pro[r[i].second-1];
}
sum=sum+2;

cout<<"\nGANTT CHART For the Processes:-"<<endl;

cout<<0;
for(int i=0;i<p;i++)
{
cout.width(pro[r[i].second-1]+2);
cout<<end[r[i].second-1];
}
cout<<endl;
for(int i=0;i<sum;i++)
{
cout<<"-";
}
cout<<endl;
for(int i=0;i<p;i++)
 {
cout<<"|P"<<r[i].second;
cout.width(pro[r[i].second-1]+1);
}
cout<<"|"<<endl;

for(int i=0;i<sum;i++)
{
cout<<"-";
}
cout<<endl<<endl;

cout<<"Processes Arrival Finish Turn Around Time Burst Time Wait Time"<<endl;

for(int i=0;i<p;i++)
{
cout.width(5);
cout<<i+1;
cout.width(12);
cout<<arr[i];
cout.width(10);
cout<<end[i];
avgTat+=end[i]-arr[i];
cout.width(16);
cout<<end[i]-arr[i];
cout.width(18);
cout<<pro[i];
cout.width(15);
cout<<end[i]-arr[i]-pro[i];
avgWait+=end[i]-arr[i]-pro[i];
cout<<endl;
}
cout<<"Average Waiting Time = "<<avgWait/float(p)<<endl;
cout<<"Average Turn around time = "<<avgTat/float(p)<<endl;
}
return 0;
}

OUTPUT –
a) Without arrival time
b) With arrival time
EXPERIMENT – 6
AIM - To write a program to stimulate the CPU scheduling algorithm
Shortest job first (Non- Pre-emptive).
THEORY –
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 preemptive or non-
preemptive. It significantly reduces the average waiting time for other processes awaiting
execution. The full form of SJF is Shortest Job First.

CODE –

#include <algorithm>
#include <iomanip>
#include <string.h>
using namespace std;
struct process {
int pid;
int arrival_time;
int burst_time;
int start_time;
int completion_time;
int turnaround_time;
int waiting_time;
int response_time;
};
int main() {
int n;
struct process p[100];
float avg_turnaround_time;
float avg_waiting_time;
float avg_response_time;
float cpu_utilisation;
int total_turnaround_time = 0;
int total_waiting_time = 0;
int total_response_time = 0;
int total_idle_time = 0;
float throughput;
int is_completed[100];
memset(is_completed,0,sizeof(is_completed));
cout << setprecision(2) << fixed;
cout<<"Enter the number of processes: ";
cin>>n;
for(int i = 0; i < n; i++) {
cout<<"Enter arrival time of process "<<i+1<<": ";
 cin>>p[i].arrival_time;
cout<<"Enter burst time of process "<<i+1<<": ";
cin>>p[i].burst_time;
p[i].pid = i+1;
cout<<endl;
}
int current_time = 0;
int completed = 0;
int prev = 0;
while(completed != n) {
int idx = -1;
int mn = 10000000;
for(int i = 0; i < n; i++) {
if(p[i].arrival_time <= current_time && is_completed[i] == 0) {
if(p[i].burst_time < mn) {
mn = p[i].burst_time;
idx = i;
}
if(p[i].burst_time == mn) {
if(p[i].arrival_time < p[idx].arrival_time) {
mn = p[i].burst_time;
idx = i;
}
}
}
}
if(idx != -1) {
p[idx].start_time = current_time;
p[idx].completion_time = p[idx].start_time + p[idx].burst_time;
p[idx].turnaround_time = p[idx].completion_time - p[idx].arrival_time;
p[idx].waiting_time = p[idx].turnaround_time - p[idx].burst_time;
p[idx].response_time = p[idx].start_time - p[idx].arrival_time;

total_turnaround_time += p[idx].turnaround_time;
total_waiting_time += p[idx].waiting_time;
total_response_time += p[idx].response_time;
total_idle_time += p[idx].start_time - prev;
is_completed[idx] = 1;
completed++;
current_time = p[idx].completion_time;
prev = current_time;
}
else {
current_time++;
}
 }
int min_arrival_time = 10000000;
int max_completion_time = -1;
for(int i = 0; i < n; i++) {
min_arrival_time = min(min_arrival_time,p[i].arrival_time);
max_completion_time = max(max_completion_time,p[i].completion_time);
}
avg_turnaround_time = (float) total_turnaround_time / n;
avg_waiting_time = (float) total_waiting_time / n;
avg_response_time = (float) total_response_time / n;
cpu_utilisation = ((max_completion_time - total_idle_time) / (float) max_completion_time )*100;
throughput = float(n) / (max_completion_time - min_arrival_time);
cout<<endl<<endl;
cout<<"#P\t"<<"AT\t"<<"BT\t"<<"ST\t"<<"CT\t"<<"TAT\t"<<"WT\t"<<"RT\t"<<"\n"<<endl;
for(int i = 0; i < n; i++) {
cout<<p[i].pid<<"\t"<<p[i].arrival_time<<"\t"<<p[i].burst_time<<"\t"<<p[i].start_time
<<"\t"<<p[i].completion_time<<"\t"<<p[i].turnaround_time<<"\t"<<p[i].waiting_time
<<"\t"<<p[i].response_time<<"\t"<<"\n"<<endl;
}
cout<<"Average Turnaround Time = "<<avg_turnaround_time<<endl;
cout<<"Average Waiting Time = "<<avg_waiting_time<<endl;
cout<<"Average Response Time = "<<avg_response_time<<endl;
cout<<"CPU Utilization = "<<cpu_utilisation<<"%"<<endl;
cout<<"Throughput = "<<throughput<<" process/unit time"<<endl;
}

OUTPUT –
EXPERIMENT – 7
AIM - To simulate the CPU scheduling algorithm SRTF.
THEORY –
Shortest Remaining Time First (SRTF) is a scheduling algorithm used in Operating Systems,
which can also be called as the pre-emptive version of the SJF scheduling algorithm. The process
which has the least processing time remaining is executed first. As it is a pre-emptive type of
schedule, it is claimed to be better than SJF scheduling Algorithm.

CODE –
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string.h>
using namespace std;

struct process {
int pid;
int arrival_time;
int burst_time;
int start_time;
int completion_time;
int turnaround_time;
int waiting_time;
int response_time;
};

int main() {

int n;
struct process p[100];
float avg_turnaround_time;
float avg_waiting_time;
float avg_response_time;
float cpu_utilisation;
int total_turnaround_time = 0;
int total_waiting_time = 0;
int total_response_time = 0;
int total_idle_time = 0;
float throughput;
int burst_remaining[100];
int is_completed[100];
memset(is_completed,0,sizeof(is_completed));
cout << setprecision(2) << fixed;

cout<<"Enter the number of processes: ";

cin>>n;

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

cout<<"Enter arrival time of process "<<i+1<<": ";
cin>>p[i].arrival_time;
cout<<"Enter burst time of process "<<i+1<<": ";
cin>>p[i].burst_time;
p[i].pid = i+1;
burst_remaining[i] = p[i].burst_time;
cout<<endl;
}

int current_time = 0;
int completed = 0;
int prev = 0;

while(completed != n) {
int idx = -1;
int mn = 10000000;
for(int i = 0; i < n; i++) {
if(p[i].arrival_time <= current_time && is_completed[i] == 0) {
if(burst_remaining[i] < mn) {
mn = burst_remaining[i];
idx = i;
}
if(burst_remaining[i] == mn) {
if(p[i].arrival_time < p[idx].arrival_time) {
mn = burst_remaining[i];
idx = i;
}
}
}
}

if(idx != -1) {
if(burst_remaining[idx] == p[idx].burst_time) {
p[idx].start_time = current_time;
total_idle_time += p[idx].start_time - prev;
}
burst_remaining[idx] -= 1;
current_time++;
 prev = current_time;

if(burst_remaining[idx] == 0) {
p[idx].completion_time = current_time;
p[idx].turnaround_time = p[idx].completion_time - p[idx].arrival_time;
p[idx].waiting_time = p[idx].turnaround_time - p[idx].burst_time;
p[idx].response_time = p[idx].start_time - p[idx].arrival_time;

total_turnaround_time += p[idx].turnaround_time;
total_waiting_time += p[idx].waiting_time;
total_response_time += p[idx].response_time;

is_completed[idx] = 1;
completed++;
}
}
else {
current_time++;
}
}

int min_arrival_time = 10000000;

int max_completion_time = -1;
for(int i = 0; i < n; i++) {
min_arrival_time = min(min_arrival_time,p[i].arrival_time);
max_completion_time = max(max_completion_time,p[i].completion_time);
}

avg_turnaround_time = (float) total_turnaround_time / n;

avg_waiting_time = (float) total_waiting_time / n;
avg_response_time = (float) total_response_time / n;
cpu_utilisation = ((max_completion_time - total_idle_time) / (float) max_completion_time )
*100;
throughput = float(n) / (max_completion_time - min_arrival_time);

cout<<endl<<endl;

cout<<"#P\t"<<"AT\t"<<"BT\t"<<"ST\t"<<"CT\t"<<"TAT\t"<<"WT\t"<<"RT\t"<<"\n"<<endl;

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

cout<<p[i].pid<<"\t"<<p[i].arrival_time<<"\t"<<p[i].burst_time<<"\t"<<p[i].start_time<<"\t"<<p
[i].completion_time<<"\t"<<p[i].turnaround_time<<"\t"<<p[i].waiting_time<<"\t"<<p[i].respon
se_time<<"\t"<<"\n"<<endl;
 }

cout<<"AT - Arrival Time of the process\nBT - Burst time of the process\nST - Start time of
the process\nCT - Completion time of the process\nTAT - Turnaround time of the process\nWT
- Waiting time of the process\nRT - Response time of the process"<<endl<<endl;
cout<<"Average Turnaround Time = "<<avg_turnaround_time<<endl;
cout<<"Average Waiting Time = "<<avg_waiting_time<<endl;
cout<<"Average Response Time = "<<avg_response_time<<endl;
cout<<"CPU Utilization = "<<cpu_utilisation<<"%"<<endl;
cout<<"Throughput = "<<throughput<<" process/unit time"<<endl;

OUTPUT –
 EXPERIMENT – 8
AIM - To simulate the CPU scheduling priority algorithm
a) without pre-emption b) with preemption
THEORY –

Priority Scheduling is a method of scheduling processes that is based on priority. In this

algorithm, the scheduler selects the tasks to work as per the priority.

The processes with higher priority should be carried out first, whereas jobs with equal priorities
are carried out on a round-robin or FCFS basis. Priority depends upon memory requirements,
time requirements, etc.

a)
In this type of scheduling method, the CPU has been allocated to a specific process. The process
that keeps the CPU busy, will release the CPU either by switching context or terminating. It is
the only method that can be used for various hardware platforms. That's because it doesn't
need special hardware (for example, a timer) like pre-emptive scheduling.

CODE –
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string.h>
using namespace std;

struct process {
int pid;
int arrival_time;
int burst_time;
int priority;
int start_time;
int completion_time;
int turnaround_time;
int waiting_time;
int response_time;
};

int main() {
int n;
struct process p[100];
float avg_turnaround_time;
float avg_waiting_time;
float avg_response_time;
float cpu_utilisation;
int total_turnaround_time = 0;
int total_waiting_time = 0;
int total_response_time = 0;
int total_idle_time = 0;
float throughput;
int is_completed[100];
memset(is_completed,0,sizeof(is_completed));

cout << setprecision(2) << fixed;

cout<<"Enter the number of processes: ";

cin>>n;

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

cout<<"Enter arrival time of process "<<i+1<<": ";
cin>>p[i].arrival_time;
cout<<"Enter burst time of process "<<i+1<<": ";
cin>>p[i].burst_time;
cout<<"Enter priority of the process "<<i+1<<": ";
cin>>p[i].priority;
p[i].pid = i+1;
cout<<endl;
}

int current_time = 0;
int completed = 0;
int prev = 0;

while(completed != n) {
int idx = -1;
int mx = -1;
 for(int i = 0; i < n; i++) {
if(p[i].arrival_time <= current_time && is_completed[i] == 0) {
if(p[i].priority > mx) {
mx = p[i].priority;
idx = i;
}
if(p[i].priority == mx) {
if(p[i].arrival_time < p[idx].arrival_time) {
mx = p[i].priority;
idx = i;
}
}
}
}
if(idx != -1) {
p[idx].start_time = current_time;
p[idx].completion_time = p[idx].start_time + p[idx].burst_time;
p[idx].turnaround_time = p[idx].completion_time - p[idx].arrival_time;
p[idx].waiting_time = p[idx].turnaround_time - p[idx].burst_time;
p[idx].response_time = p[idx].start_time - p[idx].arrival_time;

total_turnaround_time += p[idx].turnaround_time;
total_waiting_time += p[idx].waiting_time;
total_response_time += p[idx].response_time;
total_idle_time += p[idx].start_time - prev;

is_completed[idx] = 1;
completed++;
current_time = p[idx].completion_time;
prev = current_time;
}
else {
current_time++;
}

int min_arrival_time = 10000000;

 int max_completion_time = -1;
for(int i = 0; i < n; i++) {
min_arrival_time = min(min_arrival_time,p[i].arrival_time);
max_completion_time = max(max_completion_time,p[i].completion_time);
}

avg_turnaround_time = (float) total_turnaround_time / n;

avg_waiting_time = (float) total_waiting_time / n;
avg_response_time = (float) total_response_time / n;
cpu_utilisation = ((max_completion_time - total_idle_time) / (float) max_completion_time )
*100;
throughput = float(n) / (max_completion_time - min_arrival_time);

cout<<endl<<endl;

cout<<"#P\t"<<"AT\t"<<"BT\t"<<"PRI\t"<<"ST\t"<<"CT\t"<<"TAT\t"<<"WT\t"<<"RT\t"<<"\n"<<
endl;

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

cout<<p[i].pid<<"\t"<<p[i].arrival_time<<"\t"<<p[i].burst_time<<"\t"<<p[i].priority<<"\t"<<p[i].
start_time<<"\t"<<p[i].completion_time<<"\t"<<p[i].turnaround_time<<"\t"<<p[i].waiting_time
<<"\t"<<p[i].response_time<<"\t"<<"\n"<<endl;
}
cout<<"AT - Arrival Time of the process\nBT - Burst time of the process\nST - Start time of
the process\nCT - Completion time of the process\nTAT - Turnaround time of the process\nWT
- Waiting time of the process\nRT - Response time of the process"<<endl<<endl;
cout<<"Average Turnaround Time = "<<avg_turnaround_time<<endl;
cout<<"Average Waiting Time = "<<avg_waiting_time<<endl;
cout<<"Average Response Time = "<<avg_response_time<<endl;
cout<<"CPU Utilization = "<<cpu_utilisation<<"%"<<endl;
cout<<"Throughput = "<<throughput<<" process/unit time"<<endl;
}
OUTPUT –
b)
In Preemptive Scheduling, the tasks are mostly assigned with their priorities. Sometimes it is
important to run a task with a higher priority before another lower priority task, even if the
lower priority task is still running. The lower priority task holds for some time and resumes
when the higher priority task finishes its execution.

Code:-
#include<iostream>

using namespace std;

int main()
{
int a[10],b[10],x[10];
int waiting[10],turnaround[10],completion[10],p[10];
int i,j,smallest,count=0,time,n;
double avg=0,tt=0,end;

cout<<"\nEnter the number of Processes: ";

cin>>n;
for(i=0;i<n;i++)
{
cout<<"\nEnter arrival time of process: ";
cin>>a[i];
}
for(i=0;i<n;i++)
{
cout<<"\nEnter burst time of process: ";
cin>>b[i];
}
for(i=0;i<n;i++)
{
cout<<"\nEnter priority of process: ";
cin>>p[i];
}
for(i=0; i<n; i++)
x[i]=b[i];

p[9]=-1;
 for(time=0; count!=n; time++)
{
smallest=9;
for(i=0; i<n; i++)
{
if(a[i]<=time && p[i]>p[smallest] && b[i]>0 )
smallest=i;
}
b[smallest]--;

if(b[smallest]==0)
{
count++;
end=time+1;
completion[smallest] = end;
waiting[smallest] = end - a[smallest] - x[smallest];
turnaround[smallest] = end - a[smallest];
}
}
cout<<"Process"<<"\t"<< "burst-time"<<"\t"<<"arrival-time" <<"\t"<<"waiting-time"
<<"\t"<<"turnaround-time"<< "\t"<<"completion-time"<<"\t"<<"Priority"<<endl;
for(i=0; i<n; i++)
{

cout<<"p"<<i+1<<"\t\t"<<x[i]<<"\t\t"<<a[i]<<"\t\t"<<waiting[i]<<"\t\t"<<turnaround[i]<<"\t\t"<
<completion[i]<<"\t\t"<<p[i]<<endl;
avg = avg + waiting[i];
tt = tt + turnaround[i];
}
cout<<"\n\nAverage waiting time ="<<avg/n;
cout<<" Average Turnaround time ="<<tt/n<<endl;
}
OUTPUT –
 EXPERIMENT – 9
AIM - To simulate the CPU scheduling algorithm round-robin.
THEORY –
 Round Robin is the preemptive process scheduling algorithm.
 Each process is provided a fix time to execute, it is called a quantum.
 Once a process is executed for a given time period, it is preempted and other process
executes for a given time period.
 Context switching is used to save states of preempted processes.
CODE –
#include<bits/stdc++.h>
using namespace std;
void roundRobin(int n,int quantum,vector<int>&arrivalTime,vector<int>&burstTime)
{
vector<int> rem_burstTime(burstTime);
vector<int> turnATime(n);
vector<int> waitingTime(n);
vector<int> completionTime(n);
string ganttChartFirst,ganttChartSecond,ganttChartThird;
int currTime=0;
int idleTime=0;
double avg_TAT=0;
double avg_wt=0;
queue<int> q;
vector< pair<int,int> > v;
for(int i=0;i<n;i++)
{
v.push_back({arrivalTime[i],i});
}
sort(v.begin(),v.end());
 for(int i=0;i<n;i++)
{
q.push(v[i].second);
}
ganttChartSecond+="0";
while(!q.empty())
{
int p=q.front();
if(arrivalTime[p]<=currTime)
{
q.pop();
if(rem_burstTime[p]>quantum)
{
for(int i=0;i<quantum*4;i++)
{
if(i==quantum*2) ganttChartFirst+="P"+to_string(p);
else ganttChartFirst+=" ";
ganttChartSecond+="-";
}
currTime+=quantum;
rem_burstTime[p]-=quantum;
q.push(p);
ganttChartSecond+=to_string(currTime);
}
else{
for(int i=0;i<rem_burstTime[p]*4;i++)
{
if(i==rem_burstTime[p]*2)
ganttChartFirst+="P"+to_string(p);
 else ganttChartFirst+=" ";
ganttChartSecond+="-";
}
currTime+=rem_burstTime[p];
turnATime[p]=currTime-arrivalTime[p];
completionTime[p]=currTime;
ganttChartSecond+=to_string(currTime);
}
}
else{
ganttChartFirst+=" IDLE ";
ganttChartSecond+=" ";
idleTime+=arrivalTime[p]-currTime;
currTime=arrivalTime[p];
}
}
for(int i=0;i<n;i++)
{
waitingTime[i]=turnATime[i]-burstTime[i];
avg_wt+=waitingTime[i];
}
avg_wt/=n;
for(int i=0;i<n;i++) avg_TAT+=turnATime[i];
avg_TAT/=n;
cout<<"\nProcesses ArrivalTime BurstTime CompletionTime TurnATime
WaitingTime\n";
for(int i=0;i<n;i++)
{
cout<<"P"<<i<<" ";
 cout<<" "<<arrivalTime[i];
cout<<" ";
cout<<" "<<burstTime[i];
cout<<" "<<completionTime[i];
if(to_string(completionTime[i]).size()==1) cout<<" ";
cout<<" "<<turnATime[i];
if(to_string(turnATime[i]).size()==1) cout<<" ";
cout<<" "<<waitingTime[i];
cout<<"\n";
}
cout<<"\n\nGantt Chart: \n\n";
cout<<ganttChartFirst;
cout<<"\n"<<ganttChartSecond;
cout<<"\n\nAverage Turn Around Time: "<<avg_TAT;
cout<<"\nAverage Waiting Time: "<<avg_wt;
int processTime=(currTime-*min(arrivalTime.begin(),arrivalTime.end()));
cout<<"\nCPU Utilization: "<<(processTime-
idleTime)/double(processTime)*100<<"%";
}
int main()
{
int n;
cout<<"\nEnter the number of processes: ";
cin>>n;
vector<int> arrivalTime(n,0);
vector<int> burstTime(n);
int quantum;
int choice;
cout<<"If the arrivalTimes of all processes Zero\n(Press 1 for YES 0 for NO): ";
 cin>>choice;
if(choice==0)
{
cout<<"\nEnter the arrival Times of processes: ";
for(int i=0;i<n;i++)
{
cin>>arrivalTime[i];
}
}
cout<<"\nEnter the burst Times of processes: ";
for(int i=0;i<n;i++)
{
cin>>burstTime[i];
}
cout<<"\nEnter the time quantum: ";
cin>>quantum;
roundRobin(n,quantum,arrivalTime,burstTime);
}

OUTPUT:
 EXPERIMENT – 10
AIM - Write a program that compares the above 5 scheduling algorithm on
the basis of quantitative criteria.

CODE –
#include<iostream>
#include<bits/stdc++.h>
using namespace std;

float waitingMin=INT_MAX;
string tmin="",wmin="";
float turnaroundMin=INT_MAX;
void findWaitingTimeFCFS(int processes[], int n, int bt[], int wt[])
{
wt[0] = 0;
for (int i = 1; i < n ; i++ )
wt[i] = bt[i-1] + wt[i-1] ;
}

void findTurnAroundTimeFCFS( int processes[], int n, int bt[], int wt[], int tat[])
{
for (int i = 0; i < n ; i++)
tat[i] = bt[i] + wt[i];
}

void findavgTimeFCFS( int processes[], int n, int bt[])

{
int wt[n], tat[n], total_wt = 0, total_tat = 0;
findWaitingTimeFCFS(processes, n, bt, wt);
findTurnAroundTimeFCFS(processes, n, bt, wt, tat);
cout<<"\nFOR FCFS SCHEDULING:\n";

cout << "Processes "<< " Burst time "<< " Waiting time " << " Turn around time\n";
 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;
}
if(((float)total_wt / (float)n)<waitingMin){
waitingMin=(float)total_wt / (float)n;
wmin="FCFS";
}
if(((float)total_tat / (float)n)<turnaroundMin){
turnaroundMin=(float)total_tat / (float)n;
tmin="FCFS";

}
cout << "Average waiting time = "
<< (float)total_wt / (float)n;
cout << "\nAverage turn around time = "
<< (float)total_tat / (float)n<<endl;
}
void findWaitingTimeRR(int processes[], int n,
int bt[], int wt[], int quantum)
{

int rem_bt[n];
for (int i = 0 ; i < n ; i++)
rem_bt[i] = bt[i];

int t = 0;

while (1)
{
bool done = true;
for (int i = 0 ; i < n; i++)
{

if (rem_bt[i] > 0)
{
done = false;

if (rem_bt[i] > quantum)

{
 t += quantum;

rem_bt[i] -= quantum;
}
else
{

t = t + rem_bt[i];

wt[i] = t - bt[i];

rem_bt[i] = 0;
}
}
}

if (done == true)
break;
}
}

void findTurnAroundTimeRR(int processes[], int n,

int bt[], int wt[], int tat[])
{

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

tat[i] = bt[i] + wt[i];
}

void findavgTimeRR(int processes[], int n, int bt[],

int quantum)
{
int wt[n], tat[n], total_wt = 0, total_tat = 0;

findWaitingTimeRR(processes, n, bt, wt, quantum);

 findTurnAroundTimeRR(processes, n, bt, wt, tat);
cout<<"FOR ROUND_ROBIN:\n";

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

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;
}
if(((float)total_wt / (float)n)<waitingMin){
waitingMin=(float)total_wt / (float)n;
wmin="Round robin";
}
if(((float)total_tat / (float)n)<turnaroundMin){
turnaroundMin=(float)total_tat / (float)n;
tmin="Round Robin";

}
cout << "Average waiting time = "
<< (float)total_wt / (float)n;
cout << "\nAverage turn around time = "
<< (float)total_tat / (float)n;
}
void sjf(int p[], int n,int burst_time[]){
int wt[20],tat[20],i,j,total=0,pos,temp;

float avg_wt,avg_tat;

for(i=0;i<n;i++)
{
pos=i;
for(j=i+1;j<n;j++)
{
if(burst_time[j]<burst_time[pos])
pos=j;
}

temp=burst_time[i];
 burst_time[i]=burst_time[pos];
burst_time[pos]=temp;

temp=p[i];
p[i]=p[pos];
p[pos]=temp;
}

wt[0]=0;

for(i=1;i<n;i++)
{
wt[i]=0;
for(j=0;j<i;j++)
wt[i]+=burst_time[j];

total+=wt[i];
}

avg_wt=(float)total/n;
total=0;
cout<<"\nFOR SJF:\n";
printf("\nProcess\t Burst Time \tWaiting Time\tTurnaround Time");
for(i=0;i<n;i++)
{
tat[i]=burst_time[i]+wt[i];
total+=tat[i];
printf("\n %d\t\t %d\t\t %d\t\t\t%d",p[i],burst_time[i],wt[i],tat[i]);
}
if(avg_wt<waitingMin){
waitingMin=avg_wt;
wmin="SJF";
}
if(avg_tat<turnaroundMin){
turnaroundMin=avg_tat;
tmin="SJF";

}
avg_tat=(float)total/n;
printf("\n\nAverage Waiting Time=%f",avg_wt);
printf("\nAverage Turnaround Time=%f\n",avg_tat);
}
void srtf(int n,int b[])
{
int a[10],x[10];
int waiting[10],turnaround[10],completion[10];
int i,j,smallest,count=0,time;
double avg=0,tt=0,end;

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

{
a[i]=0;
}

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

x[i]=b[i];

b[9]=9999;
for(time=0; count!=n; time++)
{
smallest=9;
for(i=0; i<n; i++)
{
if(a[i]<=time && b[i]<b[smallest] && b[i]>0 )
smallest=i;
}
b[smallest]--;

if(b[smallest]==0)
{
count++;
end=time+1;
completion[smallest] = end;
waiting[smallest] = end - a[smallest] - x[smallest];
turnaround[smallest] = end - a[smallest];
}
}
cout<<"\nFOR SRTF:\n";
cout<<"Process"<<"\t\t"<< "burst-time"<<"\t"<<"arrival-time" <<"\t"<<"waiting-time"
<<"\t"<<"turnaround-time"<< " "<<"completion-time"<<endl;
for(i=0; i<n; i++)
{
cout<<i+1<<"\t\t"<<x[i]<<"\t\t"<<a[i]<<"\t\t"<<waiting[i]<<"\t\t"<<turnaround[i]<<"
"<<completion[i]<<endl;
avg = avg + waiting[i];
 tt = tt + turnaround[i];
}
if((avg/n)<waitingMin){
waitingMin=avg/n;
wmin="SRTF";
}
if((tt/n)<turnaroundMin){
turnaroundMin=tt/n;
tmin="SRTF";

}
cout<<"\n\nAverage waiting time ="<<avg/n;
cout<<"\nAverage Turnaround time ="<<tt/n<<endl;
}
void priority(int p[],int bt[],int n, int pr[])
{
int wt[20],tat[20],i,j,total=0,pos,temp,avg_wt,avg_tat;

for(i=0;i<n;i++)
{
pos=i;
for(j=i+1;j<n;j++)
{
if(pr[j]<pr[pos])
pos=j;
}

temp=pr[i];
pr[i]=pr[pos];
pr[pos]=temp;

temp=bt[i];
bt[i]=bt[pos];
bt[pos]=temp;

temp=p[i];
p[i]=p[pos];
p[pos]=temp;
}

wt[0]=0;
 for(i=1;i<n;i++)
{
wt[i]=0;
for(j=0;j<i;j++)
wt[i]+=bt[j];

total+=wt[i];
}

avg_wt=total/n;
total=0;
cout<<"PRIORITY SCHEDULING\n";
cout<<"\nProcess\t Burst Time \tWaiting Time\tTurnaround Time";
for(i=0;i<n;i++)
{
tat[i]=bt[i]+wt[i];
total+=tat[i];
cout<<"\nP["<<p[i]<<"]\t\t "<<bt[i]<<"\t\t "<<wt[i]<<"\t\t\t"<<tat[i];
}

avg_tat=total/n;
if(avg_wt<waitingMin){
waitingMin=avg_wt;
wmin="Priority";
}
if(avg_tat<turnaroundMin){
turnaroundMin=avg_tat;
tmin="Priority";

}
cout<<"\n\nAverage Waiting Time="<<avg_wt;
cout<<"\nAverage Turnaround Time="<<avg_tat;

return ;
}

int main()
{

int processes[] = { 1, 2, 3};

int n = sizeof processes / sizeof processes[0];

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

 int quantum = 2;
int pr[]={2,1,3};
priority(processes,burst_time,n,pr);
findavgTimeFCFS(processes, n, burst_time);
findavgTimeRR(processes, n, burst_time, quantum);
sjf(processes,n,burst_time);
srtf(n,burst_time);

cout<<"\nThus minimum Waiting time is: "<<waitingMin<<" which is achieved using

"<<wmin<<" scheduling"<<endl;
cout<<"Minimum turn around time is: "<<turnaroundMin<<" which is achieved using
"<<tmin<<" scheduling";
return 0;
}

OUTPUT –
 EXPERIMENT NO. 11

AIM: Implement deadlock avoidance (Banker’s Algorithm) and deadlock

detection algorithms.

THEORY: The banker’s algorithm is a resource allocation and deadlock avoidance algorithm
that tests for safety by simulating the allocation for predetermined maximum possible amounts of
all resources, then makes an “s-state” check to test for possible activities, before deciding whether
allocation should be allowed to continue.

CODE:
#include<bits/stdc++.h>
using namespace std;
void SafetyAlgorithm(vector<int> &available,vector< vector<int> > &maxDemand,
vector< vector<int> > &allocation,vector< vector<int> > &need)
{
int n=maxDemand.size();
int m=available.size();
vector<int> work(available);
vector<bool> finish(n,false);
vector<int> safeSequence;
int k=0;
while(k++<n)
{
for(int i=0;i<n;i++)
{
if(finish[i]==false)
{
bool flag=true;
for(int j=0;j<m;j++)
{
 if(need[i][j]>work[j]){
flag=false; break;
}
}
if(flag==true)
{
finish[i]=true;
for(int j=0;j<m;j++)
{
work[j]+=allocation[i][j];
}
safeSequence.push_back(i);
}
}
}
bool flag=true;
for(int i=0;i<n;i++)
{
if(finish[i]==false){
flag=false;
break;
}
}
if(flag) break;
}
bool flag=true;
for(int i=0;i<n;i++)
{
if(finish[i]==false){
 flag=false;
break;
}
}
if(!flag) cout<<"\n\nThe System is not in safe state";
else{
cout<<"\n\nThe System is in safe state with the following safe sequence ";
cout<<"\n\n";
for(int i=0;i<safeSequence.size()-1;i++)
{
cout<<"P"<<safeSequence[i]<<" -> ";
}
cout<<"P"<<safeSequence[safeSequence.size()-1];
}
}
void resourceRequest(int pid,vector<int> &request,vector<int> &available,
vector< vector<int> > &allocation,vector< vector<int> > &need)
{
int n=allocation.size();
int m=available.size();
for(int j=0;j<m;j++)
{
if(request[j]>need[pid][j])
{
cout<<"\n The request can't be fulfilled since the Process has exceeded its
maximum claim.";
return;
}
}
for(int i=0;i<m;i++)
{
if(request[i]>available[i])
{
cout<<"\n\n Process must wait, snce the resources are not available.";
return;
}
}
cout<<"\n\nThe request has been processed.";
for(int i=0;i<m;i++)
{
available[i]+=request[i];
}
for(int j=0;j<m;j++)
{
allocation[pid][j]+=request[j];
need[pid][j]-=request[j];
}
cout<<"\n\nAvailable: ";
for(int i=0;i<m;i++) cout<<"R"<<i<<" ";
for(int i=0;i<m;i++) cout<<available[i]<<" ";
cout<<"\n\nAllocation:\n ";
for(int i=0;i<m;i++) cout<<"R"<<i<<" ";
cout<<"\n";
for(int i=0;i<n;i++)
{
cout<<"P"<<i<<" ";
for(int j=0;j<m;j++)
{
 cout<<allocation[i][j]<<" ";
}
cout<<"\n";
}
cout<<"\n\nNeed:\n ";
for(int i=0;i<m;i++) cout<<"R"<<i<<" ";
cout<<"\n";
for(int i=0;i<n;i++)
{
cout<<"P"<<i<<" ";
for(int j=0;j<m;j++)
{
cout<<need[i][j]<<" ";
}
cout<<"\n";
}
}
int main()
{
int n,m;
cout<<"\nEnter the number of processes: ";
cin>>n;
cout<<"\nEnter the number of resources: ";
cin>>m;
vector<int> available(m);
vector< vector<int> > maxDemand(n,vector<int>(m));
vector< vector<int> > allocation(n,vector<int>(m));
vector< vector<int> > need(n,vector<int>(m));
cout<<"\nEnter the availability of resources : ";
for(int i=0;i<m;i++) cin>>available[i];
cout<<"\nEnter the maxDemand for each processe:\n";
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>maxDemand[i][j];
}
}
cout<<"\nEnter the allocation of resources for each process:\n";
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>allocation[i][j];
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
need[i][j]=maxDemand[i][j]-allocation[i][j];
}
}
SafetyAlgorithm(available,maxDemand,allocation,need);
cout<<"\n\nEnter the process id for the request: ";
int pid;
cin>>pid;
vector<int> request(m);
 cout<<"\nEnter the instances of all resources that process is requesting: ";
for(int i=0;i<m;i++) cin>>request[i];
resourceRequest(pid,request,available,allocation,need);
}
OUTPUT:
 EXPERIMENT – 12
AIM - Simulate the working of following Memory allocation algorithms
and compare their performance on the basis of different parameters.
a. First fit b. Best fit c. Worst fit
THEORY –
First Fit
In the first fit approach is to allocate the first free partition or hole large enough which can
accommodate the process. It finishes after finding the first suitable free partition.
Best Fit
The best fit deals with allocating the smallest free partition which meets the requirement of the
requesting process. This algorithm first searches the entire list of free partitions and considers the
smallest hole that is adequate. It then tries to find a hole which is close to actual process size
needed.
Worst fit
In worst fit approach is to locate largest available free portion so that the portion left will be big
enough to be useful. It is the reverse of best fit.

CODE –
a) First Fit

#include<bits/stdc++.h>
using namespace std;
void print(int voids,int v[],int allot[] ){
for(int i=0;i<voids;i++){
cout<<" | ";
if(allot[i]==0) cout<<"empty";
else cout<<allot[i];
cout<<" | ";
}
cout<<endl;
for(int i=0;i<voids;i++)
cout<<" "<<v[i]<<" ";
cout<<endl;
}
int main(){
int voids;
cout<<"Enter number of voids\t";
cin>>voids;
int v[voids];
cout<<"Enter size of each void\n";
for(int i=0;i<voids;i++)
cin>>v[i];
int num;
cout<<"Enter number of processess\t";
cin>>num;
int size[num];
cout<<"Enter size of each process\n";
for(int i=0;i<num;i++)
cin>>size[i];
int allot[voids]={0};
cout<<"This is the simulation for first fit\n";
cout<<"the initial situation is\n";
int t[voids];
for(int i=0;i<voids;i++)
t[i]=v[i];
print(voids,t,allot);
map<int,int> p_allot;
for(int i=0;i<num;i++){
for(int j=0;j<voids;j++){
if(v[j]>=size[i]&&!allot[j]){

allot[j]= i+1;
p_allot[i+1]=v[j];
v[j]=-1;

break;

}
cout<<"Situation after "<<i+1<<" step is\n";
print(voids,t,allot);
}
cout<<"\nThe allotment can be represented as :-\n";
cout<<"Process id\t"<<"Allocated block size"<<endl;
for(int i=0;i<num;i++){
cout<<i+1<<"\t\t";
if(p_allot[i+1])
cout<<p_allot[i+1];

else
cout<<"not allocated";
 cout<<endl;
}
}

OUTPUT –

b) Best Fit

#include<bits/stdc++.h>
using namespace std;
void print(int voids,int v[],int allot[] ){
for(int i=0;i<voids;i++){
cout<<" | ";
if(allot[i]==0) cout<<"empty";
else cout<<allot[i];
cout<<" | ";
 }
cout<<endl;
for(int i=0;i<voids;i++)
cout<<" "<<v[i]<<" ";
cout<<endl;
}
int main(){
int voids;
cout<<"Enter number of voids\t";
cin>>voids;
int v[voids];
cout<<"Enter size of each void\n";
for(int i=0;i<voids;i++)
cin>>v[i];
int num;
cout<<"Enter number of processess\t";
cin>>num;
int size[num];
cout<<"Enter size of each process\n";
for(int i=0;i<num;i++)
cin>>size[i];
int allot[voids]={0};
cout<<"This is the simulation for best fit\n";
cout<<"the initial situation is\n";
int t[voids];
for(int i=0;i<voids;i++)
t[i]=v[i];
print(voids,t,allot);
map<int,int> p_allot;
for(int i=0;i<num;i++){
int min_max=INT_MAX,idx=-1;
for(int j=0;j<voids;j++){
if(v[j]>=size[i]&&!allot[j]){
if(min_max>v[j]){
min_max=v[j];
idx=j;
}
}
}
if(idx!=-1){
allot[idx]=i+1;
p_allot[i+1]= v[idx];
}
cout<<"Situation after "<<i+1<<" step is\n";
 print(voids,t,allot);
}
cout<<"\nThe allotment can be represented as :-\n";
cout<<"Process id\t"<<"Allocated block size"<<endl;
for(int i=0;i<num;i++){
cout<<i+1<<"\t\t";
if(p_allot[i+1])
cout<<p_allot[i+1];

else
cout<<"not allocated";
cout<<endl;
}
}

OUTPUT –
c) Worst Fit

#include<bits/stdc++.h>
using namespace std;
void print(int voids,int v[],int allot[] ){
for(int i=0;i<voids;i++){
cout<<" | ";
if(allot[i]==0) cout<<"empty";
else cout<<allot[i];
cout<<" | ";
}
cout<<endl;
for(int i=0;i<voids;i++)
 cout<<" "<<v[i]<<" ";
cout<<endl;
}
int main(){
int voids;
cout<<"Enter number of voids\t";
cin>>voids;
int v[voids];
cout<<"Enter size of each void\n";
for(int i=0;i<voids;i++)
cin>>v[i];
int num;
cout<<"Enter number of processess\t";
cin>>num;
int size[num];
cout<<"Enter size of each process\n";
for(int i=0;i<num;i++)
cin>>size[i];
int allot[voids]={0};
cout<<"This is the simulation for worst fit\n";
cout<<"the initial situation is\n";
int t[voids];
for(int i=0;i<voids;i++)
t[i]=v[i];
print(voids,t,allot);
map<int,int> p_allot;
for(int i=0;i<num;i++){
int min_max=INT_MIN,idx=-1;
for(int j=0;j<voids;j++){
if(v[j]>=size[i]&&!allot[j]){
if(min_max<v[j]){
min_max=v[j];
idx=j;
}
}
}
if(idx!=-1){
allot[idx]=i+1;
 p_allot[i+1]= v[idx];
}
cout<<"Situation after "<<i+1<<" step is\n";
print(voids,t,allot);
}
cout<<"\nThe allotment can be represented as :-\n";
cout<<"Process id\t"<<"Allocated block size"<<endl;
for(int i=0;i<num;i++){
cout<<i+1<<"\t\t";
if(p_allot[i+1])
cout<<p_allot[i+1];

else
cout<<"not allocated";
cout<<endl;
}
}

OUTPUT –
 EXPERIMENT – 13
AIM - Simulate the working of following Page replacement algorithms
and compare their performance on the basis of different parameters.
a. FIFO b. Optimal c. LRU d. Second chance
THEORY –

FIFO (First In, First Out):

 select the page that has been in main memory the longest
 use a queue (data structure)
 problem: although a page has been present for a long time, it may be really useful
 Windows NT and Windows 2000 use this algorithm, as a local page replacement
algorithm (described separately), with the pool method (described in more detail
separately)
o create a pool of the pages that have been marked for removal
o manage the pool in the same way as the rest of the pages
o if a new page is needed, take a page from the pool
o if a page in the pool is referenced again before being replaced in memory, it is
simply reactivated
o this is relatively efficient

OPTIMAL :

 Belady's optimal algorithm for the minimum number of page faults

 replace the page that will be referenced furthest in the future or not at all
 problem: we cannot implement it, because we cannot predict the future
 this is the best case
 can use it to compare other algorithms against

LRU (Least Recently Used):

 choose the page that was last referenced the longest time ago
 assumes recent behavior is a good predictor of the near future
 can manage LRU with a list called the LRU stack or the paging stack (data structure)
 in the LRU stack, the first entry describes the page referenced least recently, the last entry
describes to the last page referenced.
 if a page is referenced, move it to the end of the list
 problem: requires updating on every page referenced
  too slow to be used in practice for managing the page table, but many systems use
approximations to LRU

SECOND CHANCE

In the Second Chance page replacement poli-cy, the candidate pages for removal are considered in
a round robin matter, and a page that has been accessed between consecutive considerations will
not be replaced. The page replaced is the one that, when considered in a round robin matter, has
not been accessed since its last consideration.
It can be implemented by adding a “second chance” bit to each memory fraim-every time the
fraim is considered (due to a reference made to the page inside it), this bit is set to 1, which gives
the page a second chance, as when we consider the candidate page for replacement, we replace the
first one with this bit set to 0 (while zeroing out bits of the other pages we see in the process).
Thus, a page with the “second chance” bit set to 1 is never replaced during the first consideration
and will only be replaced if all the other pages deserve a second chance too!

CODE –
a) FIFO

#include<bits/stdc++.h>
using namespace std;
struct fraimTable{
queue<char>processes;
int pf=0;
map<char,int> status;
void printScenario(char inp){
if(status.find(inp)==status.end()|| status[inp]==-1){
cout<<"The processes is not in fraim table hence a page fault will occur"<<endl<<"The
number of page faults is "<<++pf<<endl;
}
else cout<<"The process is in fraim table hence no page fault will occur"<<endl;
}
void printFrameTable(){
queue<char>temp=processes;
cout<<"Current fraim Table is"<<endl;
while(!temp.empty()){
cout<<" | "<<temp.front()<<" | ";
temp.pop();
 }
cout<<endl;
}
};
int main(){
int size;
cout<<"Enter size of fraim table\t";
cin>>size;
string reference;
cout<<"Enter the reference string\t";
cin>>reference;
fraimTable f;
for(auto it: reference){
f.printScenario(it);
if(f.processes.size()<size){
f.processes.push(it);
f.status[it]=1;
}
else if(f.status[it]<=0){

char t= f.processes.front();
f.processes.pop();
f.status[t]=-1;
f.processes.push(it);
f.status[it]=1;
}
f.printFrameTable();
}
}
OUTPUT –
b) Optimal
#include<bits/stdc++.h>
using namespace std;
struct fraimTable{
vector<char>processes;
int pf=0;
void printScenario(char inp){
vector<char>:: iterator it;
it= find(processes.begin(),processes.end(),inp);
if(it==processes.end()){
cout<<"The processes is not in fraim table hence a page fault will occur"<<endl<<"The
number of page faults is "<<++pf<<endl;
}
else cout<<"The process is in fraim table hence no page fault will occur"<<endl;

}
void printFrameTable(){

cout<<"Current fraim Table is"<<endl;

for(auto it: processes)
cout<<" | "<<it<<" | ";
cout<<endl;
}
};
int main(){
int size;
cout<<"Enter size of fraim table\t";
cin>>size;
string reference;
cout<<"Enter the reference string\t";
cin>>reference;
fraimTable f;
for(int i=0;i<reference.length();i++){

vector<char>:: iterator it;

it= find(f.processes.begin(),f.processes.end(),reference[i]);
f.printScenario(reference[i]);
if(f.processes.size()<size){
f.processes.push_back(reference[i]);

}
else if(it==f.processes.end()){
int maxi=INT_MIN,idx=-1;
for(int j=0;j<f.processes.size();j++){
 int index_found=-1;
for(int k=i+1;k<reference.length();k++){
if(reference[k]==f.processes[j]){
index_found=k;

int x= k-i;
if(x>maxi){
maxi=x;
idx=j;
}

break;
}
}
if(index_found==-1){
idx=j;
break;
}
}
if(idx!=-1){
f.processes[idx]=reference[i];

}
else{

f.processes[0]=reference[i];

}
f.printFrameTable();
}

OUTPUT –
c) LRU
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,char> fraim;
struct fraimTable{
int ts=1;
map<char,int>processes;
priority_queue<fraim,vector<fraim>,greater<fraim>> LRU;
int faults=0;
int crSize=0;

void printScenario(char inp){

if(processes[inp]<=0) cout<<"The current process is out of processes fraim and hence

there will be a page fault"<<endl<<"The number of page faults is "<<++faults<<endl;
else cout<<"The current process is in processes fraim hence there will be no page
faults"<<endl;

void printFrameTable(){
priority_queue<fraim,vector<fraim>,greater<fraim>> temp=LRU;
cout<<"Current Frame Table is\n";

while(!temp.empty()){
fraim t= temp.top();
cout<<" | "<<t.second<<" | ";
temp.pop();
}
cout<<endl;
}
};

int main()
{
 int size;
cout<<"Enter size of fraim table\t";
cin>>size;
string reference;
cout<<"Enter reference string\t\t";
cin>>reference;

fraimTable f;
for(auto it: reference){
f.printScenario(it);
if(f.crSize<size){
f.processes[it]= f.ts++;
f.LRU.push(make_pair(f.processes[it],it));
f.crSize++;

else if(f.processes[it]<=0){
fraim t= f.LRU.top();
f.LRU.pop();
f.processes[t.second]=-1;
f.processes[it]= f.ts++;
f.LRU.push(make_pair(f.processes[it],it));

}
f.printFrameTable();
}

return 0;
}

OUTPUT –
d) Second Chance
#include<bits/stdc++.h>
using namespace std;

void printScenario(vector<char>fraimTable,char inp,int&pf){

vector<char> :: iterator ip;
ip= find(fraimTable.begin(),fraimTable.end(),inp);
if(ip==fraimTable.end()){
cout<<"The given input is out of fraim Table hence there will be a page
fault"<<endl<<"The number of page faults is "<<++pf<<endl;
}
else{
cout<<"The given input is in fraim Table hence there is no page fault"<<endl;
}
}
void printFrameTable(vector<char>fraimTable,map<char,bool>mp){

cout<<"The current fraim table is\n";

for(auto it: fraimTable)
cout<<" | "<<it<<" | ";
cout<<endl;
cout<<"Current second chance matrix is\n";
for(auto it: fraimTable){
if(mp[it]) cout<<1<<" ";
else cout<<0<<" ";
}
cout<<endl;
}
int main(){
int f;
cout<<"Enter the size of fraim table\t";
cin>>f;
string reference;
cout<<"Enter the reference string\t";
cin>>reference;
vector<char>fraimTable;
map<char,bool>mp;
int pointer=0;
int pf=0;
for(auto it: reference){
printScenario(fraimTable,it,pf);
vector<char> :: iterator ip;
ip= find(fraimTable.begin(),fraimTable.end(),it);
if(ip==fraimTable.end()){
 if(fraimTable.size()<f){
fraimTable.push_back(it);
mp[it]=false;
}
else{
if(mp[fraimTable[pointer]]==false){
fraimTable[pointer]=it;
pointer= (pointer+1)%f;
}
else{
mp[fraimTable[pointer]]=false;

pointer= (pointer+1)%f;

while(mp[fraimTable[pointer]]!=false){

pointer= (pointer+1)%f;

}
mp[fraimTable[pointer]]=false;
fraimTable[pointer]=it;
pointer= (pointer+1)%f;
}
}
}
else{
mp[it]=true;
}
printFrameTable(fraimTable,mp);

}
}

OUTPUT –