Department of Computer Science and Engineering

Operating System Lab

(BCS-451)

Name_________________________________________

Roll No________________________________________

Year___________________________________________

Submitted By ______________________ Submitted To ______________________

 Index
Exp. Name of the Experiment Date Remarks
No.
1 Study of hardware and software
requirements of different operating systems
(UNIX, LINUX, WINDOWS XP,
WINDOWS7/8 )

2 Execute various UNIX system calls for :

i. Process management
ii. ii. File management
iii. Input/output Systems calls

3 Implement CPU Scheduling Policies:

i. SJF ii. Priority
iii. FCFS iv. Multi-level Queue

4 Implement file storage allocation technique:

i. Contiguous (using array)
ii. Linked –list (using linked-list)
iii. Indirect allocation (indexing)

5 Implementation of contiguous allocation

techniques:
i. Worst-Fit
ii. Best- Fit
iii. First- Fit

6 Calculation of external and internal

fragmentation
i. Free space list of blocks from system
ii. List process file from the system

7 Implementation of compaction for the

continually changing memory layout and
calculate total movement of data.

8 Implementation of resource allocation graph

RAG)

9 Implementation of Banker’s algorithm.

10 Conversion of resource allocation graph

(RAG) to wait for graph (WFG) for each
type of method used for storing graph.
 Program No: 01
Aim: To study of hardware and software requirements of different operating systems (UNIX, LINUX,
WINDOWS XP, WINDOWS 10)

Content: An operating system acts as an intermediary between the user of a computer and computer
hardware. The purpose of an operating system is to provide an environment in which a user can execute
programs conveniently and efficiently.
An operating system is a program that controls the execution of application programs and acts as an
interface between the user of a computer and the computer hardware.

There are various types of Operating System used throughout the world and this depends mainly on the
type of operations performed. Most commonly used operating systems are as follows:
● Windows 10, 8, 7, XP
● LINUX
● UNIX
● Mac OS

Hardware and Software Minimum Requirements

All computer software needs certain hardware components or other software resources to be present on a
computer.
Software Requirements
Software requirements deal with defining software resource requirements and prerequisites that need to be
installed on a computer to provide optimal functioning of an application such as Platform, APIs and
drivers, Web browser etc.
Hardware Requirements
The most common set of requirements defined by any operating system or software application is the
physical computer resources, also known as hardware. A hardware requirements list is often accompanied
by a hardware compatibility list (HCL), especially in case of operating systems.
1. WINDOWS 10
i. Processor: 1 gigahertz (GHz) or faster processor or SoC
ii. RAM: 1 gigabyte (GB) for 32-bit or 2 GB for 64-bit
iii. Hard disk space: 16 GB for 32-bit OS or 20 GB for 64-bit OS
iv. Graphics card: Direct X 9 or later with WDDM 1.0 driver
v. Display: 800 x 6009 with WDDM driver

2. WINDOWS XP
The minimum hardware requirements for Windows XP Home Edition are:
i. Pentium 233-megahertz (MHz) processor or faster (300 MHz is recommended)
ii. At least 64 megabytes (MB) of RAM (128 MB is recommended)
iii. At least 1.5 gigabytes (GB) of available space on the hard disk
iv. CD-ROM or DVD-ROM drive
v. Keyboard and a Microsoft Mouse or some other compatible pointing device
vi. Video adapter and monitor with Super VGA (800 x 600) or higher resolution
vii. Sound card
viii. Speakers or headphones
3. UNIX OS
i. RAM: 1 GB
ii. Processor: IBM 604e processor with a clock speed of 375 MHz or faster
iii. Free disk space: /tmp must have 1 GB free disk space. If Tivoli Identity Manager installs
WebSphere Application Server, (WAS_HOMEI must have 800 MB free disk space and /var must
have 300 MB free disk space. Allocate 500 MB for /itim45.
4. LINUX
i. 32-bit Intel-compatible processor running at 2 GHz or greater
ii. 512 MB RAM
iii. Disk space: 2.5 GB for Pipeline Pilot server plus components
iv. A DVD-ROM drive.
 Program No: 02
AIM: Execute various UNIX system calls for:
 Process management
 File management
 Input/output Systems calls

Content: The interface between a process and an operating system is provided by system calls. In
general, system calls are available as assembly language instructions. They are also included in the
manuals used by the assembly level programmers.
UNIX System Calls
System calls in Unix are used for file system control, process control, interprocess communication etc.
Access to the Unix kernel is only available through these system calls. Generally, system calls are similar
to function calls; the only difference is that they remove the control from the user process.
There are around 80 system calls in the Unix interface currently. Details about some of the important ones
are given as follows -

System Call Description

access() This checks if a calling process has access to the required file

chdir() The chdir command changes the current directory of the system

chmod() The mode of a file can be changed using this command

chown() This changes the ownership of a particular file

kill() This system call sends kill signal to one or more processes

link() A new file name is linked to an existing file using link system call.

open() This opens a file for the reading or writing process

pause() The pause call suspends a file until a particular signal occurs.

stime() This system call sets the correct time.

times() Gets the parent and child process times

alarm() The alarm system call sets the alarm clock of a process

fork() A new process is created using this command

chroot() This changes the root directory of a file.

exit() The exit system call is used to exit a process.

System call Description

GENERAL CLASS SPECIFIC CLASS SYSTEM CALL

---------------------------------------------------------------------
File Structure Creating a Channel creat()
Related Calls open()
close()
Input/Output read()
write()
Random Access lseek()
Channel Duplication dup()
Aliasing and Removing link()
Files unlink()
File Status stat()
fstat()
Access Control access()
chmod()
chown()
umask()
Device Control ioctl()
---------------------------------------------------------------------
Process Related Process Creation and exec()
Calls Termination fork()
wait()
exit()
Process Owner and Group getuid()
geteuid()
getgid()
getegid()
Process Identity getpid()
getppid()
Process Control signal()
kill()
alarm()
Change Working Directory chdir()
----------------------------------------------------------------------
Interprocess Pipelines pipe()
Communication Messages msgget()
msgsnd()
msgrcv()
msgctl()
Semaphores semget()
semop()
Shared Memory shmget()
shmat()
shmdt()

/* errmsg1.c print all system error messages using "perror()" */

#include <stdio.h>

int main()
{
int i;
extern int errno, sys_nerr;
 for (i = 0; i < sys_nerr; ++i)
{
fprintf(stderr, "%3d",i);
errno = i;
perror(" ");
}
exit (0);
}

/* errmsg2.c print all system error messages using the global error message table. */

#include <stdio.h>

int main()
{
int i;
extern int sys_nerr;
extern char *sys_errlist[];

fprintf(stderr,"Here are the current %d error messages:\n\n",sys_nerr);

for (i = 0; i < sys_nerr; ++i)
fprintf(stderr,"%3d: %s\n", i, sys_errlist[i]);
}

/* creat.c */

#include <stdio.h>
#include <sys/types.h> /* defines types used by sys/stat.h */
#include <sys/stat.h> /* defines S_IREAD & S_IWRITE */
int main()
{
int fd;
fd = creat("[Link]", S_IREAD | S_IWRITE);
if (fd == -1)
printf("Error in opening [Link]\n");
else
{
printf("[Link] opened for read/write access\n");
printf("[Link] is currently empty\n");
}

close(fd);
exit (0);
}
The following is a sample of the manifest constants for the mode
argument as defined in /usr/include/sys/stat.h:

#define S_IRWXU 0000700 /* -rwx------ */

#define S_IREAD 0000400 /* read permission, owner */
#define S_IRUSR S_IREAD
#define S_IWRITE 0000200 /* write permission, owner */
 #define S_IWUSR S_IWRITE
#define S_IEXEC 0000100 /* execute/search permission, owner */
#define S_IXUSR S_IEXEC
#define S_IRWXG 0000070 /* ----rwx--- */
#define S_IRGRP 0000040 /* read permission, group */
#define S_IWGRP 0000020 /* write " " */
#define S_IXGRP 0000010 /* execute/search " " */
#define S_IRWXO 0000007 /* -------rwx */
#define S_IROTH 0000004 /* read permission, other */
#define S_IWOTH 0000002 /* write " " */
#define S_IXOTH 0000001 /* execute/search " " */
open ()

Next is the open() system call. open() lets you open a file for
reading, writing, or reading and writing.
The prototype for the open() system call is:

#include <fcntl.h>
int open(file_name, option_flags [, mode])
char *file_name;
int option_flags, mode;

Where file_name is a pointer to the character string that names the file, option flags represent the type of
channel, and mode defines the file's access permissions if the file is being [Link] allowable
option_flags as defined in "/usr/include/fcntl.h" are:
#define O_RDONLY 0 /* Open the file for reading only */
#define O_WRONLY 1 /* Open the file for writing only */
#define O_RDWR 2 /* Open the file for both reading and writing*/
#define O_NDELAY 04 /* Non-blocking I/O */
#define O_APPEND 010 /* append (writes guaranteed at the end) */
#define O_CREAT 00400 /*open with file create (uses third open arg) */
#define O_TRUNC 01000 /* open with truncation */
#define O_EXCL 02000 /* exclusive open */
if (read(fd, buffer, sizeof(message)) == sizeof(message))
printf("\"%s\" was written to [Link]\n", buffer);
else
printf("*** error reading [Link] ***\n");
close (fd);
}
else
printf("*** [Link] already exists ***\n");
exit (0);
 Program No: 03
Aim: Implement CPU Scheduling Policies:

I. SJF
II. Priority
III. FCFS

I. Program for Shortest Job First (SJF) Algorithm

#include<stdio.h>
#include<conio.h>

int main()
{
int bt[20],p[20],wt[20],tat[20],i,j,n,total=0,pos,temp;
float avg_wt,avg_tat;
printf("Enter number of process:");
scanf("%d",&n);

printf("nEnter Burst Time:n");

for(i=0;i<n;i++)
{
printf("p%d:",i+1);
scanf("%d",&bt[i]);
p[i]=i+1;
}

//sorting of burst times

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

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=(float)total/n;
total=0;
 printf("nProcesst Burst Time tWaitingTimetTurnaround Time");
for(i=0;i<n;i++)
{
tat[i]=bt[i]+wt[i];
total+=tat[i];
printf("np%dtt %dtt %dttt%d",p[i],bt[i],wt[i],tat[i]);
}
avg_tat=(float)total/n;
printf("nnAverage Waiting Time=%f",avg_wt);
printf("nAverage Turnaround Time=%fn",avg_tat);
getch();

}
Output:

II. Program for Priority Scheduling Algorithm

#include<stdio.h>
#include<conio.h>
void main()
{
int x,n,p[10],pp[10],pt[10],w[10],t[10],awt,atat,i;
printf("Enter the number of process : ");
scanf("%d",&n);
printf("\n Enter process : time priorities \n");
for(i=0;i<n;i++)
{
printf("\nProcess no %d : ",i+1);
scanf("%d %d",&pt[i],&pp[i]);
p[i]=i+1;
}
for(i=0;i<n-1;i++)
{
for(int j=i+1;j<n;j++)
{
if(pp[i]<pp[j])
{
x=pp[i];
pp[i]=pp[j];
pp[j]=x;
x=pt[i];
pt[i]=pt[j];
pt[j]=x;
x=p[i];
p[i]=p[j];
p[j]=x;
}
}
}
w[0]=0;
awt=0;

t[0]=pt[0];
atat=t[0];

for(i=1;i<n;i++)
{
w[i]=t[i-1];
awt+=w[i];
t[i]=w[i]+pt[i];
atat+=t[i];
}
printf("\n\n Job \t Burst Time \t Wait Time \t Turn Around Time Priority \n");
for(i=0;i<n;i++)
printf("\n %d \t\t %d \t\t %d \t\t %d \t\t %d \n",p[i],pt[i],w[i],t[i],pp[i]);
awt/=n;
atat/=n;
printf("\n Average Wait Time : %d \n",awt);
printf("\n Average Turn Around Time : %d \n",atat);
getch();
}

Output:

Enter the number of process : 4

E Enter process : time priorities
P Process no 1 : 3 1
P Process no 2 : 4 2
P Process no 3 : 5 3
P Process no 4 : 6 4
Job Burst Time Wait Time Turn Around Time Priority
4 6 0 6 4
3 5 6 11 3
2 4 11 15 2
1 3 15 18 1
Average Wait Time : 8 Average Turn Around Time : 12
 III. Program for FCFS (First Come First Served) Scheduling Algorithm:

#include<stdio.h>
#include<conio.h>
int main()
{
int n,bt[20],wt[20],tat[20],avwt=0,avtat=0,i,j;
printf("Enter total number of processes(maximum 20):");
scanf("%d",&n);
printf("nEnter Process Burst Timen");
for(i=0;i<n;i++)
{
printf("P[%d]:",i+1);

scanf("%d",&bt[i]);
}

wt[0]=0;

for(i=1;i<n;i++)
{
wt[i]=0;
for(j=0;j<i;j++)
wt[i]+=bt[j];
}
printf("nProcessttBurstTimetWaitingTimetTurnaround Time");
for(i=0;i<n;i++)
{
tat[i]=bt[i]+wt[i];
avwt+=wt[i];
avtat+=tat[i];
printf("nP[%d]tt%dtt%dtt%d",i+1,bt[i],wt[i],tat[i]);
}

avwt/=i;
avtat/=i;
printf("nnAverage Waiting Time:%d",avwt);
printf("nAverage Turnaround Time:%d",avtat);
getch();
}

Output:

Processes Burst time Waiting time Turn around time

1 1 10 0 10
2 2 5 10 15
3 3 8 15 23
Average waiting time = 8.33333
A Average turnaround time = 16
 Program No: 04
Aim: Write a program to implement various File Allocation methods.

1. Sequential File Allocation method

Program:
#include<stdio.h>
#include<conio.h>
main()
{
int n,i,j,b[20],sb[20],t[20],x,c[20][20];
clrscr();
printf("Enter [Link] files:");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Enter no. of blocks occupied by file%d",i+1);
scanf("%d",&b[i]);
printf("Enter the starting block of file%d",i+1);
scanf("%d",&sb[i]);
t[i]=sb[i];
for(j=0;j<b[i];j++)
c[i][j]=sb[i]++;
}
printf("Filename\tStart block\tlength\n");
for(i=0;i<n;i++)
printf("%d\t %d \t%d\n",i+1,t[i],b[i]);
printf("Enter file name:");
scanf("%d",&x);
printf("File name is:%d",x);
printf("length is:%d",b[x-1]);
printf("blocks occupied:");
for(i=0;i<b[x-1];i++)
printf("%4d",c[x-1][i]);
getch();
}

Output:

Enter no of files: 2
Enter no. of blocks occupied by file1 4
Enter the starting block of file1 2
Enter no. of blocks occupied by file2 10
Enter the starting block of file2 5
Filename Start block length
124
2 5 10
Enter file name: rajesh
File name is:12803 length is:0blocks occupied
 2. Linked File Allocation method

Program:
#include<stdio.h>
#include<conio.h>
struct file
{
char fname[10];
int start,size,block[10];
}f[10];
main()
{
int i,j,n;
clrscr();
printf("Enter no. of files:");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Enter file name:");
scanf("%s",&f[i].fname);
printf("Enter starting block:");
scanf("%d",&f[i].start);
f[i].block[0]=f[i].start;
printf("Enter [Link] blocks:");
scanf("%d",&f[i].size);
printf("Enter block numbers:");
for(j=1;j<=f[i].size;j++)
{
scanf("%d",&f[i].block[j]);
}
}
printf("File\tstart\tsize\tblock\n");
for(i=0;i<n;i++)
{
printf("%s\t%d\t%d\t",f[i].fname,f[i].start,f[i].size);
for(j=1;j<=f[i].size-1;j++)
printf("%d--->",f[i].block[j]);
printf("%d",f[i].block[j]);
printf("\n");
}
getch();
}
Output:

Enter no. of files:2

Enter file name: venkat
Enter starting block:20
Enter [Link] blocks:6
Enter block numbers: 4
12
15
45
32
25
Enter file name:rajesh
Enter starting block:12
Enter [Link] blocks:5
Enter block numbers:6
5 5
4
3
2
File start size block
venkat 20 6 4--->12--->15--->45--->32--->25
rajesh 12 5 6--->5--->4--->3--->2

3. Indexed File Allocation method

Program:
#include<stdio.h>
#include<conio.h>
main()
{
int n,m[20],i,j,sb[20],s[20],b[20][20],x;
clrscr();
printf("Enter no. of files:");
scanf("%d",&n);
for(i=0;i<n;i++)
{ printf("Enter starting block and size of file%d:",i+1);
scanf("%d%d",&sb[i],&s[i]);
printf("Enter blocks occupied by file%d:",i+1);
scanf("%d",&m[i]);
printf("enter blocks of file%d:",i+1);
for(j=0;j<m[i];j++)
scanf("%d",&b[i][j]);
} printf("\nFile\t index\tlength\n");
for(i=0;i<n;i++)
{
 printf("%d\t%d\t%d\n",i+1,sb[i],m[i]);
}printf("\nEnter file name:");

scanf("%d",&x);
printf("file name is:%d\n",x);
i=x-1;
printf("Index is:%d",sb[i]);
printf("Block occupied are:");
for(j=0;j<m[i];j++)

printf("%3d",b[i][j]);
getch();
}

Output:

Enter no. of files: 2

Enter starting block and size of file1: 2 5
Enter blocks occupied by file1:10
Enter blocks of file1:3
254672647
Enter starting block and size of file2: 3 4
Enter blocks occupied by file2:5
Enter blocks of file2: 2 3 4 5 6
File index length
1 2 10
235
Enter file name: venkat
file name is:12803
Index is:0
 Program No: 05
Aim: Write a program to simulate the contiguous memory allocation techniques.
(a) First Fit
(b) Best Fit
(c) Worst Fit

(a) First Fit

Program:

#include<stdio.h>
void main()
{
int bsize[10], psize[10], bno, pno, flags[10], allocation[10], i, j;
for(i = 0; i< 10; i++)
{
flags[i] = 0;
allocation[i] = -1;

}
printf("Enter no. of blocks: ");
scanf("%d", &bno);
printf("\nEnter size of each block: ");
for(i = 0; i<bno; i++)
scanf("%d", &bsize[i]);

printf("\nEnter no. of processes: ");

scanf("%d", &pno);
printf("\nEnter size of each process: ");
for(i = 0; i<pno; i++)
scanf("%d", &psize[i]);
for(i = 0; i<pno; i++) //allocation as per first fit
for(j = 0; j <bno; j++)
if(flags[j] == 0 &&bsize[j] >= psize[i])
{
allocation[j] = i;
flags[j] = 1;
break;
}
//display allocation details
printf("\nBlock no.\tsize\t\tprocess no.\t\tsize");
for(i = 0; i<bno; i++)
{
printf("\n%d\t\t%d\t\t", i+1, bsize[i]);
if(flags[i] == 1)
printf("%d\t\t\t%d",allocation[i]+1,psize[allocation[i]]);
else
printf("Not allocated");
}
}
Output:

(b) Best Fit

Program:

#include<stdio.h>
void main()
{
int fragment[20],b[20],p[20],i,j,nb,np,temp,lowest=9999;
static int barray[20],parray[20];
printf("\n\t\t\tMemory Management Scheme - Best Fit");
printf("\nEnter the number of blocks:");
scanf("%d",&nb);
printf("Enter the number of processes:");
scanf("%d",&np);
printf("\nEnter the size of the blocks:-\n");
for(i=1;i<=nb;i++)
{
printf("Block no.%d:",i);
scanf("%d",&b[i]);
}
printf("\nEnter the size of the processes :-\n");
for(i=1;i<=np;i++)
{
printf("Process no.%d:",i);
scanf("%d",&p[i]);
}
for(i=1;i<=np;i++)
{
for(j=1;j<=nb;j++)
{
if(barray[j]!=1)
{
temp=b[j]-p[i];
if(temp>=0)
if(lowest>temp)
{
parray[i]=j;
lowest=temp;
}
}
}
fragment[i]=lowest;
barray[parray[i]]=1;
lowest=10000;
}
printf("\nProcess_no\tProcess_size\tBlock_no\tBlock_size\tFragment");

for(i=1;i<=np &&parray[i]!=0;i++)
printf("\n%d\t\t%d\t\t%d\t\t%d\t\t%d",i,p[i],parray[i],b[parray[i]],fragment[i]);
}
Output:

(c) Worst Fit:

Program:
#include<stdio.h>
#include<conio.h>
#define max 25

void main()
{
int frag[max],b[max],f[max],i,j,nb,nf,temp,highest=0;
static int bf[max],ff[max];
clrscr();
printf("\n\tMemory Management Scheme - Worst Fit");
printf("\nEnter the number of blocks:");
scanf("%d",&nb);
printf("Enter the number of files:");
scanf("%d",&nf);
printf("\nEnter the size of the blocks:-\n");
for(i=1;i<=nb;i++) {printf("Block %d:",i);scanf("%d",&b[i]);}
printf("Enter the size of the files :-\n");
for(i=1;i<=nf;i++) {printf("File %d:",i);scanf("%d",&f[i]);}

for(i=1;i<=nf;i++)
{
for(j=1;j<=nb;j++)
{
if(bf[j]!=1) //if bf[j] is not allocated
{
temp=b[j]-f[i];
if(temp>=0)
if(highest<temp)
{
ff[i]=j;
highest=temp;
}
}
}
frag[i]=highest;
bf[ff[i]]=1;
highest=0;
}
printf("\nFile_no:\tFile_size :\tBlock_no:\tBlock_size:\tFragement");
for(i=1;i<=nf;i++)
printf("\n%d\t\t%d\t\t%d\t\t%d\t\t%d",i,f[i],ff[i],b[ff[i]],frag[i]);
getch();
}

Output:

Process No. Process Size Block no.

1 40 4
2 10 1
3 30 2
4 60 Not Allocated
 Program No: 06
Aim: Calculation of external and internal fragmentation
i. Free space list of blocks from system.
ii. List process file from the system.

Content: Types of Fragmentation

There are mainly two types of fragmentation in the operating system. These are as follows:
1. Internal Fragmentation
2. External Fragmentation
Internal Fragmentation

When a process is allocated to a memory block, and if the process is smaller than the amount of memory
requested, a free space is created in the given memory block. Due to this, the free space of the memory
block is unused, which causes internal fragmentation.
3. External Fragmentation:
External fragmentation happens when there’s a sufficient quantity of area within the memory to
satisfy the memory request of a method. However, the process’s memory request cannot be
fulfilled because the memory offered is in a non-contiguous manner. Whether you apply a first-fit
or best-fit memory allocation strategy it’ll cause external fragmentation.
 Difference between Internal fragmentation and External fragmentation

[Link] Internal fragmentation External fragmentation

In external fragmentation, variable-sized

In internal fragmentation fixed-sized memory,
memory blocks square measure appointed to the
blocks square measure appointed to process.
1. method.

Internal fragmentation happens when the External fragmentation happens when the
2. method or process is smaller than the memory. method or process is removed.

The solution of internal fragmentation is The solution to external fragmentation is

3. the best-fit block. compaction and paging.

External fragmentation occurs when memory is

Internal fragmentation occurs when memory is
divided into variable size partitions based on the
divided into fixed-sized partitions.
4. size of processes.

The unused spaces formed between non-

The difference between memory allocated and
contiguous memory fragments are too small to
required space or memory is called Internal
serve a new process, which is called External
fragmentation.
5. fragmentation.

Internal fragmentation occurs with paging and External fragmentation occurs with segmentation
6. fixed partitioning. and dynamic partitioning.

It occurs on the allocation of a process to a

It occurs on the allocation of a process to a
partition greater than the process’s
partition greater which is exactly the same
requirement. The leftover space causes
memory space as it is required.
7. degradation system performance.

It occurs in worst fit memory allocation It occurs in best fit and first fit memory
8. method. allocation method
 Program No: 07
Aim: Implementation of compaction for the continually changing memory layout and calculate total
movement of data.
Content: Compaction is a technique to collect all the free memory present in form of fragments into one
large chunk of free memory, which can be used to run other processes.
It does that by moving all the processes towards one end of the memory and all the available free space
towards the other end of the memory so that it becomes contiguous.
It is not always easy to do compaction. Compaction can be done only when the relocation is dynamic
and done at execution time. Compaction cannot be done when relocation is static and is performed at
load time or assembly time.

Before Compaction
Before compaction, the main memory has some free space between occupied space. This condition is
known as external fragmentation. Due to less free space between occupied spaces, large processes
cannot be loaded into them.

Main Memory

Occupied space

Free space

Occupied space

Occupied space

Free space

After Compaction
After compaction, all the occupied space has been moved up and the free space at the bottom. This
makes the space contiguous and removes external fragmentation. Processes with large memory
requirements can be now loaded into the main memory.

Main Memory

Occupied
space

Occupied
space

Occupied
space

Free space

Free space

Purpose of Compaction in Operating System

While allocating memory to process, the operating system often faces a problem when there’s a
sufficient amount of free space within the memory to satisfy the memory demand of a process. however
the process’s memory request can’t be fulfilled because the free memory available is in a non-
contiguous manner, this problem is referred to as external fragmentation. To solve such kinds of
problems compaction technique is used.

C code for Contiguous File Allocation using Compaction algorithm

#include<stdio.h>
#include<conio.h>

void create(int,int);
void del(int);
void compaction();
void display();

int fname[10],fsize[10],fstart[10],freest[10],freesize[10],m=0,n=0,start;

int main()
{
int name,size,ch,i;
int *ptr;
// clrscr();
ptr=(int *)malloc(sizeof(int)*100);
start=freest[0]=(int)ptr;
freesize[0]=500;

printf("\n\n");

printf(" Free start address Free Size \n\n");

for(i=0;i<=m;i++)
printf("%d%d\n",freest[i],freesize[i]);
printf("\n\n");
while(1)
{

printf("[Link].\n");
printf("[Link].\n");
printf("[Link].\n");
 printf("[Link].\n");
printf("Enter your choice: ");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("\nEnter the name of file: ");
scanf("%d",&name);
printf("\nEnter the size of the file: ");
scanf("%d",&size);
create(name,size);
break;
case 2:
printf("\nEnter the file name which u want to delete: ");
scanf("%d",&name);
del(name);
break;
case 3:
compaction();
printf("\nAfter compaction the tables will be:\n");
display();
break;
case 4:
exit(1);
default:
printf("\nYou have entered a wrong choice.\n");
}
}

void create(int name,int size)

{
int i,flag=1,j,a;
for(i=0;i<=m;i++)
if( freesize[i] >= size)
a=i,flag=0;
if(!flag)
{
for(j=0;j<n;j++);
n++;
fname[j]=name;

fsize[j]=size;

fstart[j]=freest[a];
freest[a]=freest[a]+size;
freesize[a]=freesize[a]-size;
printf("\n The memory map will now be: \n\n");
display();
}
else
{
printf("\nNo enough space is [Link] compaction......");
flag=1;
compaction();
 display();
for(i=0;i<=m;i++)
if( freesize[i] >= size)
a=i,flag=0;
if(!flag)
{
for(j=0;j<n;j++);
n++;
fname[j]=name;
fsize[j]=size;
fstart[j]=freest[a];
freest[a]+=size;
freesize[a]-=size;
printf("\n The memory map will now be: \n\n");
display();
}
else
printf("\nNo enough space.\n");
}
}
void del(int name)
{
int i,j,k,flag=1;
for(i=0;i<n;i++)
if(fname[i]==name)
break;
if(i==n)
{
flag=0;
printf("\nNo such process exists......\n");
}
else
{
m++;
freest[m]=fstart[i];
freesize[m]=fsize[i];
for(k=i;k<n;k++)
{
fname[k]=fname[k+1];
fsize[k]=fsize[k+1];
fstart[k]=fstart[k+1];
}
n--;
}

if(flag)
{
printf("\n\n After deletion of this process the memory map will be : \n\n");
display();
}
}

void compaction()
{

int i,j,size1=0,f_size=0;
if(fstart[0]!=start)
 {
fstart[0]=start;
for(i=1;i<n;i++)
fstart[i]=fstart[i-1]+fsize[i-1];
}
else
{
for(i=1;i<n;i++)
fstart[i]=fstart[i-1]+fsize[i-1];
}
f_size=freesize[0];

for(j=0;j<=m;j++)
size1+=freesize[j];
freest[0]=freest[0]-(size1-f_size);
freesize[0]=size1;
m=0;
}

void display()
{
int i;

printf("\n *** MEMORY MAP TABLE *** \n");

printf("\n\nNAME SIZE STARTING ADDRESS \n\n");
for(i=0;i<n;i++)
printf(" %d%10d%10d\n",fname[i],fsize[i],fstart[i]);
printf("\n\n");
printf("\n\n*** FREE SPACE TABLE ***\n\n");
printf("FREE START ADDRESS FREE SIZE \n\n");
for(i=0;i<=m;i++)
printf("%d%d\n",freest[i],freesize[i]);
}

Output Of the above program:-

 Program No: 08
Aim: Implementation of resource allocation graph (RAG).

Content: The resource allocation graph is the pictorial representation of the state of a system. As its
name suggests, the resource allocation graph is the complete information about all the processes which are
holding some resources or waiting for some resources. It also contains the information about all the
instances of all the resources whether they are available or being used by the processes.

RAG also contains vertices and edges

In RAG vertices are mainly of two types, Resource and process. Each of them will be represented by a
different shape. Circle represents process while rectangle represents resource. There are two types of
edges in RAG –
1. Assign Edge – If you already assign a resource to a process then it is called Assign edge.
2. Request Edge – It means in future the process might want some resource.
Example of Single Instances RAG

In the above single instances RAG example, it can be seen that P2 is holding the R1 and waiting
for R3. P1 is waiting for R1 and holding R2 and, P3 is holding the R3 and waiting for R2. So, it can be
concluded that none of the processes will get executed. In the case of Multiple Instances RAG, it becomes
difficult to analyze from the RAG that the system is in a safe state or not.

//LIST OF HEADER FILES

#include<stdio.h>
#include<conio.h>
int proc,res,i,j,row=0,flag=0;
static int pro[3][3],req[3][3],st_req[3][3],st_pro[3][3];
void main()
{
clrscr();
printf("\nEnter the number of Processes:");
scanf("%d",&proc);
printf("\nEnter the number of Resources:");
scanf("%d",&res);
printf("\nEnter the Process Matrix:");
for(i=0;i<proc;i++)
for(j=0;j<res;j++)
scanf("%d",&pro[i][j]);
printf("\nEnter the Request Matrix:");
for(i=0;i<res;i++)
for(j=0;j<proc;j++)
scanf("%d",&req[i][j]);
row=0;
while(!kbhit())
{
for(i=0;i<res;i++)
{
if(pro[row][i]==1)
{
if(st_pro[row][i]>1 && flag==1)
{
printf("\nDeadlock Occured");
getch();
exit(0);
}
st_pro[row][i]++;
row=i;
break;
}
}
for(i=0;i<proc;i++)
{
if(req[row][i]==1)
{
if(st_req[row][i]>1)
{
printf("\nDeadlock Occured");
getch();
exit(0);
}
st_req[row][i]++;
row=i;
flag=1;
break;
}
}
}
cprintf("\nNo Deadlock Detected");
getch();
getch();
}
 Program No: 09
Aim: Write a program to simulate Banker’s Algorithm for the purpose of Deadlock Avoidance.
Program:
#include<stdio.h>
#include<conio.h>
int max[100][100];
int alloc[100][100];
int need[100][100];
int avail[100];
int n,r;
void input();
void show();
void cal();
int main()
{
int i,j;
printf("********** Banker's Algo ************\n");
input();
show();
cal();
getch();
return 0;
}
void input()
{
int i,j;
printf("Enter the no of Processes\t");
scanf("%d",&n);
printf("Enter the no of resources instances\t");
scanf("%d",&r);
printf("Enter the Max Matrix\n");
for(i=0;i<n;i++)< span="" style="box-sizing: border-box;">
{
for(j=0;j<r;j++)< span="" style="box-sizing: border-box;">
{
scanf("%d",&max[i][j]);
}
}
printf("Enter the Allocation Matrix\n");
for(i=0;i<n;i++)< span="" style="box-sizing: border-box;">
{
for(j=0;j<r;j++)< span="" style="box-sizing: border-box;">
{
scanf("%d",&alloc[i][j]);
}
}
printf("Enter the available Resources\n");
for(j=0;j<r;j++)< span="" style="box-sizing: border-box;">
{
scanf("%d",&avail[j]);
}
}
void show()
{
int i,j;
printf("Process\t Allocation\t Max\t Available\t");
for(i=0;i<n;i++)< span="" style="box-sizing: border-box;">
{
printf("\nP%d\t ",i+1);
for(j=0;j<r;j++)< span="" style="box-sizing: border-box;">
{
printf("%d ",alloc[i][j]);
}
printf("\t");
for(j=0;j<r;j++)< span="" style="box-sizing: border-box;">
{
printf("%d ",max[i][j]);
}
printf("\t");
if(i==0)
{
for(j=0;j<r;j++)< span="" style="box-sizing: border-box;">
printf("%d ",avail[j]);
}
}
}
void cal()
{
int finish[100],temp,need[100][100],flag=1,k,c1=0;
int safe[100];
int i,j;
for(i=0;i<n;i++)< span="" style="box-sizing: border-box;">
{
finish[i]=0;
}
//find need matrix
for(i=0;i<n;i++)< span="" style="box-sizing: border-box;">
{
for(j=0;j<r;j++)< span="" style="box-sizing: border-box;">
{
need[i][j]=max[i][j]-alloc[i][j];
}
}
printf("\n");
while(flag)
{
flag=0;
for(i=0;i<n;i++)< span="" style="box-sizing: border-box;">
{
int c=0;
for(j=0;j<r;j++)< span="" style="box-sizing: border-box;">
{
if((finish[i]==0)&&(need[i][j]<=avail[j]))
{
c++;
if(c==r)
{
for(k=0;k<r;k++)< span="" style="box-sizing: border-box;">
{
avail[k]+=alloc[i][j];
 finish[i]=1;
flag=1;
}
printf("P%d->",i);
if(finish[i]==1)
{
i=n;
}
}
}
}
}
}
for(i=0;i<n;i++)< span="" style="box-sizing: border-box;">
{
if(finish[i]==1)
{
c1++;
}
else
{
printf("P%d->",i);
}
}
if(c1==n)
{
printf("\n The system is in safe state");
}
else
{
printf("\n Process are in dead lock");
printf("\n System is in unsafe state");
}
}

Output:

Enter the no of processes 5

Enter the no of resources instances 3
Enter the max matrix
753
322
902
222
433
Enter the allocation matrix
010
200
302
211
002
Enter available resources 3 2 2
P1->p3->p4->p2->p0->
The system is in safe state.
 Program No: 10
Program: Conversion of resource allocation graph (RAG) to wait for graph (WFG) for each type of
method used for storing graph.
.
IMPLEMENTATION DETAILS:

One such deadlock detection algorithm makes use of a wait-for graph to track which other processes a
process is currently blocking on. In a wait-for graph, processes are represented as nodes, and an edge
from process Pi to Pj implies Pj is holding a resource that Pi needs and thus Pi is waiting for Pj to
release its lock on that resource. There may be processes waiting for more than a single resource
to become available. Graph cycles imply the possibility of a deadlock.

INPUT/s:

Output of experiment 7 as Resource allocation graph (RAG) through adjacency

matrices/list.

STEPS TO PERFORM:

(i) Identify the waiting processes in the RAG.

(ii) Accordingly draw Wait-for graph for the given RAG.
(iii) To draw it as graphical representation, we introduce graphics.h and work in graphics
mode.
(iv) Geometric images are entered by entering graphics, providing with parameter and
closing graphics.
(v) We now identify circular chain of dependency (i.e., appearance of loops in the graph)

OUTPUT

(i) The wait-for-graph(graphical representation).

(ii) Also, check presence of loop to detect if loop is present