lOMoARcPSD|12838665

Studocu is not sponsored or endorsed by any college or university

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

NETAJI SUBHAS UNIVERSITY OF

TECHNOLOGY

Practical File

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

LIST OF EXPERIMENTS

1. Process creation and termination for operating system (fork,wait,exit,signal,

etc)

2. Threads

3. Implementing CPU scheduling algorithms: FCFS, SJF, Round robin,preemptive

priority

4. Inter process communication

5. Critical Section Problem

6. Producer-Consumer Problem using bounded and unbounded buffer

7. Reader’s - Writer’s Problem and Dining Philosophers’ problem using

semaphores

8. Implementing Banker’s Algorithm

9. Page Replacement Algorithms: LRU, Optimal, FIFO

10. File operation system calls: open, read, close, append

11. Disk Scheduling Algorithms: CFS, SCAN, CSCAN, LOOK, CLOOK, SSTF.

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

EXPERIMENT 1

AIM: To implement Process creation and termination for operating system (fork, wait,
exit, signal)

THEORY

● Fork system call creates a new process, called child process that runs parallely
with the parent process. The child process will continue execution from
after the instruction where it was forked from.
● Wait system call blocks execution of the calling process until one of its
child processes exits or a signal is received.
○ If there is at least one child process running when the call to wait() is
made, the caller will be blocked until one of its child processes exits.
At that moment, the caller resumes its execution.
○ If there is no child process running when the call to wait() is made,
then this wait() has no effect at all. That is, it is as if no wait() is there.
● Exit system call terminates the process normally. It
○ Flushes unwritten buffered data
○ Closes all open file
○ Removes temporary files
○ Returns an integer exit status to the operating system
● A signal is a software generated interrupt that is sent to a process by the
OS. Each type of signal has different code and symbolic names.

CODE

1. fork()
#include <stdio.h>
#include <sys/types.h>
#include <unistd.h>

int main() {
pid_t pid = fork();
if (pid = 0){

printf("I am child process, pid = %d\n", getpid());

printf("My parent pid is %d\n", getppid());
} else {
printf("I am parent process, pid = %d\n", getpid());
}
return 0;
}

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

2. wait()
#include <stdio.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <unistd.h>

int main()
{
pid_t pid = fork();
if (pid = 0) {
printf("I am child process, pid = %d\n", getpid());
printf("My parent pid is %d\n", getppid());

} else {
wait(NULL);
printf("I am parent process, pid = %d\n", getpid());
printf("Because we used wait, it is guaranteed that "
"the child process has terminated\n");
}
printf("This is common to child and parent\n");
return 0;
}

3. signal()
#include<stdio.h>
#include<signal.h>

void handle_sigint(int sig){

printf("\nSIGINT received\n");
/ can be used for graceful shutdown
exit(0);
}
int main(){
signal(SIGINT, handle_sigint); / triggered by Ctrl+C

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

while(1){
printf("program running\n");
sleep(1);
}
return 0;
}

4. exit()
#include <stdio.h>
#include <stdlib.h>
int main(){
printf("This program uses exit() syscall to terminate the process\n");
exit(0);
}

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

EXPERIMENT 2

AIM: To implement working of threads in an operating system

THEORY

A thread is the smallest unit of processing that can be performed in an OS. In

most modern operating systems, a thread exists within a process - that is, a
single process may contain multiple threads. Threads are not executed parallelly
in uniprocessor systems, but processor scheduling gives the illusion of them
being executed all at once. Each thread has the following

● Program Counter
● Register Set
● Stack Space

Other resources, like the following, are shared between threads

● Code
● Data
● Open files
● OS resources

CODE
#include <iostream>
#include <cstdlib>
#include <pthread.h>
using namespace std;
#define NUM_THREADS 5

void *print_hello(void *thread_id) {

long tid;
tid = (long)thread_id;
cout < "Hello World! Thread ID, " < tid < endl;
pthread_exit(NULL);
}

int main () {
pthread_t threads[NUM_THREADS];
int rc;
int i;

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

cout < "main() : creating thread, " < i < endl;
rc = pthread_create(&threads[i], NULL, print_hello, (void *)i);

if (rc) {
cout < "Error:unable to create thread," < rc < endl;
exit(-1);
}
}
pthread_exit(NULL);

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

EXPERIMENT 3

AIM: To implement CPU scheduling algorithms

FCFS

First come first serve (FCFS) scheduling algorithm simply schedules the jobs
according to their arrival time. The job which comes first in the ready queue will
get the CPU first. The lesser the arrival time of the job, the sooner the job will get
the CPU.

CODE
#include<iostream>
using namespace std;

int main() {
int n,bt[20],wt[20],tat[20],avwt=0,avtat=0,i,j;
cout <"Enter total number of processes(maximum 20):";
cin >n;

cout <"\nEnter Process Burst Time\n";

for(i=0;i<n;i +){
cout <"P[" <i+1 <"]:";
cin >bt[i];
}

wt[0]=0; /waiting time for first process is 0

/calculating waiting time
for(i=1;i<n;i +)
{
wt[i]=0;
for(j=0;j<i;j +)
wt[i]+=bt[j];
}
cout <"\nProcess\t\tBurst Time\tWaiting Time\tTurnaround Time";

/calculating turnaround time

for(i=0;i<n;i +){
tat[i]=bt[i]+wt[i];
avwt+=wt[i];
avtat+=tat[i];
cout <"\nP[" <i+1 <"]" <"\t\t" <bt[i] <"\t\t" <wt[i] <"\t\t" <tat[i];
}
avwt =i;
avtat =i;
cout <"\n\nAverage Waiting Time:" <avwt;
cout <"\nAverage Turnaround Time:" <avtat <"\n";
return 0;
}

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

SHORTEST JOB FIRST (NON PREEMPTIVE)

Shortest Job First (SJF) is an algorithm in which the process having the smallest
execution time is chosen for the next execution. In non-preemptive scheduling, once
the CPU cycle is allocated to a process, the process holds it till it reaches a
waiting state or is terminated. This scheme is also known as Shortest Job Next.

CODE
#include<stdio.h>
struct process { int id,WT,AT,BT,TAT; };
struct process a[10];

void swap(int *b,int *c) {

int tem;
tem=*c;
*c=*b;
*b=tem;
}

int main() {
int n,check_ar=0;
int Cmp_time=0;
float Total_WT=0,Total_TAT=0,Avg_WT,Avg_TAT;
printf("Enter the number of process \n");
scanf("%d",&n);
printf("Enter the Arrival time and Burst time of the process\n");
printf("AT BT\n");
for(int i=0;i<n;i +) {
scanf("%d%d",&a[i].AT,&a[i].BT);
a[i].id=i+1;
/ here we are checking that arrival time
/ of the process are same or different
if(i =0)

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

check_ar=a[i].AT;
if(check_ar =a[i].AT )
check_ar=1;
}

/ if process are arrived at the different time

/ then sort the process on the basis of AT
if(check_ar =0) {
for(int i=0;i<n;i +){
for(int j=0;j<n-i-1;j +){
if(a[j].AT>a[j+1].AT){
swap(&a[j].id,&a[j+1].id);
swap(&a[j].AT,&a[j+1].AT);
swap(&a[j].BT,&a[j+1].BT);
}
}
}
}

/ logic of SJF non preemptive algo

/ if all the process are arrived at different time
if(check_ar =0){
a[0].WT=a[0].AT;
a[0].TAT=a[0].BT-a[0].AT;
Cmp_time=a[0].TAT;
Total_WT=Total_WT+a[0].WT;
Total_TAT=Total_TAT+a[0].TAT;
for(int i=1;i<n;i +){
int min=a[i].BT;
for(int j=i+1;j<n;j +){
if(min>a[j].BT & a[j].AT =Cmp_time){
min=a[j].BT;
swap(&a[i].id,&a[j].id);
swap(&a[i].AT,&a[j].AT);
swap(&a[i].BT,&a[j].BT);
}
}
a[i].WT=Cmp_time-a[i].AT;
Total_WT=Total_WT+a[i].WT;

/ completion time of the process

Cmp_time=Cmp_time+a[i].BT;
/ Turn Around Time of the process
/ compl-Arival
a[i].TAT=Cmp_time-a[i].AT;
Total_TAT=Total_TAT+a[i].TAT;
}
}

/ if all the process are arrived at same

time
else {
for(int i=0;i<n;i +){
int min=a[i].BT;
for(int j=i+1;j<n;j +){
if(min>a[j].BT & a[j].AT =Cmp_time){
min=a[j].BT;

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

swap(&a[i].id,&a[j].id);
swap(&a[i].AT,&a[j].AT);
swap(&a[i].BT,&a[j].BT);
}
}
a[i].WT=Cmp_time-a[i].AT;
/ completion time of the process
Cmp_time=Cmp_time+a[i].BT;

/ Turn Around Time of the process

/ compl-Arrival
a[i].TAT=Cmp_time-a[i].AT;
Total_WT=Total_WT+a[i].WT;
Total_TAT=Total_TAT+a[i].TAT;

}
}

Avg_WT=Total_WT/n;
Avg_TAT=Total_TAT/n;

/ Printing of the results

printf("The process are\n");
printf("ID \tWT \tTAT\n");

for(int i=0;i<n;i +)
printf("%d\t%d\t%d\n",a[i].id,a[i].WT,a[i].TAT);
printf("Avg waiting time is: %f\n",Avg_WT);
printf("Avg turn around time is: %f\n",Avg_TAT);
return 0;
}

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

ROUND ROBIN

Each process is provided a fixed time to execute, it is called a quantum. Once a

process is executed for a given time period, it is preempted and another process
executes for a given time period. Context switching is used to save states of
preempted processes.

CODE
#include <stdio.h>

void main()

{
int i, NOP, sum = 0, count = 0, y, quant, wt = 0, tat = 0, at[10], bt[10],
temp[10];
float avg_wt, avg_tat;
printf(" Total number of process in the system: ");
scanf("%d", &NOP);
y = NOP;
for (i = 0; i < NOP; i +){
printf("\n Enter Arrival and Burst time of Process[%d]\n", i + 1);
printf(" Arrival time is: \t"); / Accept arrival time
scanf("%d", &at[i]);
printf(" \nBurst time is: \t"); / Accept the Burst time
scanf("%d", &bt[i]);
temp[i] = bt[i]; / store the burst time in temp array
}

printf("Enter the Time Quantum for the process: \t");

scanf("%d", &quant);

/ Display the process No, burst time, Turn Around Time

/ and the waiting time
printf("\n Process No \t\t Burst Time \t\t TAT \t\t Waiting Time "); for
(sum = 0, i = 0; y = 0;) {
if (temp[i] = quant & temp[i] > 0) / define the conditions
{
sum = sum + temp[i];
temp[i] = 0;
count = 1;
}

else if (temp[i] > 0){

temp[i] = temp[i] - quant;
sum = sum + quant;
}

if (temp[i] = 0 & count = 1){

y -; / decrement the process no.
printf("\nProcess No[%d] \t\t %d\t\t\t\t %d\t\t\t %d", i + 1,
bt[i], sum - at[i], sum - at[i] - bt[i]);
wt = wt + sum - at[i] - bt[i];
tat = tat + sum - at[i];

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

count = 0;
}

if (i = NOP - 1)
i = 0;
else if (at[i + 1] = sum)
i +;
else
i = 0;
}

/ represents the average waiting time and Turn Around time

avg_wt = wt * 1.0 / NOP;
avg_tat = tat * 1.0 / NOP;
printf("\n Average Turn Around Time: \t%f", avg_wt);
printf("\n Average Waiting Time: \t%f\n", avg_tat);
}

LONGEST REMAINING TIME FIRST

This is a preemptive version of Longest Job First algorithm. Here, we continuously

check for the process with the maximum remaining time and execute it.

CODE

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

#include <iostream>
using namespace std;

int main() {
int a[10], b[10], x[10];
int waiting[10], turnaround[10], completion[10];
int i, j, largest, count = 0, time, n;
double avg = 0, tt = 0, end;
cout < "\nEnter the number of Processes: "; / input
cin > n;
for (i = 0; i < n; i +) {
cout < "\nEnter arrival time of process " < i + 1 < ": ";
cin > a[i];
}
for (i = 0; i < n; i +) {
cout < "\nEnter burst time of process " < i + 1 < ": ";
cin > b[i];
}

for (i = 0; i < n; i +)
x[i] = b[i];

b[9] = 0;
for (time = 0; count = n; time +){
largest = 9;
for (i = 0; i < n; i +) {
if (a[i] = time & b[i] > b[largest] & b[i] > 0)
largest = i;
}
b[largest] -;
if (b[largest] = 0){
count +;
end = time + 1;
completion[largest] = end;
waiting[largest] = end - a[largest] - x[largest];
turnaround[largest] = end - a[largest];
}
}
cout < "Process" < "\t" < "burst-time" < "\t" < "arrival-time"
< "\t" < "waiting-time" < "\t" < "turnaround-time" < "\t"
< "completion-time" < 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] < endl;
avg = avg + waiting[i];
tt = tt + turnaround[i];
}

cout < "\nAverage waiting time =" < avg / n;

cout < "\nAverage Turnaround time =" < tt / n < endl;
return 0;
}

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

EXPERIMENT 4

AIM: To implement inter process communication

THEORY

Inter process communication is the mechanism an operating system provides to

allow processes to manage shared resources. Typically, applications can use IPC,
categorized as client and server, where client requests data and server responds
to client requests.

IPC is crucial for microkernels as the reduced core functionality in kernel needs to be
compensated by the different modules interacting with each other via IPC.

CODE

writer.cpp
#include <iostream>
#include <sys/ipc.h>
#include <sys/shm.h>
#include <stdio.h>

using namespace std;

void main() {
/ ftok function is used to generate unique key
key_t my_key = ftok("shmfile",65);

/ shmat to join to shared memory

int shmid = shmget(my_key,1024,0666|IPC_CREAT);
char *str = (char*) shmat(shmid,(void*)0,0);

cout <"Write Data : ";

fgets(str, 50, stdin);
printf("Data written in memory: %s\n",str);

/detach from shared memory

shmdt(str);
}

reader.cpp
#include <iostream>
#include <sys/ipc.h>
#include <sys/shm.h>
#include <stdio.h>

using namespace std;

int main() {

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

/ ftok function is used to generate unique key

key_t my_key = ftok("shmfile",65);

/ shmget returns an ide in shmid

int shmid = shmget(my_key,1024,0666|IPC_CREAT);

/ shmat to join to shared memory

char *str = (char*) shmat(shmid,(void*)0,0);
printf("Data read from memory: %s\n",str);
shmdt(str);

shmctl(shmid,IPC_RMID,NULL); / destroy the shared memory

Compile commands
g + writer.cpp -o w
g + reader.cpp -o r

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

EXPERIMENT 5

AIM: To implement Critical Section Problem

THEORY

The critical section refers to the segment of code where processes access shared
resources, such as common variables and files, and perform write operations on
them.

The critical section problem is used to design a protocol followed by a group of

processes, so that when one process has entered its critical section, no other process
is allowed to execute in its critical section.

Since processes execute concurrently, any process can be interrupted mid-execution.

In the case of shared resources, partial execution of processes can lead to data
inconsistencies. When two processes access and manipulate the shared resource
concurrently, and the resulting execution outcome depends on the order in which
processes access the resource; this is called a race condition.

Solutions to Critical Section Problem

● Mutual exclusion: When one process is executing in its critical section, no

other process is allowed to execute in its critical section.
● Progress: When no process is executing in its critical section, and there exists a
process that wishes to enter its critical section, it should not have to wait
indefinitely to enter it.
● Bounded waiting: There must be a bound on the number of times a process
is allowed to execute in its critical section, after another process has requested
to enter its critical section and before that request is accepted.

CODE

#include <stdio.h>
#include <pthread.h>
#include <stdlib.h>
#define MAX 1e9

int turn, ans = 0, flag[2];

void lock_init() {
flag[0] = flag[1] = 0;
turn = 0;
}

void lock(int self) {

flag[self] = 1;
turn = 1 - self;
while (flag[1 - self] = 1 & turn = 1 - self);
}
void unlock(int self) { flag[self] = 0; }
void *func(void *s) {

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

int i = 0;
int *limitptr = (int *)s;
int self = *limitptr;
printf("Thread %d in queue for critical section\n", self);
lock(self);
printf("Thread %d entered critical section\n", self);
for (i = 0; i < MAX; i +)
ans +;
printf("Thread %d completed executing\n", self);
printf("Thread %d is exiting critical section\n", self);
unlock(self);
}
int main() {
pthread_t p1, p2;
int a = 0, b = 1;
lock_init();
pthread_create(&p1, NULL, func, &a);
pthread_create(&p2, NULL, func, &b);
pthread_join(p1, NULL);
pthread_join(p2, NULL);
printf("Exiting main()\n");
return 0;
}

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

EXPERIMENT 6

AIM: To give solution of Producer and Consumer problem using bounded and
unbounded buffer respectively

THEORY

The Producer - Consumer problem is a multi process synchronization problem, where

we are trying to achieve safe synchronization between more than one process.

There is one Producer which is producing some items. And there is one Consumer
which is consuming the produced items. Producer should produce data only when
the buffer is not full. Consumer can consume data only if the memory buffer is
not empty. Also, both Producer and Consumer must not access memory at the
same time.

CODE
#include<stdio.h>
#include<stdlib.h>

int mutex=1,full=0,empty=3,x=0;

int main()
{
int n;
void producer();
void consumer();
int wait(int);
int signal(int);
printf("\n1.Producer\n2.Consumer\n3.Exit");
while(1) {
printf("\nEnter your choice:");
scanf("%d",&n);
switch(n){
case 1: if((mutex =1) &(empty =0))
producer();
else
printf("Buffer is full !");
break;
case 2: if((mutex =1) &(full =0))
consumer();
else
printf("Buffer is empty !");
break;
case 3:
exit(0);
break;
}

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

}
return 0;
}

int wait(int s){

return ( -s);
}

int signal(int s) {
return( +s);
}

void producer() {
mutex=wait(mutex);
full=signal(full);
empty=wait(empty);
x +;
printf("\nProducer produces the item %d",x);
mutex=signal(mutex);
}

void consumer(){
mutex=wait(mutex);
full=wait(full);
empty=signal(empty);
printf("\nConsumer consumes item %d",x);
x -;
mutex=signal(mutex);
}

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

EXPERIMENT 7

AIM: To implement Dining Philosophers problem and Reader Writer’s problem

THEORY

The Dining Philosopher Problem states that K philosophers are seated around a
circular table with one chopstick between each pair of philosophers. There is one
chopstick between each philosopher. A philosopher may eat if he can pick up the two
chopsticks adjacent to him. One chopstick may be picked up by any one of its
adjacent followers but not both.

CODE
#include <iostream>
#include <thread>
#include <chrono>
#include <atomic>

int myrand(int min, int max) {

return rand()%(max-min)+min;
}
void lock(std :atomic<int>& m) {
while (m)
; / busy waiting
m=1;
}

void unlock(std :atomic<int>& m) { m=0;}

void phil(int ph, std :atomic<int>&

ma, std :atomic<int>& mb) {
while(true) {
int duration=myrand(1000, 2000);
std :cout <ph <" thinks " <duration <"ms\n";
std :this_thread :sleep_for(std :chrono :milliseconds(duration));
lock(ma);
std :cout <"\t\t" <ph <" got ma\n";
std :this_thread :sleep_for(std :chrono :milliseconds(1000));
lock(mb);
std :cout <"\t\t" <ph <" got mb\n";
duration=myrand(1000, 2000);
std :cout <"\t\t\t\t" <ph <" eats " <duration <"ms\n";
std :this_thread :sleep_for(std :chrono :milliseconds(duration));
unlock(mb);
unlock(ma);
}
}

int main() {
std :cout <"dp_5\n";
srand(time(nullptr));
std :atomic<int> m1{0}, m2{0}, m3{0}, m4{0};

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

std :thread t1([&] {phil(1, m1, m2);});

std :thread t2([&] {phil(2, m2, m3);});
std :thread t3([&] {phil(3, m3, m4);});
std :thread t4([&] {phil(4, m1, m4);});

t1.join();
t2.join();
t3.join();
t4.join();
}

READER WRITER’S PROBLEM

Consider a situation where we have a file shared between many people.

• If one of the people tries editing the file, no other person should be reading or
writing at the same time, otherwise changes will not be visible to him/her.

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

• However if some person is reading the file, then others may read it at the same
time.

In OS we call this situation as the readers-writers problem

CODE
#include<semaphore.h>
#include<stdio.h>
#include<stdlib.h>
#include<unistd.h>
#include<pthread.h>

sem_t x,y;
pthread_t tid;
pthread_t writerthreads[100],readerthreads[100];

int readercount = 0;
void *reader(void* param){
sem_wait(&x);
Readercount +;
if(readercount =1)
sem_wait(&y);
sem_post(&x);
printf("%d reader is inside\n",readercount);
usleep(3);
sem_wait(&x);
readercount -;
if(readercount =0){
sem_post(&y);
}
sem_post(&x);
printf("%d Reader is leaving\n",readercount+1);
return NULL;
}

void *writer(void* param){

printf("Writer is trying to enter\n");
sem_wait(&y);
printf("Writer has entered\n");
sem_post(&y);
printf("Writer is leaving\n");
return NULL;
}

int main(){
int n2,i;
printf("Enter the number of readers:");
scanf("%d",&n2);
printf("\n");
int n1[n2];
sem_init(&x,0,1);
sem_init(&y,0,1);

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

for(i=0;i<n2;i +) {
pthread_create(&writerthreads[i],NULL,reader,NULL);
pthread_create(&readerthreads[i],NULL,writer,NULL);
}

for(i=0;i<n2;i +) {
pthread_join(writerthreads[i],NULL);
pthread_join(readerthreads[i],NULL);
}
}

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

EXPERIMENT 8

AIM: To implement Banker’s Algorithm

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 <iostream>
using namespace std;

int main()
{
/ P0, P1, P2, P3, P4 are the Process names here

int n, m, i, j, k;
n = 5; / Number of processes
m = 3; / Number of resources
int alloc[5][3] = { { 0, 1, 0 }, / P0 / Allocation Matrix
{ 2, 0, 0 }, / P1
{ 3, 0, 2 }, / P2
{ 2, 1, 1 }, / P3
{ 0, 0, 2 } }; / P4

int max[5][3] = { { 7, 5, 3 }, / P0 / MAX Matrix

{ 3, 2, 2 }, / P1
{ 9, 0, 2 }, / P2
{ 2, 2, 2 }, / P3
{ 4, 3, 3 } }; / P4

int avail[3] = { 3, 3, 2 }; / Available Resources

int f[n], ans[n], ind = 0;

for (k = 0; k < n; k +) {
f[k] = 0;
}
int need[n][m];
for (i = 0; i < n; i +) {
for (j = 0; j < m; j +)
need[i][j] = max[i][j] - alloc[i][j];
}
int y = 0;
for (k = 0; k < 5; k +) {
for (i = 0; i < n; i +) {
if (f[i] = 0) {

int flag = 0;
for (j = 0; j < m; j +) {
if (need[i][j] > avail[j]){

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

flag = 1;
break;
}
}

if (flag = 0) {
ans[ind +] = i;
for (y = 0; y < m; y +)
avail[y] += alloc[i][y];
f[i] = 1;
}
}
}
}

int flag = 1;

/ To check if sequence is safe or not

for(int i = 0;i<n;i +)
{
if(f[i] =0)
{
flag = 0;
cout < "The given sequence is not safe";
break;
}
}

if(flag =1)
{
cout < "Following is the SAFE Sequence" < endl;
for (i = 0; i < n - 1; i +)
cout < " P" < ans[i] < " >";
cout < " P" < ans[n - 1] <endl;
}

return (0);
}

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

EXPERIMENT 9

AIM: To implement various page replacement algorithms

THEORY

FIFO Page Replacement Algorithm

FIFO which is also called First In First Out is one of the types of Replacement
Algorithms. This algorithm is used in a situation where an Operating system replaces
an existing page with the help of memory by bringing a new page from the secondary
memory.

CODE
#include <stdio.h>
int main()
{
int referenceString[10], pageFaults = 0, m, n, s, pages, frames;
printf("\nEnter the number of Pages:\t");
scanf("%d", &pages);
printf("\nEnter reference string values:\n");
for( m = 0; m < pages; m +){
printf("Value No. [%d]:\t", m + 1);
scanf("%d", &referenceString[m]);
}
printf("\n What are the total number of frames:\t");
{
scanf("%d", &frames);
}
int temp[frames];
for(m = 0; m < frames; m +)
{
temp[m] = -1;
}
for(m = 0; m < pages; m +)
{
s = 0;
for(n = 0; n < frames; n +)
{
if(referenceString[m] = temp[n])
{
s +;
pageFaults -;
}
}
pageFaults +;
if((pageFaults = frames) & (s = 0))
{
temp[m] = referenceString[m];
}
else if(s = 0)
{
temp[(pageFaults - 1) % frames] = referenceString[m];

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

}
printf("\n");
for(n = 0; n < frames; n +)
{
printf("%d\t", temp[n]);
}
}
printf("\nTotal Page Faults:\t%d\n", pageFaults);
return 0;
}

LRU Page Replacement Algorithm

Least Recently Used (LRU) page replacement algorithm works on the concept that the
pages that are heavily used in previous instructions are likely to be used heavily
in next instructions. And the page that are used very less are likely to be used
less in future. Whenever a page fault occurs, the page that is least recently used is
removed from the memory frames. Page fault occurs when a referenced page is
not found in the memory frames.

CODE
#include<stdio.h>

int findLRU(int time[], int n) {

int i, minimum = time[0], pos = 0;
for (i = 1; i < n; +i) {

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

if (time[i] < minimum) {

minimum = time[i];
pos = i;
}
}
return pos;
}
int main() {
int no_of_frames, no_of_pages, frames[10], pages[30], counter = 0, time[10],
flag1, flag2, i, j,
pos, faults = 0;
printf("Enter number of frames: ");
scanf("%d", & no_of_frames);
printf("Enter number of pages: ");
scanf("%d", & no_of_pages);
printf("Enter reference string: ");
for (i = 0; i < no_of_pages; +i) {
scanf("%d", & pages[i]);
}
for (i = 0; i < no_of_frames; +i) {
frames[i] = -1;
}
for (i = 0; i < no_of_pages; +i) {
flag1 = flag2 = 0;
for (j = 0; j < no_of_frames; +j) {
if (frames[j] = pages[i]) {
counter +;
time[j] = counter;
flag1 = flag2 = 1;
break;
}
}
if (flag1 = 0) {
for (j = 0; j < no_of_frames; +j) {
if (frames[j] = -1) {
counter +;
faults +;
frames[j] = pages[i];
time[j] = counter;
flag2 = 1;
break;
}
}
}
if (flag2 = 0) {
pos = findLRU(time, no_of_frames);
counter +;
faults +;
frames[pos] = pages[i];
time[pos] = counter;
}
printf("\n");
for (j = 0; j < no_of_frames; +j) {
printf("%d\t", frames[j]);
}

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

}
printf("\n\nTotal Page Faults = %d\n", faults);
return 0;
}

Optimal Page Replacement Algorithm

Optimal page replacement algorithm says that if page fault occurs then that page
should be removed that will not be used for maximum time in future.

CODE
#include<stdio.h>

int main() {
int no_of_frames, no_of_pages, frames[10], pages[30], temp[10], flag1, flag2,
flag3, i, j, k, pos,
max, faults = 0;
printf("Enter number of frames: ");
scanf("%d", & no_of_frames);
printf("Enter number of pages: ");
scanf("%d", & no_of_pages);
printf("Enter page reference string: ");
for (i = 0; i < no_of_pages; +i) {
scanf("%d", & pages[i]);
}
for (i = 0; i < no_of_frames; +i) {
frames[i] = -1;
}
for (i = 0; i < no_of_pages; +i) {
flag1 = flag2 = 0;
for (j = 0; j < no_of_frames; +j) {
if (frames[j] = pages[i]) {
flag1 = flag2 = 1;
break;
}
}
if (flag1 = 0) {
for (j = 0; j < no_of_frames; +j) {
if (frames[j] = -1) {
faults +;

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

frames[j] = pages[i];
flag2 = 1;
break;
}
}
}
if (flag2 = 0) {
flag3 = 0;
for (j = 0; j < no_of_frames; +j) {
temp[j] = -1;
for (k = i + 1; k < no_of_pages; +k) {
if (frames[j] = pages[k]) {
temp[j] = k;
break;
}
}
}
for (j = 0; j < no_of_frames; +j) {
if (temp[j] = -1) {
pos = j;
flag3 = 1;
break;
}
}
if (flag3 = 0) {
max = temp[0];
pos = 0;
for (j = 1; j < no_of_frames; +j) {
if (temp[j] > max) {
max = temp[j];
pos = j;
}
}
}
frames[pos] = pages[i];
faults +;
}
printf("\n");
for (j = 0; j < no_of_frames; +j) {
printf("%d\t", frames[j]);
}
}
printf("\n\nTotal Page Faults = %d\n", faults);
return 0;
}

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

EXPERIMENT 10

AIM: To implement file system operation calls

CODE

Open
#include<stdio.h>
#include<fcntl.h>
#include<errno.h>
extern int errno;
int main()
{
/ if file does not have in directory
/ then file foo.txt is created.
int fd = open("foo.txt", O_RDONLY | O_CREAT);
printf("fd = %d\n", fd);
if (fd =-1)
{
/ print which type of error have in a code
printf("Error Number % d\n", errno);
/ print program detail "Success or failure"
perror("Program");
}}

System Calls
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <sys/stat.h>
#include <fcntl.h>

typedef struct Student {

int roll;
char name[100];
float percentage;
}
Student;
char * file_path;
void write_student(Student student) {
int fd = open(file_path, O_WRONLY | O_APPEND);
if (fd < 0) {
printf("\nError writing file");
exit(0);
} else {
write(fd, & student, sizeof(student));
printf("\n Writen successfully!");
}

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

close(fd);
}
void read_student() {
Student student;
int fd = open(file_path, O_RDONLY);
if (fd < 0) {
printf("\nError reading file");
exit(0);
} else {
while (read(fd, & student, sizeof(student)))
printf("Name: %s\nRoll Number: %d\nPercentage: %f\n", student.name,
student.roll,
student.percentage);
}
close(fd);
}
void delete_student(int rno) {
char * tmp = "temp";
Student student;
int fd1 = open(file_path, O_RDONLY);
int fd2 = open(tmp, O_CREAT | O_WRONLY);
if (fd1 < 0) {
printf("\nError reading file");
exit(0);
} else {
while (read(fd1, & student, sizeof(student))) {
if (student.roll = rno) {} else {
write(fd2, & student, sizeof(student));
}
}
}
remove(file_path);
rename(tmp, file_path);
close(fd1);
close(fd2);
}
void search_student(int rno) {
Student student;
int fd1 = open(file_path, O_RDONLY);
int flag = 0;
if (fd1 < 0) {
printf("\nError reading file");
exit(0);
} else {
while (read(fd1, & student, sizeof(student))) {
if (student.roll = rno) {
printf("Name: %s\nRoll Number: %d\nPercentage: %f\n", student.name,
student.roll,
student.percentage);
flag = 1;
}
}
}
if (flag = 0)
printf("\nRecord not Found!");

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

close(fd1);
}
int main(int argc, char
const * argv[]) {
Student student;
int ch;
int fd, r;
char dname[20];
while (1) {
printf("\n1. Create database \n2. Insert Record \n3. Read Record \n4.
Delete Record \n5. Search Record \n6. Exit \n >");
scanf("%d", & ch);
switch (ch) {
case 1: {
printf("Enter database name: ");
scanf("%s", dname);
file_path = dname;
int fd = open(file_path, O_CREAT);
if (fd < 0) {
printf("\nError creating file");
exit(0);
} else {
printf("\nFile created successfully!\n");
}
close(fd);
}
break;
case 2: {
printf("\nEnter the Roll Number, Name and Percentage\n"); scanf("%d
%s%f", & student.roll, student.name, & student.percentage);
write_student(student);
}
break;
case 3: {
read_student();
}
break;
case 4: {
printf("\nEnter roll no:");
scanf("%d", & r);
delete_student(r);
}
break;
case 5: {
printf("\nEnter roll no:");
scanf("%d", & r);
search_student(r);
}
break;
case 6:
exit(0);
default:
printf("\nInvalid Choice!");
}
}

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

return 0;
}

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

EXPERIMENT 11
AIM: To implement the various disk scheduling algorithms

THEORY

Shortest Seek Time First (SSTF)

Given an array of disk track numbers and initial head position, our task is to find
the total number of seek operations done to access all the requested tracks if
Shortest Seek Time First (SSTF) is a disk scheduling algorithm is used. Basic idea
is the tracks which are closer to current disk head position should be serviced
first in order to minimize the seek operations

CODE

#include <bits/stdc +.h>

using namespace std;
/ Calculates difference of each
/ track number with the head position
void calculatedifference(int request[], int head,
int diff[][2], int n)
{
for(int i = 0; i < n; i +){ diff[i]
[0] = abs(head - request[i]);
}
}
/ Find unaccessed track which is
/ at minimum distance from head
int findMIN(int diff[][2], int n){
int index = -1;
int minimum = 1e9;
for(int i = 0; i < n; i +){
if (!diff[i][1] & minimum > diff[i][0]){
minimum = diff[i][0];
index = i;
}
}
return index;
}
void shortestSeekTimeFirst(int request[],
int head, int n)
{
if (n = 0)
{
return;
}
/ Create array of objects of class node
int diff[n][2] = { { 0, 0 } };
/ Count total number of seek operation
int seekcount = 0;
/ Stores sequence in which disk access is done
int seeksequence[n + 1] = {0};

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

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

seeksequence[i] = head;
calculatedifference(request, head, diff, n);
int index = findMIN(diff, n);
diff[index][1] = 1;
/ Increase the total count
seekcount += diff[index][0];
/ Accessed track is now new head
head = request[index];
}
seeksequence[n] = head;
cout < "Total number of seek operations = "
< seekcount < endl;
cout < "Seek sequence is : " < "\n";
/ Print the sequence
for(int i = 0; i = n; i +)
{
cout < seeksequence[i] < "\n";
}
}
/ Driver code
int main()
{
int n = 8;
int proc[n] = { 176, 79, 34, 60, 92, 11, 41, 114 };
shortestSeekTimeFirst(proc, 50, n);
return 0; }

SCAN (Elevator) algorithm

In SCAN disk scheduling algorithm, head starts from one end of the disk and
moves towards the other end, servicing requests in between one by one and reach the
other end. Then the direction of the head is reversed and the process continues as
head continuously scan back and forth to access the disk. So, this algorithm
works as an elevator and hence also known as the elevator algorithm. As a result, the
requests at the midrange are serviced more and those arriving behind the disk
arm will have to wait.

CODE

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

#include <bits/stdc +.h>

using namespace std;
int sz = 8;
int disk_size = 200;
void SCAN(int arr[], int head, string direction)
{
int seek_count = 0;
int distance, cur_track;
vector<int> left, right;
vector<int> seek_sequence;
/ appending end values
/ which has to be visited
/ before reversing the direction
if (direction = "left")
left.push_back(0);
else if (direction = "right")
right.push_back(disk_size - 1);
for (int i = 0; i < sz; i +) {
if (arr[i] < head)
left.push_back(arr[i]);
if (arr[i] > head)
right.push_back(arr[i]);
}
/ sorting left and right vectors
std :sort(left.begin(), left.end());
std :sort(right.begin(), right.end());
/ run the while loop two times.
/ one by one scanning right
/ and left of the head
int run = 2;
while (run -) {
if (direction = "left") {
for (int i = left.size() - 1; i = 0; i -) {
cur_track = left[i];
/ appending current track to seek sequence
seek_sequence.push_back(cur_track);
/ calculate absolute distance
distance = abs(cur_track - head);
/ increase the total count
seek_count += distance;
/ accessed track is now the new head
head = cur_track;
}
direction = "right";
}
else if (direction = "right") {
for (int i = 0; i < right.size(); i +) {
cur_track = right[i];
/ appending current track to seek sequence
seek_sequence.push_back(cur_track);
/ calculate absolute distance
distance = abs(cur_track - head);
/ increase the total count

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

seek_count += distance;
/ accessed track is now new head
head = cur_track;
}
direction = "left";
}
}
cout < "Total number of seek operations = "
< seek_count < endl;
cout < "Seek Sequence is" < endl;
for (int i = 0; i < seek_sequence.size(); i +) {
cout < seek_sequence[i] < endl;
}
}
/ Driver code
int main()
{
/ request array
int arr[sz] = { 176, 79, 34, 60,
92, 11, 41, 114 };
int head = 50;
string direction = "left";
SCAN(arr, head, direction);
return 0; }

C-SCAN (Circular Elevator) Disk Scheduling Algorithm

The circular SCAN (C-SCAN) scheduling algorithm is a modified version of the
SCAN disk scheduling algorithm that deals with the inefficiency of the SCAN
algorithm by servicing the requests more uniformly. Like SCAN (Elevator Algorithm)
C-SCAN moves the head from one end servicing all the requests to the other end.
However, as soon as the head reaches the other end, it immediately returns to the
beginning of the disk without servicing any requests on the return trip (see chart
below) and starts servicing again once reaches the beginning. This is also
known as the “Circular

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

Elevator Algorithm” as it essentially treats the cylinders as a circular list that wraps
around from the final cylinder to the first one.

CODE
#include <bits/stdc +.h>

using namespace std;

int sz = 8;
int disk_size = 200;
void CSCAN(int arr[], int head) {
int seek_count = 0;
int distance, cur_track;
vector < int > left, right;
vector < int > seek_sequence;
/ appending end values
/ which has to be visited
/ before reversing the direction
left.push_back(0);
right.push_back(disk_size - 1);
/ tracks on the left of the
/ head will be serviced when
/ once the head comes back
/ to the beginning (left end).
for (int i = 0; i < sz; i +) {
if (arr[i] < head)
left.push_back(arr[i]);
if (arr[i] > head)
right.push_back(arr[i]);
}
/ sorting left and right vectors
std :sort(left.begin(), left.end());
std :sort(right.begin(), right.end());
/ first service the requests
/ on the right side of the
/ head.
for (int i = 0; i < right.size(); i +) {
cur_track = right[i];
/ appending current track to seek sequence
seek_sequence.push_back(cur_track);
/ calculate absolute distance
distance = abs(cur_track - head);
/ increase the total count
seek_count += distance;
/ accessed track is now new head
head = cur_track;
}
/ once reached the right end
/ jump to the beginning.
head = 0;
/ adding seek count for head returning from 199 to 0
seek_count += (disk_size - 1);
/ Now service the requests again
/ which are left.
for (int i = 0; i < left.size(); i +) {

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

cur_track = left[i];
/ appending current track to seek sequence
seek_sequence.push_back(cur_track);
/ calculate absolute distance
distance = abs(cur_track - head);
/ increase the total count
seek_count += distance;
/ accessed track is now the new head
head = cur_track;
}
cout < "Total number of seek operations = " <
seek_count < endl;
cout < "Seek Sequence is" < endl;
for (int i = 0; i < seek_sequence.size(); i +) {
cout < seek_sequence[i] < endl;
}
}
/ Driver code
int main() { / request array
int arr[sz] = {
176,
79,
34,
60,
92,
11,
41,
114
};
int head = 50;
cout < "Initial position of head: " < head < endl;
CSCAN(arr, head);
return 0;
}

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

LOOK Disk Scheduling Algorithm

LOOK is the advanced version of SCAN algorithm which gives slightly better seek time
than any other algorithm in the hierarchy (FCFS->SRTF->SCAN->C-SCAN->LOOK). The
LOOK algorithm services request similarly as SCAN algorithm meanwhile it also
“looks” ahead as if there are more tracks that are needed to be serviced in the
same direction. If there are no pending requests in the moving direction the head
reverses the direction and start servicing requests in the opposite direction.
The main reason behind the better performance of LOOK algorithm in comparison to
SCAN is because in this algorithm the head is not allowed to move till the end of
the disk.

CODE
#include <bits/stdc +.h>

using namespace std;

int sz = 8;
int disk_size = 200;
void LOOK(int arr[], int head, string direction) {
int seek_count = 0;
int distance, cur_track;
vector < int > left, right;
vector < int > seek_sequence;
/ direction from the head.
for (int i = 0; i < sz; i +) {
if (arr[i] < head)
left.push_back(arr[i]);
if (arr[i] > head)
right.push_back(arr[i]);
}
std :sort(left.begin(), left.end());

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

std :sort(right.begin(), right.end());

int run = 2;
while (run -) {
if (direction = "left") {
for (int i = left.size() - 1; i = 0; i -) {
cur_track = left[i];
seek_sequence.push_back(cur_track);
distance = abs(cur_track - head);
seek_count += distance;
head = cur_track;
}
direction = "right";
} else if (direction = "right") {
for (int i = 0; i < right.size(); i +) {
cur_track = right[i];
seek_sequence.push_back(cur_track);
distance = abs(cur_track - head);
seek_count += distance;
head = cur_track;
}
/ reversing the direction
direction = "left";
}
}
cout < "Total number of seek operations = " <
seek_count < endl;
cout < "Seek Sequence is" < endl;
for (int i = 0; i < seek_sequence.size(); i +) {
cout < seek_sequence[i] < endl;
}
}
/ Driver code
int main() {
/ request array
int arr[sz] = {
176,
79,
34,
60,
92,
11,
41,
114
};
int head = 50;
string direction = "right";
cout < "Initial position of head: " <
head < endl;
LOOK(arr, head, direction);
return 0;
}

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

C-LOOK (Circular LOOK) Disk Scheduling Algorithm

C-LOOK is an enhanced version of both SCAN as well as LOOK disk scheduling
algorithms. This algorithm also uses the idea of wrapping the tracks as a circular
cylinder as C-SCAN algorithm but the seek time is better than C-SCAN algorithm. We
know that C-SCAN is used to avoid starvation and services all the requests more
uniformly, the same goes for C-LOOK.
In this algorithm, the head services requests only in one direction(either left or right)
until all the requests in this direction are not serviced and then jumps back to the
farthest request on the other direction and service the remaining requests which
gives a better uniform servicing as well as avoids wasting seek time for going till
the end of the disk.

CODE

#include <bits/stdc +.h>

using namespace std;

int sz = 8;
int disk_size = 200;
void CLOOK(int arr[], int head) {
int seek_count = 0;
int distance, cur_track;
vector < int > left, right;
vector < int > seek_sequence;
for (int i = 0; i < sz; i +) {
if (arr[i] < head)
left.push_back(arr[i]);
if (arr[i] > head)
right.push_back(arr[i]);
}
std :sort(left.begin(), left.end());
std :sort(right.begin(), right.end());
for (int i = 0; i < right.size(); i +) {

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

cur_track = right[i];
seek_sequence.push_back(cur_track);
distance = abs(cur_track - head);
seek_count += distance;
head = cur_track;
}
seek_count += abs(head - left[0]);
head = left[0];
for (int i = 0; i < left.size(); i +) {
cur_track = left[i];
seek_sequence.push_back(cur_track);
distance = abs(cur_track - head);
/ Increase the total count
seek_count += distance;
/ Accessed track is now the new head
head = cur_track;
}
cout < "Total number of seek operations = " <
seek_count < endl;
cout < "Seek Sequence is" < endl;
for (int i = 0; i < seek_sequence.size(); i +) {
cout < seek_sequence[i] < endl;
}
}
int main() {
/ Request array
int arr[sz] = {
176,
79,
34,
60,
92,
11,
41,
114
};
int head = 50;
cout < "Initial position of head: " < head < endl;
CLOOK(arr, head);
return 0;
}

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

First Come First Serve (FCFS)

FCFS is the simplest disk scheduling algorithm. As the name suggests, this algorithm
entertains requests in the order they arrive in the disk queue. The algorithm looks
very fair and there is no starvation (all requests are serviced sequentially) but
generally, it does not provide the fastest service.

CODE

#include <bits/stdc +.h>

using namespace std;

int sz = 8;
void FCFS(int arr[], int head) {
int seek_count = 0;
int distance, cur_track;
for (int i = 0; i < sz; i +) {
cur_track = arr[i];
distance = abs(cur_track - head);
seek_count += distance;
head = cur_track;
}
cout < "Total number of seek operations = " <
seek_count < endl;
cout < "Seek Sequence is" < endl;
for (int i = 0; i < sz; i +) {
cout < arr[i] < endl;
}
}
int main() {
/ request array
int arr[sz] = {
176,
79,
34,

Downloaded by veenit kumar ([email protected])

 lOMoARcPSD|12838665

60,
92,
11,
41,
114
};
int head = 50;
FCFS(arr, head);
return 0;
}

Downloaded by veenit kumar ([email protected])